Bayesian Sketch Learning for Program Synthesis

By Vijayaraghavan Murali, Swarat Chaudhuri, C. Jermaine. 2017

38 citations recorded by the source corpus.

We present a Bayesian statistical approach to the problem of automatic program synthesis. Our synthesizer starts by learning, offline and from an existing corpus, a probabilistic model of real-world programs. During synthesis, it is provided some ambiguous and incomplete evidence about the nature of the programming task that the user wants automated, for example sets of API calls or data types that are relevant for the task. Given this input, the synthesizer infers a posterior distribution over type-safe programs that assigns higher likelihood to programs that, according to the learned model, are more likely to match the evidence. We realize this approach using two key ideas. First, our learning techniques operate not over code but syntactic abstractions, or sketches, of programs. During synthesis, we infer a posterior distribution over sketches, then concretize samples from this distribution into type-safe programs using combinatorial techniques. Second, our statistical model explicitly models the full intent behind a synthesis task as a latent variable. To infer sketches, we first estimate a posterior distribution on the intent, then use samples from this posterior to generate a distribution over possible sketches. We show that our model can be implemented effectively using the new neural architecture of Bayesian encoder-decoders, which can be trained with stochastic gradient descent and yields a simple inference procedure. We implement our ideas in a system, called Bayou, for the synthesis of API-heavy Java methods. We train Bayou on a large corpus of Android apps, and find that the trained system can often synthesize complex methods given just a few API method names or data types as evidence. The experiments also justify the design choice of using a latent intent variable and the levels of abstraction at which sketches and evidence are defined.

Subfields: Information Systems, Software, Probabilistic & Bayesian Methods, Code Generation & Program Synthesis

How researchers see this paper

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

In Information Systems

In Software

In Probabilistic & Bayesian Methods

In Code Generation & Program Synthesis

Citations in the corpus

CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding and Generation (2021, methodology): “The program synthesis [47, 58, 62, 74, 17, 40, 90] extends the text-to-code generation task aims to generate programs from a specification [21], such as pseudocode, natural language description, and input/output examples.”
Multi-Level Variational Autoencoder: Learning Disentangled Representations from Grouped Observations (2017, methodology): “While not directly related to our work, Murali et al. [2017] perform computer program synthesis using grouped user-supplied example programs, and Allamanis et al. [2017] learn continuous semantic representations of mathematical and logical expressions.”
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).”
code2vec: learning distributed representations of code (2018, methodology): “Several works have investigated the properties of source code as bimodal: it is at the same time executable for machines, and readable for humans [Allamanis et al. 2015a, 2016, 2015b; Iyer et al. 2016; Murali et al. 2017; Zilberstein and Yahav 2016].”
Neural Program Synthesis with Priority Queue Training (2018, neutral): “…2016; Zaremba et al., 2016; Barone & Sennrich, 2017; Beltramelli, 2017; Cai et al., 2017; Devlin et al., 2017; Hu et al., 2017; Guu et al., 2017; Johnson et al.; Liang et al., 2017; Murali et al., 2017; Parisotto et al., 2016; Rabinovich et al., 2017; Vigueras et al., 2017; Yin & Neubig, 2017).”
Structural Language Models for Any-Code Generation (2019, background): “…et al., 2016; Shin et al., 2019) or SQL (Yu et al., 2018; Dong and Lapata, 2018), while other recent approaches generate code in general languages like Java and C#, but severely restrict the syntax, vocabulary or nature of the generated expressions (Murali et al., 2017; Brockschmidt et al., 2019a).”
Adversarial examples for models of code (2019, background): “duction Neural models of code have achieved state-of-the-art performance on various tasks such as prediction of variable names and types [1, 5, 11, 42], code summarization [2, 3, 20], code generation [4, 13, 35], code search [15, 30, 44], and bug finding [39,43,46]. In other domains, such as compute”
Structural Language Models of Code (2019, background): “, 2017), while other recent approaches generate code in general languages like Java and C#, but severely restrict the syntax, vocabulary, domain, or nature of the generated programs (Murali et al., 2018; Brockschmidt et al., 2019a; Young et al., 2019; Ellis et al., 2019).”
Neural Attribute Machines for Program Generation (2017, methodology): “A recent body of work uses neural techniques [26, 27, 28] to solve this problem.”
When deep learning met code search (2019, background): “ping productivity by exploiting an aligned corpus of code and natural language. Allamanis et al. [2] proposes a probablistic model to synthesize a program snippet from a natural language query. Bayou [25] is a system that uses deep neural networks to synthesize code programs from a few API calls and”
Retrieval on source code: a neural code search (2018, methodology): “Several recent work [2, 11, 15, 18] have shown how to generate code snippets given a natural language query.”