Elamur Research⌕
☰
home / papers / 2019 / Structural Language Models of Code

Structural Language Models of Code

Paper · 2019 · Uri Alon, Roy Sadaka, Omer Levy et al.

Summary

The authors address the task of any-code completion: a missing fragment of a program must be reconstructed from the rest of its code, with no restriction on the vocabulary or syntactic form of the result. Earlier approaches either worked with narrowly specialized languages or generated only simple expressions without user-defined functions. The paper proposes structural language modeling (SLM). A program is represented as an abstract syntax tree (AST), and its probability is decomposed by the chain rule into a product of conditional probabilities of individual nodes, ordered by a depth-first traversal. The neural network predicts each next node from a set of partial paths in the tree: from every already known leaf, and from the root, to the node currently being expanded. To control the number of child nodes and the length of identifiers, auxiliary nodes EOS_node and EOS_tok are added. The model describes the context and the missing fragment jointly, without a separate encoder and decoder. On Java and C#, SLM outperforms seq2seq and a number of structural models. The paper shows that explicitly accounting for the syntax of the language improves the generation of arbitrary code.

Key points

  • Java, any-code completion: exact match on the first attempt (acc@1) is 18.04%, and among five candidates (acc@5) it is 24.83%. The previous best result was 16.93% and 23.17%.
  • C#, the restricted task of Brockschmidt et al. (2019): acc@1 is 37.61%, compared with 26.42% for previous models.
  • Node-by-node generation instead of grammar rules: the model first decides that there will be a function call here, and only then chooses the object and the method. In production-based approaches, the method name has to be chosen before the object on which it is called.
  • Technical details: identifiers are split into subtokens by camelCase. Paths are encoded by an LSTM, and shared path prefixes are computed once and cached, which noticeably speeds up training and inference. An ablation study showed that jointly modeling the context and the target works better than a separate encoder and decoder.
  • Resources: the code, data and trained models are published at github.com/tech-srl/slm-code-generation, and an online demo is available at AnyCodeGen.org.

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,644 citations🎓Technion – Israel Institute of TechnologyHaifa · Israel59 works · 7,598 citations

 Fields, topics and concepts

📚 Shelves 6The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 worksInformation Systems · 1,888 worksComputer Science Applications · 184 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 4,145 works

Cite

Cite as Uri Alon, Roy Sadaka, Omer Levy and Eran Yahav. 2019. Structural Language Models of Code. arXiv:1910.00577.

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

@misc{alon2019structural,
  title = {{Structural Language Models of Code}},
  author = {Uri Alon, Roy Sadaka, Omer Levy and Eran Yahav},
  year = {2019},
  doi = {10.48550/arxiv.1910.00577},
  eprint = {1910.00577},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1910.00577}
}

