Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis

By Rudy Bunel, Matthew J. Hausknecht, Jacob Devlin, Rishabh Singh, Pushmeet Kohli. 2018

231 citations recorded by the source corpus.

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

Subfields: Electrical and Electronic Engineering, Information Systems, Software, Natural Language Processing, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Electrical and Electronic Engineering

In Information Systems

In Software

In Natural Language Processing

In Reinforcement Learning

Citations in the corpus

Neural Execution Engines: Learning to Execute Subroutines (2020, background): “[8] develops a custom architecture that is tested on performing arithmetic, but trains on symbols in the range of [1 , 12] and does not demonstrate strong generalization.”
Neural Logic Machines (2019, methodology): “Neural program induction and synthesis (Neelakantan et al., 2016; Reed & De Freitas, 2016; Kaiser & Sutskever, 2016; Parisotto et al., 2017; Devlin et al., 2017; Bunel et al., 2018; Sun et al., 2018) are recently introduced to solve problems by synthesizing computer programs with neural augmentation”
Programmatically Interpretable Reinforcement Learning (2018, methodology): “There have also been some recent approaches to use R L for learning to search programs in DSLs (Bunel et al., 2018; Abolaﬁa et al., 2018).”
Automatically Composing Representation Transformations as a Means for Generalization (2018, background): “The ﬁrst as-Automatically sumes pre-speciﬁed transformations and learns the structure (from dense supervision on execution traces to sparse-rewards) [13, 14, 18, 22, 25, 28, 65, 87, 90].”
Lifelong Learning of Compositional Structures (2020, background): “The majority of such methods either learn the structure for piecing together a given set of components [30, 4, 5] or learn the set of components given a known structure for how to compose them [3].”
WILDS: A Benchmark of in-the-Wild Distribution Shifts (2020, neutral): “…and software engineering in various ways: automatic code completion (Raychev et al., 2014; Svyatkovskiy et al., 2019), program synthesis (Bunel et al., 2018; Kulal et al., 2019), program repair (Vasic et al., 2019; Yasunaga and Liang, 2020), code search (Husain et al., 2019), and code…”
Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing (2018, methodology): “. Our source code is available at goo.gl/TXBp4e 1 Introduction There has been a recent surge of interest in applying policy gradient methods to various application domains including program synthesis [26, 17, 68, 10], dialogue generation [25, 11], architecture search [69, 71], game [53, 31] and cont”
BUSTLE: Bottom-up program-Synthesis Through Learning-guided Exploration (2020, background): “One can also train a machine learning model to emit whole programs token-by-token using an encoder-decoder neural architecture (Bunel et al., 2018; Devlin et al., 2017; Parisotto et al., 2017), but when one does this one loses the ability to inspect outputs of intermediate programs.”
Neural Learning of One-of-Many Solutions for Combinatorial Problems in Structured Output Spaces (2020, background): “Another line of work, which comes close to ours is the task of Neural Program Synthesis [Devlin et al., 2017, Bunel et al., 2018].”
NAPS: Natural Program Synthesis Dataset (2018, background): “…on program synthesis from examples for single domain of programming: string transformations (Robust-Fill (Devlin et al., 2017b), Neuro-Symbolic Program Synthesis (Parisotto et al., 2016) and Deep API Programmer (Bhupatiraju et al., 2017)) or Karel (Devlin et al. (2017a), Bunel et al. (2018)).”
Execution-Guided Neural Program Synthesis (2018, methodology): “We evaluate our techniques on the Karel task (Bunel et al., 2018; Devlin et al., 2017a), the largest publicly available benchmark for input-output program synthesis, on which the most performant model in the past can achieve only an accuracy of around 77% (Bunel et al., 2018).”
Teaching Large Language Models to Self-Debug (2023, background): “, 2022), programming by examples (Devlin et al., 2017; Bunel et al., 2018; Chen et al., 2019), and code translation (Roziere et al.”
Neural Production Systems (2021, background): “Neural networks have been studied as a way to address the problems of learning procedural behavior and program induction (Graves et al., 2014; Reed & De Freitas, 2015; Neelakantan et al., 2015; Cai et al., 2017; Xu et al., 2018; Trask et al., 2018; Bunel et al., 2018; Li et al., 2020).”
SpreadsheetCoder: Formula Prediction from Semi-structured Context (2021, background): “Our problem brings several new challenges compared to related work in programming by example (Gulwani, 2011; Bunel et al., 2018; Balog et al., 2017), semantic parsing (Popescu et al., 2003; Zhong et al., 2017; Yu et al., 2018) and source code completion (Ray-chev et al., 2014; Li et al., 2018;…”
Synthetic Data for Deep Learning (2019, background): “ipulation programs [218] and soon branched into deep learning, using recurrent architectures to guide search-based methods [614] or to generate programs in encoder-decoder architectures [106,146]. In [76,546], reinforcement 44 Input: j=8584 for x in range(8): j+=920 b=(1500+j) print((b+7567)) Target”
From LSAT: The Progress and Challenges of Complex Reasoning (2021, methodology): “As the symbolic executor is non-differential, policy-gradient methods are usually employed to train the model [74, 87].”
CodeRL: Mastering Code Generation through Pretrained Models and Deep Reinforcement Learning (2022, methodology): “More related to our work are RL-based program synthesis [Guu et al., 2017, Bunel et al., 2018, Liang et al., 2018, Zhong et al., 2018] and execution-guided synthesis approaches [Ellis et al., 2019, Chen et al., 2021b].”
AutoPandas: neural-backed generators for program synthesis (2019, methodology): “Additionally, since DataFrames are not of a fixed size, the CNNs used to encode fixed-size grid-based examples in Bunel et al. [2018] are also not applicable.”