BUSTLE: Bottom-up program-Synthesis Through Learning-guided Exploration

  • 2020-07-28 17:46:18
  • Augustus Odena, Kensen Shi, David Bieber, Rishabh Singh, Charles Sutton
  • 41

Abstract

Program synthesis is challenging largely because of the difficulty of searchin a large space of programs. Human programmers routinely tackle the task ofwriting complex programs by writing sub-programs and then analysing theirintermediate results to compose them in appropriate ways. Motivated by thisintuition, we present a new synthesis approach that leverages learning to guidea bottom-up search over programs. In particular, we train a model to prioritizecompositions of intermediate values during search conditioned on a given set ofinput-output examples. This is a powerful combination because of severalemergent properties: First, in bottom-up search, intermediate programs can beexecuted, providing semantic information to the neural network. Second, giventhe concrete values from those executions, we can exploit rich features basedon recent work on property signatures. Finally, bottom-up search allows thesystem substantial flexibility in what order to generate the solution, allowingthe synthesizer to build up a program from multiple smaller sub-programs.Overall, our empirical evaluation finds that the combination of learning andbottom-up search is remarkably effective, even with simple supervised learningapproaches. We demonstrate the effectiveness of our technique on a new data setfor synthesis of string transformation programs.

 

Quick Read (beta)

loading the full paper ...