Learning to Synthesize.

In many scenarios we need to find the most likely program under a localcontext, where the local context can be an incomplete program, a partialspecification, natural language description, etc. We call such problem programestimation. In this paper we propose an abstract framework, learning tosynthesis, or L2S in short, to address this problem. L2S combines four tools toachieve this: syntax is used to define the search space and search steps,constraints are used to prune off invalid candidates at each search step,machine-learned models are used to estimate conditional probabilities for thecandidates at each search step, and search algorithms are used to find the bestpossible solution. The main goal of L2S is to lay out the design space tomotivate the research on program estimation.

We have performed a preliminary evaluation by instantiating this frameworkfor synthesizing conditions of an automated program repair (APR) system. Thetraining data are from the project itself and related JDK packages. Compared toACS, a state-of-the-art condition synthesis system for program repair, ourapproach could deal with a larger search space such that we fixed 4 additionalbugs outside the search space of ACS, and relies only on the source code of thecurrent projects.