FOSD origami

Origami

A fundamental generalization of metamodels is origami. The essential idea is that a program's design need not be represented by a single expression; multiple expressions can be used. This involves the use of multiple orthogonal GenVoca models.

E = D•H•P -- tool equation E = S•B -- language equation

Let U=[U₁,U₂,...,U_n] be a GenVoca model of n features, and W=[W₁,...W_m] be a GenVoca model of m features. The relationship between two orthogonal models U and W is a matrix UW, called an Origami matrix, where each row corresponds to a feature in U and each column corresponds to a feature in W. Entry UW_ij is a function that implements the combination of features U_i and W_j.

Note: UW is the tensor product of U and W (i.e., UW=U×W). U W = U × W = [ U W 11 U W 12 ⋯ U W 1 n ⋮ ⋮ ⋱ ⋮ U W m 1 U W m 2 ⋯ U W m n ] T L = T × L = [ P B P G P S H B H G H S D B D G D S J B J G J S ]

To see how multiple equations are used to synthesize a program, again consider models U and W. A program F is described by two equations, one per model. We can write an equation for F in two different ways: referencing features by name or by their index position, such as:

F = U 1 ⋅ U 2 ⋅ U 4 = ∑ i = 1 , 2 , 4 U i —U expression of F F = W 1 ⋅ W 3 = ∑ j = 1 , 3 W i —W expression of F

The UW model defines how models U and W are implemented. Synthesizing program F involves projecting UW of unneeded columns and rows, and aggregating (a.k.a. tensor contraction):

F = U W 11 ⋅ U W 21 ⋅ . . . ⋅ U W 33 = ∑ i = 1 , 2 , 3 ∑ j = 1 , 3 U W i , j = ∑ j = 1 , 3 ∑ i = 1 , 2 , 3 U W i , j

A fundamental property of origami matrices, called orthogonality, is that the order in which dimensions are contracted does not matter. In the above equation, summing across the U dimension (index i) first or the W dimension (index j) first does not matter. Of course, orthogonality is a property that must be verified. Efficient (linear) algorithms have been developed to verify that origami matrices (or tensors/n-dimensional arrays) are orthogonal. The significance of orthogonality is one of view consistency. Aggregating (contracting) along a particular dimension offers a 'view' of a program. Different views should be consistent: if one repairs the program's code in one view (or proves properties about a program in one view), the correctness of those repairs or properties should hold in all views.

In general, a product of a product line may be represented by n expressions, from n orthogonal and abstract GenVoca models G₁ ... G_n. The Origami matrix (or cube or tensor) is an n-dimensional array A:

A = G 1 × . . . × G n = ∏ k = 1 n G k

A product H of this product line is formed by eliminating unnecessary rows, columns, etc. from A, and aggregating (contracting) the n-cube into a scalar:

H = ∑ i 1 ∑ i 2 . . . ∑ i n G i 1 , i 2 . . . i n

Applications

There are several of product line applications developed using Origami. Among them include:

AHEAD Tool Suite and Extensible Java Preprocessors

Expression Problem or the Extensibility Problem

Refinements and Multi-Dimensional Separation of Concerns

More applications to be supplied.