Source-linked AI summary
Structured Generative Models of Natural Source Code
Chris J. Maddison, Daniel Tarlow
TL;DR
The paper asks how to build generative models that capture the rich sequential, hierarchical, and compiler-constrained structure of natural source code. It introduces structured tree-traversal models with distributed representations and compiler integration, then finds that appropriate structure yields large quantitative improvements and more realistic samples. The approach is efficient to learn but leaves several modeling challenges open.
Problem
Generative models of natural source code must represent sequential and hierarchical structure, naturalness, and code-specific structural constraints.
Method
The paper builds Log-bilinear Tree-Traversal models over compiler-derived ASTs, using compiler reasoning and scope information to model structured code generation.
Results
The models yield large quantitative improvements over baselines and produce more realistic samples, while deterministic traversal variables allow efficient learning.
Takeaways & Limitations
Structured generative modeling of source code provides a useful framework for leveraging compiler abstractions in machine learning models of code.
Takeaways & Limitations
The model leaves open high-level task structure and uses a naive Block-statement model that significantly contributes to log probabilities.
Abstract
from arXiv · showhide
We study the problem of building generative models of natural source code (NSC); that is, source code written and understood by humans. Our primary contribution is to describe a family of generative models for NSC that have three key properties: First, they incorporate both sequential and hierarchical structure. Second, we learn a distributed representation of source code elements. Finally, they integrate closely with a compiler, which allows leveraging compiler logic and abstractions when building structure into the model. We also develop an extension that includes more complex structure, refining how the model generates identifier tokens based on what variables are currently in scope. Our models can be learned efficiently, and we show empirically that including appropriate structure greatly improves the models, measured by the probability of generating test programs.
1. Introduction
Machine learning can address source-code tasks by modeling natural source code directly, using its available data and statistical structure. The paper develops structured generative models that capture code structure and compiler-related constraints, and reports substantially improved modeling results.
- Motivation: Source code is abundant in public repositories and educational assignments, creating an opportunity for machine learning methods.The paper motivates source-code modeling through the availability of large collections of human-written code.
- Motivation: A generative source-code model can support multiple tasks as queries on one learned model, including completion and bug fixing.The paper frames code completion as conditional sampling and bug fixing as model-based denoising.
- Modelling challenge: Building a useful model requires representing source code from high-level program structure through language constraints and low-level naming details.The generative formulation is intended to model all of these aspects jointly.
- Contribution: The proposed models combine sequential and hierarchical structure, distributed representations, and compiler-like reasoning for natural source code.The paper introduces Log-bilinear Tree-Traversal models and focuses empirically on C# using Roslyn compiler data structures.
2. Modelling Source Code
The paper represents source code as compiler-derived abstract syntax trees rather than flat token sequences. It uses traversal variables to model context dependence that ordinary PCFG independence assumptions miss, including dependencies among identifiers and scopes.
- Hierarchical Representation: A flat token sequence represents nested constructs inefficiently, whereas an abstract syntax tree compactly captures hierarchical program structure.For loops illustrate why nested code benefits from a hierarchical representation.
- Hierarchical Representation: AST internal nodes correspond to compiler-level expressions and statements, while children tuples contain nodes or tokens.The AST provides the representation over which the generative models define distributions.
- Hierarchical Representation: AST structure can determine which variables are in scope at different program locations, making it useful for reasoning about source code.This scope information is one reason the paper chooses ASTs as its primary representation.
- Modelling Context Dependence: PCFGs generate child tuples independently of the rest of the tree, which loses contextual dependencies and can produce nonsensical identifier usage.Basic syntactic constraints may remain satisfied even when variable and method names are unrelated.
- Modelling Context Dependence: Traversal variables evolve during generation and condition child distributions on the AST context generated so far.They extend the model beyond the independence assumption of a PCFG.
3. Log-bilinear Tree-Traversal Models
LTTs generate ASTs depth-first with a stack while using sequential traversal variables and distributed representations to condition children. Extensions add deterministic structure, richer node types, and scope-aware identifier generation.
- Tree-traversal generation: LTTs generate ASTs depth-first by popping nodes from a stack, expanding internal nodes into children, and labeling tokens as encountered.Traversal variables are updated when internal nodes are popped, so each variable corresponds to a partial generated tree.
- Tree-traversal generation: The model defines a root prior, a children-tuple distribution conditioned on the parent and traversal state, and a transition distribution for traversal variables.With depth-first traversal, emitted tokens follow their observed code order; the stack makes the model a probabilistic pushdown process.
- Distributed parameterization: A log-bilinear parameterization scores children tuples by combining representations of parent-state pairs, children tuples, and child biases.The children distribution is obtained by exponentiating and normalizing the negative energy over training-observed children tuples.
- Distributed parameterization: Representations use D-dimensional rows of indexed matrices, while diagonal context matrices modulate variable contributions by position.The parameter count grows linearly in the traversal-state dimension, allowing high-dimensional traversal variables without exponential data fragmentation.
- Structured extensions: LTT extensions permit traversal variables to depend on prior AST elements, enrich node types, and compose children representations with deterministic scope reasoning.Deterministic traversal variables can condition on the generated partial tree; uncertain annotations may instead increase generation cost and worsen held-out log probabilities.
- Structured extensions: Identifier generation first chooses local or global sampling, then uses a scope representation containing feature vectors for currently in-scope variables.A variable is in scope when its identifier matches a string identifier in the scope set; feature representations combine identifier and attribute vectors.
5. Inference and Learning in LTTs
LTT learning is straightforward when traversal variables are deterministic because compiler-derived AST information makes model variables observed. Latent traversal variables couple productions and require restricted exact inference for efficient learning.
- Deterministic variables: Compiler-computed ASTs determine deterministic traversal variables, making all model variables observed and decomposing learning into independent production-level problems.The resulting productions can be stacked into one training set and optimized with standard gradient methods, including NCE.
- Latent variables: Latent traversal variables couple learning across productions from the same tree, so exact inference is restricted to one discrete latent variable per step.The restriction preserves efficient exact inference; lifting it would require approximate inference.
6. Related Work
LTTs relate to established sequence and grammar models through special cases, while prior source-code modeling work used simpler NLP, Bayesian grammar, or nonparametric approaches.
- Connections to existing models: An LTT becomes an HMM when children encode token transitions, and becomes a PCFG when traversal has one state and children distributions have finite support.These correspondences position LTTs as a broader structured framework containing familiar sequential and grammar models as special cases.
- Prior source-code modeling: Earlier source-code modeling studies addressed related tasks with simple NLP models, nonparametric Bayesian grammars, or nonparametric priors over program structure.The cited work includes code naturalness modeling, code-idiom learning, and models encoding structural priors on programs.
7. Experimental Analysis
Experiments on 2261 C# programs compare baseline, deterministic, latent, scope-aware, and hybrid LTT models using average log probability per token. Combining hierarchy and sequence features substantially improves performance, while scope modeling further improves the previous best model and shifts cost from token generation toward tree generation.
- Experimental setup: The experiments use 2261 C# programs and evaluate average log probability per token, with disjoint users in the test set.The dataset contains 140k lines of code and 2.4M AST parent nodes; splits are 70% train, 10% validation, and 20% test.
- Baselines and basic models: The basic log-bilinear LTT-/0 model performs nearly identically to the standard PCFG, whereas the log-bilinear 10-gram model outperforms basic n-gram baselines.The 10-gram model allows longer contexts and generalizes better; results are reported in Figure 4.
- Deterministic traversal variables: Hierarchy-only features outperform sequence-only features, while combining both in LTT-HiSeq yields a substantial gain over either individual feature set.The hierarchy features encode depth, parent and ancestor history; sequence features encode the last 10 generated tokens.
- Latent traversal variables: Latent traversal variables improve over LTT-/0, but their gains are smaller than those from deterministic features; adding them to LTT-HiSeq was too slow for practical training.These latent models use 32 discrete states and are trained with EM; a log-bilinear HMM performs far worse than the other models.
- Scope model: Adding the scope model produces a large improvement over LTT-HiSeq, using identifier, type, declaration-order, and last-assignment features for variables.The scope model uses deterministic compiler-like reasoning about variables currently available in context.
- Cost analysis: The full scope model incurs slightly higher tree-generation cost than Hi&Seq but pays a much smaller token-generation cost.The extra tree cost reflects choosing whether IdentifierTokens come from local or global scopes.
- Cost analysis: Global-scope IdentifierTokens account for 30.1% of total cost, followed by locally covered IdentifierTokens at 10.9% and Blocks at 10.6%.The breakdown suggests extending scope coverage and improving the model of Block sequences.
- Qualitative evaluation: Samples from LTT-HiSeq-Scope capture high-level organization, variable use and reuse, and patterns such as int variables appearing inside square brackets.The qualitative evaluation samples for loops and full source-code files.
8. Discussion
The models capture important structure in natural source code, improving quantitative measures and the realism of generated samples. The paper frames probabilistic source-code modeling as a rich area for machine-learning research while identifying substantial remaining challenges.
- The models leverage compiler work to capture source-code structure, producing large quantitative improvements and more realistic samples than baselines.The paper emphasizes both measured gains and qualitative sample quality.
- Remaining challenges include representing program purpose and discovering high-level structure related to accomplishing tasks.
- The Block-statement model is naive and significantly contributes to log probabilities, motivating more sophisticated sequence models for Block children.
- The scope model could be extended to other child tuples and method calls, while richer handling of typing rules remains promising.The simple node-annotation approach to typing hurt the models.
- Probabilistic source-code modeling offers a rich set of problems that could advance machine-learning research.
EM Learning for Latent Traversal Variable LTTs
EM learning for latent traversal-variable LTTs uses compiler-determined structure where available, forward-backward inference for latent variables, and stochastic updates for model parameters.
- Compiler-computable deterministic variables make their probability terms equal to 1, removing them from the latent-variable computation.
- The remaining latent-variable sum is computed with the forward-backward algorithm within a standard EM formulation.
- In the E step, Q distributions are optimized given current parameters; in the M step, learning decomposes across productions.
- Transition probabilities use tabular representations with stochastic gradient updates, while emission terms use standard log-bilinear training.
- Latent traversal values are sampled from their Q distributions so unmodified log-bilinear training methods can process the resulting examples.
More Experimental Protocol Details
The experiments selected unvalidated hyperparameters manually and trained latent-variable models with databatched forward-backward inference followed by incremental AdaGrad updates.
- Unvalidated hyperparameters were manually selected on a training-set subsample by optimizing training log probabilities.Examples include minibatch size, initialization scale, and learning rate.
- EM training used databatches of 10 full programs, followed by minibatches for an incremental M step with AdaGrad.
Smoothed Model
The smoothed model assigns support beyond Roslyn AST trees, so the reported AST log probability becomes a lower bound on the full program log probability. Smoothing combines broad-support defaults with token and child-count models.
- The model mixes each child distribution with a broad-support default to avoid zero probability for unsupported test-set tuples.The assumed token and internal-node-type sets come from the Roslyn API.
- For token-only children, the default distribution is an additively smoothed empirical token model.
- For other child distributions, smoothing models tuple size with a Poisson distribution and child identities independently with additive smoothing.
- Because smoothing gives positive support to non-Roslyn trees, the reported AST log probability is only a lower bound on logp(α).Multiple trees can therefore be consistent with one token sequence, preventing the earlier direct computation of logp(α).