Elamur Research⌕
☰
home / papers / 2018 / A General Path-Based Representation for Predicting Program Properties

A General Path-Based Representation for Predicting Program Properties

Paper · 2018 · Uri Alon, Meital Zilberstein, Omer Levy et al.

Summary

The paper addresses the automatic prediction of program properties: variable names, method names, and expression types. The central problem here is how to represent a program for a machine learning model. Features are usually hand-engineered for each task and each language. The authors instead propose a general, purely syntactic representation that is built automatically. The program is parsed into an AST, and each code element is described by a set of paths between nodes of the tree. A path consists of nodes and of up and down movements between them. To keep the number of paths from growing too large, they can be abstracted, limited by length and width hyperparameters, or sampled. The approach is implemented in the PIGEON tool and evaluated on JavaScript, Java, Python, and C# with two learning algorithms: CRF and word2vec. In every evaluated task and language, AST paths performed better than hand-crafted task-specific features. For JavaScript and Java, where prior methods already existed, they outperformed those methods. Thus a single representation works across languages, tasks, and models, and it requires no semantic analysis.

Key points

  • An AST path is a sequence of syntax tree nodes connected by up (↑) and down (↓) movements. The general family of such representations also includes n-ary paths and paths that do not end in a leaf.
  • PIGEON is a cross-language tool that predicts names of program elements, method names, and expression types for JavaScript, Java, Python, and C#.
  • The comparison was made against UnuglifyJS (Raychev et al.) and against the approach of Allamanis et al. to method names. AST paths distinguish code fragments that look identical to the hand-crafted features of UnuglifyJS.
  • The trade-off between accuracy and training time is tunable: sampling paths barely reduces accuracy but noticeably shortens training.
  • The closest analogue in NLP is Parse Tree Paths (Gildea and Jurafsky), which are used in Semantic Role Labeling.

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 WashingtonSeattle · United States422 works · 213,538 citations🎓Technion – Israel Institute of TechnologyHaifa · Israel59 works · 7,590 citations

 Fields, topics and concepts

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

Cite

Cite as Uri Alon, Meital Zilberstein, Omer Levy and Eran Yahav. 2018. A General Path-Based Representation for Predicting Program Properties. arXiv:1803.09544.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1803.09544 · arXiv 1803.09544

@misc{alon2018general,
  title = {{A General Path-Based Representation for Predicting Program Properties}},
  author = {Uri Alon, Meital Zilberstein, Omer Levy and Eran Yahav},
  year = {2018},
  doi = {10.48550/arxiv.1803.09544},
  eprint = {1803.09544},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1803.09544}
}

