续体

在计算机科学中，续体（，也译作计算续体、续延、延續性），是实化计算机程序的控制状态的一种抽象表示。程式在運算過程中給定一個點，其「剩餘將要執行的部分」，即為「續體」。借助程式語言中的續體特性，程式設計師不但能模組化地自訂迴圈、break陳述句、continue陳述句等基本控制結構；此外還能以更加簡練的方式實現更加複雜的控制結構或計算模式，例如：異常處理、 生成器、協程、回溯、非确定性計算、概率编程、反向传播算法、可微分编程等。

概述
對一段程式 1 (2 + 3) - 4 而言，若當前正在計算 2 + 3，這部份則稱為可約表達式（）；而其餘的部分 1 [\cdot] - 4 即是續體。這裡的符號 [\cdot] 被稱為「洞」，表示可約表達式之計算結果將要回填的地方，可視為佔位符。

續體的種類
續體的概念在任何程式語言中都會出現，而不同的程式語言之間的差別在於是否提供構造或是算子，以供顯示地捕捉跟恢復續體。不同種類的算子，亦有相異的抽象程度與表達能力。

头等续体
若能將捕捉到的續體實化作為一般的值儲存與傳遞，便會稱其為头等續體（）。而當被捕捉的續體被呼叫時，程式的流程控制將會恢復到續體被捕捉時所在的地方。這賦予程式语言強大的执行順序控制能力。它可以在呼叫堆疊中跨越多個棧幀來返回結果，或者跳转到此前已经退出了的函数。可以认为其保存了程序的控制流程上下文，而需要注意的是這與不同，它不保存程序数据，只保存控制流程上下文。这经常采用“续体三明治”譬喻来说明：

你正站在冰箱前，想要做一个三明治。

你就把這個情況變成一个续体，放入口袋里。

接着，从冰箱里拿出火鸡肉和面包，並坐到桌案前，做了一个三明治。

你启用了口袋里的续体。

这时发现自己再次站到了冰箱之前，想要一个三明治。

幸运的是，在桌案上就有一个三明治，而用于做三明治的材料都没有了。你可以吃三明治了。

在这个譬喻中，三明治是一部份程序数据，比如在分配堆上一个对象，并非去调用“制做三明治”例程并等它返回，这里调用“以当前续体制做三明治”例程，它创建一个三明治并在已脱离执行的续体所保存的地方继续执行。

多發及單發恢復
能夠恢復多次的多發續體（），其表達能力比僅能恢復一次的單發續體（）還要強。單發續體能夠直接表達迴圈、异常处理、迭代器、生成器、协程等控制結構，而多發續體不僅僅是具備單發續體的能力，此外還能用在非確定性、回溯法、布林可滿足性問題、反向傳播這些單發續體無法直接表達的問題。

然而，多發恢復的續體在編譯器及執行期系統的實現面臨著工程上的挑戰。為了實現多發恢復的語意，通常需要以複製呼叫堆疊實現，這也為多發續延帶來了一些性能負擔。考慮到這個原因，部分程式語言僅提供單發恢復，例如OCaml的Effect；也有程式語言實現提供了單發化版本的控制算子，例如Chez Scheme提供了call/1cc。而如何更高效地實現多發恢復，在近年來（2025）仍然是學者積極探討的問題。

學界也探討了單發有界續體與協程的關係。有堆疊的非對稱式協程，例如Lua所提供的協程，可以對應到單發有界續體。

历史
Gerald J. Sussman和Guy L. Steele Jr.在1976年论文《Lambda：终极指令式》中，提及了在1972年介入变换的论文《高阶编程语言的定义性解释器》中采用了术语“续体”，并认定Alonzo Church在1941年著作《Lambda转换的演算》里，已经清晰的理解了“续体”的使用，这是用纯λ演算彻底完成所有事情即邱奇编码的唯一方式，并举出其中有序对定义所对应的Scheme表示为证，下面示例有序对邱奇编码的Scheme和Python表示代码：

在1993年的论文《续体的发现》中给出了发现续体的完整历史。Reynolds认为续体的最早描述由Adriaan van Wijngaarden在1964年9月作出。van Wijngaarden在奥地利的維也納附近巴登召开的关于“形式语言描述语言”的工作会议上，在关于ALGOL 60预处理器的的论文《语法和语义的递归定义》中，倡导将真正（proper）过程变换成续体传递风格，并附带消除标签和goto语句，但是他没有使用“续体”这个名字。

Steve Russell为他给IBM 704的LISP实现的一个用户，发明了续体来解决问题，但是他没有为其命名。

