Towards Full-line Code Completion with Neural Language Models

Since (Hindle et al. 2012) have found out that source code shares mutual statistical properties with natural language, researchers started using statistical language models on source code. Most early researches use the N-gram language models to model source code. (Tu, Su, and Devanbu 2014) pointed out that source code has a unique property of ”localness,” which could not be captured by the traditional N-gram model. (Hellendoorn and Devanbu 2017) introduced an improved cache-based N-gram model to address the localness and unlimited vocabulary in source code. Their evaluation results on code completion showed that their model outperformed existing statistical and neural language models. (Raychev, Bielik, and Vechev 2016) proposed a probabilistic language model based on decision trees and domain-specific grammars. They performed experiments on predicting AST nodes rather than directly performing on source code.

Recently, deep learning-based language models have been applied to source code for the code completion task. (Liu et al. 2016) proposed a code completion model based on an LSTM network. (Bhoopchand et al. 2016) proposed an RNN model with a pointer mechanism aiming at copying tokens from the past. Similarly, (Li et al. 2018) proposed a pointer mixture network to address the Out-of-Vocabulary (OoV) issue. In predicting the type of the next AST node, their model outperforms (Raychev, Bielik, and Vechev 2016) on both Python and JavaScript datasets. (Karampatsis et al. 2020) use a GRU language model for code completion and use byte-pair encoding (BPE) (Sennrich, Haddow, and Birch 2016) to overcome the open vocabulary problem. In the above works, RNN language models are adopted to model the programs. However, RNNs share a common weakness: they cannot efficiently capture the long-term dependencies in sequential data (Khandelwal et al. 2018). An efficient way of mitigating long-term dependency problems in neural network language models is to use the Transformer (Vaswani et al. 2017) model. (Radford et al. 2018) first use Transformer to build autoregressive language models and achieved improvement over LSTM-based models on various natural language classification and generation tasks. For code completion, (Liu et al. 2019) adopted Transformer-XL (Dai et al. 2019) on the AST node completion task, and achieved state-of-the-art results.

The task of automatically generating program code with deep neural networks has been discussed in the natural language processing community as a part of semantic parsing researches. One of the key challenges of code generation is to generate syntactically valid code snippets. (Dong and Lapata 2016) proposed SEQ2TREE, which uses a tree-structured LSTM to directly generate ASTs, but this model cannot guarantee the validness of generated trees. (Yin and Neubig 2017) addresses this issue by converting the generation of a code snippet into applying a sequence of actions defines by the grammar of the programming language. An action either apply a grammar production rule or emit a terminal token. (Rabinovich, Stern, and Klein 2017) first introduced abstract syntax description language (ASDL) (Wang et al. 1997) grammar into code generation by using a tree-structured decoder. (Yin and Neubig 2018) proposed tranX, which further improved the code generation framework in (Yin and Neubig 2017) by replacing the context-free grammar used to generate action sequences into ASDL grammars and expand the framework into a wider range of languages including regular expressions, Python3 and SQL.

In this paper we perform neural language models in GRU and Transformer in our experiment. Our Transformer language model follows the architecture of GPT and GPT-2 (Radford et al. 2018, 2019):

Where $C$ is the code context, $W_{e}$ is the token embedding matrix and $W_{p}$ is the position embedding matrix. The hyperparameters of our model are listed in Table 1. We train the model like traditional language models and maximize the log-likelihood of:

Where $a_{t}$ is the token at timestep $t$ in the input program. We do not follow the training procedure in GPT-like models (Radford et al. 2018, 2019) which cut input sequences into equal length. Instead, we perform traditional batched training with padding. We assume that splitting action sequences will destroy the syntactical dependencies within a program file, so we keep the input sequences intact in our experiment. Accordingly, as the length of input sequences greatly varies, instead of applying learned position embeddings, we apply the sinusoidal position embedding in the original Transformer (Vaswani et al. 2017). During inference, we apply beam search to keep candidate sequences with the highest probabilities.

To prepare the action sequence for our full-line code completion task, we need to mark the end of each line in order to terminate the generation after a full line is completed. To achieve this, we manually add an end of line token ’$<$eol$>$’ after each line in a source code file.

Among all types of code tokens, we take an additional step to handle tokens with string type. The contents of strings vary drastically among different programs and often have little relevance to its context, so it is nearly impossible for a language model to suggest an accurate string. Besides, suggesting a wrong string to programmers usually have a negative effect on the user experience. So we mask out all the strings in our data during experiments by replacing all strings in our datasets with a unified token ’$<$str$>$’.

