PaperlayerView exact revision on arXiv

Source-linked AI summary

Neural Program Generation Modulo Static Analysis

Rohan Mukherjee, Yeming Wen, Dipak Chaudhari, Thomas W. Reps, Swarat Chaudhuri, Chris Jermaine

arXiv:2111.01633v2cs.LGcs.AIcs.PL

TL;DR

Neural code models often handle expressions and lines better than entire method bodies, where long-range semantic relationships are difficult to learn from syntax. This paper uses static analysis to provide semantic facts that condition a neural program generator. On Java method-body generation, its implementation outperforms larger state-of-the-art transformers in semantic properties and fidelity.

  • Problem

    Neural code models commonly struggle with long-horizon generation, and learning semantic relationships from syntax alone is difficult for complex, general-purpose languages.

    Source: §1 · p. 1

  • Method

    The model uses a static analyzer to compute semantic facts about generated code and conditions its generation actions on those facts.

    Source: §1 · p. 1

  • Results

    The implementation outperforms several larger state-of-the-art transformers in semantic properties and fidelity of generated method bodies.

    Source: §7 · p. 10

  • Takeaways & Limitations

    The work presents static analysis as a way to annotate programs at training and test time while leaving program search to a neural network.

    Source: §7 · p. 10

    BLEU is not invariant to variable renaming and does not account for program structure, limiting its suitability for measuring whole-method fidelity.

    Source: §5.2 · p. 8

Abstract

from arXiv · show

State-of-the-art neural models of source code tend to be evaluated on the generation of individual expressions and lines of code, and commonly fail on long-horizon tasks such as the generation of entire method bodies. We propose to address this deficiency using weak supervision from a static program analyzer. Our neurosymbolic method allows a deep generative model to symbolically compute, using calls to a static-analysis tool, long-distance semantic relationships in the code that it has already generated. During training, the model observes these relationships and learns to generate programs conditioned on them. We apply our approach to the problem of generating entire Java methods given the remainder of the class that contains the method. Our experiments show that the approach substantially outperforms state-of-the-art transformers and a model that explicitly tries to learn program semantics on this task, both in terms of producing programs free of basic semantic errors and in terms of syntactically matching the ground truth.

1 Introduction

Neural code models often struggle to generate long code blocks, where semantic relationships may be difficult to learn from syntax alone. The paper introduces neurosymbolic attribute grammars that use static analysis to condition generation, and evaluates them on Java method-body generation.

1 Introduction

  • Neural code models often excel at generating expressions or lines but struggle with long code blocks, where transformers can produce semantic errors and diverge syntactically from the ground truth.The paper identifies uninitialized variables and type-incorrect expressions as examples of semantic errors.Source: §1 · p. 1
  • The approach uses a static analyzer as a weak supervisor to compute semantic facts about generated code and condition the model’s next-generation actions on them.The facts capture semantic relationships between parts of a program that are far apart in the code.Source: §1 · p. 1
  • Neurosymbolic attribute grammars extend attribute grammars with attributes representing semantic relationships and a neural distribution over grammar rules conditioned on those attributes.During generation, the model samples rules while computing attributes of the generated code.Source: §1 · pp. 1–2
  • The NSG reliably outperforms the baselines, including larger state-of-the-art transformers, on semantic correctness and syntactic fidelity when generating Java method bodies.The comparison includes fine-tuned GPT-NEO and CODEGPT models, zero-shot CODEX, and a GNN-based method.Source: §1 · p. 2
  • The paper presents the approach as a new form of source-code generative modeling weakly supervised by static analysis.The authors argue that learning semantics from syntax is difficult for complex, general-purpose languages.Source: §1 · pp. 1–2

2 Conditional Program Generation

Conditional program generation predicts a program from a specification, such as information about the class surrounding a missing Java method. The paper frames this as a long-horizon task and illustrates how static-analysis attributes can help generate a type-safe completion.

