续延传递风格

玻尔百科

核心要点

续延传递风格（CPS）通过传递一个代表“计算其余部分”的“续延”函数作为参数，从而使控制流显式化。
通过将递归调用转换为尾调用，CPS 允许进行尾调用优化，使深度递归能够在常量栈空间内执行。
CPS 是现代异步编程特性（如 async/await）的基础机制，也是编译器设计中处理复杂控制流的关键技术。
CPS 的结构揭示了计算与经典逻辑之间的深刻联系，将控制操作符与双重否定消除等基本逻辑原理联系起来。

引言

在编程世界中，程序如何决定下一步做什么——即其控制流——通常由调用栈等隐藏机制来管理。虽然这种隐式机制行之有效，但它有其固有的局限性，例如递归的栈空间有限，以及其僵化的结构使异常或异步事件等复杂操作变得模糊不清。本文旨在弥补这一差距，揭开控制流的神秘面纱。本文将深入探讨续延传递风格（CPS），这是一种变革性的编程技术，它将“计算的其余部分”变成了一个我们可以明确操控的实体。在接下来的章节中，我们将首先探索 CPS 的核心“原理与机制”，揭示它如何将程序从调用栈中解放出来。随后，“应用与跨学科联系”一章将展示这个单一而强大的思想如何统一了看似无关的概念，从编译器优化和现代异步编程，一直到数理逻辑的根基。

原理与机制

看不见的机器：调用栈

想象一下，你让一个勤奋但头脑简单的助手计算 3 的阶乘，即 $3!$ 。你告诉他规则：数字 $n$ 的阶乘是 $n$ 乘以 $n-1$ 的阶乘，而 0 的阶乘是 1。

他是怎么做的呢？在知道 $2!$ 是多少之前，他无法计算 $3 \times (2!)$ 。所以，他在一个记事本上写下：“一旦我算出 $2!$ ，我需要将结果乘以 3。”他把这张便条放在一堆便条上。

然后，为了计算 $2!$ ，他需要 $1!$ 。他又写了一张新便条：“一旦我算出 $1!$ ，我需要将结果乘以 2。”他把这张便条放在第一张便条的上面。

这个过程一直持续到他需要计算 $0!$ 。啊哈！这个就是 1。不需要再写新便条了。现在他可以开始从这堆便条的顶部往回处理了。他拿起最上面的便条：“将结果乘以 1。”上一个结果是 1，所以 $1 \times 1 = 1$ 。现在他得到了 $1!$ 的值。

他拿起下一张便条：“将结果乘以 2。”上一个结果是 1，所以 $2 \times 1 = 2$ 。这就是 $2!$ 。

最后，他拿到底部的便条：“将结果乘以 3。”上一个结果是 2，所以 $3 \times 2 = 6$ 。答案就这样得出了。

这堆便条正是计算机通常运行递归函数的方式。它被称为调用栈。每张便条是一个激活记录或栈帧。它是一个后进先出（LIFO）的结构，存储了“待完成的工作”——即计算机在子问题解决后为完成计算所作出的承诺。对于一个简单的 $n$ 的阶乘，栈会增长 $n$ 层深，形成一条等待基本情况解决的待处理乘法链。

这个栈是一个隐式的机制。它工作得很好，但对程序员来说是隐藏的。它的行为由语言运行时固定。但如果不是这样呢？如果我们能拿起其中一张便条——其中一个承诺——并将其视为一个真实的对象呢？

让承诺显式化：续延

这就是续延传递风格（CPS）的核心思想。我们不再依赖隐式的栈来记住下一步该做什么，而是将“计算的其余部分”作为一个我们传递的显式值。这个值被称为续延。

让我们重新构想我们的阶乘函数。在直接风格中，它看起来是这样的：

乘以 $n$ 的操作发生在递归调用 factorial(n-1) 返回之后。这就是存储在调用栈上的待完成工作。

在 CPS 中，一个函数从不以传统意义上的“返回”。取而代之的是，它接受一个额外的参数：续延，我们称之为 $k$ 。当函数产生结果时，它通过调用 $k$ 并将该结果作为参数来“返回”。

我们的 CPS 阶乘函数 factorial_cps 将接受两个参数： $n$ 和一个续延 $k$ 。

现在是有趣的部分。为了计算 factorial_cps(n, k)，我们需要 factorial(n-1) 的结果。但在我们得到那个结果（比如说 $r$ ）之后，我们需要计算 $n \times r$ ，然后将这个结果传递给我们最初的续延 $k$ 。

