PaperlayerView exact revision on arXiv

Source-linked AI summary

A General Path-Based Representation for Predicting Program Properties

Uri Alon, Meital Zilberstein, Omer Levy, Eran Yahav

arXiv:1803.09544v3cs.PLcs.LG

TL;DR

The paper addresses how to represent programs effectively for predicting properties such as names and types. It introduces an automatically extracted representation based on AST paths and finds that it generalizes across tasks, learning algorithms, and four programming languages, while improving results over task-specific handcrafted representations.

  • Problem

    Program-property prediction needs representations that facilitate effective learning, but representation design is often manual for each task and programming language.

  • Method

    The paper represents program elements with automatically extracted, purely syntactic paths in their abstract syntax trees and applies the representation across tasks, languages, and learning algorithms.

  • Results

    The representation produces accurate results across variable-name, method-name, and type prediction in JavaScript, Java, Python, and C#, improving results over prior or handcrafted representations where comparisons exist.

  • Takeaways & Limitations

    AST paths provide a reusable program representation that can improve different learning algorithms without modifying the algorithms themselves.

  • Takeaways & Limitations

    Representing every AST path uniquely can be computationally infeasible or harm prediction, so abstractions are needed to trade off accuracy, training time, and model size.

Abstract

from arXiv · show

Predicting program properties such as names or expression types has a wide range of applications. It can ease the task of programming and increase programmer productivity. A major challenge when learning from programs is $\textit{how to represent programs in a way that facilitates effective learning}$. We present a $\textit{general path-based representation}$ for learning from programs. Our representation is purely syntactic and extracted automatically. The main idea is to represent a program using paths in its abstract syntax tree (AST). This allows a learning model to leverage the structured nature of code rather than treating it as a flat sequence of tokens. We show that this representation is general and can: (i) cover different prediction tasks, (ii) drive different learning algorithms (for both generative and discriminative models), and (iii) work across different programming languages. We evaluate our approach on the tasks of predicting variable names, method names, and full types. We use our representation to drive both CRF-based and word2vec-based learning, for programs of four languages: JavaScript, Java, Python and C\#. Our evaluation shows that our approach obtains better results than task-specific handcrafted representations across different tasks and programming languages.

1 Introduction

The paper introduces an automatically extracted AST-path representation designed to support learning program properties across tasks, languages, and learning algorithms. It replaces task- and language-specific feature design with a general syntactic representation.

  • Motivation: The central challenge is representing programs so machine-learning models can effectively predict properties such as variable names, method names, and expression types.Existing representations are often designed manually for each task and programming language.
  • Approach: The approach represents program elements using paths through an abstract syntax tree, extracted automatically after parsing the program.Paths are sequences of AST nodes connected by upward and downward movements; an element is represented by the paths involving its occurrences.
  • Generality: AST paths provide a general representation because they can be used across programming languages without manually identifying language-specific patterns and nuances.The representation is purely syntactic and does not require semantic analysis.
  • Generality: The same representation can support varied prediction tasks and be combined with off-the-shelf learning algorithms without changing the learning algorithm.The paper evaluates tasks including program-element names, method names, and types using different learning approaches.
  • Relation to prior work: Unlike prior work that uses AST paths mainly to identify context nodes, this approach uses the path itself to represent a program element.Predictions therefore depend on both the context node and how that node is structurally related to the target.
  • Evaluation: Experiments cover JavaScript, Java, Python, and C# and report more accurate results than previous or task-specific handcrafted representations where comparisons are available.The evaluation spans variable-name, method-name, and type prediction, with both CRF and word2vec learning.

2 Overview

The approach represents program elements with automatically extracted AST paths, using their structural context to support name prediction. The same representation distinguishes code patterns that handcrafted relations cannot and works with different learning algorithms.

  • The goal is to predict likely names for local variables and function parameters with non-descriptive names.
  • AST paths represent program elements by connecting nodes in the program’s abstract syntax tree.Paths can connect leaves or higher nonterminals, include multiple nodes, and use different abstraction levels.
  • A path between occurrences of d captures its use as a negated while-loop stopping condition before an if-dependent reassignment.A separate path to true captures that the assignment changes d to true and stops the loop.
  • The model predicts done for d, whereas prior work predicts neither done, complete, nor similar names in this example.
  • AST paths outperform manual or sequence-based representations for this prediction task with both CRFs and word2vec.The learning algorithm can vary, trading off efficiency and accuracy.
  • AST paths distinguish code snippets that produce identical handcrafted relations even though the variable plays different roles.This illustrates their greater discriminative power for structurally different examples.
  • The representation is automatic, language-independent, applicable to varied prediction tasks, and compatible with existing models.Users choose among proposed path abstractions rather than manually designing relationships.

3 Background

