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

什么是 Continuation

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

如何获取 Continuation

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

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

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

1
2
3
4
5
T call/cc(ContinuationConsumer cc_consumer);

using ContinuationConsumer = function<T(Continuation)>;

using Continuation = function<void(T)>;

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(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,我们就可以实现这一点。

1
2
3
4
5
6
7
8
9
10
(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 来实现它。

第一次尝试

1
2
3
4
5
6
7
8
9
10
11
(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 实现了提前返回的功能。我们还需要实现在上一次返回的位置接着执行下去。

第二次尝试

1
2
3
4
5
6
7
8
9
10
11
12
13
(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,我们现在换一下需求,不再直接返回元素,而是做一些改动。如果是第奇数个元素,就直接返回;否则就返回它的相反数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(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,也就是不取反的情况。

最后的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(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 做一点微小的贡献。