续体

在计算机科学中，续体（continuation，也译作计算续体、续延、延续性），是实化计算机程序的控制状态的一种抽象表示。程式在运算过程中给定一个点，其“剩余将要执行的部分”，即为“续体”。借助程式语言中的续体特性，程序员不但能模组化地自订循环、break陈述句、continue陈述句等基本控制结构；此外还能以更加简练的方式实现更加复杂的控制结构或计算模式，例如：异常处理、生成器、协程、回溯、非确定性计算、概率编程、反向传播算法、可微分编程等。

## 概述

对一段程式 `1 * (2 + 3) - 4` 而言，若当前正在计算 `2 + 3`，这部分则称为可约表达式（redex; reducible expression）；而其余的部分 `1 * <math>[\cdot]</math> - 4` 即是续体。这里的符号 `<math>[\cdot]</math>` 被称为“洞”，表示可约表达式之计算结果将要回填的地方，可视为占位符。

## 续体的种类

续体的概念在任何程式语言中都会出现，而不同的程式语言之间的差别在于是否提供构造或是算子，以供显示地捕捉跟恢复续体。不同种类的算子，亦有相异的抽象程度与表达能力。

### 头等续体

若能将捕捉到的续体实化作为一般的值储存与传递，便会称其为头等续体（first-class continuations）。而当被捕捉的续体被呼叫时，程式的流程控制将会恢复到续体被捕捉时所在的地方。这赋予程式语言强大的执行顺序控制能力。它可以在呼叫堆叠中跨越多个栈帧来返回结果，或者跳转到此前已经退出了的函数。可以认为其保存了程序的控制流程上下文，而需要注意的是这与系统映像不同，它不保存程序数据，只保存控制流程上下文。这经常采用“续体三明治”譬喻来说明：

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

你就把这个情况变成一个续体，放入口袋里。

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

你启用了口袋里的续体。

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

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

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

### 多发及单发恢复

能够恢复多次的多发续体（multi-shot continuations），其表达能力比仅能恢复一次的单发续体（one-shot continuations）还要强。单发续体能够直接表达循环、异常处理、迭代器、生成器、协程等控制结构，而多发续体不仅仅是具备单发续体的能力，此外还能用在非确定性、回溯法、布林可满足性问题、反向传播这些单发续体无法直接表达的问题。

然而，多发恢复的续体在编译器及执行期系统的实现面临着工程上的挑战。为了实现多发恢复的语意，通常需要以复制呼叫堆叠实现，这也为多发续延带来了一些性能负担。考虑到这个原因，部分程式语言仅提供单发恢复，例如OCaml的Effect；也有程式语言实现提供了单发化版本的控制算子，例如Chez Scheme提供了`call/1cc`。而如何更高效地实现多发恢复，在近年来（2025）仍然是学者积极探讨的问题。

学界也探讨了单发有界续体与协程的关系。有堆叠的非对称式协程，例如Lua所提供的协程，可以对应到单发有界续体。

## 历史

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

```
“ Reynolds uses the term "continuation" in [Reynolds 72]. Church clearly understood the use of continuations; it is the only way to get anything accomplished at all in pure lambda calculus! For example, examine his definition of ordered pairs and triads on page 30 of [Church 41]. In SCHEME notation. this is:<br />
```

下面示例有序对邱奇编码的Scheme和Python表示代码：

Scheme｜Python

```scheme
(define (cons m n)
  (lambda (a) (a m n)))
(define (car a)
  (a (lambda (b c) b)))
(define (cdr a)
  (a (lambda (b c) c)))
```

```python
def cons(m, n):
    return lambda a: a(m, n)
def car(a):
    return a(lambda b, c: b)
def cdr(a):
    return a(lambda b, c: c)
```

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

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

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

$\mathcal{C}$

$\mathcal{P}$

$\mathcal{C}$

$\mathcal{P}$。续体的概念在指称语义中定型于Joe Stoy在1977年出版的著作《指称语义：Scott-Strachey编程语言理论途径》。

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

Daniel P. Friedman、Mitchell Wand和William Clinger基于按照Scheme语言的“续体语义”而编写的编译器，在1984年为Scheme介入了头等续体算子以当前续体调用（简写为`call/cc`），随后还介入了其约束形式。Matthias Felleisen和Daniel P. Friedman在1986年借鉴John C. Reynolds的扩展了续体的元循环解释器，修订Peter Landin规定用来执行应用表达式的SECD机，从而规定了CEK机

$\mathcal{C}$

$\mathcal{A}$