This section introduces CRFs and word2vec as learning models, then explains how AST paths replace conventional program or token-stream contexts. The representation can be used within both model families, including a reported improvement for word2vec-based prediction.

  • Conditional Random Fields: CRFs model the conditional distribution P(y|x) directly using a graphical structure.
  • Conditional Random Fields: CRF factors depend on subsets of variables and assign non-negative compatibility values, with Z normalizing the distribution.
  • Conditional Random Fields: In the CRF adaptation, AST paths replace Raychev et al.’s original factors, while unary factors connect occurrences of the same program element.
  • Neural Word Embeddings: SGNS learns vector representations by increasing similarity for observed word-context pairs and decreasing similarity for randomly sampled contexts.
  • Neural Word Embeddings: Word2vec uses AST paths as prediction contexts rather than surrounding code tokens.
  • Neural Word Embeddings: 96% relative improvement is reported when AST paths provide context instead of treating code as a token stream with surrounding-token context.

4 AST Paths Representation

The representation models program elements through paths in an AST, with abstractions and length/width limits controlling expressiveness, sparsity, and computational cost.

  • AST Paths: AST paths connect nodes through up and down movements, and path-contexts pair a path with the values at its endpoints.The formal definitions allow paths between arbitrary AST nodes, while the simplified presentation focuses on terminal endpoints.
  • AST Paths: An abstract path-context replaces a concrete AST path with the output of an abstraction function while retaining its endpoint values.The identity function preserves the path, whereas other functions can discard information such as movement arrows.
  • Path Abstractions: Naïvely representing every AST path uniquely can be computationally infeasible and can worsen prediction through the bias-variance tradeoff.Alternative abstractions reduce the number of distinct paths and tune the trade-off among accuracy, training time, and model size.
  • Path Limits: max_length limits path length, while max_width limits the allowed difference between sibling nodes participating in a path.The optimal combination is selected by grid search on a validation set separately for each language and task.
  • Path Limits: Limiting path length and width can improve accuracy because distant paths add noise, long paths increase sparsity and overfitting, and extracting too many paths harms training performance.The paper frames shorter paths as higher-bias and longer paths as higher-variance representations.

5 Evaluation

The evaluation tests whether AST-path representations transfer across representations, languages, tasks, and learning algorithms. Experiments mainly use leafwise-paths and semi-paths, with an exception for full Java expression types.

  • Evaluation Goals: The evaluation compares different program-element representations while keeping off-the-shelf learning algorithms unchanged whenever possible.This isolates the effect of the representation on prediction accuracy.
  • Evaluation Goals: The experiments ask whether AST paths outperform existing representations and generalize across programming languages, prediction tasks, and learning algorithms.They also examine semantic regularities, useful path lengths, path dimensions, and path abstractions.
  • Representations: Most experiments use leafwise-paths between AST terminals and semi-paths between a terminal and an ancestor.Leafwise-paths are more diverse and expressive, whereas semi-paths provide more generalization.
  • Representations: Full-type prediction in Java also uses paths from terminals to the nonterminal representing the expression being typed.This is the stated exception to the predominantly terminal-based path choices.
  • Implementation: PIGEON applies the same main path-extraction algorithm across Java, JavaScript, Python, and C#, with separate language-specific parsing and traversal modules.The learning experiments use both Conditional Random Fields and word2vec-based learning.

5.2 Experimental Setting

The experiments use public GitHub projects divided into training, validation, and test sets, with duplicate filtering and exact-match evaluation across languages.

  • Datasets: For each language, source code from public GitHub projects was randomly split into training, validation, and test sets.The collection emphasized top-ranked projects and projects with the most forks.
  • Datasets: The Java dataset required an order of magnitude more data than the other languages to approach comparable results.The dataset was repeatedly enlarged during preparation for the experiments.
  • Datasets: Duplicate filtering used file names, directory names, and file md5 values, with particular effort devoted to the JavaScript dataset.The authors note that duplication is less severe in Java and Python because those projects do not commit dependencies.
  • Metric: The evaluation metric is the percentage of exact-match predictions, ignoring case and differences in non-alphabetical characters.For comparison with Allamanis et al., the paper also reports F1 score because their model was optimized for sub-token F1.

5.3 Quantitative Evaluation

The evaluation tests AST paths across multiple prediction tasks, languages, baselines, and learning algorithms. AST-path models generally outperform alternative representations, while CRFs are more accurate and word2vec is more efficient.

  • Variable names: 7.6% higher accuracy was achieved by AST-path representations than previous work for JavaScript variable naming under matched datasets and settings.The comparison kept datasets, settings, AST terminals, and CRF nodes the same, isolating the input representation.
  • Variable names: AST paths yielded higher CRF results than manually defined features, n-grams, and rule-based approaches across the evaluated languages.The Java evaluation included CRF n-grams and a rule-based baseline.
  • Variable names: AST paths with word2vec produced much better variable-name results than linear token-stream and path-neighbors without paths.The baselines differed either by using surrounding tokens or by hiding the path representation while retaining surrounding AST nodes.
  • Cross-language results: Accuracy was lower for Python than JavaScript, while C# accuracy was similar to Java despite using significantly less training data.The paper attributes these differences to variation in code quality, domains, naming structure, and IDE support.
  • Method names: Method-name prediction accuracy was approximately 50% across all languages, and Java AST-path CRFs significantly improved over prior work in exact accuracy and F1 score.The Java comparison used the same training corpus as the earlier model.
  • Full types: 69.1% accuracy was obtained for full Java-type prediction, compared with 24.1% for uniformly predicting java.lang.String.The learning approach reconstructed types locally, whereas type inference used global project scope and remained more accurate.

