A New Program Integration Algorithm

Abstract

Program integration attempts to construct a merged program from several related but different variants of a base program. The merged program must include the changed computations of the variants as well as the computations of the base program that are preserved in all variants. A fundamental problem of program integration is determining the sets of changed and preserved computations of each variant. This paper describes a new algorithm for partitioning program components (in one or more programs) into disjoint equivalence classes so that two components are in the same class only if they have the same execution behavior. This partitioning algorithm can be used to identify changed and preserved computations, and thus forms the basis for the new program-integration algorithm presented here. The new program-integration algorithm is strictly better than the original algorithm of Horwitz, Prins, and Reps: integrated programs produced by the new algorithm have the same semantic properties relative to the base program and its variants as do integrated programs produced by the original algorithm, the new algorithm successfully integrates program variants whenever the original algorithm does, but here are classes of program modifications for which the new algorithm succeeds while the original algorithm reports interference.