Continuation 从入门到放弃

最近又捡起了一本关于 List 的书，之前只看了一点就放弃了。当时我在读到 continuation 的时候，整个人都有点懵逼了。刚刚又重新读到这部分，终于好像来感觉了。

什么是 Continuation

简单来说，某个位置的 continuation 可以理解成在这个位置要做的运算。比如在 (+ 1 2) 这个例子里，不严谨地说，对于 2 来说，它所处的 continuation 就是把它和 1 相加。如果我们有办法把这个 continuation 抽取并保存下来，我们就可以把它运用(apply)到其他值上来执行相同的运算。

如何获取 Continuation

那么现在问题来了，我们要怎么获得一个位置的 continuation 呢？接下来的这几句话有点绕，我们一句句看。

Scheme 本身提供了 call/cc 函数。它接受一个函数作为参数。我们姑且叫这个函数为 cc-consumer。cc 是 current continuation 的缩写。
这个函数 cc-consumer 就和它的名字一样，也接受一个参数，这个参数就是当前的 continuation，也就是 cc。
cc 就像上面说的，可以被理解成某个位置接下来要做的运算。这也意味着，cc 也是一个函数，它接受一个参数作为这个位置上的值。它一旦被调用，就会回到它对应的位置，并且把它的参数放在这个位置，然后进行接下来的操作。

说了这么多，其实也很难有个直观的了解。让我们用伪代码来描述一下这些函数和参数的类型。

T call/cc(ContinuationConsumer cc_consumer);

using ContinuationConsumer = function<T(Continuation)>;

using Continuation = function<void(T)>;

接下来，我们来看一个简单的例子。这个例子使用了 call/cc 来实现最开始我们提到的 add1 这个操作。你可以使用 Chez Scheme 来执行下面的代码。

(define add1 #f)

(+
  1
  (call/cc
    (lambda (cc)
            (set! add1 cc)
            0
    )
  )
)

(add1 10) ; => 11
(add1 20) ; => 21

在上面代码的第四行，我们通过调用 call/cc 来获取当前的 continuation。
call/cc 接受一个用户自定义的函数作为参数，并且会把当前的 continuation 传给这个函数作为它的参数。简单来说，call/cc 接受一个回调函数，并把 continuation 传给回调函数。
在回调函数中，我们把 continuation 保存到了 add1 这个变量中，之后我们就可以使用它来访问这个 continuation。

在上面代码的最后两行，我们通过 add1 来使用保存下来的 continuation。当我们使用它的时候，程序会把传给它的参数，放到 call/cc 对应的位置上然后继续执行。显然，(add1 10) 就会执行 (+ 1 10) => 11。

为什么需要 Continuation

我们废了半天劲理解了 continuation 是什么（甚至可能没有理解…)，但是问题来了。为什么我们需要它呢？continuation 可以帮我们做很多事，比如提前返回。提前返回听上去好像很普通（比如 Java 里一个 return 就好了），但是 Lisp 其实没有很简单的办法。有了 continuation，我们就可以实现这一点。

