Elamur Research⌕
☰
home / papers / 2014 / Mining Idioms from Source Code

Mining Idioms from Source Code

Paper · 2014 · Miltiadis Allamanis and Charles Sutton

Summary

The authors pose a new task: automatically finding code idioms. An idiom here is a syntactic fragment that recurs across different projects, serves a single semantic purpose and contains metavariables, such as a loop body or a variable name. Modern IDEs only allow such templates to be defined manually. As a result, a programmer who has just started working with a language or library is left without suggestions.

The proposed system, Haggis, represents idioms as fragments of abstract syntax trees (ASTs). It learns without supervision using a nonparametric Bayesian probabilistic tree substitution grammar (pTSG) borrowed from NLP. Haggis does not simply search for frequent subtrees. It keeps only those fragments that explain the corpus better, that is, that increase its probability under the model. This filters out templates that are common but meaningless.

The system was applied to popular open-source Java projects from GitHub. The idioms it found occur across different projects and in examples from StackOverflow. They describe object creation, exception handling and resource management. The work shows that statistical NLP methods are suitable for code analysis and can provide suggestions in an IDE.

Key points

  • 67% of the idioms found in the training projects from GitHub also appear in an independent set of code snippets from StackOverflow.
  • Idioms can be suggested based on the imported packages alone. When suggestions are shown in 20% of cases, recall-at-rank-5 is 76%.
  • Idioms can be general to the language (a loop over an array), tied to a library (closing an android.database.Cursor in a finally block) or project-specific. The association between idioms and packages was measured with lift on the examples of android.location, android.net.wifi and org.hibernate.
  • Idioms differ from code clones: they recur across different projects and have "gaps" for expressions and blocks. What distinguishes them from API mining is their syntactic structure.
  • Some idioms point to shortcomings of the language. An example is several consecutive catch blocks, which Java 7 replaced with the multi-catch construct.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of EdinburghEdinburgh · United Kingdom396 works · 82,279 citations

 Fields, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksInformation Systems · 1,888 works

🧭 Topics 2Research subjects and languages the work is about.Code & programming languages · 194 worksIdioms & multiword expressions · 223 works

Cite

Cite as Miltiadis Allamanis and Charles Sutton. 2014. Mining Idioms from Source Code. arXiv:1404.0417.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1145/2635868.2635901 · arXiv 1404.0417

@misc{allamanis2014mining,
  title = {{Mining Idioms from Source Code}},
  author = {Miltiadis Allamanis and Charles Sutton},
  year = {2014},
  doi = {10.1145/2635868.2635901},
  eprint = {1404.0417},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1145/2635868.2635901}
}

References

