PaperlayerView exact revision on arXiv

Source-linked AI summary

Structural Language Models of Code

Uri Alon, Roy Sadaka, Omer Levy, Eran Yahav

arXiv:1910.00577v4cs.LGcs.PLstat.ML

TL;DR

Code completion must handle missing code without restricting its vocabulary or structure, while earlier approaches limited what they could generate. SLM models code as an AST and predicts its nodes from paths through the tree, achieving state-of-the-art Java results and outperforming existing models on restricted C# completion.

  • Problem

    Any-code completion concerns predicting missing code without vocabulary or structure restrictions, whereas prior approaches have limited the syntax, vocabulary, domain, or kind of generated programs.

    Source: §1 · p. 1

  • Method

    SLM models source and target code as the same AST and computes conditional node probabilities using paths leading to each target node.

    Source: §1 · p. 1

  • Results

    SLM outperforms baselines across Java any-code and restricted C# completion; Java exact-match accuracy@1 is 18.04% (previous SOTA: 16.93%).

    Source: §1 · p. 1, §9 · p. 9

  • Takeaways & Limitations

    The paper demonstrates general-purpose code generation in restricted and unrestricted settings across two languages.

    Source: §9 · p. 9

    Without considering the entire project and its dependencies, compilation-based filtering cannot remove candidates that fail to compile; compiler-guided generation is left to future work.

    Source: §7 · p. 8

Abstract

from arXiv · show

We address the problem of any-code completion - generating a missing piece of source code in a given program without any restriction on the vocabulary or structure. We introduce a new approach to any-code completion that leverages the strict syntax of programming languages to model a code snippet as a tree - structural language modeling (SLM). SLM estimates the probability of the program's abstract syntax tree (AST) by decomposing it into a product of conditional probabilities over its nodes. We present a neural model that computes these conditional probabilities by considering all AST paths leading to a target node. Unlike previous techniques that have severely restricted the kinds of expressions that can be generated in this task, our approach can generate arbitrary code in any programming language. Our model significantly outperforms both seq2seq and a variety of structured approaches in generating Java and C# code. Our code, data, and trained models are available at http://github.com/tech-srl/slm-code-generation/ . An online demo is available at http://AnyCodeGen.org .

1. Introduction

The paper introduces any-code completion, which targets unrestricted code snippets, and models source and target code jointly as trees. SLM achieves state-of-the-art Java results and outperforms existing models on restricted C# completion.

1. Introduction

  • Code completion has been constrained by the challenge of unbounded syntax and user-defined symbols, and prior general-language approaches restrict generated syntax, vocabulary, domain, or program type.Earlier synthesis approaches are often tailored to domain-specific languages.Source: §1 · p. 1
  • Any-code completion predicts a missing program part from the rest, without restricting the vocabulary or structure of code in a general-purpose language.The task generalizes restricted completion that limited targets to primitive types and excluded user-defined functions.Source: §1 · p. 1
  • Because input and output are both code, the approach models them jointly rather than using separate encoders and decoders for different modalities.The paper presents joint modeling as a way to pursue better generalization.Source: §1 · p. 1
  • SLM models source and target code as the same AST, estimating program probability through conditional node probabilities based on all paths leading to each target node.It generates the target AST node by node.Source: §1 · p. 1
  • 18.04% exact-match accuracy@1 and 24.83% accuracy@5 establish Java any-code completion state of the art over previous SOTA values of 16.93% and 23.17%.The paper also reports 37.61% accuracy@1 versus 26.42% for existing models on restricted C# completion.Source: §1 · p. 1

2. Code Generation as Structural Language Modeling

The method assigns probability to code represented as an AST, decomposes that probability into conditional node predictions, and uses paths through the partial tree to provide context. Special end markers support node-by-node tree generation.

