Title: STRUCTURAL LANGUAGE MODELS FOR CODE GENERATION

Abstract: We address the problem of Any-Code-to-Code Generation (AnyC2C) -generating code given its surrounding code without any restriction on the vocabulary or structure. The state-of-the-art in this problem is the sequence-to-sequence (seq2seq) approach, which treats code as a sequence and does not leverage any structural information. We introduce a new approach to AnyC2C that leverages the strict syntax of programming languages to model a code snippet as a tree -structural language modeling (SLM). SLM estimates the probability of the program's abstract syntax tree (AST) by decomposing it into a product of conditional probabilities over its nodes. We present a neural model that computes these conditional probabilities by considering all AST paths leading to a target node. Unlike previous structural techniques that have severely restricted the kinds of expressions that can be generated in this task , our approach can generate arbitrary expressions in any programming language. Our model significantly outperforms both seq2seq and a variety of existing structured approaches in generating Java and C# code. We make our code, datasets, and models available online.

1. INTRODUCTION:

Generating source code requires reasoning over an unbounded number of syntactic structures and potential symbols. Previous approaches have avoided this issue by limiting the generation problem: program synthesis approaches (Manna and Waldinger, 1971 ) are tailored to domain-specific languages (Gulwani, 2011) , semantic parsing approaches focus on highly templated datasets (Ling et al., 2016; Shin et al., 2019) or SQL (Yu et al., 2018; Dong and Lapata, 2018) , while other recent approaches generate code in general languages like Java and C#, but severely restrict the syntax, vocabulary or nature of the generated expressions (Murali et al., 2017; Brockschmidt et al., 2019a) .

We introduce the task of Any-Code-to-Code Generation (AnyC2C) -generating source code in a general-purpose programming language without any restriction on its vocabulary or structure. Specifically, we focus on generating code in context: given a program P and some part of the program p, predict p from the rest of the program P -=P\p. The only restriction we place is that the target p must have a valid subtree within the program's abstract syntax tree (AST). AnyC2C thus generalizes the restricted expression generation task of Brockschmidt et al. (2019a) , where target code contains only primitive types and excludes user-defined functions. Figure 1 shows two such AnyC2C examples.

While a sequence-to-sequence (seq2seq) model with a copy mechanism works better than existing code generation approaches on AnyC2C (see Section 5), it ignores the structural information available from the code's AST. We present a new approach that explicitly leverages the strict syntax of programming languages to model code snippets as trees -structural language modeling (SLM). SLM estimates the probability of the program's AST by decomposing it into a product of conditional probabilities over its nodes. We present a neural model that computes these conditional probabilities by considering all AST paths leading to a target node. While prior work uses AST paths to read programs (Alon et al., 2019a) , we generate code by producing the target AST node-by-node.

We evaluate SLM on Java AnyC2C benchmarks, where our model achieves a new state-of-the-art exact-match accuracy of 18.04% (previous SOTA: 16.93%). SLMs also outperform existing models on the restricted expression generation task of Brockschmidt et al. (2019a) in C# by a wide margin, 37.61% compared to 26.42%. Our ablation study reveals the importance of using AST paths for both reading and generating code. Finally, we discuss the theoretical advantages of SLMs, and show how they generalize many previous structural approaches for code generation.

2. CODE GENERATION AS STRUCTURAL LANGUAGE MODELING:

We model the task of Any-Code-to-Code Generation (AnyC2C) by computing the probability of a program P r (P), similar to how a language model computes the probability of a natural language sentence. While language models typically assume a sequence as their input, our input is an abstract syntax tree A P . We thus introduce a structural language modeling approach (SLM) for code generation.

We first show a chain-rule decomposition of the tree's probability P r (A P ) into a product of conditional node probabilities, and then describe our path-based model for computing the individual conditional probabilities. We explain how to construct a tree from local node predictions, and finally discuss how our approach differs from previous work on production-based tree generation.

Representing Code as a Tree A program P is a sequence of tokens that is unambiguously equivalent to an abstract syntax tree A P , where each node represents an element in the language (e.g. conditions, loops, variable declarations) from a set T . The AST's leaves (terminals) have an additional user-defined value v ∈ V. Nonterminal nodes can have a varying number of children nodes.

Decomposing the Probability of a Tree Given a tree A P , we first traverse the tree, depth-first,1 to induce an ordering over its nodes a 0 , . . . , a |A P | ∈ A P . We can now decompose the probability of a tree P r (A P ) using the chain rule, akin to the standard approach in language modeling:

EQUATION

where a <t are all the nodes that were traversed before a t .

In AnyC2C, part of the tree (A P -) is already observed. Therefore, we order the nodes of A P - before the nodes of the target p, and compute only the conditional probabilities over the nodes in p, essentially conditioning on the observed tree A P -.

