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 JunDisplayed 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 20mTalk | 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 20mTalk | A Concurrent Approach to String Transformation Synthesis PLDI Research Papers DOI | ||
11:10 20mTalk | Exact Loop Bound Analysis PLDI Research Papers DOI | ||
11:30 20mTalk | 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 20mTalk | 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 |