在指称语义领域的研究中，学者采用“续体”来规定一个控制构造对整个程序执行最终结果的贡献。Christopher Strachey和Christopher P. Wadsworth在1974年技术专著《续体：处理完全跳转的数学语义》中给出了一个“小型续体语言”示例。续体的概念在指称语义中定型于在1977年出版的著作《指称语义：Scott-Strachey编程语言理论途径》。

Scheme语言的1975年最初版本提供了续体算子，即源自Maclisp的用于例外处理的命名catch/throw。和Uwe F. Pleban在1980年论文《LISP与SCHEME的语义比较》中为Scheme语言介入了基于“续体语义”的指称语义规定。当前Scheme语言报告中的形式语义描述，沿袭了指称语义一系著作中所采用的概念和表示法。

Daniel P. Friedman、和基于按照Scheme语言的“续体语义”而编写的编译器，在1984年为Scheme介入了头等续体算子（简写为call/cc），随后还介入了其约束形式。Matthias Felleisen和Daniel P. Friedman在1986年借鉴的扩展了续体的元循环解释器，修订Peter Landin规定用来执行应用表达式的SECD机，从而规定了，在其中定义了捕获当前续体算子\,\mathcal{C}\,和call/cc ≡ λf.\mathcal{C}λk.(f k)。

Bruce Duba等人在1991年将头等续体模块介入到了SML/NJ，CONT签名具有接口：val callcc : ('a cont -> 'a) -> 'a和val throw : 'a cont -> 'a -> 'b。这里的'a cont是接受类型参数'a的续体类型，callcc f应用f到当前续体，如果f以实际参数x调用这个续体，则如同(callcc f)返回x作为结果。throw k a以实际参数a调用续体k；它在本质上将续体强制转变成为了函数，故而在每次续体调用之时重新介入了一个独立的类型参数'b。

续体传递风格
续体的概念主要起源于计算模型研究，比如λ演算、指称语义。这些模型仰仗于编程者或语义工程师书写数学函数时采用“续体传递风格”（continuation-passing style，简写为CPS）。续体传递风格（CPS）意味着编程中用到的每个函数，都接纳并于结束时应用一个表示有关于这个函数调用的余下计算的函数。

下面的示例是高阶函数foldr和map的续体传递风格实现，并据此定义一个整数列表的sum：

所有CPS函数比如这里的g，都接受一个额外的实际参数比如这里的k，它被称为续体。在限定了CPS函数中只应用CPS函数或续体的前提下，CPS函数中的函数调用的所有实际参数，必须要么是一个λ表达式比如这里fn x => k (f (a, x))，它将续体k应用于函数f的应用，要么是一个变量比如这里的l和r，而不能是更复杂的表达式。

当CPS函数已经计算出来其结果值的时候，它通过以结果值作为实际参数调用续体函数来返回它，比如这里的g ([], k) = k b，在计算的任何步骤中只要直接返回结果值就会终止整个计算。一个函数比如这里的foldr'，要调用CPS函数比如这里的g，就必须提供一个函数比如这里的fn x => x，用来接受它所调用的CPS函数的结果值。

对于输入[e1, e2, …, en]，这里的sum函数等价于将函数复合即上述Standard ML代码中的(fn x => x)∘(fn x => e1 + x)∘(fn x => e2 + x)∘…∘(fn x => en + x)，应用于初始值0之上，它得到(e1 + (e2 + (… + (en + 0)…)))。此外，建立在惰性求值和柯里化之上的Haskell提供了函数复合算子。

在求值的时候，表达式的最内部份必须首先求值，将表达式转换为续体传递风格等价者，比如在1972年论文《Lambda演算基模》中所举的例子，实际参数求值的次序变为显见；随之而来，过程返回变成了对续体的调用，而尾调用变成将传递给这个调用者的续体不加修改的传递给被调用过程。

要在REPL或直接风格函数中调用CPS函数，必须提供接受CPS函数计算结果的一个续体，比如恒等函数：

(pythag& 3 4 (lambda (x) x))
(fact& 4 (lambda (x) x))

注意在上述CPS版本的代码中，使用的函数原语（functional primitive），比如这里的*&、+&、-&、=&和sqrt&，自身也是CPS风格而非直接风格，下面以这里的CPS版本函数原语=&定义为例：

(define (=& x y k) (k (= x y)))

采用续体传递风格使函数式编程者能获得以任意方式操纵控制流程的表达能力，代价是手工维护控制续体通常是高度复杂的任务。终极解决方案是用Scheme写一组转换例程，将Scheme的直接风格转换成CPS表达式。