Representing Partial Trees via Paths How can we represent the partial tree composed of a <t when computing P r (a t |a <t )? In regular language modeling, the structure is linear, and a <t is a sequence. One way to represent a partial tree is to linearize it according to the traversal order (Xiao et al., 2016) ; however, this could create artificially long distances between the current node a t and ancestor nodes (e.g., the root a 0 ). Another option is to use only the path from the root node to a t (Rabinovich et al., 2017) , but this ignores a lot of contextual information (e.g., sibling nodes).

We follow Alon et al. (2018) and use the set of paths from every leaf to the current node to expand, as well as the path R t originating from the root. We denote the (candidate) node at time t as a t , its (given) parent, which is the currently expanded node, by π (a t ), and the set of all paths as S t : where π (a t ) is the (only) path in the tree between a leaf and the current node to expand π (a t ), and R t = a 0 π (a t ) is the path from the root of the program to π (a t ), which represents the current, relative position of π (a t ) in the program (marked as R in Figure 2 ). Whereas prior work used whole paths (between two leaf nodes) to encode an AST (Alon et al., 2019b; a) , our model observes partial paths (between a leaf and an intermediate node) and learns to extend them.

EQUATION

Figure 2 illustrates the traversal order of a subtree that represents the expression x > 1, as well as some of the paths used to compute the probability at each step. At each step, the probability of the next node is computed given the paths S t from the root and every given leaf up to the current node to expand. Figure 2(d) shows how after the terminal node Name and its value x are given, path 3 originating from this leaf is also used to compute the probability of the next nodes.

Our path-based approach generalizes previous approaches, such as parent feeding (Yin and Neubig, 2017) , previous action encoding (Yin and Neubig, 2017) , context nodes (Bielik et al., 2016) , and some of the graph-edges of Brockschmidt et al. (2019a) . See Section 8 for further discussion. Generating Trees In sequence generation, the length of the generated sequence is controlled by generating a single EOS token to stop. When generating trees, we require a more sophisticated mechanism to control arity and depth. We augment A P in two ways to allow node-by-node generation.

First, we add a special EOS node node to every nonterminal to control for arity. Generating this node indicates that the parent node has no more children. Second, we decompose each terminal node n v into a sequence of terminal nodes T v by splitting up the node's value v into subtokens based on camel notation (Allamanis et al., 2015) . For example, if v = toLowerCase, then T v = to → lower → case → EOS tok . We end each subtoken sequence with a special EOS tok node to control for depth during generation. Figure 3 shows an example of both EOS node and EOS tok in action.

Node Trees vs. Production Trees While we predict a single node at each step, previous work (Iyer et al., 2018; Brockschmidt et al., 2019a) predicts a grammar production rule. This more direct grammatical representation decomposes the code in a way that often forces the model to predict with partial information. For instance, consider the expression str.Substring(3). The model of Brockschmidt et al. (2019a) would first predict the rule Expr→Expr.Substring(Expr), and only then expand Expr→str and Expr→3; i.e., the model needs to predict the method name (Substring) before the invoking object (str). Further, the Substring method can get either one or two arguments, forcing the model to choose whether to use the one-or two-argument production rule in advance. Node generation, however, allows us to predict the presence of a function call and only then to predict its object, method name, and arguments, rather than predicting these a priori.

We note that there exist other approaches that generate an arbitrary number of child nodes with production rule-based models. For example, Rabinovich et al. (2017) used a "horizontal LSTM" to decide whether or not to generate another child; and Yin and Neubig (2018) presented a transition system with a "Reduce" action.

3. MODEL ARCHITECTURE:

In the previous section, we described how we can generate code given the probabilities P r (a t |a <t ), where a <t is represented by the set of partial AST paths S t . Here, we present a neural model that estimates P r (a t |S t ). We first apply an LSTM-based path encoder to represent each path in S t as a vector (Section 3.1). We then contextualize and aggregate the entire set into a single vector (Section 3.2). Finally, we predict the target node a t by combining a limited output vocabulary with a syntactic copy mechanism (Section 3.3).

3.1. ENCODING AST PATHS:

Given a partial AST path (node sequence n 1 , . . . , n k ), our goal is to create a vector representation.

We first represent each node n i using embeddings. A subtoken node is represented by the index of its subtoken w in the embedding matrix E subtoken ; AST nodes are represented as a pair n i = (τ, κ) where τ is the node type, e.g. IfStatement, and κ is the node index among its sibling nodes. We represent node types using a learned embedding matrix E type and the child indices using a learned matrix E index . The node's vector representation is the concatenation of the type and index vectors.

EQUATION

We encode the entire path using a uni-directional LSTM stack, and take the final states:2 

f (n 1 , . . . , n k ) = LSTM (e (n 1 ) , . . . , e (n k ))

