續體

在電腦科學中，續體（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.