一句话：提出首个从仅记录副作用调用的部分轨迹中，合成含副作用函数、纯函数与控制流程序的方法。
本文研究从部分轨迹合成程序的问题，其中轨迹只记录副作用函数调用，却需要生成能组合副作用函数、纯函数与控制流的脚本；该设定可服务于从 API 调用日志合成 API 编排脚本，或从系统调用轨迹合成工作负载脚本。所有提供轨迹均为正例，无需负例。方法上，作者先对示例进行泛化，并用代价度量避免过度泛化；由于问题对传统单体合成过于复杂，提出将优化重写与语法引导程序合成相结合。合成程序按构造保证正确，即输出总能重现输入轨迹。作者在真实基准上评估不同优化度量下合成程序的质量及合成器效率，结果表明可生成有用的真实程序。
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.
@article{paperbot3109,
title = {Program Synthesis from Partial Traces},
author = {Margarida Ferreira and Victor Nicolet and Joey Dodds and Daniel Kroening},
journal = {Proceedings of the ACM on Programming Languages},
volume = {9},
number = {PLDI},
year = {2025},
doi = {10.1145/3729316}
}