SPoC: Search-based Pseudocode to Code

By Sumith Kulal, Panupong Pasupat, Kartik Chandra, Mina Lee, Oded Padon, A. Aiken, Percy Liang. 2019

329 citations recorded by the source corpus.

We consider the task of mapping pseudocode to long programs that are functionally correct. Given test cases as a mechanism to validate programs, we search over the space of possible translations of the pseudocode to find a program that passes the validation. However, without proper credit assignment to localize the sources of program failures, it is difficult to guide search toward more promising programs. We propose to perform credit assignment based on signals from compilation errors, which constitute 88.7% of program failures. Concretely, we treat the translation of each pseudocode line as a discrete portion of the program, and whenever a synthesized program fails to compile, an error localization method tries to identify the portion of the program responsible for the failure. We then focus search over alternative translations of the pseudocode for those portions. For evaluation, we collected the SPoC dataset (Search-based Pseudocode to Code) containing 18,356 programs with human-authored pseudocode and test cases. Under a budget of 100 program compilations, performing search improves the synthesis success rate over using the top-one translation of the pseudocode from 25.6% to 44.7%.

Subfields: Information Systems, Software, Code Generation & Program Synthesis

How researchers see this paper

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

In Information Systems

In Software

In Code Generation & Program Synthesis

Citations in the corpus

PaLM: Scaling Language Modeling with Pathways (2022, methodology): “Following Kulal et al. (2019), we report results using the pass@k metric, in which for each problem in the test set, k samples of source code are drawn from the model, and a problem is counted as solved if any sample solves it.”
Competition-level code generation with AlphaCode (2022, methodology): “, 2017), convert pseudocode to code (Kulal et al., 2019), directly generate a target program (Devlin et al.”
Program Synthesis with Large Language Models (2021, methodology): “Such datasets include the Natural Program Synthesis (NAPS) dataset [Zavershynskyi et al., 2018], the Search-based Pseudocode to Code (SPoC) dataset [Kulal et al., 2019], the APPS dataset [Hendrycks et al., 2021], the PROGRES dataset [Alet et al., 2021], and the CodeNet dataset [Puri et al., 2021].”
Evaluating Large Language Models Trained on Code (2021, methodology): “As a consequence, recent works in unsupervised code translation (Lachaux et al., 2020) and pseudocode-to-code translation (Kulal et al., 2019) have turned to functional correctness instead, where a sample is considered correct if it passes a set of unit tests.”
Graph-based, Self-Supervised Program Repair from Diagnostic Feedback (2020, methodology): “This stage is analogous to the input encoding in Kulal et al. (2019).”
InCoder: A Generative Model for Code Infilling and Synthesis (2022, background): “, input-output examples [12, 28, 19, 13], partial implementations [58], or natural language descriptions [74, 73, 72, 42, 18] of the desired program as input.”
CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis (2022, methodology): “, 2016), pseudo-code (Kulal et al., 2019), a docstring and function signature (Chen et al.”
MultiPL-E: A Scalable and Polyglot Approach to Benchmarking Neural Code Generation (2023, background): “Moreover, of these datasets, only Kulal et al.’s includes unit tests to enable evaluation of code correctness [8].”
CodeGeeX: A Pre-Trained Model for Code Generation with Multilingual Benchmarking on HumanEval-X (2023, methodology): “Specifically, we use the unbiased method to estimate pass@ 𝑘 [7]: where 𝑛 is the total number of generations ( 𝑛 =200 in this work), 𝑘 is the sampling budget (typically 𝑘 ∈ { 1, 10, 100 } ), and 𝑐 is the number of samples that pass all test cases.”
SantaCoder: don't reach for the stars! (2023, neutral): “Many single-language benchmarks for evaluating code completion exist (Kulal et al., 2019; Iyer et al., 2018; Zhong et al., 2017; Yu et al., 2018; Austin et al., 2021; Hendrycks et al., 2021; Chen et al., 2021; Austin et al., 2021; Athiwaratkun et al., 2022; Lai et al., 2022).”
LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code (2024, methodology): “We use the Pass@ 1 (Kulal et al., 2019; Chen et al., 2021) metric for our evaluations.”
Measuring Coding Challenge Competence With APPS (2021, methodology): “We compared to several datasets in the (Kulal et al., 2019; Yu et al., 2018; Raychev et al., 2016; Iyer et al., 2018; Lu et al., 2021) main paper.”
Multi-lingual Evaluation of Code Generation Models (2022, methodology): “We use pass@k scores (Kulal et al., 2019) with the unbiased estimate presented in (Chen et al., 2021) as the metrics for our evaluation, where each task is considered successful if any of the k samples are correct.”
WILDS: A Benchmark of in-the-Wild Distribution Shifts (2020, neutral): “…engineering in various ways: automatic code completion (Raychev et al., 2014; Svyatkovskiy et al., 2019), program synthesis (Bunel et al., 2018; Kulal et al., 2019), program repair (Vasic et al., 2019; Yasunaga and Liang, 2020), code search (Husain et al., 2019), and code summarization…”
The Robots Are Here: Navigating the Generative AI Revolution in Computing Education (2023, background): “com /daset/m pp Seah-Based Pseucode-toCode (PO C[111] Psedocode descrinsofcoding pblem s”
LLM-Assisted Code Cleaning For Training Accurate Code Generators (2023, methodology): “We assess the code generation performance of the models using the P ASS @ K metric (Kulal et al., 2019; Chen et al., 2021), which evaluates the functional correctness of generated programs.”
Energy-Based Models for Code Generation under Compilability Constraints (2021, background): “Taking that one step further, Kulal et al. (2019) use compilation errors (with their precise location) to guide search over the space of possible programs.”
Leveraging Automated Unit Tests for Unsupervised Code Translation (2021, background): “…of the code and typically correlate poorly with the correctness of the generated function, prompting the use of new metrics checking if the generated solution passes series of test cases (Kulal et al., 2019; Roziere et al., 2020; Hendrycks et al., 2021; Chen et al., 2021; Drain et al., 2021).”
Large Language Monkeys: Scaling Inference Compute with Repeated Sampling (2024, unknown): “One of the most effective use cases is coding [48, 15, 38], where performance continues to scale up to a million samples and verification tools (e.g. unit tests) are often available to automatically score every candidate solution.”