一句话：提出迹引导的归纳合成方法，用递归调用迹增强版本空间代数，从少量示例合成递归函数式程序。
该论文研究从输入输出示例合成递归函数式程序时面临的歧义性与泛化性挑战。作者提出一种迹引导的方法，将递归迹（即程序递归子调用）加入程序搜索空间，并设计新的版本空间代数（VSA），用于紧凑表示和高效操作相互一致的递归迹与程序对。基于该方法实现了工具 SyRup，并在先前工作的基准上进行评估。实验表明，与现有合成器相比，SyRup 不仅达到一定成功率所需示例更少，而且对示例质量更不敏感，说明递归迹的引入能有效约束搜索空间并提升归纳合成的泛化能力。
We propose a novel trace-guided approach to tackle the challenges of ambiguity and generalization in synthesis of recursive functional programs from input-output examples. Our approach augments the search space of programs with recursion traces consisting of recursive subcalls of the programs. Our method is based on a new version space algebra (VSA) for succinct representation and efficient manipulation of pairs of recursion traces and programs that are consistent with each other. We have implemented this approach in a tool called SyRup and evaluated it on benchmarks from prior work. Our evaluation demonstrates that SyRup not only requires fewer examples to achieve a certain success rate than existing synthesizers, but is also less sensitive to the quality of the examples.
@article{paperbot1986,
title = {Trace-Guided Inductive Synthesis of Recursive Functional Programs},
author = {Yongwei Yuan and Arjun Radhakrishna and Roopsha Samanta},
journal = {Proceedings of the ACM on Programming Languages},
volume = {7},
number = {PLDI},
year = {2023},
doi = {10.1145/3591255}
}