Semantic Scaffolds for Pseudocode-to-Code Generation

Ruiqi Zhong, Mitchell Stern, Dan Klein


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.
Anthology ID:
2020.acl-main.208
Volume:
Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics
Month:
July
Year:
2020
Address:
Online
Editors:
Dan Jurafsky, Joyce Chai, Natalie Schluter, Joel Tetreault
Venue:
ACL
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
2283–2295
Language:
URL:
https://aclanthology.org/2020.acl-main.208
DOI:
10.18653/v1/2020.acl-main.208
Bibkey:
Cite (ACL):
Ruiqi Zhong, Mitchell Stern, and Dan Klein. 2020. Semantic Scaffolds for Pseudocode-to-Code Generation. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 2283–2295, Online. Association for Computational Linguistics.
Cite (Informal):
Semantic Scaffolds for Pseudocode-to-Code Generation (Zhong et al., ACL 2020)
Copy Citation:
PDF:
https://aclanthology.org/2020.acl-main.208.pdf
Software:
 2020.acl-main.208.Software.zip
Video:
 http://slideslive.com/38929435
Code
 ruiqi-zhong/SemanticScaffold
Data
SPoC