Analysis of Tree-Structured Architectures for Code Generation

Samip Dahal, Adyasha Maharana, Mohit BansalACL 2021 · OpenReview

TL;DR

This paper investigates how incorporating the syntactic structure of natural language (NL) input, specifically using constituency parse trees, can improve code generation. They demonstrate that a "structure-aware" Transformer model, which explicitly processes these trees, significantly outperforms standard sequence-to-tree models on code generation tasks, especially for inputs with complex structures or specific patterns.

What Problem Does This Paper Address?

Generating code from natural language descriptions is a challenging task. While recent advances in sequence-to-sequence models, particularly Transformers, have shown promise, they often treat the input natural language as a flat sequence of words. However, natural language has inherent hierarchical structures (like sentence constituents) that mirror the hierarchical structure of code (Abstract Syntax Trees or ASTs). The authors hypothesize that leveraging these input linguistic structures can lead to better code generation by facilitating alignment between the input's structure and the target code's structure. The gap they address is the under-exploration of using input parse tree structures for code generation, as most prior work focused on using the target code's AST.

Methods

The paper proposes and evaluates three main approaches:

  • Baseline (Text-to-Tree): A standard Transformer model that treats the input natural language as a linear sequence.
  • Linearized Tree-to-Tree: This model takes the input natural language, converts it into a constituency parse tree, linearizes this tree (e.g., using pre-order traversal), and then feeds this linearized sequence to a Transformer. The idea is to preserve some structural information but in a flattened format.
  • Structured Tree-to-Tree (with Hierarchical Accumulation): This is the core novel contribution. It adapts a "Tree Transformer" architecture that is specifically designed to process tree structures. This model directly encodes the constituency parse tree, using mechanisms like hierarchical accumulation and subtree masking to capture the tree's hierarchical relationships. This allows for a more direct and nuanced understanding of the input's structure compared to linearization.

All models generate the Abstract Syntax Tree (AST) of the target code, which is then converted into source code. They also incorporate a pointer network to copy relevant entities from the input.

Datasets

The models were evaluated on two datasets:

  • CoNaLa: A Python-based code generation dataset consisting of manually curated natural language intent-code snippet pairs.
  • ATIS: A semantic parsing dataset that translates natural language sentences into lambda calculus logical forms. This dataset was used to assess the model's performance on a related task where structured input might also be beneficial.

Key Insights and Ideas

  • Structure Matters: Explicitly encoding the hierarchical structure of the natural language input significantly improves code generation performance. Simply linearizing the parse tree is not as effective as directly processing the tree structure.
  • Structure-Awareness is Key: The "structure-aware" Transformer model, which directly processes constituency parse trees, is crucial for capturing complex relationships and improving code quality.
  • Subtree Masking is Important: Within the structure-aware model, subtree masking (limiting attention to relevant parts of a subtree) proved more critical than hierarchical embeddings for effective encoding. This suggests that focusing on local structural context is vital.
  • Specific Input Patterns Benefit Most: The structured model shows particularly large gains when input sentences contain quoted strings (often user-defined identifiers) or when variable entities appear at the end of the sentence. This highlights the model's ability to handle specific linguistic cues that are structurally important.
  • Short Inputs are a Sweet Spot: The structured model shows a wider performance gap over the baseline for shorter input sentences and shallower parse trees, suggesting it's particularly effective in simplifying and clarifying these inputs.

Key Results

  • CoNaLa Dataset: The structured constituency tree-to-tree model achieved a BLEU score of 30.30, outperforming the baseline (28.13) by 2.17 points and a previous state-of-the-art LSTM model (Xu et al., 2020) by 3.1 points.
  • ATIS Dataset: The structured model significantly improved accuracy over the baseline and other models, achieving 86.83% accuracy compared to the baseline's 75.89%.
  • Human Evaluation (CoNaLa): Human evaluators preferred the code generated by the structured model 35% of the time, compared to 27% for the baseline, indicating better code quality.
  • Pattern Analysis: The structured model achieved significantly higher BLEU scores (e.g., 26.42 vs. 20.79 for inputs ending with a quoted string on CoNaLa) when specific linguistic patterns were present.

Limitations and Future Work

  • Model Complexity: The structured models have significantly more parameters than the baseline LSTM models they were compared against, though the authors note that increasing parameters in simpler models didn't yield similar gains.
  • Target AST Structure: The authors note that their model lacks a specific module for encoding the target AST during generation, which might explain why it's slightly worse than TreeGen on ATIS. They suggest that joint modeling of input and output parse trees could be a promising direction.
  • Input Complexity Nuances: While the structured model performs better on shorter inputs, the relationship with input complexity (length and height) is more nuanced and requires further investigation, especially for the ATIS dataset where height didn't show a clear correlation.
  • Generalizability: The paper focuses on constituency trees. Future work could explore dependency trees or other syntactic representations.

Summary updated

BibTeX
@inproceedings{dahal2021analysis,
  author = {Samip Dahal and Adyasha Maharana and Mohit Bansal},
  title = {{Analysis of Tree-Structured Architectures for Code Generation}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
  url = {https://openreview.net/forum?id=hPV6DCQaW-c},
}
Figure