Title: TREE-TO-TREE NEURAL NETWORKS FOR PROGRAM TRANSLATION

Abstract: Program translation is an important tool to migrate legacy code in one language into an ecosystem built in a different language. In this work, we are the first to consider employing deep neural networks toward tackling this problem. We observe that program translation is a modular procedure, in which a sub-tree of the source tree is translated into the corresponding target sub-tree at each step. To capture this intuition, we design a tree-to-tree neural network as an encoderdecoder architecture to translate a source tree into a target one. Meanwhile, we develop an attention mechanism for the tree-to-tree model, so that when the decoder expands one non-terminal in the target tree, the attention mechanism locates the corresponding sub-tree in the source tree to guide the expansion of the decoder. We evaluate the program translation capability of our tree-to-tree model against several state-of-the-art approaches. Compared against other neural translation models, we observe that our approach is consistently better than the baselines with a margin of up to 15 points. Further, our approach can improve the previous state-of-the-art program translation approaches by a margin of 20 points on the translation of real-world projects.

1. INTRODUCTION:

Programs are the main tool for building computer applications, the IT industry, and the digital world. Various programming languages have been invented to facilitate programmers to develop programs for different applications. At the same time, the variety of different programming languages also introduces a burden when programmers want to combine programs written in different languages together. Therefore, there is a tremendous need to enable program translation between different programming languages.

Nowadays, to translate programs between different programming languages, typically programmers would manually investigate the correspondence between the grammars of the two languages, then develop a rule-based translator. However, this process can be inefficient and error-prone. In this work, we make the first attempt to examine whether we can leverage deep neural networks to build a program translator automatically.

Intuitively, the program translation problem in its format is similar to a natural language translation problem. Some previous work propose to adapt phrase-based statistical machine translation approaches (SMT) for code migration (Nguyen et al., 2013; Karaivanov et al., 2014; Nguyen et al., 2015) . Recently, neural network approaches, such as sequence-to-sequence-based models (Bahdanau et al., 2015; Cho et al., 2015; Eriguchi et al., 2016; He et al., 2016; Vaswani et al., 2017) , have achieved the state-of-the-art performance on machine translation. In this work, we study neural machine translation methods to handle the program translation problem. However, a big challenge making a sequence-to-sequence-based model ineffective is that, unlike natural languages, programming languages have rigorous grammars and are not tolerant to typos and grammatical mistakes. It has been demonstrated that it is very hard for an RNN-based sequence generator to generate syntactically correct programs when the lengths grow large (Karpathy et al., 2015) .

In this work, we observe that the main issue of an RNN that makes it hard to produce syntactically correct programs is that it entangles two sub-tasks together: (1) learning the grammar; and (2) aligning the sequence with the grammar. When these two tasks can be handled separately, the performance can typically boost. For example, Dong & Lapata (2016) employs a tree-based decoder to separate the two tasks. In particular, the decoder in (Dong & Lapata, 2016) leverages the tree structural information to (1) generate the nodes at the same depth of the parse tree using an LSTM decoder; and (2) expand a non-terminal and generate its children in the parse tree. Such an approach has been demonstrated to achieve the state-of-the-art results on several semantic parsing tasks.

Inspired by this observation, we hypothesize that the structural information in both input and output parse trees can be leveraged to enable such a separation. Inspired by this intuition, we propose tree-to-tree neural networks to combine both a tree encoder and a tree decoder. In particular, we observe that in the program translation problem, both input and output programs have their parse trees. In addition, a cross-language compiler typically follows a modular procedure to translate the individual sub-components in the source tree into their corresponding target ones, and then compose them to form the final target tree. Therefore, we design the workflow of a tree-to-tree neural network to align with this procedure: 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 sub-tree to guide the non-terminal expansion. In particular, a tree encoder is helpful in this scenario, since it can aggregate all information of a sub-tree to the embedding of its root, so that the embedding can be used to guide the non-terminal expansion of the target tree.

We follow the above intuition to design the tree-to-tree translation model. Existing works (Socher et al., 2011b; Kusner et al., 2017) have proposed tree-based autoencoder architectures. However, in these models, the decoder can only access to a single hidden vector representing the source tree, thus they are not performant in the translation task. In contrast, we employ an attention mechanism for the decoder to access the source tree, so that our approach can significantly improve the translation performance (i.e., from 0% to > 90%). To the best of our knowledge, this is the first tree-to-tree neural network architecture proposed for translation tasks in the literature.

