一等续延与 call/cc | Codeboy's Blog

形式陈述

把剩余计算变成一个值

一等续延是能够像函数一样被传递、返回和以后调用的控制值。本文用 call/cc 捕获整个当前续延，具体语义沿用CEK 机器的词法闭包与从左到右按值顺序，扩展整数、变量、λ、应用、加法及 callcc(e)。模型纯粹、单线程、单返回值，没有 store、异常、dynamic-wind、提示符或宿主外部事件。

值增加 $\operatorname{Cont}(K)$ ，其中 K 是一条不可变续延帧链。帧链保存的是之后要做什么及这些工作需要的环境，不是程序从开头到现在的运行历史。callcc 先把参数表达式求成函数值 f，再把当时的 K 保存为值并传给 f。

捕获与恢复的规则不同

把 CEK 的表达式状态写成 $\langle e,\rho,K\rangle$ ，返回值状态写成 $\langle v,K\rangle_v$ 。增加临时帧 Cap，得到

\langle\operatorname{callcc}(e),\rho,K\rangle \to\langle e,\rho,\operatorname{Cap}(K)\rangle,

\langle f,\operatorname{Cap}(K)\rangle_v \to\operatorname{Apply}(f,\operatorname{Cont}(K),K).

Apply 是“函数和实参都已求好”的辅助状态。普通闭包沿原 CEK 规则进入定义环境，并保留调用处 K；保存的续延则使用

\operatorname{Apply}(\operatorname{Cont}(K_s),v,K_c) \to\langle v,K_s\rangle_v.

$K_c$ 被丢弃，而不是接在 $K_s$ 后面。这使控制值的调用具有退出当前计算位置的效果；它与一般函数返回到调用处不是一回事。若 f 不调用传给它的控制值，而是正常返回 w，w 会沿捕获时的 K 继续执行。[1, §6.4]

直觉

保存的是未来的工作清单

当程序正算 $1+\square$ ，当前续延就是“拿到一个数，加 1，返回顶层”。call/cc 把这份清单交给 f。f 可以照常完成，也可以在后来某个位置把一个值直接交给这份旧清单。

要特别区分两个时刻：创建 Cont(K) 并不会立即跳走，f 仍要获得这个参数并开始执行；真正改变控制的是以后调用 Cont(K)。它也不等于保存所有变量内容的快照。本文纯模型没有写入；若将来加入可变存储，保存控制帧并不自动撤销两次调用之间的写入。

例子与边界

为什么结果是 6，而不是 106

计算

text

1 + callcc(lambda k. 100 + k(5))

以 Add(n,K) 记“将返回值加 n 后交给 K”，End 记顶层结束。捕获时保存的是 $K_s=\operatorname{Add}(1,\operatorname{End})$ 。进入 f 后，k 指向 Cont( $K_s$ )。求 100+k(5) 时，调用 k 的当前位置变为

K_c=\operatorname{Add}(100,\operatorname{Add}(1,\operatorname{End})).

恢复规则把 5 交给 $K_s$ ，丢弃 $K_c$ ，于是只做 $1+5=6$ 。100 那一层没有返回值可接，因为它已被退出。对照 1+callcc(lambda k.105)：f 根本不调用 k，正常将 105 交给捕获时的 K，结果便是 106。

嵌套call/cc中exit保存加1，inner保存先加10再加1；分别恢复得到6与16。

一等与多次调用各意味着什么

callcc(lambda k.k) 在顶层可以直接返回一个保存 End 的控制值。把这个结果保存为 s，然后在两次独立的顶层求值中分别调用 s(7)、s(9)，会分别把 7、9 送到同一个保存的终点。这展示它能离开最初的捕获调用后继续存在；两个调用并没有破坏保存的不可变 K。

R5RS 的 escape procedure 允许保存并多次调用。这里用持久帧链建模同样的多次恢复能力。某些其他控制接口是一次性的，第一次恢复后便消耗控制值，不能套用本模型。反过来，多次调用也不表示会自动把每次结果汇集成列表；每次 call/cc 续延调用都先按规则丢弃自己的当前续延。[1, §6.4]

它不是通用的资源回滚

一个计算可能已输出日志或写入共享单元，再通过保存的续延离开。这些动作是否撤销取决于另加的状态或事务机制，不能由“回到原来的控制位置”推出。完整 Scheme 还有 dynamic-wind，进入和离开动态范围时可执行 before/after；本页明确排除它，所以这套三条规则不是完整 Scheme 实现。

现代语言中的同名 call/cc 还可能受提示符边界限制，或对跨线程调用另有规定。本文讨论的是给定顶层以内的完整续延，不将所有同名 API 视为相同。要只保存某个显式边界以内的工作，并在完成后返回调用处，可比较shift/reset 分界续延。

推论与应用

与求值上下文之间的对应

CEK 的每个帧记录一个缺少结果的求值位置；把帧链逐层读回，就得到一个求值上下文 E。普通返回是把 v 填进 E 再继续；捕获把这个 E 对应的帧链保留为 Cont；恢复则以保存的 E 替换调用处的上下文。因此证明机器实现符合规则时，核心不变量是“当前帧链解释为当前剩余上下文”，不是“栈高度一直不变”。

若用不可变链并允许共享，捕获完整 K 只保存头指针，恢复也只更换当前指针，二者可为 $O(1)$ ；建立普通新帧仍逐项分配。若宿主用可变连续栈，安全保存可能需要复制 d 个帧，成本为 $O(d)$ 。保存一个指针仍可能让长帧链及其中环境长期可达，所以常数捕获时间不推出常数保留空间。下载执行器默认还记录事件：捕获时枚举保存帧，恢复时枚举调用处与保存帧，另需与这些帧数成正比的时间和日志空间。传入 record_events=False 可关闭这项观察；上面的常数界只计共享帧链的核心保存/切换，不包含日志或随后执行的工作。

异常式提前退出是一个用途，但普通异常处理器一般没有“把控制对象返回并任意次恢复”的接口。用一等续延构造搜索或协程还要设计结果传递和状态协议；仅有捕获规则并不会自动提供公平调度、状态隔离或取消清理。

迁移到嵌套捕获：计算 1+callcc(lambda exit.10+callcc(lambda inner.exit(5)))。外层 exit 保存 1+[]，内层 inner 保存 1+(10+[])；调用 exit(5) 得到 6。仅把最内层调用改为 inner(5)，结果变为 16，因为它保留了内层捕获时那份加 10 的工作。分别列出两个保存 K 和最后调用处 K，说明为何捕获更晚不等于跳得更远。终点任务的执行器会同时输出捕获、丢弃与恢复的帧标签。

参考资料

[1] Richard Kelsey、William Clinger、Jonathan Rees（编），Revised⁵ Report on the Algorithmic Language Scheme，1998，§6.4，印刷 pp.33–34：call-with-current-continuation 的捕获、放弃调用处续延、无限存续与多次调用；§1.1 给出对象存续约定。本文排除报告中的多值及 dynamic-wind 扩展。

[2] Matthias Felleisen、Robert Hieb，The Revised Report on the Syntactic Theories of Sequential Control and State，Theoretical Computer Science 103(2)，1992，235–271。控制与上下文的理论背景；本页的规则具体通过已有 CEK 定义与上述 R5RS 接口展开。

形式陈述 ​

把剩余计算变成一个值 ​

捕获与恢复的规则不同 ​

保存的是未来的工作清单 ​

为什么结果是 6，而不是 106 ​

一等与多次调用各意味着什么 ​

它不是通用的资源回滚 ​

与求值上下文之间的对应 ​

反向链接