References

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

  1. Aharoni, R. and Goldberg, Y. Towards string-to-tree neural machine translation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 132–140, 2017.
  2. Allamanis, M. The adverse effects of code duplication in machine learning models of code. In Proceedings of the 2019 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software, pp. 143–153.
  3. Allamanis, M., Tarlow, D., Gordon, A., and Wei, Y. Bimodal modelling of source code and natural language. In International conference on machine learning, pp. 2123–2132, 2015.
  4. Allamanis, M., Peng, H., and Sutton, C. A convolutional attention network for extreme summarization of source code. In International conference on machine learning, pp. 2091–2100, 2016.
  5. Allamanis, M., Brockschmidt, M., and Khademi, M. Learning to represent programs with graphs. In International Conference on Learning Representations, 2018.
  6. Alon, U. and Yahav, E. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05205, 2020. — [arXiv:2006.05205](https://arxiv.org/abs/2006.05205) find
  7. Alon, U., Zilberstein, M., Levy, O., and Yahav, E. A general path-based representation for predicting program properties. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 404–419, 2018.
  8. Alon, U., Brody, S., Levy, O., and Yahav, E. code2seq: Generating sequences from structured representations of code. In International Conference on Learning Representations, 2019a.
  9. Alon, U., Zilberstein, M., Levy, O., and Yahav, E. code2vec: Learning distributed representations of code. Proceedings of the ACM on Programming Languages, 3(POPL):1–29, 2019b. find
  10. Amodio, M., Chaudhuri, S., and Reps, T. arXiv:1705.09231, 2017.
  11. Neural attribute machines for program generation. Balog, M., Gaunt, A. L., Brockschmidt, M., Nowozin, S., and Tarlow, D. Deepcoder: Learning to write programs. In International Conference on Learning Representations, 2017.
  12. Bielik, P., Raychev, V., and Vechev, M. Phog: probabilistic model for code. In International Conference on Machine Learning, pp. 2933–2942, 2016. find
  13. Brockschmidt, M., Allamanis, M., Gaunt, A. L., and Polozov, O. Generative code modeling with graphs. In International Conference on Learning Representations, 2019. find
  14. Brody, S., Alon, U., and Yahav, E. Neural edit completion. arXiv preprint arXiv:2005.13209, 2020. — [arXiv:2005.13209](https://arxiv.org/abs/2005.13209) find
  15. Chen, X., Liu, C., and Song, D. Tree-to-tree neural networks for program translation. In Advances in Neural Information Processing Systems, pp. 2547–2557, 2018. find
  16. Devlin, J., Uesato, J., Bhupatiraju, S., Singh, R., Mohamed, A.-r., and Kohli, P. Robustfill: Neural program learning under noisy i/o. In International Conference on Machine Learning, pp. 990–998, 2017. find
  17. Dong, L. and Lapata, M. Coarse-to-fine decoding for neural semantic parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 731–742, 2018. find
  18. Ellis, K., Nye, M., Pu, Y., Sosa, F., Tenenbaum, J., and Solar-Lezama, A. Write, execute, assess: Program synthesis with a repl. In Advances in Neural Information Processing Systems, pp. 9169–9178, 2019.
  19. Fernandes, P., Allamanis, M., and Brockschmidt, M. Structured neural summarization. In International Conference on Learning Representations, 2019. find
  20. Gaunt, A. L., Brockschmidt, M., Kushman, N., and Tarlow, D. Differentiable programs with neural libraries. In International Conference on Machine Learning, pp. 1213–1222, 2017. arXiv preprint Green, C. Application of theorem proving to problem solving. In Readings in Artificial Intelligence, pp. 202… find
  21. Gu, J., Lu, Z., Li, H., and Li, V. O. Incorporating copying mechanism in sequence-to-sequence learning. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1631–1640, 2016.
  22. Gulwani, S. Automating string processing in spreadsheets using input-output examples. In Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pp. 317–330, 2011.
  23. Gulwani, S., Polozov, O., Singh, R., et al. Program synthesis. Foundations and Trends® in Programming Languages, 4 (1-2):1–119, 2017.
  24. Iyer, S., Konstas, I., Cheung, A., and Zettlemoyer, L. Mapping language to code in programmatic context. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 1643–1652, 2018.
  25. Iyer, S., Cheung, A., and Zettlemoyer, L. Learning programmatic idioms for scalable semantic parsing. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pp. 5429–5438, 201… find
  26. Kingma, D. and Ba, J. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
  27. Klein, G., Kim, Y., Deng, Y., Senellart, J., and Rush, A. M. Opennmt: Open-source toolkit for neural machine translation. In Proceedings of ACL 2017, System Demonstrations, pp. 67–72, 2017.
  28. Ling, W., Blunsom, P., Grefenstette, E., Hermann, K. M., Kočiskỳ, T., Wang, F., and Senior, A. Latent predictor networks for code generation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 599–609, 2016.
  29. Luong, M.-T., Pham, H., and Manning, C. D. Effective approaches to attention-based neural machine translation. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pp. 1412–1421, 2015.
  30. Maddison, C. and Tarlow, D. Structured generative models of natural source code. In International Conference on Machine Learning, pp. 649–657, 2014. find
  31. Murali, V., Qi, L., Chaudhuri, S., and Jermaine, C. Neural sketch learning for conditional program generation. In International Conference on Learning Representations, 2018. find
  32. Parisotto, E., Mohamed, A.-r., Singh, R., Li, L., Zhou, D., and Kohli, P. Neuro-symbolic program synthesis. In International Conference on Learning Representations, 2017.
  33. Pnueli, A. and Rosner, R. On the synthesis of a reactive module. In Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pp. 179–190. ACM, 1989. find
  34. Polozov, O. and Gulwani, S. Flashmeta: a framework for inductive program synthesis. In Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, pp. 107– 126, 2015. find
  35. Rabinovich, M., Stern, M., and Klein, D. Abstract syntax networks for code generation and semantic parsing. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1139–1149, 2017. find
  36. Raychev, V., Bielik, P., Vechev, M., and Krause, A. Learning programs from noisy data. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 761–774, 2016. find
  37. Si, X., Yang, Y., Dai, H., Naik, M., and Song, L. Learning a meta-solver for syntax-guided program synthesis. In International Conference on Learning Representations, 2019. find
  38. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. Attention is all you need. In Advances in Neural Information Processing Systems, pp. 6000–6010, 2017.
  39. Waldinger, R. J. and Lee, R. C. Prow: A step toward automatic program writing. In Proceedings of the 1st international joint conference on Artificial intelligence, pp. 241–252, 1969. find
  40. Xiao, C., Dymetman, M., and Gardent, C. Sequence-based structured prediction for semantic parsing. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1341–1350, 2016. find
  41. Yin, P. and Neubig, G. A syntactic neural model for general-purpose code generation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 440–450, 2017.
  42. Yin, P., Neubig, G., Allamanis, M., Brockschmidt, M., and Gaunt, A. L. Learning to represent edits. In International Conference on Learning Representations, 2019. find
  43. Young, H., Bastani, O., and Naik, M. Learning neurosymbolic generative models via program synthesis. In International Conference on Machine Learning, pp. 7144–7153, 2019. find
  44. Yu, T., Li, Z., Zhang, Z., Zhang, R., and Radev, D. Typesql: Knowledge-based type-aware neural text-to-sql generation. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pp. 588–5…
  45. Zhao, R., Bieber, D., Swersky, K., and Tarlow, D. Neural networks for modeling source code edits. arXiv preprint arXiv:1904.02818, 2019. — [arXiv:1904.02818](https://arxiv.org/abs/1904.02818) find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/alon-2019-structural-language-models-code/