Given a set of partial paths S (omitting the iterator t for simplicity), we denote their encodings as

H = { f (n 1 , . . . , n k ) | (n 1 , . . . , n k ) ∈ S}.

Efficient Computation When processing an entire tree, there are large overlaps between paths from different time steps. In particular, paths that originate from the same leaf share the same prefix. We therefore apply the LSTM on the prefix once, and cache the state across suffixes, speeding up both training and inference significantly. An example is shown in Figure 6 in the Appendix.

3.2. AGGREGATING MULTIPLE PATHS:

Given the set of paths S leading up to the target node's parent π(a), our goal is to represent S as a vector, in the context of predicting a. To do so, we introduce the aggregation function g (H, r, i).

As its input, g takes the set of encoded paths H, the encoded root path r, and the child index i of the currently predicted child node a relatively to its parent.

We first contextualize the path encodings H using a transformer encoder (Vaswani et al., 2017) . 3 In parallel, we apply a non-linear transformation to the encoding of the root path r = f (R), in order to inform it that we wish to predict the i-th child of π(a t ):

EQUATION

In this formulation, the parameter matrix C i is used when the child index is i, while the parameter matrix W a is used for every instance.

We then compute attention over the set of contextualized path encodings Z with the index-informed root-path encoding r as the query, pass the weighted average z and the root-path encoding r through another fully-connected layer and denote the resulting vector representation as h:

EQUATION

3.3. PREDICTING WITH A SYNTACTIC COPY MECHANISM:

We can now predict a from the representation h. If the target node's parent π(a) is a nonterminal AST node, then a must be an AST node; otherwise, a is a subtoken.

Predicting AST Nodes We predict a using a softmax over the node type embeddings E type :

P r (a|S) = softmax E type • h (π(a) is a nonterminal) (6)

Predicting Subtokens Programs repeatedly refer to previously declared symbols, resulting in highly repetitive usage of identifiers. We therefore add a copy mechanism (Gu et al., 2016) to allow our model to predict either entire tokens or subtokens that already exist in the context. As we show in Section 6, copying greatly improves our model's performance. For brevity, we describe how entire tokens are copied, and elaborate on the copy of subtokens in Appendix C. We score each leaf using a bilinear function (W c ) between its path's encoding H and h. At the same time, we score the token w, which is the token associated with , from a limited vocabulary using the inner product between its representation in the subtoken embedding matrix E subtoken and h.

EQUATION

The scores s copy and s gen are then summed over different occurrences that correspond to the same symbol, and subsequently normalized via softmax. A key difference from previous work (Gu et al., 2016; Yin and Neubig, 2017 ) is that our copy mechanism uses the syntactic relation between the source and the target (AST path), rather than their sequential relation. Yin et al. (2019) proposed a graph-based copying mechanism that is capable of copying both tokens and subtrees from the context.

4. EXPERIMENTAL SETUP:



4.1. BENCHMARKS:

Any-Code Generation (AnyC2C): Java We take the Java-small dataset of Alon et al. (2019a) , which contains 11 GitHub projects, broken down to a single method per example, and split to train/dev/test by project to reduce code overlap. This dataset was found to contain the least code duplication by Allamanis (2018b) . We create AnyC2C examples by selecting every expression larger than a single AST node as the target, using the remainder of the method as the context. We remove methods that contain the word "test" in their body or file name, and remove methods longer than 20 lines to avoid auto-generated code. To make the task even harder, we remove examples where the target subtree appear as-is in the context. This dataset contains 1.3M/10k/20k train/dev/test examples. The average number of targets for our model is 10.8; for the seq2seq baselines the average is 7.8 targets; if we modeled our targets using production rules, the average would have been 7.9. Detailed statistics of all datasets are provided in Appendix A.

Metrics We follow Brockschmidt et al. (2019a) and report exact match accuracy at 1 and 5. We also introduce a new tree@k metric, which counts a prediction as correct if the entire tree structure, ignoring leaf values, is identical to the tree of the ground truth. For example, the expressions x > 1 and y > 2 would not count as identical in exact match, but would count as "tree-match identical" because both express that an identifier is greater than an integer (NAME > INT). tree@k is interesting because it allows us to tease apart the model's syntactic errors from incorrect subtoken predictions.

4.2. BASELINES:

We compare our model to a variety of original implementations and adaptations of existing models.

We put significant effort to perform a fair comparison, including adding a copy mechanism to the NMT baselines and subtokenization as in our model. We adapt strong baselines from the literature to our task, even if they were designed to different tasks such as NL→code and code→NL. We re-train all the following baselines on the same datasets as our model.

Neural Machine Translation:

