# TerpreT: A Probabilistic Programming Language for Program Induction

arXiv: https://arxiv.org/abs/1608.04428 · HTML: https://mlsanity.com/paper/1608.04428/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Aug 2016.

## Built on by (most cited first, 13 of 13)

- [Communicating Natural Programs to Humans and Machines](https://mlsanity.com/paper/2106.07824/) (2021)
- [From Perception to Programs: Regularize, Overparameterize, and Amortize](https://mlsanity.com/paper/2206.05922/) (2022)
- [Efficient Symbolic Policy Learning with Differentiable Symbolic Expression](https://mlsanity.com/paper/2311.02104/) (2023)
- [Unsupervised Learning of Neurosymbolic Encoders](https://mlsanity.com/paper/2107.13132/) (2021)
- [Smoothing Methods for Automatic Differentiation Across Conditional Branches](https://mlsanity.com/paper/2310.03585/) (2023)
- [Uncertainty Quantification for Neurosymbolic Programs via Compositional Conformal Prediction](https://mlsanity.com/paper/2405.15912/) (2024)
- [BF++: a language for general-purpose program synthesis](https://mlsanity.com/paper/2101.09571/) (2021)
- [Algorithmic Language Models with Neurally Compiled Libraries](https://mlsanity.com/paper/2407.04899/) (2024)
- [Geometry of Program Synthesis](https://mlsanity.com/paper/2103.16080/) (2021)
- [CTSketch: Compositional Tensor Sketching for Scalable Neurosymbolic Learning](https://mlsanity.com/paper/2503.24123/) (2025)
- [Understanding in Artificial Intelligence](https://mlsanity.com/paper/2101.06573/) (2021)
- [Compile Once, Differentiate Everywhere: A Differentiable Meta-Circular Interpreter](https://mlsanity.com/paper/2606.09930/) (2026)
- [Differentiate the Evaluator, Not the Program: An Efficient Runtime Representation for Neuro-Symbolic Learning](https://mlsanity.com/paper/2607.03574/) (2026)

## Abstract (arXiv)

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.