Stepping Stones to Inductive Synthesis of Low-Level Looping Programs
This work addresses the problem of automating program synthesis for general looping programs, which is incremental as it builds on existing methods to handle more complex tasks like sorting and game puzzles.
The authors tackled the challenge of synthesizing low-level looping programs from input/output examples, presenting MAKESPEARE, a delayed-acceptance hillclimbing method that succeeded on the previously unsolved 'Collatz Numbers' problem and achieved strong performance on benchmarks, including rapid sorting of integer arrays.
Inductive program synthesis, from input/output examples, can provide an opportunity to automatically create programs from scratch without presupposing the algorithmic form of the solution. For induction of general programs with loops (as opposed to loop-free programs, or synthesis for domain-specific languages), the state of the art is at the level of introductory programming assignments. Most problems that require algorithmic subtlety, such as fast sorting, have remained out of reach without the benefit of significant problem-specific background knowledge. A key challenge is to identify cues that are available to guide search towards correct looping programs. We present MAKESPEARE, a simple delayed-acceptance hillclimbing method that synthesizes low-level looping programs from input/output examples. During search, delayed acceptance bypasses small gains to identify significantly-improved stepping stone programs that tend to generalize and enable further progress. The method performs well on a set of established benchmarks, and succeeds on the previously unsolved "Collatz Numbers" program synthesis problem. Additional benchmarks include the problem of rapidly sorting integer arrays, in which we observe the emergence of comb sort (a Shell sort variant that is empirically fast). MAKESPEARE has also synthesized a record-setting program on one of the puzzles from the TIS-100 assembly language programming game.