Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis

Program synthesis is the task of automatically generating a program with a specification. Recent years have seen proposal of a number of approaches for program synthesis, many of which adopt a sequence paradigm similar to neural machine translation, in which-to-sequence models are trained to maximize the likelihood of known programs. While achieving impressive results, this strategy has two limitations. First, it ignores Program Aliasing: the fact that many programs may satisfy a given specification (especially with specifications such as a few input-output examples). By maximizing likelihood of only a single reference program, it penalizes many correct programs, which can adversely affect the synthesizer. Second, this strategy overlooks the fact that programs have a syntax that can be efficiently checked. To address the first limitation, perform reinforcement learning on top of a supervised model with an that explicitly maximizes the likelihood of generating semantically programs. For addressing the second limitation, we introduce a training that directly maximizes the probability of generating syntactically programs that fulfill the specification. We show that our contributions to improved accuracy of the models, especially in cases where the training is limited.