Feature Oriented Programming

"Feature Oriented Programming (FOP)" or "Feature Oriented Software Development (FOSD)" is a general paradigm for program synthesis in software product lines.

FOSD arose out of layer-based designs of network protocols and extensible database systems in the late-1980s cite web | title=Design and Implementation of Hierarchical Software Systems with Reusable Components | url=ftp://ftp.cs.utexas.edu/pub/predator/tosem-92.pdf] . A program was defined as 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 function 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 functions (layers). The figure to the right illustrates the stacking of layers h, j, and i (where h is on the bottom and i is on the top). The algebraic notations i(j(h))and i•j•h express these designs.

Over time, the idea of layers was generalized to features, where a "feature" is an increment in program development or functionality. The paradigm for program design and synthesis was recognized to be a generalization of relational query optimization, where query evaluation programs were defined as relational algebra expressions, and query optimization was expression evaluation cite web | title=Access Path Selection In Relational Databases | url=http://portal.acm.org/citation.cfm?id=582099] .A "software product line (SPL)" is a family of programs where each program is defined by a unique composition of features, and no two programs have the same combination of features. FOSD has since evolved into the study of feature modularity, tools, analyses, and design techniques to support feature-based program synthesis.

Further advances in FOSD arose from recognizing the following facts: Every program has multiple representations (e.g., source, makefiles,documentation, etc.) and adding a feature to a program could elaborate each of its representations so that all representations are consistent. Additionally, some of these representations could be generated (or derived)from other representations. In this article, the mathematics of the three most recent generations of FOSD, namely GenVoca, AHEADcite web | title=Scaling Step-Wise Refinement | url=ftp://ftp.cs.utexas.edu/pub/predator/TSE-AHEAD.pdf] , and FOMDD, are progressivelydescribed, 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 presented on separate pages:
MetaModels, Origami,
Feature Algebras, and Feature Interactions.

"Please note this page is under construction (it currently has both omissions and errors). A first draft should be finished by September 2008."

GenVoca

"GenVoca" (a meld of the names Genesis and Avoca) is a compositional paradigm for defining programs of a 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 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.:

p₁ = j • f -- program p₁ has features j and f p₂ = j • h -- program p₂ has features j and h p₃ = i • j • h -- program p₃ has features i, j, and h

A "GenVoca model" of a domain or software product line is a set of values and functions. The programs (expressions) that can be created defines a product line. Expression optimization is "program design optimization", and expression evaluation is "program synthesis".

: 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 the automation of program design and construction. Consider program p₃ 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 diagrams (which can be translated into propositional formulas) are graphical representations that define legal combinations of features. cite web | title=Feature Models, Grammars, and Propositional Formulas | url=ftp://ftp.cs.utexas.edu/pub/predator/splc05.pdf]

: 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.cite web | title=An Algebra for Features and Feature Composition | url=http://www.infosun.fim.uni-passau.de/cl/publications/docs/AMAST2008.pdf] cite web | title=Superimposition: A Language-Independent Approach to Software Composition | url=http://www.infosun.fim.uni-passau.de/cl/publications/docs/SC2008.pdf] . 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 compositions are meaningful as mentioned above.

GenVoca features were originally implemented using C preprocessor (#ifdef feature ... #endif) techniques. A more advanced technique, called mixin layers, showed the connection of features to object-oriented collaboration-based designs.

AHEAD

"Algebraic Hierarchical Equations for Application Design (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 g_f, Java source s_f, and documentation d_f. Program f is modeled by the tuple f= [g_f, s_f, d_f] . 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.

:: Example. Suppose terminal representations are files. In AHEAD, grammar g_f corresponds to a single BNF file, source s_f corresponds to a tuple of Java files [c₁…c_n] , and documentation d_f is a tuple of HTML files [h₁…h_k] . A GenVoca value (nested tuples) can be depicted as a directed graph: the graph for program 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 g_f and subdirectories s_f and d_f. Similarly, directory s_f contains files c₁…c_n, and directory df contains files h₁…h_k.

:: 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.).

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 $Delta$g_j (new rules and tokens are added), extends source code by $Delta$s_j (new classes and members are added and existing methods are modified), and extends documentation by $Delta$d_j. The tuple of deltas for feature j is modeled by j= [$Delta$g_j,$Delta$s_j,$Delta$d_j] , which we call a "delta tuple". Elements of delta tuples can themselves be delta tuples. For example, $Delta$s_j represents the changes that are made to each class in s_f by feature j, i.e., $Delta$s_j= [$Delta$c₁…$Delta$c_n] .The representations of a program are computed recursively by composing tuples element-wise. The representations for parser p (whose GenVoca expression is j•f) are:

