FOSD program cubes

A program in Feature Oriented Software Development (FOSD) is a composition of functions (program transformations): a base program (modeled by a 0-ary function) is composed with increments in program functionality, called features (which are unary functions) to produce a complex program. A software product line (SPL) is a family of related programs. Suppose product line PL has F₀ as a base program, and F₁..F_n as features that could be added to F₀. Different compositions of these functions/transformations yield different programs. For this discussion, let + denote function composition. A program P in PL might have the following expression:

  $P=F_{8}+F_{4}+F_{2}+F_{1}+F_{0}$

That is, program P has features F₈, F₄, F₂, F₁, and F₀ composed in this order.

We can recast P in terms of a projection and contraction of a 1-dimensional array. Let F_i = [F₀ .. F_n] denote the array of transformations that define PL. A projection of F_i eliminates unneeded transformations, yielding a shorter array (call it) G_i. A contraction of G_i composes each transformation of G_i in a specific order, to yield a scalar expression. The expression for P above is rewritten as:

    $P=\sum _{i=(0,1,2,4,8)}\mathbf {F} _{i}$

where the index values accomplish projection and summation is array contraction. This idea generalizes to n-dimensional arrays that model n-dimensional product lines.

N-Dimensional Product-Lines

A multi-dimensional product-line is described by multiple interacting sets of features.

As an elementary example of a 2-dimensional product-line, it is easy to create a product line of calculators, where program variants offer different sets of operations. A variation might offer different GUI front ends to calculators, one with no GUI, another with a Java GUI, a third with a web GUI. These variations interact: each calculator operation has a specific GUI representation, so each calculator feature cannot be designed independently of its GUI features. Such a design leads to a matrix: columns represent increments in calculator functionality, and rows represent different front-ends and increments in their functionality. Such a matrix M is shown to the right: columns allow one to pair basic calculator functionality (base) with optional logarithmic/exponentiation (lx) and trigonometric (tg) features. Rows allow one to pair core functionality with no front-end (core), with optional GUI (gui) and web-based (web) front-ends.

An element Mij defines how column feature i and row feature j are 'simultaneously' implemented. For example, the element labeled cb is a base program that implements the core functionality of a calculator. Element gb adds code that displays the core functionality as a GUI; element wb adds code that displays the core functionality via the web. Similarly, element ct adds trigonometric code to the core functionality; elements gt and wt add code to display the trigonometric functionality as a GUI and web front-end.

A calculator is uniquely specified by two sequences of features: one sequence defining the calculator functionality, the other the front-end. For example, calculator C that offers both base and trig functionality in a web format is defined by the expression:

  $C=M_{cb}+M_{ct}+M_{wb}+M_{wt}$

Note: each dimension of a program kube is a collection of base programs and features. Not all of their compositions are meaningful. A feature model is used to define the legal combinations of features. Thus, each dimension of a kube would have its own feature model. It is possible that selected features along one dimension may preclude or require features along other dimensions. In any case, these feature models define the legal combinations of features in an n-dimensional product line.

Kubes

In general, a kube is an n-dimensional array. The rank a kube is its dimensionality. A scalar is a kube of rank 0, a vector is a kube of rank 1, and a matrix is rank 2. Following tensor notation: the number of indices a kube has designates its rank. A scalar S is rank 0 (it has no indices), V_k is a vector (rank 1), M_ij is a matrix (rank 2), C_ijk is a cube (rank 3).

Program Cubes or program kubes are n-dimensional arrays of functions (program transformations) that represent n-dimensional product-lines.

In general, kubes can have arbitrary dimensionality. The values along each axis of a kube denote either a base program or a feature that could elaborate a base program. A kube represents an n-dimensional model of a SPL. The rank of a product line is the rank of its kube.

Note: program kubes are inspired by data cubes in databases. The primary difference is that data cube elements are numerical values that are aggregated during contraction; program kube elements are transformations that are composed during kube aggregation. Both use tensor notations and terminology, although kubes satisfy few algebraic properties of tensors.

A program is uniquely specified by n sequences of features S₁..S_n, one per dimension. The design of a program is a scalar (expression) that is formed by (1) projecting the kube of its unneeded elements, and (2) contracting the resultant kube to a scalar:

  $P=\sum _{i_{1}=S_{1},i_{2}=S_{2},..i_{n}=S_{n}}K_{i_{1}i_{2}..i_{n}}$

Program synthesis is evaluating the scalar expression to produce program P.

An interesting property of kube design is that the order in which dimensions are contracted does not matter -- any permutation of dimensions during contraction will result in a different scalar expression (i.e. a different program design), but all expressions produce the same value (program). For example, another expression (design) to produce P contracts dimensions in the opposite order from the above:

  $P=\sum _{i_{n}=S_{n},..i_{2}=S_{2},i_{1}=S_{1}}K_{i_{1}i_{2}..i_{n}}$

Note: Underlying kube designs is a commuting diagram, such that there are an exponential number of paths from the empty program 0 to program P. Each path denotes a particular contraction of a kube, and corresponds to a unique incremental design of P. Included among these paths are kube aggregations that contract kubes using different dimensional orders.

The significance of program kubes is that it provides a structured way in which to express and build n-dimensional models of SPLs. Further, it provides scalable specifications. If each dimension has k values, a n-kube specification of a program requires O(kn) terms, as opposed to O(kⁿ) kube elements that would otherwise have to be identified and then composed. In general, kubes provide a compact way to specify complex programs.

Note: each dimension of a program kube is a collection of base programs and features. Not all of their compositions are meaningful. A feature model is used to define the legal combinations of features. Thus, each dimension of a kube would have its own feature model. It is possible that selected features along one dimension may preclude or require features along other dimensions. In any case, these feature models define the legal combinations of features in an n-dimensional product line; and in doing so, define the legal projections of a SPL's kube.

Applications

The expression problem (EP) (a.k.a. the extensibility problem) is a fundamental problem in programming languages aimed at type systems that can add new classes and methods to a program in a type-safe manner. It is also a fundamental problem in multi-dimensional SPL design. The expression problem is an example of an SPL of rank 2. The following applications either explain/illustrate the expression problem or show how it scales to product lines of large programs. EP is really a SPL of ~30 line programs; the applications below show how these ideas scale to programs of >30K lines (a 10³ increase in size).

• Expression Problem
• Illustration of Small Expression Problem
• Extensible IDEs
• Multi-Dimensional Separation of Concerns

Also, FOSD metamodels can be viewed as special cases of program kubes.

See also

• Feature Oriented Programming -- basic overview
• FOSD Metamodels -- how to express product lines of product lines
• FOSD Feature Algebras -- operations from which FOSD features (0-ary and 1-ary) functions are defined
• FOSD Feature Interactions -- general concepts for feature interactions