(define (find lst elem)
  (call/cc (lambda (return)
    (for-each
      (lambda (e)
              (if (eq? elem e)
                  (return 'found)
                  'nil))
      lst)
    (return 'not-found)
    )))

因为 call/cc 的调用在最外层，所以这个位置的 continuation 就是什么也不做，直接返回。而这个 continuation 被传递给参数 return，这样当我们想返回时，调用 return 即可。

更复杂的例子: Generator

上面的例子比较简单，我们来看一个比较复杂的例子，generator。我们想实现一个函数，每次调用它都会依次返回给定 list 中的元素。这样的函数其实也可以通过闭包来实现，但是我们今天试试用 call/cc 来实现它。

第一次尝试

(define (new-generator lst)
  (define (cc-consumer return)
    (for-each
      (lambda (e)
        (return e))
      lst))
  (define (generator)
    (call/cc cc-consumer))
  generator)

(define generator (new-generator '(1 2 3)))

先别急着说”第一次尝试”就这么复杂。上面大部分的代码其实都是模版代码。

先看第一行，因为我们想要实现一个可以根据指定 list 创建 generator 的函数，所以很自然的，我们定义一个接受 lst 作为参数的 new-generator。这个函数应该返回一个 generator，也是一个函数。所以在 7～9 行，我们定义一个函数，并且返回它。

然后我们再看第8行。显然今天的主角是 call/cc，所以我们这里怎么也得用一下它对吧。我们定义了 cc-consumer 这个函数作为 call/cc 的参数。

最后我们看第一个版本的核心部分，第2～6行。在 cc-consumer 中，我们遍历了传入的 lst，每次都调用 return 返回每个元素。

显然这次尝试是失败的。每次调用 generator 都只会返回列表中的第一个元素。这是因为我们目前只通过 continuation 实现了提前返回的功能。我们还需要实现在上一次返回的位置接着执行下去。

第二次尝试

(define (new-generator lst)
 (define (cc-consumer return)
  (for-each
   (lambda (e)
    (call/cc (lambda (resume)             ; new
              (set! cc-consumer resume)   ; new
              (return e))))               ; new
   lst))
 (define (generator)
  (call/cc cc-consumer))
 generator)

(define generator (new-generator '(1 2 3)))

第二次尝试，我们改动了三行。因为我们想让每次调用 generator 都会回到上次返回的地方，因为我们希望能够把上次返回的位置的 continuation 保存下来。因此，我们把原本第一个版本调用 return 的地方，改成了调用 call/cc。然后在第6行，我们把这个位置的 continuation 赋值给 cc-consumer。这样，当我们再次调用 generator 的时候，我们会回到第6行，然后执行下一次循环。

用这个版本，我们的 generator 运行的很好。每次调用都正确的返回了下一个元素。但是这个版本其实有一个严重的 bug。为了暴露出这个 bug，我们现在换一下需求，不再直接返回元素，而是做一些改动。如果是第奇数个元素，就直接返回；否则就返回它的相反数。

(define (new-generator lst)
 (define (cc-consumer return)
  (for-each
   (lambda (e)
    (call/cc (lambda (resume)
              (set! cc-consumer resume)
              (return e))))
   lst))

 (let ((index 0))
  (define (generator)
       (set! index (+ index 1))
       (if (eq? (mod times 2) 0)
           (- 0 (call/cc control-state))
           (call/cc control-state)))
  generator))

上面的版本尝试实现新的需求。它的主要改动在于我们维护一个 index 来判断当前是第几个元素，然后决定是否取反。这个改动的目的主要是要构造出两个不同的 continuation，也就是第14和15行。我们通过多次调用 generator 发现，每次都返回了元素本身，不管它是第几个元素。之所以这样，就是因为 cc-consumer 的参数 return 没有被更新过，永远都是用第一次调用 cc-consumer 时的 continuation，也就是不取反的情况。

最后的版本

(define (new-generator lst)
 (define (cc-consumer return)
  (for-each
   (lambda (e)
    (set! return                                 ; new
          (call/cc (lambda (resume)
                     (set! cc-consumer resume)
                     (return e))))
    )                                            ; new
   lst))

 (let ((index 0))
  (define (generator)
       (set! index (+ index 1))
       (if (eq? (mod times 2) 0)
           (- 0 (call/cc control-state))
           (call/cc control-state)))
  generator))

为了解决上面发现的问题，我们需要更新 return 的值。

当我们第一次调用 generator 的时候，因为 index 是 1，所以第 17 行会被执行，这是，return 的值会是第 17 行对应的 continuation。当这次调用完成之后，cc-consumer 已经被更新成 resume 了，也就是第6行对应的 continuation。这时 return 还没有更新，我们又回到第 17 行，然后 generator 返回，第一次执行结束。

当我们再一次调用 generator 的时候，我们会触发第16行的 call/cc，而这次的参数是更新后的 cc-consumer，也就是 resume。这次调用会让我们回到第6行。这时，第6行的返回值，也就是第16行的 continuation。它会被赋值给 return。赋值完之后，我们开始第二次循环，这次，我们会返回第二个元素。注意，因为 return 是第16行的 continuation，我们会正确地执行取反的操作。

总结

我个人觉得 continuation 很绕，很难解释地清楚。很多的文章都直接把一个完成的例子抛出来，就算读者理解了这么写能够 work，但是还是不知道为什么要这么写。我把 generator 这个例子拆成了三个阶段，来解释每一部分的代码写成那样的原因，希望能够为你理解 continuation 做一点微小的贡献。

瞎扯

目录