TerpreT: A Probabilistic Programming Language for Program Induction

Abstract

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.

50 pages, 20 figures, 4 tables

References in corpus (5)

• Church: a language for generative models
• Adding Gradient Noise Improves Learning for Very Deep Networks
• Tightening LP Relaxations for MAP using Message Passing
• Programming with a Differentiable Forth Interpreter
• Adaptive Neural Compilation

Cited by in corpus (38)

• Grammar Variational Autoencoder
• RobustFill: Neural Program Learning under Noisy I/O
• Programming with a Differentiable Forth Interpreter
• D-VAE: A Variational Autoencoder for Directed Acyclic Graphs
• Learning to Infer and Execute 3D Shape Programs
• Programs as Black-Box Explanations
• pix2code: Generating Code from a Graphical User Interface Screenshot
• Neural Program Synthesis with Priority Queue Training
• Learning Compositional Neural Programs with Recursive Tree Search and Planning
• Strong Generalization and Efficiency in Neural Programs
• Logical Rule Induction and Theory Learning Using Neural Theorem Proving
• Recent Advances in Neural Program Synthesis
• Neural Program Search: Solving Programming Tasks from Description and Examples
• Towards Neural Theorem Proving at Scale
• Neural Guided Constraint Logic Programming for Program Synthesis
• Smoothing Methods for Automatic Differentiation Across Conditional Branches
• Deep API Programmer: Learning to Program with APIs
• Why Build an Assistant in Minecraft?
• Synthesizing Action Sequences for Modifying Model Decisions
• REAS: Combining Numerical Optimization with SAT Solving
• Learning Differentiable Programs with Admissible Neural Heuristics
• Differentiable Functional Program Interpreters
• The Three Pillars of Machine Programming
• Probabilistic Neural Programs
• Towards Neural-Guided Program Synthesis for Linear Temporal Logic Specifications
• Program Synthesis Through Reinforcement Learning Guided Tree Search
• Derivatives of Turing machines in Linear Logic
• Summary - TerpreT: A Probabilistic Programming Language for Program Induction
• PLANS: Robust Program Learning from Neurally Inferred Specifications
• Geometry of Program Synthesis
• Automatically Generating Codes from Graphical Screenshots Based on Deep Autocoder
• Formal Fields: A Framework to Automate Code Generation Across Domains
• Type-driven Neural Programming by Example
• Understanding in Artificial Intelligence
• Probabilistic Programming with CuPPL
• Program Synthesis from Visual Specification
• BF++: a language for general-purpose program synthesis
• Sequential Coordination of Deep Models for Learning Visual Arithmetic