We use standard autoregressive sequence-to-sequence NMT baselines, in which we subtokenize the given code snippet, replace the target in the source with a special PRED symbol, and train the network to predict the target as a sequence of subtokens. Transformer-base+copy (Vaswani et al., 2017) uses the implementation of OpenNMT (Klein et al., 2017) with a copy mechanism (Gu et al., 2016) . Transformer-small+copy uses d model = 256, d ff = 1024, and 4 self attention heads per layer. BiLSTM→LSTM+copy is a d = 512 2-layer bidirectional LSTM encoder-decoder with attention (Luong et al., 2015) . seq2tree+copy follows Aharoni and Goldberg (2017) and learns to generate the linearized, subtokenized target AST, with the same architecture as BiLSTM→LSTM+copy.

Java-specific Baselines We used the original implementation of Iyer et al. (2018) , and also their seq2prod baseline which is a re-implementation of Yin and Neubig (2017) ; these are designed for NL→code tasks, in which we feed the (sub)tokenized code context as the NL input. The model of Iyer et al. (2018) is designed to get additional input of the available variables and their types, for which we do not feed types. While in theory these models could also be applied to other languages, their implementation only supports Java.

C#-specific Baselines We compare our model to GNN →NAG using the original implementation of Brockschmidt et al. (2019a) which contains additional improvements using ideas from Cvitkovic et al. (2019) . Bielik et al. (2016) kindly trained and tested their non-neural PHOG model on our C# dataset. We note that PHOG does not have an explicit copy mechanism, and considers only context to the left of the target code, while we consider also context to the right. Extending PHOG to use copying and considering more context could potentially improve its results.

In both Java and C#, we compare to code2seq (Alon et al., 2019a) , which is a strong code→NL model and train it to generate the target code as a sequence of subtokens.

4.3. IMPLEMENTATION AND HYPERPARAMETER SETTINGS:

Architecture We use embeddings of size 512, 2 layers of LSTMs with 256 units, and 4 transformer layers with 8 attention heads. We kept a subtoken vocabulary of size 1,000 to encourage the model to learn to copy; larger vocabularies did not show an improvement. These resulted in a very lightweight model of only 15M trainable parameters, which is close to Transformer-small (11.8M parameters).

In comparison, the Transformer-base model had more than 45M trainable parameters.

Training We train the model end-to-end using the cross entropy objective and the Adam optimizer (Kingma and Ba, 2014) , an initial learning rate of 10 -4 decayed by a factor of 0.95 every 20k steps.

We bucket examples based on the number of predictions in the target subtree (nodes + subtokens + EOS symbols), and vary the batch size such that each batch contains about 512 targets. We train the model to prefer copying entire tokens rather than copying subtokens, if possible. We apply dropout of 0.25 in the Transformer layers, and a recurrent dropout of 0.5 in the LSTMs.

Inference We perform beam search with width of 5, and optimize for accuracy@1.