下面的转换函数例子仅将直接风格函数原语转换成CPS函数原语：

在Scheme中，reverse函数反转LISP列表所用的单向链表，其首次应用将原来尾部元素反转到了首部，接着取出这个元素应用并再次应用reverse函数将余下诸元素反转成原来次序。函数的应用(apply f args)，以args列表的诸元素作为实际参数调用f函数。函数eval和apply，是传统元循环求值器的两大中心构件。

下面将前述的据毕达哥拉斯定理求欧几里得范数的Scheme代码转写为Python代码：

def pythag_cps(x, y, k):
return (
mul_(x, x, lambda a:
mul_(y, y, lambda b:
add_(a, b, lambda c:
sqrt_(c, k)))))

pythag_cps(3, 4, lambda x: x)

一般编程在写CPS函数之时，经常不采用函数原语的CPS版本，比如将前面的阶乘函数写为：

Daniel P. Friedman和，在1984年论文《续体与协程》中，为Scheme 84子集语言介入了基于表达式、环境和续体的元循环解释器，在其中以续体传递方式定义了call/cc，并将函数应用时的实际参数列表形式从(arg1 …… argn k)修订为((arg1 …… argn) k)。他们在首次出版于1992年的著作《》中发展出了用Scheme及后续的Racket来编写“续体传递解释器”。

以当前续体调用
基于承当调用栈的解绕与重绕的基础设施，一些编程语言比如Scheme和SML/NJ，提供了实化控制流程的算子call/cc来直接支持头等续体。

栈解绕是从被调用函数返回的动作，它从调用栈弹出一个或多个栈帧并留下其返回的一个值，从而恢复在程序中其它某处的执行，它被用于实现非局部跳转控制结构。在应用头等续体的时候，堆栈在逻辑上被解绕去掉这个续体不需要的栈并重绕上它所需要堆栈，接着盘绕上要传递的那一个值。一个保存了的头等续体可以在往后时重入（re-enter），这意味着它所涉及的整个调用序列的栈帧都应仍然存在。

非形式化描述
在Scheme语言中，每当一个Scheme表达式被求值的时候，就会有一个续体想要这个表达式的结果。续体表示了这个计算的全部抑或缺省的未来。例如，如果这个表达式被求值于顶层，那么续体将接受这个结果，将它打印到屏幕上，提示下一次输入，进行求值，周而复始。多数时候续体包括用户代码所指定的动作，比如在接受这个结果的续体中，向它乘以存储在一个局部变量中的值再加上7，并将答案给予顶层续体来打印它。通常情况下编程者不用过多考虑那些隐藏在幕后的无处不在的续体。

在Scheme语言中，call/cc显式的处理续体，它将当前续体包装（package up）成为一个“逃脱过程”（escape procedure），即具有作为其唯一的运算，并把它作为实际参数传递给Scheme编程者所定义的函数。call/cc所包装的续体是头等对象，逃脱过程有着无限制的（extent），可以被存储在变量或数据结构之中，它可以按需要多次调用。

在Scheme语言中，在call/cc的调用(call/cc f)中的函数f，接受包装了当前续体的逃脱过程作为其唯一实际参数。在后续执行中将逃脱过程应用于一个实际参数之时，此刻生效的续体被舍弃，转而使用创将这个逃脱过程之时生效的那个续体，控制流程将在这个续体被捕获的那一点上继续，而传递给这个逃脱过程的实际参数则变成这个call/cc调用的返回值。本章节的Scheme代码解说中出现的词语“当前续体”或“续体”，一般就是指在Scheme语言报告中描述的这个可操纵的包装它的“逃脱过程”。

归约语义
callcc的形式语义，除了采用指称语义中进行CPS变换的方式来给出，也可以采用操作语义中小步语义的方式来定义，即使用在上下文\,C\,之下的规则：
:
\begin{align}
C[\operatorname{callcc} (\lambda k.\, e)] &\;\to\; C[(\lambda k.\, e)(\lambda x.\, C[x])] \\
C[\operatorname{throw} (\lambda x.\, k)\, v] &\;\to\; (\lambda x.\, k)\, v
\end{align}

这里的callcc捕获的当前续体是\,\lambda x.\, C[x]\,，其中\,x\,是不被\,C\,所绑定的变量。

下面的用例2*callcc(λk.(1+(throw k 0)))，通过SML/NJ的来演示：

open SMLofNJ.Cont;
2 * callcc (fn k => 1 + (throw k 0));

