PaperlayerView exact revision on arXiv

Source-linked AI summary

Mining Idioms from Source Code

Miltiadis Allamanis, Charles Sutton

arXiv:1404.0417v3cs.SE

TL;DR

Existing tools require programmers to know and manually organize idioms, motivating automatic mining from idiomatic code corpora. HAGGIS models idioms with nonparametric Bayesian probabilistic tree substitution grammars and finds recurring, semantically meaningful patterns across projects and examples.

  • Problem

    Manual idiom tools require setup and prior knowledge, while automatic identification from idiomatic code corpora was unavailable.

  • Method

    HAGGIS automatically mines syntactic code idioms from AST corpora using nonparametric Bayesian probabilistic tree substitution grammars.

  • Results

    67% of idioms identified from one open-source project set also appear in an independent StackOverflow example-code set, and many idioms correlate with package imports.

  • Takeaways & Limitations

    The mined idioms include project-specific, API-specific, and language-specific patterns describing concepts such as object creation, exception handling, and resource management.

  • Takeaways & Limitations

    Maximum-likelihood grammar learning overfits by adding a fragment rule for every training tree, motivating strong control of model complexity.

Abstract

from arXiv · show

We present the first method for automatically mining code idioms from a corpus of previously written, idiomatic software projects. We take the view that a code idiom is a syntactic fragment that recurs across projects and has a single semantic role. Idioms may have metavariables, such as the body of a for loop. Modern IDEs commonly provide facilities for manually defining idioms and inserting them on demand, but this does not help programmers to write idiomatic code in languages or using libraries with which they are unfamiliar. We present HAGGIS, a system for mining code idioms that builds on recent advanced techniques from statistical natural language processing, namely, nonparametric Bayesian probabilistic tree substitution grammars. We apply HAGGIS to several of the most popular open source projects from GitHub. We present a wide range of evidence that the resulting idioms are semantically meaningful, demonstrating that they do indeed recur across software projects and that they occur more frequently in illustrative code examples collected from a Q&A site. Manual examination of the most common idioms indicate that they describe important program concepts, including object creation, exception handling, and resource management.

1. INTRODUCTION

The paper motivates automatically mining code idioms because idiomatic code supports communication, while manual IDE tools require prior knowledge and setup. HAGGIS addresses this gap with a probabilistic method that identifies patterns explaining source code and finds idioms recurring across projects.

  • Idiomatic code helps programmers communicate operational details to developers who later adapt, update, test, and maintain it.
  • Code idioms are recurring syntactic fragments with single semantic roles, potentially containing metavariables that abstract over identifiers or code blocks.
  • Manual IDE templates support defining and reusing idioms, but developers must organize them and already know which idioms to use.
  • Frequent AST fragments alone are inadequate because removing leaves makes true idioms more frequent, yielding short, generic, incomplete patterns.
  • HAGGIS uses a probabilistic model and nonparametric Bayesian analysis to retain idioms that improve the model’s explanation of training code.
  • 67% of idioms identified from one open-source project set also appear in an independent StackOverflow example-code set.

2. PROBLEM DEFINITION

The paper defines idioms as structured AST fragments that recur across projects and serve one semantic purpose, distinguishing them from clones and API patterns. It formulates unsupervised idiom mining and explains why probabilistic modeling is needed beyond frequent-tree mining.

  • An idiom is a syntactic AST fragment that recurs across software projects and serves a single semantic purpose.
  • Idioms can be parameterized by metavariables, including identifier names, expressions, and code blocks such as a Cursor-handling body.
  • The idiom-mining problem is unsupervised: given ASTs from previously written idiomatic source files, identify fragments occurring in subsets of the training corpus.
  • Idioms differ from clones because they typically recur across projects rather than being copied code blocks, and from API patterns because they preserve syntactic structure.
  • Frequent-tree mining tends to return small generic fragments because removing leaves always increases a fragment’s frequency, even when those leaves matter semantically.
  • HAGGIS’s probabilistic approach penalizes failing to extend a pattern with a frequently co-occurring node, addressing the incompleteness of simple frequency-based mining.

3. MINING CODE IDIOMS

HAGGIS mines recurring AST fragments by learning probabilistic tree-substitution grammars from source-code corpora, using Bayesian methods to control model complexity and MCMC to infer idioms.

  • 3.1 Probabilistic Grammars: HAGGIS models code idioms as recurring AST fragments and uses probabilistic tree substitution grammars to represent contiguous grammar-rule sequences.The approach extends a known programming-language grammar rather than relearning it.
  • 3.1 Probabilistic Grammars: Naive frequent-tree mining returns small, generic fragments, while maximum likelihood can overfit by memorizing individual training trees.The method instead favors patterns that improve probabilistic explanation of the source-code corpus.
  • 3.2 Nonparametric Bayesian Methods: Nonparametric Bayesian methods infer model complexity automatically, balancing useful pattern discovery against excessive fragment rules that memorize the training set.This avoids requiring the number of fragments per nonterminal to be fixed in advance.
  • 3.2 Nonparametric Bayesian Methods: The prior assigns probability to possible fragments, and the posterior is characterized by a finite set of fragments for each nonterminal that become candidate idioms.This provides a principled bridge from an unbounded fragment space to an identifiable set of idioms.
  • 3.3 Inference: Inference parses each source file with the base CFG, then samples binary boundaries indicating where tree fragments begin and end.Gibbs sampling updates these boundary variables iteratively; fragments from the converged posterior are returned as idioms.