2. Code Generation as Structural Language Modeling

  • Tree modeling is motivated by the possibility of better generalization and less learning capacity spent relearning syntactic patterns from program text.The passage presents these as the intuition behind representing code as a tree.Source: §2 · p. 2
  • A depth-first traversal orders AST nodes for chain-rule probability decomposition, with completion conditioning on the observed tree before scoring target nodes.The framework also allows traversal orderings other than depth-first.Source: §2 · p. 2
  • At each step, the model predicts the next node using paths from leaves and the root, whose structural and distant context can inform the target.For example, paths can reveal an array's type and that a target occurs inside a loop.Source: §2 · p. 3, Figure 2 · p. 3
  • The model uses partial paths from leaves to nodes being expanded, extending them by predicting their next node rather than relying only on complete leaf-to-leaf paths.This representation addresses alternatives that linearize the partial tree or use only the root-to-target path, which can create long distances or omit context.Source: §2 · pp. 2–3
  • EOSnode marks that a parent has no more children, while EOStok ends a terminal's subtoken sequence to control tree arity and generation depth.For example, toLowerCase is split into subtokens followed by EOStok.Source: §2 · pp. 3–4
  • Predicting individual nodes lets the model defer a function's object and method name and avoid choosing argument-count-specific production rules in advance.The passage contrasts this with production-based generation, which can require predicting a method before its invoking object.Source: §2 · p. 4

3. Model Architecture

The model predicts code nodes from partial AST paths by encoding and aggregating those paths, then choosing AST-node or subtoken predictions with a syntactic copy mechanism.

3. Model Architecture

  • The model encodes each partial AST path, contextualizes and aggregates the path set, then predicts the target node using a subtoken vocabulary and syntactic copy mechanism.The path set represents the partial AST available when predicting each node.Source: §3 · p. 4

3.1. Encoding AST Paths

  • AST nodes are represented by their type and sibling index, and a unidirectional LSTM encodes each path; shared prefixes are cached across suffixes.Caching overlapping path prefixes speeds training and inference.Source: §3.1 · p. 4

3.2. Aggregating Multiple Paths

  • A transformer contextualizes encoded paths, while an index-informed root-path representation attends over them to form the prediction vector.The aggregation also receives the target child’s index and combines the attended paths with the root-path encoding.Source: §3.2 · p. 4

3.3. Predicting with a Syntactic Copy Mechanism

  • The model predicts AST nodes from node-type embeddings and scores subtokens through both a limited vocabulary and copying from context leaves.Copy scores use each leaf’s AST-path encoding; scores for the same symbol are summed and normalized.Source: §3.3 · pp. 4–5

4. Experimental Setup

The experiments use constructed Java any-code and restricted C# completion benchmarks, compare against adapted and task-specific baselines, and report exact-match and tree-match metrics. The implementation uses a compact model and specified training and inference settings.

4.1. Benchmarks

  • The Java benchmark uses expression targets from Java-small methods, split by project, and excludes tests, long methods, and targets already present in context.It contains 1.3M/10k/20k train/dev/test examples.Source: §4.1 · p. 5
  • The restricted C# benchmark follows Brockschmidt et al. (2019) by limiting targets to expressions without non-primitive types or user-defined functions.It uses 30 GitHub projects and contains 16k/8k/3k train/dev/test examples.Source: §4.1 · p. 5
  • Evaluation reports exact-match accuracy at 1 and 5, plus tree@k, which ignores leaf values to distinguish syntactic errors from incorrect subtokens.For example, x > 1 and y > 2 count as tree-match identical because both have the structure NAME > INT.Source: §4.1 · p. 5

4.2. Baselines

  • The comparison retrains baselines on the same datasets, including sequence-to-sequence, Java-specific, and C#-specific models, with adaptations such as copy mechanisms and subtokenization.The baselines include Transformer and BiLSTM encoder-decoders, seq2tree, Java NL-to-code models, and a C# graph model.Source: §4.2 · pp. 5–6

4.3. Implementation and Hyperparameter Settings

  • The model has 15M parameters; training uses cross-entropy and Adam, while inference uses width-5 beam search optimized for accuracy@1.The architecture uses 512-dimensional embeddings, two 256-unit LSTM layers, and four transformer layers with eight attention heads.Source: §4.3 · p. 6