使用具有上下文C = 2[ ]的callcc规则，此刻在C[ ]之内应用λk.e = λk.(1+(throw k 0))于λx.C[x] = λx.(2x)，对整个程序也就是这个表达式进行归约：

⇒ 2 (fn k => 1 + (throw k 0)) (fn x => 2 x) 
⇒ 2 (1 + (throw (fn x => 2 x) 0))

接着使用具有上下文C = 2(1+[ ])的throw规则，此刻舍弃C[ ]而应用λx.k = λx.(2x)于v = 0，继续进行归约：

⇒ (fn x => 2 x) 0 ⇒ 2 0 ⇒ 0

示例
下面用明确要求其实现进行尾调用优化（TCO）的Scheme来演示call/cc的典型应用。

立即返回
下面的例子中，使用call/cc来模拟C风格语言中的return语句：

(define (f return)
(return 2)
3)

(f (lambda (x) x))
===> 3

(call/cc f)
===> 2

第一个演示，以恒等函数(lambda (x) x)作为实际参数调用函数f，函数f将绑定到形式参数return上的恒等函数应用于2，接着执行最后一个表达式3，从而函数f返回3。第二个演示，将call/cc应用于函数f，函数f将绑定到形式参数return上的续体应用于2，这在控制流程上等价于非局部跳转回到调用(call/cc f)的那一点上，将其为返回值2。

生成器
下面是生成器的实现代码：