5.4 Qualitative Evaluation

Qualitative examples show AST paths producing meaningful names in Python, JavaScript, and Java, including cases where informative type or interface names were unavailable. Top-ranked alternatives also often preserve semantic similarity.

  • Examples: Python examples received meaningful predictions such as process, cmd, and retcode.The examples were presented as an anecdotal qualitative evaluation.
  • Examples: The JavaScript example produced names such as url and callback, while the compared online model used a different training dataset.The dataset-matched UnuglifyJS model yielded worse results in the reported comparison.
  • Examples: Java examples produced done, values, value, and count even when class and interface names could not aid prediction.These challenging examples required leveraging syntactic structure rather than informative type-related names.
  • Semantic similarities: Top candidates frequently showed semantic similarity, including ended, complete, finished, req∼request, and list∼array.The authors state that this supports the hypothesis that AST paths capture a program element’s semantic role.

5.5 Impact of Parameter Values

Path length and width affect prediction accuracy and computational cost, with longer paths especially important for name prediction. Downsampling can reduce training time while preserving or retaining competitive accuracy.

  • Path parameters: For name prediction across languages, the best path length was 6–7 and the best width was 3–4.The reported path-length variation reflected minor differences in AST structure, including between Java and C#.
  • Path parameters: Increasing max_length significantly improved JavaScript variable-name accuracy, while increasing max_width had a positive but minor effect.The result supports the importance of long-distance paths for prediction.
  • Path parameters: For method-name prediction, path length was set to 12 for JavaScript, 10 for Python, and 6 for Java.Fewer paths made higher parameter values computationally feasible in this task.
  • Path parameters: Full Java-type prediction used length 4 and width 1, achieving 69.1% accuracy.The short path length was motivated by local inference from neighboring types and explicit declarations.
  • Downsampling: Higher max_length and max_width increased training times, but downsampling enabled larger values while controlling the accuracy–training-time tradeoff.The downsampling procedure randomly omitted path-context occurrences with probability 1 − p.
  • Downsampling: With p = 0.8, downsampling matched the complete-set accuracy while reducing training time by about 25%.At p = 0.2, accuracy remained higher than UnuglifyJS while training time fell by about 80% versus p = 1.0.

5.6 Abstractions of AST Paths

Path abstractions trade representational detail for model size and training speed. Keeping more path information generally improves accuracy, but first-top-last offers a strong efficiency–accuracy compromise.

  • Abstraction choices: The evaluated abstractions ranged from full paths without arrows to bags of nodes, selected endpoints, the top node, and no paths.The no-paths variant uses surrounding identifiers without syntactic relations.
  • Accuracy and cost: More retained path information increased accuracy at the cost of longer training time.The experiments used CRFs for Java variable-name prediction with identical training data and other settings.
  • Accuracy and cost: Arrows and node order contributed about 1% accuracy.This isolates the reported contribution of directional and ordering information within the path representation.

6 Related Work

Related work applies machine learning, probabilistic models, NLP techniques, and tree-based representations to programming-language tasks. The paper distinguishes its path representation from approaches that manually design features, use paths only to identify context nodes, or decompose ASTs into subtrees.

  • Earlier naming approaches used manually designed features for specific tasks, while CRF-based methods modeled names and types in program-property prediction.
  • Other related applications include code similarity, naming recommendations, program synthesis, code translation, code completion, and code summarization.
  • Parse Tree Paths use paths from target words to linguistic constituents, whereas this work uses AST paths as program-element representations.
  • Bielik et al. and Raychev et al. used AST paths to identify context nodes, so predictions depended on the selected context node rather than the path itself.
  • Tree-convolutional learning decomposes ASTs into subtrees, whereas this representation decomposes them into paths intended to better capture data-flow properties.

7 Conclusion

The paper presents a simple, general representation that models programs with paths in their ASTs, allowing learning systems to use source-code structure. The representation works across programming languages and prediction tasks, improves different learning algorithms without changing them, and may extend to other machine-learning applications.

  • The approach represents programs using paths in their abstract syntax trees rather than flat token sequences.
  • AST-path representations can support varied programming languages and prediction tasks.
  • The representation improves results for different learning algorithms without modifying the learning algorithm itself.
  • The authors suggest AST-path representations may apply to other machine-learning tasks, applications, and learning models.
Loading 1803.09544v3…