To test our hypothesis, we develop two novel program translation tasks, and employ a Java to C# benchmark used by existing program translation works (Nguyen et al., 2015; 2013) . First, we compare our approach against several neural network approaches on our proposed two tasks. Experimental results demonstrate that our tree-to-tree model outperforms other state-of-the-art neural networks on the program translation tasks, and yields a margin of up to 5% on the token accuracy and up to 15% on the program accuracy. Further, we compare our approach with previous program translation approaches on the Java to C# benchmark, and the results show that our tree-to-tree model outperforms previous state-of-the-art by a large margin of 20% on program accuracy. These results demonstrate that our tree-to-tree model is promising toward tackling the program translation problem. Meanwhile, we believe that our proposed tree-to-tree neural network could also be adapted to other tree-to-tree tasks, and we consider it as future work.

2. PROGRAM TRANSLATION PROBLEM:

In this work, we consider the problem of translating a program in one language into another. One approach is to model the problem as a machine translation problem between two languages, and thus numerous neural machine translation approaches can be applied.

For the program translation problem, however, a unique property is that each input program unambiguously corresponds to a unique parse tree. Thus, rather than modeling the input program as a sequence of tokens, we can consider the problem as translating a source tree into a target tree. Note that most modern programming languages are accompanied with a well-developed parser, so we can assume that the parse trees of both the source and the target programs can be easily obtained.

The main challenge of the problem in our consideration is that the cross-compiler for translating programs from one language into another typically does not exist. Therefore, even if we assume the existence of parsers for both the source and the target languages, the translation problem itself is still non-trivial. We formally define the problem as follows.

Definition 1 (Program translation). Given two programming languages L s and L t , each being a set of instances (p k , T k ), where p k is a program, and T k is its corresponding parse tree. We assume that there exists a translation oracle π, which maps instances in L s to instances in L t . Given a dataset of instance pairs (i s , i t ) such that i s ∈ L s , i t ∈ L t and π(i s ) = i t , our problem is to learn a function F that maps each i s ∈ L s into i t = π(i s ). Note that this problem definition does not restrict on whether F knows only the program p k or only the parse tree T k . Thus it can leverage both information to finish the translation task. Also, in the target language, since a program and its parse tree uniquely matches each other, F only needs to predict one of them to be correct.

In this definition, L s and L t are the source and target languages respectively, and we use the oracle π to model the goal of the translation. Notice that different tasks can be modeled with different choices of π. For example, besides program translation between two languages, we can also model the compiler optimization by setting L s = L t and choosing π that maps an un-optimized program into an optimized one.

In this work, we focus on the problem setting that we have a set of paired source and target programs to learn the translator. Note that all existing program translation works (Karaivanov et al., 2014; Nguyen et al., 2015; 2013) also study the problem under such an assumption. When such an alignment is lacking, the program translation problem is more challenging. Several techniques for NMT have been proposed to handle this issue, such as dual learning (He et al., 2016) , which have the potential to be extended for the program translation task. We leave these more challenging problem setups as future work.

3. TREE-TO-TREE NEURAL NETWORK:

In this section, we present our design of the tree-to-tree neural network. We first motivate the design, and then present the details.

3.1. PROGRAM TRANSLATION AS A TREE-TO-TREE TRANSLATION PROBLEM:

Figure 1 presents an example of translation from CoffeeScript to JavaScript. We observe several interesting properties of the program translation problem. First, the translation can be modular.

The figure highlights a sub-component in the source tree corresponding to x=1 and its translation in the target tree corresponding to x=1;. This correspondence is independent of other parts of the program. Consider when the program grows longer and this statement may repetitively occur multiple times, it may be hard for a sequence-to-sequence model to capture the correspondence based on only token sequences without structural information.

Second, such a correspondence makes it a natural solution to locate the referenced sub-tree in the source tree when expanding a non-terminal in the target tree into a sub-tree. Inspired by this intuition, we design the tree-to-tree neural network with attention, so that when decoding a non-terminal into a (sub-)tree, the model can employ an attention mechanism to locate the referenced source sub-tree. The soft-attention mechanism makes the model differentiable, so that it can be trained end-to-end. The black dotted arrow from the source tree root to the target tree root indicates that the LSTM state is copied. The green box denotes the expanding node, and the grey one denotes the node to be expanded in a queue. The sub-tree of the source tree corresponding to the expanding node is highlighted in yellow. The right corner lists the formulas to predict the token for the expanding node.

Third, although the corresponding sub-trees are analogues to each other, they differ in two aspects. On the one hand, the non-terminal nodes are different. For example, the non-terminal IdentifierLiteral in CoffeeScript is called Identifier in JavaScript. Some nonterminals, such as Value, may not even have a correspondence. On the other hand, the topology structures of the corresponding sub-trees can be different. For example, the Assign node in the source tree has two children, while its correspondence in the target tree has three: an additional = is inserted in the middle. These differences can pose a challenge to build a program translation model.

