一句话：提出块级剪枝与版本空间学习，从输入输出示例合成递归函数式程序。
该论文研究如何从输入–输出示例合成递归函数式程序。由于递归子表达式需要在目标函数尚未完全定义时构造，合成递归函数十分困难。作者提出“块”的概念，即无递归和条件的直线代码，先为每个示例合成尽可能多的块，再在版本空间学习中搜索递归程序并剪掉与块不一致的候选。论文还利用库函数的采样输入–输出行为实现面向目标的库函数递归程序搜索。系统 Trio 在已有及新合成任务上显著优于先前工作。
Abstract We present a novel approach to synthesizing recursive functional programs from input–output examples. Synthesizing a recursive function is challenging because recursive subexpressions should be constructed while the target function has not been fully defined yet. We address this challenge by using a new technique we call block-based pruning. A block refers to a recursion- and conditional-free expression (i.e., straight-line code) that yields an output from a particular input. We first synthesize as many blocks as possible for each input–output example, and then we explore the space of recursive programs, pruning candidates that are inconsistent with the blocks. Our method is based on an efficient version space learning, thereby effectively dealing with a possibly enormous number of blocks. In addition, we present a method that uses sampled input–output behaviors of library functions to enable a goal-directed search for a recursive program using the library. We have implemented our approach in a system called Trio and evaluated it on synthesis tasks from prior work and on new tasks. Our experiments show that Trio significantly outperforms prior work.
@article{paperbot3325,
title = {Inductive synthesis of structurally recursive functional programs from non-recursive expressions},
author = {HANGYEOL CHO and WOOSUK LEE},
journal = {Journal of Functional Programming},
volume = {35},
year = {2025},
doi = {10.1017/s0956796825100063}
}