5. Results

SLM outperforms the reported Java baselines and all models on restricted C# completion. The results also distinguish accuracy from tree-structure scores and suggest possible reasons for baseline differences.

Any-Code Completion: Java

  • 3.8% acc@1 and 3.4% acc@5 over Transformersmall; SLM also improves over the two strongest baselines by over 1.1% acc@1 and 0.78% acc@5.The Transformersmall comparison is identified as having a closer parameter count to SLM.Source: §5 · p. 6
  • NMT baselines outperform code-specific baselines; the authors hypothesize that their more general design better fits these comparisons.They note that the code-specific baselines were designed for different tasks, and that some lack a copy mechanism.Source: §5 · p. 6
  • Seq2tree has the highest tree@k among baselines, while SLM achieves higher acc@k and tree@k.The authors note that syntax can also benefit NMT models.Source: §5 · p. 6

Restricted Completion: C#

  • SLM achieves significant gains over all models on restricted C# completion, including copy-equipped seq2seq and seq2tree baselines.Those baselines substantially outperform the original GNN→NAG state of the art in this setting.Source: §5 · p. 6, Table 2 · p. 6
  • The authors suggest SLM’s advantage over GNN→NAG may relate to the GNN bottleneck for long-range messages, which paths handle naturally in their model.This is offered as a possible explanation, not a demonstrated cause.Source: §5 · p. 7

6. Ablation Study

The ablations examine path-based modeling, parameter tying, encoder–decoder choices, root attention, and copying. Together, they identify advantages for joint modeling and specific components of the SLM design.

Results

  • SLM outperforms Paths→Paths, supporting the importance of jointly modeling context and target subtree through parameter tying.Paths→Paths uses separate encoder and decoder weights, unlike SLM.Source: §6 · p. 7
  • Paths→Paths and seq2seq baselines each outperform Paths→Seq and Seq→Path, suggesting matching encoder and decoder types suits code completion.Paths→Seq generates target code as a subtoken sequence; Seq→Path encodes context as subtokens and generates the missing subtree. The authors contrast code completion with tasks whose input and output modalities differ.Source: §6 · p. 7
  • Paths→Paths performs better than seq2seq baselines, showing an advantage for paths over textual sequences even without parameter tying.Paths→Paths uses separate encoder and decoder weights.Source: §6 · p. 7
  • Removing root attention degrades acc@1 and acc@5 by 3.6% to 6.3%, underscoring the role of dynamically attending to context paths.The variant replaces attention with max pooling and concatenates the root-to-parent path instead of using it as the attention query.Source: §6 · p. 7
  • Removing the copy mechanism causes a 7.3% to 9.1% degradation, consistent with the repeated use of program symbols and identifiers.The No Copy variant replaces copying with a much larger 25k-subtoken vocabulary instead of 1k.Source: §6 · p. 7

7. Qualitative Analysis

Tree matches substantially outnumber exact matches, with many errors involving identifiers or literals; compiler-guided filtering could improve candidate ranking.

7. Qualitative Analysis

  • Tree-match accuracy exceeds exact-match accuracy across models, and SLM has higher acc@k than baselines but substantial room to improve tree@k.The analysis focuses on cases where the structure is correct but identifiers prevent an exact match.Source: §7 · p. 7
  • Figure 4 illustrates tree-matches ranked above exact matches, including a fifth candidate logically equivalent to the ground truth.Its examples include a literal mismatch and a conditional expression whose fifth candidate is logically equivalent.Source: §7 · p. 7, Figure 4 · p. 8
  • 30% of top tree-match errors involve a single subtoken mismatch, while 74% involve a whole-token mismatch.The authors suggest that better name prediction could further improve results.Source: §7 · p. 8
  • Project-aware compilation could filter invalid candidates and move the correct candidate from fifth to second; compiler-guided generation is left for future work.The example's invalid candidates call methods absent from the currentAttempt object.Source: §7 · p. 8

8. Related Work

