Mining idioms from source code

By Miltiadis Allamanis, Charles Sutton. 2014

215 citations recorded by the source corpus.

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 purpose. 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.

Subfields: Artificial Intelligence, Information Systems, Software, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Software

In Natural Language Processing

Citations in the corpus

A Survey of Machine Learning for Big Code and Naturalness (2017, methodology): “Although TSGs have been used in NLP to improve parsing performance (which is ambiguous in text), Allamanis and Sutton [12] observe that the inferred fragments represent common code usage conventions and name them idioms.”
CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding and Generation (2021, background): “For example, the idiom mining task [2, 35] is to extract code idioms, which are syntactic fragments that recur across software projects and serve a single semantic purpose [2].”
code2vec: learning distributed representations of code (2018, methodology): “code snippet. Traditional machine learning algorithms such as decision trees [Raychev et al. 2016], Conditional Random Fields [Raychev et al. 2015], Probabilistic Context-Free Grammars [Allamanis and Sutton 2014;Bielik et al. 2016;Gvero and Kuncak2015;Maddison and Tarlow2014], n-grams [Allamanis et ”
Learning API Usages from Bytecode: A Statistical Approach (2015, methodology): “Other techniques includes mining associate rules [24], item sets [6], subgraphs [31], [9], code idioms [4], topic modeling [27], etc.”
LongCoder: A Long-Range Pre-trained Language Model for Code Completion (2023, methodology): “…works have explored the use of statistical learning for the code completion task, such as the use of n-gram techniques (Tu et al., 2014; Hindle et al., 2016) and probabilistic grammar-based methods (Allamanis & Sutton, 2014; Bielik et al., 2016; Raychev et al., 2016; Hellendoorn & Devanbu, 2017).”
Neural Attribute Machines for Program Generation (2017, methodology): “Statistical models used in this task include n-gram topic models [22], probabilistic tree-substitution grammars [25], a generalization of probabilistic grammars known as probabilistic higher-order grammars [24], and recurrent neural networks [6].”
Learning Python Code Suggestion with a Sparse Pointer Network (2016, methodology): “Similar to Allamanis & Sutton (2013) and Allamanis et al. (2014), we select Python projects with more than 100 stars, sort by the number of forks descending, and take the top 1000 projects.”
End-to-end Deep Learning of Optimization Heuristics (2017, background): “Deep learning techniques have shown astounding successes in identifying complex patterns and relationships in images [10, 11], audio [12], and even computer code [7, 13, 14].”
On the "Naturalness" of Buggy Code (2015, methodology): “Following this work, language models have been used to good effect in code suggestion [22, 48, 53, 15], cross-language porting [38, 37, 39, 24], coding standards [2], idiom mining [3], and code deobfuscation [47].”
CODIT: Code Editing With Tree-Based Neural Models (2018, methodology): “[76], [77] proposed statistical modeling technique for mining source code idioms, where they leverages probabilistic Tree Substitution Grammar (pTSG) for mining code idioms.”
CodeFill: Multi-token Code Completion by Jointly learning from Structure and Naming Sequences (2022, methodology): “[4] employ probabilistic context-free grammars, while Raychev et al.”
Mining Semantic Loop Idioms from Big Code (2016, methodology): “…the commendable practice of code reuse (e.g. sorting algorithms), means that many syntactic idioms often fall short of being meaningful, as you can see in this example, from Allamanis and Sutton (2014): FileSystem name= FileSystem.get([Path].toUri(), conf); where name and [Path] are meta-variables.”
Code Completion with Neural Attention and Pointer Networks (2017, methodology): “As the original attention mechanism (Bahdanau, Cho, and Bengio 2014) is used in sequence-to-sequence models, we adapt it into our sequence model and design an attention mechanism for code completion as follows: where W m , W h ∈ R k ∗ k and v ∈ R k are trainable parameters.”
Program Synthesis and Semantic Parsing with Learned Code Idioms (2019, methodology): “As described previously, our code idiom mining is an extension of the procedure developed by Alla-manis et al. [2, 3].”
Learning Programmatic Idioms for Scalable Semantic Parsing (2019, methodology): “This method is in contrast with the approach using probabilistic tree substitution grammars (pTSG) taken by Allamanis and Sutton (2014), who use the explanation quality of an idiom to prioritize idioms that are more interesting, with an end goal to suggest useful idioms to programmers using IDEs.”