“固定一个以λ 演算为核心的左到右传值调用源语言,以及答案类型 $R$。对源项 $e$,写 $\mathcal C\llbracket e\rrbracket k$ 表示“求值 $e$ 后把结…”
形式陈述 ​
续延(continuation)表示某个程序点之后“剩余的计算”。若当前子计算产生类型
续延传递风格把隐含的结果去向变成函数参数;完整的语法导向条款、答案类型翻译、行政归约与模拟关系见续延传递风格变换。本页关注续延这个对象本身。第一类续延允许程序捕获、存储并再次调用当前续延,不要求整段程序预先经过 CPS 翻译。
控制系统还需区分无界续延与只捕获到最近提示符的受限续延,以及只能恢复一次的 one-shot 续延与可重复恢复的 multi-shot 续延;这些选择决定哪些控制片段能被捕获和重放。
直觉
普通执行栈隐式记录“当前函数返回后去哪里、拿结果做什么”,续延把这份信息变成可以命名和传递的对象。计算 1 + (2 * 3) 时,求 2 * 3 的续延就是“把结果加一并作为最终答案”;它只描述未来,不包含已经完成的过去。把控制流函数化后,返回、异常、跳转和协程都能用“选择哪个续延调用”统一解释。类比调用栈很有用,但第一类续延比普通栈更强,因为它可被保存、复制甚至多次恢复。
例子与边界
在 1 + (2 * 3) 中,子计算 2 * 3 的续延可写成
边界是把续延误认为“最终结果”。续延接收当前结果后才产生后续行为,本身不是当前值。多次调用捕获的续延可能重复执行一段控制流程;若其中含 I/O 或可变状态,效果也会重复,不能仅用纯函数等式推断行为。
推论与应用
CPS 是编译器消除隐式控制栈、实现尾调用和中间表示转换的经典技术。求值上下文经重化可变成抽象机器中的显式续延栈,而去重化又可还原高阶函数表示。
异常、回溯、生成器、协程和 call/cc 都可用续延建模;代数效应处理器则把到最近 handler 为止的受限恢复点交给操作分支,并另行规定 one-shot 或 multi-shot 使用纪律。
参考资料
- Robert Harper, Practical Foundations for Programming Languages, 2nd ed., Cambridge University Press, 2016,Chs. 27–30, continuations and control。
- Glynn Winskel, The Formal Semantics of Programming Languages, MIT Press, 1993,Chs. 7–10, continuations and semantic transformations。