The paper frames code generation through partial AST paths, which generalize several structural approaches. It distinguishes this general-purpose, context-conditioned task from prior methods limited by domain, vocabulary, or input modality.

8. Related Work

  • Partial AST paths generalize approaches using ancestor nodes, previous-action encodings, or a single context node, while also representing many manually designed graph relations.Unlike PHOG's single context leaf, SLM conditions on every previously traversed leaf and its syntactic path.Source: §8 · p. 8
  • Many program-generation approaches are bounded to domain-specific languages, while unconditional general-purpose code generation does not address fitting code to a given context.Bielik et al. (2016) use a dynamic DSL expression for a single context; Maddison & Tarlow (2014) and Amodio et al. (2017) generate unconditional code.Source: §8 · pp. 8–9
  • Unlike Brockschmidt et al. (2019), this work permits general-purpose generation with any types and names rather than primitive types or arrays, a closed vocabulary, and no user-defined functions.The paper reports significantly better performance than that approach.Source: §8 · p. 9
  • API-to-code, edit-to-code, and natural-language-to-code methods differ from this task because they model input separately from output code, whereas this task has code on both sides.Code translation approaches can also require strong alignment between source and target trees.Source: §8 · p. 9

9. Conclusion

The paper presents joint AST modeling with a structural language model for any-code completion and reports state-of-the-art performance across restricted and unrestricted settings in two languages. It also identifies potential applications and makes code, datasets, and trained models publicly available.

9. Conclusion

  • The approach reaches state-of-the-art performance across challenging benchmarks in restricted and unrestricted settings in two languages, outperforming programming-language-oriented and NMT baselines.The paper describes generating general-purpose code in both settings.Source: §9 · p. 9
  • The method jointly models an AST and its missing subtree using a structural language model.The conclusion presents this as the paper's approach to any-code completion.Source: §9 · p. 9
  • Proposed applications include code completion, detecting and fixing unlikely code, and re-ranking solutions from another synthesizer or solver; code, datasets, and trained models are public.The authors describe broader future applications as an expectation.Source: §9 · p. 9

Supplementary Material

Figure 6 reports dataset statistics, measured on the training set unless otherwise noted.

Supplementary Material

  • Figure 6 presents dataset statistics, with measurements taken on the training set unless otherwise noted.The supplied passage gives no individual statistics.Source: Figure 6 · p. 10

A. Data Statistics

The appendix describes Java split sampling and the validation-based procedure for choosing configurations and checkpoints. It also reports tested settings and shared-prefix computation for AST paths.

A. Data Statistics

  • Shared AST-path prefixes can be computed once across time steps, avoiding repeated work when the prefix is longer than either suffix.Figure 7 illustrates the shared prefix from the leaf to Greater.Source: Figure 7 · p. 10
  • Java validation and test sets were random samples of 10,000 and 20,000 examples, respectively; raw and preprocessed datasets were slated for release with the final version.Source: A. Data Statistics · p. 10

B. Additional Evaluation Details

  • Beam search ran on validation after each training iteration; configurations and checkpoints were selected by accuracy@1, followed by a single test evaluation.Source: B. Additional Evaluation Details · p. 10
  • Tested settings included LSTM or Transformer path encoders, 256- or 512-dimensional subtoken embeddings, and learning-rate decay every 10,000, 20,000, or 40,000 steps.Source: B. Additional Evaluation Details · p. 10

C. Qualitative Analysis cont. - Correct Tree, Incorrect Names

Table 4 reports stronger exact-match results and greater potential improvement than leading baselines when single-token or subtoken errors are tolerated. The appendix also describes partial-token copying and test-set examples for Java and restricted C# completion.

C. Qualitative Analysis cont. - Correct Tree, Incorrect Names

D. Copying Single Subtokens

  • Position-specific subtoken scoring lets the model copy part or all of a token, such as generating setX from getX by generating set and copying X.Source: D. Copying Single Subtokens · p. 11

E. Example: Usefulness of Copy Mechanism

F. Java Examples

G. C# Examples

Related papers

Loading 1910.00577v4…