所以，对于递归调用的“计算的其余部分”是“接受一个结果 $r$ ，将它乘以 $n$ ，然后调用 $k$ 。”我们可以将这个逻辑打包成一个新的续延！

让我们定义一个新的续延 k_new，作为一个小函数：lambda r: k(n * r)。现在我们可以写出完整的递归步骤：

仔细看最后一行：factorial_cps(n - 1, k_new)。这个递归调用是该函数所做的最后一件事。没有待完成的工作了。所有曾经待完成的工作——乘以 $n$ ——都已经被打包并作为新续延的一部分传递下去了。

我们甚至可以通过使用最简单的续延——恒等函数 $id(x) = x$ （它只是返回任何给定的值）来启动一个 CPS 函数，从而将其转换回其直接风格的等价形式。这有效地闭合了承诺链，并给了我们最终的答案。

伟大的解放：常量栈空间

这种结构，即一个函数的最后一个动作是调用另一个函数（或其自身），被称为尾调用。这为什么特别？一个聪明的编译器或运行时可以执行尾调用优化（TCO）。当它看到一个尾调用时，它会意识到当前函数的栈帧不再需要了。它可以直接重用那个相同的栈帧来进行新的调用，而不是在栈上推入一个新的。

在我们的直接风格阶乘函数中，对 factorial(n-1) 的调用不是一个尾调用，因为待处理的乘法必须存储在栈上。但在 factorial_cps 中，递归调用是一个尾调用。

这带来了一个惊人的结果：当我们运行 factorial_cps(n, id) 时，调用栈不会增长！无论 $n$ 有多大，计算都以一个常量级的、微小的栈空间进行。曾经存储在栈上的待处理操作链现在存储在从一次调用传递到下一次调用的嵌套续延对象中。我们实际上是用堆空间（续延对象所存在的地方）换取了栈空间。

从魔法到机制：作为数据的续延

这可能仍然有点像魔法。我们用这些神秘的“续延函数”替换了栈。但它们到底是什么？让我们通过证明它们只不过是数据结构来揭开它们的神秘面纱。

考虑更复杂的斐波那契数列： $\mathrm{fib}(n) = \mathrm{fib}(n-1) + \mathrm{fib}(n-2)$ 。一个直接的递归实现会进行两次调用，导致栈帧呈树状爆炸式增长。

如果我们将它转换为 CPS，续延会变得更加复杂。为了计算 $\mathrm{fib}(n)$ ，我们首先计算 $\mathrm{fib}(n-1)$ 。这一步的续延必须记住接下来要计算 $\mathrm{fib}(n-2)$ ，并且在那一步完成后，将两个结果相加。

这揭示了我们需要不同种类的续延。我们可以将这些不同的行为表示为简单的、带有类型标签的数据对象，而不是函数：

EndFrame：最终的续延，标志着整个计算的结束。
EvalFibFrame(m)：一个在当前任务完成后计算 fib(m) 的承诺。
AddFrame(v)：一个将值 v 加到下一个出现的结果上的承诺。

现在，我们可以编写一个简单的循环来代替递归，该循环操作一个由当前值和这些续延数据对象组成的栈构成的状态。这个过程被称为去函数化（defunctionalization）。它证明了一个深刻的观点：通过使控制流显式化（CPS），我们可以将任何递归算法转换为一个迭代算法，该算法使用一个用户管理的、显式的数据栈，而不是运行时的隐藏调用栈。魔法消失了，取而代之的是一个清晰的机制。

一个没有栈的世界

让我们将这个想法推向其逻辑终点。如果续延处理了函数调用的“返回”部分，并且我们可以显式地管理它们，那么硬件调用栈还有什么用处呢？

想象一个完全围绕 CPS 设计的运行时系统。堆上的一个续延对象将包含两个关键信息：一个指向接下来要运行的代码的指针（来自的 k_pc），以及该代码需要的任何数据（其捕获的环境）。

在这个世界里：

函数“调用”只是一个到目标函数地址的 JMP 指令。
函数“返回”是一个间接的 JMP，跳转到它所获得的续延对象中存储的代码地址。

CPU 的 CALL 和 RET 指令变得多余。用于管理栈帧的栈指针（ $SP$ ）和帧指针（ $FP$ ）将无事可做。它们可以在程序的整个生命周期内保持其初始值！。

