Semantic Scaffolds for Pseudocode-to-Code Generation

Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 2283–2295 July 5 - 10, 2020. c⃝2020 Association for Computational Linguistics 2283 Semantic Scaffolds for Pseudocode-to-Code Generation Ruiqi Zhong Mitchell Stern Computer Science DivisionDan Klein University of California, Berkeley {ruiqi-zhong,mitchell,klein}@berkeley.edu Abstract We propose a method for program generation based on semantic scaffolds, lightweight struc- tures representing the high-level semantic and syntactic composition of a program. By first searching over plausible scaffolds then using these as constraints for a beam search over programs, we achieve better coverage of the search space when compared with existing techniques. We apply our hierarchical search method to the SPoC dataset for pseudocode- to-code generation, in which we are given line-level natural language pseudocode anno- tations and aim to produce a program satisfy- ing execution-based test cases. By using se- mantic scaffolds during inference, we achieve a 10% absolute improvement in top-100 ac- curacy over the previous state-of-the-art. Ad- ditionally, we require only 11 candidates to reach the top-3000 performance of the pre- vious best approach when tested against un- seen problems, demonstrating a substantial im- provement in efficiency. 1 Introduction Systems that can map from natural language de- scriptions of tasks or programs to executable code have the potential for great societal impact, help- ing to bridge the gap between non-expert users and basic automation or full-fledged software de- velopment. Accordingly, this area of research has garnered significant interest in recent years, with systems being devised for the translation of natu- ral language specifications into database queries (Wang et al., 2018), if-then programs (Chen et al., 2016), game elements (Ling et al., 2016), and more. While much of the prior work in executable se- mantic parsing involves short descriptions being mapped into single-line programs, some tasks have recently been proposed that involve multiple natu- ral language utterances on the input side and full programs on the output side, often reaching tens of Line Pseudocode Code 1 in function main int main() { 2 n is a long integer 0 long n = 0; 3 while n is less than o while (n < ‘o’) { 4 … … 5 close while scope } Translate while (n < o) { while (n < ‘o’) Other wrong candidates error: use of undeclared identifier 'o' error: missing '{' Figure 1: Pseudocode is translated to code for each line and combined to form a valid program. Certain combi- nations are invalid due to syntactic and semantic con- straints. lines in length and including non-trivial state ma- nipulation. Examples include the Magic the Gather- ing and Hearthstone datasets (Ling et al., 2016) de- rived from trading cards and Java or Python classes implementing their behavior in a game engine, the CONCODE dataset (Iyer et al., 2018) consisting of Java documentation strings and method bodies, and the NAPS and SPoC datasets (Zavershynskyi et al., 2018; Kulal et al., 2019) consisting of pseudocode annotations and source code for programming com- petition problems. Past approaches to these large-scale language- to-code …

Content truncated to 500 words