Semantic Scaffolds for Pseudocode-to-Code Generation

By Ruiqi Zhong, Mitchell Stern, Daniel Klein. 2020

26 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Hardware and Architecture, Software, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Percy Liang
2. Graham Neubig
3. Michihiro Yasunaga
4. Bogdan Vasilescu
5. Frank F. Xu
6. Nan Duan

In Hardware and Architecture

1. Ge Li
2. Percy Liang
3. Graham Neubig
4. Bogdan Vasilescu
5. Frank F. Xu

In Software

1. Neel Sundaresan
2. Alexey Svyatkovskiy
3. Daya Guo
4. Nan Duan
5. Colin B. Clement
6. Shao Kun Deng
7. Michihiro Yasunaga
8. Dawn Drain

In Natural Language Processing

1. Graham Neubig
2. Nan Duan
3. Frank F. Xu
4. Michihiro Yasunaga
5. Percy Liang
6. Ming Zhou
7. Duyu Tang
8. Neel Sundaresan

Citations in the corpus

• Graph-based, Self-Supervised Program Repair from Diagnostic Feedback (2020, background): “We note that a concurrent work (Zhong et al., 2020) uses semantic constraints of programs to improve the search and achieves state-of-the-art results (46.1% / 62.8% on TestP / TestW).”
• CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding and Generation (2021, methodology): “The program synthesis [47, 58, 62, 74, 17, 40, 90] extends the text-to-code generation task aims to generate programs from a specification [21], such as pseudocode, natural language description, and input/output examples.”
• In-IDE Code Generation from Natural Language: Promise and Challenges (2021, methodology): “Some work also generate programs from easier-towrite pseudo-code [56, 127].”