2 Conditional Program Generation

  • For Java method generation, the specification can include class and method information, while valid outputs must satisfy language invariants before textual dissimilarity is assessed.The example specification includes method names, types, API calls, parameters, and JavaDoc; invariants include type safety and initialization before use.Source: §2 · pp. 2–3
  • Conditional program generation targets long token sequences from a possibly imprecise specification, rather than predicting the next token from a token sequence.The paper describes this as more challenging than next-token prediction.Source: §2 · p. 2
  • Generating a FileWriter call requires a FileWriter-typed result variable and a first argument of type File or a subtype, constraints the paper says are hard for state-of-the-art neural models to learn.The example illustrates why method-body generation requires tracking relationships between distant code elements.Source: §2 · p. 3
  • Static-analysis attributes include a symbol table mapping in-scope variables to types, which can help the model select a type-compatible variable for a FileWriter constructor.The training example links the type of f in the symbol table to its use as the constructor’s first argument.Source: §2 · p. 3
  • The illustrated NSG completion initializes variables before use, uses type-safe operations, and reuses a variable name across try and catch scopes.The symbol table carries scope information, and the paper notes that static-analysis information can also help match the ground truth syntactically.Source: §2 · p. 3

3 Static Analysis with Attribute Grammars

Attribute grammars extend context-free grammars by attaching attributes to grammar symbols and propagating values through syntax trees. Their equations can carry information between nodes, as illustrated by left-to-right propagation of symbol tables through sequential statements.

3 Static Analysis with Attribute Grammars

  • An attribute grammar extends a context-free grammar with attributes on terminals and nonterminals, propagated through syntax trees by attribute equations.Inherited attributes transfer information from parent to child or to the same node; synthesized attributes transfer information upward, to siblings, or to the same node.Source: §3 · p. 4
  • For a production, input attributes comprise inherited attributes of the parent and synthesized attributes of its children, while output attributes comprise synthesized attributes of the parent and inherited attributes of its children.The equations relate these inputs and outputs using attributes of the parent, children, and left sibling.Source: §3 · p. 4
  • A symbol-table example shows sequential composition passing information left to right: one statement’s synthesized symbol table becomes the next statement’s inherited input.The symbol table supports lookup of variables in scope.Source: §3 · p. 4

4 Neurosymbolic Attribute Grammars

Neurosymbolic Attribute Grammars (NSGs) condition program generation on semantic relationships computed by static analysis. They combine a latent-variable model with attribute-bearing grammar expansions to guide generation of Java methods.

4 Neurosymbolic Attribute Grammars

  • NSGs use static-analysis attributes to condition a neural distribution over grammar rules, exposing long-range semantic relationships during program generation.The model builds on a latent-variable approach in which Z represents intent behind an incomplete or ambiguous evidence set [26].Source: §4 · p. 4
  • The model defines P(Y|X) by combining a latent context Z inferred from evidence with a distribution over programs conditioned on Z.Evidence can include fixed types such as method names, formal parameters, and Javadoc comments; neural encoders map evidence instances to vectors.Source: §4 · p. 4
  • A leftmost stochastic grammar expands symbols using prior expansion choices and Z, with the fully expanded derivation yielding a program.For each symbol, a trial selects one of its possible right-hand-side sequences.Source: §4 · p. 5
  • Inherited attributes condition grammar choices, while synthesized attributes pass computed information upward; static analysis exposes semantic rules directly to the learner.Generation is guided by these attributes rather than relying on the model to learn their importance only from data.Source: §4 · pp. 5–6
  • The static analysis is designed to guide generation toward semantic properties, not to impose hard constraints on generated programs.The authors use validation constraints as a mental model for choosing attribute equations at important generation decisions.Source: §4 · p. 6
  • In the write-method example, symbol-table and type attributes help select a FileWriter declaration, a compatible constructor argument, and a subsequent write call.The symbol table records variables in scope and their types, including the newly declared FileWriter.Source: §4 · p. 6

5 Evaluation

The evaluation tests whether static-analysis attributes help neural models generate entire Java method bodies. NSG generally passed more static checks and achieved much higher fidelity accuracy than the baselines, though the approach operates on a subset of Java.

5 Evaluation

  • The evaluation hypothesis is that static analysis computes long-distance dependencies that syntax-only neural models struggle to learn, especially for whole method bodies.The authors propose that this added information can help NSG generate more accurate and semantically correct code.Source: §5 · p. 7