$\mathcal{A}$

$\mathcal{C}$

$\mathcal{C}$

$\mathcal{C}$

$\mathcal{C}$

$\mathcal{A}$

$\mathcal{A}$

在其中定义了捕获当前续体算子$\,\mathcal{C}\,$和`call/cc ≡ λf.<math>\mathcal{C}</math>λk.(f k)`。

Bruce Duba等人在1991年将头等续体模块介入到了SML/NJ，`CONT`签名具有接口：

```sml
val callcc : ('a cont -> 'a) -> 'a
```

和

```sml
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：

Standard ML｜Python

```sml
fun foldr' f b l = let
    fun g ([], k) = k b
      | g (a :: r, k) = g (r, fn x => k (f (a, x)))
    in
        g (l, fn x => x)
    end

fun map' f l =
    foldr' (fn (x, y) => (f x) :: y) [] l 

fun sum l =
    foldr' (fn (x, y) => (x + y)) 0 l
```

```python
def foldr(f, b, l):
    def g(l, k): 
        match l:
            case []: return k(b)
            case [a, *r]: return g(r, lambda x: k(f(a, x)))
    return g(l, lambda x: x)

def map_(f, l):
    return foldr((lambda x, y: [f(x), *y]), [], l) 

def sum(l):
    return foldr((lambda x, y: x + y), 0, l)
```

所有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函数的结果值。

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

在表达式 (计算机科学)求值的时候，表达式的最内部分必须首先求值，将表达式转换为续体传递风格等价者，比如Michael J. Fischer在1972年论文《Lambda演算基模》中所举的例子：将$\;(f\ (g\ (h\ a)))\;$变换成$\;(\hat{h}\ (\lambda x\ .\ (\hat{g}\ (\lambda y\ .\ (f\ y))\ x))\ a)\;$，具有将表达式“从内至外”翻转的效果，从而使求值次序以及控制流程变得更加明确。

下面是在Scheme语言中仅使用其基本形式的几个例子，对比了直接风格代码和对应的CPS代码，这里约定了将续体函数表示为名为`k`的形式参数：

直接风格｜续体传递风格

```scheme
(define (pythag x y)
  (sqrt (+ (* x x) (* y y))))
```

```scheme
(define (pythag& x y k)
  (*& x x (lambda (a)
    (*& y y (lambda (b)
      (+& a b (lambda (c)
        (sqrt& c k))))))))
```

```scheme
(define (fact n)
  (if (= n 0)
    1
    (* n (fact (- n 1)))))
```

```scheme
(define (fact& n k)
  (=& n 0 (lambda (t)
    (if t
      (k 1)
      (-& n 1 (lambda (n-1)
        (fact& n-1 (lambda (acc)
          (*& n acc k)))))))))
```

```scheme
(define (fact n)
  (define (loop n acc)
    (if (= n 0)
      acc
      (loop (- n 1) (* n acc))))
  (loop n 1))
```

```scheme
(define (fact& n k)
  (define (loop& n acc k)
    (=& n 0 (lambda (t)
      (if t
        (k acc)
        (-& n 1 (lambda (n-1) 
          (*& n acc (lambda (n*acc)
            (loop& n-1 n*acc k)))))))))
  (loop& n 1 k))
```

对于函数式编程者而言，以续体传递风格表达代码使得在直接风格中隐含的一些事物显露出来：中介值或临时值都被指定了名字，实际参数求值的次序变为显见；随之而来，过程返回变成了对续体的调用，而尾调用变成将传递给这个调用者的续体不加修改的传递给被调用过程。

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

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

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

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

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

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

Scheme｜Python

```scheme
(define (cps-prim f)
  (lambda args
    (let ((r (reverse args)))
      ((car r) (apply f (reverse (cdr r)))))))

(define =& (cps-prim =))
(define *& (cps-prim *))
(define +& (cps-prim +))
(define -& (cps-prim -))
(define sqrt& (cps-prim sqrt))
```

```python
import operator, math
def cps_prim(f):
    return (lambda *args, **kwargs:
        args[-1](f(*args[0:-1], **kwargs)))

