Introduction
Representing complex computer code in a format suitable for deep learning models remains a significant challenge in software engineering. While sequence-to-sequence (seq2seq) architectures excel at natural language processing, they often struggle with the rigid, hierarchical structure of source code. This paper introduces a novel approach using Prüfer sequences—a classic tool from graph theory—to create a concise, lossless encoding of Abstract Syntax Trees (ASTs), significantly improving code summarization tasks.
The Challenge of Code Representation
Deep learning models typically require input to be flattened into a sequence of tokens. However, code is inherently tree-structured. Previous flattening methods, such as Structure-Based Traversal (SBT) or path-based methods like Code2Seq, often produce sequences that are excessively long, redundant, or "lossy," meaning the original tree structure cannot be perfectly reconstructed. The authors propose a representation that is both compact and mathematically lossless, emphasizing critical structural components.
Methodology: Leveraging Prüfer Sequences
The core innovation lies in applying the Prüfer sequence algorithm to ASTs. In graph theory, a Prüfer sequence provides a unique one-to-one correspondence (bijection) between a labeled tree of $n$ nodes and a sequence of $n-2$ integers.
The Prüfer Sequence Algorithm
The transformation process involves four key steps:
- Tree Labeling: Every syntactic and lexical token in the AST is mapped to a unique integer.
- Sequence Generation: The sequence is generated by iteratively removing the leaf node with the smallest label and recording its parent's label until only two nodes remain.
- Syntactic Mapping: The resulting integer sequence is mapped back to tokens, creating a "syntactic Prüfer sequence."
- Implicit Weighting: A notable property of this representation is that a node's label appears $d-1$ times in the sequence, where $d$ is the node's degree. This naturally highlights important syntactic structures that govern large code blocks.
Dual-Encoder Architecture
The authors implemented a seq2seq model using Gated Recurrent Units (GRUs) with a dual-encoder setup:
- Prüfer Sequence Encoder: Captures the structural "skeleton" of the code.
- Context Encoder: Processes lexical tokens (variable names, values) in a manner that reflects the underlying AST structure.
Experimental Evaluation
The approach was evaluated on two large-scale Java datasets:
- Dataset-1: 68,469 pairs of Java code snippets and natural language comments.
- Dataset-2: 163,316 pairs sourced from the CodeXGLUE benchmark.
Results
The Prüfer-based model consistently outperformed state-of-the-art baselines, including Code2Seq and Hybrid-DeepCom, across standard metrics such as S-BLEU, C-BLEU, METEOR, and ROUGE-L.
On Dataset-1, the model achieved a performance boost of approximately 5% over baseline models. The improvements were even more pronounced on the larger Dataset-2, with gains reaching up to 15.11% in key metrics.
The results demonstrate that the Prüfer sequence representation is highly efficient, maintaining conciseness while retaining more structural information than traditional traversal methods.
Discussion and Future Work
The success of this method stems from its mathematical elegance and the natural separation of "grammar" (syntactic sequence) from "vocabulary" (lexical tokens). This allows the model to grasp the logic of a function independently of specific variable naming conventions.
While the current study focuses on Java, future research could explore the generalizability of Prüfer sequences to other programming languages with distinct AST structures, such as Python or Lisp. Additionally, further refinement of the "Context Encoder" could lead to even more effective integration of lexical and structural signals.
Summary updated