Source-linked AI summary
Write, Execute, Assess: Program Synthesis with a REPL
Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, Armando Solar-Lezama
TL;DR
Program synthesis must search through programs whose small syntactic changes can produce large semantic differences. The paper combines a REPL with policy and value models in Sequential Monte Carlo search, and validates the framework on text-editing and 2D/3D graphics tasks, where it achieves faster and more reliable synthesis. The authors identify control-flow programs with conditionals and loops as an immediate future direction.
Problem
Program synthesis must handle the difficult relationship between program syntax and semantics while searching among many possible programs.
Method
The system uses a REPL to execute partial programs and combines a code-writing policy and value function with Sequential Monte Carlo search.
Results
The framework achieves faster, more reliable synthesis in text-editing and 2D/3D graphics domains.
Takeaways & Limitations
Integrating execution and assessment into program search supports stochastic exploration of alternative partial programs across two synthesis domains.
Takeaways & Limitations
The presented framework does not yet address programs with control flow such as conditionals and loops.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper frames program synthesis as an iterative process of writing, executing, and assessing partial code. Its REPL-based stochastic search combines learned policy and value models, improving synthesis across text-editing and graphics domains.
- Motivation: Program synthesis benefits from transitioning between writing code, executing partial programs, and assessing their resulting behavior.The authors motivate this workflow as analogous to human trial-and-error programming.
- Approach: A REPL immediately executes partial programs, exposing semantics and bridging the gap between syntax and meaning.This reduces the burden on neural models to learn the difficult syntax-semantics mapping.
- Approach: Sequential Monte Carlo searches over alternative program candidates by branching when uncertain, pruning weak branches, and pursuing promising ones.This search emulates iterative coding while managing a large space of partial programs.
- Approach: The system trains a policy to propose code and a value function to evaluate the prospects of the code written so far.At inference, these models are combined with a Sequential Monte Carlo search strategy that samples, executes, and re-weights candidate programs.
- Evaluation: The framework is evaluated on text-editing programs and 2D/3D graphics programs, where it achieves faster and more reliable synthesis.The introduction reports that the approach outperforms alternative methods across these two domains.
2 An Illustrative Example
The illustrative CSG task incrementally constructs a 2D scene program while the REPL renders partial programs and the search uses value estimates to avoid brittle failures.
- CSG Example: CSG synthesizes a target scene by combining primitive shapes with boolean union and subtraction operations.The example uses circles and rotated rectangles represented in a context-free grammar.
- Incremental Construction: The policy extends an initially empty set of in-scope partial programs one action at a time.Actions add primitives or apply boolean combinators to existing subtrees and their arguments.
- REPL Guidance: The REPL executes in-scope partial programs into images, letting the policy condition its next action on semantic states and the specification.This moves the policy input from code syntax toward the rendered image space.
- SMC Search: SMC maintains multiple candidate programs, samples policy extensions, then uses value estimates to prune unpromising branches and prioritize promising ones.This addresses the failure mode in which one incorrect policy action causes the entire synthesis attempt to fail.
3 Our Approach
The approach formulates program synthesis as a goal-conditioned MDP over partial programs, bridges syntax and semantics with a REPL, and searches with learned policy and value functions using SMC.
- Semantic Search Space: Program synthesis is represented as a Markov decision process over partially constructed programs rather than only complete grammar-valid programs.The state includes partial program trees and the goal specification.
- Semantic Search Space: An action is a context-free grammar production, and transitions either instantiate a terminal subtree or combine non-terminal children while removing them from scope.The latter operation is described as garbage collection of the combined children.
- Semantic Search Space: The REPL evaluates each partial program into an executed representation, providing the semantic state used alongside the specification.For a set of programs pp, the REPL state is the set of their executions [[pp]].
- Learning Policy and Value: The policy predicts next actions, while the value function estimates the probability that a partial-program state will lead to a successful program.Because the reward is binary, the value function performs binary classification.
- Learning Policy and Value: The policy is pretrained on synthetic grammar programs and then fine-tuned with the value function from policy rollouts using REINFORCE-style training.Synthetic examples provide specifications, action sequences, and partial-program states; rollout rewards indicate whether the final state satisfies the specification.
- SMC Inference: At inference, SMC interleaves policy sampling, REPL execution, value-based importance reweighting, and resampling across candidate particles.Its stochastic, batched procedure supports anytime search and high GPU throughput.
4 Experiments
Experiments evaluate the REPL-based policy and value-guided search on inverse CAD and string editing. Across both domains, the integrated approach improves search efficiency, generalization, and program quality, though REPL computation can dominate runtime.
- Experimental setup: The evaluation compares REPL-conditioned models and no-REPL baselines across inverse CAD and string editing tasks.The study examines how policy, value function, and REPL components affect program search.
- Inverse CAD: CAD models train on scenes with up to 13 objects and test out of sample on scenes with up to 30 objects in 2D or 20 in 3D.The CAD specification is an image, and partial programs are rendered into distinct canvases for the networks.
- Inverse CAD: The integrated CAD system infers long programs despite a branching factor of approximately 1.3 million per line.The largest successful programs reach 19 lines and 102 tokens in 3D, and 22 lines and 107 tokens in 2D; best-performing ablations scale less far.
- Ablations and efficiency: In CAD, the value function helps beam search and sampling methods, while no-REPL inference can become competitive given a sufficiently large time budget because REPL models repeatedly evaluate CNNs.Qualitatively, the integrated policy, value network, and REPL produce programs closely matching the specifications.
- String editing: Value-guided SMC solves the most string-editing tasks while using less time and fewer node expansions than alternative inference techniques.Figure 7 reports 10x fewer node expansions and less time than previous approaches, with logarithmic x-axes.
- String editing: String-editing testing regularly recovers programs of 40 or more actions despite training programs averaging approximately 8 actions.These recovered programs have description lengths greater than 350 bits.
5 Discussion
The discussion frames the method as a general program-synthesis framework combining execution guidance, value-guided search, and reinforcement-learning formalization. It identifies broader tool integration and richer control flow as future directions.
- Discussion: The framework targets robustness across domains rather than solving only one specialized synthesis problem.The evaluated domains include text processing and graphics program synthesis.
- Discussion: Formalizing synthesis as a Markov decision process exposes reinforcement-learning and planning techniques for execution-guided search.The learned value network improves methods that do not use such value guidance.
- Discussion: The presented framework combines exploration over solution trees with executing and assessing code as it is written.This combines ideas from execution-guided synthesis and value-guided tree search.
- Future directions: Programs with conditionals and loops remain an immediate future direction.The authors suggest Forth-style stack-based languages as a promising REPL-like representation for these operators.
- Future directions: Debuggers and profilers are proposed as tools that could be reinterpreted as modules within program-synthesis systems.The authors connect this integration to writing code more robustly and rapidly like people.
A.1 Graphics Programming Language
The graphics language defines separate 2D and 3D shape-construction grammars with quantized numeric parameters. Synthetic 2D training data further restricts quadrilaterals to rotated rectangles.
- 2D graphics: The 2D grammar generates circles and quadrilaterals with numeric radius, coordinate, and vertex parameters.The listed 2D productions include circles and quadrilaterals.
- 3D graphics: The 3D grammar generates spheres, cubes, and cylinders using numeric coordinates and radii.The numeric grammar ranges over values from 0 to 31 in increments of 4.
- 2D graphics: Although arbitrary quadrilaterals are allowed in principle, synthetic 2D training data restricts them to rectangles rotated by 45-degree increments.More arbitrary rotations would require training a higher-capacity network on more examples.
A.2 String Editing Programming Language
The string-editing language builds programs by concatenating expressions formed from constants, spans, substitutions, and nesting operations. Its grammar supports token, regex, and case-based transformations.
- Program structure: A string-editing program concatenates at most six expressions.Expressions may be functions, nesting expressions, numeric forms, or constant strings.
- Expressions: Function expressions include substring, span, and substitution operations parameterized by indices or regex-related values.The grammar lists six span forms and two substitution forms.
- Nesting and types: Nesting operations include token extraction, case conversion, prefix or suffix extraction, and retrieving all or first matches.Regex types include literal text and digits, while token types include Number, Word, AlphaNum, Digit, Char, AllCaps, Proper, and Lower Case.
A.3 Training details
Training used supervised pretraining followed by REINFORCE, with separate settings for string editing and 2D/3D graphics. The authors performed no hyperparameter search and aimed for an approach insensitive to fine architectural details.
- String Editing: String editing used 24,000 supervised-pretraining iterations followed by 12,000 REINFORCE epochs.Batch sizes were 4,000 for pretraining and 2,000 for REINFORCE.
- String Editing: The RobustFill baseline trained for 50,000 iterations with batch size 32.Its DP-beam feature removed partial programs producing strings that were not prefixes of the desired output.
- 2D/3D Graphics: The 2D/3D graphics models pretrained on random CSG programs, then fine-tuned the policy with REINFORCE and trained the value network separately.Training used approximately three days for pretraining and five days for policy and value-network training on one P100 GPU.
- Design choice: Across both domains, no hyperparameter search was performed.The authors expected tuning to improve results marginally but aimed for generality rather than sensitivity to fine architectural details.
A.4 Data and test-time details
Testing used a two-minute timeout per problem while increasing beam size or particle count until timeout. The experiments used a custom string-editing dataset after near-ceiling performance on an earlier benchmark and procedurally generated held-out graphics scenes.
- Test-time procedure: Testing used a 2-minute timeout per problem and repeatedly doubled the beam or number of particles until timeout.This procedure was applied in both domains.
- String Editing: The original string-editing benchmark produced near-ceiling performance, so the authors designed their own dataset.The original benchmark combined training tasks from with a test corpus from [19].
- 2D/3D Graphics: Held-out graphics tests sampled 30 random scenes with up to 20 objects in 3D and 30 objects in 2D.Scenes were generated from random CSG trees after removing subtrees that did not affect the final render.
A.5 Architecture details
The architectures encode REPL states with domain-specific neural encoders, use a pointer-network policy to produce code, and attach a value function to assess states. The section also reports the no-REPL comparison and the evaluated string-editing results and examples.
- String Editing: The string-editing encoder embeds characters from input, output, committed, and scratch strings, while incorporating spatial mask values.Each example state is encoded separately before pooling into a hidden state used to decode the next action.
- Policy: The graphics policy uses a CNN and pointer network to predict code lines, with pointers selecting partial programs in scope for union and difference operations.The CNN processes the current REPL state, which may contain a variable number of objects.
- Value function: The graphics value function is an additional head over pooled CNN activations.The architecture uses a Deep Set encoding that separately encodes examples and sums their activations.
- Graphics encoders: The graphics state embedding concatenates spec-encoder activations with summed canvas-encoder activations from the REPL state.The spec and canvas are represented as two-channel image input for the canvas encoder.
- No REPL baseline: The no-REPL baseline uses the same CNN and pointer-network architecture but hides objects currently in scope from the pointer network.Instead, it attends to hidden states produced when previously constructed objects entered scope.
- Results and examples: Figure 10 reports string-editing results against the dataset from [6], including tasks solved versus nodes expanded and total time per task.The figure uses logarithmic x-axes; Figure 11 shows examples of long inferred string-editing programs.