Trampoline 求值驱动 | Codeboy's Blog

形式陈述

每一步先返回，再开始下一步

trampoline 用显式协议管理控制转移：一个任务要么返回最终结果 Done(v)，要么返回下一步的无参数函数 More(thunk)。类型形状为

T(A)=\operatorname{Done}(A)+\operatorname{More}(1\to T(A)).

驱动器使用宿主的普通循环：

text

run(job):
    while job is More(thunk):
        job = thunk()
    require job is Done(value)
    return value

每次 thunk 完成一段有限工作后必须返回一个新任务。只有旧调用已经回到循环，循环才调用下一个 thunk，因此不要求宿主优化尾调用。若 thunk 内又进行任意深的普通递归，协议本身不会替它消除这些调用。[1, §§1.1–2]

将已写成CPS的纯程序转换时，把每个用户函数的尾调用 f(args) 改成 More(lambda: fT(args))，最终续延改为产生 Done。传给函数的续延在以后调用时，也属于必须延迟的用户函数调用。原语计算保留原有顺序，且要求一次任务里的原语和非递归辅助工作使用有界宿主调用深度。本页没有并发调度、I/O 挂起、异常清理或资源配额语义。

同时延迟进入与恢复

用不依赖大阶乘的求和例说明，原递归是 $S(0)=0$ 、 $S(n)=n+S(n-1)$ ，输入整数 $n\ge0$ 。CPS 版本把待做的加法放进续延。完整延迟版为

text

sumT(n,k):
    if n == 0: return More(lambda: k(0))
    return More(lambda:
        sumT(n-1, lambda v: More(lambda: k(n+v))))

run(sumT(n, lambda v: Done(v)))

两个 More 分别保护递归进入和逐层恢复；基例调用 k 也被延迟。只在下降阶段包装一次，回升阶段仍可能连续调用 n 个续延函数，因而不能由“函数表面尾递归”推出常数宿主栈。

直觉

返回任务对象不等于立即执行它

More(lambda: f(x)) 是把工作装进一个尚未调用的函数。More(f(x)) 会先执行 f，等它返回后才构造 More；如果 f 继续递归，这一写法在把控制交回驱动器之前就已经积累了调用栈。差别发生在参数求值时，不是 More 这个标签自带了特殊运行时能力。

同样，不能把驱动器写成宿主中的普通递归 run(thunk())，然后又假设宿主没有尾调用优化。原论文用 Scheme 的尾调用表达驱动器；本文把这一处写成 while，明确展示在普通宿主上的实现条件。

例子与边界

把续延也变成数据，完整走到 6

对上例实际使用去函数化：最终续延为 End，待加 n 的续延为 Plus(n,K)。任务分成 Enter(n,K)、Resume(v,K)、Halt(v)，规则为

\begin{aligned} \operatorname{Enter}(n,K)&\to\operatorname{Enter}(n-1,\operatorname{Plus}(n,K))&&n>0,\\ \operatorname{Enter}(0,K)&\to\operatorname{Resume}(0,K),\\ \operatorname{Resume}(v,\operatorname{Plus}(n,K))&\to\operatorname{Resume}(n+v,K),\\ \operatorname{Resume}(v,\operatorname{End})&\to\operatorname{Halt}(v). \end{aligned}

每条规则由同一个 while 执行，不递归调用下一条规则。n=3 的状态依次为

text

Enter(3, End)
Enter(2, Plus(3,End))
Enter(1, Plus(2,Plus(3,End)))
Enter(0, Plus(1,Plus(2,Plus(3,End))))
Resume(0, Plus(1,Plus(2,Plus(3,End))))
Resume(1, Plus(2,Plus(3,End)))
Resume(3, Plus(3,End))
Resume(6, End)
Halt(6)

共有 8 次转移，峰值 3 个 Plus 帧。高阶 More 版本先在驱动器外调用一次 sumT 来创建初任务，随后有 $2n+1$ 次 thunk 调用；一阶任务机把基例转移与最终 Halt 转移都计入循环，故有 $2n+2$ 次转移。两个计数的起点不同，但输出一致。

