# Differentiable Functional Program Interpreters

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

## Key facts

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

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

- [ProTo: Program-Guided Transformer for Program-Guided Tasks](https://mlsanity.com/paper/2110.00804/) (2021)
- [Smoothing Methods for Automatic Differentiation Across Conditional Branches](https://mlsanity.com/paper/2310.03585/) (2023)
- [Learning to Theorize the World from Observation](https://mlsanity.com/paper/2605.03413/) (2026)
- [Understanding in Artificial Intelligence](https://mlsanity.com/paper/2101.06573/) (2021)
- [Towards Neural Functional Program Evaluation](https://mlsanity.com/paper/2112.04630/) (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)

Programming by Example (PBE) is the task of inducing computer programs from input-output examples. It can be seen as a type of machine learning where the hypothesis space is the set of legal programs in some programming language. Recent work on differentiable interpreters relaxes the discrete space of programs into a continuous space so that search over programs can be performed using gradient-based optimization. While conceptually powerful, so far differentiable interpreter-based program synthesis has only been capable of solving very simple problems. In this work, we study modeling choices that arise when constructing a differentiable programming language and their impact on the success of synthesis. The main motivation for the modeling choices comes from functional programming: we study the effect of memory allocation schemes, immutable data, type systems, and built-in control-flow structures. Empirically we show that incorporating functional programming ideas into differentiable programming languages allows us to learn much more complex programs than is possible with existing differentiable languages.