4. SAMPLING A TSG FOR CODE

HAGGIS adapts probabilistic tree substitution grammars to Java ASTs by transforming trees and abstracting variable names, then trains idiom models offline for later use.

  • AST Transformation: HAGGIS extracts Java ASTs with Eclipse JDT and adapts them for probabilistic tree substitution grammar modeling.
  • AST Transformation: Tree binarization converts structural nodes with multiple children into binary trees by adding dummy nodes, reducing rule sparsity and capturing sequential statements.
  • AST Transformation: Variable names are abstracted through typed MetaVariable nodes, allowing mined idioms either to omit names or retain specific idiomatic names.
  • Training TSGs and Extracting Code Idioms: HAGGIS trains the TSG offline and extracts idioms afterward, so IDE users do not wait for MCMC sampling.
  • Training TSGs and Extracting Code Idioms: The sampler excludes imports and selected AST nodes from idiom mining by fixing their sampling state, constraining which structures can form idioms.

5. CODE SNIPPET EVALUATION

HAGGIS is evaluated on Java projects, library-using files, and StackOverflow snippets to assess whether its mined idioms are syntactically coherent, semantically meaningful, and useful across settings. The evaluations show strong project-specific and library-specific patterns, while also distinguishing idiom mining from clone detection.

  • Evaluation setup: Posterior samples produce syntactically correct, locally consistent code, supporting idiom inference but not higher-level information such as variable binding.The pTSG-generated code provides an intuitive check on the model’s learned structure.
  • Evaluation setup: The Projects and Library datasets contain Java open-source code split into training and test sets for in-project and cross-library idiom evaluation.Projects comprises popular large GitHub repositories, while Library comprises files importing selected Java libraries.
  • Top idioms: The mined Library idioms capture semantically consistent library actions, including object creation, resource handling, transactions, and error handling.Examples include RabbitMQ message-channel instantiation, Hadoop filesystem handles, JGit resource use, Neo4J transactions, and Hibernate error handling.
  • Quantitative evaluation: HAGGIS achieves better precision and coverage in Projects than across disparate libraries, consistent with idioms recurring more often within similar projects.Figure 9 reports average performance and variation across projects, while the comparison with Deckard shows HAGGIS finds larger, higher-coverage idioms with statistically significant differences.
  • Extrinsic evaluation: Using Library idioms, StackOverflow evaluation reaches 31% coverage and 67% precision, rising to 96.6% precision at 21% coverage for two Android libraries.These results indicate that the mined idioms occur frequently in highly idiomatic code examples and in development practice.
  • Idioms and libraries: Lift analysis shows both language-generic idioms and library- or project-specific idioms, while import-based suggestions achieve 76% recall at rank k = 5 with 20% suggestion frequency.The matrix relates idioms to imported packages, and the suggestion experiment uses imports alone to retrieve relevant idioms.

6. RELATED WORK

Prior work applies language and tree-based models to source code, but code idiom mining targets recurring, semantically meaningful tree fragments rather than sequential patterns or maximally similar clones.

  • N-gram models have been used for code autocompletion, coding-convention learning, and syntax-error detection.
  • Tree-structured code models have supported program generation by example and source-code modeling.
  • Earlier language, tree-modeling, clone-detection, and frequent-tree-mining work had not extracted non-sequential code idioms with this probabilistic notion of interest.
  • Code clone detection seeks highly similar code, whereas idiom mining searches for frequent subtrees across projects.
  • Frequent tree-mining algorithms can find common subtrees but do not ensure that frequent trees are interesting.

7. DISCUSSION & CONCLUSIONS

Haggis mines idioms that appear across projects, APIs, and programming languages, while distinguishing useful coding conventions from patterns arising from language or API deficiencies.

  • Haggis finds project-specific, API-specific, and language-specific idioms across multiple settings.
  • Some idioms may form an abstraction layer that communicates code intent more clearly, while others may compensate for language or API deficiencies.
  • A sequence of multiple catch statements is linked to Java’s language design and preceded the introduction of multi-catch in Java 7.
  • The common for(int i=0;i<n;i++) pattern is characterized as a useful, widely understandable idiom rather than a language limitation.
Loading 1404.0417v3…