# Inductive Synthesis of Functional Programs: An Explanation Based Generalization Approach

Emanuel Kitzelmann, Ute Schmid.

Year: 2006, Volume: 7, Issue: 15, Pages: 429−454

#### Abstract

We describe an approach to the inductive synthesis of recursive
equations from input/output-examples which is based on the classical
two-step approach to induction of functional Lisp programs of
Summers (1977). In a first step, I/O-examples are rewritten to
traces which explain the outputs given the respective inputs based on
a datatype theory. These traces can be integrated into one conditional
expression which represents a non-recursive program. In a second
step, this initial program term is generalized into recursive
equations by searching for syntactical regularities in the term. Our
approach extends the classical work in several aspects. The most
important extensions are that we are able to induce a *set* of
recursive equations in one synthesizing step, the equations may
contain more than one recursive call, and additionally needed
parameters are automatically introduced.