A tree-to-tree neural network follows an encoder-decoder framework to encode the source tree into an embedding, and decode the embedding into the target tree. To capture the intuition of the modular translation process, the decoder employs an (soft) attention mechanism to locate the corresponding source sub-tree when expanding the non-terminal. We illustrate the workflow of a tree-to-tree model in Figure 2 . In the following, we present each component of the model.

Converting a tree into a binary one. Note that the input and output trees may contain multiple branches. Although we can design tree-encoders and tree-decoders to handle trees with arbitrary number of branches, we observe that encoder and decoder for binary trees can be more effective. Thus, the first step is to convert both the source tree and the target tree into a binary tree. To this end, we employ the Left-Child Right-Sibling representation for this conversion.

Binary tree encoder. The encoder employs a Tree-LSTM (Tai et al. ( 2015)) to compute embeddings for both the entire tree and each sub-tree. In particular, consider a node N that is attached with a token t s in its one-hot encoding representation, and it has two children N L and N R , which are its left child and right child respectively. The encoder recursively computes the embedding for N from the bottom up.

Assume that the left child and the right child maintain the LSTM state (h L , c L ) and (h R , c R ) respectively. Then the LSTM state (h, c) of N is computed as

EQUATION

where [a; b] indicates the concatenation of two vectors a and b. Note that a node may lack one or both of its children. In this case, the encoder sets the LSTM state of the missing child to be zero.

Binary tree decoder. The decoder generates the target tree starting from a single root node. The decoder first copies the LSTM state (h, c) of the root of the source tree, and attaches it to the root node of the target tree. Then the decoder maintains a queue of all nodes to be expanded, and recursively expands each of them. In each iteration, the decoder pops one node from the queue, and expands it. In the following, we call the node being expanded the expanding node.

First, the decoder will predict the token of expanding node. To this end, the decoder computes the embedding e t of the expanding node N , and then feeds it into a softmax regression network for prediction:

t t = argmax softmax(W e t )

(2) Here, W is a trainable matrix of size V t × d, where V t is the vocabulary size of the outputs and d is the embedding dimension. Note that e t is computed using the attention mechanism, which we will explain later.

Each token t t is a non-terminal, a terminal, or a special EOS token. If t t = EOS , then the decoder finishes expanding this node. Otherwise, the decoder generates one new node as the left child and another new node as the right child of the expanding one. Assume that (h , c ), (h , c ) are the LSTM states of its left child and right child respectively, then they are computed as:

(h , c ) = LSTM L ((h, c), Bt t ) (3) (h , c ) = LSTM R ((h, c), Bt t )

(4) Here, B is a trainable word embedding matrix of size d×V t . Note that the generation of the left child and right child use two different sets of parameters for LSTM L and LSTM R respectively. These new children are pushed into the queue of all nodes to be expanded.

The target tree generation process terminates when the queue is empty.

Attention mechanism to locate the source sub-tree. Now we consider how to compute e t . One straightforward approach is to compute e t as h, which is the hidden state attached to the expanding node. However, in doing so, the embedding will soon forget the information about the source tree when generating deep nodes in the target tree, and thus the model yields a very poor performance.

To make better use of the information of the source tree, our tree-to-tree model employs an attention mechanism to locate the source sub-tree corresponding to the sub-tree rooted at the expanding node. Specifically, we compute the following probability: P (N s is the source sub-tree corresponding to N t |N t ) where N t is the expanding node. We denote this probability as P (N s |N t ), and we compute it as

EQUATION

) where W 0 is a trainable matrix of size d × d. To leverage the information from the source tree, the decoder can sample a source node N s following P (N s |N t ) or simply predict the most-likely source node N s = argmax Ns P (N s |N t ), and then get its hidden h s as e s . This embedding can then be combined with h, the hidden state of the expanding node, to compute e t as follows:

EQUATION

) where W 1 is a trainable matrix of size d × 2d, and [h; e s ] denotes the concatenation of h and e s .

However, this approach suffers a big issue that the entire network is no longer end-to-end differentiable unless explicit supervision is given to train P (N s |N t ). Unfortunately, this supervision is unavailable. We may rely on reinforcement learning algorithms to mitigate this issue, but doing so is expensive and may not be effective.

We solve this problem by changing the above hard-attention scheme to a soft-attention mechanism. Note that in Equation ( 6), we only need a continuous embedding vector e s rather than the discrete choice of N s . Therefore, we can approximate e s as the expectation of the hidden state value across all N s conditioning on N t . In fact, we have

EQUATION

Note that this final formula (7) coincides with the standard attention formalism. Combining all equations from (1) to ( 7), the entire tree-to-tree neural network is fully differentiable and can be trained end-to-end.

Source program Target program for:

i=1; i<10; i+1 do letrec f i = if x>1 then if i<10 then y=1 let = if x>1 then else let y=1 in () y=2

else let y=2 in () endfor in f i+1 else () in f 1 Figure 3 : An example of the translation for the synthetic task.

Parent attention feeding. In the above approach, the attention vectors e t are computed independently to each other, since once e t is used for predicting the token t t , e t is no longer used for further predictions. However, intuitively, the attention decisions for the prediction of each node should be related to each other. For example, for a non-terminal node N t in the target tree, suppose that it is related to N s in the source tree, then it is very likely that the attention weights of its children should focus on the descendants of N s . Therefore, when predicting the attention vector of a node, the model should leverage the attention information of its parent as well.

Following this intuition, we propose a parent attention feeding mechanism, so that the attention vector of the expanding node is taken into account when predicting the attention vectors of its children. Formally, besides the embedding of the token t t , we modify the inputs to LSTM L and LSTM R of the decoder in Equations ( 3) and (4) as below:

EQUATION

Notice that these formulas in their formats coincide with the input-feeding method for sequential neural networks (Luong et al., 2015) , but their meanings are different. For sequential models, the input attention vector belongs to the previous token, while here it belongs to the parent node.

4. EVALUATION:

In this section, we evaluate our tree-to-tree neural network with several baseline approaches on the program translation task. To do so, we first describe three benchmark datasets in Section 4.1 for evaluating different aspects. Then we evaluate our tree-to-tree model with several baseline approaches, including the state-of-the-art neural network approaches and program translation approaches. In the following, we start with presenting the details of the benchmark datasets and models, and then present the results.

4.1. DATASETS:

To evaluate different approaches for the program translation problem, we employ three tasks: (1) a synthetic translation task from an imperative language to a functional language; (2) translation between CoffeeScript and JavaScript, which are both full-fledged languages; and (3) translation of real-world projects from Java to C#, which has been used as a benchmark in the literature.

For the synthetic task, we design an imperative source language and a functional target language. Such a design makes the source and target languages use different programming paradigms, so that the translation can be challenging. Figure 3 illustrates an example of the translation, which demonstrates that a for-loop is translated into a recursive function. We manually implement a translator, which is used to acquire the ground truth. The formal grammars of the two languages and the implementation of the translator can be found in Appendix D.1 and Appendix E respectively .

For the CoffeeScript-JavaScript task, the programming paradigms of the two languages are identical. syntax. To control the program lengths of the training and test data, we develop a pCFG-based program generator and a subset of the core CoffeeScript grammar. We also limit the set of variables and literals to restrict the vocabulary size. We rely on the CoffeeScript compiler to generate the corresponding ground truth JavaScript programs. The grammar used to generate the programs in our experiments can be found in Appendix D.2 . In doing so, we can get a set of CoffeeScript-JavaScript pairs, and thus we can build a CoffeeScript-to-JavaScript dataset, and a JavaScript-to-CoffeeScript dataset by exchanging the source and the target.

For both of the above tasks, we randomly generate 100,000 pairs of source and target programs for training, 10,000 pairs as the development set, and 10,000 pairs for testing. More statistics of the above datasets can be found in Appendix B .

To build the Java to C# dataset, we employ the same approach as in (Nguyen et al., 2015) to crawl several open-source projects, which have both a Java and a C# implementation. Same as in (Nguyen et al., 2015) , we pair the methods in Java and C# based on their file names and method names. The statistics of the dataset is summarized in Table 1 . Due to the change of the versions of these projects, the concrete dataset in our evaluation may differ from (Nguyen et al., 2015) . We apply ten-fold validation for matched method pairs in each project, as in (Nguyen et al., 2015) .

4.2. METRICS:

In our evaluation, we measure the following two metrics:

• Token accuracy. Given a set of source programs, we run the evaluated model to translate them into target programs, and calculate the percentage of the tokens that can match the ground truth. • Program accuracy. Given a set of source programs, we run the evaluated model to translate them into target programs, and calculate the percentage of the predicted programs that can entirely match the ground truth.

Note that the program accuracy is an underestimation of the true accuracy based on semantic equivalence, and this metric has been used in (Nguyen et al., 2015) . This metric is more meaningful than other previously proposed metrics, such as syntax-correctness and dependency-graph-accuracy, which are not directly comparable to semantic equivalence. In addition, token accuracy can provide more insight into the performance of different models.

4.3. MODEL DETAILS:

We evaluate our tree-to-tree model against a sequence-to-sequence model (Bahdanau et al., 2015; Vinyals et al., 2015) , a sequence-to-tree model (Dong & Lapata, 2016) , and a tree-to-sequence model (Eriguchi et al., 2016) . Note that for a sequence-to-sequence model, there can be four variants to handle different input-output formats. For example, given a program, we can simply tokenize it into a sequence of tokens. We call this format as raw program, denoted as P. We can also use the parser to parse the program into a parse tree, and then serialize the parse tree as a sequence of tokens.

