Continuation 是什么？

你好，世界！

了解 Scheme 的人一定听说过 Continuation 的概念。它可以翻译成（计算的）延续，是一个程序流程控制的机制。对我来说，Continuation 是一个比较难理解和使用的概念。让我们花一些时间来学习一下这个非常重要的概念。

简单来说，Continuation 是指一系列后续需要执行的计算步骤。让我们来看一个例子。

在 Scheme 中，0 ＋ 1 ＋ 2 可以表示为 (+ 2 (+ 1 0))。其中表达式 (+ 1 0) 将会加上2。我们就称“加上2”是表达式 (+ 1 0) 的延续（Continuation）。因此，一个表达式的 Continuation 也可以理解为接收该表达式结果的计算。如果我们想写出表达式 (+ 1 0) 的 Continuation，我们可以写

(lambda (k) (+ 2 k))

这就是说，表达式 (+ 1 0) 的 Contiuation 会获得一个数，并把它加上2。

在大多数编程语言中，计算的延续是隐含的，我们无法控制。在 Scheme 中，我们可以使用内置的函数 call-with-current-continuation，或者其更著名的简写 call/cc 来捕获当前的 Continuation 并按照我们的想法做进一步处理。这使得 Scheme 变得非常强大而优美。

call-with-current-continuation

call-with-current-continuation，下面简称 call/cc，它的用法如下：

(call/cc (lambda (C) ...))

它有以下特点：

• call/cc 的参数是一个 lambda 函数。
• 该 lambda 函数有一个参数，比如 C。
• C 代表着当前的 Continuation，它也是一个函数。
• 将来再调用 C 的时候，回到 call/cc 的上下文继续执行原来的程序。
• 调用 C 的时候，比如 (C v)，返回值是调用时的参数 v。

这样说起来有时候比较难理解，那么我们来看一下 call/cc 的用法实例。

捕捉 Continuation

参看代码：

(define fc '())  ; 定义捕捉 Continuation 的函数

(define (f)
  (let ((v (call/cc (lambda (c) (set! fc c) 1))))
    (display "v is: ")
    (display v)
    (newline)))
   

当我们运行函数 f 的时候并没有调用延续 c，而是把它赋值给了 fc。这时 call/cc 正常运行，返回1，而 v 的值正常被赋为1。所以 f 的结果是：

v is: 1

将来任何时候，如果我们调用 Continuation 函数 fc 都会返回到函数 f 的现场。比如

(fc 100)

call/cc 都会返回 fc 的参数，即100，那么 v 就会被赋值100。所以 f 的结果是：

v is: 100

非本地退出

参看代码：

(define (find-even-number lst)
  (call/cc (lambda (c) (for-each (lambda (x)
                                   (if (even? x) (c x))) lst)  ; 找到第一个偶数时马上退出
                   'no-even-number)))  ; 没有找到偶数

(display (find-even-number '(1 3 4 5)))  ; 返回：4
(display (find-even-number '(1 3 5 7)))  ; 返回：no-even-number
   

生产者和消费者

许多程序类似生产和消费。一个函数产生价值，另一个函数消费价值，比如服务器和客户端就是这样的关系。我们可以用 Continuation 实现这样的关系。

参看代码：

(define dish '())

(define (put! fruit) (set! dish (list fruit)))
(define (get!) (let ((fruit (car dish))) (set! dish '()) fruit))

(define (consumer back)
  (let loop()
    (if (pair? dish)
        (let ((fruit (get!)))
          (format #t "C: get a ~a~%" fruit)
          (set! back (call/cc back))
          (format #t "resume from producer: ~a~%" fruit)
          (loop)))))

(define (producer back)
  (for-each (lambda (fruit) (put! fruit)
                    (format #t "P: put a ~a~%" fruit)
                    (set! back (call/cc back))
                    (format #t "resume from consumer: ~a~%" fruit))
            '("peach" "grape" "lemon")))

运行程序：

(producer consumer)

生产者和消费者会交替输出：

P: put a peach
    C: get a peach
    resume from consumer: peach
    P: put a grape
    resume from producer: peach
    C: get a grape
    resume from consumer: grape
    P: put a lemon
    resume from producer: grape
    C: get a lemon
    resume from consumer: lemon

总之，Continuation 是一个非常强大的概念，它可以保存上下文并进入其他函数。用它可以实现返回、跳转、多进程、异步、非本地退出等有用的结构。call/cc 的代码不太容易理解，需要多实践来体会。好在 Continuation 的多种算法实现已经打包在许多库中，独立执行，对最终用户没有直接的影响。

如果你对 Scheme 的 Continuation 和 call/cc 还有问题，立伯乐 或许可以帮你。

让 Scheme 带你进入自由软件的美好世界！