Program Kubes

Don Batory
Department of Computer Science
University of Texas at Austin
Austin, Texas 78712

Transformation-based program synthesis is a hallmark
of automated program development.  Some time ago, 
we discovered that the design of a program could be 
expressed as a matrix of program transformations, where
both rows and columns represented features.  The
technique was called Origami, as the matrix was
folded in precise ways (thereby composing transformations) 
until a scalar was produced.  This scalar defined an 
expression (a composition of transformations) that, 
when evaluated, synthesized the program.  Origami 
generalized to n-dimensional arrays, where each axis 
defined a dimension of variability.  But we never quite 
understood why Origami worked.

Our research seeks principles of automated construction 
that can be appreciated by practitioners and that are 
expressed in terms of simple mathematics.  This talk explains 
Origami's dimensions of variability by an interesting integration 
of diverse topics: database technology (data cubes), mathematics 
(elementary ideas from tensors and categories), programming languages
(the expression problem), and software design (feature interactions).