DeepCoder: Learning to Write Programs
By Matej Balog, Alexander L. Gaunt, Marc Brockschmidt, Sebastian Nowozin, Daniel Tarlow. 2016
625 citations recorded by the source corpus.
We develop a first line of attack for solving programming competition-style problems from input-output examples using deep learning. The approach is to train a neural network to predict properties of the program that generated the outputs from the inputs. We use the neural network’s predictions to augment search techniques from the programming languages community, including enumerative search and an SMT-based solver. Empirically, we show that our approach leads to an order of magnitude speedup over the strong non-augmented baselines and a Recurrent Neural Network approach, and that we are able to solve problems of difficulty comparable to the simplest problems on programming competition websites.
Subfields: Artificial Intelligence, Information Systems, Natural Language Processing, Code Generation & Program Synthesis, Signal 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
- Mohit Bansal
- Percy Liang
- Yoshua Bengio
- Quoc V. Le
- Sergey Levine
- Luke S. Zettlemoyer
- Jianfeng Gao
- Graham Neubig
In Information Systems
- Charles Sutton
- Miltiadis Allamanis
- Uri Alon
- Eran Yahav
- Rishabh Singh
- Omer Levy
- Michael Pradel
- Koushik Sen
In Natural Language Processing
- Graham Neubig
- Percy Liang
- Luke S. Zettlemoyer
- Mohit Bansal
- Quoc V. Le
- Jianfeng Gao
- Christopher D. Manning
- Jonathan Berant
In Code Generation & Program Synthesis
- Charles Sutton
- Rishabh Singh
- Miltiadis Allamanis
- Uri Alon
- Eran Yahav
- Michael Pradel
- Swarat Chaudhuri
- Marc Brockschmidt
In Signal Processing
- Yoshua Bengio
- Quoc V. Le
- Charles Sutton
- Oriol Vinyals
- Mohammad Norouzi
- Ruslan Salakhutdinov
- Lior Wolf
- Ilya Sutskever
Citations in the corpus
- Competition-level code generation with AlphaCode (2022, methodology): “Learned models can now be used to guide program search (Balog et al., 2016), generate program sketches (Guo et al.”
- Program Synthesis with Large Language Models (2021, methodology): “There has been a recent resurgence of interest in techniques (both symbolic and ‘neuro-symbolic’) for synthesizing programs [Balog et al., 2017, Devlin et al., 2017, Ellis et al., 2018, 2020, Odena et al., 2020], but these techniques have largely been applied to restricted domain-specific languages…”
- Evaluating Large Language Models Trained on Code (2021, methodology): “DeepCoder (Balog et al., 2017) trained a model to predict the functions appearing in source code, which could be used to guide program search.”
- A Survey of Machine Learning for Big Code and Naturalness (2017, background): “ several authors [9, 127, 165, 171], is to relax formal systems into probabilistic. Such systems, however, lack the guarantees formal systems (e.g. soundness) often provide. Alemi etal.[3],Baloget al.[20]andLooset al.[123]followasecondapproachthatmaintainssoundness: they learn input and context-spec”
- InCoder: A Generative Model for Code Infilling and Synthesis (2022, background): “, input-output examples [12, 28, 19, 13], partial implementations [58], or natural language descriptions [74, 73, 72, 42, 18] of the desired program as input.”
- A Retrieve-and-Edit Framework for Predicting Structured Outputs (2018, background): “Code generation is well studied [21, 17, 4, 23, 1], but these approaches have not explored edit-based generation.”
- Programmable Agents (2017, background): “Different approaches to this problem focus on networks that infer programs [3, 10, 22], on networks that execute programs [39, 30, 5] and on networks that jointly do both [14, 17, 38, 29, 13]; although there is much overlap between many of these approaches.”
- RobustFill: Neural Program Learning under Noisy I/O (2017, methodology): “DeepCoder (Balog et al., 2016) trains a neural network to predict a distribution over possible functions useful for a given task from input-output examples, which is used to augment an external search algorithm.”
- Inferring and Executing Programs for Visual Reasoning (2017, background): “Such models can take the form of a feedforward scoring function over operators in a domain-specific language that can be used to guide program search [4], or of a recurrent network that decodes a vectorial program representation into the actual program [22, 26, 34, 46, 47, 48].”
- AutoML-Zero: Evolving Machine Learning Algorithms From Scratch (2020, background): “More recently, program synthesis has focused on solving problems like sorting (Graves et al., 2014), string manipulation (Gulwani et al., 2017; Balog et al., 2017), or structured data QA (Liang et al., 2016).”
- Generalization in anti-causal learning (2018, background): “Similarly, recent approaches to program induction from input-output pairs assist various search techniques with a deep neural net trained to predict certain properties of the program (anti-causal) (Balog et al., 2017).”
- Programmatically Interpretable Reinforcement Learning (2018, methodology): “C ODER (Balog et al., 2016), B AYOU (Murali et al., 2018)), where the network weights are used to guide the program search in a DSL.”
- Neural-Symbolic VQA: Disentangling Reasoning from Vision and Language Understanding (2018, background): “Recent papers have explored using program search and neural networks to recover programs from a domain-specific language [Balog et al., 2017, Neelakantan et al., 2016, Parisotto et al., 2017].”
- code2seq: Generating Sequences from Structured Representations of Code (2018, methodology): “…code and natural language can be used for automatic code summarization (Allamanis et al., 2016), documentation (Iyer et al., 2016), retrieval (Allamanis et al., 2015b), and even generation (Balog et al., 2016; Rabinovich et al., 2017; Yin and Neubig, 2017; Devlin et al., 2017; Murali et al., 2017).”
- Abstract Syntax Networks for Code Generation and Semantic Parsing (2017, background): “Meanwhile, a separate line of work has focused on the problem of program induction from input-output pairs (Balog et al., 2016; Liang et al., 2010; Menon et al., 2013).”
- Tree-to-tree Neural Networks for Program Translation (2018, background): “A recent line of research study using neural networks for code generation [5, 10, 25, 19, 26, 32].”
- TerpreT: A Probabilistic Programming Language for Program Induction (2016, methodology): “We remain optimistic about extensions to the TERPRET framework which allow differentiable interpreters to handle problems involving perceptual data [Gaunt et al., 2016a], and about using machine learning techniques to guide search-based techniques [Balog et al., 2016].”
- JuICe: A Large Scale Distantly Supervised Dataset for Open Domain Context-based Code Generation (2019, background): “…in the form of logical forms (Zettlemoyer and Collins, 2005), λ -DCS (Liang et al., 2013), regular expressions (Kushman and Barzilay, 2013; Locascio et al., 2016), database queries (Iyer et al., 2017; Zhong et al., 2017) and general purpose programs (Balog et al., 2016; Allamanis et al., 2015).”
- Neural Program Synthesis with Priority Queue Training (2018, background): “…Joulin & Mikolov, 2015; Kaiser & Sutskever, 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…”
- Memory Augmented Policy Optimization for Program Synthesis and Semantic Parsing (2018, background): “Consider the problem of learning to map a natural language question x to a structured query a in a programming language such as SQL ( e.g. , [68]), or converting a textual problem description into a piece of source codeas in programming competitions ( e.g. , [5]).”