Induction of Recursive Program Schemes

Abstract

In this paper we present an approach to the induction of recursive structures from examples which is based on the notion of recursive program schemes. We separate induction from examples in two stages: (1) constructing initial programs from examples and (2) folding initial programs to recursive program schemes. By this separation, the induction of recursive program schemes can be reduced to a pattern-matching problem which can be handled by a generic algorithm. Construction of initial programs is performed with an approach to universal planning. “Background knowledge” is given in the form of operators and their conditions of application. Furthermore synthesizing recursive program schemes instead of programs in a predefined programming language enables us to combine program synthesis and analogical reasoning. A recursive program scheme represents the class of structural identical programs and can be assigned different semantics by interpretation. We believe that our approach mimicks in some way the problem solving and learning behavior of a (novice) human programmer and that our approach integrates theoretical ideas and empirical results of learning by doing and learning by analogy from cognitive science in a unique framework.