Algebraic Properties of Program Integration
Thomas Reps
The need to integrate several versions of a program into a common
one arises frequently, but it is a tedious and time consuming task to
merge programs by hand.
The program-integration algorithm proposed by Horwitz, Prins, and Reps
provides a way to create a semantics-based tool for integrating
a base program with two or more variants.
The integration algorithm is based on the assumption that any change in
the behavior, rather than the text, of a program variant
is significant and must be incorporated in the merged program.
An integration system based on this algorithm will determine whether the
variants incorporate interfering changes, and, if they do not,
create an integrated program that includes all changes as well as
all features of the base program that are preserved in all variants.
To determine this information, the algorithm employs a program representation
that is similar to the program dependence graphs that have been used
previously in vectorizing and parallelizing compilers.
This paper studies the algebraic properties of the program-integration
operation, such as whether there are laws of associativity and distributivity.
(For example, in this context associativity means: "If three variants
of a given base are to be integrated by a pair of two-variant
integrations, the same result is produced no matter which two variants
are integrated first.")
To answer such questions, we reformulate the Horwitz-Prins-Reps
integration algorithm as an operation in a Brouwerian algebra
constructed from sets of dependence graphs.
(A Brouwerian algebra is a distributive lattice with an operation
a - b characterized by a - b <= c
iff a <= b join c.)
In this algebra, the program-integration operation can be defined solely
in terms of join, meet, and -.
By making use of the rich set of algebraic laws that hold in Brouwerian
algebras, we have established a number of the integration operation's
algebraic properties.
(Click here to access the paper:
PostScript,
PDF.)
University of Wisconsin