调用栈，这个在我们编程心智模型中如此基础的概念，被揭示为只是管理控制流的一种可能的实现策略。CPS 提供了另一种策略，用堆上管理的更灵活、更显式的续延对象图谱取代了栈的僵化、后进先出的结构。

自由的代价：内存与生命周期

这种新获得的自由并非没有代价和复杂性。在基于栈的模型中，函数局部变量的生命周期很简单：当函数返回并且其栈帧被弹出时，它就结束了。

但是，如果一个续延的生命周期超过了创建它的函数呢？想象一个函数 $f$ 创建了一个续延 $k$ ，它捕获了 $f$ 的一个局部变量 $x$ 。然后， $f$ 没有立即使用 $k$ ，而是将它存储在一个全局数据结构中，然后完成了自己的工作。函数 $f$ 已经结束了，在正常情况下，它的栈帧和变量 $x$ 将被释放。但是续延 $k$ 仍然存活在那个全局结构中，持有着对 $x$ 的引用。如果我们稍后调用 $k$ ，它会尝试访问不再有效的内存——这是一个经典的悬空指针错误。

为了防止这种情况，编译器必须非常聪明。它必须执行逃逸分析，以确定一个续延是否可能“逃逸”其创建者的作用域。如果会，那么它捕获的环境（包括变量 $x$ ）就不能分配在短暂的栈上。它必须分配在堆上，在那里它可以存活只要它还是可达的。这就是所谓的“向上 funarg”问题，它意味着 CPS 的灵活性需要一个更复杂的内存管理策略，通常涉及垃圾回收器。

在堆上高频率地分配小型、短生命周期的续延对象可能看起来效率低下，但这正是现代分代垃圾回收器异常擅长处理的模式。它们的设计基于“分代假设”——即大多数对象都很早死亡——这恰好是大多数续延的情况。编程风格与运行时系统之间的相互作用是一场深刻而美妙的协同进化之舞。

最终的启示：作为逻辑的续延

我们从一个简单的递归函数一路探索到机器层面，再到内存管理的复杂性。但最深刻的联系却在一个完全不同的方向：数理逻辑的基础。

Curry-Howard 同构揭示了逻辑与计算之间的深刻对偶性：命题可以被看作是类型，而证明可以被看作是程序。例如，命题“ $A \implies B$ ”的一个证明是一个将类型 $A$ 的值转换为类型 $B$ 的值的函数。这种对应关系对于*直觉主义逻辑*（构造性证明的逻辑）来说非常完美。

然而，经典逻辑包含*排中律（ $A \lor \neg A$ ）和双重否定消除*（ $\neg\neg A \to A$ ）等原则，而直觉主义逻辑不接受这些原则。没有简单、直接的程序能够对应这些公理的证明。几十年来，这似乎是一个根本性的障碍。

令人瞩目的是，解开这个联系的钥匙正是续延传递风格。

考虑一个期望类型为 $A$ 的值的续延的类型：它是一个类型为 $A \to R$ 的函数，其中 $R$ 是某个最终的“答案”类型。一个通过调用这样的续延来产生 $A$ 的计算，其类型为 $(A \to R) \to R$ 。

现在看一下双重否定的命题 $\neg\neg A$ 。将否定 $\neg A$ 定义为 $A \to \bot$ （一个从 $A$ 到“假”的函数），双重否定就变成了 $(A \to \bot) \to \bot$ 。

结构完全相同！ $(A \to R) \to R$ 和 $((A \to \bot) \to \bot)$ 。

这并非巧合。CPS 变换提供了经典逻辑的计算意义。通过将程序转换为 CPS，我们将其带入一个计算世界，在这个世界里，每个类型都是“稳定的”——它等价于其双重否定。在这个世界里，像 call/cc（call with current continuation，带当前续延的调用）这样的控制操作符，允许程序捕获当前续延并在以后的任何时间恢复它，正是双重否定消除的程序化体现。

能够将整个“计算的其余部分”保存在一个瓶子里，并在以后打开它的能力，正是实现经典推理所需要的力量。一个看似实用的编译器优化，结果却成了一座通往不同逻辑宇宙的桥梁，揭示了计算基础中惊人而出乎意料的统一性。

应用与跨学科联系

既然我们已经掌握了续延传递风格（CPS）的原理，你可能会感到一种智识上的好奇，但也会有一个实际问题：这一切到底有什么用？它是一种优雅，甚至可以说是优美的程序组织方式，但它在现实世界中能为我们做什么呢？