5.1 Experimental Setup

  • Training used 1.57 million Java method bodies, with NSG attributes tracking symbol-table state, types, variable initialization, and return behavior.The corpus was curated and deduplicated; the grammar included terminals for parameters, class variables, local methods, types, and method calls.Source: §5.1 · p. 7
  • Baselines included fine-tuned GPT-NEO and CODEGPT, zero-shot CODEX, a syntax-only conditional neural grammar, and GNN2NAG.Transformer baselines covered all Java, whereas NSG supported only the subset represented by its grammar.Source: §5.1 · p. 7
  • The test removes a method body and asks models to regenerate it from the remaining class and method header, assessing static checks and fidelity.Static checks include variable, type, return-statement, and parsing properties; formal-parameter and class-variable access checks are not meaningful for transformers.Source: §5.1 · p. 7, §5.2 · p. 8

5.2 Results

  • NSG passed various static checks more often in most cases and achieved much higher fidelity accuracy than the baselines.The results are summarized in the static-check and whole-method-fidelity tables.Source: Table 2 · p. 8, Table 1 · p. 8, §5.2 · p. 9
  • Fidelity is measured with API-call sets and sequences, program-path sets, and AST exact match rather than BLEU.For each metric, the highest score across ten generated bodies is averaged across test programs; BLEU is problematic because it ignores variable-renaming invariance and program structure.Source: §5.2 · pp. 8–9
  • Transformers produced human-like code on some hand-written tasks, but often generated incorrect programs or outputs that were too short.The authors report that the incorrect programs were ones a trained human programmer would be unlikely to write.Source: §5.2 · p. 9
  • In a file-reading example, NSG reused an existing field and caught IOException, while transformer outputs included unrelated or type-incorrect code.GPT-NEO also accessed a nonexistent field and returned a blank line.Source: §5.2 · p. 9, Table 3 · p. 9

6 Related Work

Related work spans symbolic context-sensitive generators, neural models trained on program syntax, and neurally directed synthesis. NSG differs by using static-analysis-derived facts as weak supervision for a neural generator rather than learning attributes or enforcing hard constraints.

Non-Neural Models of Code

  • Earlier symbolic generators used programmatically represented functions or traversal variables to encode production context, but lacked neural representations.The cited approaches include Bielik et al. and Maddison & Tarlow [25].Source: §6 · pp. 9–10

Deep Models of Code

  • Deep code models generate from program syntax without explicit knowledge of program semantics, including sequence, tree, and transformer approaches.Examples include CODEGPT [24], CODEBERT [14], GPT-NEO, and CODEX [8].Source: §6 · p. 10
  • GNN2NAG uses an attribute grammar but learns code attributes with a graph neural network rather than computing them symbolically.The paper reports experimental benefits for its weak-supervision approach over GNN2NAG [7].Source: §6 · p. 10

Non-Neural Models of Code

  • Unlike hard-constraint attribute grammars, NSG uses attribute grammars for weak supervision rather than requiring generated programs to satisfy propagated constraints.The related hard-constraint approach can face unsatisfiability and reject generated samples as grammar complexity increases [31].Source: §6 · p. 10

Neurally Directed Program Synthesis

  • Neurally directed synthesis typically searches constrained DSLs, while NSG uses a neural generator conditioned on analysis facts without complete program search at generation time.The paper presents this design as more scalable and able to handle generation in a general-purpose language.Source: §6 · p. 10

7 Conclusion

The conclusion presents static-analysis supervision as a framework that improves generated method bodies over larger state-of-the-art transformers, and proposes using program semantics to annotate programs rather than direct combinatorial search.

7 Conclusion

  • The implemented framework uses an attribute grammar as a weak supervisor and outperforms larger state-of-the-art transformers in semantic properties and method-body fidelity.The conclusion reports both semantic properties and fidelity as areas of improvement.Source: §7 · p. 10
  • Static analysis can extract code semantics to aid neural models, and the authors suggest implementing this approach on top of a modern transformer.The paper uses a tree LSTM but says a transformer implementation is also possible.Source: §7 · p. 10
  • Rather than directing a combinatorial program search, formal semantics can annotate programs at training and test time while a neural network performs the search.The conclusion presents this as an alternative to semantic-guided search, whose scalability has been challenging.Source: §7 · p. 10

A Additional Synthesis Examples

