FOSD program cubes
 | This article or section is in a state of significant expansion or restructuring. You are welcome to assist in its construction by editing it as well. If this article or section has not been edited in several days, please remove this template. If you are the editor who added this template and you are actively editing, please be sure to replace this template with {{in use}} during the active editing session. Click on the link for template parameters to use.
This article was last edited by Sb1916 (talk | contribs) 16 years ago. (Update timer) |
A program in Feature Oriented Software Development (FOSD) is a composition of functions: a base program (modeled by a 0-ary function) composed with increments in program functionality, called features, (which are unary functions). A software product line (SPL) is a family of related programs. Suppose product line PL has F0 as a base program, and F1..Fn as features that could be added to this program. For this discussion, let + denote function composition. A program P in PL might have the following expression:
We can recast the above in terms of projection and contraction of a 1-dimensional array. Let Fi = [F0 F1 .. Fn] denote the array of functions in PL. A projection of Fi eliminates unneeded elements, yielding a shorter array (call it) Gi. A contraction of Gi composes each element of Gi in a specific order, to yield a scalar. The expression for P above is rewritten as:
where the index values accomplish projection and summation is array contraction.
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), Vk is a vector (rank 1), Mij is a matrix (rank 2), Cijk is a cube (rank 3).
Program Cubes or program kubes are n-dimensional arrays of functions (transformations) that represent n-dimensional product-lines (also known as product-lines of product-lines). As an elementary example, it is easy to create a product line of calculators, where program variants offer different sets of operations. A product line of calculator product lines might offer different GUI front ends, one SPL with no GUI, another with a Java GUI, a third with a web GUI, with each of these GUIs having options (look-and-feel, etc.). The collection of these 1-dimensional arrays (one per SPL) yields a matrix (kube of rank 2): the columns would represent increments in calculator functionality, and the rows represent different base GUIs and increments in their functionality. A particular calculator would be uniquely specified by two sequences of features: one sequence defining the calculator functionality, the other the customized GUI.
In general, kubes can have arbitrary dimensionality, although existing examples have <5 dimensions. 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. (A 1D kube is a product line, a 2D kube is a product line of 1D kubes, a 3D kube is a product line of 2D kubes, etc.). 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 S1..Sn, 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:
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 (i.e., synthesize the same program), e.g.:
- Note: the mathematical reason for this is that 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 via different dimensions.
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(kn) 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 the SPL's kube.
Applications
Note: the 'expression problem' (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. We see it as a fundamental problem in n-dimensional SPL design. The expression problem is an example of a kube of rank 2.