The impact of lexical and grammatical processing on generating code from natural language (2022)

Abstract: Considering the seq2seq architecture of Yin and Neubig (2018) for natural language to code translation, we identify four key components of importance: grammatical constraints, lexical preprocessing, input representations, and copy mechanisms. To study the impact of these components, we use a state-of-the-art architecture that relies on BERT encoder and a grammar-based decoder for which a formalization is provided. The paper highlights the importance of the lexical substitution component in the current natural language to code systems.

## introduction translating natural language program descriptions to actual code is meant to help programmers to ease writing reliable code efficiently by means of a set of advanced code completion mechanisms. there are mainly two classes of methods for obtaining code corresponding to a query expressed in natural language. the first one is code retrieval, which consists of searching and retrieving an appropriate code snippet from a code database. the second one is code generation, where the goal is to generate code fragments from a natural language description, generating potentially previously unseen code. in this work, we are interested in python code generation. code generation features a mismatch between an ambiguous and noisy natural language input and the structured nature of the generated code. although python's vocabulary has a finite number of keywords, the set of values that can be assigned to a variable is infinite and constitutes one of the issues in predicting code corresponding to natural language. like many other nlp tasks, current architectures for natural language to code generally take advantage of pre-trained language models such as bert @xcite or @xcite based on the transformer architecture @xcite . in particular, these architectures are used for code generation where parallel data is limited due to the human expertise required for alignment. the best results on code generation are reached by pretraining seq2seq models on external sources, then by fine-tuning those models on smaller data sets. for instance, @xcite fine-tune bart @xcite on data pairs of natural language and code and by taking advantage of external informations. similarly, @xcite used bert and a transformer decoder in a semi-supervised way by taking advantage of a large amount of additional monolingual data. another popular method is to train large language models on code @xcite . notably, gpt-3 has been finetuned on a large quantity of data from github to obtain a powerful language model named codex @xcite that powers github copilot, a tool to help developers. overall the above mentioned solutions aim to take advantage of large amounts of training data available nowadays, but few of them care about generating code that is guaranteed to be syntactically correct nor well typed. let us mention some exceptions from semantic parsing like @xcite ; @xcite ; yin and neubig (2017) that rely on grammatical constraints to ensure that the generated code can be executable. in this work, we study variations around the tranx seq2seq architecture @xcite for translating natural language to code. rather than generating directly code tokens from natural language, the architecture generates an abstract syntax tree (ast) constrained by the programming language grammar. the paper reports state of the art results on the task and specifically introduces: it is structured as follows. section 2 formalizes the symbolic transition system used for generating the grammatically correct code, section 3 describes a family of variants around the tranx architecture that will be used to study the impact of these variations in the experimental part of the paper (section 4). ## a transition system for code generation among the models tested in the paper, some are generating syntactically constrained code. in the context of our study, we propose a transition model that meets two objectives: the code generated is grammatically valid in terms of syntax and the whole translation process still reduces to a seq2seq transduction mechanism that allows us to leverage standard machine learning methods. to this end we introduce a transition system for code generation that generates an ast as a sequence of actions. the derivations can then be translated into asts and in actual python code by means of deterministic functions. the set of valid asts is a set of trees that are generated by an asdl grammar @xcite ). an asdl grammar is essentially a context free grammar abstracting away from low level syntactic details of the programming language and aims to ease the semantic interpretation of the parse trees. to this end asdl grammar rules come with additional decorators called constructors and field names (figure 1 ). our transition system generates derivations, or sequences of actions, that can be translated to a syntactically correct python code. we adapt to code generation the transition system of the earley parser @xcite as formalized in figure 2 . the generator state is a stack of dotted rules. a dotted rule is a rule of the form @xmath0. the •x symbol is the dotted symbol or the next symbol for which the system has to generate the subtree. the python asdl grammar includes rules with star ( * ) qualifiers allowing zero or more occurrences of the starred symbol. the transition system uses an additional set of starred actions and a close action to stop these iterations (figure 2 ). each predict(c) action starts the generation of a new subtree from its parent. the generate action adds a new leaf to a tree. the complete action finishes the generation of a subtree and continues the generation process with its parent. the set of predict actions is parametrized by the asdl rule constructor (c), thus there are as many predict actions as there are constructors in the asdl grammar. constructors are required in order to generate the actual asts from the derivations. generate(v) actions are actions responsible for generating the terminal or primitive symbols. the python asdl grammar generates asts with primitive leaf types (identifier, int, string, constant) that have to be filled with actual values for the ast to be useful. to generate actual primitive values the set of generate actions is also parametrized by the actual values v for the primitive types. the set of such values is infinite and consequently the set of generate actions is also infinite. non-determinism comes from the use of pre-dict(c), generate(v) and close rules. by contrast the application of the complete action is entirely deterministic: once the generator has a completed dotted rule on the top of its stack, it has no other choice than applying the complete rule. the sequential generation process is illustrated in figure 3 . given a start state, at each time step, the generator has to decide which action to perform according to the current state of the stack and updates the stack accordingly. once the generator reaches the goal state, we collect the list of actions performed (the derivation) in order to build the ast that we finally translate into actual python code foot_0 . ## factors influencing code prediction all architectures analyzed in this study are variations around a seq2seq architecture. we describe the several variants of this architecture used in this paper both on the encoder and decoder side. we identify key factors that have an impact on the natural-language-to-code translation architecture each rule is built from a set of grammatical symbols (in blue), is uniquely identified by a constructor name (in red) and provides names to its right hand side symbols, its fields (in green). grammatical symbols are split in nonterminals (like expr) and terminals or primitives (like constant). grammatical symbols can also be annotated with qualifiers ( * ) that allow for zero or more iterations of the symbol. ## experiments in this section we describe the characteristics of the data sets on which we have tested our different setups and the underlying experimental parameters foot_1 . ## conclusion we formalized a transition system that allows us to guarantee the generation of syntactically correct code. a detailed study of the components of the seq2seq architecture reveals that the models have difficulties at managing accurately variable names and list encodings. the comparison with models trained on larger noisy data sets reveals that our grammatically constrained architecture without explicit denoising remains competitive. this further highlights the importance of grammatical constraints and of specific processes dedicated to manage variables, list naming and typing. finally, we observe that bleu and exact match, used in this paper, although commonly used in the literature, are not ideal metrics especially because high bleu scores do not guarantee that the code will be executable. even exact match is not satifactory since a single natural language query can be solved by several python programs. in future work, we plan to build extensions to the datasets used here with additional test cases assessing the correction of the generated code. these tests are likely to support more relevant metrics for code generation evaluation.