B Static Checks Considered

  • Variable-access checks cover undeclared variables and whether input variables and class fields are available in the class definition.The symbol table tracks variables in scope and their types.Source: B Static Checks Considered · pp. 14, 17
  • Static checks assess whether API arguments and invoked objects have compatible types, and whether API return types match types expected at their call sites.The checks use symbol-table and type attributes to inform argument and object generation.Source: B Static Checks Considered · p. 17
  • Other checks assess return-type consistency, the presence of a return statement, Java parsing, and aggregate pass rates.Parsing checks syntax only; rule-based generation models parse by definition.Source: B Static Checks Considered · pp. 17–18
  • The checks also measure whether declared variables are used and reference-type variables are initialized.The attribute grammar tracks use and initialization state during generation.Source: B Static Checks Considered · pp. 17–18

C Implementation Details

The implementation encodes class and method context separately from generated-code attributes, then conditions neural decoding on relevant attributes as the AST is built.

C Implementation Details

  • The evidence encoder represents seven kinds of context, including class-level information, method-header components, and available Javadoc.Names are encoded as sets, while type information and Javadoc use sequential encodings; the surrounding method uses its header components.Source: C Implementation Details · p. 18
  • Separate LSTM decoding units choose among grammar-rule right-hand sides for program blocks, types, initializations, API calls, variable accesses, and internal-method calls.The units have separate parameters but share recurrent state tracking the unfinished program.Source: C Implementation Details · p. 19
  • Neural units receive grammar attributes such as the symbol table, expected return and argument types, variable-use and initialization flags, and return-statement status.Attributes are supplied only when relevant to a production rule.Source: C Implementation Details · p. 19
  • Training supplies contextual information and AST attributes to the decoder, which learns symbol-category distributions using a sum of cross-entropy losses.The grammar attributes provide additional decoder inputs beyond those of a simple neural model.Source: C Implementation Details · p. 19
  • At inference, required attributes are inferred on the fly from the partial AST, and beam search is adapted to traverse the AST depth-first.The L-attributed grammar makes the needed inputs available without information from the yet-unsynthesized AST.Source: C Implementation Details · pp. 19–20

D Implementation of Baselines

The baseline implementations use a graph-neural model and fine-tuned pretrained language models, with different input contexts and decoding setups.

D Implementation of Baselines

  • GNN2NAG represents AST nodes with six edge types, propagates information using a gated graph neural network, then applies an LSTM to predict the next token.The LSTM iterates over edges because edge-type information for token generation is unavailable in this setup.Source: D Implementation of Baselines · p. 20
  • The transformer baselines include GPTNeo 125M, GPTNeo 1.3B, CODEGPT, and CODEX; all but CODEX are fine-tuned on the Java dataset.At evaluation, transformers receive the header and the rest of the class, including method bodies; the NSG receives headers.Source: D Implementation of Baselines · p. 20
  • Transformer fine-tuning uses CodeXGLUE token-level completion on 600,000 training instances, with learning rate 8e−5 and batch size 1 per GPU.Training used 16 GPUs and took about four days for two epochs.Source: D Implementation of Baselines · p. 20

E Generation of Training Data

Training examples are generated by compiling corpus methods and recording AST choices with their attributes; separate experiments restrict which surrounding-class evidence is available.

E Generation of Training Data

  • For each corpus method, an attribute-grammar compiler creates a parse tree, evaluates attributes in a left-to-right pass, and emits an example for each subtree node.The task models procedure bodies from the start nonterminal Prog, conditioned on context X.Source: E Generation of Training Data · p. 20
  • Each training input pairs the prior pre-order nonterminal and production choices with the current node's attributes to predict its right-hand-side production.The input-output pairs are formed from the method's Prog subtree.Source: E Generation of Training Data · p. 20

F Restricting Available Evidence

  • Evidence restriction randomly makes each surrounding-class evidence item available with probability x%, modeling generation when the class is less complete.The unrestricted setup simulates generating the last method after the rest of the class is visible.Source: F Restricting Available Evidence · p. 21
  • Tables 7 and 8 report static checks and average fidelity with 25% evidence, while Tables 9 and 10 report results with 50% evidence.The tables repeat experiments conducted earlier in the paper under reduced evidence availability.Source: F Restricting Available Evidence · p. 21, Table 7 · p. 21, Table 8 · p. 21

