Skip to content

续延

Continuation

表示计算余下部分、接收当前结果并产生最终结果的对象。

条目类型
定义

形式陈述

续延(continuation)表示某个程序点之后“剩余的计算”。若当前子计算产生类型 A 的值,整个程序最终产生答案类型 R,则续延可抽象为函数 k:AR。在求值上下文语义中,一洞上下文 E 也可视为续延:给定值 v,继续执行 E[v]

续延传递风格把隐含的结果去向变成函数参数;完整的语法导向条款、答案类型翻译、行政归约与模拟关系见续延传递风格变换。本页关注续延这个对象本身。第一类续延允许程序捕获、存储并再次调用当前续延,不要求整段程序预先经过 CPS 翻译。

控制系统还需区分无界续延与只捕获到最近提示符的受限续延,以及只能恢复一次的 one-shot 续延与可重复恢复的 multi-shot 续延;这些选择决定哪些控制片段能被捕获和重放。

直觉

普通执行栈隐式记录“当前函数返回后去哪里、拿结果做什么”,续延把这份信息变成可以命名和传递的对象。计算 1 + (2 * 3) 时,求 2 * 3 的续延就是“把结果加一并作为最终答案”;它只描述未来,不包含已经完成的过去。把控制流函数化后,返回、异常、跳转和协程都能用“选择哪个续延调用”统一解释。类比调用栈很有用,但第一类续延比普通栈更强,因为它可被保存、复制甚至多次恢复。

例子与边界

1 + (2 * 3) 中,子计算 2 * 3 的续延可写成 λv.1+v:它接收 6 后产生最终结果 7。异常可由另一个失败续延表示,正常路径把值交给成功续延,抛出路径则跳到失败续延;这里展示的是两个“结果去向”,不是完整 CPS 变换的全部翻译规则。

边界是把续延误认为“最终结果”。续延接收当前结果后才产生后续行为,本身不是当前值。多次调用捕获的续延可能重复执行一段控制流程;若其中含 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。
关系图谱8 个相邻概念 · 1 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组