Model acc@1 acc@5 tree@1 tree@5 code2seq (Alon et 

5. RESULTS:

Any-Code Generation: Java Table 1 shows that our SLM achieves over 1.1% and 0.78% better acc@1 and acc@5 (respectively) over the two strongest baselines. The improvement over Transformer-small, which is closer to our model in the number of parameters, is even higher: over 3.8% and 3.4% in acc@1 and acc@5.

In general, the NMT baselines performed better than code-specific baselines. We hypothesize that the reason is that the NMT baselines are more generic, while the code-specific baselines are designed for different tasks: seq2prod is designed for tasks which involve generating code given natural language input; Iyer et al. ( 2018) additionally expects all member methods, variables, and their types as input; code2seq is designed to generate sequences rather than code, and does not have a copy mechanism. An approximation of code2seq with a copy mechanism is presented in Section 6.

Interestingly, the syntactically-informed seq2tree baseline achieved the highest tree@k among the baselines, while our model achieved higher acc@k and tree@k. This shows that leveraging the syntax can be beneficial in NMT baselines as well.

Restricted Code Generation (RestrictC2C): C# Table 2 shows the results for the RestrictC2C task in C#, where seq2seq+copy is the BiLSTM→LSTM+copy model which performed the best among the Java baselines. We first observe that the seq2seq+copy and the seq2tree+copy baselines outperform the GNN →NAG of Brockschmidt et al. (2019a) , who introduced this task. Although Brockschmidt et al. (2019a) did compare to a seq2seq baseline, their GNN →NAG model could copy symbols from the context, but their baseline did not. To conduct a fair comparison with our SLM model, we equip the seq2seq and seq2tree baselines with a copy mechanism. Even though the seq2seq+copy and the seq2tree+copy baselines perform substantially better than the state of the art in this setting, our SLM model is able to go beyond, achieving significant gains over all models.

Examples for predictions made by our model and baselines can be found in Appendices D and E.

6. ABLATION STUDY:

To understand the importance of the various components and design decisions in our model, we conducted an extensive ablation study on the AnyC2C task in Java. Paths→Seq follows code2seq (Alon et al., 2019a ) and separates the model to an encoder and a decoder, where the decoder generates the target subtree as a sequence of subtokens. The main difference from code2seq is that Paths→Seq includes a copy mechanism, as in our SLM model.

Seq→Path follows Rabinovich et al. ( 2017) and separates the model to an encoder and a decoder (including a copy mechanism), where the encoder encodes the context as a sequence of subtokens using a BiLSTM, and the decoder uses only the root path and the index of the generated child.

Paths→Paths uses separate encoder and decoder which both are AST-path based. These encoder and decoder have different parameters, unlike our SLM model which models the context and the prediction using the same components.

No Root Attention uses max pooling instead of attention in aggregating multiple paths (see Section 3.2). The index-informed path from the root to the target's parent (R in Figure 2 ) is concatenated with the result, instead of being used as attention query.

No Copy replaces copy mechanism with a much larger vocabulary (25k subtokens instead of 1k).

Table 3 shows the results of these alternatives. The significantly lower results of Paths→Seq and Seq→Path show the great benefit of using a unified structural language model, instead of separate encoder and decoder components. While this separation between encoders and decoders might be necessary in semantic parsing (Rabinovich et al., 2017; Dong and Lapata, 2018) , NL→code (Yin and Neubig, 2017) and code→NL (Alon et al., 2019a; Fernandes et al., 2019) tasks because of the different modalities of the input and the output, this separation may hurt performance when the output is essentially a missing part of the input's AST. As expected, Paths→Seq performs better than code2seq (Table 1 ), as it includes a copy mechanism and code2seq does not.

As SLM performs better than Paths→Paths, this ablation shows the importance of joint modeling of the context and the target subtree by parameter tying. Each of Paths→Paths and the seq2seq baselines (Table 1 ) performs better than Paths→Seq and Seq→Path; this shows the importance of using the same type of encoder and decoder for the AnyC2C task, rather than combining "an optimal encoder" with "an optimal decoder". Paths→Paths performs better than the seq2seq baselines (Table 1 ), showing the advantage of using paths over textual sequences, even without parameter tying.

No Root Attention degrades acc@1 and acc@5 by 3.6% to 6.3%. This shows that dynamically attending to the context paths given the current root path is crucial, even though the root path is necessarily included as a sub-path of other paths in the set S t which go through self-attention.

Not using a copying mechanism results in a degradation of 7.3% to 9.1%. Programs use symbols and identifiers repetitively, thus the ability to copy symbols from the context is crucial for this task.

For this reason, we included a copying mechanism in all NMT baselines in Section 4. (2.6%) (tree-match) zkfcUgi.getUser()

(1.7%) (tree-match) zkfcUgi.getUserId() (0.6%) (tree-match)

Entirely copied tokens are marked in brown; unknown copied subtokens are marked in blue; in-vocabulary subtokens are marked in black; subtokens that are both in-vocabulary and copied from context are marked in purple. 7 QUALITATIVE ANALYSIS

7.1. CORRECT TREE, INCORRECT IDENTIFIER ASSIGNMENT:

As shown in Section 5, there is a gap between acc@k and tree@k across all models: when ignoring identifier values and considering only the tree structure, the accuracy is significantly higher. Our SLM model performs better than all baselines in acc@k (Table 1 ); further, our model also shows a greater potential for improvement in its tree@k results which are much higher than the baselines.

We focus on the studying the cases where the tree structure was predicted correctly, but the model failed to generate the code exactly including names. Figure 4 shows a representative example for this case: the ground truth event.getTaskId() was predicted correctly only as the fifth candidate; nevertheless, all top-5 candidates are a "tree-match" since all of them express a method which is invoked on an object without arguments, of the form: NAME.NAME(). Generating the correct method name [get,task,id] is very difficult in this case, since neither getTaskId nor TaskId appear in the context and there is no apparent hint for them.

7.2. USEFULNESS OF COPY MECHANISM:

As shown in Section 6, the ability to copy is crucial for the AnyC2C task, because of the repetitive use of identifiers and symbols in programs. Figure 5 shows a representative example for the necessity of the copy mechanism: generating the ground truth zkfcUgi.getShortUserName() is feasible only thanks to the copy mechanism, since zkfc is obviously an UNK subtoken which was not observed in the training data.

In this case, since both zkfcUgi and getShortUserName appear in context, both were copied as entire tokens, rather than generated using subtokens. This example also shows how the ability to copy entire tokens ease the generation process by reducing the number of target symbols (our SLM model is able to copy and combine single subtokens as well).

Generalizing Previous Approaches Our approach frames code generation as predicting the next node in all partial AST paths. This simple framing generalizes most previous work, without handcrafted special edges and actions:

• All models that use information about ancestor nodes only (Rabinovich et al., 2017; Maddison and Tarlow, 2014) , as well as the "Parent Feeding" of Yin and Neubig (2017) , are generalized by our model, since all paths that go into a node a t pass through its parent, and the path from the root R t (Figure 2 ) is used as the attention query. • The "previous action encoding" of Yin and Neubig (2017) is also a special case of our approach, because S t contains the paths starting from the previously expanded leaves of A p into the currently expanded node π (a t ), such as path 3 in Figure 2 (e). • The "context node" of PHOG (Bielik et al., 2016) is just one of the previously-traversed leaf nodes in a <t . Thus, not only that our model conditions on this context node as well, our model also takes into account the syntactic relation, i.e., the path, between the context and π (a t ).

Moreover, while PHOG conditions on a single leaf, SLMs condition on every leaf in a <t . • Finally, Brockschmidt et al. (2019a) define special graph edges (e.g., "NextSib" and "Child") to capture relations on the AST. Most of these relations can be expressed as partial AST paths.

Program Generation Learning to generate programs is one of the oldest problems in machine learning (Waldinger and Lee, 1969) and has been considered by some as the "holy grail of computer science" (Pnueli and Rosner, 1989; Gulwani et al., 2017) . Typically, the task is to generate a program given some form of input or context, such as complete formal specifications (Green, 1981) or inputoutput examples (Gulwani, 2011; Devlin et al., 2017; Parisotto et al., 2017) . While these approaches work well in some cases, they are bounded to DSLs that prevent them from being applied to realistic, general-purpose code. Maddison and Tarlow (2014) and Amodio et al. (2017) generate supposedly general-purpose code in a modern programming language, but do not deal with the challenge of fitting the code to a given context. Murali et al. (2017) generate code conditioned on a set of APIs; they state that their approach is thus intrinsically limited to generate API-heavy programs and is unusable for general, logical programs lacking external calls. Further, their generated programs are in an only "Java-like" language. Yin and Neubig (2017) , Iyer et al. (2018) and Rabinovich et al. (2017) generated general-purpose code as well, but for another task of generating code given natural language description. Yin et al. (2019) generated "any code" given an encoded edit that needs to be applied to a given code snippet.

Other work used datasets that are either small (Ling et al., 2016) , containing highly aligned examples (Oda et al., 2015; Chen et al., 2018) , limited-purpose languages like SQL (Yu et al., 2018) , or general-purpose but containing eminently templated programs (Ling et al., 2016) . Brockschmidt et al. (2019a) limit their model to generate only expressions of primitive types or arrays of these; use a closed vocabulary; and ignore expressions containing user-defined functions, because function names are hardcoded in their syntax production rules. In this paper, we lift these constraints and allow any, general-purpose, generation of code, of all types and containing any names. Our work is also related to Habash (2004) , who used structural n-grams over dependency trees for statistical machine translation (SMT).

9. CONCLUSION:

We presented a novel approach for generating code given surrounding context: computing the probability of an AST using a structural language model. We show that our approach generalizes most previous work in this area, while reaching state-of-the-art performance on of challenging benchmarks. We are eager to see future work advance SLMs further, and apply them to other real-life coding applications as well as other structured-data domains. 

B CODE GENERATION PSEUDOCODE:

Algorithm 1 shows the pseudocode for our depth-first, left-to-right, code generation approach. We keep a stack (line 1) which is initialized with an initial node to expand. We loop while the stack is not empty (line 3), and pop (line 4) the next node to expand at each step. If the node to expand is a nonterminal, we predict a child node (line 7). If the node is a terminal to a subtoken, we predict a subtoken from a vocabulary or copy (line 7). If the predicted child node, whether AST node or subtoken, can be further expanded (line 10), it is pushed back to the stack (line 12).

C COPYING SINGLE SUBTOKENS:

In addition to scoring the entire token to be copied, we also score each of the subtokens composing it according to their position. For each position i, we add a scoring function s copyi , such that s copyi ( ) produces the copying score of the i'th subtoken of , which we denote as i :

EQUATION

P r (a|S) = softmax (s)

Where s copy token is the scoring function of copying the entire token, described in Section 3.3.

For example, a token of getX is scored entirely using s copy token ; each of its subtokens, get and X, are scored using s copy1 and s copy2 respectively. That is, the model can either copy the entire token, or copy only some of its subtokens. This ability is especially useful in generating a name like setX, where getX appears in the context, and X is any unknown, user-defined, subtoken; the model learns to generate set from the vocabulary, and copy only the subtoken X.

D JAVA EXAMPLES:

Figures 5-12 contain examples from our test set for the AnyC2C task in Java, along with the prediction of our model and some of the baselines. The highlighted expressions are the true references that should be generated. Indentation and line breaks may have been altered for typesetting reasons.

Algorithm 1: Pseudocode for the code generation algorithm.

Input : partial AST A -, initial node to expand a0 Output: subtree τ 1 stack ← emptyStack(); push(stack, a0); 2 τ ← initTree(a0) ; 3 while stack is not empty do 

:

Depth-first ordering is common practice in tree generation(Maddison and Tarlow,

2014;Raychev et al., 2016; Brockschmidt et al., 2019a), but our framework also allows for other orderings, in theory.

Replacing the LSTMs with transformers yielded similar results in preliminary experiments.

Since H is a set, we do not use positional embeddings.

Figures and Tables:

Figure1: AnyC2C examples from the Java (left) and C# (right) test sets. The highlighted expression in each example is the target p, which we wish to generate from the rest of the snippet.

Figure 2: The expression x > 1 is generated given its surrounding code context. At each step, the model generates the next node (denoted by a question mark: ? ) of path 1 , path 2 and path 3 using the root path R. Dashed lines denote AST parent-child relations; solid lines denote AST paths.

Figure 3: Augmenting the AST with EOS node and EOS tok nodes

Figure 4: A Java AnyC2C example from our test set along with the predictions of our model. The predictions of the baselines are shown in Figure 8 in Appendix D.

Figure 5: A Java AnyC2C example from our test set along with the predictions of our model. The predictions of the baselines are shown in Figure 7 in Appendix D.

Figure6: Efficient computation: partial paths for different time steps share the same prefix, allowing a shared computation. In this example, the prefix is the shared path from the leaf (not shown) to Greater, and is much longer than either of the suffixes.

Figure12: Java examples from our test set along with the predictions of our model and the baselines.

Figure 20: C# examples from our test set of the RestrictC2C task along with the predictions of our model and the baselines.

Results on Any-Code-to-Code Generation (AnyC2C) in Java.

Table content: <table><tr><td/><td/><td>al., 2019a)</td><td/><td/><td>10.68</td><td>15.56</td><td>30.46</td><td>43.94</td></tr><tr><td colspan="2">Iyer et al. (2018)</td><td/><td/><td/><td>5.94</td><td>9.19</td><td>25.54</td><td>36.75</td></tr><tr><td colspan="4">seq2prod (Yin and Neubig, 2017)</td><td/><td>8.05</td><td>11.82</td><td>30.77</td><td>41.73</td></tr><tr><td colspan="5">Transformer-small (Vaswani et al., 2017)+copy</td><td>14.23</td><td>21.35</td><td>31.83</td><td>47.40</td></tr><tr><td colspan="5">Transformer-base (Vaswani et al., 2017)+copy</td><td>16.65</td><td>24.05</td><td>34.68</td><td>50.52</td></tr><tr><td colspan="5">BiLSTM→LSTM (Luong et al., 2015)+copy</td><td>16.93</td><td>23.17</td><td>34.29</td><td>49.72</td></tr><tr><td colspan="5">seq2tree (Aharoni and Goldberg, 2017)+copy</td><td>16.81</td><td>23.04</td><td>38.14</td><td>52.36</td></tr><tr><td colspan="2">SLM (this work)</td><td/><td/><td/><td>18.04</td><td>24.83</td><td>39.10</td><td>55.32</td></tr><tr><td>Model</td><td colspan="4">acc@1 acc@5 tree@1 tree@5</td></tr><tr><td>GNN→NAG</td><td>15.19</td><td>27.05</td><td>26.48</td><td>40.09</td></tr><tr><td>code2seq</td><td>6.20</td><td>10.05</td><td>21.97</td><td>30.89</td></tr><tr><td>seq2seq+copy</td><td>26.42</td><td>37.94</td><td>34.10</td><td>49.23</td></tr><tr><td>seq2tree+copy</td><td>22.29</td><td>35.86</td><td>31.85</td><td>48.53</td></tr><tr><td>PHOG</td><td>7.40</td><td>12.00</td><td>-</td><td>-</td></tr><tr><td>SLM (this work)</td><td>37.61</td><td>45.51</td><td>51.10</td><td>59.82</td></tr></table>