In order to make sure the generated code line is syntactically correct, a promising approach is converting the generation procedure of a line into generating its partial AST. In this paper, we adopt the parser of TranX (Yin and Neubig 2018) which can decompose an AST into a sequence of tree-constructing actions following an abstract syntax description language (ASDL) (Wang et al. 1997) grammar.

An ASDL grammar can be seen as an extension of traditional context-free grammar (CFG). Figure 2 shows a typical example of a production rule in the ASDL grammar of Python. Similar to CFG, the values on the right side of an ASDL production are the children of the value on the left. An ASDL grammar has two basic constructs: types and constructors. For example, in Figure 2 a value of type expr can be constructed by a Call constructor. Some constructors have a sequence of fields that describe the type of values associated with a constructor. In this example, the Call constructor denotes function call expressions, and has five fields: func, args, keywords, starargs and kwargs. Each field in the constructor also has a type that specifies the type of value the field can hold. Apart from the type information, each field also has a qualifier (single, optional ? and sequential $*$), which specifies the number of children the field can hold. For example, in Figure 2 The func field can only contain one value, and field args can contain an arbitrary number of values.

An AST is generated in top-down, left-to-right order. The action sequence is composed of three types of actions:

• •

  APPLYRULE: apply a production rule from the programming language grammar to expand a non-terminal AST node.

• •

  GENTOKEN: generate an exact value for a terminal node, i.e., variable, constant, API call, etc.

• •

  REDUCE: a REDUCE action marks the completion of the generation of children for a field with optional (?) or multiple ($*$) qualifier.

With these three types of actions, a Python code snippet can be converted into an action sequence and back into source code unambiguously. Figure 3 shows an example of converting a Python statement to an action sequence. We can train and evaluate neural language models on action sequences similar to source code token sequences.

During each timestep of generating the next code line, tranX will inspect the already generated actions and select a set of valid actions at the current timestep. Before applying the softmax function to predict the next action, we apply a mask on the hidden state of the language model to set the positions of all invalid actions to 0. This ensures that the generated action sequence can always be converted back to source code.

A problem of converting AST to action sequence is for some code lines like function declaration or for/while iterators, their syntax is not complete thus cannot be parsed into ASTs. In the inference stage, if the model generates the action sequence for these statements, the tranX parser cannot convert them back to source code. When we counter these situations, we manually add the action sequence of a pass statement after the generated sequence. Then we can convert the modified sequence back to source code and remove the added pass statement to get the final output code.

We evaluate our approach on two public Python datasets crawled from Github repositories. The first one, Py150 (Raychev, Bielik, and Vechev 2016) contains 150,000 Python2 files, split in to a training set of 100,000 files and test set of 50,000 files. In our experiments, we take 10% of the training files as the validation set. The second dataset PyCodeSuggest (Bhoopchand et al. 2016) consists of 949 projects compatible with Python3. We create our experiment data by removing python files with action sequences longer than the maximum input length 1500 for both datasets. We list the detailed information of tokens and actions of two datasets in Table 2. We can see that program files in Py150 contain more lines, while the code lines in PyCodeSuggest are usually longer than those in Py150. For both datasets, converting source code tokens to action sequences increases the average length of code lines.

We use the following metrics to evaluate the performance of our approaches:

• •

  Accuracy: We compare the exact matching accuracy between the generated statement and the ground truth. We list the accuracy of top-1 and top-5 candidates in our paper. We further calculate the accuracy when neglecting identifier names to measure the ability to generate correct statement structures for our models.

• •

  Mean reciprocal rank (MRR): we calculate MRR from the top-5 candidates of every test sample. We use it to measure the ability to give the correct sequence a high rank, which is similar to the real scenario of code completion, where developers are given a group of suggestions.

• •

  BLEU (Papineni et al. 2002): BLEU measures the precision of N-grams, so we use it to measure the similarity between the target statement and the generated statement.

• •

  Edit similarity: if the suggested code line is not precisely correct, developers want to make as few edits as possible to correct the code line. The character-level edit similarity of the predicted output $\hat{y}$ and the target output $y$ is computed by:

  $$sim=1-\frac{lev(\hat{y},y)}{|y|+|\hat{y}|}$$

  (7)

  Here $lev()$ is the Levenshtein distance (edit distance) and $\left|\cdot\right|$ is the length (number of characters) of the sequence.

