Source-linked AI summary
Tree-to-tree Neural Networks for Program Translation
Xinyun Chen, Chang Liu, Dawn Song
TL;DR
Program translation seeks to migrate code between programming languages when a cross-compiler is unavailable. The paper introduces a tree-to-tree neural network with source-tree attention, and reports improvements over neural and prior program-translation baselines, including on real-world projects.
Problem
Program translation aims to migrate programs between languages, but real-world settings may lack aligned input-output pairs and include longer programs or infinite vocabularies.
Method
The paper uses a tree-to-tree neural network with a tree-RNN encoder, a tree-RNN decoder, and attention that locates corresponding source sub-trees during target-tree expansion.
Results
Up to 15% gains over other neural translation models and a 20% program-accuracy improvement over previous state-of-the-art approaches are reported.
Takeaways & Limitations
The model is presented as a promising approach for program translation and potentially other tree-to-tree tasks.
Takeaways & Limitations
The approach remains challenged by longer-than-training programs, infinite vocabularies, and the need for aligned input-output training data.
Abstract
from arXiv · showhide
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 employ 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 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
The paper frames program translation as an important but difficult migration problem and proposes tree-to-tree neural networks with attention to exploit program structure. Its models outperform neural and prior program-translation baselines across evaluated tasks.
- Manual grammar analysis and rule-based translator development are inefficient and error-prone, motivating automatic neural program translation.
- Programming languages require syntactically correct outputs, making sequence generation increasingly difficult as program length grows.
- Tree-to-tree neural networks separate source and target program structure through a tree encoder and tree decoder aligned with modular translation.
- The model uses attention to locate corresponding source sub-trees during target non-terminal expansion, while parent attention captures dependencies between attention maps.
- Up to 5% token-accuracy and 15% program-accuracy gains over neural baselines, plus a 20% program-accuracy margin over prior approaches on Java-to-C# translation.
2 Program Translation Problem
Program translation learns a mapping from paired source and target programs, using their parse trees to represent structurally corresponding programs. The central challenge is learning this mapping when a cross-compiler is unavailable.
- Tree representation: Each program unambiguously corresponds to a parse tree, making tree-to-tree translation an alternative to sequence-based token modeling.Modern programming languages commonly provide parsers for obtaining these trees.
- Challenge: The main difficulty is that the cross-compiler needed to translate between the languages typically does not exist.Parsers for both languages do not by themselves solve the translation problem.
- Problem formulation: Program translation maps a source program and parse tree in Ls to a target program and parse tree in Lt using paired examples.The task is to learn a function F that approximates translation oracle π.
- Learning setting: The paper focuses on paired source-target programs, while lacking alignment makes program translation more challenging.The paired-data assumption matches existing program translation work; dual learning is mentioned as a possible direction when alignment is unavailable.
3 Tree-to-tree Neural Network
The model translates source parse trees into target trees with an encoder-decoder architecture, attention over corresponding source sub-trees, and parent-aware attention for child predictions.
- Tree representation: The workflow converts source and target trees into binary trees using a Left-Child Right-Sibling representation.Binary-tree encoders and decoders are used because they can be more effective for trees with arbitrary branching.
- Binary tree encoder: A Tree-LSTM recursively computes embeddings for the entire source tree and each source sub-tree from the bottom up.Missing child states are set to zero.
- Binary tree decoder: The decoder copies the source-root LSTM state to the target root, then expands target nodes from a queue.Each iteration pops one expanding node and processes it recursively.
- Binary tree decoder: For each expanding node, the decoder predicts a terminal, non-terminal, or ⟨EOS⟩ token using an attention-informed embedding and softmax regression.Non-⟨EOS⟩ predictions create left and right child nodes that are added to the expansion queue.
- Attention mechanism: Attention estimates the source sub-tree corresponding to each expanding target node and combines its expected hidden state with the target-node state.Using only the target hidden state can cause source information to be forgotten for deep target nodes.
- Parent attention feeding: Parent attention feeding incorporates a node’s attention vector when predicting attention vectors for its children.The authors distinguish this tree-based use from sequential input-feeding and report that it significantly improves performance.
4 Evaluation
The evaluation compares tree-to-tree translation with neural and prior program-translation baselines across synthetic, CoffeeScript–JavaScript, and Java–C# tasks. Results show strong gains overall, especially with attention, longer programs, and sufficient training data, while temporary variables and short targets constrain improvements.
- Evaluation setup: The evaluation covers three tasks: synthetic imperative-to-functional translation, CoffeeScript–JavaScript translation, and real-world Java–C# translation.The study uses three benchmark settings to evaluate different aspects of program translation.
- Evaluation setup: The main metric is program accuracy, the percentage of predicted target programs exactly matching the ground truth.The metric underestimates semantic equivalence and is used because it is more meaningful than syntax-correctness or dependency-graph accuracy.
- Evaluation setup: The comparison includes nine models spanning sequence-to-sequence, sequence-to-tree, tree-to-sequence, and tree-to-tree architectures.Input and output representations use raw programs or parse trees, producing nine evaluated model variants.
- CoffeeScript–JavaScript results: The tree2tree model outperforms all baselines on all CoffeeScript–JavaScript datasets, with gains reaching 75% over seq2seq and around 20 points over seq2tree on longer programs.The results indicate better learning of source–target correspondence, particularly for longer inputs.
- Ablation results: 30 points: on JC-BL, full tree2tree program accuracy exceeds tree2tree without parent attention feeding.The ablation compares the full model with variants removing parent attention feeding or attention.
- Ablation results: Nearly 0%: removing attention reduces tree2tree program accuracy to nearly zero, whereas the full architecture significantly outperforms prior tree-to-tree-like architectures.The attention ablation highlights the importance of the model’s attention mechanism.
- CoffeeScript–JavaScript results: Improvements are smaller for JavaScript-to-CoffeeScript translation because the target programs are much shorter, although tree2tree still outperforms all baselines.A 20-token CoffeeScript program may correspond to more than 300 JavaScript tokens.
- Real-world project results: 20.2% to 41.9%: tree2tree outperforms previous state-of-the-art approaches on every Java–C# project except Antlr.The comparison includes J2C#, 1pSMT, and mppSMT on a real-world Java-to-C# benchmark.
5 Related Work
Prior work applies statistical and neural approaches to program translation, parsing, code generation, and tree-structured modeling, while this work presents a successful generic tree-to-tree translation design.
- Statistical machine translation approaches adapt phrase-based models and grammatical structures for code migration.
- Tree-structured neural networks use structural encoders and decoders to embed inputs and predict output trees.
- A tree-structured attentional encoder-decoder for natural-language translation performs slightly worse than an attention-based sequence-to-sequence model.
- Neural parsing work generates output trees recursively or incorporates grammar knowledge into the architecture.
- Neural code-generation systems target DSLs but require additional manual effort for adaptation, whereas this work proposes a generic approach applicable to any grammar.
6 Conclusion and Future Work
The paper concludes that its tree-to-tree neural network successfully addresses program translation and outperforms several state-of-the-art models, while identifying major unresolved generalization, vocabulary, and data challenges.
- The proposed model combines tree-RNN encoding and decoding and is presented as the first successful tree-to-tree neural network for translation tasks.
- Extensive evaluation shows that the tree-to-tree neural network outperforms several state-of-the-art models.
- Existing techniques struggle to generalize beyond training-program lengths, handle infinite real-world vocabularies, and obtain aligned input-output datasets.
- The paper identifies these challenges as future work in solving program translation.
B More Statistics of the Datasets
This section points to detailed dataset statistics for the CoffeeScript-JavaScript task and the Java-to-C# dataset.
- Detailed statistics for the CoffeeScript-JavaScript datasets are presented in Table 4.
- Detailed statistics for the Java-to-C# dataset are presented in Table 5.
C More Results on the CoffeeScript-JavaScript Task
The paper reports token-accuracy results for CoffeeScript-JavaScript translation and describes token accuracy as a finer-grained correctness measure.
- Token accuracy measures the percentage of predicted tokens exactly matching the ground truth.
- Token accuracy provides additional performance insight beyond program-level accuracy because it is a finer-grained correctness measurement.
- Figure 3 presents a subset of the CoffeeScript grammar used to generate the CoffeeScript-JavaScript dataset, with <br> denoting a newline character.
- Table 6 reports token accuracy for approaches translating between CoffeeScript and JavaScript.
D Grammar for the CoffeeScript-JavaScript Task
The CoffeeScript-JavaScript dataset uses a grammar that is a subset of the core CoffeeScript grammar.
- The dataset grammar is provided as a subset of the core CoffeeScript grammar.
E Evaluation on the Synthetic Task
The synthetic evaluation translates programs from an imperative source language to a functional target language, using a manually implemented translator to generate ground truth and randomly generated datasets.
- Evaluation materials: Figure 4 illustrates a synthetic translation example, while Tables 7 and 8 present task results and dataset statistics.The supplied captions identify the figure and tables but do not report their contents beyond these roles.
- Task design: The synthetic task translates an imperative source language into a functional target language, changing programming paradigms.A for-loop is translated into a recursive function.
- Task design: A manually implemented translator generates the ground-truth translations for the synthetic task.
- Dataset construction: The synthetic evaluation uses randomly generated, non-overlapping, unique program pairs for training, development, and testing.The dataset contains 100,000 training pairs, 10,000 development pairs, and 10,000 test pairs.
E.2 Results on the Synthetic Task
The synthetic experiments compare models on short and long programs and report that tree2tree performs best, with attention mechanisms improving its performance while longer inputs reduce performance.
- Dataset variants: The synthetic task uses datasets with average program lengths of 20 tokens and 50 tokens.Program length is defined as the number of tokens in the source program.
- Results: Tree2tree outperforms all baseline models on the synthetic task.The result is reported for the token-accuracy and program-accuracy comparison summarized in Table 7.
- Results: Both attention and parent-attention feeding mechanisms significantly improve the tree2tree model’s performance.
- Results: All evaluated models perform worse on longer synthetic inputs.This comparison concerns the short and long synthetic datasets.
- Task specification: Figures 5 and 6 specify the grammars for the FOR source language and LAMBDA target language, while Figure 7 shows the corresponding Python translator.