(define (generator lst)
(define iterator
(lambda (yield)
(for-each (lambda (item)
(set! yield
(call/cc (lambda (resume)
(set! iterator resume)
(yield item)))))
lst)
(yield 'stop-iteration)))
(lambda () (call/cc iterator)))

在这里于生成器之中定义它所生成的迭代器函数iterator，和随后定义函数generate-digit的时候，采用了函数定义的不加语法糖的原始形式。call/cc在这里被用到了两处：一处是(call/cc iterator)，它以当前取用遍历返回值续体调用迭代器；另一处是(call/cc (lambda (resume) ……))，它在迭代器遍历目标列表之时捕获当前位置，用于下次重入迭代器之时于此处恢复执行。下面是上述代码的简单用例：

(define generate-digit
(generator '(0 1 2)))

(define (display-two-digits)
(display (generate-digit)) (newline)
(display (generate-digit)) (newline))

(display-two-digits) ;; 分两行打印 0 和 1
(display-two-digits) ;; 分两行打印 2 和 stop-iteration

这里定义的函数generate-digit，是将函数generator应用于聚集（aggregate）即这里的列表'(0 1 2)之上，而得到的闭包(lambda () (call/cc iterator))。每次执行(generate-digit)之时，都转为执行(call/cc iterator)，它捕获取用迭代器遍历聚集逐个返回的值的续体，比如用例中有2个display作为外部应用续体。

在第一次执行(generate-digit)之时，iterator所绑定的是静态定义的函数，执行(call/cc iterator)，将外部应用续体绑定到函数iterator的形式参数yield之上；然后开始遍历列表的元素进行迭代的(for-each (lambda (item) ……) lst)，在求值(set! yield ……)的第二个实际参数之时，进行每一次迭代步骤(call/cc (lambda (resume) ……))，其中的(set! iterator resume)，将绑定到变量resume上的当前续体，重新绑定到函数名字iterator之上用于以后恢复执行，最后执行暂停表达式(yield item)返回当前列表项目。

在下一次执行(generate-digit)之时，iterator所绑定的已经是表示迭代器内部恢复位置的续体，执行(call/cc iterator)，以当前外部续体作为参数调用这个内部位置续体iterator；控制流程将在上次迭代的(set! yield (call/cc ……))之处恢复，此刻(set! yield ……)中的第二个实际参数(call/cc ……)求值完毕，这个设置表达式的将变量yield的绑定内容更新为此刻传入的外部应用续体，此后继续这一次的迭代步骤。在遍历了列表的元素之后迭代结束，最终执行(yield 'stop-iteration)，返回一个约定的常量。

协程
call/cc还可以表达其他复杂的原始运算比如协程。下面的代码使用续体达成协程即协作式多任务的用户级线程：

(define ready-list '())

(define (yield)
(call/cc (lambda (reenter)
(let ((cont (car ready-list)))
(set! ready-list (append (cdr ready-list) (list reenter)))
(cont #f)))))

(define (fork fn . args)
(call/cc (lambda (abort)
(set! ready-list (cons abort ready-list))
(yield)
(apply fn args)
(let ((cont (car ready-list)))
(set! ready-list (cdr ready-list))
(cont #f)))))

(define (schedule)
(let loop ()
(if (not (null? ready-list)) (begin
(yield)
(loop)))))

这里的全局变量ready-list是就绪线程列表，它存储处于脱离（detached）状态的就绪线程的重入续体；在选择重入线程的时候，将就绪线程列表头部的续体从列表中取出，并应用它以重入对应线程。退让过程yield，捕获对应于调用者的当前续体，将其追加到就绪线程列表的尾部，取出并应用就绪线程列表头部的续体而使本线程脱离运行（operating）。

分叉过程fork，接受一个函数fn和相应的参数列表args，它首先捕获自身的当前续体并将其添加到就绪线程列表的头部；然后调用退让过程yield，从而创建了一个用来创建工人（worker）线程的线程，接着取出并应用就绪线程列表头部的续体而使本线程脱离运行；由于分叉过程自身的续体已经添加到了就绪线程列表头部，重入它而随即结束分叉过程的这次调用。当重入这个创建工人线程的线程之时，调用函数fn，预期这个函数在自身之中调用退让过程yield，从而创建重入函数fn内部的工人线程。当工人线程最终并未调用退让过程而从函数fn直接退出回到分叉过程之时，必须接着以取出并应用就绪线程列表头部的续体的方式来结束这个工人线程，因为对分叉过程的调用早已结束。

调度过程schedule，持续检测就绪线程列表，只要有任何其他线程等待就调用退让过程yield，取出并应用就绪线程列表头部的续体而使本线程脱离运行，最终在无就绪者等待之时结束。调度过程在每一轮并发运行循环中只运行一次。调度过程在所有分叉过程之后调用，它起到的根本作用是充当会合点，即并发运行的多个线程中的最终剩下的唯一线程。下面是上述代码的简单用例：

(import (srfi 28))

(define (echo-string-n-times str n)
(let loop ((i 0))
(if (
其输出为：

This is AAA 0
Hello from BBB 0
This is AAA 1
Hello from BBB 1
This is AAA 2

在这个用例的两个分叉过程中，前面的分叉过程先执行并且后结束，如果不介入调度过程转而完全由工人线程自行调度，会合于此处将导致非预期的情况出现，即除非就此退出这个进程，在其后的分叉过程会再次执行。

最后演示对上述协程代码的一种变化：将退让过程yield改成具有返回值，调用了退让过程的分叉过程fork也相应更改；将调度过程schedule改为采用策略，它与前面代码的区别在于将调度过程自身的续体添加到就绪线程列表的头部；并为调度过程增加了一个函数参数fn，用这个函数来处理工人线程的返回值。这种调度过程也可以改名为分派过程dispatch：

(define ready-list '())

(define (yield x)
(call/cc (lambda (reenter)
(let ((cont (car ready-list)))
(set! ready-list (append (cdr ready-list) (list reenter)))
(cont x)))))

(define (fork fn . args)
(call/cc (lambda (abort)
(set! ready-list (cons abort ready-list))
(yield #f)
(apply fn args)
(let ((cont (car ready-list)))
(set! ready-list (cdr ready-list))
(cont #f)))))

(define (schedule fn)
(let loop ()
(if (not (null? ready-list)) (begin
(fn (call/cc (lambda (return)
(let ((cont (car ready-list)))
(set! ready-list (cons return (cdr ready-list)))
(cont #f)))))
(loop)))))

这种协程也称为“半协程”或“生成器”，它与前面例子中同名的生成器机制各有用途。下面是其用例：

(import (srfi 28))

(define (echo-string-n-times str n)
(let loop ((i 0))
(if (

编程语言的直接支持
除了Scheme、Racket和SML/NJ之外，一些编程语言直接支持头等续体比如：

*Common Lisp：cl-cont，还可以使用定制宏

*Factor：callcc0和callcc1
*Haskell：在Control.Monad.Cont中的续体单子
*Icon / Unicon：coexpression的create与@算子
*Kotlin：Continuation
*R：callCC
*Ruby：callcc
*Smalltalk：Continuation类的currentDo:，在多数现代Smalltalk环境中续体不需要额外的VM支持就能实现

参见
*
*Chicken：基于续体传递风格底层机制而实现的Scheme，它具有叫做F-operator的包含算子的扩展库。

引用与注释
延伸阅读
*
*
*
*
*
*
*
*
*
*
*
*

外部链接
*
*
*[https://docs.scheme.org/tyscheme/index-Z-H-15.html#TAG:__tex2page_chap_13 Teach Yourself Scheme in Fixnum Days] by Dorai Sitaram features a nice chapter on continuations.
*