Automatic program synthesis from example problems

摘要

Desired algorithms to be synthesized are described implicitly by example problems that the algorithms should solve. The example problems are first solved by the problem-solver LAWALY. The obtained solution represents a trace of the desired algorithm. From the trace, the algorithm is synthesized by the synthesizer SYN. SYN writes recursive programs with repeat statements, and generates its own subroutines. Examples of functions synthesized include repetitive robot tasks and tree traversal algorithms