Neural Program Generation Modulo Static Analysis
Authors: Rohan Mukherjee
Yeming Wen
Dipak Chaudhari
Thomas Reps
Swarat Chaudhuri
Chris Jermaine
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Program generation
neurosymbolic learning
attribute grammars
program synthesis

Abstract: 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 a state-of-the-art transformer 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. 

Neural Program Generation Modulo Static Analysis
Rohan Mukherjee Rice University
Yeming Wen UT Austin
Dipak Chaudhari UT Austin
Thomas W. Reps University of Wisconsin
Swarat Chaudhuri
Chris Jermaine
UT Austin
Rice University
Abstract
State-of-the-aae neural models of source code tend to be evaluated on the generation of individual expressions and lines of code, and commonly fail long- horizon tasks such as the generation of entire method bodies. We propose to address this deficiency using weak supervision from static program analyzer. Our neurosym- bolic method allows a deep generative model to symbolically compute, using calls static-analysis tool, long-distance semantic relationships in the code that it has already generated. During training, the model observes these relationships and learns generate programs conditioned on them. We apply our approach 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 of-the-art transformers and 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.
Introduction
Neural models source code have received much attention in the recent past [38, 9, 26, 23, 30, 36, 16, 24]. However, these models have basic weakness: while they frequently excel generating individual expressions or lines of code, they do not do so well when tasked with synthesizing larger code blocks. For example, can generate code with elementary semantic errors, such as uninitialized variables and type-incorrect expressions, when asked to generate method bodies, opposed to single lines. Even in terms of syntactic accuracy measures, the quality of the code that transformers produce on such "long-horizon" tasks can far removed from the ground truth.
show later in this paper, state-of-the-ard transformer models [8, 6, 24]
The root cause of these issues, we believe, is that current neural models code treat programs as text rather than artifacts that constructed following semantics. In principle, model could learn semantics from syntax given enough data. In practice, such learning is difficult for complex, ceneral-purpose languages.
In this paper, we propose to address this challenge through an alternative neurosymbolic approach. static program analysis extract
Our main observation is that symbolic methods-speciffen deep semantic relationships between far-redoved parts of a program. However, these relationships not apparent at the level of syntax, and it is difficult for even large neural networks to learn them automatically. Driven by this observation, we use a static-analysis tool as a weak supervisor for deep model of code. During generation, semantic facts about the code generated so far. The distribution over the model's next generation actions is conditioned on these facts.
model invokes this static analyzer to compute set of
We concretely develop our approach by extending the classic formalism of altribute grammars [20]. Attribute grammars are like context-free grammars but allow rules to carry symbolic alfributes of the
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