Our serialization of a tree follows its depth-first traversal order, which is the same as (Vinyals et al., 2015) . We call this format as parse tree, denoted as T. For both input and output formats, we can choose either P or T. Similarly, for a sequence-to-tree model, we have two variants based on its input format being either P or T, and for a tree-to-sequence model, we have two variants based on its output format being either P or T. Note that the sequence-to-tree model generates a tree as output, and thus requires its output format to be T (unserialized). For the same reason, the tree-to-sequence model requires its input format to be T (unserialized), and our tree-to-tree only has one form. Therefore, we have 9 different models in our evaluation.

The hyper-parameters used in different models can be found in Appendix A . The baseline models have employed their own input-feeding or parent-feeding method that is analogous to our parent attention feeding mechanism.

4.4. RESULTS ON THE SYNTHETIC TASK:

We create two datasets for the synthetic task: one with average length 20 (SYN-S) and the other with average length 50 (SYN-L). Here, the length of a program indicates the number of tokens in the source program.

The results are presented in Table 2 . We can observe that our tree2tree model outperforms all baseline models on both datasets and with both metrics. Especially, on the dataset with longer programs, the program accuracy significantly outperforms all seq2seq models by a large margin, i.e., > 85%. Its margin over a seq2tree model can also reach around 30 points. These results demonstrate that tree2tree model is more capable of learning the program translation relationship.

Notice that increasing the length of the programs indeed makes the problem harder: the program accuracy drops for all models. However, we observe that the decrease of our tree2tree model on the program accuracy is only around 2 points, which is much smaller than the decrease of other models. This shows that the tree2tree model is significantly better than other baselines at handling longer inputs.

In addition, we perform ablation study to compare the full tree2tree model with (1) tree2tree without parent attention feeding (T→T (-PF)) and (2) tree2tree without attention (T→T (-Attn)). We observe that the full tree2tree model significantly outperforms the other alternatives. In particular, on SYN-L, the full tree2tree's program accuracy is 40 points higher than the tree2tree model without parent attention feeding.

More importantly, we observe that the program accuracy of tree2tree model without the attention mechanism is always 0%. Note that such a model is similar to a tree-to-tree autoencoder architecture. This result shows that our novel architecture can significantly outperform previous tree-to-tree-like architectures on the program translation task.

4.5. RESULTS ON THE COFFEESCRIPT-JAVASCRIPT TASK:

We now move on to the CoffeeScript-JavaScript task. We create several datasets named as XY-ZW: X and Y (C or J) indicate the source and target language respectively; Z (A or B) indicates the vocabulary; and W (S or L) indicates the program length. In particular, vocabulary A uses only {x,y} as variable names and {0,1} as literals; vocabulary B uses all alphabetical characters as variable names, and all single digits as literals. S indicates that the CoffeeScript programs contain 10 tokens on average; and L for 20.

The program accuracy results are presented in Table 3 , and the token accuracy results can be found in Appendix A . Most of the observations from our synthetic task remain: our tree2tree model outperforms all baseline models; all models perform worse on longer inputs; both the attention and the parent attention feeding mechanisms boost the performance of our tree2tree model significantly.

In addition, we observe that for the translation from JavaScript to CoffeeScript, the improvements of the tree2tree model over the baselines are much smaller than for CoffeeScript to JavaScript translation. We attribute this to the fact that the target programs are much shorter. For example, for a CoffeeScript program with 20 tokens, its corresponding JavaScript program may contain more than 300 tokens. Thus, the model needs to predict much less tokens for a CoffeeScript program than a JavaScript program, so that even seq2seq models can achieve a reasonably good accuracy. However, still, we can observe that our tree2tree model outperforms all baselines.

4.6. RESULTS ON REAL-WORLD PROJECTS:

We now compare our approach with three state-of-the-art program translation approaches, i.e., J2C# (jav), 1pSMT (Nguyen et al., 2013), and mppSMT (Nguyen et al., 2015) , on the real-world benchmark from Java to C#. Here, J2C# is a rule-based system, 1pSMT directly applies the phrasebased SMT on sequential programs, and mppSMT is a multi-phase phrase-based SMT approach that leverages both the raw programs and their parse trees. Our approach handles the out-of-vocabulary problem by canonicalizing all variable names, literals and string constants. For example, the first variable in a program (and its subsequent references) is renamed as v1, the second as v2, etc. In this way, the dataset contains only a small set of variable names.