eq_ = cps_prim(operator.eq)
mul_ = cps_prim(operator.mul)
add_ = cps_prim(operator.add)
sub_ = cps_prim(operator.sub)
sqrt_ = cps_prim(math.sqrt)
```

在Scheme中，`reverse`函数反转LISP列表所用的单向链表，其首次应用将原来尾部元素反转到了首部，接着取出这个元素应用并再次应用`reverse`函数将余下诸元素反转成原来次序。`apply`函数的应用`(apply f args)`，以`args`列表的诸元素作为实际参数调用`f`函数。函数`eval`和通用图灵机定理`apply`

$apply$

$apply$

$f$

$f'$

$args$

$(arg_{1}, \cdots , arg_{n})$

$arg_{1}, \cdots , arg_{n}$

$apply[f ; args]$

$f'[arg_{1}, \cdots , arg_{n}]$

$arg_{1}, \cdots , arg_{n}$

是传统元循环求值器的两大中心构件

```scheme
(define (EVAL exp env procedures)
  (cond 
    ((atom exp)
      (cond
        ((eq exp 'nil) 'nil)
        ((eq exp 't) 't)
        ((NUMBERP exp) exp)
        (t (VALUE exp env))))
    ((eq (car exp) 'quote)
      (cadr exp))
    ((eq (car exp) 'cond)
      (EVCOND (cdr exp) env procedures))
    (t
      (APPLY
        (VALUE (car exp) procedures)
        (EVLIS (cdr exp) env procedures)
        procedures))))

(define (APPLY fun args procedures)
  (cond
    ((PRIMOP fun) (PRIMOP-APPLY fun args))
    (t 
      (EVAL
        (cadr fun)
        (BIND (car fun) args '())
        procedures))))

(define (EVCOND clauses env procedures)
  (cond
    ((null clauses) (ERROR))
    ((EVAL (caar clauses) env procedures)
     (EVAL (cadar clauses) env procedures))
    (t (EVCOND (cdr clauses) env procedures))))  

(define (EVLIS arglist env procedures)
  (cond 
    ((null arglist) '())
    (t
      (cond
        (EVAL (car arglist) env procedures)
        (EVLIS (cdr arglist) env procedures)))))
```

```scheme
(define (BIND vars args env)
  (cond
    ((= (length vars) (length args))
      (cons (cons vars args) env))
    (t (ERROR))))

(define (VALUE name env)
  (VALUE1 name (LOOKUP name env)))

(define (VALUE1 name slot)
  (cond 
    ((eq slot '&UNBOUND) (ERROR))
    (t (car slot))))

(define (LOOKUP name env)
  (cond 
    ((null env) '&UNBOUND)
    (t (LOOKUP1 name (caar env) (cdar env) env))))

(define (LOOKUP1 name vars vals env)
  (cond
    ((null vars) (LOOKUP name (cdr env)))
    ((eq name (car vars)) vals)
    (t (LOOKUP1 name (cdr vars) (cdr vals) env))))
```

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

```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版本，比如将前面的阶乘函数写为：

Scheme｜Python

```scheme
(define (fact& n k)
  (if (= n 0)
    (k 1)
    (fact& (- n 1) (lambda (acc) (k (* n acc))))))
```

```python
def fact_cps(n, k):
    return (
        k(1) if n == 0 else
        fact_cps(n - 1, lambda acc: k(n * acc)))
```

Daniel P. Friedman和Mitchell Wand，在1984年论文《续体与协程》中，为Scheme 84子集语言介入了基于表达式、环境和续体的元循环解释器

```scheme
(define meaning 
  (lambda (e r k) ; e = expression, r = environment, k = continuation
    (case (type-of-expression e)
      [constant (k e)]
      [identifier (k (R-lookup e r))]
      [lambda (k (lambda (actuals k)
        (evaluate-all 
          (body-pts e)
          (extend-env r (formals-pt e) actuals)
          k)))]
      [if (meaning (test-pt e) r
        (lambda (v) (if v
          (meaning (then-pt e) r k)
          (meaning (else-pt e) r k))))]
      [set! (meaning (val-pt e) r
        (lambda (v) (k (store! (L-lookup (id-pt e) r) v))))]
      [call/cc (meaning (fn-pt e) r
        (lambda (f)
          (f
            (list (lambda (actuals dummy) (k (car actuals)))) 
            k)))]
      [application (meaning-of-all (comb-parts e) r
        (lambda (vals) ((car vals) (cdr vals) k)))])))

(define evaluate-all
  (lambda (exp-list r k)
    (meaning (car exp-list) r
      (if (null? (cdr exp-list))
        k
        (lambda (v) (evaluate-all (cdr exp-list) r k))))))

(define meaning-of-all
  (lambda (exp-list r k)
    (meaning (car exp-list) r
      (lambda (v) (if (null? (cdr exp-list))
        (k (cons v nil))
        (meaning-of-all (cdr exp-list) r
          (lambda (vr) (k (cons v vr)))))))))
```

在其中以续体传递方式定义了`call/cc`，并将函数应用时的实际参数列表形式从`(arg<sub>1</sub> …… arg<sub>n</sub> k)`修订为`((arg<sub>1</sub> …… arg<sub>n</sub>) 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`的调用

```scheme
(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的来演示：

```sml
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.(2*x)`，对整个程序也就是这个表达式进行归约：

```sml
⇒ 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.(2*x)`于`v = 0`，继续进行归约：

```sml
⇒ (fn x => 2 * x) 0 ⇒ 2 * 0 ⇒ 0 	 	
```

### 示例

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

#### 立即返回

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

```scheme
(define (f return)                                                                                                                               
  (return 2)                                                                                                                                     
  3)

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

(call/cc f)
===> 2
```

第一个演示，以恒等函数

```scheme
(lambda (x) x)
```

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

#### 生成器

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

```scheme
(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`在这里被用到了两处：一处是

```scheme
(call/cc iterator)
```

它以当前取用遍历返回值续体调用迭代器；另一处是

```scheme
(call/cc (lambda (resume) ……))
```

它在迭代器遍历目标列表之时捕获当前位置，用于下次重入迭代器之时于此处恢复执行。下面是上述代码的简单用例：

```scheme
(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)`之上，而得到的闭包

```scheme
(lambda () (call/cc iterator))
```

每次执行`(generate-digit)`之时，都转为执行

```scheme
(call/cc iterator)
```

它捕获取用迭代器遍历聚集逐个返回的值的续体，比如用例中有2个`display`作为外部应用续体。

在第一次执行`(generate-digit)`之时，`iterator`所绑定的是静态定义的函数，执行`(call/cc iterator)`，将外部应用续体绑定到函数`iterator`的形式参数`yield`之上；然后开始遍历列表的元素进行迭代的

```scheme
(for-each (lambda (item) ……) lst)
```

在求值

```scheme
(set! yield ……)
```

第二个实际参数之时，进行每一次迭代步骤

```scheme
(call/cc (lambda (resume) ……))
```

其中的

```scheme
(set! iterator resume)
```

将绑定到变量`resume`上的当前续体，重新绑定到函数名字`iterator`之上用于以后恢复执行，最后执行暂停表达式`(yield item)`返回当前列表项目。

在下一次执行`(generate-digit)`之时，`iterator`所绑定的已经是表示迭代器内部恢复位置的续体，执行`(call/cc iterator)`，以当前外部续体作为参数调用这个内部位置续体`iterator`；控制流程将在上次迭代的

```scheme
(set! yield (call/cc ……))
```

之处恢复，此刻`(set! yield ……)`中的第二个实际参数`(call/cc ……)`求值完毕，这个设置表达式的将变量`yield`的绑定内容更新为此刻传入的外部应用续体，此后继续这一次的迭代步骤。在遍历了列表的元素之后迭代结束，最终执行`(yield 'stop-iteration)`，返回一个约定的文字 (计算机编程)常量。

#### 协程

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

```scheme
(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`，取出并应用就绪线程列表头部的续体而使本线程脱离运行，最终在无就绪者等待之时结束。调度过程在每一轮并发运行循环中只运行一次。调度过程在所有分叉过程之后调用，它起到的根本作用是充当会合点，即并发运行的多个线程中的最终剩下的唯一线程。下面是上述代码的简单用例：

```scheme
(import (srfi 28))

(define (echo-string-n-times str n)
  (let loop ((i 0))
    (if (< i n) (begin
      (display (format "~a ~a~%" str i))
      (yield)
      (loop (+ i 1))))))

(define (main)
  (fork echo-string-n-times "This is AAA" 3)
  (fork echo-string-n-times "Hello from BBB" 2)
  (schedule))

(main)
```

其输出为：

```console
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`：

```scheme
(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)))))
```

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

```scheme
(import (srfi 28))

(define (echo-string-n-times str n)
  (let loop ((i 0))
    (if (< i n) (begin
      (yield (format "~a ~a~%" str i))
      (loop (+ i 1))))))

(define (main)
  (fork echo-string-n-times "This is AAA" 3)
  (fork echo-string-n-times "Hello from BBB" 2)
  (schedule display))

(main)
```

### 编程语言的直接支持

除了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的包含有界续体算子的扩展库。

## 外部链接

- Teach Yourself Scheme in Fixnum Days by Dorai Sitaram features a nice chapter on continuations.