Results on RestrictC2C in C#.

Table content: <table><tr><td>Ablation</td><td colspan="2">acc@1 acc@5</td></tr><tr><td>Paths→Seq</td><td>12.95</td><td>18.52</td></tr><tr><td>Seq→Path</td><td>12.12</td><td>17.12</td></tr><tr><td>Paths→Paths</td><td>17.63</td><td>24.62</td></tr><tr><td>No Root Att</td><td>14.43</td><td>18.48</td></tr><tr><td>No Copy</td><td>10.72</td><td>15.70</td></tr><tr><td>SLM (original model)</td><td>18.04</td><td>24.83</td></tr></table>

Ablations on AnyC2C in Java.

Table content: <table/>

Statistics of our datasets. When not mentioned otherwise, the statistic was measured on the training set.

Table content: <table><tr><td>Java</td><td>C#</td></tr></table>

shows some statistics of our used datasets. In Java: for the validation set, we randomly sampled 10, 000 examples from the raw dev set; for the test set, we randomly sampled 20, 000 examples from the raw test set.

Table content: <table/>

Peer review (iclr2020):
This paper presents a grammar-based generation approach for *slot-filling* style code generation tasks. Given a context AST with opening non-terminal node, the model completes the opening node by predicting a sequence of child nodes, which forms a sub-AST rooted at the original opening node. The proposed model encodes context ASTs using a path-based approach (Alon et al., 2019a), essentially generalizing the previous model of Alon et al., 2019a from a code-to-sequence setting (e.g., generating natural language comments from code) to a *code-to-code* setting (i.e., code completion given contextual snippets). Strong Points: * The paper is very well written. The idea of formalizing code completion as structured language modeling and extending Alon et al., 2019a for the task is natural and well executed, with strong models and significantly improved results on two code completion benchmarks for both Java and C#. * The authors attempted to establish comparisons with most existing code generation models. Detailed Review: *Technical Contribution* I have a very mixed feeling with this paper, while the model registers high empirical performance, the technical contribution is a bit limited, as detailed below: - *Path-based Context Encoding* The most important contribution in this submission is the application of path-based AST encoding model of Alon et al., 2019a to encode context (the given contextual and partially generated ASTs) for code generation. While the path-based encoding scheme is indeed a powerful model that intuitively encapsulates and generalizes over most previous approaches (Section 7), applying the model to a different task without significant task-specific adaptation or in-depth analysis might not sound technically novel. Meanwhile, the core idea of modeling/encoding the information flow in both the given context AST and partially generated programs for opening node expansion has already been explored in Brockschmidt et al. (2019a), albeit using a different encoding approach (GNNs) and in a relatively restricted setting of generating arithmetic expressions. - *Node-based Tree Generation Model* Apart from the path-based context encoding model, the node-based generation model presented in Section 2 also seems interesting. However, it might take longer time-steps to generate the node sequence instead of the sequence of production rules (composed of multiple child nodes), which could make optimization and inference more difficult. On the other hand, to control arity, the node-based approach need to inject synthetic *EOS* nodes to signal end of generating an argument sequence, while existing production rule-based systems could easily generate arbitrary number of argument nodes using either a transition system (e.g., Yin and Neubig, 2018) or a special neural component to compute end-of-argument-list probability (e.g., Rabinovich et al. (2017)), without using separate production rules of different arity. - *Syntactic Copy Mechanism* While the proposed syntactic terminal token copy mechanism (Section 3.3) could be better than the vanilla sequential one, there have already been syntactic copying models capable of copying both terminal tokens and partial ASTs from the context (Yin et al., 2019). How to Improve: to better understand the different technical contributions outlined above and their relative impacts, the following ablation studies would be helpful: - Importance of Path-based Context Encoding: the Seq?Path ablation in Table 3 alone might not be adequate to demonstrate the importance of path-based encoding of AST contexts for code generation tasks. The authors should compare with the GNN-based context encoding approach in Brockschmidt et al. (2019a) as this is the most relevant work. The original GNN?NAG model cited in Table 2 used a much simpler copying mechanism and a vanilla production-based tree generation model, and therefore not directly comparable with a tuned SLM. - Importance of Node-based Tree Generation Model: If possible, the authors might consider swapping their node-based tree generation model with a state-of-the-art production-based approach (e.g., Yin et al., 2019) to demonstrate its effectiveness. *Claims* The authors claimed in the beginning of the paper that previous program synthesis approaches are either restricted in domains (e.g., DSLs like SQL) or grammars (e.g., restricted grammar of the full language), therefore coining the proposed approach as *any-code generation*. However, there are indeed code generation systems (some of them cited in this paper) that synthesize open-domain code snippets in general-porpuse programming languages without restriction on vocabulary or grammar. To give a few examples, Iyer et al. (2018) generate open-domain Java class member functions; Rabinovich et al. (2017) and Zhao et al. (2019) predict full Python classes or partial snippets, while Yin et al. (2019) synthesize open-domain short C# code diffs observed in GitHub commits. In fact, the the proposed *any-code generation* benchmark is limited to sub-expressions defined within a function, whose scope is more restricted than other benchmarks like CONCODE. How to improve: the authors might present more evidence to substantiate the their claim on the novelty of the AnyGen benchmark compared with existing open-domain, general purpose code synthesis benchmarks, or consider revising the claim and the title. References: * Zhao et al., Neural Networks for Modeling Source Code Edits. 2019 * Yin et al., Learning to Represent Edits. 2019