PLDI 2025
Mon 16 - Fri 20 June 2025 Seoul, South Korea
Wed 18 Jun 2025 11:50 - 12:10 at Orchid - Synthesis Chair(s): Sébastien Bardin

We present the first technique to synthesize programs that compose side-effecting functions, pure functions, and control flow, from partial traces containing records of only the side-effecting functions. This technique can be applied to synthesize API composing scripts from logs of calls made to those APIs, or a script from traces of system calls made by a workload, for example. All of the provided traces are positive examples, meaning that they describe desired behavior. Our approach does not require negative examples. Instead, it generalizes over the examples and uses cost metrics to prevent over-generalization. Because the problem is too complex for traditional monolithic program synthesis techniques, we propose a new combination of optimizing rewrites and syntax-guided program synthesis. The resulting program is correct by construction, so its output will always be able to reproduce the input traces.
We evaluate the quality of the programs synthesized when considering various optimization metrics and the synthesizer's efficiency on real-world benchmarks. The results show that our approach can generate useful real-world programs.

Wed 18 Jun

Displayed time zone: Seoul change

10:30 - 12:10
SynthesisPLDI Research Papers at Orchid
Chair(s): Sébastien Bardin CEA LIST, University Paris-Saclay
10:30
20m
Talk
Programming by Navigation
PLDI Research Papers
Justin Lubin University of California at Berkeley, Parker Ziegler University of California at Berkeley, Sarah E. Chasins University of California at Berkeley
DOI Pre-print
10:50
20m
Talk
A Concurrent Approach to String Transformation Synthesis
PLDI Research Papers
Yuantian Ding Purdue University, Xiaokang Qiu Purdue University
DOI
11:10
20m
Talk
Exact Loop Bound Analysis
PLDI Research Papers
Daniel Riley Florida State University, Grigory Fedyukovich Florida State University
DOI
11:30
20m
Talk
Multi-stage Relational Programming
PLDI Research Papers
Michael Ballantyne Northeastern University, Rafaello Sanna Harvard University, Jason Hemann Seton Hall University, William E. Byrd University of Alabama at Birmingham, Nada Amin Harvard University
DOI
11:50
20m
Talk
Program Synthesis From Partial Traces
PLDI Research Papers
Margarida Ferreira Carnegie Mellon University; INESC-ID; Instituto Superior Técnico - University of Lisbon, Victor Nicolet Amazon, Joey Dodds Amazon, Daniel Kroening Amazon
DOI