A program integration algorithm that accommodates semantics-preserving transformations

Reviewer: Peter N. van den Bosch

A program may be developed into two variants—possibly because it is available on a popular operating system and is enhanced independently and with different intent at two sites—which do not interfere in the sense that they expect a variable to have different values at the same point in an execution trace. It may be desirable to merge these versions with the original in such a way that the enhancements are present and the original semantics are otherwise preserved. The problem is undecidable, but may be conservatively satisfied: the trick is to be as liberal as possible. Textual merger programs that produce an update file (a cost-saving device for distributing versions to a large number of sites in compact form) have existed for some time, but they do not have any sense of semantics and therefore have a coarse conception of interference that may be both too liberal and too conservative, depending on the individual case. Earlier work contributed to by two of the three authors [1] used a variant of dataflow graphs, long used in program optimization, and a slicing operation on these to determine a safe superset of “changed” computations and then merged these provided they did not lead to nondeterministic data flow such as would be caused by semantic interference. The resulting algorithm was so conservative, however, that it frequently failed to integrate noninterfering variants. As in the earlier paper, the focus here is on a simplified but computationally complete programming language. The new algorithm adapts ideas from basic block optimization to detect equivalent computations and so eliminate one common source of apparent interference; program integration is also generalized from the earlier formulation so that it is now independent of the equivalence detection, which may be separately refined. The paper is long (a lengthy proof fills an appendix that accounts for more than a quarter of its length, however), but the development is well organized, going to the unusual length (for a technical paper) of providing signposts for the first-time reader by anticipating questions that may not be answered until a later section. It also has the rare virtue of being essentially self-contained: even ideas imported from what are now textbook subjects (such as fsa minimization and basic block optimization) are well documented. The scope for further work in several areas promises this paper a long life in the reference lists of computing literature. Two areas spring to mind: extending the linguistic expressiveness to procedures—probably using ideas from global optimization—and refining the equivalence detection techniques to deal with two juicy examples presented with rare candor.