Bayesian Sketch Learning for Program Synthesis

Vijayaraghavan Murali, Swarat Chaudhuri, Chris JermainearXiv 2017 · arXiv

Introduction

Generating source code using neural networks is a significant challenge in artificial intelligence. Unlike natural language, programming languages are highly brittle; a single syntax error or type mismatch can render an entire program non-functional. Furthermore, source code is often saturated with low-level details, such as arbitrary variable names, which act as "noise" and hinder the generalization capabilities of standard machine learning models.

This paper introduces BAYOU, a system designed for conditional program generation. Given sparse "intent" labels—such as specific API calls or data types—BAYOU generates complete, type-safe Java method bodies. The core philosophy behind BAYOU is to bridge the gap between neural intuition and symbolic precision by generating high-level "program sketches" rather than raw source code.

Methodology: The Two-Step Synthesis Pipeline

The researchers propose a novel architecture that separates the creative task of structural prediction from the rigorous task of syntactic validation. This is achieved through a two-step process: Neural Sketching followed by Combinatorial Concretization.

The BAYOU pipeline: Evidence $X$ is mapped to a latent sketch $Y$, which is then concretized into a final program $Prog$.

1. Neural Sketching

Instead of predicting every character of code, the system learns to produce a "sketch." A sketch is a tree-structured representation of a program that preserves control flow (loops, conditionals, try-catch blocks) and API calls but abstracts away variable names and specific arguments. This abstraction allows the model to focus on the underlying logic of the program.

The model uses a Gaussian Encoder-Decoder (GED). The encoder takes input "evidence" (sets of API calls, types, and keywords) and maps them to a latent space $Z$ using a Gaussian distribution. A tree-structured Recurrent Neural Network (RNN) then decodes samples from this latent space into a program sketch.

2. Combinatorial Concretization

Once a sketch is generated, it must be "fleshed out" into a valid Java program. BAYOU employs a type-guided combinatorial search to find variable names and expressions that satisfy the constraints of the Java type system. This step ensures that 100% of the generated programs are well-formed and parsable, a feat that direct-learning models often fail to achieve.

Experimental Evaluation and Results

The system was trained on a massive dataset of approximately 150,000 Java methods extracted from 1,500 Android applications. These methods were translated into a simplified intermediate language called AML to capture the essence of API-heavy code.

BAYOU (specifically the GED-Sk model) was compared against baseline models that attempted to learn Abstract Syntax Trees (ASTs) directly. The results were stark:

  • Accuracy: BAYOU correctly predicted the exact AST of a test program 59% of the time when given full evidence, compared to just 13% for the baseline.
  • Robustness: Under partial observability (only 25% of labels provided), BAYOU maintained a 21% accuracy rate, while the baseline's performance collapsed to 2%.

Key Insights: API Knowledge in Latent Space

One of the most compelling findings of the study is the organization of the model's latent space. By visualizing the latent representations using t-SNE, the researchers discovered that the model naturally clusters different APIs based on their functionality.

t-SNE visualization of the model's latent space, showing natural clustering of different Java and Android API packages.

As shown in the visualization, packages like java.io and android.webkit form distinct clusters. Interestingly, the model even identified sub-clusters within a single API, such as separate groupings for file reading versus file writing operations. This suggests that the neural network effectively "learned" the semantic relationships between different library components without explicit supervision.

Conclusion

BAYOU demonstrates the power of a hybrid neural-symbolic approach to program synthesis. By using a neural network to handle the high-level "creative" leap of structural sketching and a symbolic search to handle the "rigorous" details of type-safety, the system achieves state-of-the-art results in generating complex Java code. Future work may involve integrating natural language processing to allow developers to describe their intent in plain English, further lowering the barrier to automated code generation.

Summary updated

Abstract

We study the problem of generating source code in a strongly typed, Java-like programming language, given a label (for example a set of API calls or types) carrying a small amount of information about the code that is desired. The generated programs are expected to respect a "realistic" relationship between programs and labels, as exemplified by a corpus of labeled programs available during training. Two challenges in such conditional program generation are that the generated programs must satisfy a rich set of syntactic and semantic constraints, and that source code contains many low-level features that impede learning. We address these problems by training a neural generator not on code but on program sketches, or models of program syntax that abstract out names and operations that do not generalize across programs. During generation, we infer a posterior distribution over sketches, then concretize samples from this distribution into type-safe programs using combinatorial techniques. We implement our ideas in a system for generating API-heavy Java code, and show that it can often predict the entire body of a method given just a few API calls or data types that appear in the method.
BibTeX
@misc{murali2017bayesian,
  author = {Vijayaraghavan Murali and Swarat Chaudhuri and Chris Jermaine},
  title = {{Bayesian Sketch Learning for Program Synthesis}},
  year = {2017},
  eprint = {1703.05698},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1703.05698},
}
Figure