Source-linked AI summary
Generative Code Modeling with Graphs
Marc Brockschmidt, Miltiadis Allamanis, Alexander L. Gaunt, Oleksandr Polozov
TL;DR
Source-code generation must satisfy syntax and semantics while producing likely programs, a balance current models often miss. The paper augments grammar-driven generation with deterministic program-graph structure and neural message passing, and reports semantically meaningful expression generation that outperforms strong baselines. The approach is demonstrated on small expressions conditioned on imprecise code context, with possible applications to program repair and code review.
Problem
Source-code generators struggle to combine formal syntactic and semantic constraints with the production of natural, likely programs.
Method
The model augments a partially generated syntax tree with deterministic relationship edges and uses neural message passing to guide subsequent grammar-based expansions.
Results
The model generates small, semantically meaningful expressions from imprecise context information and outperforms a range of strong baselines.
Takeaways & Limitations
The approach may support program repair and code review, where proposals can be scored or unlikely expressions highlighted.
Takeaways & Limitations
The model’s variable-use edges follow lexical order rather than dataflow analysis, so they do not represent full dataflow relationships.
Abstract
from arXiv · showhide
Generative models for source code are an interesting structured prediction problem, requiring to reason about both hard syntactic and semantic constraints as well as about natural, likely programs. We present a novel model for this problem that uses a graph to represent the intermediate state of the generated output. The generative procedure interleaves grammar-driven expansion steps with graph augmentation and neural message passing steps. An experimental evaluation shows that our new model can generate semantically meaningful expressions, outperforming a range of strong baselines.
1 INTRODUCTION
Source-code generation must reconcile formal syntax and semantics with the likelihood of natural programs. The paper proposes a graph-based generative procedure and evaluates it through ExprGen and broader baseline comparisons.
- Motivation: Current approaches typically prioritize either formal correctness or realistic code, leaving the other modality inadequately handled.Synthesis systems may produce unlikely programs, while learned code models may generate semantically irrelevant programs.
- Approach: The proposed model augments a grammar-generated syntax tree with deterministic relationship edges and applies neural message passing during generation.Generation interleaves grammar expansion, graph augmentation, and representation updates for intermediate program states.
- Approach: The method generalizes graph-based generation to structured objects by incorporating rich structural information available deterministically at generation time.Its graphs augment generated trees rather than independently generating all nodes and edges.
- Evaluation: ExprGen evaluates generation of small, semantically complex expressions conditioned on source-code context.The task is presented as one of the paper’s central contributions alongside the graph-based procedure and experimental evaluation.
- Evaluation: The paper reports a comprehensive evaluation against a range of baseline methods from the literature.The supplied introduction identifies this evaluation as part of the paper’s contribution, without reporting numerical results here.
2 BACKGROUND & TASK
The paper frames code generation as sequential AST construction under context, then introduces ExprGen as hole completion for whole expressions. Its setting uses surrounding code and in-scope variables to guide generation.
- Background: Earlier token-sequence models can produce syntactically incorrect code, motivating grammar-based abstract syntax tree generation.Grammar-based generation selects production rules instead of directly emitting an unconstrained token sequence.
- Background: AST generation expands one node at a time using grammar production rules, turning code generation into context-dependent classification decisions.The partial AST and context determine the production choice at each step.
- ExprGen: ExprGen fills a hole in an existing program by generating whole Boolean, arithmetic, or string expressions rather than single tokens.The task uses surrounding code, including information about following code, without another formal specification.
- ExprGen: In ExprGen, the context comprises pre-existing code around the hole and variables in scope at that location.These in-scope variables can guide the decoding procedure.
3 GRAPH DECODING FOR SOURCE CODE
The decoder combines grammar-driven AST expansion with a deterministically constructed attribute graph and neural message passing. Typed edges encode syntactic, semantic, and usage relationships, while graph representations guide production, variable, and literal choices.
- Generation procedure: At each step, the decoder expands the left-most AST node using a grammar production selected from a representation informed by the augmented graph.The grammar-driven strategy converts generation into sequential production-rule classification while the graph supplies richer context.
- Training: The complete system trains the encoder, graph propagation process, and decoder choice functions end-to-end with maximum likelihood and no pre-trained components.Context and variable representations initialize nodes in the augmented syntax graph.
- Graph representation: The model lifts grammar-based AST decoding into a graph by associating each AST node with inherited and synthesized attribute nodes.Inherited information comes from context and generated AST parts; synthesized information summarizes a subtree.
- Graph representation: Graph edges are added deterministically as nodes are generated, encoding child, parent, sibling, token-order, variable-use, and inherited-to-synthesized relationships.NextUse follows lexical order rather than dataflow analysis, and InhToSyn edges were found helpful for training.
- Neural message passing: Attribute representations are computed with GGNN-style message passing that transforms incoming states by edge type, sums them, and applies a gated update.Representations are computed in topological order, starting from the context encoder’s representation of the root inherited attribute.
- Generation procedure: Variables are selected from the in-scope set, preventing unknown or out-of-scope variable predictions, while literals combine vocabulary generation with context copying.Unknown tokens can arise only through the literal-generation operation.
4 RELATED WORK
Source-code generation research has progressed from token sequences to grammar-guided trees, with models differing in how much partial-program information guides expansion. The paper positions ExprGen as a distinct hole-completion task requiring arbitrary contextual code and complex expressions.
- Grammar-based generation: Earlier code generators produced token sequences, whereas newer approaches use the target grammar to generate syntactically structured trees.Tree-based models differ mainly in the information used to select the next expansion rule.
- Grammar-based generation: Tree decoders range from parent-based representations to recurrent tree traversals and bounded learned AST traversals for selecting expansion rules.The cited approaches include Maddison & Tarlow, R3NN-based models, and PHOG.
- ExprGen novelty: Prior work had not, to the authors’ knowledge, studied generative filling of a program hole with an expression.ExprGen differs from API-call completion by handling arbitrary surrounding code and constructing potentially complex expressions from a small operator set.
- ExprGen novelty: ExprGen also differs from prior variable-selection work because it generates expressions rather than choosing one variable from candidate contexts.This makes ExprGen a generative task rather than a single-variable prediction problem.
5 EVALUATION
The evaluation tests ExprGen on C# code contexts using sequence- and graph-based encoders, multiple decoders, and validity, fit, and semantic metrics. Graph-informed models perform best on semantic measures, while transfer to unseen projects remains difficult.
- Dataset: The dataset contains expressions extracted from 593 highly-starred open-source C# projects, restricted to numeric, Boolean, string, or array types without user-defined functions.Expressions were removed from otherwise existing programs to create hole-completion instances.
- Encoders: Seq encodes tokens around the hole and in-scope variables with bidirectional GRUs, while G uses an 8-step graph neural network over program context.G represents the hole with a fresh dummy node and reads out representations for the hole and contextual variables.
- Metrics: The evaluation measures per-token perplexity, well-typedness, and retrieval of the ground-truth expression, alongside syntactic validity.Lower perplexity indicates better fit to the real data distribution, while well-typedness tests compatibility with the original context.
- Quantitative evaluation: Graph encoder architectures perform best overall on semantic measures, and NAG performs best on most measures while being least affected by transfer.All models generate syntactically valid code, but semantic performance varies with the information available about partially generated programs.
- Quantitative evaluation: Transfer to unseen projects with new project-specific vocabularies substantially worsens results.The evaluation describes this degradation as expected, with NAG appearing least impacted among the evaluated models.
- Task difficulty: The strongest models achieve no more than 50% accuracy on the top prediction, although professional developers can easily solve most instances.The context does not provide a precise formal specification, limiting classical logico-deductive synthesis for this task.
- Qualitative evaluation: Qualitative examples show G →NAG using relationships between variables, whereas G →ASN often omits relevant variables; both can learn common string-processing patterns without recovering the exact literal.These examples illustrate semantic and contextual differences among the strongest evaluated models.
6 DISCUSSION & CONCLUSIONS
The paper concludes that graph representations of partially generated programs can guide generation of small, semantically interesting expressions from imprecise context. It identifies possible applications in program repair and code review, and extensions to related domains.
- Conclusion: The proposed model augments partial programs into graphs and uses graph neural networks to compute representations that guide the remainder of generation.The approach leverages known semantics of partially generated programs during generation.
- Conclusion: The approach generates small but semantically interesting expressions from very imprecise context information.The conclusion presents this as an experimentally demonstrated capability.
- Applications: The model could support program repair by scoring repair proposals and code review by highlighting very unlikely expressions.The paper also suggests applications in semantic parsing, neural program synthesis, and text generation.
A DATASET SAMPLES
The training-set samples show code contexts from multiple projects for the ExprGen task, with highlighted expressions designated for generation.
- Highlighted expressions in the training snippets are the targets to be generated for ExprGen.
- The samples include code from Lean, BotBuilder, Chocolatey, CommonMark.NET, Humanizer, Nancy, and OpenLiveWriter projects.
B SAMPLE GENERATIONS
The test-set examples present ground-truth expressions alongside suggestions from different models, covering varied code contexts and candidate expressions with associated percentages.
- Test-set snippets pair highlighted ground-truth expressions with suggestions produced by different models.
- Other suggestions generate method calls, string operations, boolean conditions, arithmetic expressions, and tokenized unknowns.
- Suggestions include comparisons such as paramCount > methodParamCount and lineNumber < endLineNumber.
- The examples span projects and contexts including StyleCop, ShareX, acat, Abot, OpenLiveWriter, cassette, and Afterthought.