New Programs From Old

This paper studies operations for creating new variants of a program that relate, in a well-defined way, to existing variants of the program. We formalize a program modification as a (special kind of) function from programs to programs, and study the algebra of these program modifications. We make use of the algebraic structure to formalize several intuitive concepts, such as that of “compatibility among program modifications”, and establish several new results concerning the problems of program merging and separating consecutive edits. We also identify a category in which the objects are programs and the morphisms are program modifications, and show how program integration relates to the pushout in this category