TerpreT: A Probabilistic Programming Language for Program Induction

By Alexander L. Gaunt, Marc Brockschmidt, Rishabh Singh, Nate Kushman, Pushmeet Kohli, Jonathan Taylor, Daniel Tarlow. 2016

129 citations recorded by the source corpus.

We study machine learning formulations of inductive program synthesis; given input-output examples, we try to synthesize source code that maps inputs to corresponding outputs. Our aims are to develop new machine learning approaches based on neural networks and graphical models, and to understand the capabilities of machine learning techniques relative to traditional alternatives, such as those based on constraint solving from the programming languages community. Our key contribution is the proposal of TerpreT, a domain-specific language for expressing program synthesis problems. TerpreT is similar to a probabilistic programming language: a model is composed of a specification of a program representation (declarations of random variables) and an interpreter describing how programs map inputs to outputs (a model connecting unknowns to observations). The inference task is to observe a set of input-output examples and infer the underlying program. TerpreT has two main benefits. First, it enables rapid exploration of a range of domains, program representations, and interpreter models. Second, it separates the model specification from the inference algorithm, allowing like-to-like comparisons between different approaches to inference. From a single TerpreT specification we automatically perform inference using four different back-ends. These are based on gradient descent, linear program (LP) relaxations for graphical models, discrete satisfiability solving, and the Sketch program synthesis system. We illustrate the value of TerpreT by developing several interpreter models and performing an empirical comparison between alternative inference algorithms. Our key empirical finding is that constraint solvers dominate the gradient descent and LP-based formulations. We conclude with suggestions for the machine learning community to make progress on program synthesis.

Subfields: Probabilistic & Bayesian Methods

How researchers see this paper

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

In Probabilistic & Bayesian Methods

Citations in the corpus

A Survey of Machine Learning for Big Code and Naturalness (2017, background): “This is an interesting emerging area of research [101] but does not yet scale to the types of problems considered by the programming language and software engineering community [59, 69]; also see Devlin et al.”
RobustFill: Neural Program Learning under Noisy I/O (2017, background): “…program synthesis, where the program is generated by a neural network conditioned on the I/O examples (Balog et al., 2016; Parisotto et al., 2017; Gaunt et al., 2016; Riedel et al., 2016), and (2) neural program induction, where network learns to generate the output directly using a latent…”
DeepCoder: Learning to Write Programs (2016, background): “However, Gaunt et al. (2016) showed that differentiable interpreterbased program induction is inferior to discrete search-based techniques used by the programming languages community.”
A Compositional Object-Based Approach to Learning Physical Dynamics (2016, methodology): “This approach of starting with a general sketch of a program and ﬁlling in the speciﬁcs is inspired by ideas from the program synthesis community (Ellis et al., 2015; Gaunt et al., 2016; Solar-Lezama, 2008).”
Grammar Variational Autoencoder (2017, background): “Recently there is increased interest in training generative models to construct more complex, discrete data types such as arithmetic expressions (Kusner & Hernández-Lobato, 2016), source code (Gaunt et al., 2016; Riedel et al., 2016) and molecules (Gómez-Bombarelli et al., 2016b).”
Neuro-Symbolic Program Synthesis (2016, background): “While some recently proposed methods (Kurach et al., 2015; Gaunt et al., 2016; Riedel et al., 2016; Bunel et al., 2016) do learn interpretable programs, they still need to learn a separate neural network model for each individual task.”
Neural Program Synthesis with Priority Queue Training (2018, background): “…2016; Kurach et al., 2015; Neelakantan et al., 2016; Reed & de Freitas, 2016; Andreas et al., 2016; Balog et al., 2017; Bhoopchand et al., 2016; Gaunt et al., 2016; Khanh Dam et al., 2016; Neelakantan et al., 2017; Riedel et al., 2016; Schaechtle et al., 2016; Zaremba et al., 2016; Barone &…”
Automatic programming: The open issue? (2019, methodology): “Other approaches from which we might learn and adapt include inductive logic programming [44] and the related ADATE [45], and more recent incarna-tions such as DeepCoder [4], IGOR2 [31] and MagicHaskeller [28], Flashfill [15] and TerpreT [14].”
Neural Program Lattices (2016, methodology): “Similar to NTMs, many of the proposed architectures have used differentiable memory (Kurach et al., 2016; Graves et al., 2016; Weston et al., 2014; Sukhbaatar et al., 2015b; Neelakantan et al., 2016; Gaunt et al., 2016; Feser et al., 2016), while others have used REINFORCE (Williams, 1992) to train ”
Automatic Program Synthesis of Long Programs with a Learned Garbage Collector (2018, unknown): “Our setting also differs from frameworks that complete partial programs, where parts of the program are provided or otherwise constrained [7, 8].”
pix2code: Generating Code from a Graphical User Interface Screenshot (2017, background): “[4], the generation of source code is enabled by learning the relationships between input-output examples via differentiable interpreters.”
Towards Neural Theorem Proving at Scale (2018, background): “…without the explicit symbolic representations of a program (Graves et al., 2014; 2016; Kaiser and Sutskever, 2016; Neelakantan et al., 2016; Andrychowicz and Kurach, 2016), and consequently with it (Reed and de Freitas, 2016; Bosnjak et al., 2017; Gaunt et al., 2016; Parisotto et al., 2016).”
Why Build an Assistant in Minecraft? (2019, background): “[28] Alexander L Gaunt, Marc Brockschmidt, Rishabh Singh, Nate Kushman, Pushmeet Kohli, Jonathan Taylor, and Daniel Tarlow.”
Neurosymbolic Programming (2021, background): “Subsequent work on differentiable program interpreters (Gaunt et al., 2016; Riedel et al., 2016; Gaunt et al., 2017) connected continuous relaxations with automatic differentiation.”
On the difficulty of benchmarking inductive program synthesis methods (2017, methodology): “it is only known how TerpreT performs on the Basic Execution Results of applying TerpreT, Flash Fill, MagicHaskeller (MH) and PushGP on the Basic Execution Models problems from [2].”