We evaluate the following models on our datasets:

• •

  BPE-NLM (Karampatsis et al. 2020): a GRU language model for code completion using BPE to split source code tokens. This approach achieved state-of-the-art results on code completion tasks in multiple programming languages.

• •

  Language models: we use Transformer and GRU language models on source code token sequences or ASDL action sequences. In order to analyze the effectiveness of byte-pair encoding, we also run Transformer language models on BPE subtokens.

We have also attempted to apply encoder-decoder models for this task, i.e., using an encoder to encode the program context and a decoder to generate the target statement. However, for encoder-decoder models, we have to create separate training samples for each statement in the code files, which tremendously increase the size of the training set, making the training time unacceptable.

There also exists a group of researches on code completion by predicting the next AST node in the flattened sequence of ASTs (Raychev, Bielik, and Vechev 2016; Li et al. 2018; Liu et al. 2019). Our goal is to recommend a line of code to developers, while a sequence of AST nodes cannot always be transferred into source code. So these approaches are not suitable for full-line code completion, and we do not evaluate them in our experiments.

In each test sample, the input is the first $k$ lines of a Python file, and the target output is the $k+1$th line. So for a Python file of $N$ lines, we can create $N-1$ test samples. We remove test samples whose target is an Import statement or longer than 100 tokens. We exclude Import because they are often irrelevant to the previous code context. For code statements longer than 100 tokens, we find out these statements are often the definition of large lists or dictionaries, which are incapable for neural language models to complete.

For token-based and syntax-based approaches, we set the vocabulary size to 80,000. For BPE-based approaches, we set the number of merge operations to 30,000. The hidden size of GRU models is 512. The batch size is 8 for GRU and 4 for Transformer models, since larger batches cannot be fed once into the memory. We use the Adam optimizer (Kingma and Ba 2015) to train all models. We implement our models in PyTorch (Paszke et al. 2019) and run our experiments on a NVIDIA Tesla V100 GPUs with 16GB memory.

Table 3 and Table 4 show the results of all models on the two datasets. Results on all metrics are reported in percentage (%). We can see that in all experiment settings, Transformer models outperform GRU models on all evaluation metrics. A somewhat unexpected finding is that syntax-based approaches do not outperform token sequence-based ones, and even perform worse on Py150. We assume this is caused by the differences in sequence length between these two types of approaches. From Table 2, we can clearly figure out that the action sequence for a Python program is often longer than its source code token sequence, which brings an extra burden to language models. The main advantage of ASDL action sequences over source code tokens is that an action sequence can be necessarily converted to a syntactically correct code snippet. This is important for NL-based code generation tasks like Django (Oda et al. 2015) or CoNaLa (Yin et al. 2018) since in these tasks, the source code corpus is small-scaled and each code sample is short. However, in large-scale real-world corpora with file-level code snippets, neural language models are capable of learning program grammar from data, so the effect of explicit syntax restrictions becomes undermined. We manually inspected the statements generated by TransformerLM+token, and nearly all of them are syntactically correct. Also, we must notice that currently, our syntax guidance is still very coarse for code completion. First, we do not augment our language models with syntactical dependencies like AST parent-child connections. The neural language models are still purely sequential. Second, the ASDL parser in our experiments only guarantee that generated code lines can be parsed into ASTs, while in the real scenario of code completion, the restriction of outputs is much stronger, including restriction on variable usage, API calls, and arguments, etc. A promising way of applying these restrictions is to leverage powerful static analysis tools. Static analysis can be applied to source code tokens, which relieves language models from learning on longer ASDL action sequences.

Another phenomenon is that language models with BPE outperform token-level language models on accuracy without identifiers but achieved similar or lower results than token-level models on accuracy with identifiers. This implies that BPE can mitigate the out-of-vocabulary problem to a certain extent, but for some identifiers, token-based models can generate them with only one step, while in BPE, they are separated to subtokens, which increase the difficulty of generating them.

We also make an evaluation of the time efficiency of our models. Table 5 compare the average time consuming for inferencing a whole line of code for all models. We report the time cost when the beam size is set to 5. Although all models have acceptable time efficiency, the inference speed of syntax-based models are much slower than token-based or BPE subtoken-based models. This shows that masking out invalid actions with an ASDL parser is much more time consuming than predicting a code element with neural language models. From our experiments, we believe that in order to keep a high time efficiency for full-line code completion, our model should be based on source code tokens. We need to explore the possibility of adding grammatical constraints to source token sequences.