Programming by Analogy: Retrieval, Mapping, Adaptation and Generalization of Recursive Program Schemes

We present an approach to program reuse by analogical transfer based upon the notion of recursive program schemes (RPSs). RPSs are representations which capture the structure of a program and are executable (if the symbols are interpreted by operator symbols of a functional programming language). This kind of representation is extremly useful for programming by analogy. The general outline of our approach is as follows: we start with a straight-forward program (initial program) which can be seen as handsimulation for transforming a fixed input into the corresponding output value. The desired iterative (recursive) program generalizing over the fixed input (RPS) is constructed by analogical transfer of an already known RPS which is structural similar to the new programming problem. Source and target RPSs are generalized to an RPS representing the common structure of both problems. Target RPS and generalized RPS are stored in memory with the generalized RPS as parent to source and target. By building a hierachical memory of generalized RPSs we can use programs as well as abstract schemes as sources. In this paper we present our approach to retrieval from and stepwise construction of an hierarchical memory and an algorithm and first results for adaptation of isomorphical and non-isomorphical sources.