imported>GreenC bot: Move 15 urls. Wayback Medic 2.5 per WP:URLREQ#citeftp

2025-05-27T09:30:24Z

Move 15 urls. Wayback Medic 2.5 per WP:URLREQ#citeftp

New page

{{primary sources|date=March 2018}}
In [[computer programming]], '''feature-oriented programming''' ('''FOP''') or '''feature-oriented software development''' ('''FOSD''') is a [[programming paradigm]] for program generation in [[software product lines]] (SPLs) and for incremental development of programs.

== History ==
[[File:StackingLayers.jpg|thumb|upright=0.4|right|alt=vertical stacking of layers|Connection between layer stacks and transformation compositions]]
FOSD arose out of layer-based designs and levels of abstraction in network protocols and extensible database systems in the late-1980s.<ref name="genvoca">{{cite web | title=Design and Implementation of Hierarchical Software Systems with Reusable Components | archive-url=https://web.archive.org/web/20170706123320/ftp://ftp.cs.utexas.edu/pub/predator/tosem-92.pdf | archive-date=2017-07-06 | url-status=dead | url=ftp://ftp.cs.utexas.edu/pub/predator/tosem-92.pdf}}</ref> A program was a stack of layers. Each layer added functionality to previously composed layers and different compositions of layers produced different programs. Not surprisingly, there was a need for a compact language to express such designs. Elementary algebra fit the bill: each layer was a function (a [[program transformation]]) that added new code to an existing program to produce a new program, and a program's design was modeled by an expression, i.e., a composition of transformations (layers). The figure to the left illustrates the stacking of layers i, j, and h (where h is on the bottom and i is on the top). The algebraic notations i(j(h)), i•j•h, and i+j+h have been used to express these designs.

Over time, layers were equated to features, where a ''feature'' is an increment in program functionality. The paradigm for program design and generation was recognized to be an outgrowth of relational query optimization, where query evaluation programs were defined as relational algebra expressions, and [[query optimization]] was expression optimization.<ref name="selinger">{{cite book | title=Access Path Selection In Relational Databases | date=30 May 1979 | pages=23–34 | doi=10.1145/582095.582099 | isbn=9780897910019 | s2cid=8537523 | url=http://portal.acm.org/citation.cfm?id=582099}}</ref> A software product line is a family of programs where each program is defined by a unique composition of features. FOSD has since evolved into the study of feature modularity, tools, analyses, and design techniques to support feature-based program generation.

The second generation of FOSD research was on feature interactions, which originated in telecommunications. Later, the term ''feature-oriented programming'' was coined;<ref name="FOP">{{cite web | title=Feature-Oriented Programming: A Fresh Look at Objects | url=http://www4.informatik.tu-muenchen.de/papers/ecoop_prehofer_1997_Publication.html | access-date=2015-12-16 | archive-url=https://web.archive.org/web/20030803215756/http://www4.informatik.tu-muenchen.de/papers/ecoop_prehofer_1997_Publication.html | archive-date=2003-08-03 | url-status=dead }}</ref> this work exposed interactions between layers. Interactions require features to be adapted when composed with other features.

A third generation of research focussed on the fact that every program has multiple representations (e.g., source, makefiles, documentation, etc.) and adding a feature to a program should elaborate each of its representations so that all are consistent. Additionally, some of representations could be generated (or derived) from others. In the sections below, the mathematics of the three most recent generations of FOSD, namely [[#GenVoca|GenVoca]],<ref name="genvoca"/> [[#AHEAD|AHEAD]],<ref name="ahead">{{cite web | title=Scaling Step-Wise Refinement | archive-url=https://web.archive.org/web/20170706122700/ftp://ftp.cs.utexas.edu/pub/predator/TSE-AHEAD.pdf | archive-date=2017-07-06 | url-status=dead | url=ftp://ftp.cs.utexas.edu/pub/predator/TSE-AHEAD.pdf}}</ref> and [[#FOMDD|FOMDD]]<ref name="fomdd"/><ref name="genmeta"/> are described, and links to product lines that have been developed using FOSD tools are provided. Also, four additional results that apply to all generations of FOSD are: [[FOSD metamodels]], [[FOSD program cubes]], and FOSD feature interactions.

== GenVoca ==
'''GenVoca''' (a [[portmanteau]] of the names Genesis and Avoca)<ref name="genvoca"/> is a compositional paradigm for defining programs of product lines. Base programs are 0-ary functions or transformations called '''values''':

f -- base program with feature f
h -- base program with feature h

and features are unary functions/transformations that elaborate (modify, extend, refine) a program:

i + x -- adds feature i to program x
j + x -- adds feature j to program x

where + denotes function composition. The ''design'' of a program is a named expression, e.g.:

p1 = j + f -- program p1 has features j and f
p2 = j + h -- program p2 has features j and h
p3 = i + j + h -- program p3 has features i, j, and h

A '''GenVoca model''' of a domain or software product line is a collection of base programs and features (see [[FOSD metamodels|MetaModels]] and [[FOSD program cubes|Program Cubes]]).
The programs (expressions) that can be created defines a product line. Expression optimization is ''program design optimization'', and expression evaluation is ''program generation''.

: Note: GenVoca is based on the stepwise development of programs: a process that emphasizes design simplicity and understandability, which are key to program comprehension and automated program construction. Consider program p3 above: it begins with base program h, then feature j is added (read: the functionality of feature j is added to the codebase of h), and finally feature i is added (read: the functionality of feature i is added to the codebase of j•h).

: Note: not all combinations of features are meaningful. [[Feature Model|Feature models]] (which can be translated into propositional formulas) are graphical representations that define legal combinations of features.<ref name="splc">{{cite web | title=Feature Models, Grammars, and Propositional Formulas | archive-url=https://web.archive.org/web/20170706123201/ftp://ftp.cs.utexas.edu/pub/predator/splc05.pdf | archive-date=2017-07-06 | url-status=dead | url=ftp://ftp.cs.utexas.edu/pub/predator/splc05.pdf}}</ref>

: Note: A more recent formulation of GenVoca is '''symmetric''': there is only one base program, 0 (the empty program), and all features are unary functions. This suggests the interpretation that GenVoca composes program structures by '''superposition''', the idea that complex structures are composed by superimposing simpler structures.<ref name="amast08">{{cite web | title=An Algebra for Features and Feature Composition | url=http://www.infosun.fim.uni-passau.de/cl/publications/docs/AMAST2008.pdf}}</ref><ref name="symmetric">{{cite web | title=Superimposition: A Language-Independent Approach to Software Composition | url=http://www.infosun.fim.uni-passau.de/cl/publications/docs/SC2008.pdf}}</ref> Yet another reformulation of GenVoca is as a [[monoid]]: a GenVoca model is a set of features with a composition operation (•); composition is associative and there is an identity element (namely 1, the identity function). Although all compositions are possible, not all are meaningful. That's the reason for [[Feature Model|feature models]].

GenVoca features were originally implemented using C preprocessor (<code>#ifdef feature ... #endif</code>) techniques. A more advanced technique, called [[FOSD Mixin Layers|mixin layers]], showed the connection of features to object-oriented collaboration-based designs.

== AHEAD ==
'''Algebraic Hierarchical Equations for Application Design''' ('''AHEAD''')<ref name="ahead"/> generalized GenVoca in two ways. First, it revealed the internal structure of GenVoca values as tuples. Every program has multiple representations, such as source, documentation, bytecode, and makefiles. A GenVoca value is a tuple of program representations. In a product line of parsers, for example, a base parser f is defined by its grammar gf, Java source sf, and documentation df. Parser f is modeled by the tuple f=[gf, sf, df]. Each program representation may have subrepresentations, and they too may have subrepresentations, recursively. In general, a GenVoca value is a tuple of nested tuples that define a hierarchy of representations for a particular program.

:: [[Image:Hierarchy.JPG|thumb|Hierarchical relationships among program artifacts]]
Example. Suppose terminal representations are files. In AHEAD, grammar gf corresponds to a single BNF file, source sf corresponds to a tuple of Java files [c1…cn], and documentation df is a tuple of HTML files [h1…hk]. A GenVoca value (nested tuples) can be depicted as a directed graph: the graph for parser f is shown in the figure to the right. Arrows denote projections, i.e., mappings from a tuple to one of its components. AHEAD implements tuples as file directories, so f is a directory containing file gf and subdirectories sf and df. Similarly, directory sf contains files c1…cn, and directory df contains files h1…hk.

:: Note: Files can be hierarchically decomposed further. Each Java class can be decomposed into a tuple of members and other class declarations (e.g., initialization blocks, etc.). The important idea here is that the mathematics of AHEAD are recursive.

Second, AHEAD expresses features as nested tuples of unary functions called '''deltas'''. Deltas can be '''program refinements''' (semantics-preserving transformations), '''extensions''' (semantics-extending transformations),
or '''interactions''' (semantics-altering transformations). We use the neutral term “delta” to represent all of these possibilities, as each occurs in FOSD.

To illustrate, suppose feature j extends a grammar by Δgj (new rules and tokens are added), extends source code by Δsj (new classes and members are added and existing methods are modified), and extends documentation by Δdj. The tuple of deltas for feature j is modeled by j=[Δgj,Δsj,Δdj], which we call a '''delta tuple'''. Elements of delta tuples can themselves be delta tuples. Example: Δsj represents the changes that are made to each class in sf by feature j, i.e., Δsj=[Δc1…Δcn].
The representations of a program are computed recursively by nested vector addition. The representations for parser p2 (whose GenVoca expression is j+f) are:

p2 = j + f -- GenVoca expression
= [Δgj, Δsj, Δdj] + [gf, sf, df] -- substitution
= [Δgj+gf, Δsj+sf, Δdj+df] -- compose tuples element-wise

That is, the grammar of p2 is the base grammar composed with its extension (Δgj+gf), the source of p2 is the base source composed with its extension (Δsj+sf), and so on. As elements of delta tuples can themselves be delta tuples, composition recurses, e.g., Δsj+sf=
[Δc1…Δcn]+[c1…cn]=[Δc1+c1…Δcn+cn].
Summarizing, GenVoca values are nested tuples of program artifacts, and features are nested delta tuples, where + recursively composes them by vector addition. This is the essence of AHEAD.

The ideas presented above concretely expose two FOSD principles. The '''Principle of Uniformity''' states that all program artifacts are treated and modified in the same way. (This is evidenced by deltas for different artifact types above). The '''Principle of Scalability''' states all levels of abstractions are treated uniformly. (This gives rise to the hierarchical nesting of tuples above).

The original implementation of AHEAD is the AHEAD Tool Suite and Jak language, which exhibits both the Principles of Uniformity and Scalability. Next-generation tools include CIDE
<ref name="CIDE">{{cite web| title=Guaranteeing Syntactic Correctness for all Product Line Variants: A Language-Independent Approach | archive-url=https://web.archive.org/web/20170706122709/ftp://ftp.cs.utexas.edu/pub/predator/Tools2009.pdf | archive-date=2017-07-06 | url-status=dead | url=ftp://ftp.cs.utexas.edu/pub/predator/Tools2009.pdf}}</ref>
and FeatureHouse.<ref name="FH">{{cite web| title=FeatureHouse: Language-Independent, Automated Software Composition | url=http://www.infosun.fim.uni-passau.de/cl/publications/docs/ICSE2009fh.pdf}}</ref>

== FOMDD ==
[[Image:CommutingDiagram.JPG|thumb|Derivational and refinement relationships among program artifacts]]
'''Feature-Oriented Model-Driven Design''' ('''FOMDD''')<ref name="fomdd">{{cite web| title=Feature Oriented Model Driven Development: A Case Study for Portlets | archive-url=https://web.archive.org/web/20170706122327/ftp://ftp.cs.utexas.edu/pub/predator/ICSE07.pdf | archive-date=2017-07-06 | url-status=dead | url=ftp://ftp.cs.utexas.edu/pub/predator/ICSE07.pdf}}</ref><ref name="genmeta">{{cite book |date = October 2007 |pages= 105–114 |doi = 10.1145/1289971.1289990| chapter-url=http://portal.acm.org/citation.cfm?id=1289971.1289990 |first1= Salvador |last1= Trujillo|first2= Maider |last2= Azanza|first3= Óscar|last3= Díaz|title = Proceedings of the 6th international conference on Generative programming and component engineering |chapter = Generative metaprogramming |isbn = 9781595938558 |s2cid = 236715 }}</ref> combines the ideas of AHEAD with '''Model-Driven Design''' ('''MDD''') (a.k.a. '''[[Model-Driven Architecture]]''' ('''MDA''')). AHEAD functions capture the lockstep update of program artifacts when a feature is added to a program. But there are other functional relationships among program artifacts that express derivations. For example, the relationship between a grammar gf and its parser source sf is defined by a compiler-compiler tool, e.g., javacc. Similarly, the relationship between Java source sf and its bytecode bf is defined by the javac compiler. A [[commuting diagram]] expresses these relationships. Objects are program representations, downward arrows are derivations, and horizontal arrows are deltas. The figure to the right shows the commuting diagram for program p3 = i+j+h = [g3,s3,b3].

A fundamental property of a [[Commutative diagram|commuting diagram]] is that all paths between two objects are equivalent. For example, one way to derive the bytecode b3 of parser p3 (lower right object in the figure to the right) from grammar gh of parser h (upper left object) is to derive the bytecode bh and refine to b3, while another way refines gh to g3, and then derive b3, where + represents delta composition and () is function or tool application:

: b3 = Δbj + Δbi + {{mono|[[javacc]]}}( {{mono|[[javac]]}}( gh ) ) = {{mono|javac}}( {{mono|javacc}}( Δgi + Δgj + gh ) )

There are <math>\tbinom{4}{2}</math> possible paths to derive the bytecode b3 of parser p3 from the grammar gh of parser h. Each path represents a [[Metaprogramming|metaprogram]] whose execution generates the target object (b3) from the starting object (gf).
There is a potential optimization: traversing each arrow of a [[commuting diagram]] has a cost. The cheapest (i.e., shortest) path between two objects in a [[commuting diagram]] is a '''geodesic''', which represents the most efficient metaprogram that produces the target object from a given object.

: Note: A “cost metric” need not be a monetary value; cost may be measured in production time, peak or total memory requirements, power consumption, or some informal metric like “ease of explanation”, or a combination of the above (e.g., [[Multiobjective optimization|multi-objective optimization]]). The idea of a geodesic is general, and should be understood and appreciated from this more general context.

: Note: It is possible for there to be m starting objects and n ending objects in a geodesic; when m=1 and n>1, this is the [[Steiner tree problem|Directed Steiner Tree Problem]], which is NP-hard.

[[Commuting diagram]]s are important for at least two reasons: (1) there is the possibility of optimizing the generation of artifacts (e.g., geodesics) and (2) they specify different ways of constructing a target object from a starting object.<ref name="fomdd"/><ref name="testing">{{cite web | title=Testing Software Product Lines Using Incremental Test Generation | archive-url=https://web.archive.org/web/20170706122351/ftp://ftp.cs.utexas.edu/pub/predator/ISSRE08.pdf | archive-date=2017-07-06 | url-status=dead | url=ftp://ftp.cs.utexas.edu/pub/predator/ISSRE08.pdf }}</ref> A path through a diagram corresponds to a tool chain: for an FOMDD model to be consistent, it should be proven (or demonstrated through testing) that all tool chains that map one object to another in fact yield equivalent results. If this is not the case, then either there is a bug in one or more of the tools or the FOMDD model is wrong.

: Note: the above ideas were inspired by [[category theory]].<ref name="fomdd"/><ref name="genmeta"/>

== Applications ==
* [https://web.archive.org/web/20170706123320/ftp://ftp.cs.utexas.edu/pub/predator/tosem-92.pdf Network Protocols]
* [https://web.archive.org/web/20170706123320/ftp://ftp.cs.utexas.edu/pub/predator/tosem-92.pdf Extensible Database Systems]
* [https://web.archive.org/web/20170706123114/ftp://ftp.cs.utexas.edu/pub/predator/sigsoft-93.pdf Data Structures]
* [https://web.archive.org/web/20170706014110/ftp://ftp.cs.utexas.edu/pub/predator/fsatsRevised.pdf Distributed Army Fire Support Simulator]
* [https://web.archive.org/web/20170706123117/ftp://ftp.cs.utexas.edu/pub/predator/sigsoft-94.pdf Production System Compiler]
* [https://web.archive.org/web/20170706122254/ftp://ftp.cs.utexas.edu/pub/predator/GPL.pdf Graph Product Line]
* [https://web.archive.org/web/20170706014058/ftp://ftp.cs.utexas.edu/pub/predator/ahead.pdf Extensible Java Preprocessors]
* [https://web.archive.org/web/20170706122327/ftp://ftp.cs.utexas.edu/pub/predator/ICSE07.pdf Web Portlets]
* [https://web.archive.org/web/20170706122855/ftp://ftp.cs.utexas.edu/pub/predator/icmt08.pdf SVG Applications]

== See also ==
* [[FOSD metamodels]] – product lines of product lines
* [[FOSD origami]]
* [[FOSD program cubes]] – multi-dimensional product lines
* [[Very high-level programming language]]

== References ==
<references/>

{{Programming paradigms navbox}}

{{DEFAULTSORT:Feature-Oriented Programming}}
[[Category:Feature-oriented programming| ]]

Feature-oriented programming - Revision history

imported>GreenC bot: Move 15 urls. Wayback Medic 2.5 per WP:URLREQ#citeftp