context in which a rule is fired. In our model, called Neurosymbolic Attribute Grammars (NsGs), the context is an incomplete program, and rules are fired to replace a nonterminal (a stand-in for unknown code) in this program. The attributes are semantic relationships (for example, symbol tables) computed using static analysis. The neural part of the model represents probability distribution over the rules of the grammar conditioned on the attributes. During generation, the model repeatedly samples from this distribution while simultaneously computing the attributes of the generated code.
We evaluate our approach in the task of generating the entire body of a Java method given the rest of the class in which the method occurs. We consider a large corpus of curated Java programs, over a large vocabulary of API methods and tyies. this corpus, we train an NsG whose attributes, among other things, track the state of the symbol table and the types of arguments and return values of invoked methods at various points of a program, and whose neural component is a basic tree LSTM. We compare this model against several recent models: fine-tuned versions of two GPT-NRO [6] transformers and the CODEGPT [24] transformer, OpenAl's CODEX system [8] (used in a zero-shot manner), and GNN-based method for program encoding [7]. Some of these models are multiple orders of magnitude larger than our NSG model. Our experiments show that the NsG model reliably outperforms all of the baselines on our task, both terms of producing programs free of semantic errors and in terms of matching the ground truth syntactically.
In summary, this paper makes three contributions:
We present new approach to the generative modeling of source code that uses a static-analysis tool as a weak supervisor.
We embody this approach the specific form of neurosymbolic altribute grammars (NsGs).
We evaluate the NsG approach on the long-horizon task of generating entire Java method bodies, and show that it significantly outperforms several larger, state-of-the-arr transformer models.
2 Conditional Program Generation
We start by stating our problem, known as conditional program generation (CPG) [26]. We imagine a joint dis- tribution D(X, Y), where X ranges over specifications of
(a)
public class Fileutil[ String ext) public int readiFile f...)
problems and Y ranges over pro- grams. The probability D(X = X, Y = Y) is high when is solution to X. Also, we consider a family of dis- tributions PY X), parameterized by 8, that we might want to learn. Learning to conditionally generate programs amounts finding parameters I that minimize the prediction error E(X,Y)) (X)(() Y)), where is suitable distance function between programs.
/s write lines to file */ public void writed File f, String str) [??1)
(b)
void write (rile 5, String str) try
Filekeiter var_0;
var_0 new Ti (e var warte (str); catch (RcchcTTTxeptiii var_31 vor_0. prw_..priinttttckrsee
Specifications and distances between programs can be de- fined in many ways. In our experiments, the goal is to generate Java method bodies. A specification is an evi- dence set that contains information-e.g. method names, types of variables and methods about the class in which the method lies. We define 5(Y,, Y2) to be large num- ber if Y1 or Y2 violates one of several language-Ieve invariants (c.g.. type-safety, initialization of variables be- fore use) that we require programs to satisfy. When both programs satisfy the invariants, 8(Y1, Y2) measures the textual dissimilarity between the two programs.
system.out out out. .uiittiii ASG )
return;
Figure 1: (a) An instance of conditional program generation. (b) A top comple- tion of the write method, generated using an Nsg. ARG stands for string literal.
Note that CPG is much more challenging task than the well-studied next-token-prediction task [24, 7]. The goal is to predict long sequences of tokens (e.g., an entire method body). Also, X is a (possibly imprecise) specification of the code to generate, not just sequence of tokens are trying to complete by, say, choosing the correct method to call for a variable.
Example. Fig. 1-(a) illustrates the kind of task that we target. Here, we are given a class with missing write method. The specification X includes: (i) the class name FileUtil; (ii) the

---

(a)
(b)
Stnt:
Stnt; Sont
Expr Method (ArgList)
Stut {
SymTab symTaa 4:
Syn/Tab symTabOut f:
DectType Var new NewType (ArgList)
(c)
(d)
Stnt Sonit Sont;
Stout symmabb Stmr50.symi
symtab
Stmu52.smm' SymTab__ = Stoff ssmm TabOut
Strt
Stmr80.sym'l syyTaaour = Smwr52. SourS2..ymTTabOom f)
Stat:
Expr Method (ArgList)
Sine
Stnt
[
SttttsymmaabOn 1 == Symt.sy +
DeelType new NewType (ArgTist)
Sinn
Sint
[ Declfype.synii 4
Sont.symiaak
Var symTaa 1. : Stmt Stmt.syuTab
Stnr.symTabbO
Stun.sym'Tab
nVar.name 1 , DeclType sype 1)
ArgLisr.types sypeList 4 = -yeniyypt.ppeiiss
Erpe Fego/Hetborrttrppcc
Gerileee Wark Nearye (Aegind)
sym
Stmt cymtsyymTall Tab
NewType.deelTTpee + = yeeTType.type fi
Figure 2: (a) A basic context-free grammar. (b) Attributes of the Stmt nonterminal. (c) Attribute equations for the productions (the parts of the equations denoted by " "..." are elided). (d) An attributed tree, illustrating left-to-right threading of attributes.
type Strinn ng of the class variable err; (iii) information about complete methods within the class (including the methods' return types and formal-parameter parameter types and names, and sequences of API calls made within such methods); (iv) information about the method with missing code (rite), including its name, formal parameters, and JavaDoc comments for the method with missing code (e.g., "write lines to file"). Our objective on this input is to generate automatically a non-buggy, natural completion of write, without any provided, partial implementation of the method.
To understand the challenges in this task, consider completion that starts by: declaring local variable var_0;
0; and (ii) invoking the constructor for F FileWritez and storing the result in var 0. proper implementation of these two steps must ensure that var_ of type FileWriter Weweiierr... Also, the first argument to the constructor of Fi Welleriie tee must be of type Fi le e (or subtype of F File). As we show in Sec. is hard for state-of-the the- neural models learn to satisfy these rules.
In contrast, in our approach, the generator has access to a set of semantic attributes computed via static analysis. These attributes include symbol lable mapping in-scope variables their types.
Suppose that during training we are given new Fi Neewrieerr (f, true)". Our model's symbol table includes the names var_0 and and their types. The grammar is also able to compute the type of the first argument in the invoked constructor for Fiierriter. Consequently, the model can observe that the type of f is listed as File in the symbol table, and that is the first argument to the FileWriter constructor. With few observations like these, the model can learn that the first argument of "new FileWriter" tends to be of type Pile (or subtype). During generation, the model uses this knowledge, locating variable of the correct type in the symbol table each time it constructs FileWriter
following line of code: "var_o
Fig. 1-(b) shows top completion of wri te generated by our NsG implementation. Note that variables in this code are initialized before use, and that all operations are type-safe. Also, the name var_0 is reused between the try and the catch blocks. Such reuse possible because the symbol table carries information about the scopes which different names belong. Finally, will see in Sec. 5, the extra information provided by the static analyzer can also help with accuracy terms of syntactic matches with the ground truth.
Static Analysis with Attribute Grammars
As mentioned in Sec. 1, we develop our approach an extension of the classic attribute grammar (AG) framework [20]. Now we give some background on statie analysis using AGs. the next section, we show how to use AGs to weakly supervise neural program generator.

---

An AG extends traditional context-free grammar (CFG) [18] by attaching set of attributes to each terminal or nonterminal symbol of the grammar and by using a set of attribute equations to propagate attribute values through syntax trees. The attributes of symbol S can be divided into inherited attributes and synthesized attributes, which we suffix by and 1. respectively. Inherited attributes transfer information from parent to child, or from node to itself. Synthesized attributes transfer information from child to parent, from a node to a sibling, or from a node to itself. We assume that the terminal symbols of the grammar have synthesized attributes and that the root symbol of the grammar has a special set of inherited attributes, known as the initial attributes.
The output attributes of a production S + Si...., Sy consist of the synthesized-attrin of the nonterminal S, plus the inherite--attribut occurrences of all of the S.'s. The input attributes are the inherited-attribun The grammar's attribute equations relate the input and output attributes of a node in terms of the attributes of its parent, children, and left sibling in the syntax tree that the grammar generates.
occurrences
occurrences of S. plus the muathesized-attribung occurrences of the S; s.
Example. Consider the simple CFG in Fig. 2-(a). The nonterminal Stmt stands for program statements. The grammar says that statement can either be a sequential composition of statements, method call, or a variable declaration. A natural AG extension of this CFG tracks symbol tables, which allow easy lookup of all variables in scope.
Specifically, the grammar associates two symbol-table-valuu attributes, symTab &. and sym SymTabOut f. with Simt (Fig. 2-(b)). The attributes are propagated following the equations in Fig. 2-(c). In these equations, we distinguish between the three different occurrences of nonterminal "Stmi" via the symbols "SmmrSO," " "StmrS1," and "Smur22." where the numbers denote the lefumost occurrence, the next-to-leftmost occurrence, etc. In this case, the leftmost occurrence is the left-hand-side occurrence.
For concreteness, let consider the attribute equations for the production for sequential composition in the grammar. Here, the inherited attribute of StmrSO gets passed "down" the syntax tree as an inherited attribute of Stmr$1. The synthesized attribute received at Stmr81 is passed to Stm182 as an inherited attribute. More generally, the attribute equations define a left-to-right information flow through the syntax tree, as illustrated in Fig. 2-(d).
4 Neurosymbolic Attribute Grammars
Now we introduce the model of neurosymbolic attribute grammars (NsGs). Our goal is to learn a distribution P(Y]X), where Y is random variable whose domain is all possible programs (concretely, Java method bodies) and X is a specification a mnogram--eneratinn set made up of useful information extracted symbolically from the method's context and then encoded using a neural network). Attributes containing the results of a symbolic, static analysis are available to the neural network implementing this distribution. This weak supervision allows the network to mimic more accurately the long-range dependencies present in real code-bases.
problem (concretely, an evidence
The Underlying Model. The idea of weak supervision using a static analyzer could be developed on top of many different kinds of models. Here, develop the idea on top of model from Murali et al. [26]. This model uses a latent variable Z to represent the true user intent behind the incomplete or ambiguous evidence set Y. We then have P(Y[X) = fz PY))x)P(Y|Z)ddz To define the distribution P(Z(X), assume that the evidence set has data of a fixed number of types c.g., method names, formal parameters, and Javadoc comments.
The jth type of evidence has neural encoder fj- An individual piece of evidence X is either encoded as a single vector or as a set of vectors with no particular ordering. For example, our implementation encodes Javadoc comments vectors using LSTMs, and each member of a set of formal parameters using a basic feedforward network. Let X₁,x refer to the ktth instance of the j"h kind of evidence in X.
Assume a Normal prior on Z, and let (X( = I[ (X,)) Z, Io3)- Assume that the encoding
j.k
of each type of evidence is sampled from Normal centered at Z. If ʃ is 1-1 and onto, we have [26]:
Σoz 2 (7(X,,N)
P(Z[X)= NN
Z
J.
1
Σ 1xylo
21 1+ 1+Σ E1x1,00

---

Next, we define the distribution P()|Z). Con- sider a stochastic CFG which assumes (1) that a leftmost derivation is carried out, and (2) the probability distribution governing the expan- sion of symbol in the grammar takes into account the sequence of all expansions so far, as well input value Z upon which all expansions are conditioned.
Algorithm 1: Gen(S, A(S) SyySooar,, Z)
Input: current symbol S, inherited attributes A(S) sequence of symbols so far
SymSoFar, latent encoding Z
Modifies: all symbols expanded are appended to SymSoFar
Returns: A(S) the synthesized attes of S
This CFG consists of productions of the form S seqı sequ | seqs... sequ- Each sym- bol such as S corresponds to categorical random variable with sample space ((S) (seq, s001,,89.,..... ..., seg, J. A trial over the sym- bol S randomly selects one of the RHS se- quences for that symbol. If S is a terminal symbol, then (2) {e}. where e is special value that cannot be expanded. Subsequently, when a trial over S is performed and an RHS sequence from (2S5) is randomly selected, we will use the sans-serif 5th to denote the iden- tity of the RHS sequence observed.
if S is a terminal symbol then Append (S, e) to SymSoFar
return V
else
Choose a rightt right-hand-side (RHS) sequence Sth ~ PSS SymSoFar, A(S) Z)
Append (S, 5th to SymSoFar
SynthSoFar <
for S' E Shh in left-to-right order do Compute A(5") from A(S) and SynthSoFar
A(S")t <-
Gen(S", AA(S") SymSooar,, Z)
Now consider a depth-first, left-to-right al- gorithm for non-deterministicaly expanding rules in the grammar to generate a program end Compute A(S) from A(S) and SynthSoFar return A(S)T
Append A(S")t to SynthSoFar end
Y = (( (S2, S!!)),..>> (th, a symbol encountered during the expansion, and each tith is the identity of the RHS cho-
here each S;
sen for that symbol. Let S1 correspond to the symbol Start. We perform a trial over S1 and select one the RHS sequences from (2(S)). Let the identity of the RHS sequence selected be S Note that Sihs is itself sequence of symbols. Choose the first symbol in the sequence Sits, call this symbol S2. Perform a trial over S2, and let the identity of the RHS sequence chosen be Sits Choose the first symbol in tth (call it Sy) and expand it the same way. This recursive descent continues until a terminal symbol S; is encountered, and the recursion unwinds. If the recursion unwinds to symbol S2, for example, then we choose the second symbol in the sequence Sitt, which we call S We perform a trial over S and let the identity of the RHS sequence chosen be Sthe This sequence is recursively expanded. Once all of the symbols in the RHS associated with the Start symbol S1 have been fully expanded, we have a program.
This generative process defines probability distribution P(Y|Z), where for particular program Y, the probability of observing Y is computed as
PYYIZ)= = PSS, = Sth |S Stls S Sths Z).
(1)
We henceforth abbreviate the expression for the inner probability as P(S ST
Sthn 3-11 Z).
Weak Supervision with Attributes. Now assume that the grammar is an AG, so that each symbol has an attribute set A(S). We use A(S) denote the synthesized attributes of S, and A(S)L to denote the inherited attributes of S.
An NsG extends the model that the conditional distribution P(Y is defined as:
P(Y[Z) = II (S Sgi ..., S.. A(S.)..))
That is, when a symbol S; is non sonddterminnitically expanded, its value depends not just on the latent position and the sequence of expansions thus far, but also on the values of S,'s inherited attributes, ASS)).. In theory, a powerful enough learner with enough data could learn the importance of these sets of attribute values, without ever seeing them explicitly. In that sense, they could be treated as latent variables to be learned. However, the benefit of having a static analysis produce these values
5

---

deterministically is that the author of static analysis knows the semantic rules that must be followed by a program; by presenting the data used to check whether those rules are followed directly to a learner, the process of learning to generate programs is made much easier.
Generation of program under an NsG is descrihed in Algorithm 1, where the distribution governing the expansion of symbol S' has access to attribute values A(S)
Designing an appropriate static analysis. Intuitively, a program generated with the supervision of a static analyzer is likely to generate a semantically correct program because the static analysis provides key semantic clues during program generation. In conventional AG- AG-based analyzer, the AG would be used to maintain data structures that can be used to validate that in a complete program, key relationships hold among the values of the production's 's attributes. Our goal is to generate programs, rather than validate them; also, we want to guide the learner rather than impose hard constraints. However, constraints are a good mental model for designing good Nsg. That is, generally expect the attribute equations used at important decision points during a neural generation process to be also helpful for validating key semantic properties of complete programs.
Example. Now we show how to use the attribute grammar in Fig. 2 in generating the body of the write method from Sec. 2. Let us assume that the grammar has a start nonterminal Start (not shown in Fig. 2) that appears in a single rule expanding it to the statement nonterminal Stmt. We start by extracting the context X around the method, then use this information to sample Z from P(Z X). Next, a Java compiler processes the surrounding code and the method's 's formal parameters to form the attributes A(Start) which assume consist of a symbol table { ~ Fi le, str H String) }.
To generate a program, we sample from the distribution P(Start (), A(Star)) Z). First, Start is expanded to "Simt; Stmf"". When expanding the first Stmt, the NsG needs to choose between method invocation and a variable declaration. Because the NsG is "aware" that this step is to expand the first line of the method a variable. This choice gives us the RHS "DecIType Var = new NewType (ArgList)". Expanding DecIType, the NsG samples Java type from the distribution
list of RHS values chosen so far is empty-we would expect it to declare
P(DeclTypel(" ("Stm Stmf", "DeclType Var new NewType (ArgList)"), A(Dec/Type)),,) Z).
From the rules for expanding the nonterminal DecIType in Fig. 2, any Java type as the declared type of the variable. At this point, the NsG is aware that the goal is to create method called write (this is encoded in Z) and that it is choosing type be declared on the first line of the method. It also has access to the symbol table that is maintained as part of A(Declfype)4- Thus, the NsG may decide to expand the symbol DeclType to FileWriter. This type is then passed upward via the synthesized attribute DeclType.typp type1.
that the NsG can choose
Next, the grammar must expand the Var rule and pick variable name to declare. This choice is returned via the synthesized attribute nar.n Now is time to expand NewType. The attributes make this easy: when sampling from P(NewTypel).... the NsG has access to Nyw.yye.typel. which takes the value FileWriter. A synthesizer may err by choosing a type that is not compatible with Fi sileWriters However, we may expect that during training, every time that NewType was expanded and the declared type was Fi lewr ter, the type chosen was either F FileWriter or some subelass of F FileWriter: Hence the NsG is unlikely make an error.
Assume that the NsG chooses FileWriter. It must now expand ArgList. Again, the NsG has the advantage of having access to Argeiis.typeLLst, (an explicit representation of the types required by the constructor being called) and, most importantly, Arglist.symTabb (an explicit list of the variables in scope, as well as their types). At this point, it is easy for the NsG to match the required type of the first argument to the constructor (File) with an appropriate variable in the symbol table (f).
Now that the declaration of var_ has been fully expanded, the NsG updates the symbol table with binding for the newly-declared variable var_0, and the attribute Stmt.symTab takes the value {f + File, str + Str String, var__ + FileWritt werr). When the second occurrence of Stmr expanded, the symbol table is passed down via the inherited attribute Stmt .symmab 4. All of the information available- thhebeleeeeheeeee latent variable Z encoding the contextual information (including the name of the method "write" being generated), and the symbol table containing a i 1 leerriie ter and Stringg ni)innnlpppp the NSG to deduce correctly that this Siml symbol should be expanded into an invocation of wr tee method. Also, the presence of the symbol table makes it easy for the Nsg to correctly attach the write method call to the variable var_ and to use str r as the argument.

---

5
Evaluation
Our experimental hypothesis is that neural networks find difficult to learn the intricate rules that govern the generation of code by only looking at the syntax of example programs. These issues become especially visible when the units of code to be generated are large, for example, entire method bodies. In contrast, an NsG can use its static analysis to compute long-distane dependencies between program variables and statements "for free." Because of this extra power, NSGs can outperform much larger neural models at generating accurate and semantically correct code.
5.1 Experimental Setup
Data. To test our hypothesis, we used curated, deduplicated set of Java source-code files [26]. For each class and each method, we used the remainder of the class as evidence or context, and the method body was used to produce training or test data. We used 1.57 M method bodies for training. The grammar used had ten terminals corresponding to formal parameters, ten for class variables, and ten for methods local the class. None of the Java classes in the corpus needed more than ten of each of these terminals; when generating training data, each declared Java variable or method was randomly mapped to one of the appropriate terminals. Approximately 8,000 types and 27,000 method calls from the Java JDK also appeared as terminals in the grammar.
NsG Implementation. We implemented an NsG for our subset of Java. Here, attributes are used to keep track of the state of the symbol table, the expected return type of each method, expected types of actual parameters, variable initialization, whether the variable has been used, and whether the method has a return statement. The symbol table contains entries for all formal parameters, class variables, and internal methods within the class.
The neural part of our model has 63 M parameters. To expose the attributes to the neural part of the model, we implement depth-first search over program's 's abstract syntax tree (AST) to extract node information. The attributes are then encoded in a standard way- - for example, the symbol table is represented matrix (rows correspond to types, columns to variables, the value 1 is present if the corresponding type/variable pair is in scope). The distribution | 5 : S.. A(S.)4. Z) implemented as set of LSTMs that decode the sequence of symbols, well as the encoded A(S)), and Z, into a distribution over S We trained our framework on top of Tensorflow [1]. Using one GPU, the NsG training time is around 72 hours. See Appendix C for more details.'
Baselines We consider three categories of baselines. The first consists of large pretrained trans- formers. Specifically, we consider two variants of the GPT-NEO [6] model with 125 M and 1.3 B parameters. Both models are pre-trained on the Pile dataset [15], which consists of 800 GB English-text corpus and open-source code repositories. On the APPS dataset [17], they perform well compared to OpenAl's 12-B- B-B--arrmeter, GPT-3-like CODEX model [8]. We also compare against CODEGPT [24] which is a GPT-2-like model with 125 million parameters. This model was pre- trained on Python and Java corpora from the CodeSearchNet dataset, which consists of 1.1 M Python functions and 1.6 M Java methods. We fine-tune all of these pretrained models on our Java dataset, using the token-level code-completion task provided by CodeXGLUE [24]. Finally, comparison against the CODEX model [8]. Because we did not have access to the model's 's pretrained weights, this model is only used in a zero-shot fashion (no fine-tuning on our Java dataset). It should be noted here that the transformer baselines work on the entire Java language, whereas our Nsg framework works on sub-part of Java which is supported in our grammar definition.
also offer
The second category comprises an ablation, called a "conditional neural grammar" (CNG), that is identical to our NsG model but is trained without any of the attribute information. In other words, the CNG model is trained only on the program syntax. The third category includes GNN2NAG [7], a graph-neural-netwee based method that uses an attribute grammar but learns the attributes from data rather than computing them symbolically. See Appendix C for more details on the baselines.
Test Scenario. Our test scenario is as follows. Given Java class, we remove the entire body of randomly selected method. We then use the remaining potion of the class along with the method header as context information that is then fed to the model as input. We run our NsG model and the baselines to regenerate this method body conditioned on the resulting context. We report the accuracy of the prediction based on static-semantic checks and fidelity measures.
Our implementation is available https: http//ggttttttteeeeee
7

---

Table 1: Percent of Static Checks Passed
GPT 25M
GPTNeol 3B
CODEX
CODEGPT
GNNZNAG
CNG
NSG
undeclared variable access
89 89.87%
90.36%
88 62%
90.94%
47.44%
19.78%
99.82%
Valid formal parameter access
NA
NA
NA
NA
25.78%
11.03%
99.58 %
Valid class variable access
NA
NA
NA
NA
13.40%
12.75%
99.53% %
uninitaaized objects
93.90%
91.73%
90.82%
94.37%
21.20%
21.56%
99.01 %
No variable access emror
90.36%
90.51%
88.86%
91.32%
28.92%
17.92%
99.69%
Object-method compatibility
98.36 %
98.09%
98.35%
97. 87.84%
21.43%
12.23%
97.53%
Return type at call site
97.38%
98.01% S
98.53%
97.83%
23.8669
16.40%
98.01 '6:
Actual parameter type
87.03%
86.36%
92. 28%%
88.71%
9.27%
16.09%
97.96 %
Return statement type
84.05%
85.09%
133
85.23%
12.34%
9.51%
90.97% %
No type errors
87.25%
88.13%
91.42%
88.10%
16.31%
13.56%
97.08% %
Return statement exists
99.61% &
99.80%
94.4
99.57%
94.02%
99.92% %
27. 10%
No unused variables
96.42%
96.46%
96.825
97.64%
20.95%
24.29%
93.84%
Percentage of parsing
98.18%
93.138
96.41%
97.08%
100.095
100.0%
100.00%
Pass all checks
65.26%
64.88%
47.49%
67.73%
17.34%
12.87%
86.41% %
Table 2: Average Fidelity of Generated Method Bodies
G. GPINeo125M
CODEX
CODEGPT
GNN2NAG
CNG
Set of API APlCa
32%
37%
36%
36%
3%
22%
53%
Sequences of API Calls
17%
20%
16%
19%
0.3%
18%
42%
Sequenees of Program Paths
12%
15%
10%
14%
0%
17%
39 %
AST Exact Match
12%
13%
10%
14%
0%
6%
26%
5.2 Results
Static Checks. For each generated method body, check the following properties: (1) No unde- clared variable access: Are all the variables used in program declared (within an enclosing scope) before they are used? (2) Valid formal parameter access: Are formal parameters that are used in the method body present in the method declaration? (3) Valid class-variable access: Are the class vari- ables that are used in the method body present in the class declaration? (4) No uninitialized objects: Do variables have non-null value when they are used? (5) No variable access errors: Are checks (1)-(4) all satisfied? (6) Object-method compatibility: Are methods called on objects of a given class actually available within that class? (7) Return type at the call site: Is the assignment of the return value type-correct with respect to the return type of the called method? (8) tartual-rrratter type: Are the actual- -arrametr types in an API call consistent with the corresponding formal-pane parametee types? (9) Return-statemen type: Is the type of the expression in a return statement consistent with the method's ' declared return type? (10) No type errors: Are checks (6)-(10) all satisfied? (11) Return statement exists: Does the method body have a return statement somewhere? (12) No unused variables: Are all variables declared in the method body used in the method? (13) Percentage of parsing: Can the generated method be parsed by a standard Java parser? (14) Pass all checks: Are checks (1)-(13) all satisfied?
Note that (2) and (3) are not meaningful metries for approaches, such as our transformer baselines, that do not use grammar to generate code. This is because in these models, when variable token is generated, there is no way to tell what category of variable (class variable, formal parameter, etc.) meant to be. These metrics meaningful for the NsG, CNG, and GNN2NAG models, which use a Java parser capable of partitioning variable names into different categories.
The results of our comparisons appear in Table 1. These scores are interpreted as follows. Suppose that generated program uses five variables. of which four are declared correctly in the proper scope. This situation is scored as 80% correct on the "No undeclared-vante variaable access" criterion. We report the average success rate over each of these properties over all the generated programs in our test suite.
Whole-Method Fidelity. We also check the fidelity of the generated code to the reference code. One possibility here is to use standard metric for text generation, such as the BLEU score. However, this is problematic. As the BLEU score is not invariant to variable renamings, nonsensical program that uses commonplace variable names can get an artificially high BLEU score. Also, programs are structured objects in which some tokens indicate control flow and some indicate data flow. The BLEU score does not take this structure into account. See Appendix J for concrete example of these issues.
8

---

Instead, we consider four fidelity metries: (1) Set of API Calls: Extract the set of API calls from the generated and refer- ence codes, and compute the Jaccard sim- ilarity between the sets. (2) Sequences of API Calls: Generate the set of all pos- sible API call sequences possible along code paths, and compute the Jaceard sim- ilarity between the sets for the generated and reference code. (3) Sequences of Pro- gram Paths: Generate the set of all possi- ble paths from root to leaf in the AST, then compute the Jaccard similarity between the sets (two paths are equal if all elements except for object references match). (4) AST Exact Match: Exact AST match (ex- cept for object references), scored as or 1. We compute the highest value for each metric across the ten bodies gener- ated, and average the highest across all test programs. Results for these measures are presented in Table 2.
Query
public class FileUtils( FiLeReader rield_"; BufferedReades field_5;
read line from file x/ public String reader (1 (1)
NsG public String readert)
Lava.lang..Be String var_9; try [var_9-faeee S. (); catch (10xxception var_a)
var_ w.....priatttccee return var_9;
CodeGPT
public String () StringRuffer buf new Stringeuffer auffer.agoe:dd return buffer.
CODEX public String reader throws :0Exception!
field_s= new ButreredReader! new F:leReader (field_]))
return #ield_S.
G3
public String reader!) throws =0Exception
try
field_7-new PileReader (this.file)
field_S-new BufferedReader (field_7);
Summary of results. We find that in most cases, the NsG had a higher incidence of passing the various static checks compared to the baselines. This is perhaps not sur- prising, given that the NsG has access to the result of the static analysis via the at- tribute grammar. More intriguing is the much higher accuracy of the NsG for the fidelity results. Pre-trained language mod- els and GNN2NAG are designed for next-token- -rreeecctriiiiion tasks (we give some results on these tasks in Appendix G). However, in our CPG task, no tokens are available from the method body to be generated. In particular, language models must treat the surrounding code and method header as input from which to generate the entire method body, and this proves difficult. The NsG, on the other hand, uses static analysis to symbolically extract this context, which is explicitly given to the neural network in the form of the class variables and methods that are available to called (in A()) and in the class name, encoded comments, variable names, and
String Line;
while @tsald_5.readdiinn
Syatem,
line;
catch (silelctroomdaeceppiin e) le.print StacttteackTreeelll
return null;
Table 3: Reading from file: Outputs for the NsG and transformer baselines.
(in Z).
Transformers vs. NSGs: As complement to our quantitative evaluation, we manually examined the outputs of our model and the baselines on set of hand-written tasks for qualitative evaluation. The transformers produced impressively human-likk code on several of these tasks. However, in quite few cases, they produced incorrect programs that trained human programmer would be unlikely write. Also, the transformers were biased towards producing short programs, which often led them to produce uninteresting outputs.
Table 3 illustrates some of the failure modes of the transformer baselines. Here, consider the task of reading a string from a file utility class. The top result for our NsG model declares a String variable to read from the already existing field while also correctly catching an 10Exception. The CODEGPT output in this case is unrelated to the context. CODEX initiates FileReader object by invoking an argument which of type FileReader itself, thereby causing a type mismatch. The code from GPT-NEO accesses file instance variable that does not exist and also returns blank line from the method. A few other examples of NsG and transformer outputs appear in Appendix A.
Related Work
Non-Neural Models of Code, Many non-neural models of code have been proposed over the years [25, 32, 28, 2, 27, 5]. few of these models condition generation on symbolic information from the context. Specifically, Bielik et al. [5] use programmatically represented functions to gather

---

information about the context in which productions for program generation are fired, then utilize this information to impose a distribution on rules. Maddison & Tarlow [25] generate programs using a model that encodes a production's o context using set of "traversal variables." However, the absence of neural representations in these models puts a ceiling on their performance.
Deep Models of Code. There is, by now, a substantial literature on deep models trained on program syntax. Early work on this topic represented programs as sequences [32] or trees [26, 38, 9], and learned using classic neural models, such as RNNs, as well as specialized architectures [23, 30, 3]. The recent trend to use transformers [36, 16, 14, 24]. Some of these models - for example, CODEGPT [24] - are trained purely on code corpora (spanning variety of languages. including Java). Other models, such as CODEBERT [14], GPT-NEO [6], and CODEX [8], are trained on both natural language and code. In all of these cases, programs are generated without any explicit knowledge of program syntax or semanties.
The GNN2NAG model by Brockschmidt et al. [7] also uses an attribute grammar to direct the generation of programs. However, unlike our method, this model use a graph neural net to learn attributes of code. Our experiments show the benefits of our weak supervision approach over this.
Also related is work by Dai et al. [11]. who extend grammar variational autoencoders [21] with hard constraints represented as attribute grammars. In that work, attribute constraints are propagated top-down, and every generated artifact is required to satisfy the top-level constraint. This strategy comes with challenges; as is well-known in the program-synten propagation can lead to unsatisfiability, and require rejection of generated samples, for grammars above a certain level of complexity. We sidestep this issue by using attribute grammars as a form of weak supervision, rather than means to enforce hard constraints.
literature [31], top-down constraint
Neurally Directed Program Synthesis. Many recent papers study the problem of neurally directed program synthesis [4, 12, 34, 10, 33, 29]. Here, neural networks, and sometimes program analysis, used guide combinatorial search over programs. Because such search is expensive, these methods are typically limited to constrained domain-specific languages. In contrast, our approach does not aim for complete search over programs at generation time (our decoder does perform beam search, but the width of this beam is limited). Instead, we embody our program generator as a facts part of its data. This design choice makes language.
neural network that sees ioogram-analysis-deeee
our method more scalable and allows it to handle generation in a
7 Conclusion
We have presented a framework for deep generation of source code in which the training procedure is weakly supervised by static analyzer, in particular, an attribute grammar. We have shown that our implementation of this approach outperforms several larger, state-of-the-art transformers both in semantic properties and fidelity of generated method bodies.
A lesson of this work is that while modern transformers excel at writing superficially human-like -lkee code, they still lack the ability to learn the intricate semantics of general-purpose languages. At the same time, the semantics of code can be defined rigorously and partially extracted "for free" using program analysis. This extracted semantics they struggle with during program generation. While we have used this idea to extend a tree L.TM, could have implemented it on top of modern transformer as well. We hope that future work will pursue such implementations.
be used to aid neural models with the concepts that
Our work demonstrates an alternative use for formal language semantics, compared to how semantics are typically used in program synthesis research. Historically, semantics have been used to direct generation-tina combinatorial searches over programs. However, scalability has been challenge with such approaches. Our work points to an alternative use of semantics: rather than using semantic program analyses to direct search over programs, one could use them to annotate programs at training and test time and leave the search to a modern neural network. We believe that such a strategy has the potential to vastly extend the capabilities of algorithms for program synthesis.
Acknowledgments. This work was funded by NSF grants 1918651 and 2033851; US Air Force and DARPA contract FA8750-20-C-00N0 and ONR grants N00014-20-1-2115. We thank Matt Amodio for his help with our initial exploration of the problem studied here, and Martin Rinard and the anonymous referees for their valuable comments.
231, and
10

---

References
[1] Abadi, M., Agarwal, A., Barham, P., Brevdo, E., Chen, Z., Citro, C., Corrado, G. S., Davis, A., Dean, J., Devin, M., Ghemawat, S., Goodfellow, I., Harp, A., Irving, G., Isard, M., Jia, Y., Jozefowicz R., Kaiser, L., Kudlur, M., Levenberg. J., Mané, D., Monga, R., Moore, S., Murray, D., Olah, C., Schuster, M., Shlens. J., Steiner, B., Sutskever, I., Talwar, K., Tucker, P., Vanhoucke, V., Vasudevan, V., Viégas, F., Vinyals, O.. Warden, P., Wattenberg, M., Wicke, M., Yu, Y., and Zheng, X. TensorFlow: Large-scale machine learning heterogeneous systems, 2015. Software available from tensorflow.org.
[2] Allamanis, M. and Sutton, C. Mining idioms from source code. In Proceedings of the 22Nd ACM SIGSOFT International Symposium Foundations of Softwrre Engineering, FSE 2014, pp. 472-483, New York, NY, USA, 2014. ACM. ISBN 978- 178-1-4003-3056-5 doi: 10.1 (0.1145/633886 141126666888.66339111
[3] Alon, U., Zilberstein, M., Levy, O., and Yahav, E. code2vec: Learning distributed repre- sentations of code. Proceedings of the ACM on Programming Languages, 3(POPL):1-29, 2019.
[4] Balog, M., Gaunt, A. L., Brockschmidt, M., Nowozin, S., and Tarlow, D. Deepcoder: Learning to write programs. International Conference on Learning Representations (ICLR), 2017.
[5] Bielik, P., Raychev, V., and Vechev, M. PHOG: Probabilistic model for code. In ICML, pp- 19-24, 2016.
[6] Black, S., Gao, L., Wang, P., Leahy, C., and Biderman, S. GPT-Neo: Large Scale Autoregressive Language Modeling with Mesh- Tensorflow, March 2021.
[7] Brockschmidt, M., Allamanis, M., Gaunt, A. L., and Polozov, O. Generative code modeling with graphs. In International Conference Learning Representations, 2018.
[8] Chen, M., Tworek, J., Jun, H., Yuan, Q., Ponde, H., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021.
[9] Chen, X., Liu, C., and Song, D. Tree-to-tree neural networks for program translation. Advances in Neural Information Processing Systems, 31, 2018.
[10] Chen, Y., Wang, C., Bastani, O., Dillig, I., and Feng, Y. Program synthesis using deduction- guided reinforcement learning. In International Conference on Computer Aided Verification, pp. 587-610. Springer, 2020.
[11] Dai, H., Tian, Y., Dai, B., Skiena, S., and Song, I.. directed variational autoencoder for structured data. In International Conference Learning Representations, 2018.
[12] Devlin, J., Uesato, J., Bhupatiraju, S., Singh, R., Mohamed, A.-r., and Kohli, P. Robustfill: Neural program learning under noisy i/o. International conference on machine learning, pp- 990-998. PMLR, 2017.
[13] Devlin, J., Chang, M., Lee, K., and Toutanova, K. BERT: pre-training of deep bidirectional transformers for language understanding. In NAACL-HLL (1), 2019.
[14] Feng, Z., Guo, D., Tang, D., Duan, N., Feng, X., Gong, M., Shou, L.,, Qin, B., Liu, T., Jiang, D., et al. Codebert: A pre-trained model for programming and natural languages. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: Findings, pp. 1536-1547, 2020.
[15] Gao, I.,, Biderman, S. R., Black, S., Golding, L., Hoppe, T., Foster, C., Phang, J., He, H., Thite, A., Nabeshima, N., Presser, S., and Leahy, The pile: An 800gb dataset of diverse text for language modeling, ArXiv, abs/2101.00027 2021.
[16] Gemmell, C., Rossetto, F., and Dalton, J. Relevance transformer: Generating concise code snippets with relevance feedback. In Proceedings of the 43rd International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 2005-2008, 2020.

---

[17] Hendrycks, D., Basart, S., Kadavath, S., Mazeika, M., Arora, A., Guo, E., Burns, C., Puranik, S., He, H., Song, D., and Steinhardt, J. Measuring coding challenge competence with apps. NeurlPS, 2021.
[18] Hopcroft, J. E., Motwani, R., and Ullman, D. Introduction to automata theory, languages, and computation. Acm Sigact News, 32(():60-65 65, 2001.
[19] Javalang. Pure Python Java parser and tools, March 2020. hutps//pypp.org/prriccttvvaaaaa
[20] Knuth, D. Semantics of context-free languages. Mathematical Systems Theeory 2(2):127-145, June 1968.
[21] Kusner, M. J., Paige, B., and Gernández-Lobato.. J. M. Grammar variational autoencoder. In International Conference on Machine Learning, pp. 1945-1954 PMLR, 2017.
[22] Li, Y., Tarlow, D., Brockschmidt, M., and Zemel, Gated graph sequence neural networks. CoRR, abs/151 hts//511.054922 1.05493, 2016.
[23] Ling, W., Blunsom, P., Grefenstette, E., Hermann, K. M. Kočiský, T., Wang, E,, and Senior, A. Latent predictor networks for code generation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, (Volume 1). pp. 599-609, 2016.
[24] Lu, S., Guo, D., Ren, S., Huang, J., Svyatkovskiy, A., Blanco, A., Clement, C., Drain, D., Jiang, D., Tang, D., et al. Codexglue: A machine learning benchmark dataset for code understanding and generation. arXiv preprint
N..:21022.46644 2021.
[25] Maddison, C. and Tarlow, D. Structured generative models of natural source code. In JCML, pp- 11-649-11-657, 2014.
[26] Murali, V., Qi, L., Chaudhuri, S., and Jermaine, C. Neural sketch learning for conditional program generation. In ICLR, 2018
[27] Nguyen, A. T. and Nguyen, T. N. Graph-based statistical language model for code. In Proceedings of the 37th International Conference on Software Engineering Volume ICSE '15, pp. 358-868, Piscataway, NJ, USA, 2015. IEEE Press. ISBN 978 17781-4799-1934-5
[28] Nguyen, T. T., Nguyen, A. T., Nguyen, H. A., and Nguyen, T. N. A statistical semantic language model for source code. Proceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2013, pp. 532-542, New York, NY, USA, 2013. ACM. ISBN 978-1-4503-2237-99 doi: 10. (45/2491411.24999
(29] Odena, A. and Sutton, C. Learning to represent programs with property signatures. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, OpenReview.net, 2020.
[30] Parisotto, E., Mohamed, A.r Singh, R., Li, L., Zhou, D., and Kohli, P. Neuro-symbolic program synthesis. In ICLR, 2017.
[31] Polikarpova, N., Kuraj, I., and Solar-Lezama, A. Program synthesis from polymorphie refine- ment types. ACM SIGPLAN Notices, 51(6):522-538, 2016.
[32] Raychev, V., Vechev, M., and Yahav, E. Code completion with statistical language models. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 419 428, 2014.
[33] Shah, A., Zhan, E., Sun, J. J., Verma, A., Yue, Y., and Chaudhuri, Learning diffecrntiablee programs with admissible neural heuristics. In Advances in Neural Information Processing Systems, 2020.
[34] Si, X., Yang, Y., Dai, H., Naik, M., and Song. L. Learning a meta-solver for syntax-guided program synthesis. In International Conference on Learning Representations, 2019.
[35] Sutskever, I., Vinyals, O., and Le, Q. Sequence to sequence learning with neural networks.
In Advances in neural information processing systems, pp. 3104-3112, 2014.
12

---

[36] Svyatkovskiy, A., Deng, S. K., Fu, S., and Sundaresan, N. Intellicode compose: Code generation using transformer. In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering, Pp. 1433, 2020.
[37] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L.,, Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention is all you need. In Advances in neural information processing systems, pp.
2017.
[38] Yin, P. and Neubig, G. A syntactic neural model for general-purpose code generation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, ACL 2017, Vancouver, Canada, July 30 August 4, Volume 1: Long Papers, pp. 440-450, 2017.
13


Reviews:
[{"review_id": "kb_la7dzdSF", "reviewer": "Reviewer_spNu", "summary": "Leveraging compiler inferences about code, such as from static analyzers, can improve the ability of neural models to reason about code. This paper introduces a method that relies on attribute grammar coupled with static analysis that operates on partial programs, demonstrating that access to this information greatly improves the quality of generated programs.", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "*Note: I appreciate the authors' response; they did not impact my score because I already strongly support acceptance.*\n\nThis is a strong paper. It is well-written and easy to follow while introducing a method that bridges several ideas and performs well. The resulting modeling delta compared to previous models is simple enough that it ought to be more broadly useful, although, as the authors point out as well, the need to implement static analyzers is a bit of a hurdle. Given that, my review mostly concerns minor issues and notes.\n\nIn terms of evaluation, while the baselines seem adequate, it is a slightly questionable choice to apply CodeGPT in this way -- presenting entire files while removing the method's body. Besides being somewhat removed from its pretraining objective (which the finetuning presumably helped overcome), transformers typically don't scale well to larger inputs. Indeed, the appendix suggests that this model was trained with a sequence length of up to 512 tokens, which tends to be (far) less than the size of typical files. Please clarify how this impacted the model.\n\nPresentation:\n- L147: consider splitting out the definition of mu and sigma from this equation, to make it more readable.\n- The citation style used in the paper appears to be incorrect for NeurIPS; it uses the numerical references rather than surname-of-first-author.\n- Table 1: consider adding a \"totals\" row, to make it easier to assess the overall performance of these models. Also consider better emphasizing the \"intermediate\" totals (row 5 & 10).\n\nTypos:\n- L47: \"and whose with grammar\"\n- L390: missing semicolon or \"and\" after \"beam search\"\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addresses both.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.5"}, "extra_text": {}}, {"review_id": "jBMJ7Bl-cUO", "reviewer": "Reviewer_HvAo", "summary": "The system generates long code snippets such as method bodies given their surrounding context. In contrast to modern\ncode generation models that are supervised by program syntax, it additionally conditions generation on semantic\nattributes that are computed on AST nodes by the compiler. The paper shows that this approach generate significantly\nmore idiomatic code with fewer language errors than syntax-only Transformers or purely-neural neural attribute models.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrengths:\n\n+ A principled formalism and implementation that incorporates semantic information computed by the compiler into neural\n  code generation models. Prior work usually either ignores it (syntactic codegen, either for sequences or for ASTs),\n  hard-filters by it at inference time, or incorporates specific instances, like data flow in GNN-based models. Adopting\n  it into the well-known formalism of attribute grammars is appreciated.\n+ Clear motivating examples and well-explained decision rationale\n+ Fair comparison to two most relevant baselines, one syntax-only and one attribute-inspired but not explicitly\n  supervised with symbolic attributes.\n+ Evaluation along multiple important dimensions: method generation accuracy, small expression generation accuracy (as\n  in prior work), and individual language rules.\n+ An explicit discussion of limitations is welcome, not discussed often enough in our community.\n\nWeaknesses:\n\n- The paper spends significant space on the NSG formalism and on the particular generative model re-used from Murali et\n  al., which forces it to defer its instantiation for Java, choice of attributes, and their encoding to the Appendix.\n  As a result, Section 4 ends abruptly, confusing the reader. The \"design\" paragraph helps set up the scene but, I\n  imagine, would not actually be informative to someone without formal methods background, at least without a single\n  concrete example.\n- Similarly, lack of space likely forced the authors to leave out Appendix H. It provides a valuable complementary\n  perspective on the respective strengths and weaknesses of training approaches, and a quick summary of it would be\n  welcome in the paper.\n- Characterizing [7] as \"next token prediction\" is unfair, as that model generates whole ASTs and – just like this\n  work – supervised with its production rule decisions at every step. The difference is in (a) size of the target AST,\n  (b) the amount of available in-method context for conditioning and for copy.\n- Phrasing aside, it would be interesting to see how [7] fairs against NSG for _in-method_ expression completion (medium\n  horizon). I imagine NSG would still outperform, as it leverages more explicit conditioning on attributes rather than\n  their neural abstractions.\n\nQuestions & Remarks:\n\n- The general line of reasoning that \"semantics are hard to learn from syntax\" is not wrong, but:\n  - It largely depends on the size of the model and its pretraining data, with improvement following a power law.\n  - It further improves with multi-language training as the model pick ups non-formalizable yet similarly expressed\n    cross-language cues.  \n  \n  Both were shown empirically by [Codex](https://arxiv.org/abs/2107.03374), concurrently with this submission. This does\n  not diminish the paper's contribution, just shows that the two directions keep improving and could further benefit\n  each other.\n\n- A better Transformer baseline would be [GPT-NEO](https://github.com/EleutherAI/gpt-neo) or\n  [GPT-J](https://github.com/kingoflolz/mesh-transformer-jax/#gpt-j-6b). Both are pretrained on The Pile corpus, which\n  includes a big portion of Github and more natural language. The former was shown to be a strong baseline for code\n  generation against Codex and in the [APPS paper](https://arxiv.org/abs/2105.09938), with or without finetuning.\n\n- L404-405: There are many methods to integrate tree structure and generative Transformers. See e.g.:\n  - Scholak et al. \"DuoRAT: Towards Simpler Text-to-SQL Models\", NAACL 2021.\n  - Sun et al. \"TreeGen: A Tree-Based Transformer Architecture for Code Generation\", AAAI 2020.\n\n- How much of attribute vocabulary could be shared cross-language? Most popular imperative languages could implement a\n  compiler frontend that computes a version of the attributes in Appendix D. Could this help us effectively train\n  cross-language and cross the gap to language model training?\n\n- Is the NSG model robust to presence or absence of attributes? For example, suppose the code/linker is in a broken\n  state so that type-based attributes cannot be properly resolved. Does the model break down completely or can it still\n  rely on other features?\n\n- Follow-up to previous question: In addition to conditioning on attributes, the model could be trained to predict them\n  as an auxiliary task. Multitask learning has improved performance or accelerated training in many domains, code could\n  work just as well.\n\nTypo:\n- L47: \"whose with grammar\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations are explicitly and nicely discussed in the Conclusion.\n\nOn societal impact, the authors state \"We have proposed an approach to better generation of source code and used open-source programs as training data. We do not anticipate any direct negative societal impact of this work.\"  \nAs a counter-point, I recommend reading the thorough and elaborate discussion of possible impacts of such models in the very recent \"Evaluating Large Language Models Trained on Code\" (Chen et al., 2021).", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "WRH9n4VZxC", "reviewer": "Reviewer_bycS", "summary": "The paper proposes a novel approach to conditional program generation that leverages supervision from a static analysis tool during generation. This serves to address a common difficulty in program synthesis using language models, that of generating code without semantic errors. The program generation and static analysis both follow the linear information flow through a program defined by an attribute grammar, with the program generation model having access to the attributes from the analysis. The paper applies this technique to a dataset of 1 million Java programs, comparing primarily with baselines CodeGPT and GNN2NAG. Evaluating both on static checks, overall fidelity metrics, and exact match, the paper finds the proposed NSG method outperforms the baselines considered on nearly all metrics.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers the challenging and important task of conditional program generation, an area of increasing interest at NeurIPS in recent years. The main weakness identified, that neural models of source code usually struggle with generation of long sections of code, is important. Being able to generate long semantically coherent programs is a key challenge in the field, and this paper presents an approach to program generation that deals with this effectively.\n\nThe method is explained clearly overall, providing background on static analysis with attribute grammars and a clear explanation of the algorithm for using such a static analysis during program generation, compatible with a wide class of models. The appendix provides the details that were omitted from the main paper, including how the training data is prepared, the attributes considered and part of the definition of the attribute grammar, how attributes are encoded, and details about the main and baseline methods.\n\nA key element of the approach is the attribute grammar defines a linear path through the program, allowing the model to be trained using pre-computed attributes and requiring on-the-fly computation of attributes during inference. This is explained best in the training and inference appendix.\n\nA strength of the approach, and an advantage over prior work, is that the method allows for learning constraints and guiding principles from the input corpus, rather than using the static analysis to provide hard constraints. This gives more freedom to the static analysis designer to include attributes that correspond to best-practices or that appear only in certain contexts, without needing to avoid attributes that don't define hard-and-fast rules about programs. Prior work leveraging attribute grammars for program generation used them to enforce hard constraints.\n\nA weakness is that the evaluation static checks match those properties provided by the static analysis attribute grammar. I would be interested to see an evaluation indicating whether the method learns to preserve additional properties beyond those directly measured by the static analysis. Perhaps to that end, please clarify what is meant by 50% evidence. Does this refer to full evidence at 50% of nodes, or 50% evidence at each node? How is the 50% selected? Outside of these concerns, the evaluation is solid. The task and baselines are appropriate, the metrics capture properties of interest, and the evidence from the results tells a quite clear story. Including a measure of spread would improve the results section.\n\n---\n\nLine 71: $\\delta$ accepts programs as inputs, but in the prediction error expression $\\textbf{E}_{(X,Y)\\sim D}[\\delta(P_\\theta(X|Y), Y)]$ you incorrectly pass $P_\\theta(X|Y)$, rather than a program, as the first input to $\\delta$.\n\nNit: Line 165 refers to specification Y rather than specification X.\n\nLine 765 has a broken reference simply appearing as \"??\".", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the main technical limitation of the proposed approach, that the implementation is language-specific, whereas language model baselines are generally language agnostic. The paper does not address (nor, per the checklist, anticipate) potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "DPmNh5ppoTw", "reviewer": "Reviewer_3UN5", "summary": "This paper presents a new model for automatic code completion of full methods\n(rather than simply single lines).  The main innovation is the use of a static\nanalysis tool which can analyze partially generated programs.  The program is\ngenerated hierarchically from an attribute grammar using a model they call a\nNeurosymbolic Attribute Grammer (NSG).  At each step the model has access to:\n- The context code surrounding the code to be generated\n- All the tree nodes which have been generated so far\n- The attributes generated by running the static analyzer over the partially\ncompleted program\n\nTheir hypothesis is that the kind of information that the static analyzer\ngenerates is difficult for a neural network model to learn by simply training on\na large dataset of programs.  They show that their model outperforms both a\nsmallish transformer baseline (~100M parameters) and a Graph Neural Network\nbaseline. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper is well written and relatively easy to understand.\n- Their model *significantly* outperforms all of the baseline models on both\ntheir static analysis metrics as well as their whole code metrics.\nSpecifically, the transformer baseline CodeGPT only generates correct API calls\nfor 4.7% of test samples while their method generates correct API calls for 43.7% of test samples.\n- Tackles the important and immediately applicable task of conditional code\ngeneration.  \n- The idea of using on-line static analysis to aid neural models seems very\ngenerally applicable to almost any conditional code generation model, and their\nresults show that it can make a significant difference.\n\n\nWeaknesses:\n- They only test on relatively small transformer models.  Recent work has\nshown that scaling the size of such transformer models significantly improves\ntheir performance.  So it's possible that the gains from the static\nanalysis will disappear once the transformer models are big enough.  While I don't expect them to scale to GPT-3 results it would have been good to see some analysis of how the performance gains change as the Transformer model size increases.\n- As far as I can tell their model is trained on canonicalized versions of\nthe code where all variable, method and class names are changed to generic names\n(i.e. var_0, var_1, etc.), which prevents the model from taking advantage of the\nsoft information provided in such naming in source code corpora.\n- Most of their whole method metrics are AST based metrics which are biased\ntoward AST base models like theirs rather than sequential metrics like BLEU\nwhich would be biased towards sequential models like CodeGPT (the transformer\nbaseline).  I understand that code is inherently hierarchical and the AST\nmetrics may better represent this, but I would have liked to see results for\nBLEU score as well (which should be quite easy to compute).\n- Their evaluation setup does not include test cases so they cannot directly\nexecute the code to tell whether the code they generate is semantically correct\n(or at least semantically matches the code in the dataset).\n\nQuestions:\n- Was the context size of 512 tokens that you used for CodeGPT large enough\nto include both the relevant specification (surrounding code) as well as the\ngenerated method body for most samples in your training and test sets? What\nfraction of samples were truncated in the training and test sets?\n- What were you trying to show with the 50% evidence visible setting?  This\ndoesn't seem like a realistic setting and so I wasn't sure why you included\nthese results.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I would have liked to see the author acknowledge the fact that their baseline model was a relatively small transformer and that larger transformers may significantly reduce/eliminate the gains provided by their methods.", "review_text": "", "extra_scores": {"ethical_concerns": "I don't see any ethical concerns which are not shared by all code generation models trained on publicly available data.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is well written and clearly motivated, with good results outperforming the most relevant baselines.  All reviewers agree this is a good paper and should be accepted.

There are, however, some comments shared by the reviewers that the authors should take into account to improve this work.  Most notably the transformer language model baseline chosen for comparison may have been a bit weak given the recent progress in this direction.
Decision: Accept (Spotlight)