Induction of schemata for program synthesis
Nancy Lynn Tinkham, Alan W. Biermann · 1990
The observation that beginning students appear to learn program patterns by seeing groups of specific, similar programs suggests the automatic programming technique of constructing program schemata by generalization from programs and then using those schemata in the synthesis of future programs. For example, after one has seen several programs involving recursion on the tail of a list, one might remember this recursive pattern and use it on the next list-processing problem. We consider, then, two problems: (1) Given a set of programs, find a schema which is a generalization of every program in that set; (2) Given a schema and a set of examples and counterexamples of the desired input/output behavior of a target program, find a program which is a specialization of that schema and whose input/output behavior matches the given set of examples. We present a method for finding schemata from a set of programs, and we show that these schemata may be used to improve the efficiency of program synthesis.