Learning Programmatic Idioms for Scalable Semantic Parsing

Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, pages 5426–5435, Hong Kong, China, November 3–7, 2019. c⃝2019 Association for Computational Linguistics 5426 Learning Programmatic Idioms for Scalable Semantic Parsing Srinivasan Iyer†, Alvin Cheung§ and Luke Zettlemoyer†‡ †Paul G. Allen School of Computer Science and Engineering, Univ. of Washington, Seattle, WA {sviyer, lsz}@cs.washington.edu §Department of Electrical Engineering and Computer Sciences, UC Berkeley, Berkeley, CA akcheung@cs.berkeley.edu ‡ Facebook AI Research, Seattle lsz@fb.com Abstract Programmers typically organize executable source code using high-level coding patterns or idiomatic structures such as nested loops, exception handlers and recursive blocks, rather than as individual code tokens. In contrast, state of the art (SOTA) semantic parsers still map natural language instructions to source code by building the code syntax tree one node at a time. In this paper, we introduce an it- erative method to extract code idioms from large source code corpora by repeatedly col- lapsing most-frequent depth-2 subtrees of their syntax trees, and train semantic parsers to ap- ply these idioms during decoding. Apply- ing idiom-based decoding on a recent context- dependent semantic parsing task improves the SOTA by 2.2% BLEU score while reducing training time by more than 50%. This im- proved speed enables us to scale up the model by training on an extended training set that is 5× larger, to further move up the SOTA by an additional 2.3% BLEU and 0.9% exact match. Finally, idioms also significantly im- prove accuracy of semantic parsing to SQL on the ATIS-SQL dataset, when training data is limited. 1 Introduction When programmers translate Natural Language (NL) specifications into executable source code, they typically start with a high-level plan of the major structures required, such as nested loops, conditionals, etc. and then proceed to fill in spe- cific details into these components. We refer to these high-level structures (Figure 1 (b)) as code idioms (Allamanis and Sutton, 2014). In this pa- per, we demonstrate how learning to use code id- ioms leads to an improvement in model accuracy and training time for the task of semantic parsing, i.e., mapping intents in NL into general purpose source code (Iyer et al., 2017; Ling et al., 2016). ( Expr ) if ParExpr Statement IfOrElse Statement Block Statement Block Statement (b) (a) if ( Expr ) { Expr ; } else { Expr ; } { BlockStatement } { BlockStatement } Expr ; Expr ; else Statement Statement Figure 1: (a) Syntax tree based decoding for seman- tic parsing uses as many as 11 rules (steps) to pro- duce the outer structure of a very frequently used if-then-else code snippet. (b) Direct application of an if-then-else idiom during decoding leads to im- proved accuracy and training time. State-of-the-art semantic parsers are neural encoder-decoder models, where decoding guided by the target programming language gram-is mar (Yin and Neubig, 2017; Rabinovich et al., 2017; Iyer et al., 2018) to ensure syntactically valid programs. For general purpose program- ming …

Content truncated to 500 words