答案是肯定的。事实上，你几乎肯定使用过基于这个理念构建的系统，甚至可能没有意识到。CPS 不仅仅是一个理论上的奇珍；它是一个镜头，通过它我们可以理解、统一和实现广泛的计算现象。它是精密编译器中的秘密成分，是现代异步编程背后的引擎，甚至是一座通往数理逻辑根基的桥梁。让我们踏上一段旅程，看看这一个思想如何为看似无关的领域带来美妙的统一。

编译器的艺术：驾驭控制流

把编译器想象成一位钟表大师，其任务是将程序的高级设计转化为机器指令的复杂而精确的齿轮系统。为了做好这份工作，编译器需要对每一个齿轮和弹簧都有绝对的控制。续延传递风格是它实现这种控制最强大的工具。

考虑一个简单的布尔表达式，如 A B。在大多数语言中，如果发现 A 为假，程序就会足够聪明，根本不去评估 B——这是一种称为“短路求值”的技巧。编译器如何实现这一点？使用 CPS，答案变得异常明确。表达式不被翻译成一个返回值的函数，而是被翻译成一个过程，该过程在给定选择的情况下，将跳转到两个位置之一：一个“成功续延”（如果结果为真该怎么做）或一个“失败续延”（如果结果为假该怎么做）。

为了评估 A B，编译器生成的代码首先评估 A。如果 A 为假，它会立即跳转到整个表达式的失败续延。如果 A 为真，它则继续评估 B，使用原始的成功和失败续延。是否评估 B 的决定不再是隐式的；它是一个显式的控制转移，通过在正确的时间传递正确的续延而得到完美的编排。

这种多续延的思想可以扩展到处理远为复杂的控制流。什么是异常？try/catch 块又是什么？它只是另一种非本地跳转。使用 CPS，编译器可以通过给每个函数两个续延来对此建模：一个用于一切顺利时的正常续延 k_v，和一个用于出错时的异常续延 k_e。throw 语句只是一条忽略正常续延并调用当前异常续延的指令。try 块则是一条指令，用于在一段代码的执行期间临时安装一个新的异常续延——即 catch 块。突然之间，异常不再是一个神秘、独立的系统；它们只是续延的另一种形式，统一在同一个概念框架之下。

驯服递归：递归算法的迭代核心

CPS 带给我们的最深刻的洞见之一是关于递归本身的性质。我们通常认为递归和迭代（使用循环）是两种截然不同的编程方式。但 CPS 揭示了这种区别是一种错觉。在其核心，每个递归算法都有一颗迭代的心，而 CPS 就是让我们揭示它的手术刀。

当一个函数调用自己时，计算机硬件使用“调用栈”来记住它在做什么。当递归调用结束时，它会查看栈顶以知道从哪里恢复。CPS 所做的就是使这个调用栈显式化。我们不再依赖硬件，而是传递一个函数——续延——它代表了“其余的工作”。

对此的一个优美演示是二叉树的中序遍历。一个标准的递归实现很优雅，但不是“尾递归”的——在递归调用返回后仍有工作要做。通过将其转换为 CPS，我们发现每个递归调用都成为函数做的最后一件事。那些“待完成的工作”（打印当前节点的值，遍历右子树）都被打包到传递下去的续延中。这个嵌套续延链实际上就是一个代表调用栈的数据结构。

这就是神奇之处：一旦我们将这个续延链视为一个数据结构，我们就可以停止将其表示为一组嵌套函数，而是使用一个简单的一阶数据结构，比如一个列表或一个栈！这最后的转换，称为“去函数化”（defunctionalization），给了我们一个纯粹的迭代算法，它使用一个显式的栈来管理其工作。我们分三步，将一个递归算法变成了一个迭代算法，并在此过程中揭示了隐式的硬件栈和迭代算法的显式栈是同一枚硬币的两面 [@problem-id:3278487]。

这项技术不仅限于简单的线性递归。它可以应用于复杂的搜索算法，如 N 皇后问题的回溯求解器。在那里，续延不仅代表“下一步做什么”，还代表“如果这条路失败了，接下来尝试哪条替代路径”，完美地捕捉了搜索的精髓。

引擎室：现代运行时如何工作

将递归转化为迭代的能力并不仅仅是一个理论游戏。它是许多现代编程语言运行时如何在不崩溃的情况下执行代码的基础。硬件调用栈是一种有限的、通常很小的资源。非常深的递归会导致“栈溢出”。