n等于3的一阶求和机依次经过九个状态、八次转移；while每轮只推进一步，峰值三个堆框架。

三种空间不能合成一句“常数空间”

在以上协议下，驱动器和单次 thunk 的宿主控制深度有一个不随 n 增长的上界。但待做的加法仍保存 n 个续延闭包或 Plus 帧，峰值堆控制数据为 $O(n)$ ；这不是常数总空间。若改用带累加器的尾递归求和，则可不保存这条待恢复链，额外控制数据才可降为常数。

整数 n、部分和及最终答案的位数也会增长，按真实大整数运算计费时不能把每次加法都当一条等成本指令。本文的 $O(n)$ 时间是 $O(n)$ 次控制转移和整数运算的计数；位复杂度另计。若把所有状态都记录成调试轨迹，即使计算本来只保留常数个对象，记录本身也会增加空间。

宿主自动回收旧对象、引用计数连锁释放的内部实现以及有限内存失败，不属于这里证明的“用户函数调用深度”模型。下载的大输入测试展示所用宿主上的完成结果，不是所有运行时的资源定理。

推论与应用

用不变量解释它为什么只是换了执行方式

给 K 一个含义 $\llbracket\operatorname{End}\rrbracket(v)=v$ ， $\llbracket\operatorname{Plus}(n,K)\rrbracket(v)=\llbracket K\rrbracket(n+v)$ 。Enter(m,K) 代表待完成答案 $\llbracket K\rrbracket(S(m))$ ；Resume(v,K) 代表 $\llbracket K\rrbracket(v)$ 。四条规则分别使用求和递推或续延定义，因此都保持这份答案。有限 n 先严格减少到 0，再逐个弹出有限帧，最后返回 $S(n)$ 。

推广到 CPS 转换时，一次原来的尾调用对应“返回 More，再由驱动器调用”的有限管理步骤。它不改变下一函数、实参或续延；只要没有把延迟边界跨过可见副作用，就能建立执行模拟。本文选纯语言，避免把工作分批后对并发观察、异常时机或取消响应的影响隐藏掉。

尾调用帧复用是在机器调用约定内复用返回续延，trampoline 则把转移变成用户可检查的返回值协议。两者都能处理某些深递归，但额外堆分配、分派频率和调试栈形态可以不同。去函数化也不自动保证常数栈；必须像这里一样让各个恢复步骤回到外层循环。

迁移测试先输入 10,000，核对结果 50,005,000 和 20,001 次 thunk 调用；再把内层 lambda v: More(lambda: k(n+v)) 错改为 lambda v: k(n+v)，指出恢复链会在哪里变成嵌套宿主调用。最后将显式任务的 Plus 改成乘法帧，检查不变量应随之改变，而不是沿用求和证明。终点任务提供复算入口。

参考资料

[1] Steven E. Ganz、Daniel P. Friedman、Mitchell Wand，Trampolined Style，ICFP 1999，pp.18–27，§1.1 的 done/doing 单计算驱动与 §2 的尾调用变换、Figure 1。本文只采用单计算的控制返回协议，不展开论文的线程调度扩展。

[2] Olivier Danvy、Lasse R. Nielsen，Defunctionalization at Work，BRICS RS-01-23，2001，§3：将有限续延函数形状改为显式数据与分派。本文 Plus 任务机和计数为独立构造。

形式陈述 ​

每一步先返回，再开始下一步 ​

同时延迟进入与恢复 ​

返回任务对象不等于立即执行它 ​

把续延也变成数据，完整走到 6 ​

三种空间不能合成一句“常数空间” ​

用不变量解释它为什么只是换了执行方式 ​

反向链接

形式陈述

每一步先返回，再开始下一步

同时延迟进入与恢复

返回任务对象不等于立即执行它

把续延也变成数据，完整走到 6

三种空间不能合成一句“常数空间”

用不变量解释它为什么只是换了执行方式