Feature Oriented Programming
Encyclopedia
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 and levels of abstraction in network protocols and extensible database systems in the late-1980s . 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 function (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 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 expressed 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 .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. 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 should
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, AHEAD, and FOMDD, 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 presented elsewhere:
MetaModels
,
Program Cubes
,
Feature Algebras
, and Feature Interactions
.
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 MetaModels
and Program Cubes
).
The programs (expressions) that can be created defines a product line. Expression optimization is program design optimization, and expression evaluation is program synthesis.
GenVoca features were originally implemented using C preprocessor (
, showed the connection of features to object-oriented collaboration-based designs.
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. As an 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 composing tuples element-wise. The representations for parser p (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 p is the base grammar composed with its extension (
gj•gf), the source of p 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. 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 refined 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
and FeatureHouse.
(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 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 above figure) from
grammar gf of parser f (upper left object) is to derive the bytecode bf and refine to b3, while another way refines gf to g3, and then derive b3:
bi • 
bj • javac • javacc = javac • javacc • 
gi • 
gj
There are
possible paths to derive the bytecode b3 of parser p3 from the grammar gf of parser f. Each path represents a metaprogram whose execution synthesizes 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.
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 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 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).
Software product lines
Software product lines, or software product line development, refers to software engineering methods, tools and techniques for creating a collection of similar software systems from a shared set of software assets using a common means of production....
.
FOSD arose out of layer-based designs and levels of abstraction in network protocols and extensible database systems in the late-1980s . 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 function (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 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 expressed 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 .A software product line
Software product lines
Software product lines, or software product line development, refers to software engineering methods, tools and techniques for creating a collection of similar software systems from a shared set of software assets using a common means of production....
(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. 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 should
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, AHEAD, and FOMDD, 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 presented elsewhere:
MetaModels
FOSD metamodels
Feature Oriented Software Development is a general paradigm for program synthesis in software product lines, where a model of a product line is a tuple of 0-ary and 1-ary functions...
,
Program Cubes
FOSD Program Cubes
A program in Feature Oriented Software Development isa composition of functions : a base program is composed with...
,
Feature Algebras
FOSD Feature Algebras
Feature Oriented Programming or Feature Oriented Software Development is a general paradigm for program synthesis in software product lines. Please read the Feature Oriented Programming page that explains how an FOSD model of a product line is a tuple of 0-ary and 1-ary functions...
, and Feature Interactions
FOSD Feature Interactions
Feature Oriented Programming or Feature Oriented Software Development is a general paradigm for program synthesis in software product lines. The building blocks of programs are features...
.
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/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 MetaModels
FOSD metamodels
Feature Oriented Software Development is a general paradigm for program synthesis in software product lines, where a model of a product line is a tuple of 0-ary and 1-ary functions...
and Program Cubes
FOSD Program Cubes
A program in Feature Oriented Software Development isa composition of functions : a base program is composed with...
).
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 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 modelsFeature modelFeature model is a compact representation of all the products of the Software Product Line in terms of "features". Feature models are visually represented by means of feature diagrams. Feature models are widely used during the whole product line development process and are commonly used as input...
(which can be translated into propositional formulas) are graphical representations that define legal combinations of features.
- 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.. Yet another reformulation of GenVoca is as a monoidMonoidIn abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
: 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 as mentioned above.
GenVoca features were originally implemented using C preprocessor (
#ifdef feature ... #endif) techniques. A more advanced technique, called mixin layersFOSD Mixin Layers
The key implementation technique of GenVoca is due to Smaragdakis called mixin-layers.Aspectual mixin layers and aspectual feature modules are recent extensions that incorporate aspect-oriented programming....
, 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 gf, Java source sf, and documentation df. Program 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.-
- 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 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 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.).
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. As an 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 composing tuples element-wise. The representations for parser p (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-wiseThat is, the grammar of p is the base grammar composed with its extension (
gj•gf), the source of p 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. 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 refined 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
and FeatureHouse.
FOMDD
Feature Oriented Model Driven Design (FOMDD) combines the ideas of AHEAD with Model Driven Design (MDD) (a.k.a. Model-Driven ArchitectureModel-driven architecture
Model-driven architecture is a software design approach for the development of software systems. It provides a set of guidelines for the structuring of specifications, which are expressed as models. Model-driven architecture is a kind of domain engineering, and supports model-driven engineering of...
(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 commuting diagram
Commutative diagram
In mathematics, and especially in category theory, a commutative diagram is a diagram of objects and morphisms such that all directed paths in the diagram with the same start and endpoints lead to the same result by composition...
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 above figure) from
grammar gf of parser f (upper left object) is to derive the bytecode bf and refine to b3, while another way refines gf to g3, and then derive b3:
bi • bj • javac • javacc = javac • javacc • gi • gjThere are
possible paths to derive the bytecode b3 of parser p3 from the grammar gf of parser f. Each path represents a metaprogram whose execution synthesizes 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, some informal metric like “ease of explanation”, or a combination of the above (e.g., multi-objective optimizationMultiobjective optimizationMulti-objective optimization , also known as multi-criteria or multi-attribute optimization, is the process of simultaneously optimizing two or more conflicting objectives subject to certain constraints....
). The idea of a geodesic is quite 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 Directed Steiner Tree ProblemSteiner treeThe Steiner tree problem, or the minimum Steiner tree problem, named after Jakob Steiner, is a problem in combinatorial optimization, which may be formulated in a number of settings, with the common part being that it is required to find the shortest interconnect for a given set of objects.The...
, which is NP-hard.
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 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 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 above ideas were inspired by category theoryCategory theoryCategory theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...
.
Applications
- [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]
See also
- FOSD MetaModelsFOSD metamodelsFeature Oriented Software Development is a general paradigm for program synthesis in software product lines, where a model of a product line is a tuple of 0-ary and 1-ary functions...
-- product lines of product lines - FOSD Program CubesFOSD Program CubesA program in Feature Oriented Software Development isa composition of functions : a base program is composed with...
-- multi-dimensional product lines - FOSD Feature AlgebrasFOSD Feature AlgebrasFeature Oriented Programming or Feature Oriented Software Development is a general paradigm for program synthesis in software product lines. Please read the Feature Oriented Programming page that explains how an FOSD model of a product line is a tuple of 0-ary and 1-ary functions...
-- basic operations from which FOSD features (0-ary and 1-ary) functions are defined - FOSD Feature InteractionsFOSD Feature InteractionsFeature Oriented Programming or Feature Oriented Software Development is a general paradigm for program synthesis in software product lines. The building blocks of programs are features...
-- general concepts for feature interactions