continuation 实在是一个比较晦涩的概念。花了不少时间，看了很多资料，总算是大概弄明白了。这里我试着尽可能清楚地解释一些关于 continuation 的细节。

• 1. continuation 是什么
• 2. continuation 的特性
• 3. continuation 的作用
  • 3.1. return
  • 3.2. generator
  • 3.3. thread
• 4. 消除 call/cc

1. continuation 是什么

Contination 最早出现在 scheme 中，是一种流程控制机制，实现诸如 return、break、thread 以及 exception 等功能。continuation 被翻译成『延续』，表示程序将要进行的计算。

这些简单代码应该能提供一个大致的印象：

(define f '())               ;; 0

(+ 2 (* 2
        (call/cc
         (lambda (c)
           (set! f c)
           1))))             ;; 1

(f 5)                        ;; 2
;; => 12

第 1 条语句的含义是，将当前 continuation 赋值给变量 f，当前 continuation 是什么呢？既然 continuation 表示程序中将要进行的计算，那么它应该是乘以 2 再加上 2。所以 (f 5) 返回 12。可以用函数来表示 continuation：

(lambda (val)
  (+ 2 (* 2 val)))

尽管很多时候在内部实现上被表示为数据结构，然而从含义上看，continuation 本质上确实是一个函数。

2. continuation 的特性

• 特性零：scheme 程序使用函数 call/cc 来获取程序当前的 continuation

• 特性一：call/cc 的参数是一个匿名函数，匿名函数的参数即为当前 continuation。和函数一样，continuation 也是 first class，被调用时接受一个参数

• 特性二：call/cc 的返回值遵循这样的规则：如果 continuation 被调用，则 call/cc 立即返回，返回值为调用当前 continuation 的参数；否则正常执行并返回

• 特性三：continuation 保存了程序执行时的所有上下文。continuation 被调用后，当前的执行状态被挂起，转而跳到 continuation 所在上下文继续执行

下面这些代码片段可以体现这四个特点：

(define f '())                       ;; 0

(append (list 1 2 3)
        (list (call/cc (lambda (c)
                         (set! f c)
                         4))))       ;; 1

;; => (1 2 3 4)
(f 5)                                ;; 2
;; => (1 2 3 5)

(+ 1 (f 5))                          ;; 3
;; => (1 2 3 5)

语句 1 中使用 call/cc 获取了当前 continuation，并且绑定在参数 c 中。之后将 c（也就是当前的 continuation）赋值给变量 f，由于过程中 c 没有被调用，所以 call/cc 顺序执行，call/cc 返回 4。程序最后返回 (1 2 3 4)。

语句 2 中使用参数 5 来调用 f，这里的 f 就是从语句 1 中获取到的 continuation。根据特性二，一旦 continuation 被调用就立即返回，且返回值为调用参数（在这里是 5）。但这个 5 该返回到哪里呢？根据特性三，此时程序跳转到了语句 1 所在的上下文，5 成了 (call/cc (lambda (c) (set! f c 4))) 的返回值。之后程序继续执行 (append (list 1 2 3) (list ...))，最终返回 (1 2 3 5)。

既然语句 2 的返回值是一个 list，那么在语句 3 中使用这个 list 和一个整数来调用加法，为什么不会抛异常呢？因为特性三：一旦 f 被调用，当前程序立即被挂起，不再执行。

特性零表面上很好理解，其实很容易被误解。原因在于『当前』这两个字。『当前』的含义是：当 call/cc 被调用时，自其所在的位置，沿着它的调用者，一直到 top-level。也就是说『当前』取决在哪里被调用，而不是在哪里被定义。可见 continuation 不具备引用透明性。

语句 4 到语句 8 展示了 continuation 的非引用透明性。

(define current-cc
  (lambda ()
    (call/cc (lambda (c) c))))       ;; 4

(define x (current-cc))              ;; 5

(x 0)                                ;; 6

(display x)                          ;; 7
;; => 0

((current-cc) 0)                     ;; 8
;; => raise error

语句 5 中将 (current-cc) 赋值给 x，如果具有引用透明性的话，那么语句 6 和 8 应该是等价的。但实际上语句 6 正常执行了，语句 8 却抛出错误。因为 call/cc 获取的 continuation 是基于被调用时的上下文，而不是定义时的环境。

语句 5 (current-cc) 获取到的 continuation 是下面这样的。为什么可以写成这样，在第三节《消除 call/cc》会提到

(lambda (k)
  (define x k))

所以，语句 6 可以写成这样：

((lambda (k)
   (define x k)) 0)

这也解释了语句 7 为什么输出 0。但是语句 8 中 (current-cc) 获取到的 continuation 是这样的：

(lambda (k)
  (k 0))

语句 8 实际上是用 0 来调用 0，所以抛出了错误。

3. continuation 的作用

下面根据 continuation 的这些特点，实现了 return、generator 和 thread。

3.1. return

作为一门函数型语言，scheme 是没有 return 语句的，每一个函数都会隐式地返回一个值，这个值又传递给上一级函数调用，这样逐级返回指定顶层。也就是说显式的 return 对于 scheme 并没有多大用处。

但如果在 for-each 这样的过程式代码中，想在中途返回一个值就显得比较困难了。

下面这段代码利用了 continuation 来实现在 for-each 循环中 return 的功能。

(define member?
  (lambda (lst element)
    (define member
      (lambda (lst element return)
        (for-each (lambda (l)
                    (if (equal? l element)
                        (return l))) lst))
      '())

    (call/cc (lambda (c)
               (member lst element c)))))

(member? '(1 2 3 4 5) 3) ;; => 3

(member? '(1 2 3 4 5) 6) ;; => ()

这个例子是特性二和三的体现，当 member 中的 return（也就是传入 member 的 continuation）被调用，member? 会立即返回，返回值为调用 return 的参数 l。

这叫做 non-local exit。和 return 一样，break 也是一种 non-local exit，只是退到哪里的问题。

3.2. generator

(define make-next
  (lambda (lst)
    (define next-i
      (lambda (lst return)
        (for-each (lambda (l)
                    (call/cc (lambda (c)
                               (set! next-i c)
                               (return l))))
                  lst)
        "no element"))

    (define next
      (lambda ()
        (call/cc (lambda (c)
                   (next-i lst c)))))
    next))

(define f (make-next '(1 2 3 4)))

(f) ;; => 1

(f) ;; => 2

(f) ;; => 3

(f) ;; => 4

(f) ;; => "no element"

这个例子用了两个 call/cc。

next 中使用 call/cc 是为了实现 return。

next-i 中的 call/cc 则要复杂一些，当第一次执行 (f)，next 内部会调用 next-i，这时 next-i 是 make-next 中定义的普通函数，next-i 先获取 continuation 并赋值给自身（next-i），然后再返回 lst 的第一个元素。把 continuation 赋值给 next-i 之后，next-i 就变成 continuation 了。所以第二次调用 next-i 时程序会跳到之前 (set! next-i c) 时的运行上下文，接着当时返回第一个元素的地方继续运行，最终 for-each 迭代第二个元素，并再次保存当前 continuation 到 next-i。类似的，直到第五次执行 (f)，next-i 返回 "no element"。

3.3. thread

前面两个例子，都不是非 continuation 不能实现。不使用 continuation，改变代码的结构程序也可以在任何位置 return；使用闭包，也能实现 generator。下面这个关于 thread 的例子，更能体现 continuation 的强大威力。

这里的 thread 不是指系统级的线程，它更像 lua 的协程，程序在运行时能主动控制执行流程。

(define *queue* '())

(define enqueue
  (lambda (task)
    (set! *queue* (append *queue* (list task)))))

(define dequeue
  (lambda ()
    (let ((task (car *queue*)))
      (set! *queue* (cdr *queue*))
      task)))

(define start
  (lambda ()
    ((dequeue))))

(define switch
  (lambda ()
    (call/cc (lambda (c)
               (enqueue c)
               ((dequeue))))))

(define print-loop
  (lambda (str)
    (define print-loop-i
      (lambda (str n)
        (format #t "~A ~A\n" str n)
        (switch)
        (print-loop-i str (+ n 1))))

    (lambda ()
      (print-loop-i str 1))))

(enqueue (print-loop "AAAAA"))                   ;; 0

(enqueue (print-loop "BBBBB"))                   ;; 1

(start)                                          ;; 2

这个例子来自 Wikipedia，进行了些简化。

这段代码会交替打印 “AAAAA” 和 “BBBBB”，就好像两个线程同时工作。语句 0 和 1 分别将两个打印函数加入全局队列，执行 (start) 后队列启动，先是 (print-loop "AAAAA") 开始工作。print-loop 函数循环打印字符，每打印一条字符后会执行 switch 函数。switch 的作用是保存当前 continuation，将其加入队列尾部，然后将队列头部的函数（或者 continuation）取出并调用。

打印 “AAAAA” 之后，switch 取出打印 “BBBBB” 的任务，反之亦然，如此交替执行。最终程序的运行效果就是循环往复地交替打印两条字符。

switch 是 thread 的核心，它像一个调度员，协调整个队列。(print-loop "AAAAA") 和 (print-loop "BBBBB") 调用的是同一个 switch 函数，但其中获取到的 continuation 却不一样（又一个非引用透明的例子）。

4. 消除 call/cc

现代语言中常见的 return、break、goto、thread、exception 都可以算作 continuation 的子集。然而 continuation 并不太容易理解，我们可以根据 continuation 的特性，通过变形来消除 call/cc。

比如前面提到过的一个例子：

(define f '())                        ;; 0
(append (list 1 2 3)
        (list (call/cc (lambda (c)
                         (set! f c)
                         4))))        ;; 1
(f 5)    ;; => (1 2 3 5)              ;; 2

既然 continuation 本质是函数，那完全可以把上面的例子改写成函数：

• continuation 可以被调用，并且接受一个参数
• continuation 表示自 call/cc 所在一层一直上溯到顶层的计算行为

语句 1 中的 call/cc 获取到的 continuation 应该具有这种形式：

(define cont
  (lambda (k)
    (append (list 1 2 3)
            (list ...))))

cont 中的 ... 是什么呢？

答案在特性二中：call/cc 的返回值取决于 continuation 有没有被调用，被什么调用。因此在消除 callcc 时遵循两个原则：

• 原则一：如果在 call/cc 中 continuation 被调用，call/cc 直接返回调用 continuation 的参数

• 原则二：如果在 call/cc 中 continuation 没有被调用，那么 continuation 一定会在外部被调用，否则 continuation 就没有存在的意义。当 continuation 在外部被调用时，call/cc 的返回值依然是调用 continuation 的参数，也就是 cont 中最外层的 lambda 的参数 k

显然，代码中的 continuation 只是赋值给了 f，没有被调用，最终获取到的 continuation 是这样的：

(define cont
  (lambda (k)
    (append (list 1 2 3)
            (list k))))

所以 (f 5) 返回 (1 2 3 5) 。

另一个例子：

(((call/cc (lambda (c) c))
  (lambda (x) x)) "xxx")    ;; => "xxx"

这个例子中 call/cc 将 continuation 直接返回了，返回后的 continuation 立即被 (lambda (x) x) 调用。根据原则一，获取到的 continuation 是这样的：

(define cont
  (lambda (x) x))

将 cont 代入代码：

(((lambda (x) x) (lambda (x) x)) "xxx")   ;; => "xxx"

这样消除 call/cc 后的代码和原代码是完全等价的。

（完）

参考链接：

• 《On Lisp》by Paul Graham
• Wikipedia
• A short introduction to call-with-current-continuation
• A page about call/cc