A Combined Analytical and Search-Based Approach to the Inductive Synthesis of Functional Programs
- This thesis is concerned with the inductive synthesis of recursive declarative programs and in particular with the analytical inductive synthesis of functional programs. Program synthesis addresses the problem of (semi-)automatically generating computer programs from specifications. In inductive program synthesis, recursive programs are constructed by generalizing over incomplete specifications such as finite sets of input/output examples (I/O examples). Classical methods for induction of functional programs are analytical, that is, a recursive function definition is derived by detecting and generalizing recurrent patterns between the given I/O examples. Most recent methods, on the other side, are generate-and-test based, that is, they repeatedly generate programs independently from the provided I/O examples until a program is found that correctly computes the examples. Analytical methods are much faster than generate-and-test methods, because they do not rely on search in a program space. Therefore, however, the schemas that generatable programs conform to, must be much more restricted. This thesis at first provides a comprehensive overview of current approaches and methods to inductive program synthesis. Then we present a new algorithm to the inductive synthesis of functional programs that generalizes the analytical approach and combines it with search in a program space. Thereby, the strong restrictions of analytical methods can be resolved for the most part. At the same time, applying analytical techniques allows for pruning large parts of the problem space so that solutions can often be found faster than with generate-and-test methods. By means of several experiments with an implementation of the described algorithm, we demonstrate its capabilities.