The results are summarized in Table 4 . For previous approaches, we report the results from (Nguyen et al., 2015) . We can observe that our tree2tree approach can significantly outperform the previous state-of-the-art on all projects except Antlr. The improvements range from 20.2% to 41.9%.

On Antlr, the tree2tree model performs worse. We attribute this to the fact that Antlr contains too few data samples for training. We test our hypothesis by constructing another training and validation set from all other 5 projects, and test the model on the entire Antlr. We observe that the model can achieve a test accuracy of 58.3%, which is 9 points higher than the state-of-the-art. Therefore, we conclude that our approach can significantly outperform previous program translation approaches when there are sufficient training data.

5. RELATED WORK:

Statistical approaches for program translation. Some recent work have applied statistical machine translation techniques to program translation (Allamanis et al., 2017; Karaivanov et al., 2014; Nguyen et al., 2015; 2013; 2016) . For example, several works propose to adapt phrase-based statistical machine translation models and leverage grammatical structures of programming languages for code migration (Karaivanov et al., 2014; Nguyen et al., 2015; 2013) . Nguyen et al. (2016) proposes to use Word2Vec representation for APIs in libraries used in different programming languages, then learns a transformation matrix for API mapping. On the contrary, our work is the first to employ deep learning techniques for program translation.

Neural networks with tree structures. In recent years, various neural networks with tree structures have been proposed to employ the structured information of the data (Dong & Lapata, 2016; Rabinovich et al., 2017; Parisotto et al., 2017; Yin & Neubig, 2017; Alvarez-Melis & Jaakkola, 2017; Tai et al., 2015; Zhu et al., 2015; Socher et al., 2011a; Eriguchi et al., 2016; Zhang et al., 2016; Socher et al., 2011b; Kusner et al., 2017) . In these work, different tree-structured encoders are proposed for embedding the input data, and different tree-structured decoders are proposed for predicting the output trees. In particular, in (Socher et al., 2011b; Kusner et al., 2017) , they propose tree-structured autoencoders to learn vector representations of trees, and show better performance on tree reconstruction and other tasks such as sentiment analysis. In this work, we are the first to design the tree-to-tree neural network for translation tasks.

Neural networks for parsing. Other work study using neural networks to generate parse trees from input-output examples (Dong & Lapata, 2016; Vinyals et al., 2015; Aharoni & Goldberg, 2017; Rabinovich et al., 2017; Yin & Neubig, 2017; Alvarez-Melis & Jaakkola, 2017; Dyer et al., 2016; Chen et al., 2018; 2016) . Dong & Lapata (2016) proposes a seq2tree model that allows the decoder RNN to generate the output tree recursively in a top-down fashion. This approach achieves the stateof-the-art results on several semantic parsing tasks. Some other work incorporate the knowledge of the grammar into the architecture design (Yin & Neubig, 2017; Rabinovich et al., 2017) to achieve better performance on specific tasks. However, these approaches are hard to generalize to other tasks. Again, none of them is designed for program translation or proposes a tree-to-tree architecture.

Neural networks for code generation. A recent line of research study using neural networks for code generation (Balog et al., 2017; Devlin et al., 2017; Parisotto et al., 2017; Ling et al., 2016; Rabinovich et al., 2017; Yin & Neubig, 2017) . In (Ling et al., 2016; Rabinovich et al., 2017; Yin & Neubig, 2017) , they study generating code in a DSL from inputs in natural language or in another DSL. However, their designs require additional manual efforts to adapt to new DSLs in consideration. In our work, we consider the tree-to-tree model as a generic approach that can be applied to any grammar.

6. CONCLUSION AND FUTURE WORK:

In this work, we are the first to consider neural network approaches for the program translation problem, and are the first to propose a tree-to-tree neural network that combines both a tree-RNN encoder and a tree-RNN decoder for translation tasks. Extensive evaluation demonstrates that our tree-to-tree neural network outperforms several state-of-the-art models, including neural networks for machine translation and statistical machine translation-based program translation approaches. This renders our tree-to-tree model as a promising tool toward tackling the program translation problem. In addition, we believe that our proposed tree-to-tree neural network has potential to generalize to other tree-to-tree tasks, and we consider it as future work.

At the same time, we observe many challenges on program translation that existing techniques are not capable of handling. For example, the models are hard to generalize to programs longer than the training ones; it is unclear how to handle an infinite vocabulary set that may be employed in real-world applications; further, the training requires a dataset of aligned input-output pairs, which may be lacking in practice. We consider all these problems as important future work in the research agenda toward solving the program translation problem. 

:



Figures and Tables:

Figure 1: Translating a CoffeeScript program into JavaScript. The sub-component in the Coffee-Script program and its corresponding translation in JavaScript are highlighted.

