  Program synthesis is challenging largely because of the difficulty of search
in a large space of programs. Human programmers routinely tackle the task of
writing complex programs by writing sub-programs and then analyzing their
intermediate results to compose them in appropriate ways. Motivated by this
intuition, we present a new synthesis approach that leverages learning to guide
a bottom-up search over programs. In particular, we train a model to prioritize
compositions of intermediate values during search conditioned on a given set of
input-output examples. This is a powerful combination because of several
emergent properties. First, in bottom-up search, intermediate programs can be
executed, providing semantic information to the neural network. Second, given
the concrete values from those executions, we can exploit rich features based
on recent work on property signatures. Finally, bottom-up search allows the
system substantial flexibility in what order to generate the solution, allowing
the synthesizer to build up a program from multiple smaller sub-programs.
Overall, our empirical evaluation finds that the combination of learning and
bottom-up search is remarkably effective, even with simple supervised learning
approaches. We demonstrate the effectiveness of our technique on two datasets,
one from the SyGuS competition and one of our own creation.
