Relating logic programs via program maps

This paper presents a mathematical theory underlying a systematic method for constructing Prolog programs called stepwise enhancement. Stepwise enhancement dictates building a program starting with a skeleton program which constitutes the basic control flow for the problem to be solved, and adding extra computations to the skeleton program by using well-understood programming techniques. Each extra computation can be developed independently, and the separate enhancements combined to produce the final program. While intuition and motivation have focused on Prolog, the methods are applicable to logic programming languages more generally. The central concept in our mathematical theory for stepwise enhancement is that of a program map between two logic programs. Our definition of a program map from an enhancement to its skeleton guarantees the lifting of computations, the essence of the enhancement methodology. In this paper, we give definitions of program map and extensions, show that the definitions preserve the property of computations lifting, give examples of extensions and programming techniques which generate them, and point to directions for future work.