Figure 2: Tree-to-tree workflow: The arrows indicate the computation flow of the encoder-decoder architecture. Blue solid arrows indicate the flow from/to the left child, while orange dashed arrows are for the right child.The black dotted arrow from the source tree root to the target tree root indicates that the LSTM state is copied. The green box denotes the expanding node, and the grey one denotes the node to be expanded in a queue. The sub-tree of the source tree corresponding to the expanding node is highlighted in yellow. The right corner lists the formulas to predict the token for the expanding node.

u r n [ '<LET>' , ' b l a n k ' , t 1 , t 2 ] 11 e l i f a s t [ 0 ] == '<IF>' : 12 cmp = a s t [ 1 ] 13 t 1 = s e l f . t r a n s l a t e f r o m f o r ( a s t [ 2 ] ) 14 t 2 = s e l f . t r a n s l a t e f r o m f o r ( a s t [ 3 = s e l f . t r a n s l a t e f r o m f o r ( a s t [ 1 ] ) 18 i n i t = s e l f . t r a n s l a t e f r o m f o r ( a s t [ 2 ] ) 19 cmp = s e l f . t r a n s l a t e f r o m f o r ( a s t [ 3 ] ) 20 i n c = s e l f . t r a n s l a t e f r o m f o r ( a s t [ 4 ] ) 21 body = s e l f . t r a n s l a t e f r o m f o r ( a s t [ 5 ] ) 22 t b = [ '<LET>' , ' b l a n k ' , body , [ '<APP>' , ' f u n c ' , i n c ] ] 23 f u n c b o d y = [ '<IF>' , cmp , t b , '<UNIT>' ] 24 t r a n s l a t e = [ '<LETREC>' , ' f u n c ' , v a r , f u n c b o d y , [ '<APP>' , ' f u n c ' , i n c ] ] 25 r e t u r n t r a n s l a t e 26 e l i f a s t [ 0 ] == '<ASSIGN>' : 27 r e t u r n [ '<LET>' , a s t [ 1 ] , a s t [ 2 ] , '<UNIT>' ] 28 e l i f a s t [ 0 ] == '<Expr>'

Figure 7: The Python code to translate a FOR program into a LAMBDA program.

Statistics of the Java to C# dataset.

Table content: <table><tr><td>Project</td><td># of matched methods</td></tr><tr><td>Lucene (luc)</td><td>5,516</td></tr><tr><td>POI (poi)</td><td>3,153</td></tr><tr><td>Itext (ite)</td><td>3,079</td></tr><tr><td>JGit (jgi)</td><td>2,780</td></tr><tr><td>JTS (jts)</td><td>2,003</td></tr><tr><td>Antlr (ant)</td><td>465</td></tr><tr><td>Total</td><td>16,996</td></tr></table>

Token accuracy and program accuracy of different approaches for the synthetic task.

Table content: <table><tr><td/><td>Tree2tree</td><td/><td/><td colspan="2">Seq2seq</td><td/><td colspan="2">Seq2tree</td><td colspan="2">Tree2seq</td></tr><tr><td>T→T</td><td>T→T (-PF)</td><td>T→T (-Attn)</td><td>P→P</td><td>P→T</td><td>T→P</td><td>T→T</td><td>P→T</td><td>T→T</td><td>T→P</td><td>T→T</td></tr><tr><td/><td/><td/><td colspan="4">CoffeeScript to JavaScript translation</td><td/><td/><td/><td/></tr><tr><td colspan="11">CJ-AS 99.57% 98.80% 0.09% 90.51% 79.82% 92.73% 89.13% 86.52% 88.50% 96.96% 92.18%</td></tr><tr><td colspan="2">CJ-BS 99.75% 99.67%</td><td>0%</td><td colspan="8">97.44% 16.26% 98.05% 93.89% 91.97% 88.22% 96.83% 78.77%</td></tr><tr><td colspan="2">CJ-AL 97.15% 71.52%</td><td>0%</td><td>21.04%</td><td>0%</td><td>0%</td><td>0%</td><td colspan="4">80.82% 78.60% 82.55% 46.94%</td></tr><tr><td colspan="2">CJ-BL 95.60% 78.61%</td><td>0%</td><td colspan="8">19.26% 9.98% 25.35% 42.08% 76.12% 76.21% 83.61% 26.83%</td></tr><tr><td/><td/><td/><td colspan="4">JavaScript to CoffeeScript translation</td><td/><td/><td/><td/></tr><tr><td colspan="11">JC-AS 87.75% 85.11% 0.09% 83.07% 86.13% 73.88% 86.31% 86.86% 86.99% 71.61% 86.53%</td></tr><tr><td colspan="2">JC-BS 86.37% 80.35%</td><td>0%</td><td colspan="8">80.49% 85.94% 69.77% 85.28% 85.06% 84.25% 66.82% 85.31%</td></tr><tr><td colspan="2">JC-AL 78.59% 54.93%</td><td>0%</td><td colspan="8">77.10% 77.30% 65.52% 75.70% 77.11% 77.59% 60.75% 75.75%</td></tr><tr><td colspan="2">JC-BL 75.62% 44.40%</td><td>0%</td><td colspan="8">73.14% 73.96% 61.92% 74.51% 74.34% 71.56% 57.09% 73.86%</td></tr></table>

Program accuracy of different approaches for translation between CoffeeScript and JavaScript. The token accuracy can be found in Appendix C .

Table content: <table/>

Program accuracy on the Java to C# translation. In the parentheses, we put the program accuracy that can be achieved by increasing the training set.

Table content: <table><tr><td/><td>Tree2tree</td><td colspan="2">J2C# 1pSMT Reported in (Nguyen et al., 2015) mppSMT</td></tr><tr><td>Lucene</td><td>72.8%</td><td>21.5% 21.6%</td><td>40.0%</td></tr><tr><td>POI</td><td>72.2%</td><td>18.9% 34.6%</td><td>48.2%</td></tr><tr><td>Itext</td><td>67.5%</td><td>25.1% 24.4%</td><td>40.6%</td></tr><tr><td>JGit</td><td>68.7%</td><td>10.7% 23.0%</td><td>48.5%</td></tr><tr><td>JTS</td><td>68.2%</td><td>11.7% 18.5%</td><td>26.3%</td></tr><tr><td>Antlr</td><td colspan="2">31.9% (58.3%) 10.0% 11.5%</td><td>49.1%</td></tr></table>

Peer review (iclr2018):
 This paper aims to translate source code from one programming language to another using a neural network architecture that maps trees to trees. The encoder uses an upward pass of a Tree LSTM to compute embeddings for each subtree of the input, and then the decoder constructs a tree top-down. As nodes are created in the decoder, a hidden state is passed from parents to children via an LSTM (one for left children, one for right children), and an attention mechanism allows nodes in the decoder to attend to subtrees in the encoder. Experimentally, the model is applied to two synthetic datasets, where programs in the source domain are sampled from a PCFG and then translated to the target domain with a hand-coded translator. The model is then trained on these pairs. Results show that the nproposed approach outperforms sequence representations or serialized tree representations of inputs and outputs. Pros: - Nice model which seems to perform well. - Reasonably clear explanation. A couple questions about the model: - the encoder uses only bottom-up information to determine embeddings of subtrees. I wonder if top-down information would create embeddings with more useful information for the attention in the decoder to pick up on. - I would be interested to know more details about how the hand-coded translator works. Does it work in a context-free, bottom-up fashion? That is, recursively translate two children nodes and then compute the translation of the parent as a function of the parent node and translations of the two children? If so, I wonder what is missing from the proposed model that makes it unable to perfectly solve the first task? Cons: - Only evaluated on synthetic programs, and PCFGs are known to generate unrealistic programs, so we can only draw limited conclusions from the results. - The paper overstates its novelty and doesn*t properly deal with related work (see below) The paper overstates its novelty and has done a poor job researching related work. Statements like "We are the first to consider employing neural network approaches towards tackling the problem [of translating between programming languages]" are obviously not true (surely many people have *considered* it), and they*re particularly grating when the treatment of related work is poor, as it is in this paper. For example, there are several papers that frame the code migration problem as one of statistical machine translation (see Sec 4.4 of [1] for a review and citations), but this paper makes no reference to them. Further, [2] uses distributed representations for the purpose of code migration, which I would call a "neural network approach," so there*s not any sense that I can see in which this statement is true. The paper further says, "To the best of our knowledge, this is the first tree-to-tree neural network architecture in the literature." This is worded better, but it*s definitely not the first tree-to-tree neural network. See, e.g., [3, 4, 5], one of which is cited, so I*m confused about this claim. In total, the model seems clean and somewhat novel, but it has only been tested on unrealistic synthetic data, the framing with respect to related work is poor, and the contributions are overstated. [1] https://arxiv.org/abs/1709.06182 [2] Trong Duc Nguyen, Anh Tuan Nguyen, and Tien N Nguyen. 2016b. Mapping API elements for code migration with vector representations. In Proceedings of the International Conference on Software Engineering (ICSE). [3] Socher, Richard, et al. "Semi-supervised recursive autoencoders for predicting sentiment distributions." Proceedings of the conference on empirical methods in natural language processing. Association for Computational Linguistics, 2011. [4] https://arxiv.org/abs/1703.01925 [5] Parisotto, Emilio, et al. "Neuro-symbolic program synthesis." arXiv preprint arXiv:1611.01855 (2016).