55 references, 1 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. M. Acharya, T. Xie, J. Pei, and J. Xu. Mining API patterns as partial orders from source code: from usage scenarios to specifications. In Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering,… find
  2. M. Allamanis and C. Sutton. Mining source code repositories at massive scale using language modeling. In MSR, 2013. find
  3. M. Allamanis, E. T. Barr, C. Bird, and C. Sutton. Learning natural coding conventions. arXiv preprint arXiv:1402.4182, 2014. — [arXiv:1402.4182](https://arxiv.org/abs/1402.4182) find
  4. A. Bacchelli. Mining challenge 2013: StackOverflow. In The 10th Working Conference on Mining Software Repositories, 2013. find
  5. B. S. Baker. A program for identifying duplicated code. Computing Science and Statistics, pages 49–49, 1993. find
  6. I. D. Baxter, A. Yahin, L. Moura, M. Sant’Anna, and L. Bier. Clone detection using abstract syntax trees. In Software Maintenance, 1998. Proceedings., International Conference on, pages 368–377. IEEE, 1998. find
  7. J. Campbell, A. Hindle, and J. N. Amaral. Syntax errors just aren’t natural: Improving error reporting with language models. find
  8. S. Chuan. JavaScript Patterns Collection. http://shichuan.github.io/javascript-patterns/, 2014. Visited Feb 2014. ↗
  9. T. Cohn, P. Blunsom, and S. Goldwater. Inducing tree-substitution grammars. The Journal of Machine Learning Research, 9999:3053–3096, 2010. find
  10. R. Cottrell, R. J. Walker, and J. Denzinger. Semi-automating small-scale source code reuse via structural correspondence. In Proceedings of the 16th ACM SIG-SOFT International Symposium on Foundations of software engineering, pages 214–225. ACM, 2008. find
  11. Eclipse-Contributors. Eclipse JDT. eclipse.org/jdt, 2014. Visited Mar 2014. find
  12. J. I. Editors. Java Idioms. http://c2.com/ppr/wiki/JavaIdioms/JavaIdioms.html, 2014. Visited Feb 2014. ↗
  13. R. Falke, P. Frenzel, and R. Koschke. Empirical evaluation of clone detection using syntax suffix trees. Empirical Software Engineering, 13(6):601–643, 2008. find
  14. M. Gabel and Z. Su. A study of the uniqueness of source code. In Proceedings of the eighteenth ACM SIGSOFT international symposium on Foundations of software engineering, pages 147–156. ACM, 2010. find
  15. A. Gelman, J. B. Carlin, H. S. Stern, D. B. Dunson, A. Vehtari, and D. B. Rubin. Bayesian data analysis. CRC Press, 2013. find
  16. S. J. Gershman and D. M. Blei. A tutorial on Bayesian nonparametric models. Journal of Mathematical Psychology, 56(1):1–12, 2012. find
  17. I. Grigorik. GitHub Archive. www.githubarchive.org, 2014. Visited Mar 2014. find
  18. A. Hindle, E. T. Barr, Z. Su, M. Gabel, and P. Devanbu. On the naturalness of software. In ICSE, 2012. find
  19. N. L. Hjort. Bayesian nonparametrics. Number 28. Cambridge University Press, 2010. find
  20. R. Holmes, R. J. Walker, and G. C. Murphy. Approximate structural context matching: An approach to recommend relevant examples. Software Engineering, IEEE Transactions on, 32(12):952–970, 2006. find
  21. F. Jacob and R. Tairas. Code template inference using language models. In Proceedings of the 48th Annual Southeast Regional Conference, page 104. ACM, 2010. find
  22. JetBrains. High-speed coding with Custom Live Templates. bit.ly/1o8R8Do, 2014. Visited Mar 2014. find
  23. L. Jiang, G. Misherghi, Z. Su, and S. Glondu. Deckard: Scalable and accurate tree-based detection of code clones. In Proceedings of the 29th international conference on Software Engineering, pages 96–105. IEEE Computer Society, 2007. find
  24. A. Jiménez, F. Berzal, and J.-C. Cubero. Frequent tree pattern mining: A survey. Intelligent Data Analysis, 14 (6):603–622, 01 2010. find
  25. T. Kamiya, S. Kusumoto, and K. Inoue. CCFinder: a multilinguistic token-based code clone detection system for large scale source code. Software Engineering, IEEE Transactions on, 28(7):654–670, 2002. find
  26. C. J. Kapser and M. W. Godfrey. “Cloning considered harmful” considered harmful: patterns of cloning in software. Empirical Software Engineering, 13(6):645– 692, 2008. find
  27. M. Kim, V. Sazawal, D. Notkin, and G. Murphy. An empirical study of code clone genealogies. In ACM SIGSOFT Software Engineering Notes, volume 30, pages 187–196. ACM, 2005. find
  28. K. A. Kontogiannis, R. DeMori, E. Merlo, M. Galler, and M. Bernstein. Pattern matching for clone and concept detection. In Reverse engineering, pages 77–108. Springer, 1996. find
  29. R. Koschke, R. Falke, and P. Frenzel. Clone detection using abstract syntax suffix trees. In Reverse Engineering, 2006. WCRE’06. 13th Working Conference on, pages 253–262. IEEE, 2006. find
  30. I. Kuzborskij. Large-scale pattern mining of computer program source code. Master’s thesis, University of Edinburgh, 2011. find
  31. Z. Li, S. Lu, S. Myagmar, and Y. Zhou. CP-Miner: Finding copy-paste and related bugs in large-scale software code. Software Engineering, IEEE Transactions on, 32(3):176–192, 2006. find
  32. P. Liang, M. I. Jordan, and D. Klein. Type-based MCMC. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 573– 581. Association for Computational Linguistics, 2010. find
  33. C. J. Maddison and D. Tarlow. Structured generative models of natural source code. arXiv preprint arXiv:1401.0514, 2014. find
  34. A. Menon, O. Tamuz, S. Gulwani, B. Lampson, and A. Kalai. A machine learning framework for programming by example. In Proceedings of The 30th International Conference on Machine Learning, pages 187–195, 2013. find
  35. K. P. Murphy. Machine learning: a probabilistic perspective. MIT Press, 2012. find
  36. T. T. Nguyen, H. A. Nguyen, N. H. Pham, J. M. Al-Kofahi, and T. N. Nguyen. Graph-based mining of multiple object usage patterns. In Proceedings of the the 7th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, pages… find
  37. T. T. Nguyen, A. T. Nguyen, H. A. Nguyen, and T. N. Nguyen. A statistical semantic language model for source code. In FSE, 2013. find
  38. Oracle. Java SE Documentation: Catching Multiple Exception Types and Rethrow-ing Exceptions with Improved Type Checking. http://docs.oracle.com/javase/7/docs/technotes/guides/language/catch-multiple.html, 2014. Visited Feb 2014. ↗
  39. P. Orbanz and Y. W. Teh. Bayesian nonparametric models. In Encyclopedia of Machine Learning. Springer, 2010. find
  40. M. Post and D. Gildea. Bayesian learning of a tree substitution grammar. In Proceedings of the ACL-IJCNLP 2009 Conference Short Papers, pages 45–48. Association for Computational Linguistics, 2009. find
  41. E. Recommenders-Contributors. Eclipse Snip-Match. wiki.eclipse.org/Recommenders/Snipmatch, 2014. Visited Mar 2014. find
  42. M. Research. High-speed coding with Custom Live Templates. research.microsoft.com/apps/video/dl.aspx?id=208961, 2014. Visited Mar 2014. find
  43. C. K. Roy and J. R. Cordy. A survey on software clone detection research. Technical report, Queen’s University at Kingston, Ontario, 2007. find
  44. C. K. Roy, J. R. Cordy, and R. Koschke. Comparison and evaluation of code clone detection techniques and tools: A qualitative approach. Science of Computer Programming, 74(7):470–495, 2009. find
  45. J. Sethuraman. A constructive definition of Dirichlet priors. Technical report, DTIC Document, 1991. find
  46. Y. W. Teh. A hierarchical Bayesian language model based on Pitman-Yor processes. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pages 985–992, 2006.
  47. Y. W. Teh and M. I. Jordan. Hierarchical Bayesian nonparametric models with applications. In N. Hjort, C. Holmes, P. Müller, and S. Walker, editors, Bayesian Nonparametrics: Principles and Practice. Cambridge University Press, 2010. find
  48. A. Termier, M.-C. Rousset, and M. Sebag. Treefinder: a first step towards XML data mining. In Data Mining, 2002. ICDM 2003. Proceedings. 2002 IEEE International Conference on, pages 450–457. IEEE, 2002. find
  49. R. Waldron. Principles of Writing Consistent, Idiomatic JavaScript. https://github.com/rwaldron/idiomatic.js/, 2014. Visited Feb 2014. ↗
  50. J. Wang, Y. Dang, H. Zhang, K. Chen, T. Xie, and D. Zhang. Mining succinct and high-coverage API usage patterns from source code. In Mining Software Repositories (MSR), 2013 10th IEEE Working Conference on, pages 319–328. IEEE, 2013. find
  51. Wikibooks. More C++ Idioms. http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms, 2013. Visited Feb 2014. ↗
  52. C. K. Williams and C. E. Rasmussen. Gaussian Processes for Machine Learning, 2006. find
  53. M. J. Zaki. Efficiently mining frequent trees in a forest. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 71–80. ACM, 2002. find
  54. M. J. Zaki. Efficiently mining frequent trees in a forest: Algorithms and applications. Knowledge and Data Engineering, IEEE Transactions on, 17(8):1021–1035, 2005. find
  55. H. Zhong, T. Xie, L. Zhang, J. Pei, and H. Mei. MAPO: Mining and recommending API usage patterns. In ECOOP 2009–Object-Oriented Programming, pages 318– 343. Springer, 2009. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/allamanis-2014-mining-idioms-source-code/