A theory of program modifications

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 behaviour, rather than the text, of a program variant is significant and must be preserved 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.

This paper studies the algebraic properties of the program-integration operation, such as whether there is a law of associativity. (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.”) Whereas an earlier work that studied the algebraic properties of program integration formalized the Horwitz-Prins-Reps integration algorithm as an operation in a Brouwerian algebra, this paper introduces a new algebraic structure in which integration can be formalized, called fmalgebra. In fm-algebra, the notion of integration derives from the concepts of a program modification and an operation for combining modifications. (Thus, while earlier work concerned an algebra of programs, this paper concerns an algebra of program modifications.)

The potential benefits of an algebraic theory of integration, such as the one developed in this paper, are actually three-fold: