Functional Program Synthesis from Examples

Inductive inference is not so common in automatic programming. We first define, in Section 3.1, the underlying specification formalism, namely examples. In Section 3.2, we present the major results about inductive inference. Then, in Section 3.3 and Section 3.4, we survey the synthesis of functional programs from examples, and the synthesis of logic programs from examples, respectively. Finally, in Section 3.5, we draw some conclusions on the use of inductive inference in automatic programming. 

The next two sections survey the synthesis of functional programs from examples, and the synthesis of logic programs from examples, respectively. 

A few researchers have tackled this lack of discipline in the synthesis of recursive logic programs from examples for instance, [Tinkham 90] and [Sterling and Kirschenbaum 93] investigate the use of schemas to guide synthesis. Curiously, the now virtually defunct research on trace-based synthesis of functional programs from examples [Summers 77] [Biermann 78] did not suffer from such a marked lack of discipline , even though this research preceded ILP research. 

In Chapter 3, we survey the use of inductive inference in automatic programming. Specifications by examples are concise and natural, but are usually also incomplete and ambiguous, due to the insufficient expressive power of examples. As inductive inference is much less known than deductive inference, we first survey this field. Inductive synthesis from specifications by examples can be classified into trace-based synthesis and model-based synthesis. We survey the achievements of inductive synthesis of LISP functions and Prolog predicates. 

---