G Next-Token Prediction

Baselines outperform the NSG on next-token prediction, while the paper reports that the NSG remains semantically accurate on the longer task of generating entire Java method bodies. An attribute ablation reduces return-statement accuracy, but the model retains a large advantage over the no-attribute CNG model on return-statement type accuracy.

G Next-Token Prediction

  • Next-token evaluation scores whether the predicted right-hand-side symbol matches the observed symbol, with terminal-symbol correctness recorded for each test program.The NSG is evaluated using the actual left context, its attributes, and the latent variable Z.Source: G Next-Token Prediction · p. 21
  • The NSG is less accurate than CODEGPT and GNN2NAG on next-token prediction, yet remains capable of generating semantically accurate Java methods on the long-horizon CPG task.The authors contrast these next-token results with earlier CPG results.Source: G Next-Token Prediction · pp. 21–22

H Application to Novel Semantic Checks

  • With 50% of the evidence, omitting return-statement attributes lowers Return Stmt Type accuracy from 92.15% to 77.45% and Return Stmt Exists accuracy from 97.47% to 95.68%.The resulting Return Stmt Type accuracy remains above the vanilla CNG model’s 9.51%.Source: H Application to Novel Semantic Checks · p. 22
  • The authors suggest the model learns type-safe generation from other properties, especially symTab, which records types of objects in scope.They propose that a small core of key attributes may substantially improve code-generation accuracy.Source: H Application to Novel Semantic Checks · p. 22

I Robustness Incomplete Analysis

The robustness analysis simulates three kinds of static-analyzer resolution failures and finds that their effects vary by attribute. Errors resolving return-type information can sharply reduce relevant semantic-check accuracy, while failure to resolve the unused-variable attribute has a narrower reported impact.

I Robustness Incomplete Analysis

  • When the analyzer cannot resolve the missing method’s return type, Return Stmt Type accuracy falls from 90.97% to 77.28%, without an apparent effect on other static checks.The scenario passes a default null value for methodRetType.Source: I Robustness Incomplete Analysis · pp. 22–23
  • Failure to resolve API return-type attribute retType drops Return type at call site accuracy from 98.01% to 18.16%, alongside declines in two other checks and AST exact match from 26% to 10%.The authors attribute broader degradation to retType being used in many parts of the attribute grammar.Source: I Robustness Incomplete Analysis · p. 23
  • Failure to resolve attrOut.isUsed lowers No unused variables accuracy from 93.84% to 91.10%; all other metrics change negligibly.Source: I Robustness Incomplete Analysis · p. 23
  • The results indicate that NSG depends heavily on the analyzer, and that some attributes affect performance more than others.The authors say accurate analyzer results are critical at inference time to avoid performance degradation.Source: I Robustness Incomplete Analysis · p. 23

J BLEU-Score Analysis

The BLEU example illustrates that surface lexical matches can disagree with the authors’ judgment of output quality. The appendix describes the grammar productions and semantic attributes used by the NSG.

J BLEU-Score Analysis

  • CodeGPT’s BLEU score is 25.11 versus NSG’s 19.07, although the authors judge the NSG output better; superficial variable-name matches can inflate BLEU.They use alternative program-equivalence metrics because this mismatch occurred often in their experiments.Source: J BLEU-Score Analysis · p. 23

K.1 Context Free Grammar

  • The NSG uses a context-free grammar whose production groups expand statements, control flow, and terminal symbols in Java method bodies.The appendix groups productions into statement-level expansions, corresponding expansions, control-flow operations, and terminal-symbol generation.Source: K Grammar · p. 24, §K.1 · p. 24

K.2 Attribute Grammar

  • The attribute grammar tracks symTab and methodRetType through the AST, while attrIn and attrOut carry isInitialized, isUsed, retStmtGenerated, and itrVec.The appendix shows attribute propagation and validity checks across grammar productions.Source: K Grammar · p. 24, §K.2 · pp. 25–26

K Grammar

  • The appendix presents the production rules alongside the attributes used to train the NSG for synthesizing real-life Java programs.Source: K Grammar · p. 24
Loading 2111.01633v2…