References

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

  1. [n. d.]. JavaParser. http://javaparser.org. ↗
  2. [n. d.]. Roslyn. https://github.com/dotnet/roslyn. ↗
  3. [n. d.]. UglifyJS. https://github.com/mishoo/UglifyJS. ↗
  4. [n. d.]. UnuglifyJS. https://github.com/eth-srl/UnuglifyJS. ↗
  5. Miltiadis Allamanis, Earl T. Barr, Christian Bird, and Charles Sutton. 2014. Learning Natural Coding Conventions. In Proceedings of the 22Nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2014). ACM, New York, NY, USA, 281– 293. https://doi.org/10.1145/2635868.263588… — [doi:10.1145/2635868.2635883](https://doi.org/10.1145/2635868.2635883) ↗
  6. Miltiadis Allamanis, Earl T. Barr, Christian Bird, and Charles Sutton. 2015. Suggesting Accurate Method and Class Names. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering (ESEC/FSE 2015). ACM, New York, NY, USA, 38–49. https://doi.org/10.1145/2786805.2786849 — [doi:10.1145/2786805.2786849](https://doi.org/10.1145/2786805.2786849) ↗
  7. Miltiadis Allamanis, Hao Peng, and Charles A. Sutton. 2016. A Convolutional Attention Network for Extreme Summarization of Source Code. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016. 2091– 2100. http://jmlr.org/proceeding… ↗
  8. Miltiadis Allamanis and Charles Sutton. 2014. Mining Idioms from Source Code. In Proceedings of the 22Nd ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2014). ACM, New York, NY, USA, 472–483. https://doi.org/10.1145/2635868.2635901 ↗
  9. Miltiadis Allamanis, Daniel Tarlow, Andrew D. Gordon, and Yi Wei. 2015. Bimodal Modelling of Source Code and Natural Language. In Proceedings of the 32nd International Conference on Machine Learning (JMLR Proceedings), Vol. 37. JMLR.org, 2123–2132.
  10. Yoshua Bengio, Réjean Ducharme, Pascal Vincent, and Christian Janvin. 2003. A Neural Probabilistic Language Model. J. Mach. Learn. Res. 3 (March 2003), 1137–1155. http://dl.acm.org/citation.cfm?id=944919.944966 ↗
  11. Benjamin Bichsel, Veselin Raychev, Petar Tsankov, and Martin Vechev. 2016. Statistical Deobfuscation of Android Applications. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS ’16). ACM, New York, NY, USA, 343–355. https://doi.org/10.1145/2976749.2978422 — [doi:10.1145/2976749.2978422](https://doi.org/10.1145/2976749.2978422) ↗
  12. Pavol Bielik, Veselin Raychev, and Martin T. Vechev. 2016. PHOG: Probabilistic Model for Code. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016. 2933–2942. http://jmlr.org/proceedings/papers/v48/bielik16.html ↗
  13. S. Butler, M. Wermelinger, Y. Yu, and H. Sharp. 2009. Relating Identifier Naming Flaws and Code Quality: An Empirical Study. In 2009 16th Working Conference on Reverse Engineering. 31–35. https://doi.org/10.1109/WCRE.2009.50 — [doi:10.1109/wcre.2009.50](https://doi.org/10.1109/wcre.2009.50) ↗
  14. Ronan Collobert and Jason Weston. 2008. A Unified Architecture for Natural Language Processing: Deep Neural Networks with Multitask Learning. In Proceedings of the 25th International Conference on Machine Learning (ICML ’08). ACM, New York, NY, USA, 160–167. https://doi.org/10.1145/1390156.1390177 — [doi:10.1145/1390156.1390177](https://doi.org/10.1145/1390156.1390177) ↗
  15. Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa. 2011. Natural language processing (almost) from scratch. Journal of Machine Learning Research 12, Aug (2011), 2493–2537.
  16. Aditya Desai, Sumit Gulwani, Vineet Hingorani, Nidhi Jain, Amey Karkare, Mark Marron, Sailesh R, and Subhajit Roy. 2016. Program Synthesis Using Natural Language. In Proceedings of the 38th International Conference on Software Engineering (ICSE ’16). ACM, New York, NY, USA, 345–356. https://doi.org/… — [doi:10.1145/2884781.2884786](https://doi.org/10.1145/2884781.2884786) find
  17. Daniel Gildea and Daniel Jurafsky. 2002. Automatic Labeling of Semantic Roles. Comput. Linguist. 28, 3 (Sept. 2002), 245–288. https://doi.org/10.1162/089120102760275983 ↗
  18. Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. find
  19. Trevor Hastie, Robert Tibshirani, and Jerome Friedman. 2001. The Elements of Statistical Learning. Springer New York Inc., New York, NY, USA. find
  20. Abram Hindle, Earl T. Barr, Zhendong Su, Mark Gabel, and Premkumar Devanbu. 2012. On the Naturalness of Software. In Proceedings of the 34th International Conference on Software Engineering (ICSE ’12). IEEE Press, Piscataway, NJ, USA, 837–847. http://dl.acm.org/citation.cfm?id=2337223.2337322 ↗
  21. Einar W. Høst and Bjarte M. Østvold. 2009. Debugging Method Names. In Proceedings of the 23rd European Conference on ECOOP 2009 — Object-Oriented Programming (Genoa). Springer-Verlag, Berlin, Heidelberg, 294–317. https://doi.org/10.1007/978-3-642-03013-0_14 — [doi:10.1007/978-3-642-03013-0_14](https://doi.org/10.1007/978-3-642-03013-0_14) ↗
  22. Srinivasan Iyer, Ioannis Konstas, Alvin Cheung, and Luke Zettlemoyer. 2016. Summarizing Source Code using a Neural Attention Model. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 1: Long Papers. http://… find
  23. Svetoslav Karaivanov, Veselin Raychev, and Martin Vechev. 2014. Phrase-Based Statistical Translation of Programming Languages. In Proceedings of the 2014 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software (Onward! 2014). ACM, New York, NY, USA, 173–184… — [doi:10.1145/2661136.2661148](https://doi.org/10.1145/2661136.2661148) find
  24. D. Koller, N. Friedman, L. Getoor, and B. Taskar. 2007. Graphical Models in a Nutshell. In Introduction to Statistical Relational Learning, L. Getoor and B. Taskar (Eds.). MIT Press. find
  25. John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. 2001. Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. In Proceedings of the Eighteenth International Conference on Machine Learning (ICML ’01). Morgan Kaufmann Publishers Inc., San Francisco, CA… find
  26. Omer Levy and Yoav Goldberg. 2014. Dependency-Based Word Embeddings.. In ACL (2). Citeseer, 302–308. find
  27. Omer Levy and Yoav Goldberg. 2014. Neural Word Embeddings as Implicit Matrix Factorization. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada. 2177–2185. find
  28. Ben Liblit, Andrew Begel, and Eve Sweeser. 2006. Cognitive Perspectives on the Role of Naming in Computer Programs. In Proceedings of the 18th Annual Psychology of Programming Workshop. Psychology of Programming Interest Group, Sussex, United Kingdom. find
  29. Cristina V. Lopes, Petr Maj, Pedro Martins, Vaibhav Saini, Di Yang, Jakub Zitny, Hitesh Sajnani, and Jan Vitek. 2017. DéJàVu: A Map of Code Duplicates on GitHub. Proc. ACM Program. Lang. 1, OOPSLA, Article 84 (Oct. 2017), 28 pages. https://doi.org/10.1145/3133908 — [doi:10.1145/3133908](https://doi.org/10.1145/3133908) ↗
  30. Chris J. Maddison and Daniel Tarlow. 2014. Structured Generative Models of Natural Source Code. In Proceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32 (ICML’14). JMLR.org, II–649–II–657. http://dl.acm.org/citation.cfm?id=3044805.3044965 ↗
  31. Oren Melamud, Omer Levy, and Ido Dagan. 2015. A Simple Word Embedding Model for Lexical Substitution. In Proceedings of the 1st Workshop on Vector Space Modeling for Natural Language Processing, VS@NAACL-HLT 2015, June 5, 2015, Denver, Colorado, USA. 1–7. http://aclweb.org/anthology/W/W15/W15-1501.p… ↗
  32. Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient Estimation of Word Representations in Vector Space. CoRR abs/1301.3781 (2013). http://arxiv.org/abs/1301.3781 ↗
  33. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Distributed Representations of Words and Phrases and Their Compositionality. In Proceedings of the 26th International Conference on Neural Information Processing Systems (NIPS’13). Curran Associates Inc., USA, 3111–3119.…
  34. Lili Mou, Ge Li, Lu Zhang, Tao Wang, and Zhi Jin. 2016. Convolutional Neural Networks over Tree Structures for Programming Language Processing. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI’16). AAAI Press, 1287–1293. http://dl.acm.org/citation.cfm?id=3015812.30160… ↗
  35. Judea Pearl. 2011. Bayesian networks. (2011). find
  36. Judea Pearl. 2014. Probabilistic reasoning in intelligent systems: networks of plausible inference. Elsevier. find
  37. Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. GloVe: Global Vectors for Word Representation. In Empirical Methods in Natural Language Processing (EMNLP). 1532–1543. http://www.aclweb.org/anthology/D14-1162 ↗
  38. Veselin Raychev, Pavol Bielik, and Martin Vechev. 2016. Probabilistic Model for Code with Decision Trees. In Proceedings of the 2016 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA 2016). ACM, New York, NY, USA, 731–747. https://doi.o… ↗
  39. Veselin Raychev, Pavol Bielik, Martin Vechev, and Andreas Krause. 2016. Learning Programs from Noisy Data. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’16). ACM, New York, NY, USA, 761–774. https://doi.org/10.1145/2837614.2837671 ↗
  40. Veselin Raychev, Martin Vechev, and Andreas Krause. 2015. Predicting Program Properties from "Big Code". In Proceedings of the 42Nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’15). ACM, New York, NY, USA, 111–124. https://doi.org/10.1145/2676726.2677009 ↗
  41. Veselin Raychev, Martin Vechev, and Eran Yahav. 2014. Code Completion with Statistical Language Models. SIGPLAN Not. 49, 6 (June 2014), 419–428. https://doi.org/10.1145/2666356.2594321 — [doi:10.1145/2666356.2594321](https://doi.org/10.1145/2666356.2594321) ↗
  42. Shai Shalev-Shwartz and Shai Ben-David. 2014. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, New York, NY, USA. find
  43. Charles Sutton and Andrew McCallum. 2012. An Introduction to Conditional Random Fields. Found. Trends Mach. Learn. 4, 4 (April 2012), 267–373. https://doi.org/10.1561/2200000013 — [doi:10.1561/2200000013](https://doi.org/10.1561/2200000013) ↗
  44. Armstrong A. Takang, Penny A. Grubb, and Robert D. Macredie. 1996. The effects of comments and identifier names on program comprehensibility: an experimental investigation. J. Prog. Lang. 4, 3 (1996), 143–167. http://compscinet.dcs.kcl.ac.uk/JP/jp040302.abs.html ↗
  45. Joseph Turian, Lev Ratinov, and Yoshua Bengio. 2010. Word Representations: A Simple and General Method for Semi-supervised Learning. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL ’10). Association for Computational Linguistics, Stroudsburg, PA, USA,…
  46. Meital Zilberstein and Eran Yahav. 2016. Leveraging a Corpus of Natural Language Descriptions for Program Similarity. In Proceedings of the 2016 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward! 2016). ACM, New York, NY, USA, 197–211. https… — [doi:10.1145/2986012.2986013](https://doi.org/10.1145/2986012.2986013) find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/alon-2018-general-path-based-representation-predicting/