# Neural Machine Translation for Code Generation

Dharma KC
University of Arizona
<EMAIL_ADDRESS>&Clayton T. Morrison
University of Arizona
<EMAIL_ADDRESS>
###### Abstract

Neural machine translation (NMT) methods developed for natural language
processing have been shown to be highly successful in automating translation
from one natural language to another. Recently, these NMT methods have been
adapted to the generation of program code. In _NMT for code generation_ , the
task is to generate output source code that satisfies constraints expressed in
the input. In the literature, a variety of different input scenarios have been
explored, including generating code based on natural language description,
lower-level representations such as binary or assembly (neural decompilation),
partial representations of source code (code completion and repair), and
source code in another language (code translation). In this paper we survey
the NMT for code generation literature, cataloging the variety of methods that
have been explored according to input and output representations, model
architectures, optimization techniques used, data sets, and evaluation
methods. We discuss the limitations of existing methods and future research
directions.

##  1 Introduction

Neural machine translation (NMT) has been widely used in natural language
processing, where the task is to translate sentences in one language to
sentences in another language (such as from English to German). Most NMT
frameworks follow an Encoder-Decoder architecture pioneered by Sutskever et
al. [162]. In this architecture, input sequences of tokens (representing words
or characters in the source language) are input to an encoder neural network
that computes an internal representation, and then a decoder neural network
takes that internal representation and decodes it into an output sequence of
tokens corresponding to the target language. Recent work has begun to explore
applying this and related ideas to the task of generating source code, leading
to a new sub-field of NMT for code generation. This is now an active and
rapidly evolving area of research with many applications [6, 101, 69]. For
example, code generation from natural language can help novice developers to
write code and seasoned programmers to work more efficiently [108, 10]. In so-
called neural decompilation, NMT for code generation has been applied to
translate from assembly or binary to source code. This in turn can help
security researchers with malware identification, understanding the
functionality of programs, program comparison, and more [57, 109]. Code
generation from partial source code can help in program completion, repair,
and providing automated feedback [19, 40]. And finally, in the setting
directly analogous to NMT for natural language translation, NMT methods can be
used to translate from source code in one programming language to another
[33]. In the literature, researchers are using various methods in each of
these application domains, but in general, the field is evolving very fast,
with important results being siloed within particular application communities,
and important insights that might transfer to other application is challenging
to track. Summarizing these papers based on the methods and ideas they use and
identifying their limitations is important to inform the development of new
architectures and solutions. In the survey presented here, we develop several
dimensions along which to distinguish the various approaches. One natural
dimension is to consider the class of neural network architecture that is
used; this includes variants of recurrent neural networks (RNNs), transformers
and large language models (LLMs), tree decoders, graph neural networks (GNNs),
neurosymbolic methods, and incorporation of reinforcement learning (RL). We
consider each in terms of their advantages and limitations. Along another
dimension, we characterize the approaches according to the output
representation they generate: sequence or graph (abstract syntax tree (AST))
with advantages and limitations of each of the methods. We hope the contents
of this paper will be useful for new researchers to get an overview of the
field, and for experts to design new architectures and solutions suitable for
their tasks and requirements. When the boundary between methods is not clear
or when papers use hybrid methods, we have grouped them based on their major
component.

Program Synthesis: foundations and trends [69] provides a detailed analysis of
traditional methods such as inductive program synthesis (enumerative search or
sketch-based solutions [155]), and deductive program synthesis techniques.
Deductive program synthesis works by translating the descriptions from formal
language (specifications) to the source code using theorem prover to find a
proof that satisfies all the constraints and extracts the program from the
proofs [63, 121]. Thus, it requires explicit program descriptions in the
formal language to start with. Inductive methods [68] can generate source code
from input-output example pairs, but they perform a search over all the
language rules and are hard to scale to real-world source code generation.
They mostly work with domain-specific languages (DSLs) with few rules compared
to the grammar of general programming languages such as C, C++, and Python.
Existing survey papers [6, 101] also provide a survey of probabilistic
methods, domain-specific language (DSL) guided models, and n-gram language
models [76] along with applications of machine learning techniques on code
such as code summarization, bug fixing, and more. Recent paper [101] covers
deep learning-based methods for source code generation but does not cover the
latest techniques like RL-based methods, papers from the neural decompilation
domain, recent large language models like Codex and AlphaCode, and code
representation techniques. Another line of work popular for program synthesis
is based on differentiable interpreters. Differential interpreter based
methods [23, 113, 61, 97, 88, 142, 62] generate source code from input output
examples. They define a differentiable mapping from inputs and source code to
the outputs and use gradient descent to search for the best program that
satisfies the constraints. The major disadvantage of differentiable
interpreter-based methods is that each problem is solved independently, and
existing methods based on this idea do not yet scale to code generation in a
general programming language such as C, C++, and Python. We do not cover
methods that do not yet scale to code generation in general programming
languages such as C, C++, and Python and suggest our readers look into survey
papers. Semantic parsing and code generation are quite related tasks where the
ideas from one field can be transferred to another, we refer our readers to
this survey paper [103] on semantic parsing and code generation. Similarly,
[186] is more focused on code understanding while we focus on code generation.

This survey paper is organized as follows: section overview[2] provides brief
overview of the components used by NMT based algorithms, section NMT [3]
introduces neural machine translation framework followed by methods used in
NLP for language translation that serve as a basis for current code generation
techniques, section NMT4Code [4] provides description of methods used by
existing code generation papers, section copy mechanism [refsection:copy]
introduces copy mechanism that will help the NMT models to copy some tokens
from the input sequence to the output sequence, section representation
learning [6] provides current representation learning techniques, section
datasets [8] provides a list of datasets being used for source code
generation, section evaluation [9] provides evaluation techniques, section
open problems [7] provides open problems and future research directions.
Finally, in section conclusion [10] we conclude our paper.

##  2 Overview

In this section, we provide a summary of the important components used by
these code generation papers.

###  2.1 Recurrent neural networks (RNNs)

Recurrent neural networks [146, 87, 154] are the extension of feedforward
models for learning from a sequence. At any time step $t$, given the current
input token ($x_{t}$) and previous hidden state ($x_{t-1}$), the RNN unit
produces a hidden state ($h_{t}$: summary of the sequence up to current time
step) along with some output ($o_{t}$). We can model $o_{t}$ and $h_{t}$ with
following equations:

$\displaystyle h_{t}$ $\displaystyle=tanh(W_{i}*x_{t}+W_{h}*h_{t-1})$ (1)
$\displaystyle o_{t}$ $\displaystyle=W_{o}*h_{t}$ (2)

Given a sequence of words ($x_{1},x_{2},...,x_{t})$, RNN works in a sequential
fashion producing output ($o_{t}$) and hidden state ($h_{t}$) at each time
step $t$. The advantage of RNN is that it can handle a sequence of any length.
The disadvantage of RNN is that it can not handle long-range dependencies, and
is hard to train because of the vanishing gradient problem [133, 77]. Long
short-term memory (LSTM) [78] and gated recurrent units (GRUs) [35] are the
variations of RNNs with a gated mechanism with two states: hidden state for
short-term memory and cell state for long term memory, and are shown to handle
long-range dependencies better than vanilla RNNs. We can use RNNs and their
variants to generate the representation for sequential data like a sequence of
source code, a linearized form of the abstract syntax tree (AST), or a natural
language description of the source code.

###  2.2 Transformer and large language models (LLMs)

Transformer [173] removes the sequential encoding mechanism of RNNs and
instead encodes tokens in feedforward networks with multi-headed dot product
attention layers. The advantage of transformers is that they can handle long-
range dependencies better than RNNs and are easy to parallelize. Given, query
($Q$), value ($V$), and key ($K$) vectors, The attention is then calculated as
follows:

$\displaystyle MultiHeadAttention(Q,K,V)$
$\displaystyle=concat([head_{1},head_{2},....,head_{k}]W_{0}$ (3)
$\displaystyle head_{i}$
$\displaystyle=Attention(QW_{i}^{Q},KW_{i}^{K},VW_{i}^{V})$ (4) $\displaystyle
Attention(Q,K,V)$ $\displaystyle=softmax(\frac{QK^{T}}{\sqrt{d_{k}}})V$ (5)

Where $\sqrt{d_{k}}$ is the scaling factor equal to the feature vector
dimension. The input is transformed into a key, query, and value vector using
a linear operator and the attention is calculated using multiple heads as
shown by the above equations. The feature vector for a query token is updated
with the linear combination of the feature vector of other tokens. This
feature vector then goes through another feedforward layer with a residual
connection and this process is repeated. Given that the source code has long-
range dependencies [101] and transformers can handle long-range dependencies,
transformers are important architecture for source code generation. Large
language models based on Transformer-like GPT-3 [25] and BERT [41] have
dominated the field of NLP for sequence generation and representation learning
respectively, and are being used increasingly for code generation [179, 53].
We can use transformers or LLMs to generate the sequential representation of
the source code, or the linearized form of the abstract syntax tree (AST).

###  2.3 TreeDecoder

Tree decoding-based methods such as Tree-to-Tree translation [33] generate a
tree by decoding a node at a time with some tree traversal algorithms such as
depth-first search (DFS) or breadth-first search (BFS). Tree-based decoders
generally use attention [12] over the input sequence to generate a new node.
Tree-based decoders also use parent feeding (using the hidden state of the
parent) [33] to improve the decoding of a new node. The system can be extended
to attend to the partially generated tree along with attention to the input
sequence. The core components of these decoders are RNNs (LSTMs, and GRUs).
For example, Tree-to-Tree [33] uses two LSTMs, one for the left child and
another for the right child prediction. Most of the tree decoder-based code
generation methods first generate an abstract syntax tree (AST) that can then
be converted into the source code.

###  2.4 GNNs

Graph neural networks [187, 92, 174, 43] are quite powerful methods for graph-
structured prediction and learning. Most of them work on the principle of
message passing where a node gets some information about its neighbors and
updates its state. Let’s consider our partial AST as a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of
nodes and $\mathcal{E}$ is the set of edges. Let,
$\mathcal{X}\in\mathbb{R}^{|v|*d}$ be the set of node features where each node
$v\in\mathcal{V}$ has a $d$ dimensional feature. The $k^{th}$ message passing
iteration of a GNN can be modeled as a variation of the following equation
[73]:

$\displaystyle h_{v}^{(k+1)}$
$\displaystyle=\texttt{update}^{(k)}(h_{v}^{(k)},\texttt{aggregate}^{(k)}(h_{u}^{(k)},\quad\forall
u\in\mathcal{N}(v))$ (6)
$\displaystyle=\texttt{update}^{(k)}(h_{v}^{(k)},\boldsymbol{m}_{\mathcal{N}(v)}^{(k)})$
(7)

Where $\mathcal{N}(v)$ denotes the neighbors of node $v$. At any iteration of
the GNN, the aggregate function takes the embedding of the neighbors of the
node $v$ and combines them into one embedding vector. The update function
takes the embedding of the node $v$ at the previous time-step and the output
embedding vector of the aggregate function to give us a new embedding for the
node $v$. Here, update and aggregate can be any differentiable functions.
Given that the aggregate function takes a set of inputs, GNNs defined this way
are permutation invariant. Moreover, the equations can be easily modified to
include edge embedding vector information if available. Note that the one
iteration of the GNN collects information from the first-hop neighborhood. If
we want to collect information from the k hop neighborhood, we can run the GNN
k times [k layers]. We can use GNNs to generate the tree representation of the
source code namely abstract syntax tree (AST).

###  2.5 Neurosymbolic

Neurosymbolic methods [59, 28] are methods that combine neural networks with
symbolic logic. In this survey paper, we include papers that have a neural
component and a symbolic component such as DeepCoder [13] and DreamCoder [49]
as neurosymbolic methods. Another paradigm of neurosymbolic methods generates
a program $P$ that when applied to the input produces the desired output. For
example, Fix Bugs with Transformer through a Neural-Symbolic Edit Grammar [80]
uses transformers [173] and pointer networks [175] to predict a sequence of
edit grammar rules (DSL rules such as insert and delete from a location).
Let’s call these sequences of actions a program ($P$). This program ($P$) when
applied to the buggy source code ($x$), outputs the bug-free program ($y$).
The advantage of neurosymbolic methods is that the DSL rules are humanly
interpretable, and also the method can generalize better at extrapolation than
compared to neural-only approaches. The neurosymbolic methods are divided into
multiple groups based on their major component whether it is a neural or
symbolic module [59]. The more symbolic components the method uses, the more
interpretable it is but harder to scale to large code generation problems.

###  2.6 RL

All of the above methods do not take advantage of the unit tests and compiler
error messages as these are non-differentiable. Algorithms such as REINFORCE
[185] can be used to train the system from such non-differentiable values.
Reinforcement learning-based methods convert the results of unit tests and
compiler output to reward values and mostly use policy gradient methods [163,
42] to train the network based on these signals [100]. Once we have a
mechanism to calculate reward based on these signals, we can use it as a loss
function where our objective is to maximize the total reward. Thus the loss
becomes:

loss_rl $\displaystyle=-\mathbb{E}_{\hat{y}\sim P_{\theta}}[r(\hat{y})],$ (8)

where $\hat{y}=[\hat{y_{1}},...\hat{y_{T}}]$ is the sequence generated by the
model (transformer, GNN, etc), $P_{\theta}$ and $r(\hat{y})$ is the reward for
that given generated sequence. Then we can estimate the gradient of the non-
differentiable reward function as follows:

$\displaystyle\nabla_{\theta}\texttt{loss\\_rl}$
$\displaystyle\approx-\mathbb{E}_{\hat{y}\sim
p_{\theta}}[r(\hat{y})*\nabla_{\theta}logp_{\theta}(\hat{y}|\boldsymbol{x})]$
(9) $\displaystyle\approx-\mathbb{E}_{\hat{y}\sim
p_{\theta}}[r(\hat{y})*\sum_{t}\nabla_{\theta}logp_{\theta}(\hat{y_{t}}|\hat{y_{1}},...,\hat{y_{t-1}},\boldsymbol{x})],$
(10)

where $\hat{y}$ is the output sequence generated by the model from the input
sequence $\boldsymbol{x}$ and $\hat{y_{t}}$ is the token predicted in a
sequence at time step $t$.

##  3 Neural Machine Translation: NMT

In this section, we provide a mathematical framework for the neural machine
translation system. We then describe important papers and ideas that are
important for the NMT-based code generation systems. These translation systems
generally follow a mathematical framework described below. Mostly, they assume
to have a parallel corpus for training the model which contains paired input
and output sequences. Let the input be $\boldsymbol{x}$ which contains a
sequence of tokens $x_{1},x_{2},x_{3},...,x_{n}$. Let the ground truth target
for the input sequence $\boldsymbol{x}$ be $\boldsymbol{y}$ which contains a
sequence of output tokens $y_{1},y_{2},y_{3},...,y_{m}$. Let the translation
framework be parameterized by $\theta$. Then the overall objective is to
maximize the conditional probability of $\boldsymbol{y}$ given
$\boldsymbol{x}$. Where $\hat{y_{i}}$ is the prediction of the token at time-
step $i$ and $y_{i}$ is the ground truth token at time-step $i$. As we can see
from the equation below, maximizing this conditional probability is equivalent
to minimizing the sum of cross-entropy loss at each time-step that can be
minimized using backpropagation through time (BPTT) [184]. For the language
translation tasks $\boldsymbol{x}$ is the input sentence in one language and
$\boldsymbol{y}$ is the output sentence in another language. For code
generation $\boldsymbol{y}$ is the source code, while $\boldsymbol{x}$ can be
any representation of the source code such as assembly code or the natural
explanation of the code. Most of the NMT models differ in how they calculate
$P(y_{i}|y_{<i},\boldsymbol{x};\theta)$. We can model
$P(y_{i}|y_{<i},\boldsymbol{x};\theta)$ using models such as RNNs,
transformers, tree decoders, or GNNs. For NMT models, $y_{i}$ is the ground
truth token at decoding step $i$. For tree decoder and GNN, $y_{i}$ is the
ground truth token at node $i$. Thus, for NMT models, the total loss of one
sample is the sum of cross-entropy loss at each time of the decoding step. For
the tree decoder and GNN model, the total loss is the sum of cross-entropy
loss at each node of the decoding step.

$\displaystyle P(\boldsymbol{y}|\boldsymbol{x};\theta)$
$\displaystyle=\operatorname*{arg\,max}_{\theta}P(y_{1},y_{2},y_{3},\
...,y_{m}|\boldsymbol{x};\theta)$
$\displaystyle=\operatorname*{arg\,max}_{\theta}P(y_{1}|\boldsymbol{x})*P(y_{2}|y_{1},\boldsymbol{x};\theta)\
*...*P(y_{m}|y_{m-1},...y_{1},\boldsymbol{x};\theta)\quad\because\texttt{chain
rule}$
$\displaystyle=\operatorname*{arg\,max}_{\theta}\prod_{i=1}^{m}P(y_{i}|y_{<i},\boldsymbol{x};\theta)\quad\texttt{where:
}y_{<i}=y_{1},...,y_{i-1}$ which is equivalent to maximizing the log
likelihood
$\displaystyle=\operatorname*{arg\,max}_{\theta}log\prod_{i=1}^{m}P(y_{i}|y_{<i},\boldsymbol{x};\theta)$
$\displaystyle=\operatorname*{arg\,max}_{\theta}\sum_{i=1}^{m}logP(y_{i}|y_{<i},\boldsymbol{x};\theta)$
which is equivalent to minimizing the negative log likelihood
$\displaystyle=\operatorname*{arg\,min}_{\theta}-\sum_{i=1}^{m}logP(y_{i}|y_{<i},\boldsymbol{x};\theta)$
$\displaystyle\texttt{let
}P(y_{i}|y_{<i},\boldsymbol{x};\theta)\sim\texttt{Categorical(p)}$ then, using
the pmf of a categorical distribution
$\displaystyle=\operatorname*{arg\,min}_{\theta}-\sum_{i=1}^{m}log\prod_{k=1}^{K}p_{k}^{\mathbbm{I(\hat{y}=k)}}$
$\displaystyle=\operatorname*{arg\,min}_{\theta}\sum_{i=1}^{m}\sum_{k=1}^{K}-logp_{k}^{\mathbbm{I(\hat{y}=k)}}$
$\displaystyle=\operatorname*{arg\,min}_{\theta}\sum_{i=1}^{m}-y_{i}*logp(\hat{y_{i}})$

Here, Categorical(p) is the categorical distribution over the output
vocabulary. All of these models try to maximize the likelihood of the next
token given tokens generated till now. Thus, the generated tokens may not be
syntactically correct. Some of the neurosymbolic methods often put a
constraint on the grammar of the output language at each token prediction
step, such that the output is always syntactically correct [192].In the
following section, we summarize important papers that build the foundation for
current NMT techniques for source code generation.

###  3.1 Sequence to Sequence Learning with Neural Networks

Sequence-to-sequence networks (Encoder-Decoder architecture) proposed by [162]
is one of the most widely used frameworks for neural machine translation. The
following figure shows their architecture where $sos$ denotes the start of the
sequence token, and $eos$ denotes the end of the sequence token. The $h_{t}$
denotes the hidden state of the LSTM at time step $t$. EMB-E denotes the
embedding layer for the encoder and EMB-D denotes the embedding layer for the
decoder. LIN denotes the linear layer that transforms the output hidden state
of the decoder into the output word probabilities. The $z$ is the context
vector from the final time step of the encoder that captures all the
information about the input sequence and is passed to the decoder to make the
prediction.

Figure 1: Sequence to sequence learning

At a single time step, the LSTM takes the embedding vector of input $x_{t}$
and its previous hidden state $h_{t-1}$ to have its current hidden state
$h_{t}$. The main problem with this mechanism is that it needs to squash all
the information about the input sequence into the single context vector $z$,
which quickly becomes a bottleneck for longer sequences. The implications for
the code generation are that: although this is a good baseline method, it is
not that robust at handling long-range dependencies that are frequent in the
code generation task.

###  3.2 Neural Machine Translation by Jointly Learning To Align And Translate

The architecture of this sequence to sequence with attention [12] is similar
to the above sequence to sequence architecture (encoder-decoder) [162] with
the following differences: first, the input token representation (embedding)
at each time step ($h_{t}$) combines the representation (embedding) of a word
calculated using the context from both sides of the word. The context from the
left side ($h_{t}^{\rightarrow}$) is calculated using a GRU [35] that takes
tokens from the input sequence from the left to the right manner. The context
from the right side ($h_{t}^{\leftarrow}$) is calculated using a GRU [35] that
takes tokens from the input sequence from the right to the left manner.
Finally, these two representations: ($h_{t}^{\rightarrow}$) and
($h_{t}^{\leftarrow}$) are concatenated to get the representation of a word.
This helps the model to capture the context of a word from both sides. Second,
it reduces the bottleneck problem of previous architecture using an attention
mechanism. This architecture lets the model look at the hidden representation
of all the time steps of the input sequence while decoding $\hat{y_{t}}$. Thus
the model doesn’t need to compress all the information into the context vector
$z$. At every decoding step $\hat{y_{t}}$, this model takes the previous
prediction $\hat{y_{t-1}}$ and a vector $c_{i}$. The context vector $c_{i}$ is
different for every decoding step. First, it calculates the $\alpha$ values,
which are the weight (scalar) the model should give to the input word, i.e.
$\alpha_{t,1}$ denotes the weight the model should give to the input word
$x_{1}$ while decoding $y_{t}$. Then the final context vector $c_{i}$ is
calculated as follows:

$\displaystyle c_{i}$ $\displaystyle=\sum_{j=1}^{T}\alpha_{i,j}h_{j}$ (11)

Where $h_{j}=h_{j}^{\rightarrow};h_{j}^{\leftarrow}$ and ; denotes the
concatenation operator. They use a multi-layer perceptron (MLP) to calculate
the weight $\alpha_{i,j}$. These weights are then converted to a [0, 1] range
using a softmax function. The implications for the code generation are that:
the attention mechanism helps this model to handle long-range dependencies
compared to the previous architecture.

###  3.3 Attention Is All You Need

The main problem with the previous two architectures [162, 12] is that they
are sequential, meaning they take one word at a time which increases training
time and is hard to parallelize. Transformer [173] solves this problem by
removing the recurrent neural network architecture that takes one token at a
time and using attention layers and fully connected layers that can take the
whole sequence at a time. Thus, the model is easy to parallelize across GPUs.
Moreover, it overcomes the vanishing gradient and exploding gradient problem
of the above two architectures as it does not have long chain multiplication
that occurs in backpropagation through time (BPTT). We can see the multi-head
attention as generating a contextualized embedding of the input token. As the
model takes the whole sequence at a time as the input, it does not preserve
the sequential nature of the input and output. They use positional encoding to
solve this problem where the embedding of the input word is added to the
embedding of the position it occurs in. The implication for the code
generation is that: it can handle long-term dependencies more easily than the
previous two architectures because each input token is connected to another
through a multi-head attention unit. The major disadvantage of this model is
that the run time complexity and memory complexity of the system grows
quadratic with respect to input length. This can be a big issue for code
generation as the input to the code generation (such as assembly) can be quite
huge. In such cases, methods that improve this complexity to linear such as
BigBird [196], and LongFormer [16] can provide a good alternative solution.
Moreover, making the attention mechanism IO aware and sparse [38] is another
alternative direction for handling long-range sequences.

Following table 1 shows complexity analysis for a single decoding step of the
decoder with respect to the length of the input sequence (n).

Table 1: Comparison between NMT Models

Model | run-time complexity | memory complexity | path length | easy to parallelize
---|---|---|---|---
Seq2Seq | $O(n)$ | $O(1)$ | $O(n)$ | $\times$
Attention | $O(n)$ | $O(n)$ | $O(n)$ | $\times$
Transformer | $O(n^{2})$ | $O(n^{2})$ | $O(1)$ | $\checkmark$

Moreover, state space models [64, 66, 65, 39] are getting popular at handling
long-range dependencies better than transformer architecture and exploring
this direction for code generation is an interesting and exciting research
direction.

###  3.4 Towards String-to-Tree Neural Machine Translation

This paper [2] injects syntactic knowledge about the target language into the
model by translating the target sequence into a constituency tree. They
linearize this tree into a sequence and use sequence to sequence with
attention [12] to generate the target sequence. They show that this improves
the prediction and alignment between the input sequence and target sequence
compared to direct output sequence prediction without syntactic knowledge. The
implications of this for code generation are that: we can convert the source
code to an abstract syntax tree (AST) that contains syntactic information and
try to predict this AST instead of the source code to get a better model.
Direct tree prediction is hard to parallelize, but the linearization step
allows us to use the sequence to sequence models such as transformers [173] to
make a prediction, and it is easy to parallelize. Moreover, there are an
increasing number of papers that try to inject syntactic knowledge by
pretraining on ASTs [177], and semantic knowledge by pretraining on data flow
graphs [70]. The model that can capture the syntactic structure and semantic
structure of the code is better than the one that doesn’t.

###  3.5 Tokenization

Tokenization of the source code is an important component of neural machine
translation for source code generation. Developers come up with new words all
the time for naming their variables, and functions, thus increasing the output
vocabulary size. The complexity of training and decoding the NMT-based system
increases with output vocabulary size [84]. The tokenization of the source
code or natural language can be grouped into the following high-level groups:

####  3.5.1 word-based tokenization:

Word-based tokenization tokenizes the source code or the natural language
based on the complete words for frequent words and uses the "<unk>" (unknown)
token for rare words. But this degrades the quality of translation if the
number of unknown words increases [12]. Given that the source code has really
long tail distribution [101], it is important to take care of these tokens.
There are multiple solutions to this problem in the literature, for example,
[118] perform alignment of the "<unk>" token with the input sequence and
replaces the "<unk>" token with the aligned word from the input sequence. In
the case of source code, another possible solution is to replace variables
with specific tokens like "var0, var1, …" (and the same for functions). This
is a good solution to reduce the size of output vocabulary, but it makes the
generated code unreadable. In summary, this word-based tokenization increases
vocabulary size and is problematic for open vocabulary learning. An increase
in vocabulary size increases time complexity and memory requirement for NMT-
based solutions.

####  3.5.2 Character-based tokenization:

Character level encoding [36, 112] uses a single character as a token. The
advantage of the character level tokenization is that the output vocabulary is
small, but it increases the sequence length by a large amount that is hard to
predict for an NMT model. Moreover, it is hard to learn the semantic
representation of a character (’c’) compared to a word (’computer’). Thus,
this is good for reducing the vocabulary size but it makes the model harder to
converge as it increases the sequence length by a large amount.

####  3.5.3 Subword-based tokenization:

A hybrid solution between character-level tokenization and word-level
tokenization is sub-word-based tokenization. It is based on the idea that
frequent words should be tokenized as words and rare words should be tokenized
as meaningful sub-words. This is interesting in the case of source code
because developers often generate new names using camel-case and snake-case
which are quite rare and this technique allows us to split these new words
into constituent meaningful sub-words. This allows the sub-word-based
tokenization to have a smaller vocabulary and still can learn meaningful
representations. There are multiple ways of doing sub-word tokenization such
as byte pair encoding (BPE) [150], WordPiece [147], and SentencePiece [95].
Also, source code contains large numerical values and tokenizing each number
separately is not possible. In such cases, it is better to tokenize these
numbers into a sequence of digits [90].

We refer to [122, 159, 180, 138] for more analysis on tokenization techniques.

###  3.6 Data Augmentation:

Data augmentation is an important technique to improve the generalization of
deep neural networks [153]. Several techniques such as rotation, flip, random
crop, etc exist for data augmentation in computer vision domain [153]. Several
techniques such as random addition, random deletion, synonym replacement, etc
exist for NLP domain [52]. We can apply some of the data augmentation
techniques from NLP for source code generation. Recently, Neutron tried data
augmentation techniques such as random masking and show impressive performance
improvement from data augmentation. Moreover, Exploring Data Augmentation for
Code Generation Tasks [31] experiments with data augmentation techniques for
source code generation such as using monolingual data using back translation
[149, 37], improving numeric awareness and shows improvement in the code
generation. But, the research on data augmentation techniques for code
generation is still nascent and is an important research direction.

###  3.7 Decoding strategy

Most of the NMT-based solutions generate source code in an auto-regressive
fashion. The next token is predicted based on the maximum likelihood of the
token given the input sequence and already generated tokens. It has been shown
that this greedy approach has multiple problems such as degenerate solutions
[182] and lacking semantic consistency [15]. The greedy approach is
computationally efficient and is the optimal choice for the current time step,
but when we generate the full sequence, it may be a sub-optimal choice.
Another option would be to store every prediction at every decoding step and
explore all possible sequences (exhaustive search) from these predictions,
this will give us the correct sequence, but this will lead us to an
exponential algorithm. The beam search decoding stands in the middle of these
two extremes by keeping a fixed number of sequences at each time step based on
their joint probability. Thus, it provides a good compromise between accuracy
and computational cost. The implication of this for code generation is that:
beam search is a powerful method that can improve the accuracy of the source
code generation models. Beam search keeps a fixed (beam size) number of
predictions at each time step, but beam search with adaptive size could even
improve results even better [55]. Moreover, beam search can be extended to
generate syntactically correct source code with some computational cost. These
maximization-based methods (greedy and beam search) have been shown to
generate solutions with undesirable repetition [51] in the field of NLP.
Recently, [48] have shown that sequential monte carlo (SMC) with some value
function performs better than beam search for the graphics program generation
from images. Sequential monte carlo keeps $K$ number of particles (programs)
and re-weights them on some value function. One disadvantage of SMC is that it
is more computationally expensive than beam search. Another set of methods
that are frequently used for decoding is stochastic methods like top-k
sampling [51], and nucleus sampling [79]. These stochastic methods are shown
to produce semantically inconsistent text with prefix [157] in the field of
NLP. Another line of decoding strategy is to use another model as a ranker.
For example, LEVER: Learning to Verify Language-to-Code Generation with
Execution [126] reranks the generated programs based on LM based ranker or
verifier that takes the input description, sampled code and execution results
and shows improved results. Coder Reviewer Reranking for Code Generation [201]
samples multiple solutions using temperature parameter and uses two models:
coder model that evaluates $p(y|x)$ and reviewer mode that evaluates $p(x|y)$
and uses the product of these two scores to select the generated program. They
show impressive results and claim state-of-the-art results. Recently,
contrastive search-based decoding strategies [157, 156] have shown to be a
good decoding strategy for neural text generation. But, their research on
source code generation is limited and is an important research direction.
NeuroLogic Decoding [116] introduces logical constraints during decoding for
text generation. NeuroLogic $A^{*}$ [117] decoding extends neurologic decoding
with lookahead heuristics to generate a text that satisfies the constraints.
Similar techniques may be useful for code generation under constraints.
Recently, Planning With Large Language Models for Code Generation [199]
propose planning guided transformer decoding where the idea is to use
pretrained model to generate complete sequence from a given token (lookahead
search) and evaluate it using test cases. This method generated better
programs but is computationally expensive.

##  4 Neural Machine Translation for Code: NMT4Code

In this section, we summarize papers that use neural machine translation for
code generation based on the output representation produced by these methods
and the methods they use for code generation. These papers can be summarized
into two groups namely _Sequence_ and _Graph_ based on the output
representation they produce for the source code.

Sequence methods represent the output source code in a sequential
representation. This sequential representation can be either a sequential form
of the original source code or the linearized form of the AST representation
of the source code. The advantage of sequential representation is that we can
use sequence-to-sequence models [162, 12, 173] in their raw form for the
generation of the source code.

###  4.1 SourceCode

These methods generate source code directly from the given input. They mostly
use RNN, LSTM, and Transformer techniques for the generation of the source
code. The advantage of generating source code directly instead of the AST is
that we don’t need a module to convert from AST to the source code. Another
advantage of direct source code generation is that the same method can be
easily transferred for source code generation in multiple languages. The
disadvantage of direct source code generation instead of AST generation is
that it doesn’t contain syntactic information explicitly, making it harder for
the model to learn them on its own, and also the representations learned are
more specific to the target language [8, 7]. In the following section, we
briefly summarize papers that generate source code based on the methods they
use.

####  4.1.1 RNNs

: These methods generate source code using recurrent neural networks (RNNs)
and their variants such as LSTM and GRU. The problem with RNN-based models is
that they can not handle long-range dependencies quite well. For example,
RNNDecompilation [90] generates C source code from binary sequence using RNNs.
They tokenize input binary sequences at the byte level. They do not use
existing disassemblers that are good at translating from input binary to
assembly, which can give good inductive bias for the neural network as it
contains richer semantics and structural information than binary sequence.
NeuralDecompilation [91] uses LSTM with attention to generate source code (C)
from input assembly representation. They use compiler feedback to retrain the
system with some additional data if most of the generated code does not
compile. This idea of using compiler feedback for improving the system (either
by retraining as done here or using them as reward signals in RL-based
systems) is an important research direction for compilable source code
generation. Neutron: [109] uses LSTM with attention model [119] to generate
source code (C) from assembly language. They first segment input assembly into
different blocks using an LSTM encoder and translate each unit thus generating
code fragments in a high-level language. They use data flow, and control flow
analysis of the input assembly to compose these code fragments into a
function. Moreover, they use feedback from the syntax checker and improve the
system further by retraining and using rule-based checkers as error correction
techniques. LPN: Latent Predictor Networks for Code Generation [113] tackles
the problem of source code generation in high-level languages like Python and
Java from input descriptions using a modified LSTM with attention [12]
mechanism. They propose a hybrid approach based on pointer networks [175] and
character RNNs (predictors). The model first selects the predictor (latent)
conditioned on input and uses that to either generate a character or copy from
the input. Thus the same network can generate characters and copy from the
input sequence at the same time. SynFix: Automated correction for syntax
errors in programming assignments using recurrent neural networks [19] uses
RNNs to fix syntax errors (e.g.missing bracket) in massive open online courses
(MOOCs) for buggy code using a model learned from a correct submission for the
given problem. They use a sequence model to predict token replacement or
insertion at the location provided by the compiler. As the compiler does not
always provide the correct location of the bug, DeepFix: Fixing Common C
Language Errors by Deep Learning [72] propose RNNs with attention [12] to
predict the buggy line and the code to replace it. They use compiler feedback
to iteratively fix errors in the program until they are fixed completely.
These methods [19, 72] mostly fix syntax-related bugs but trying to solve
semantics-related bugs (e.g.replacing variables) is also an interesting
direction [40]. An Empirical Study on Learning Bug-Fixing Patches in the Wild
via Neural Machine Translation [170] performs a large-scale empirical study on
the viability of these RNN-based NMT models for fixing real-world bugs and
comes up with a positive answer. pix2Code: Generating Code from a Graphical
User Interface Screenshot [17] generate source code from graphical user
interface. They use CNNs to process the input GUI and generate source code
using LSTM. SparsePointerNetwork: Learning Python Code Suggestion with a
Sparse Pointer Network [20] use LSTM with attention to generate new tokens for
code completion. They also apply pointer network [175] with attention to
existing identifiers to select them for code completion. Thus, the model can
generate new tokens and also can select one from the existing set for
completion. NL2Bash: A Corpus and Semantic Parser for Natural Language
Interface to the Linux Operating System [111] and Program Synthesis from
Natural Language Using Recurrent Neural Networks [110] use RNNs with attention
to generate bash scripts from natural language explanations. A common
limitation of RNN-based code generation is that the performance of these RNN-
based decoders decreases as the length of the sequence increases.

####  4.1.2 Transformer and LLMs

: Code generation using transformer [173] and large language models [136, 25,
41] is the current state-of-the-art method. Codex [30] finetunes a language
model called GPT [136] on public source code available in GitHub for source
code generation from natural language explanation. They generate multiple
samples and select the best one based on criteria such as unit tests or mean
log probability, and this improves the performance of the system by a large
margin. The limitation of this model is that the model performance degrades
when the sequence length increases. Codex has also been deployed in real-world
toolkits such as GitHub Copilot to assist developers by generating source code
from the natural descriptions. AlphaCode [108] presents a solution that can
generate competition-level source code (Python and C++) from natural language
examples and unit tests. They pre-train their model on multiple programming
languages using masked language modeling like BERT [41] for the encoder and
next token prediction for the decoder [108]. They then fine-tune their model
on the CodeContests dataset. During inference, they generate millions of
samples per problem in parallel using high temperature (e.g.T=0.25). Once they
generate multiple samples, they filter those codes that can pass the given
example unit tests. They also cluster the solutions based on their response to
input test cases. These sampling, filtering, and clustering are important
steps for the competition-level source code generation [108]. LLM: Program
synthesis with large language models [10] performs a large-scale study of
large language models (LLMs) for source code generation (Python) from natural
language description and unit tests. They show that these LLMs are quite
effective at few-shot learning tasks on code generation. InCoder: A Generative
Model for Code Infilling and Synthesis [56] presents a unified framework for
code generation and code editing based on LLMs. They train autoregressive
models to predict a masked document (a document where some span is replaced by
<mask> and moved to the end). This allows them to generate code at test time
and also allows code editing, variable re-naming, type prediction, and comment
generation using a single model. PolyCoder A systematic evaluation of large
language models of code [189] presents systematic evaluation of autoregressive
LLMs such as Codex [30], GPT-Neo [21], GPT-J [176], GPT-NeoX [22], CodeParrot
[172] across various programming languages. They also propose a medium-sized
LLM called PolyCoder trained in multiple programming languages. They observe
the performance of LLMs increases by training using multiple languages,
increasing the model size (except CodeParrot), and training longer. NL2Code: A
Scalable and Extensible Approach to Benchmarking NL2Code for 18 Programming
Languages [27] present parallel code generation benchmark on multiple
languages and evaluate two popular LLM-based models Codex and InCoder for code
generation. Generating Bug-Fixes Using Pretrained Transformers [47] show that
transformr [173] based models are also quite effective at fixing bugs.
Learning Autocompletion from Real-World Datasets [11] and IntelliCode Compose:
Code Generation using Transformer [165] use these transformer-based models for
real-world code completion. Learning Performance-Improving Code Edits [120]
uses anguage model to predict optimized code (instead of a code that has time
complexity $O(n^{2})$, suggest code that does it on $O(n)$ ). Conversation: A
Conversational Paradigm for Program Synthesis [128] and The Programmer’s
Assistant [144] presents a conversational approach to source code generation
(Python) from natural language explanation using LLM based model where the
model interacts with a user to generate subprograms multiple times leading to
the complete solution. They concatenate the previous prompts with previous
subprograms for the next subprogram prediction using LLMs. Making the system
capable of generating source code on a conversational paradigm is an important
research direction. This allows the model to understand the user intent in a
better way. Understanding user intent for code generation is an important
first step towards code generation [60]. Conversational Automated Program
Repair [188] uses conversational paradigm to fix a buggy code using LLM models
like codex and ChatGPT [131]. Recently, prompt-based engineering [183, 181]
has been quite popular as a way to understand user intent for natural text
generation. Evaluating the Text-to-SQL Capabilities of Large Language Models
[139] uses prompt-based evaluation of codex on text-to-SQL conversion and
shows improved results. DocPrompting [203] use prompting to gather knowledge
from changing documentation and APIs (of library functions) to code
generation. These retrieval augmentation-based language models are good for
incorporating knowledge from constantly changing documentation and APIs.
Asking Clarification Questions for Code Generation in General-Purpose
Programming Language [105] uses clarification questions (CQs) to resolve
ambiguities in the user’s intent understanding by using LLM as a CQ generator
and code generator. This model is quite interesting as it can ask questions to
users when the natural description is ambiguous. Another important paradigm
for code generation is the breakdown of a big problem into subproblems and
generating programs to tackle each subproblem separately. This is closely
related to how humans generate programs. Parsel: A (De-)compositional
Framework for Algorithmic Reasoning with Language Models [197] converts a
natural description into parsel functions (subproblems) with constraints from
human input, then they solve these subproblems with actual implementations
using a language model (Codex) and also use a solver to satisfy the
constraints. It would be really interesting if the model can decompose a
problem into subproblems. One method that tries this idea is Self-planning
Code Generation with Large Language Model [86]. It uses LLMs for self-
planning. The LLM generates plans for solving a task using prompt engineering
and solves the problem in a step-by-step fashion. Another closely related
paradigm for code generation is sketch generation. We can think of sketch as a
high-level guideline to solve program generation. This idea is also inspired
by how humans write source code. We first create a rough sketch and then fill
in the small details. Coarse-to-Fine Decoding for Neural Semantic Parsing [44]
first decodes the sketch of the program (with coarse tokens) and secondly
decodes the low-level details like variable names based on the input and the
sketch. A similar idea has been used in [130]. SKCODER: A Sketch-based
Approach for Automatic Code Generation [106] combines the idea of retrieval
augmented model with sketch-based generation. Given an NL description it
chooses a similar code snippet from a retrieval corpus, based on the NL
description it uses a sketcher to extract a code sketch from a similar code,
and employs an editor to edit the sketch based on the NL description and
obtain the target code. Recently, these transformer-based models have also
shown their impressive performance in solving math problems by framing them as
a program synthesis problem from natural descriptions [167]. Moreover, LLM-
based program synthesis is being used to generate programs that can operate on
images and natural languages to generate an answer. This mechanism provides a
neuro-symbolic framework for solutions to problems in computer vision and
natural language processing. For example, PAL: Program-aided Language Models
[58] uses code generation as an intermediate step for solving symbolic and
arithmetic reasoning. Code as Policies: Language Model Programs for Embodied
Control [181] uses code generation as an intermediate step that can be
executed as a policy for robot manipulation. Binding Language Models in
Symbolic Languages [34] takes an input, generates a program (binder program:
like a python with pandas) using a language model (Codex) that can then be
executed by the binder interpreter (SQL + python + language model) to produce
an answer for natural language question-answering tasks. The performance of
these LLMs increases with the increase in their model size [10, 30], but the
large size makes them expensive to train and evaluate.

####  4.1.3 RL

: Code generation models based on RL can utilize the signals from unit tests
or compilers to improve the code generation system unlike previous RNNs and
LLMs-based models (AlphaCode uses unit tests to filter out samples but doesn’t
learn from its feedback). For example, CodeRL [100] uses actor-critic
framework [94, 163] where the actor (LLM [179]) generates a code and a critic
(transformer) generates feedback signals for the actor. Similarly, Execution-
based Code Generation using Deep Reinforcement Learning [152] executes the
generated code and uses the results from the execution as rewards to update
the model along with KL divergence penalty to reduce memorization, AST, and
DFG matching scores for syntactic and semantic knowledge. REPL: Write,
Execute, Assess: Program Synthesis with a REPL [48] use RL-based learning
paradigm to utilize the signals from REPL(read-eval-print-loop) to generate
the source code (graphic programs) from images. This paper is based on the
idea of execution-guided program synthesis [32, 207] where the idea is to use
the execution states of the current subprogram to generate a better program.
This is a powerful paradigm that can be combined with any encoder-decoder
architecture [32]. This paper uses a policy network ($\pi$) to select an
action (production rule from the grammar: add circle/add rectangle rule for 2D
graphics) and create a subprogram, REPL to execute the current subprogram and
generate current output (render the current program to generate an image), and
a value function ($v$) to assess how likely the current program will help
towards the final goal (spec: final image to be rendered). Another interesting
part of this paper is the evaluation framework where they generate programs
using sequential monte carlo [46] guided by the value function ($v$) and show
that it performs better than the beam search. This is similar to how humans
write programs: write something, evaluate it, and correct it until it works.
This line of work is a good research direction. Similarly, Seq2SQL: Generating
Structured Queries from Natural Language using Reinforcement Learning [202]
uses a policy network to generate SQL queries from natural language
descriptions and utilize the signals from the execution of a generated query.
The reinforcement framework allows us to train a system where we can have
multiple SQL queries producing the same result using rewards, which are
otherwise penalized by cross-entropy loss except for the ground truth query.
RLCorrection: Deep reinforcement learning for programming language correction
uses actor-critic framework [124] to fix common errors in C source code. They
show that the system can be trained faster with expert demonstrations and
eventually beat DeepFix. CompCoder: Compilable Neural Code Generation with
Compiler Feedback [178] use compiler feedback as a reward signal to improve
the LLM for source code (Python) completion and generation from natural
language description. Thus, LLMs with RL framework are quite powerful models
for code generation.

####  4.1.4 NeuroSymbolic

: Neurosymbolic methods [59] contain a neural module and a symbolic module.
Neural networks are great at learning from noisy data but are not
interpretable and lack explicit reasoning capabilities. Symbolic models are
great at reasoning but are quite inefficient at learning from noisy data. Thus
they complement each other for learning from noisy data with reasoning. Thus,
neurosymbolic methods are getting quite popular. In this section, we will
cover neurosymbolic methods for program generation. We also include library
learning methods (methods that build a learned library) inside neurosymbolic
methods treating the library as a symbolic module. In the context of code
generation, there are two primary ideas: one is to use classical search-based
techniques and another is to use neural networks. Classical techniques
enumerate over the program space such as enumerative search, or add some
heuristics and constraints to speed up such as sketch-based solutions and SMT
solver-based solutions. The major disadvantage of these methods is we need to
perform a combinatorial search in the program space which is really hard and
these models only work with DSLs (do not scale to real-world programming
languages like Python and C++). Neural network-based methods generate source
code based by predicting the next likely token each time and thus can fail if
one token is wrong in the sequence. Methods like DeepCoder: Learning to Write
Programs [13] use both techniques for code generation. It uses a neural
network to predict the presence or absence of high-level functions (e.g. sort,
max, min, reverse) based on input-output examples and let this result guide
the search process of classical program induction techniques such as sketch-
based solution [155] and $\lambda^{2}$ [54]. They show that their solution
improves the search time by a large margin. The limitation of the paper is
that the solution has been tried for a small DSL and applying a similar idea
for source code generation in real-world programming languages such as Python,
C, and C++ is an interesting research direction. Library Learning for
Neurally-Guided Bayesian Program Induction [50] and Dreamcoder [49] proposes a
program induction algorithm that learns DSL (higher abstractions) while
jointly training a neural network to predict program properties like
DeepCoder. This is related to the programming paradigm where a programmer
builds libraries of reusable subroutines that are shared across related
programming tasks and can be composed to generate increasingly complex and
powerful subroutines. The system extracts new DSL subroutines from a common
structure found across syntax trees of the generated programs that solve the
given set of tasks. These methods are promising directions for human-like code
generation but their applicability to source code generation in real-world
programming languages such as C, C++, and Python is yet to be seen as the
search space of these real-world programming languages is extremely huge
compared to the search space defined by the DSL these methods use.

###  4.2 ASTSequence

These papers first represent the program in the form of AST, but at prediction
time they linearize the AST into a sequence and make a prediction. The
advantage of such a system is that the linearized system is easy to
parallelize and the AST representation carries explicit syntax information
helping the model learn the grammar of the language easily. The disadvantage
of this method is that we need to introduce new tokens (e.g.brackets) for
linearization of the AST that introduce long-range dependencies in the
prediction. Thus, if we miss one corresponding token, the output can’t be
converted into AST using automated code and thus we can’t generate the source
code. But these constraints can be satisfied during decoding. For example,
PointerMixture: Code completion with neural attention and pointer networks
[107] use this framework for code completion in a dynamically-typed language
like Python. They propose a Pointer mixture network where the model can
generate new tokens from the output vocabulary using LSTM and attention [12],
and also can copy tokens from the partial code by using pointer networks
[175]. They use in-order depth-first traversal to flatten the AST
representation of the source code. They also propose parent attention for AST-
based code completion where the idea is that the parent node should have high
relevance for the child node compared to other nodes. Representing source code
using AST and letting the model predict AST instead of source code makes the
model easier to converge as the syntax is explicit. The model also learns
representations that can be shared across multiple languages [8, 7] compared
to the model that directly predicts the source code. But, converting source
code to AST and flattening them increases the size and introduces long-range
dependencies between tokens [198]. The deeper ASTs also weaken the capability
of the models to capture complex semantics [206]. The solution to this problem
is to augment the AST with data flow and control flow structures [5]. Another
solution would be to decompose large ASTs into a sequence of small statement
trees [198]. The methods that use ASTs for injecting syntacting structure into
the model and data flow graphs for injecting semantic awareness to the model
are rising. Also, comparing models based on multiple output representations
and the impact of output representation on code generation is an important
research direction.

###  4.3 Graph

These methods generate a graph (AST) representation of the source code. The
advantage of such methods is that the AST captures the syntax of the given
language explicitly. The major disadvantage of such systems is that it’s non-
trivial to parallelize such systems and we need another extra module that
generates source code from AST representation. These methods generate a graph
(AST) representation of the source code.

####  4.3.1 BinaryTree

These methods first encode the Nary AST tree into a binary tree using
predefined algorithm like the left child right sibling algorithm and generate
a binary tree. The disadvantage of this idea is that we again need another
module that converts from binary tree to Nary AST tree. The conversion from an
AST tree to a binary tree also increases the long-range dependency between
tokens and it can make the training harder. Neural Code Completion [114]
convert the source code to AST. They then convert the AST to a binary tree
using the left-child right-sibling algorithm. They use LSTM to predict the
next node for code completion. Tree2Tree [33] translates programs written in
one language (Java/Coffeescript) to another language (C#/Javascript). They
generate the AST of the target language given the AST of the input language
using a tree decoder. They use tree-lstm [166] to encode the input AST
representation of the source code. When the decoder expands a non-terminal, it
locates the corresponding sub-tree in the source tree using an attention
mechanism and uses the information of the subtree to guide the non-terminal
expansion. They also use the idea of parent attention feeding (if target node
t depends on source node s, it’s likely that the child of t depends on the
child of s ) to improve the prediction results. Coda: An End-to-End Neural
Program Decompiler [57] generates AST representation of the source code from
the input assembly. They use instruction type aware encoders (separate RNNs
for different types of statements instruction types: memory, arithmetic, and
branch operations) to encode the input assembly. They generate a binary AST
tree by converting the original AST into a binary tree using left child right
sibling representation and use an AST tree decoder with an attention mechanism
for decoding similar to Tree2Tree. The tree decoder consists of two LSTMs, one
for the left-child prediction and the another for the right-child prediction.

####  4.3.2 NaryTree

These methods directly predict the Nary AST tree. The advantage of this idea
is that we don’t need another module that converts from a binary tree to a
Nary AST tree compared to binary tree generation. The disadvantage of such
methods is that it’s non-trivial to parallelize these models compared to
sequence-to-sequence models. In the following section, we divide the Nary AST
tree prediction methods based on the methods they use such as RNNs,
transformers, GNNs, and neurosymbolic.

[RNNs and CNNs]: SNM: A syntactic neural model for general-purpose code
generation [192] generates abstract syntax trees and then uses them to
generate high-level programming language code like Python from the natural
language description of the source code. They use the encoder-decoder paradigm
where the encoder is a simple LSTM network that encodes the description of the
code. The decoder generates ASTs from the encoded input and uses the grammar
of the AST. At each step of the generation, it selects one production rule
(function call, if-statement) and adds it to the partial AST if the generation
step is non-terminal. If the generation step corresponds to the terminal, it
generates variable names and values using a copy mechanism using pointer
networks [175]. They also use parent feeding while generating a subtree
(passing the embeddings of the parent that generated the children and using
that for prediction). LCPC: Mapping Language to Code in Programmatic Context
[82] uses encoder-decoder architecture to transform the natural language
description of method names to generate the code for that method. This paper
selects rules using the attention mechanism and uses those rules for decoding
the program structure (ATSs). They also use a supervised copy mechanism from
using CopyNet [67]. ASNs: Abstract Syntax Networks for Code Generation and
Semantic Parsing [135] propose abstract syntax networks (ASNs) that generate
source code abstract syntax trees [ASTs] (Python) in a top-down manner from
natural descriptions extracted from card games such as HearthStone. They use
an encoder-decoder mechanism where the encoder encodes the natural language
[extracted from images] and the decoder constructs ASTs for the source code in
a top-down manner. They use vertical and horizontal LSTMs with attention to
transferring information in the top-down and horizontal directions
respectively. They use different modules corresponding to the construct in the
grammar. The advantage is that the network always respects the grammar of the
language being generated. The network first predicts the module and the
corresponding module does the expansion. They also use the supervised loss for
the alignment (attention) of target tokens with some input tokens instead of
using attention as a post-processing step for the copy mechanism. Program
Synthesis and Semantic Parsing with Learned Code Idioms [151] mines code
idioms (fragments of code that represent higher level abstraction: sum of two
numbers) from the dataset by using their ASTs and looking at the repetitive
patterns. During the program synthesis, it generates an AST: but for each node
generation, it can either generate a token or a code idiom (subgraph of AST).
This code idiom mining is an important idea for building subroutines that can
be used across multiple tasks for source code generation. CNNDecoder A
grammar-based structural CNN decoder for code generation [160] use
convolutional neural networks (CNNs) [102] instead of RNNs for predicting the
grammar rules in a similar fashion of ASNs. They show that CNNs can handle
long-range dependencies better than RNNs.

[Transformer and LLMs]: SLM: structural language models [9] uses abstract
syntax trees (ASTs) for code completion. Given the source code of the program
with some lines left out, the model can predict the left-out code. The main
idea is to jointly learn the encoder and decoder. Given the source and target
both are codes, they jointly learn the probability of the program’s AST. The
probability of an AST is calculated as a conditional probability of each node
given other nodes observed so far. To gather the information of each node for
predicting what the next node will be, they use paths from the root to the
given node and paths from every leaf terminal to the given node (encoded using
LSTM). They then use transformer [173] to aggregate information from multiple
paths. AST Path-based representation of the source code has been quite
powerful for source code representation [8, 7]. TreeGen: A Tree-Based
Transformer Architecture for Code Generation [161] uses transformer [173] to
generate AST representation of the source code by making a prediction over the
grammar rules from natural explanation. The advantage of this method is that
the transformer can handle long-range dependencies well compared to RNNs and
the prediction over the grammar rule makes sure that the generated code is
syntactically correct.

[GNNs]: GMG: Generative Code Modeling with Graphs [24] attempts to do code
completion given some context code using graph neural networks. The main idea
is to use ASTs to represent the given partial code and augment it using some
type of edges between nodes in partial ASTs like the parent of edge, child of
edge, next sibling edge, etc (data flow and control flow augmentation). They
then apply a graph neural network to get the representation of the partial
program. During each expansion of the node, they perform classification on the
grammar rules and select one among the possible grammar rules so that the
subtrees generated are always syntactically correct.

[NeuroSymbolic:] SemFix: Semantic Code Repair using Neuro-Symbolic
Transformation Networks [40] developed a system to predict the location of the
simple semantic bugs (incorrect variable, incorrect comparison operator,
missing not operator, missing self) along with the actual fix without using
unit tests for Python. They convert the source code to AST, embed the AST node
with information such as the string form of the node, position of the node,
relationship with the parent, and the type of the node, and encode AST using
bidirectional LSTM. They then use another module to select the repair
candidate rules (e.g.replace == by != at node n). They use MLP to select
repair candidate rules as they are fixed and pointer networks [175] to
variable replacement. The limitation of this paper is that the developers need
to write these repair candidate rules. The research on using neurosymbolic
methods for code generation is limited and is an important research direction.

##  5 Copy Mechanism

Copy mechanisms: a system for copying the tokens from input to output are
quite useful for code generation. For example, they can be extremely useful
for neural decompilation where we need to copy the values from input assembly
to output code. They are equally important for code generation from natural
language, program translation, and more. There are multiple solutions to this
problem. PtrNet: Pointer Networks [175] proposes the idea of using attention
as a pointer to select a member of the input sequence as the output token.
This allows the model to select some part of the input at the time of
generation. This idea has been quite powerful and multiple papers in machine
translation and code generation use this idea or its variants to copy some
tokens from the input sequence. It also allows us to limit the output
vocabulary during code generation as we can copy some of the tokens from the
input directly (even if they are out of vocabulary tokens for the output
language). PtrGenNet: Get To The Point: Summarization with Pointer-Generator
Networks [148] uses sequence-to-sequence networks for abstract text
summarization with the hybrid approach of generation of tokens and copying
values from the input using pointer networks. They also use a penalty term in
the loss function that penalizes repetitive attention to the same location.
CopyNet: Incorporating Copying Mechanism in Sequence-to-Sequence Learning
[67]. It introduces a mechanism to copy values from the input sequence to the
output sequence in the sequence-to-sequence learning scenarios. Their method
decides when to copy from the input or when to predict the target value using
two functions. The function calculates attention between the current hidden
state of the decoder to every word in the vocabulary and to every word in the
input sequence and decides to copy or generate the target token. Moreover, the
system can be trained in an end-to-end fashion from the data. Thus copying
mechanism is an important part of the neural machine translation systems for
code generation. But, in some cases, direct copying from the input sequence
may not be a good option as the output token depends on some function of the
input token. For example, when we are trying to generate a source code from an
assembly sequence where the multiplication by two in the source code is
implemented by shift operations, direct copying may give us the wrong results.
In such cases, complementing the copying mechanism with simple functions like
multi-layer perceptron could give better results.

##  6 Representation Learning and pretraining

Learning a good way to represent the source code or the text is an important
part of the source code generation. The embeddings learned from these
techniques can be used for various downstream tasks such as code generation,
code summarization, and code completion. In this section, we summarize various
ideas that can be used for representation learning and pretraining. Initial
work on code representation is inspired by works in NLP such as Word2Vec:
Efficient Estimation of Word Representations in Vector Space and Distributed
Representations of Words and Phrases and their Compositionality [123]. It uses
a distributional hypothesis that states words that occur in similar contexts
have a similar meaning. Pretraining strategies are quite popular in NLP and CV
as a way to utilize unlabelled data to learn the representations. In the
following sections, we will describe some of the important pretraining and
representation learning strategies for source code. NMT-based code generation
uses an encoder-decoder-based model for code generation. Based on the
component(encoder, decoder, bot) they use for pertaining, these methods can be
divided into the following groups:

###  6.1 Encoder only:

These methods pre-train only the encoder. For example, CuBERT: Learning and
Evaluating Contextual Embedding of Source Code [89] uses BERT’s [41] masked
language modeling objective for code generation pre-training. CodeBERT: A Pre-
Trained Model for Programming and Natural Languages [53] uses masked language
modeling along with replaced token detection for code generation.
GraphCodeBERT [70] use data flow information extracted from code in
conjunction with CodeBERT. DOBF [145] uses deobfuscation based pre-training to
inject programming language domain information. DOBF and GraphCodeBERT focus
only on the code-specific encoder. The disadvantage of these methods is that
they do not utilize the decoder for pre-training.

###  6.2 Decoder only:

These methods only pre-train the decoder. For example, IntelliCode [165] uses
GPT for code completion task and are trained for next-word prediction. The
disadvantage of these models is that they do not utilize the encoder during
the pre-training stage.

###  6.3 Encoder-Decoder:

These methods pre-train both encoder and decoder at the same time. For
example, CodeT5 [179] augments model T5 [137] that employs denoising sequence
to sequence pre-training (corrupt the input and lets the decoder decode it)
and adds identifier tagging, masked identifier prediction, masked span
prediction, and dual generation to improve the system. As this model can pre-
train both encoder and decoder for their respective tasks, this method has an
advantage over encoder-only and decoder-only methods for source code
generation [179]. PLBART [3]: trains on with denoising sequence to sequence
models like BART [104] but does not inject domain information from programming
languages domain. LangAgnostic [208] proposes to capture the relative
distances between code tokens over the code.

Based on the type of information these methods try to capture, they can be
divided into the following groups:

###  6.4 text-based

text-only models of representation learning such as [179] capture only the
text-based representation of the source code. But, source code has a richer
structure that can be defined using abstract syntax trees (ASTs) and semantics
that can be captured using data flow graphs (DFGs) and program dependence
graphs (PDGs). The text-only representation learning forces the model to learn
these syntactical information and semantic information on its own and thus may
not be the optimal way for representation learning of the source code.

###  6.5 syntax-based

These methods try to inject the syntactical knowledge of the source code into
their representation learning objective. For example, Code2Vec: Learning
Distributed Representations of Code [8] and Code2Seq: Generating Sequences
from Structured Representations of Code [7] generates a vector representation
of the given code snippet by generating a vector representation for AST paths
(path between leaf nodes in an AST) and aggregating them using an attention
module. These representations can be useful for tasks like code summarization,
documentation, retrieval, code completion, and more. Code2Seq uses LSTM to
embed paths into a fixed length vector while Code2Vec uses a linear layer.
Language-Agnostic Representation Learning of Source Code from Structure and
Context [208] leverages context (source-code) and structure (AST) to learn a
good representation of the source code. UniXcoder: Unified Cross-Modal Pre-
training for Code Representation [71] proposes multimodal pretraining that
utilizes code comments and linearized AST along with the source code. It uses
masked language modeling, next token prediction, denoising objective along
with multi-modal contrastive learning objective (similar embeddings for
similar examples and different for different), and cross-modal generation
objective (generate comment from AST and vice versa) as pretraining
strategies. In a similar way, TreeBERT [85] uses the encoder-decoder
transformer framework and utilizes the tree structural information by modeling
AST paths (tree-based masked language modeling and node order prediction).
SYNCOBERT: Syntax-Guided Multi-Modal Contrastive Pre-Training for Code
Representation [177] incorporates abstract syntax tree for pretraining. It
uses Identifier prediction and AST edge prediction as two pretraining
strategies and tries to maximize the mutual information between multimodal
inputs such as code, comments, and AST using contrastive learning. SPT-Code:
Sequence-to-Sequence Pre-Training for Learning Source Code Representations
[129] uses both text and linearized AST of a code with an encoder-decoder
framework for code representation learning.

###  6.6 semantic-based

These methods try to inject not only text-based and syntactic information, but
also semantic information into their learning objectives. Given, source code-
based representation learning methods capture context and AST-based techniques
capture syntax, hybrid methods that try to learn the context and syntax are
increasing. For example, LRPG: Learning to Represent Programs with Graphs [5]
augments the AST with data flow and control flow edges. They use graph neural
networks over these graphs to learn a semantic representation of the source
code. Contrastive code representation learning [83] uses contrastive learning
for source code representation learning. The idea is to maximize similarity
with equivalent programs and minimize similarity with functionally different
programs. They claim that it is better than masked language models (MLM) as
they (MLM) only learn local language reasoning which may not be the best way
to summarize the functionality of the program. StructCoder: Structure-Aware
Transformer for Code Generation [168] encodes syntactic and semantic
information to the encoder and decoder for code generation using AST path
prediction for syntactic information and data flow for semantic information.
Recently, Flow2Vec: Value-Flow-Based Precise Code Embedding [158] uses value
flows for code representation learning and shows impressive results.

##  7 Open problems and research directions

Source code generation is a challenging task. There are multiple open problems
and research directions. In this section, we will try to highlight some of the
open problems and potential research directions. Source code has long
dependencies in multiple places [101]. For example, a statement to open a file
can be in line 3, while the command to close the same file can be in line 100.
This really long dependency is a problem for existing techniques. It has been
shown that the performance of these encoder-decoder models decreases as the
sequence length increases. Thus solving long-range dependencies is an
important research direction for source code generation. Most of the existing
methods work on next-token prediction (NTP) and optimize the likelihood of the
next token given previous tokens and input and this leads to accumulating
errors [18, 140]. Current NMT-based systems work on next token prediction in a
sequential fashion. Although different decoding strategies help in avoiding
these pitfalls, they are computationally expensive. Humans do not generate a
complete program token by token for a complete task like current code
generation methods [108]. We break down a problem into subproblems and test
them iteratively. Methods that can break down a problem into small problems,
generate code for such subprograms, and evaluate them such as [48, 197] are
good potential research directions. Most of the current code generation
systems do not combine the generated code abstractions into higher-level
abstractions as humans do. Humans keep a collection of subroutines and combine
them to perform higher-level tasks. DreamCoder: growing generalizable,
interpretable knowledge with wake-sleep bayesian program learning [49] takes
an initial step in this direction. Most of the best-performing methods in
current source code generation are based on large language models. But, these
LLMs require a lot of training data and compute resources. Thus, the current
solutions are not sample efficient. Making these source code generation
samples efficient is an interesting research direction. The syntax-guided
method takes care of syntax but not semantics. In particular, standard
supervised training procedure could suffer from program aliasing: for the same
input-output examples, there are multiple semantically equivalent programs,
but all except the one provided in the training data will be penalized as
wrong programs [32]. To mitigate this [26] propose to train with reinforcement
learning so that it rewards all semantically correct programs once they are
fully generated. But [32] show we can use execution-guided synthesis for this
task. Execution-guided synthesis [32, 207] currently works with DSLs, but
extending them to real-world source code generation is also an interesting
research direction. Humans don’t write everything from scratch for
descriptions to code generation: A Retrieve-and-Edit Framework for Predicting
Structured Outputs [74] retrieves the closest example from the training
dataset and uses an editor network to predict edits on the retrieved code so
that it does the intended job. Using these ideas of already existing code and
documentation to better improve code generation is an interesting direction.
Utilizing ideas such as Unsupervised Translation of Programming Languages [98]
when we don’t have a parallel aligned dataset is also an interesting research
direction for source code generation. As more and more papers utilize the
feedback from unit tests for improving the code generation models, it is worth
exploring automatic unit test generators based on deep learning such as Unit
Test Case Generation with Transformers and Focal Context [171]. This allows us
to improve both models, i.e. code generator and unit test generator
simultaneously. Most of the existing systems work on small programs with
single functions and extension to a program with multiple functions is
challenging and interesting research directions. The code generation module
may be just remembering the training dataset leading to security and copyright
issues: WhyGen: Explaining ML-powered Code Generation by Referring to Training
Examples [190] use fingerprints to find the closest training example. But the
scalable solution to internet scale training is still an open research
problem. Reinforcement learning from human feedback (RLHF) has been quite
popular in fine-tuning large language models with human feedback. Applying
similar ideas for improving code generation is an important research
direction. Recently, Improving Code Generation by Training with Natural
Language Feedback [29] shows initial impressive results in this research
direction.

##  8 Datasets

In this section, we will introduce some of the datasets for code generation
tasks. CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding
and Generation: [115][https://github.com/microsoft/CodeXGLUE] consists of 14
datasets for 10 diversified code intelligence tasks covering code-to-code,
code-to-text, text-to-code, and text-to-text (documentation) translation. The
dataset covers multiple languages such as C, C++, Java, Python, and more.
CodeXGLUE also includes eight previously proposed datasets — BigCloneBench
[164], POJ-104 [125], Devign [205], PY150 [141], Github Java Corpus [4],
Bugs2Fix [170], CONCODE [82], and CodeSearchNet [81]. APPS: Measuring Coding
Challenge Competence With APPS [75][https://github.com/hendrycks/apps]
consists of a dataset for Python code generation from natural language
explanation. SPoC: Search-based Pseudocode to Code
[96][https://github.com/Sumith1896/spoc] is a dataset for C++ code generation
from pseudocode. Concode: Mapping Language to Code in a Programmatic Context
[82][https://github.com/sriniiyer/concode] is a dataset for Java code
generation from docstrings. CodeSearchNet Challenge: Evaluating the State of
Semantic Code Search [81][https://github.com/github/CodeSearchNet] consists of
a dataset for code retrieval from natural language for multiple languages such
as Go, Java, JavaScript, PHP, Python, and Ruby. It can also be used for code
generation tasks. A parallel corpus of Python functions and documentation
strings for automated code documentation and code generation
[14][https://github.com/EdinburghNLP/code-docstring-corpus] consists of a
dataset for code generation in Python from docstring and vice versa. StaQC: A
Systematically Mined Question-Code Dataset from Stack Overflow
[191][https://github.com/LittleYUYU/StackOverflow-Question-Code-Dataset]
consists of a dataset for question-to-code pairs for python and SQL mined from
stack-overflow. CoNaLa: The Code/Natural Language Challenge
[193][https://conala-corpus.github.io/] consists of a dataset for python code
generation from natural language. HumanEval: Hand-Written Evaluation Set
[30][https://github.com/openai/human-eval] consists of a dataset for
handwritten Python program generation from function signature, docstring, and
body with an average of 7.7 unit tests per program. CodeContests: competitive
programming dataset [108][https://github.com/deepmind/code_contests] includes
CodeNet dataset as well AlphaCode Competition level dataset for Python and C++
code generation from a natural language with unit tests. MBPP (mostly basic
programming problems) dataset [10][https://huggingface.co/datasets/mbpp]
consists of a dataset for Python code generation from natural language
explanation along with test cases. Spider: A Large-Scale Human-Labeled Dataset
for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task
[195][https://yale-lily.github.io/spider] consists of a dataset for SQL code
generation from natural language. NL2Bash: Generating bash command from
natural language [111][https://github.com/TellinaTool/nl2bash] consists of a
dataset for bash script generation from natural language explanation.
PolyCoder: A Systematic evaluation of large language models of code
[https://github.com/VHellendoorn/Code-LMs] consists of a dataset for code
generation in 12 programming languages from natural language explanation.
Pix2code: Generating Code from a Graphical User Interface Screenshot
[17][https://github.com/tonybeltramelli/pix2code] consists of a dataset for
code generation(Android, IOS, Web Technologies) from a graphical user
interface. WikiSQL: Generating Structured Queries from Natural Language using
Reinforcement Learning [202][https://github.com/salesforce/WikiSQL] consists
of a dataset for SQL query generation from a natural explanation. MultiPL-E: A
Scalable and Extensible Approach to Benchmarking NL2Code for 18 Programming
Languages [27][https://github.com/nuprl/multipl-e] consists of a dataset for
source code generation in 18 programming languages from natural language
explanation. CodeNet: A Large-Scale AI for Code Dataset for Learning a
Diversity of Coding Tasks [134][https://github.com/IBM/Project_CodeNet]
consists of a dataset for multiple tasks like source code generation, code
translation, etc in 55 different programming languages. DS-1000: A Natural and
Reliable Benchmark for Data Science Code Generation [99][https://ds1000-code-
gen.github.io/] consists of a dataset for code generation problems in data
science from natural descriptions. The Stack: 3 TB of permissively licensed
source code [93][https://huggingface.co/datasets/bigcode/the-stack] is a 3.1
TB dataset consisting of permissively licensed source code in 30 programming
languages. CoderEval: A Benchmark of Pragmatic Code Generation with Generative
Pre-trained Models [194] consists of a dataset for code generation from
natural language collected from real-world open-source projects. Multi-Turn
Programming Benchmark (MTPB) [127] consists of a dataset for conversational
code generation where the user specifies the subtasks and the model completes
them.

##  9 Evaluation

In this section, we will introduce common metrics that are being currently
used for generated code evaluation.

  * •

BLEU Score: BLEU score [132] and exact match accuracy. Exact match accuracy is
the fraction of test samples that the model predicts the entire sequence
correctly. The BLEU score has been a standard for evaluating machine
translation against human translation in natural language processing. The BLEU
score is defined as follows:

BLEU $\displaystyle=\texttt{BP}.exp\big{(}\sum_{n=1}^{N}w_{n}logp_{n}\big{)}$

Where, $w_{n}$ is a scalar such that $\sum_{n=1}^{N}w_{n}=1$, $p_{n}$ is a
modified precision for n-gram that is defined as follows ($\hat{y}$ is the
prediction):

$p_{n}=\frac{\sum\limits_{n-gram\in\hat{y}}Count_{clip}(n-gram)}{\sum\limits_{n-gram\in\hat{y}}Count(n-gram)}$

Where, $Count(n-gram)$ is the number of n-grams in the prediction, and
$Count_{clip}(n-gram)$ is the number of these n-grams in the prediction that
are present in the target sentence but clipped by the maximum frequency of
that n-gram in the target sentence. BP is a brevity penalty that penalizes
short translations and is defined as follows:

$\texttt{BP}=\begin{cases}1,&\text{if}\ c>r\\\
e^{(1-\frac{r}{c})},&\text{otherwise}\end{cases}$

Where $c$ is the length of the prediction and $r$ is the length of the ground
truth target (reference). This gives us a value between [0, 1] for every
translation. Generally, N is set to 4, and $w_{n}$ is set to $\frac{1}{N}$.

The problem with the bleu score is that it can not measure the functional
correctness of the programs and can not capture semantic features specific to
code: [100, 75, 30, 143]. Also, [30] shows some examples where the
functionally equivalent codes have lower blue scores than functionally
nonequivalent ones. This can be explained by the fact that semantically
identical programs can potentially have very low n-gram overlap; for example,
because of identifier renaming [10, 75, 30]. Although the BLEU score has been
used in multiple papers for evaluation, the BLEU score is not a good metric
for the evaluation of the generated source code. Does BLEU Score Work for Code
Migration [169] shows that BLEU is not a good measure for code evaluation and
proposes a method called RUBY based on string edit distance (text: code
similarity), tree edit distance (AST: syntactic similarity) and graph edit
distance (PDG: semantic similarity).

  * •

CodeBLEU: A Method for Automatic Evaluation of Code Synthesis [143]: uses a
weighted combination of BLEU (4-gram), syntactic matching (matching subtrees
in AST), and semantic matching (using dataflow structure). They demonstrate
this has a better correlation with human evaluation compared to BLEU.

CodeBLEU
$\displaystyle=\alpha*\texttt{BLEU}+\beta*\texttt{BLEU}_{\texttt{weight}}+\gamma*\texttt{Match}_{\texttt{ast}}+\delta*\texttt{Match}_{\texttt{df}}$
(12)

Where BLEU is the standard BLEU score [132], BLEU_weight is the weighted
n-gram match (high importance for keywords), Match_ast is the syntactic AST
match, and Match_df is the semantic data flow match [143] Although codeBLEU
captures multiple aspects of code compared to the BLEU score, it can measure
the functional correctness of the code. Thus, codeBLEU alone is not a good
measure for the evaluation of the generated source code.

  * •

Exact Match (EM): Exact match compares the whole sequence to the ground truth.
Given, programs without much overlap can produce the same results, EM is a
harsh measure for the evaluation of source code. Exact match-based metrics are
unable to account for large and complex space of program functions equivalent
to the reference solution [30]

  * •

Edit distance: Levenschtein distance (minimum cost sequence of string edit
operations to transform generated sequence to ground truth sequence) in case
of source code sequence and graph edit distance [1] (minimum cost sequence of
node and edge edit operations to transform generated graph to ground truth
graph) have been used in the literature for the evaluation of AST based code
generation. As noted in the above metrics, it suffers similar problems and can
not measure the functional correctness of the program.

  * •

Unit tests: Unit tests are the set of conditions that need to be passed by the
generated code. This metric is supported by test-driven development paradigm
where developers first write unit tests before writing the software [108].
Given a sufficient number of unit tests that cover all the paths of execution
of a reference code, we can verify that the two programs are functionally
equivalent. But, limited test programs can falsely claim that the program is
correct when it is not. Thus, sufficient unit tests are a really good method
of evaluation of the generated source code. One problem with unit tests is
that the generated code may be malicious. In such a case, it is better to run
the generated code in the sandbox environment.

  * •

pass@k metric [96, 30]: This metric is used with unit tests, where the idea is
to generate k samples per program and the problem is solved if any one of the
k solutions passes the unit tests. But this one has high variance [30], and
thus a modification was proposed by [30] to generate $n>k$ solutions and count
solutions that pass the unit tests as $c$. Then pass@k is defined as:

$\displaystyle pass@k$
$\displaystyle=\mathbb{E}_{\texttt{problems}}\Big{[}1-\frac{{n-c\choose
k}}{{n\choose k}}\Big{]}$ (13)

also, timeout-based evaluations to approximate the algorithmic complexity of
the generated solution [108] are being used in conjunction with the pass@k
metric.

  * •

CodeBERTScore and CodeScore: Evaluating Code Generation With Pretrained Models
of Code [204] and CodeScore: Evaluating Code Generation by Learning Code
Execution [45] proposes to use LLM for generated code evaluation similar to
BERTScore [200] that is used for evaluation of generated natural language.
They claim that this metric has a higher correlation with human preference and
with functional correctness than all existing metrics of code evaluation. It
works by calculating the similarity of generated code and reference code in
the embedding space where the embeddings are generated by using a pre-trained
model called CodeBERT [53].

##  10 Conclusion

Neural machine translation-based architectures are getting quite popular for
source generation from various inputs. The NMT-based code generation is useful
in multiple domains such as code generation from natural explanation, code
generation from input binary or assembly (decompilation), code-to-code
translation, code repair, bug fixing, and many more. In this survey paper, we
cover the latest techniques being used for source code generation from
multiple types of inputs. We also highlighted important techniques that are
useful for source code generation along with the identification of current
challenges and potential research directions. We presented common evaluation
methods with their advantages and disadvantages. We think our survey papers
lay the foundation for new researchers to start working in the field with an
overall current set of techniques and motivate experienced researchers to
develop new solutions that can solve the challenges identified in the paper
and more.

## References

  * Abu-Aisheh et al. [2015] Zeina Abu-Aisheh, Romain Raveaux, Jean-Yves Ramel, and Patrick Martineau.  An exact graph edit distance algorithm for solving pattern recognition problems.  In _4th International Conference on Pattern Recognition Applications and Methods 2015_ , 2015.
  * Aharoni and Goldberg [2017] Roee Aharoni and Yoav Goldberg.  Towards string-to-tree neural machine translation.  _arXiv preprint arXiv:1704.04743_ , 2017.
  * Ahmad et al. [2021] Wasi Uddin Ahmad, Saikat Chakraborty, Baishakhi Ray, and Kai-Wei Chang.  Unified pre-training for program understanding and generation.  _arXiv preprint arXiv:2103.06333_ , 2021.
  * Allamanis and Sutton [2013] Miltiadis Allamanis and Charles Sutton.  Mining source code repositories at massive scale using language modeling.  In _2013 10th working conference on mining software repositories (MSR)_ , pages 207–216. IEEE, 2013.
  * Allamanis et al. [2017] Miltiadis Allamanis, Marc Brockschmidt, and Mahmoud Khademi.  Learning to represent programs with graphs.  _arXiv preprint arXiv:1711.00740_ , 2017.
  * Allamanis et al. [2018] Miltiadis Allamanis, Earl T Barr, Premkumar Devanbu, and Charles Sutton.  A survey of machine learning for big code and naturalness.  _ACM Computing Surveys (CSUR)_ , 51(4):1–37, 2018\.
  * Alon et al. [2018] Uri Alon, Shaked Brody, Omer Levy, and Eran Yahav.  code2seq: Generating sequences from structured representations of code.  _arXiv preprint arXiv:1808.01400_ , 2018.
  * Alon et al. [2019] Uri Alon, Meital Zilberstein, Omer Levy, and Eran Yahav.  code2vec: Learning distributed representations of code.  _Proceedings of the ACM on Programming Languages_ , 3(POPL):1–29, 2019.
  * Alon et al. [2020] Uri Alon, Roy Sadaka, Omer Levy, and Eran Yahav.  Structural language models of code.  In _International conference on machine learning_ , pages 245–256. PMLR, 2020.
  * Austin et al. [2021] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al.  Program synthesis with large language models.  _arXiv preprint arXiv:2108.07732_ , 2021.
  * Aye et al. [2021] Gareth Ari Aye, Seohyun Kim, and Hongyu Li.  Learning autocompletion from real-world datasets.  In _2021 IEEE/ACM 43rd International Conference on Software Engineering: Software Engineering in Practice (ICSE-SEIP)_ , pages 131–139. IEEE, 2021.
  * Bahdanau et al. [2014] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio.  Neural machine translation by jointly learning to align and translate.  _arXiv preprint arXiv:1409.0473_ , 2014.
  * Balog et al. [2016] Matej Balog, Alexander L Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow.  Deepcoder: Learning to write programs.  _arXiv preprint arXiv:1611.01989_ , 2016.
  * Barone and Sennrich [2017] Antonio Valerio Miceli Barone and Rico Sennrich.  A parallel corpus of python functions and documentation strings for automated code documentation and code generation.  _arXiv preprint arXiv:1707.02275_ , 2017.
  * Basu et al. [2020] Sourya Basu, Govardana Sachitanandam Ramachandran, Nitish Shirish Keskar, and Lav R Varshney.  Mirostat: A neural text decoding algorithm that directly controls perplexity.  _arXiv preprint arXiv:2007.14966_ , 2020.
  * Beltagy et al. [2020] Iz Beltagy, Matthew E Peters, and Arman Cohan.  Longformer: The long-document transformer.  _arXiv preprint arXiv:2004.05150_ , 2020.
  * Beltramelli [2018] Tony Beltramelli.  pix2code: Generating code from a graphical user interface screenshot.  In _Proceedings of the ACM SIGCHI Symposium on Engineering Interactive Computing Systems_ , pages 1–6, 2018.
  * Bengio et al. [2015] Samy Bengio, Oriol Vinyals, Navdeep Jaitly, and Noam Shazeer.  Scheduled sampling for sequence prediction with recurrent neural networks.  _Advances in neural information processing systems_ , 28, 2015.
  * Bhatia and Singh [2016] Sahil Bhatia and Rishabh Singh.  Automated correction for syntax errors in programming assignments using recurrent neural networks.  _arXiv preprint arXiv:1603.06129_ , 2016.
  * Bhoopchand et al. [2016] Avishkar Bhoopchand, Tim Rocktäschel, Earl Barr, and Sebastian Riedel.  Learning python code suggestion with a sparse pointer network.  _arXiv preprint arXiv:1611.08307_ , 2016.
  * Black et al. [2021] Sid Black, Leo Gao, Phil Wang, Connor Leahy, and Stella Biderman.  Gpt-neo: Large scale autoregressive language modeling with mesh-tensorflow.  _If you use this software, please cite it using these metadata_ , 58, 2021.
  * Black et al. [2022] Sid Black, Stella Biderman, Eric Hallahan, Quentin Anthony, Leo Gao, Laurence Golding, Horace He, Connor Leahy, Kyle McDonell, Jason Phang, et al.  Gpt-neox-20b: An open-source autoregressive language model.  _arXiv preprint arXiv:2204.06745_ , 2022.
  * Bošnjak et al. [2017] Matko Bošnjak, Tim Rocktäschel, Jason Naradowsky, and Sebastian Riedel.  Programming with a differentiable forth interpreter.  In _International conference on machine learning_ , pages 547–556. PMLR, 2017.
  * Brockschmidt et al. [2018] Marc Brockschmidt, Miltiadis Allamanis, Alexander L Gaunt, and Oleksandr Polozov.  Generative code modeling with graphs.  _arXiv preprint arXiv:1805.08490_ , 2018.
  * Brown et al. [2020] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Bunel et al. [2018] Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli.  Leveraging grammar and reinforcement learning for neural program synthesis.  _arXiv preprint arXiv:1805.04276_ , 2018.
  * Cassano et al. [2022] Federico Cassano, John Gouwar, Daniel Nguyen, Sydney Nguyen, Luna Phipps-Costin, Donald Pinckney, Ming Ho Yee, Yangtian Zi, Carolyn Jane Anderson, Molly Q Feldman, et al.  A scalable and extensible approach to benchmarking nl2code for 18 programming languages.  _arXiv preprint arXiv:2208.08227_ , 2022.
  * Chaudhuri et al. [2021] Swarat Chaudhuri, Kevin Ellis, Oleksandr Polozov, Rishabh Singh, Armando Solar-Lezama, Yisong Yue, et al.  Neurosymbolic programming.  _Foundations and Trends® in Programming Languages_ , 7(3):158–243, 2021.
  * Chen et al. [2023] Angelica Chen, Jérémy Scheurer, Tomasz Korbak, Jon Ander Campos, Jun Shern Chan, Samuel R Bowman, Kyunghyun Cho, and Ethan Perez.  Improving code generation by training with natural language feedback.  _arXiv preprint arXiv:2303.16749_ , 2023.
  * Chen et al. [2021] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al.  Evaluating large language models trained on code.  _arXiv preprint arXiv:2107.03374_ , 2021.
  * Chen and Lampouras [2023] Pinzhen Chen and Gerasimos Lampouras.  Exploring data augmentation for code generation tasks.  _arXiv preprint arXiv:2302.03499_ , 2023.
  * Chen et al. [2018a] Xinyun Chen, Chang Liu, and Dawn Song.  Execution-guided neural program synthesis.  In _International Conference on Learning Representations_ , 2018a.
  * Chen et al. [2018b] Xinyun Chen, Chang Liu, and Dawn Song.  Tree-to-tree neural networks for program translation.  _Advances in neural information processing systems_ , 31, 2018b.
  * Cheng et al. [2022] Zhoujun Cheng, Tianbao Xie, Peng Shi, Chengzu Li, Rahul Nadkarni, Yushi Hu, Caiming Xiong, Dragomir Radev, Mari Ostendorf, Luke Zettlemoyer, et al.  Binding language models in symbolic languages.  _arXiv preprint arXiv:2210.02875_ , 2022.
  * Cho et al. [2014] Kyunghyun Cho, Bart Van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio.  On the properties of neural machine translation: Encoder-decoder approaches.  _arXiv preprint arXiv:1409.1259_ , 2014.
  * Chung et al. [2016] Junyoung Chung, Kyunghyun Cho, and Yoshua Bengio.  A character-level decoder without explicit segmentation for neural machine translation.  _arXiv preprint arXiv:1603.06147_ , 2016.
  * Currey et al. [2017] Anna Currey, Antonio Valerio Miceli-Barone, and Kenneth Heafield.  Copied monolingual data improves low-resource neural machine translation.  In _Proceedings of the second conference on machine translation_ , pages 148–156, 2017.
  * Dao et al. [2022a] Tri Dao, Daniel Y Fu, Stefano Ermon, Atri Rudra, and Christopher Ré.  Flashattention: Fast and memory-efficient exact attention with io-awareness.  _arXiv preprint arXiv:2205.14135_ , 2022a.
  * Dao et al. [2022b] Tri Dao, Daniel Y Fu, Khaled K Saab, Armin W Thomas, Atri Rudra, and Christopher Ré.  Hungry hungry hippos: Towards language modeling with state space models.  _arXiv preprint arXiv:2212.14052_ , 2022b.
  * Devlin et al. [2017] Jacob Devlin, Jonathan Uesato, Rishabh Singh, and Pushmeet Kohli.  Semantic code repair using neuro-symbolic transformation networks.  _arXiv preprint arXiv:1710.11054_ , 2017.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Dharma [2021] KC Dharma.  Policy gradient methods in reinforcement learning: Summary.  _Policy_ , (1/19), 2021.
  * Dharma et al. [2023] KC Dharma, Clayton T Morrison, and Bradley Walls.  Texture generation using a graph generative adversarial network and differentiable rendering.  In _Image and Vision Computing: 37th International Conference, IVCNZ 2022, Auckland, New Zealand, November 24–25, 2022, Revised Selected Papers_ , pages 388–401. Springer, 2023.
  * Dong and Lapata [2018] Li Dong and Mirella Lapata.  Coarse-to-fine decoding for neural semantic parsing.  _arXiv preprint arXiv:1805.04793_ , 2018.
  * Dong et al. [2023] Yihong Dong, Jiazheng Ding, Xue Jiang, Zhuo Li, Ge Li, and Zhi Jin.  Codescore: Evaluating code generation by learning code execution.  _arXiv preprint arXiv:2301.09043_ , 2023.
  * Doucet et al. [2001] Arnaud Doucet, Nando de Freitas, and Neil Gordon.  An introduction to sequential monte carlo methods.  In _Sequential Monte Carlo methods in practice_ , pages 3–14. Springer, 2001.
  * Drain et al. [2021] Dawn Drain, Chen Wu, Alexey Svyatkovskiy, and Neel Sundaresan.  Generating bug-fixes using pretrained transformers.  In _Proceedings of the 5th ACM SIGPLAN International Symposium on Machine Programming_ , pages 1–8, 2021.
  * Ellis et al. [2019] Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama.  Write, execute, assess: Program synthesis with a repl.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Ellis et al. [2020] Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, and Joshua B Tenenbaum.  Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning.  _arXiv preprint arXiv:2006.08381_ , 2020.
  * Ellis et al. [2018] Kevin M Ellis, Lucas E Morales, Mathias Sablé-Meyer, Armando Solar Lezama, and Joshua B Tenenbaum.  Library learning for neurally-guided bayesian program induction.  2018\.
  * Fan et al. [2018] Angela Fan, Mike Lewis, and Yann Dauphin.  Hierarchical neural story generation.  _arXiv preprint arXiv:1805.04833_ , 2018.
  * Feng et al. [2021] Steven Y Feng, Varun Gangal, Jason Wei, Sarath Chandar, Soroush Vosoughi, Teruko Mitamura, and Eduard Hovy.  A survey of data augmentation approaches for nlp.  _arXiv preprint arXiv:2105.03075_ , 2021.
  * Feng et al. [2020] Zhangyin Feng, Daya Guo, Duyu Tang, Nan Duan, Xiaocheng Feng, Ming Gong, Linjun Shou, Bing Qin, Ting Liu, Daxin Jiang, et al.  Codebert: A pre-trained model for programming and natural languages.  _arXiv preprint arXiv:2002.08155_ , 2020.
  * Feser et al. [2015] John K Feser, Swarat Chaudhuri, and Isil Dillig.  Synthesizing data structure transformations from input-output examples.  _ACM SIGPLAN Notices_ , 50(6):229–239, 2015.
  * Freitag and Al-Onaizan [2017] Markus Freitag and Yaser Al-Onaizan.  Beam search strategies for neural machine translation.  _arXiv preprint arXiv:1702.01806_ , 2017.
  * Fried et al. [2022] Daniel Fried, Armen Aghajanyan, Jessy Lin, Sida Wang, Eric Wallace, Freda Shi, Ruiqi Zhong, Wen-tau Yih, Luke Zettlemoyer, and Mike Lewis.  Incoder: A generative model for code infilling and synthesis.  _arXiv preprint arXiv:2204.05999_ , 2022.
  * Fu et al. [2019] Cheng Fu, Huili Chen, Haolan Liu, Xinyun Chen, Yuandong Tian, Farinaz Koushanfar, and Jishen Zhao.  Coda: An end-to-end neural program decompiler.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Gao et al. [2022] Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig.  Pal: Program-aided language models.  _arXiv preprint arXiv:2211.10435_ , 2022.
  * Garcez and Lamb [2023] Artur d’Avila Garcez and Luís C. Lamb.  Neurosymbolic AI: the 3rd wave.  _Artificial Intelligence Review_ , March 2023.  ISSN 0269-2821, 1573-7462.  doi: 10.1007/s10462-023-10448-w.  URL https://link.springer.com/10.1007/s10462-023-10448-w.
  * Gottschlich et al. [2018] Justin Gottschlich, Armando Solar-Lezama, Nesime Tatbul, Michael Carbin, Martin Rinard, Regina Barzilay, Saman Amarasinghe, Joshua B Tenenbaum, and Tim Mattson.  The three pillars of machine programming.  In _Proceedings of the 2nd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages_ , pages 69–80, 2018.
  * Graves et al. [2014] Alex Graves, Greg Wayne, and Ivo Danihelka.  Neural turing machines.  _arXiv preprint arXiv:1410.5401_ , 2014.
  * Graves et al. [2016] Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska-Barwińska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al.  Hybrid computing using a neural network with dynamic external memory.  _Nature_ , 538(7626):471–476, 2016.
  * Green [1981] Cordell Green.  Application of theorem proving to problem solving.  In _Readings in Artificial Intelligence_ , pages 202–222. Elsevier, 1981.
  * Gu et al. [2020] Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré.  Hippo: Recurrent memory with optimal polynomial projections.  _Advances in neural information processing systems_ , 33:1474–1487, 2020.
  * Gu et al. [2021a] Albert Gu, Karan Goel, and Christopher Ré.  Efficiently modeling long sequences with structured state spaces.  _arXiv preprint arXiv:2111.00396_ , 2021a.
  * Gu et al. [2021b] Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher Ré.  Combining recurrent, convolutional, and continuous-time models with linear state space layers.  _Advances in neural information processing systems_ , 34:572–585, 2021b.
  * Gu et al. [2016] Jiatao Gu, Zhengdong Lu, Hang Li, and Victor OK Li.  Incorporating copying mechanism in sequence-to-sequence learning.  _arXiv preprint arXiv:1603.06393_ , 2016.
  * Gulwani [2011] Sumit Gulwani.  Automating string processing in spreadsheets using input-output examples.  _ACM Sigplan Notices_ , 46(1):317–330, 2011.
  * Gulwani et al. [2017] Sumit Gulwani, Oleksandr Polozov, Rishabh Singh, et al.  Program synthesis.  _Foundations and Trends® in Programming Languages_ , 4(1-2):1–119, 2017.
  * Guo et al. [2020] Daya Guo, Shuo Ren, Shuai Lu, Zhangyin Feng, Duyu Tang, Shujie Liu, Long Zhou, Nan Duan, Alexey Svyatkovskiy, Shengyu Fu, et al.  Graphcodebert: Pre-training code representations with data flow.  _arXiv preprint arXiv:2009.08366_ , 2020.
  * Guo et al. [2022] Daya Guo, Shuai Lu, Nan Duan, Yanlin Wang, Ming Zhou, and Jian Yin.  Unixcoder: Unified cross-modal pre-training for code representation.  _arXiv preprint arXiv:2203.03850_ , 2022.
  * Gupta et al. [2017] Rahul Gupta, Soham Pal, Aditya Kanade, and Shirish Shevade.  Deepfix: Fixing common c language errors by deep learning.  In _Thirty-First AAAI conference on artificial intelligence_ , 2017\.
  * Hamilton [2020] William L. Hamilton.  Graph representation learning.  _Synthesis Lectures on Artificial Intelligence and Machine Learning_ , 14(3):1–159, 2020.
  * Hashimoto et al. [2018] Tatsunori B Hashimoto, Kelvin Guu, Yonatan Oren, and Percy S Liang.  A retrieve-and-edit framework for predicting structured outputs.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Hendrycks et al. [2021] Dan Hendrycks, Steven Basart, Saurav Kadavath, Mantas Mazeika, Akul Arora, Ethan Guo, Collin Burns, Samir Puranik, Horace He, Dawn Song, et al.  Measuring coding challenge competence with apps.  _arXiv preprint arXiv:2105.09938_ , 2021.
  * Hindle et al. [2016] Abram Hindle, Earl T Barr, Mark Gabel, Zhendong Su, and Premkumar Devanbu.  On the naturalness of software.  _Communications of the ACM_ , 59(5):122–131, 2016\.
  * Hochreiter [1998] Sepp Hochreiter.  The vanishing gradient problem during learning recurrent neural nets and problem solutions.  _International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems_ , 6(02):107–116, 1998.
  * Hochreiter and Schmidhuber [1997] Sepp Hochreiter and Jürgen Schmidhuber.  Long short-term memory.  _Neural computation_ , 9(8):1735–1780, 1997.
  * Holtzman et al. [2019] Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi.  The curious case of neural text degeneration.  _arXiv preprint arXiv:1904.09751_ , 2019.
  * Hu et al. [2022] Yaojie Hu, Xingjian Shi, Qiang Zhou, and Lee Pike.  Fix bugs with transformer through a neural-symbolic edit grammar.  _arXiv preprint arXiv:2204.06643_ , 2022.
  * Husain et al. [2019] Hamel Husain, Ho-Hsiang Wu, Tiferet Gazit, Miltiadis Allamanis, and Marc Brockschmidt.  Codesearchnet challenge: Evaluating the state of semantic code search.  _arXiv preprint arXiv:1909.09436_ , 2019.
  * Iyer et al. [2018] Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, and Luke Zettlemoyer.  Mapping language to code in programmatic context.  _arXiv preprint arXiv:1808.09588_ , 2018.
  * Jain et al. [2020] Paras Jain, Ajay Jain, Tianjun Zhang, Pieter Abbeel, Joseph E Gonzalez, and Ion Stoica.  Contrastive code representation learning.  _arXiv preprint arXiv:2007.04973_ , 2020.
  * Jean et al. [2014] Sébastien Jean, Kyunghyun Cho, Roland Memisevic, and Yoshua Bengio.  On using very large target vocabulary for neural machine translation.  _arXiv preprint arXiv:1412.2007_ , 2014.
  * Jiang et al. [2021] Xue Jiang, Zhuoran Zheng, Chen Lyu, Liang Li, and Lei Lyu.  Treebert: A tree-based pre-trained model for programming language.  In _Uncertainty in Artificial Intelligence_ , pages 54–63. PMLR, 2021\.
  * Jiang et al. [2023] Xue Jiang, Yihong Dong, Lecheng Wang, Qiwei Shang, and Ge Li.  Self-planning code generation with large language model.  _arXiv preprint arXiv:2303.06689_ , 2023.
  * Jordan [1997] Michael I Jordan.  Serial order: A parallel distributed processing approach.  In _Advances in psychology_ , volume 121, pages 471–495. Elsevier, 1997.
  * Kaiser and Sutskever [2015] Łukasz Kaiser and Ilya Sutskever.  Neural gpus learn algorithms.  _arXiv preprint arXiv:1511.08228_ , 2015.
  * Kanade et al. [2020] Aditya Kanade, Petros Maniatis, Gogul Balakrishnan, and Kensen Shi.  Learning and evaluating contextual embedding of source code.  In _International Conference on Machine Learning_ , pages 5110–5121. PMLR, 2020.
  * Katz et al. [2018] Deborah S Katz, Jason Ruchti, and Eric Schulte.  Using recurrent neural networks for decompilation.  In _2018 IEEE 25th International Conference on Software Analysis, Evolution and Reengineering (SANER)_ , pages 346–356. IEEE, 2018.
  * Katz et al. [2019] Omer Katz, Yuval Olshaker, Yoav Goldberg, and Eran Yahav.  Towards neural decompilation.  _arXiv preprint arXiv:1905.08325_ , 2019.
  * Kipf and Welling [2016] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Kocetkov et al. [2022] Denis Kocetkov, Raymond Li, Loubna Ben Allal, Jia Li, Chenghao Mou, Carlos Muñoz Ferrandis, Yacine Jernite, Margaret Mitchell, Sean Hughes, Thomas Wolf, et al.  The stack: 3 tb of permissively licensed source code.  _arXiv preprint arXiv:2211.15533_ , 2022.
  * Konda and Tsitsiklis [1999] Vijay Konda and John Tsitsiklis.  Actor-critic algorithms.  _Advances in neural information processing systems_ , 12, 1999.
  * Kudo and Richardson [2018] Taku Kudo and John Richardson.  Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing.  _arXiv preprint arXiv:1808.06226_ , 2018.
  * Kulal et al. [2019] Sumith Kulal, Panupong Pasupat, Kartik Chandra, Mina Lee, Oded Padon, Alex Aiken, and Percy S Liang.  Spoc: Search-based pseudocode to code.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Kurach et al. [2015] Karol Kurach, Marcin Andrychowicz, and Ilya Sutskever.  Neural random-access machines.  _arXiv preprint arXiv:1511.06392_ , 2015.
  * Lachaux et al. [2020] Marie-Anne Lachaux, Baptiste Roziere, Lowik Chanussot, and Guillaume Lample.  Unsupervised translation of programming languages.  _arXiv preprint arXiv:2006.03511_ , 2020.
  * Lai et al. [2022] Yuhang Lai, Chengxi Li, Yiming Wang, Tianyi Zhang, Ruiqi Zhong, Luke Zettlemoyer, Scott Wen-tau Yih, Daniel Fried, Sida Wang, and Tao Yu.  Ds-1000: A natural and reliable benchmark for data science code generation.  _arXiv preprint arXiv:2211.11501_ , 2022.
  * Le et al. [2022] Hung Le, Yue Wang, Akhilesh Deepak Gotmare, Silvio Savarese, and Steven CH Hoi.  Coderl: Mastering code generation through pretrained models and deep reinforcement learning.  _arXiv preprint arXiv:2207.01780_ , 2022.
  * Le et al. [2020] Triet HM Le, Hao Chen, and Muhammad Ali Babar.  Deep learning for source code modeling and generation: Models, applications, and challenges.  _ACM Computing Surveys (CSUR)_ , 53(3):1–38, 2020\.
  * LeCun et al. [1995] Yann LeCun, Yoshua Bengio, et al.  Convolutional networks for images, speech, and time series.  _The handbook of brain theory and neural networks_ , 3361(10):1995, 1995.
  * Lee et al. [2021] Celine Lee, Justin Gottschlich, and Dan Roth.  Toward code generation: A survey and lessons from semantic parsing.  _arXiv preprint arXiv:2105.03317_ , 2021.
  * Lewis et al. [2019] Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer.  Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  _arXiv preprint arXiv:1910.13461_ , 2019.
  * Li et al. [2022a] Haau-Sing Li, Mohsen Mesgar, André FT Martins, and Iryna Gurevych.  Asking clarification questions for code generation in general-purpose programming language.  _arXiv preprint arXiv:2212.09885_ , 2022a.
  * Li et al. [2023] Jia Li, Yongmin Li, Ge Li, Zhi Jin, Yiyang Hao, and Xing Hu.  Skcoder: A sketch-based approach for automatic code generation.  _arXiv preprint arXiv:2302.06144_ , 2023.
  * Li et al. [2017] Jian Li, Yue Wang, Michael R Lyu, and Irwin King.  Code completion with neural attention and pointer networks.  _arXiv preprint arXiv:1711.09573_ , 2017.
  * Li et al. [2022b] Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, et al.  Competition-level code generation with alphacode.  _arXiv preprint arXiv:2203.07814_ , 2022b.
  * Liang et al. [2021] Ruigang Liang, Ying Cao, Peiwei Hu, and Kai Chen.  Neutron: an attention-based neural decompiler.  _Cybersecurity_ , 4(1):1–13, 2021.
  * Lin et al. [2017] Xi Victoria Lin, Chenglong Wang, Deric Pang, Kevin Vu, and Michael D Ernst.  Program synthesis from natural language using recurrent neural networks.  _University of Washington Department of Computer Science and Engineering, Seattle, WA, USA, Tech. Rep. UW-CSE-17-03-01_ , 2017.
  * Lin et al. [2018] Xi Victoria Lin, Chenglong Wang, Luke Zettlemoyer, and Michael D Ernst.  Nl2bash: A corpus and semantic parser for natural language interface to the linux operating system.  _arXiv preprint arXiv:1802.08979_ , 2018.
  * Ling et al. [2015] Wang Ling, Isabel Trancoso, Chris Dyer, and Alan W Black.  Character-based neural machine translation.  _arXiv preprint arXiv:1511.04586_ , 2015.
  * Ling et al. [2016] Wang Ling, Edward Grefenstette, Karl Moritz Hermann, Tomáš Kočiskỳ, Andrew Senior, Fumin Wang, and Phil Blunsom.  Latent predictor networks for code generation.  _arXiv preprint arXiv:1603.06744_ , 2016.
  * Liu et al. [2016] Chang Liu, Xin Wang, Richard Shin, Joseph E Gonzalez, and Dawn Song.  Neural code completion.  2016\.
  * Lu et al. [2021a] Shuai Lu, Daya Guo, Shuo Ren, Junjie Huang, Alexey Svyatkovskiy, Ambrosio Blanco, Colin Clement, Dawn Drain, Daxin Jiang, Duyu Tang, et al.  Codexglue: A machine learning benchmark dataset for code understanding and generation.  _arXiv preprint arXiv:2102.04664_ , 2021a.
  * Lu et al. [2020] Ximing Lu, Peter West, Rowan Zellers, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi.  Neurologic decoding:(un) supervised neural text generation with predicate logic constraints.  _arXiv preprint arXiv:2010.12884_ , 2020.
  * Lu et al. [2021b] Ximing Lu, Sean Welleck, Peter West, Liwei Jiang, Jungo Kasai, Daniel Khashabi, Ronan Le Bras, Lianhui Qin, Youngjae Yu, Rowan Zellers, et al.  Neurologic a* esque decoding: Constrained text generation with lookahead heuristics.  _arXiv preprint arXiv:2112.08726_ , 2021b.
  * Luong et al. [2014] Minh-Thang Luong, Ilya Sutskever, Quoc V Le, Oriol Vinyals, and Wojciech Zaremba.  Addressing the rare word problem in neural machine translation.  _arXiv preprint arXiv:1410.8206_ , 2014.
  * Luong et al. [2015] Minh-Thang Luong, Hieu Pham, and Christopher D Manning.  Effective approaches to attention-based neural machine translation.  _arXiv preprint arXiv:1508.04025_ , 2015.
  * Madaan et al. [2023] Aman Madaan, Alexander Shypula, Uri Alon, Milad Hashemi, Parthasarathy Ranganathan, Yiming Yang, Graham Neubig, and Amir Yazdanbakhsh.  Learning performance-improving code edits.  _arXiv preprint arXiv:2302.07867_ , 2023.
  * Manna and Waldinger [1971] Zohar Manna and Richard J Waldinger.  Toward automatic program synthesis.  _Communications of the ACM_ , 14(3):151–165, 1971\.
  * Mielke et al. [2021] Sabrina J Mielke, Zaid Alyafeai, Elizabeth Salesky, Colin Raffel, Manan Dey, Matthias Gallé, Arun Raja, Chenglei Si, Wilson Y Lee, Benoît Sagot, et al.  Between words and characters: A brief history of open-vocabulary modeling and tokenization in nlp.  _arXiv preprint arXiv:2112.10508_ , 2021.
  * Mikolov et al. [2013] Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  Efficient estimation of word representations in vector space.  _arXiv preprint arXiv:1301.3781_ , 2013.
  * Mnih et al. [2016] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.  Asynchronous methods for deep reinforcement learning.  In _International conference on machine learning_ , pages 1928–1937. PMLR, 2016.
  * Mou et al. [2016] Lili Mou, Ge Li, Lu Zhang, Tao Wang, and Zhi Jin.  Convolutional neural networks over tree structures for programming language processing.  In _Thirtieth AAAI conference on artificial intelligence_ , 2016.
  * Ni et al. [2023] Ansong Ni, Srini Iyer, Dragomir Radev, Ves Stoyanov, Wen-tau Yih, Sida I Wang, and Xi Victoria Lin.  Lever: Learning to verify language-to-code generation with execution.  _arXiv preprint arXiv:2302.08468_ , 2023.
  * Nijkamp et al. [2022a] Erik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, Silvio Savarese, and Caiming Xiong.  Codegen: An open large language model for code with multi-turn program synthesis.  _arXiv preprint arXiv:2203.13474_ , 2022a.
  * Nijkamp et al. [2022b] Erik Nijkamp, Bo Pang, Hiroaki Hayashi, Lifu Tu, Huan Wang, Yingbo Zhou, Silvio Savarese, and Caiming Xiong.  A conversational paradigm for program synthesis.  _arXiv preprint arXiv:2203.13474_ , 2022b.
  * Niu et al. [2022] Changan Niu, Chuanyi Li, Vincent Ng, Jidong Ge, Liguo Huang, and Bin Luo.  Spt-code: sequence-to-sequence pre-training for learning source code representations.  In _Proceedings of the 44th International Conference on Software Engineering_ , pages 2006–2018, 2022.
  * Nye et al. [2019] Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar-Lezama.  Learning to infer program sketches.  In _International Conference on Machine Learning_ , pages 4861–4870. PMLR, 2019.
  * Ouyang et al. [2022] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744, 2022.
  * Papineni et al. [2002] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th annual meeting of the Association for Computational Linguistics_ , pages 311–318, 2002.
  * Pascanu et al. [2013] Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio.  On the difficulty of training recurrent neural networks.  In _International conference on machine learning_ , pages 1310–1318. PMLR, 2013.
  * Puri et al. [2021] Ruchir Puri, David S Kung, Geert Janssen, Wei Zhang, Giacomo Domeniconi, Vladimir Zolotov, Julian Dolby, Jie Chen, Mihir Choudhury, Lindsey Decker, et al.  Codenet: A large-scale ai for code dataset for learning a diversity of coding tasks.  _arXiv preprint arXiv:2105.12655_ , 2021.
  * Rabinovich et al. [2017] Maxim Rabinovich, Mitchell Stern, and Dan Klein.  Abstract syntax networks for code generation and semantic parsing.  _arXiv preprint arXiv:1704.07535_ , 2017.
  * Radford et al. [2018] Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al.  Improving language understanding by generative pre-training.  2018\.
  * Raffel et al. [2020] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, Peter J Liu, et al.  Exploring the limits of transfer learning with a unified text-to-text transformer.  _J. Mach. Learn. Res._ , 21(140):1–67, 2020.
  * Rai and Borah [2021] Abigail Rai and Samarjeet Borah.  Study of various methods for tokenization.  In _Applications of Internet of Things_ , pages 193–200. Springer, 2021.
  * Rajkumar et al. [2022] Nitarshan Rajkumar, Raymond Li, and Dzmitry Bahdanau.  Evaluating the text-to-sql capabilities of large language models.  _arXiv preprint arXiv:2204.00498_ , 2022.
  * Ranzato et al. [2015] Marc’Aurelio Ranzato, Sumit Chopra, Michael Auli, and Wojciech Zaremba.  Sequence level training with recurrent neural networks.  _arXiv preprint arXiv:1511.06732_ , 2015.
  * Raychev et al. [2016] Veselin Raychev, Pavol Bielik, and Martin Vechev.  Probabilistic model for code with decision trees.  _ACM SIGPLAN Notices_ , 51(10):731–747, 2016\.
  * Reed and De Freitas [2015] Scott Reed and Nando De Freitas.  Neural programmer-interpreters.  _arXiv preprint arXiv:1511.06279_ , 2015.
  * Ren et al. [2020] Shuo Ren, Daya Guo, Shuai Lu, Long Zhou, Shujie Liu, Duyu Tang, Neel Sundaresan, Ming Zhou, Ambrosio Blanco, and Shuai Ma.  Codebleu: a method for automatic evaluation of code synthesis.  _arXiv preprint arXiv:2009.10297_ , 2020.
  * Ross et al. [2023] Steven I Ross, Fernando Martinez, Stephanie Houde, Michael Muller, and Justin D Weisz.  The programmer’s assistant: Conversational interaction with a large language model for software development.  _arXiv preprint arXiv:2302.07080_ , 2023.
  * Roziere et al. [2021] Baptiste Roziere, Marie-Anne Lachaux, Marc Szafraniec, and Guillaume Lample.  Dobf: A deobfuscation pre-training objective for programming languages.  _arXiv preprint arXiv:2102.07492_ , 2021.