p₂ = j • f -- GenVoca expression $$ = [ $Delta$g_j, $Delta$s_j, $Delta$d_j] • [g_f, s_f, d_f] -- substitution $$ = [$Delta$g_j•g_f, $Delta$s_j•s_f, $Delta$d_j•d_f] -- compose tuples element-wise

That is, the grammar of p is the base grammar composed with its extension ($Delta$g_j•g_f), the source of p is the base source composed with its extension ($Delta$s_j•s_f), and so on. As elements of delta tuples can themselves be delta tuples, composition recurses, e.g., $Delta$s_j•s_f= [$Delta$c₁…$Delta$c_n] • [c₁…c_n] = [$Delta$c₁•c₁…$Delta$c_n•c_n] .Summarizing, GenVoca values are nested tuples of program artifacts, and features are nested delta tuples, where • recursively composes them. This is the essence of AHEAD.

The ideas presented above are a concrete formulation of two FOSD principles. The "Principle of Uniformity" states that all program artifacts should be treated the same and can be refined. (This is evidenced by deltas for different artifact types above). The "Principle of Scalability" states all levels of abstractions can be treated uniformily. (This gives rise to the hierarchial nesting of tuples above).

The primary implementation of AHEAD is called the AHEAD Tool Suite and Jak language, which illustrates the Principle of Uniformity. See Metamodels for illustrations of the Principle of Scalability.

FOMDD

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 p₃ = i•j•h = [g₃,s₃,b₃] .

A fundamental property of a commuting diagram is that all paths between two objects are equivalent. For example, one way to derive the bytecode b₃ of parser p₃ (lower right object in the above figure) from grammar g_f of parser f (upper left object) is to derive the bytecode b_f and refine to b₃, while another way refines g_f to g₃, and then derive b₃:

$Delta$b_i • $Delta$b_j • javac • javacc = javac • javacc • $Delta$g_i • $Delta$g_j

There are $binom\{4\}\{2\}$ possible paths to derive the bytecode b₃ of parser p₃ from the grammar g_f of parser f. Each path represents a metaprogram whose execution synthesizes the target object (b₃) from the starting object (g_f). 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 measure in production time, peak or total memory requirements, or even some informal metric of “ease of explanation”, or a combination of the above (e.g., multi-objective optimization). The idea of a geodesic is quite general, and should be understood and appreciated from this more general context.

Commuting diagrams are important for at least two reasons: (1) there is the possibility of optimizing the synthesis of artifacts (e.g., geodesics) and (2) they specify different ways of constructing a target object from a starting object. A path through a diagram correspond to a tool chain: for a 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 different paths/tool chains yield different results, then either there is a bug in one or more of the tools or the FOMDD model is wrong).

: Note: the ideas sketched above were inspired by elementary ideas from category theory .

Applications

There is a large history of product line applications developed using FOSD. Among them include:

* [ftp://ftp.cs.utexas.edu/pub/predator/tosem-92.pdf Network Protocols]
* [ftp://ftp.cs.utexas.edu/pub/predator/tosem-92.pdf Extensible Database Systems]
* [ftp://ftp.cs.utexas.edu/pub/predator/sigsoft-93.pdf Data Structures]
* [ftp://ftp.cs.utexas.edu/pub/predator/fsatsRevised.pdf Distributed Army Fire Support Simulator]
* [ftp://ftp.cs.utexas.edu/pub/predator/sigsoft-94.pdf Production System Compiler]
* [ftp://ftp.cs.utexas.edu/pub/predator/GPL.pdf Graph Product Line]
* [ftp://ftp.cs.utexas.edu/pub/predator/ahead.pdf Extensible Java Preprocessors]
* [ftp://ftp.cs.utexas.edu/pub/predator/ICSE07.pdf Web Portlets]
* [ftp://ftp.cs.utexas.edu/pub/predator/icmt08.pdf SVG Applications]

More applications to be supplied.

See Also

Implementation Techniques
*FOSD Mixin Layers -- an object-oriented way to express refinements and collaboration-based designs
*FOSD AHEAD -- a next generation implementation of mixin layers, feature modules, and feature composition

General extensions of FOSD:
*FOSD Metamodels -- how to express product lines of product lines
*FOSD Origami -- extension of metamodels to express multi-dimension separation of concerns
*FOSD Feature Algebras -- basic operations from which FOSD features (0-ary and 1-ary) functions are defined
*FOSD Feature Interactions -- a general model of feature interactions

References