Write, Execute, Assess: Program Synthesis with a REPL

By Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, Armando Solar-Lezama. 2019

187 citations recorded by the source corpus.

We present a neural program synthesis approach integrating components which write, execute, and assess code to navigate the search space of possible programs. We equip the search process with an interpreter or a read-eval-print-loop (REPL), which immediately executes partially written programs, exposing their semantics. The REPL addresses a basic challenge of program synthesis: tiny changes in syntax can lead to huge changes in semantics. We train a pair of models, a policy that proposes the new piece of code to write, and a value function that assesses the prospects of the code written so-far. At test time we can combine these models with a Sequential Monte Carlo algorithm. We apply our approach to two domains: synthesizing text editing programs and inferring 2D and 3D graphics programs.

Subfields: Artificial Intelligence, Control and Systems Engineering, Information Systems, Natural Language Processing, Code Generation & Program Synthesis

How researchers see this paper

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

In Artificial Intelligence

In Control and Systems Engineering

In Information Systems

In Natural Language Processing

In Code Generation & Program Synthesis

Citations in the corpus

Reasoning Like Program Executors (2022, background): “Other lines of research leverage program execution in inference as a reliable sanity guarantee for generated programs by pruning non-executable candidates (Wang et al., 2018b; Chen et al., 2019b, 2021; Odena et al., 2020; Ellis et al., 2019; Chen et al., 2019b; Sun et al., 2018; Zohar and Wolf, 2018”
CodeT: Code Generation with Generated Tests (2022, methodology): “This execution-guided approach has been widely adopted in various code-related tasks, such as code generation (Chen et al., 2021; Li et al., 2022b; Shi et al., 2022), code translation (Roziere et al., 2021), and program synthesis (Chen et al., 2018; Ellis et al., 2019).”
Learning to Synthesize Programs as Interpretable and Generalizable Policies (2021, background): “[43] Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando SolarLezama.”
In-IDE Code Generation from Natural Language: Promise and Challenges (2021, methodology): “to automatically generate functions, with some recent advances that use machine learning models [9, 20, 26, 103].”
Learning Compositional Rules via Neural Program Synthesis (2020, methodology): “We are inspired by work such as RobustFill [11], enumerative approaches [16], execution guided work [17, 18, 10, 19], and hybrid models [20, 21].”
Learning to Represent Programs with Property Signatures (2020, methodology): “Deep learning methods have shown promise at automatically generating programs from a small set of input-output examples (Balog et al., 2016; Devlin et al., 2017; Ellis et al., 2018b; 2019b).”
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].”
Language Models Can Teach Themselves to Program Better (2022, methodology): “Finally, the self-play pipeline could be combined with the popular topic of search strategies for code generation [e.g., Li et al., 2022; Le et al., 2022; Ellis et al., 2019].”
Planning with Large Language Models for Code Generation (2023, methodology): “To determine the effectiveness of the tree search algorithm, we considered another baseline, Sequential Monte-Carlo-Guided Transformer Decoding (SMCG-TD), that replaces the tree search algorithm component with a sequential Monte-Carlo algorithm (Ellis et al., 2019).”
DreamCoder: bootstrapping inductive program synthesis with wake-sleep library learning (2021, background): “Existing neural program synthesis systems pair a fixed DSL to a learned neural network that guides program search [4, 15, 18, 38, 42].”
LEGO: Latent Execution-Guided Reasoning for Multi-Hop Question Answering on Knowledge Graphs (2021, methodology): “…improve the synthesizer performance, including text-to-SQL tasks (Wang et al., 2018), synthesis of sequential program statements (Sun et al., 2018b; Zohar & Wolf, 2018; Ellis et al., 2019), and synthesis of programs including nested statements or branches (Odena et al., 2020; Chen et al., 2019a).”
Structural Language Models of Code (2019, background): “…problem: program synthesis approaches are often tailored to domain-speciﬁc languages (Gulwani, 2011; Polozov & Gulwani, 2015; De-vlin et al., 2017; Ellis et al., 2019), while other recent approaches generate code in general languages like Java and 1 Technion, Israel 2 Tel Aviv University 3…”
A large-scale benchmark for few-shot program induction and synthesis (2021, methodology): “This mode is restricted to our subset of C++ (that all programs in P ROG RESbelong to), but it is useful for methods that use partial executions to guide synthesis (Ellis et al., 2019).”
BUSTLE: Bottom-up program-Synthesis Through Learning-guided Exploration (2020, background): “Another approach is to rewrite a programming language so that it can be evaluated “left-to-right”, allowing values to be used to prioritize the search in an actor-critic framework (Ellis et al., 2019).”