Schema induction for logic program synthesis

摘要

Prolog program synthesis can be made more efficient by using schemata which capture similarities in previously-seen programs. Such schemata narrow the search involved in the synthesis of a new program. We define a generalization operator for forming schemata from programs and a downward refinement operator for constructing programs from schemata. These operators define schema-hierarchy graphs which can be used to aid in the synthesis of new programs. Algorithms are presented for efficiently obtaining least generalizations of schemata, for adding new schemata to a schema-hierarchy graph, and for using schemata to construct new programs.