Automatic Program Synthesis of Long Programs with a Learned Garbage Collector

By Amit Zohar, Lior Wolf. 2018

78 citations recorded by the source corpus.

We consider the problem of generating automatic code given sample input-output pairs. We train a neural network to map from the current state and the outputs to the program's next statement. The neural network optimizes multiple tasks concurrently: the next operation out of a set of high level commands, the operands of the next statement, and which variables can be dropped from memory. Using our method we are able to create programs that are more than twice as long as existing state-of-the-art solutions, while improving the success rate for comparable lengths, and cutting the run-time by two orders of magnitude. Our code, including an implementation of various literature baselines, is publicly available at this https URL

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Natural Language Processing

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 Computer Vision and Pattern Recognition

In Natural Language Processing

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”
Learning Execution through Neural Code Fusion (2019, methodology): “presentations [11, 17]. However, neither uses concrete program state. 5.2 Using Program State to Guide Program Synthesis There are several works that learn from program state to aid program synthesis [3, 32, 12, 47, 7, 42, 30]. In particular, Balog et al. [3] use neural networks to learn a mapping f”
Learning Compositional Rules via Neural Program Synthesis (2020, methodology): “…al. (2017), and other program synthesis approaches, including enumerative approaches (Balog et al., 2016), execution guided work (Chen et al., 2018; Zohar & Wolf, 2018; Ellis et al., 2019; Yang & Deng, 2019), and hybrid models (Murali et al., 2017; Nye et al., 2019) However, a key difference in…”
Write, Execute, Assess: Program Synthesis with a REPL (2019, methodology): “Finally we contrast our best approach—SMC—with recent execution-guided approaches [12, 13], which both perform a beam-search decoding under a learned policy.”
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).”