Semantic Scaffolds for Pseudocode-to-Code Generation (2020)

Abstract: We propose a method for program generation based on semantic scaffolds, lightweight structures 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 annotations and aim to produce a program satisfying execution-based test cases. By using semantic scaffolds during inference, we achieve a 10% absolute improvement in top-100 accuracy over the previous state-of-the-art. Additionally, we require only 11 candidates to reach the top-3000 performance of the previous best approach when tested against unseen problems, demonstrating a substantial improvement in efficiency.

## introduction systems that can map from natural language descriptions of tasks or programs to executable code have the potential for great societal impact, helping to bridge the gap between non-expert users and basic automation or full-fledged software development. accordingly, this area of research has garnered significant interest in recent years, with systems being devised for the translation of natural language specifications into database queries @xcite , if-then programs @xcite , game elements @xcite , and more. while much of the prior work in executable semantic parsing involves short descriptions being mapped into single-line programs, some tasks have recently been proposed that involve multiple natural language utterances on the input side and full programs on the output side, often reaching tens of 1 in function main int main() { 2 n is a long integer 0 long @xmath0; 3 while n is less than o while (@xmath1 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 combinations are invalid due to syntactic and semantic constraints. to address this, we propose a search procedure based on semantic scaffolds, lightweight sum-maries of higher-level program structure that include both syntactic information as well as semantic features such as variable declarations and scope constraints. see section 3 for a more formal definition. while these do not encode the full spectrum of constraints used in some formal program synthesis tools @xcite , they strike a balance between utility, speed, and ease of use, offering substantial improvements in system performance without a significant increase in complexity. in this work we focus on the search-based pseudocode to code (spoc) dataset @xcite due to its challenging multiline programs and availability of input-output test suites to evaluate denotation accuracy. the dataset contains line-level pseudocode annotations for 18,356 c++ programs provided by crowdsource workers from amazon mechanical turk. as in the approach of @xcite , we first obtain candidate code fragments for each line using an off-the-shelf neural machine translation system. we then aim to find the highestscoring combination of fragments that results in a valid program. although finding the optimal program under this setting is np-hard when variable usage constraints are introduced (see section a.3), we can approximate it with a hierarchical beam search. our algorithm first searches for semantic scaffolds for the program, then assembles fragments together conditioned on these scaffolds. this hierarchical approach speeds up search, produces higher quality variations, and leads to substantial improvements in our system's final accuracy. we achieve a new state-of-the-art by solving 55.1% of the test cases within 100 attempts. this represents a 10.4% absolute improvement over the previous best @xcite , and reaches 81% of our model's oracle performance. when tested against unseen problems (or crowd-workers), our top 11 (or top 52, respectively) candidates have the same performance as their top 3000 candidates, demonstrating marked gains in efficiency. we complement our results with a discussion of specific cases in which our semantic scaffolds use global program context to resolve ambiguities in the pseudocode. we also conduct a manual error analysis of 200 failures to better characterize the limitations of our method and suggest possible extensions for future work. our contributions are summarized as follows: in this work, we focus on the spoc dataset introduced by @xcite . ## implementation 2 empty pseudocode around 26% of the lines in the data set do not have pseudocode annotations. they usually correspond to lines of code that do not have semantically meaningful information, such as "int main() {", "{", "}", etc. @xcite replaced these empty pseudocode lines with the ground truth code, effectively giving this information away to the search algorithm. we did not use the gold code pieces for these lines, which makes our task more challenging. model training we use opennmt @xcite with its default settings to translate pseudocode into code piece candidates. our model is a two-layer lstm seq2seq model with hidden size 512, an attention mechanism @xcite and copy pointers @xcite . we estimate the fraction problems solvable given infinite search budget and 100 candidates per line as in @xcite to obtain an oracle bound on performance. due to slight difference in hyperparameters and tokenization method, our model has higher ceiling: on the unseen worker (problems) test set, the oracle performance foot_2 is 74.4% (60.5%), compared to 71.4% (55.2%) in previous work. across all test examples, the oracle performance is 68%. parsing code pieces since no off-the-shelf c++ parser extracts the information we need from code pieces, we implement our own primary expression parser to extract high level control information. we rely on the following heuristic assumptions to parse the code pieces generated by the model: (1) a code piece belongs to only one variable scope; (2) the generation of every primary expression terminal symbol lies in one line. our parser fails on less than 0.01% of the code pieces in the dataset. while selecting the candidates for each line, we immediately reject the ungrammatical pieces we cannot parse. without deliberate implementation optimization, this parsing operation takes on average 2.6 seconds to process all the top 100 code pieces for a problem -approximately the same wallclock time as 1 compilation attempt. enumerate all possible programs, find the right solution and f converges to 1. direct comparison on f values hence becomes meaningless as b increases. to address this deficiency, we define a lead metric l a 1 ,a 2 (b) equal to the extra budget x needed by algorithm a 2 to reach the same level of performance as a 1 given budget b. formally, ## analysis 7.1 program candidate variations beam search has the problem of producing fewer variations at the beginning of the search. such a weakness might be tolerable if we only care about the top 1 candidate, but becomes disastrous in a search setting where we want the top b candidates, whose variation is typically spread across the entire program. we describe the following procedure to formally define this intuition. we first aggregate code piece choices for each line for all the top b programs. as shown in figure 8 (a), we construct a matrix such that each column corresponds to a full program candidate; the number r in the i th row and j th column means that on line i, the j th full program candidate chooses the r th code piece candidate (i.e. y ic @xmath2. then we can build a prefix tree (figure 8(b) ) by treating each column as a string, where each traversal from the root to a leaf is a complete candidate program y. we define the representative branch/program as a traversal from the root to a leaf that always chooses the child that contains the most leaves (with ties being broken randomly). for each of the remaining b -1 programs/traversals, we find the smallest line number where it starts to diverge from the representative branch. among these b -1 programs, we count the fraction of divergences that take place in the first/second half of the lines. for example, in figure 8 (b), 0% of the divergences occur in the first half. we compare hierarchical vs. regular beam search under syntactic constraints with different beam widths w : hierarchical @xmath3, 50 and regular @xmath4, 200. we group the programs by length l, consider the top @xmath5. the results can be seen in