Abstract
Synthesizing program code from natural language is a challenging task as natural language utterances tend to be ambiguous and require substantial prior knowledge to interpret. Recent solutions approach these difficulties in different ways. Some models do not constrain their inputs and operate with a large variety of sentences, but tend to be less accurate. Others limit the space of possible inputs, requiring them to meet a fixed structure which makes them more similar to code than language. This paper offers a middle ground between these approaches. We train a transition-based neural network on descriptions of programming tasks generated by using context-free grammar and templates. We show that the model is able to generalize and can solve synthesis problems described in natural language.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Allamanis, M., Tarlow, D., Gordon, A., Wei, Y.: Bimodal modelling of source code and natural language. In: International Conference on Machine Learning, pp. 2123–2132. PMLR (2015)
Andor, D., et al.: Globally normalized transition-based neural networks. arXiv preprint arXiv:1603.06042 (2016)
Bahdanau, D., Cho, K., Bengio, Y.: Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473 (2014)
Budinsky, F.J., Finnie, M.A., Vlissides, J.M., Patsy, S.Y.: Automatic code generation from design patterns. IBM Syst. J. 35(2), 151–171 (1996)
Bunel, R., Hausknecht, M., Devlin, J., Singh, R., Kohli, P.: Leveraging grammar and reinforcement learning for neural program synthesis. arXiv preprint arXiv:1805.04276 (2018)
Fekete, I., Gregorios, T., Pusztai, K.K., Veszprémi, A.: Programming theorems and their applications. Teach. Math. Comput. Sci. 17(2), 213–241 (2019)
Gregorics, T.: Programming theorems on enumerator. Teach. Math. Comput. Sci. Debrecen 8(1), 89–108 (2010)
Gregorics, T.: Force of summation. Teach. Math. Comput. Sci. Debrecen 10(1), 1–15 (2014)
Gregorics, T., Sike, S.: Generic algorithm patterns. In: Proceedings of Formal Methods in Computer Science Education FORMED, pp. 141–150 (2008)
Hemel, Z., Kats, L.C.L., Groenewegen, D.M., Visser, E.: Code generation by model transformation: a case study in transformation modularity. Softw. Syst. Model. 9(3), 375–402 (2010). https://doi.org/10.1007/s10270-009-0136-1
Ling, W., et al.: Latent predictor networks for code generation. arXiv preprint arXiv:1603.06744 (2016)
Luong, M.-T., Pham, H., Manning, C.D.: Effective approaches to attention-based neural machine translation. arXiv preprint arXiv:1508.04025 (2015)
McCracken, D.D., Reilly, E.D.: Backus-Naur form (BNF). In: Encyclopedia of Computer Science, pp. 129–131 (2003)
Oliphant, T.E.: Python for scientific computing. Comput. Sci. Eng. 9(3), 10–20 (2007)
Ouyang, X., Zhou, P., Li, C.H., Liu, L.: Sentiment analysis using convolutional neural network. In: 2015 IEEE International Conference on Computer and Information Technology; Ubiquitous Computing and Communications; Dependable, Autonomic and Secure Computing; Pervasive Intelligence and Computing, pp. 2359–2364. IEEE (2015)
Papineni, K., Roukos, S., Ward, T., Zhu, W.-J.: BLEU: a method for automatic evaluation of machine translation. In: Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pp. 311–318 (2002)
Quirk, C., Mooney, R., Galley, M.: Language to code: learning semantic parsers for if-this-then-that recipes. In: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 878–888 (2015)
Rabinovich, M., Stern, M., Klein, D.: Abstract syntax networks for code generation and semantic parsing. arXiv preprint arXiv:1704.07535 (2017)
Vinyals, O., Fortunato, M., Jaitly, N.: Pointer networks. In: Advances in Neural Information Processing Systems, pp. 2692–2700 (2015)
Wang, D.C., Appel, A.W., Korn, J.L., Serra, C.S.: The Zephyr abstract syntax description language. In: DSL, vol. 97, p. 17 (1997)
Yao, Z., Li, X., Gao, J., Sadler, B., Sun, H.: Interactive semantic parsing for if-then recipes via hierarchical reinforcement learning. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 2547–2554 (2019)
Yin, P., Deng, B., Chen, E., Vasilescu, B., Neubig, G.: Learning to mine aligned code and natural language pairs from stack overflow. In: International Conference on Mining Software Repositories, MSR, pp. 476–486. ACM (2018)
Yin, P., Neubig, G.: TRANX: a transition-based neural abstract syntax parser for semantic parsing and code generation. arXiv preprint arXiv:1810.02720 (2018)
Yin, P., Neubig, G.: TranX GitHub Repository (2018). https://github.com/pcyin/tranX
Bo, Yu., Zong-ben, X., Li, C.: Latent semantic analysis for text categorization using neural network. Knowl.-Based Syst. 21(8), 900–904 (2008)
Acknowledgments
This material is based upon a research accomplished in the framework of EFOP-3.6.3-VEKOP-16-2017-00001: Talent Management in Autonomous Vehicle Control Technologies. The Project is supported by the Hungarian Government and co-financed by the European Social Fund. We would like to thank Tamás Dina for the helpful discussions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendix
Appendix
1.1 A. Our Context-Free Grammar
Our context-free grammar is defined in BNF. The rules are the following:
1.2 B. Hyperparameters
TranX has been trained with the following hyperparameters (Table 2):
1.3 C. The Templates Used for Dataset Generation
In this appendix we provide a list of all the templates used for dataset generation. The templates are separated by an empty line. The last line of each template definition describes the structure of the condition. If the last line is none” then there is no condition for the given template.
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Rikk, R., Várkonyi, T.A., Borsi, Z.R., Pintér, B., Gregorics, T. (2023). Generating Algorithmic Patterns from Semi-structured Input Using a Transition-Based Neural Network. In: Arai, K. (eds) Intelligent Systems and Applications. IntelliSys 2022. Lecture Notes in Networks and Systems, vol 543. Springer, Cham. https://doi.org/10.1007/978-3-031-16078-3_57
Download citation
DOI: https://doi.org/10.1007/978-3-031-16078-3_57
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-16077-6
Online ISBN: 978-3-031-16078-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)