Exploring Dynamic Selection of Branch Expansion Orders for Code Generation

Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, pages 5076–5085 August 1–6, 2021. ©2021 Association for Computational Linguistics 5076 Exploring Dynamic Selection of Branch Expansion Orders for Code Generation Hui Jiang1,2∗ Chulun Zhou1,2∗ Fandong Meng3 Biao Zhang4 Jie Zhou3 Degen Huang5 Qingqiang Wu1,2 Jinsong Su1,2† 1School of Informatics, Xiamen University 2Institute of Artificial Intelligence, Xiamen University 3Pattern Recognition Center, WeChat AI, Tencent Inc, China 4School of Informatics, University of Edinburgh 5Dalian University of Technology {hjiang,clzhou}@stu.xmu.edu.cn {fandongmeng,withtomzhou}@tencent.com B.Zhang@ed.ac.uk huangdg@dlut.edu.cn {wuqq,jssu}@xmu.edu.cn Abstract Due to the great potential in facilitating soft- ware development, code generation has at- tracted increasing attention recently. Gener- ally, dominant models are Seq2Tree models, which convert the input natural language de- scription into a sequence of tree-construction actions corresponding to the pre-order traver- sal of an Abstract Syntax Tree (AST). How- ever, such a traversal order may not be suit- able for handling all multi-branch nodes. In this paper, we propose to equip the Seq2Tree model with a context-based Branch Selector, which is able to dynamically determine opti- mal expansion orders of branches for multi- branch nodes. Particularly, since the selec- tion of expansion orders is a non-differentiable multi-step operation, we optimize the selector through reinforcement learning, and formulate the reward function as the difference of model losses obtained through different expansion or- ders. Experimental results and in-depth analy- sis on several commonly-used datasets demon- strate the effectiveness and generality of our ap- proach. We have released our code at https: //github.com/DeepLearnXMU/CG-RL. 1 Introduction Code generation aims at automatically generating a source code snippet given a natural language (NL) description, which has attracted increasing atten- tion recently due to its potential value in simplify- ing programming. Instead of modeling the abstract syntax tree (AST) of code snippets directly, most of methods for code generation convert AST into a sequence of tree-construction actions. This al- lows for using natural language generation (NLG) models, such as the widely-used encoder-decoder Joint work with Pattern Recognition Center, WeChat AI, Tencent Inc, China. *Equal contribution †Corresponding author models, and obtains great success (Ling et al., 2016; Dong and Lapata, 2016, 2018; Rabinovich et al., 2017; Yin and Neubig, 2017, 2018, 2019; Hay- ati et al., 2018; Sun et al., 2019, 2020; Wei et al., 2019; Shin et al., 2019; Xu et al., 2020; Xie et al., 2021). Specifically, an encoder is first used to learn word-level semantic representations of the input NL description. Then, a decoder outputs a sequence of tree-construction actions, with which the cor- responding AST is generated through pre-order traversal. Finally, the generated AST is mapped into surface codes via certain deterministic func- tions. Generally, during the generation of dominant Seq2Tree models based on pre-order traversal, branches of each multi-branch nodes are expanded in a left-to-right order. Figure 1 gives an exam- ple of the NL-to-Code conversion conducted by a Seq2Tree model. At the timestep t1, the model gen- erates a multi-branch node using the action a1 …

Content truncated to 500 words