Antecedent Predictions Are Dominant for Tree-Based Code Generation

Code generation focuses on the automatic conversion of natural language (NL) utterances into code snippets. The sequence-to-tree (Seq2Tree) methods, e.g., TRANX, are proposed for code generation, with the guarantee of the compilability of the generated code, which generate the subsequent Abstract Syntax Tree (AST) node relying on antecedent predictions of AST nodes. Existing Seq2Tree methods tend to treat both antecedent predictions and subsequent predictions equally. However, under the AST constraints, it is difﬁcult for Seq2Tree models to produce the correct subsequent prediction based on incorrect antecedent predictions. Thus, antecedent predictions ought to receive more attention than subsequent predictions. To this end, in this paper, we propose an effective method, named APTRANX (Antecedent Prioritized TRANX), on the basis of TRANX. APTRANX contains an Antecedent Prioritized (AP) Loss, which helps the model attach importance to antecedent predictions by exploiting the position information of the generated AST nodes. With better antecedent predictions and accompanying subsequent predictions, APTRANX signiﬁcantly improves the performance. We conduct extensive experiments on several benchmark datasets, and the experimental results demonstrate the superiority and generality of our proposed method compared with the state-of-the-art methods.


Introduction
Code generation is an essential text generation task in the community of natural language processing (NLP), which deals with automatically generating a piece of executable code from NL utterances. In recent years, a series of Seq2Tree models have made remarkable achievements for code generation [Dong and Lapata, 2016, Rabinovich et al., 2017, Yin and Neubig, 2017, Shin et al., 2019, Sun et al., 2019, Xie et al., 2021, Jiang et al., 2021, 2022. Specifically, given an NL utterance input, instead of outputting a sequence of code tokens directly, the Seq2Tree model outputs a sequence of AST actions, which correspond to the nodes in AST, in a traversal method, and converts them into code via certain deterministic functions eventually. Depending on the AST structure, the Seq2Tree model ensures the compilability of the generated code. Furthermore, the AST structure also helps the Seq2Tree model shrink the search space, i.e., the antecedent predictions will constrain the subsequent predictions, to generate code better.
Despite the success of the above models, they still neglect that the antecedent predictions play an important role for Tree-based code generation. The AST corresponding to the code is a structure of progressive derivation from the root node to the leaf nodes, and the child nodes are derivations of the parent nodes. Under the constraints of the AST, parent nodes are able to determine the type, order, and even number of child nodes with ease. When the output node sequence of the Seq2Tree model is based on the pre-order traversal of the AST 2 , the parent node is always ahead of the child node. Consequently, when the antecedent parent node is wrong generated, the Seq2Tree model can barely predict the subsequent child nodes in a right way, which dramatically impacts the effectiveness of the Seq2Tree model.
In this paper, we propose an effective APTRANX method with AP Loss, which helps the model prioritize antecedent predictions during training, so that generating more accurate antecedent predictions and accompanying subsequent predictions during inference. AP Loss is a dynamically scaled cross entropy loss, which contains a scaling factor and a magnitude factor. The scaling factor is related to the position of the traversal order of AST nodes, and the magnitude factor controls the magnitude of the total loss function. Intuitively, AP Loss automatically reduces the contribution of the susceptible subsequent predictions and focuses on the more important antecedent predictions during training. To demonstrate the effectiveness of APTRANX, we conduct extensive experiments on three benchmark datasets. Experimental results show that our proposed method outperforms the previous state-of-the-art methods. Furthermore, we note that APTRANX is not only suitable for the pre-order traversal but also achieves significant improvement on the breadth-first traversal, which indicates its generality.
The main contribution of this paper can be summarized as follows: • We propose that the antecedent predictions are more essential than the subsequent predictions in the Tree-based code generation method.
• We propose a novel method, namely APTRANX, with AP Loss that assists the model to concentrate on antecedent predictions by leveraging the position information of the generated AST nodes.
• Our proposed method outperforms the previous state-of-the-art methods on several benchmark datasets. Extensive experimental results also demonstrate the effectiveness and versatility of our proposed method.

Motivation
It is well known that code is a type of specialized text with strict grammatical rules and specific structural patterns. A number of statements in the code can effectively influence the structure of subsequent code, such as for, while, and if. Fig. 1 demonstrates an example for code generation. As shown in the right part of Fig. 1, the beginning tokens marked in orange lead the structure of the following code sentences, respectively, which indicates the importance of the antecedent token in the corresponding code sentence.
The antecedent node is dominant, when the code is converted into the corresponding AST based on the pre-order traversal. Fig. 2 shows the procedure of converting an input NL utterance into the corresponding python code snippet by the Seq2Tree model. As shown in Fig. 2, the AST nodes have some of the following properties: 1. The parent node can determine the left side of the production rule of the child node, e.g., since the right side of the production rule of node 0 is Module(stmt* body), the left side of the production rule of node 1 must be stmt.
2. The parent node is able to control the number and order of the child node. For instance, the right side of the production rule of node 3 is Attribute(expr value, identifier attr), therefore node 3 has two child nodes, the first is expr and the second is identifier.
3. The parent node allows for a decision of the type of the child node. For example, because the right side of the production rule of node 4 is Name(identifier id), the type of node 5 has to be the id of the identifier. Similarly, the type of node 6 has to be the attribute of the identifier.
In pre-order traversal of the AST node, the parent node precedes the child node. As a result, the more anterior AST node in pre-order traversal is more crucial.
For effective training, the Seq2Tree model at each step generate the next prediction based on the right label during training stage, which leads to an unnegligible inconsistency between training and inference stage, i.e., the right label during training is inconsistent with the real previous prediction during inference, because the right label is unknowable during inference. It is extremely difficult to generate the correct subsequent prediction based on incorrect antecedent predictions under the AST constraints. Thus, the cost of producing incorrect predictions is quite expensive during inference. To this end, in this paper, we propose an effective method to alleviate the negative effect of the training inconsistency.

Background
In this section, we describe the principle and architecture of TRANX , which is adopted as our basic model. Because of its extensive applications and competitive performance, TRANX has been widely employed in code generation. Please note that our proposed AP Loss is suitable for other Seq2Tree models as well.
In Fig. 2, based on the abstract syntax description language (ASDL) grammer and the input NL utterance, TRANX first outputs a sequence of actions used to construct the AST in pre-order traversal. Then the user specified function AST_to_Code(*) is called to map the generated intermediate AST into the code. Concretely, three types of ASDL grammar-based actions are available in TRANX: actions apply a constructor c to the composite field of a node with the same type as c, generating the child node using the fields in c.
REDUCE actions complete the generation of the child node for a field which has optional(?) or multiple( ) cardinalities.

GENTOKEN[v]
actions expand the field of a node to generate a token v.
TRANX uses an attentional encoder-decoder framework with augmented recurrent connections to interpret the topology of the AST, where the encoder is a Bidirectional Long Short-term Memory (BiLSTM) network and the decoder is an LSTM network as well. Given the input NL utterance x of n tokens, i.e., {x i } n i=1 , the BiLSTM encoder learns vectorial representations {h} n i=1 . Then, at each step t, the LSTM decoder generate hidden state s t as: where f LSTM is the LSTM decoder transition function, [:] denotes the concatenation of vectors, a t−1 and p t denote the embedding of previous action and parent action, respectively. We define the attentional vectors t as: where tanh is the hyperbolic tangent function, W c is a parameter matrix, c t denotes the context vector weighted by encoding representations {h} n i=1 using attention. Finally, the probability of an APPLYRULE[c] action with embedding a c at each step t is: where softmax is the softmax function, a T c denotes the transpose of embedding a c , W is another parameter matrix. Note that REDUCE is considered as a special APPLYRULE action. For the GENTOKEN action, its probability is defined as: where Similar to other Seq2Tree models, given a corpus (x, a), TRANX is trained to minimize the cross enropy loss: where T is the total number of actions and θ denotes the parameters of TRANX.

Methodology
In this section, we first introduce AP Loss in detail, and then a magnitude factor is given to regulate the magnitude of the total loss function.

Antecedent Prioritized Loss
We extend the standard cross entropy loss (6) to AP Loss by exploiting the position information of the AST traversal order. Specifically, a scaling factor t −γ is added with respect to the action index t, and the AP Loss is defined as: where the tunable hyperparameter γ ≥ 0. The scaling factor t −γ decreases as the action index t increases, which helps the model down-weight the action with large t and thus focus training on the action with small t, i.e., the antecedent action. The scaling factor is visualized for several values of γ ∈ [0, 2] in Fig. 3. When γ = 0, L apl is equivalent to L ce . Intuitively, we would prefer not to choose γ > 1, because the scaling factor t −γ varies dramatically under this circumstance. For example, with γ = 2, an action with index 10 would have 100× lower loss compared with L ce . This may cause the model to abandon the training of subsequent predictions completely, which is undesirable. A desired scaling factor has to balance the loss of both antecedent predictions and subsequent predictions, therefore we recommend picking γ from 0.1 to 0.5. Note that the difference between L apl and L ce is only the scaling factor t −γ , so it is quite easy to implement AP Loss in code.

Magnitude Adjustment
In practice, we insert an α-adjusted magnitude factor in AP Loss: We adopt the above form in our experiments because it yields improvements over the non-α-adjusted form (7). Generally, α can be chosen from the positive constants. Furthermore, in order to reduce the choice of hyperparameters, we keep the magnitude of L apl equal to the magnitude of original L ce using the integral, which relates α to γ.
See supplementary material for a detailed derivation of α. With the help of (9), we only need to tune γ, and the appropriate α will be calculated automatically.

Datasets
We conduct experiments on three benchmark datasets as follows: GEO [Zelle and Mooney, 1996] consists of 880 US geographical NL utterances and their corresponding code defined in lambda logical forms.
ATIS [Hemphill et al., 1990] is a collection of 5,410 paired flight data, which contains the NL description of flight information and their corresponding lambda calculus code like GEO.
CONALA  contains 2,879 real-world data of manually annotated NL questions and their Python3 solutions on STACK OVERFLOW, which is more difficult because of its complex and extensive code composition.
The detailed statistics of the three datasets are shown in Table 1.

Baselines
To exhibit the effectiveness of our proposed method, we compared it with several competitive and the state-of-the-art methods as follows: SEQ2TREE [Dong and Lapata, 2016] uses a general attention-enhanced encoder-decoder model to generate logical forms by conditioning output trees.
ASN [Rabinovich et al., 2017] outputs the AST constructed by a decoder whose modular structure is dynamically determined, parallel to the structure of the output tree.
COARSE2FINE [Dong and Lapata, 2018] first generates a rough meaning sketches abstracted abstracted from low-level information, and then fills in missing detail.
TRANX [Yin and Neubig, 2019] is our basic model described detailed in Section 3. TRANX (our) and TRANX' (our) are the versions of the pre-order and breadth-first traversals of TRANX reimplemented by us, respectively.
TREEGEN [Yin and Neubig, 2019] uses the Transformers instead of LSTM to alleviate the long-dependency problem and the AST reader to incorporate both grammar rules and AST structures. [Xie et al., 2021] adopts a mutual learning framework to jointly train models for different traversals based decodings. [Jiang et al., 2021] uses a context-based branch selector to dynamically determine optimal branch expansion orders for multi-branch nodes.

Metrics
To evaluate the effectiveness of different methods, we use two widely-used evaluation metrics: the exact matching accuracy (ACC.) for all datasets and the corpus-level BLEU for CONALA as a complement.

Settings
We train our model for a maximum epoch of 80 with Adam [Kingma and Ba, 2015] optimizer on a single GPU of Tesla V100-SXM2-32G. To ensure fair comparisons, we adopt the same experimental setup as TRANX [Yin and Neubig, 2019]. To be specific, we set the sizes of word embedding, action embedding, and hidden states as 128, 128, and 256, respectively. The beam size is set to 5 for GEO and ATIS, while 15 for CONALA. For additional hyperparameter γ and α, we pick γ ∈ [0.1, 0.5] and α from the set of 1, 2, 4, 8, and 'auto' 3 using validation set. To mitigate the instability of the model training, we exhibit the average performance of the model running five times.

Experimental Results
In this section, we first report the main experimental results to demonstrate the remarkable effectiveness of our proposed method, and then we analyze the effects of γ and α, finally, we find some examples to verify the benefits of AP Loss in practice. Table 2 lists the overall experimental results on three benchmark datasets. We can find that the performance of our reimplemented TRANX is comparable to the original paper [Yin and Neubig, 2019]. With the help of AP Loss, APTRANX outperforms baselines across all datasets, which validates the superiority of AP Loss. It also indicates that letting the model concentrate on the predictions of the antecedent AST nodes during training helps code generation in inference. In addition, the performance of TRANX' is inferior to that of TRANX. A possible reason is that the breadth-first traversal has some drawbacks. For examples, back to Fig. 2, the breadth-first traversal, compared to the pre-order traversal, prioritizes the output of the Reduce actions and delays the output of GenToken actions, which is actually evaluated. Moreover, in Fig. 2, the attribute of the variable is output before the variable in breadth-first traversal, which increases the difficulty of prediction. Nevertheless, both the pre-order and breadth-first traversals of TRANX are improved using AP Loss. It implies AP Loss can be applied to other reasonable orders.

Effects of γ and α
The coefficient γ and α are important hyperparameters to regulate AP Loss. Therefore, we first investigate the effect of γ on AP Loss with optimal α in Fig. 4. The best γ is 0.4 for GEO, 0.1 for ATIS, 0.1 and 0.2 for CONALA (γ with high BLEU is preferred in this paper). We can find the best γ is inversely correlated with the Avg Length of the AST in Table 1. This is because, in training stage, AP Loss need to increase the scaling factor t −γ appropriately by reducing γ for long AST sequences, thus avoiding ignoring the later nodes. In Table 3, we vary α for AP Loss with optimal γ. As α increases, the general trend of the performance of APTRANX rises and then falls on all datasets. When α is set to 'auto', APTRANX achieves the best performance in terms of accuracy for ATIS and CONALA, and impressive results regarding accuracy for GEO and BLEU for CONALA. When we substitute the optimal γ and the corresponding average AST length for each dataset into Eq. (9), α is 1.96 for GEO, 1.27 for ATIS, 1.23 and 1.50 for CONALA, which are all in the range of 1 to 2. Therefore, it is expected that the model works well when α is equal to 1 and 2. These results demonstrate the advantage of using Eq. (9) to calculate α automatically.

Case Study
We compare the top-1 code generated from TRANX and APTRANX on different datatsets in Table 4. We find that TRANX tends to produce the incorrect antecedent prediction, which makes it difficult to generate subsequent predictions with the constraints of the AST. By contrast, our model APTRANX succeeds in overcoming the above problem with the help of AP Loss to generate more accurate code. ( argmax $0 ( and ( place:t $0 ) ( loc:t $0 c0 ) ) c0 ) APTRANX ( argmax $0 ( and ( place:t $0 ) ( loc:t $0 c0 ) ) ( elevation:i $0 ) ) ATIS TRANX Tell me about the type of aircraft call an ac0.

Related Work
Recently, a numbers of code generation models have achieved great success [Alvarez-Melis and Jaakkola, 2017, Hayati et al., 2018, Sun et al., 2019, Wei et al., 2019, Xu et al., 2020. The work [Ling et al., 2016] treated code generation as conditional text generation and solved it with the sequence-tosequence model. In order to utilize the syntactic information of the code, the Seq2Tree models are resorted, which transforms NL utterances into a sequence of AST based grammar actions. Typically, [Dong and Lapata, 2016] first explored a Seq2Tree model for code generation. [Rabinovich et al., 2017] explored a modular encoder-decoder architecture with structured AST output spaces. ] proposed a Seq2Tree model to generate the AST as the intermediate representations of codes. Moreover, [Sun et al., 2020] used the Transformer [Vaswani et al., 2017] architecture and attention mechanisms to address the long dependency problem for code generation. [Jiang et al., 2022] explored the use of the future nodes information generated by the AST for prediction.
Some researchers have also noticed that the importance of each AST node for code generation is different. [Xie et al., 2021] proposed a mutual learning framework for Seq2Tree models to learn the information of AST nodes in different traversals simultaneously. [Jiang et al., 2021] select the generation path of the node in AST using reinforcement learning. Significantly different from the above work, we explore the impact of the position information of AST nodes during inference and propose an effective method to focus on the more important antecedent nodes during training.

Conclusion and Discussion
In this paper, we have identified the prediction of antecedent nodes as an important factor influencing the accuracy of the Seq2Tree model. To address this, we have proposed an effective APTRANX method with AP Loss, which scales the standard cross entropy loss in order to focus learning on antecedent nodes and down-weight the susceptible subsequent nodes. With the help of AP Loss, APTRANX achieves the state-of-the-art performance on three benchmark datasets. Extensive experimental result and analysis also verify its effectiveness and generality.