通过使用 CPS，语言实现可以完全避免使用硬件栈。CPS 中的函数不是进行真正的递归调用，而是返回一个“thunk”——一个代表下一个要调用的函数及其参数的小数据包。然后，运行时是一个称为 trampoline 的简单循环，它只做一件事：一个接一个地执行这些 thunk。while (there_is_a_thunk) { execute_the_thunk(); } 这个循环可以永远运行而不会加深硬件栈，因为每个 thunk 的执行在下一个开始之前就已经完成并返回到循环中。

我们所做的是用堆空间换取了栈空间。Thunk 和续延对象被分配在远大于栈的堆上。这让我们有自由进行任意深度的“逻辑”递归。更深刻的是，通过将续延具体化为数据结构（例如，一个代码标签和一个捕获变量的环境），我们实际上在软件中构建了一个虚拟机，它模仿了硬件自身的调用和返回机制。我们从机器手中夺回了控制权。

并发与异步世界

这种暂停、打包和恢复计算的能力正是现代异步和并行编程所需要的。

如果你曾经在 JavaScript、Python 或 C# 中写过 await，你就已经使用了续延。当一个 async 函数 await 一个长时间运行的操作（如网络请求）时，语言运行时并不仅仅是阻塞。它将函数的其余部分打包成一个续延，保存起来，然后将控制权交还给其事件循环。当网络请求最终完成时，运行时会拿起那个保存的续改并从它离开的地方恢复函数。在 JavaScript Promise 上的一系列 .then() 调用无非就是一条续延链，每个续延都在等待前一个产生一个值。

这个思想可以出色地扩展到高性能并行计算。想象一个像归并排序那样的“分治”算法。我们可以使用 CPS 将递归算法分解成大量的微小任务，或称续延。这些任务——比如“合并这两个已排序的子数组”——可以被放入一个共享的工作队列中。一个工作线程池可以从这个队列中拉取任务并并行执行它们。这就是现代“工作窃取”调度器的本质，它们在多核处理器上实现了惊人的性能。CPS 为将一个顺序算法分解成适合并行执行的形式提供了形式化的基础。

通往逻辑的桥梁：最深刻的联系

也许续延传递风格最惊人的应用不在于工程学，而在于数学的基础。Curry-Howard 同构揭示了计算机程序和数学证明之间深刻而优美的联系：每个命题都可以被看作一个类型，而该命题的每个证明都可以被看作是该类型的一个程序。

在逻辑学内部，存在着一个历史性的分界，一边是“经典”逻辑，它拥护排中律（ $A$ 或非 $A$ ）和反证法等原则；另一边是“直觉主义”逻辑，它要求所有证明都必须是构造性的。对于一个直觉主义者来说，一个“存在一个具有性质 $P$ 的 $x$ ”的证明只有在它确实向你展示了如何找到这样一个 $x$ 时才有效。

在很长一段时间里，经典逻辑被认为更强大，但在计算上意义不大。然后，在一个里程碑式的发现中，计算机科学家发现 CPS 变换提供了缺失的环节。事实证明，程序的 CPS 变换精确地对应于一个著名的逻辑嵌入，称为“双重否定变换”。这种变换允许人们将任何来自经典逻辑的证明机械地转换为一个有效的（尽管更复杂）直觉主义逻辑证明。

这意味着 CPS 甚至为非构造性的经典证明赋予了计算内容！此外，添加一个像 call/cc 这样的控制操作符——它赋予程序捕获当前续延并在以后使用它的神一般的能力——不仅仅是一个编程技巧。在 Curry-Howard 同构下，它等同于在你的基础逻辑中添加一个经典公理，即 Peirce 定律 ( $((A \to B) \to A) \to A$ )，从而将一个直觉主义系统转变为一个经典系统。这种控制操作符的原始力量与逻辑核心原理之间的联系是整个计算机科学中最深刻的成果之一。

计算的统一视图

从短路布尔表达式的平淡细节到数学证明的深奥结构，续延传递风格作为一个强大、统一的概念脱颖而出。它是控制流的“通用语言”，让我们看到递归与迭代、正常返回与异常、顺序代码与异步回调都只是同一个基本思想的不同侧面：决定下一步做什么。通过使这个决定显式化，CPS 为我们提供了理解、转换和控制计算结构本身的终极工具。