Continuation

Continuation 也是一个老生常谈的东西了，我们来回顾一下。首先我们看一下 TSPL4 中定义的表达式求值需要做的事：

During the evaluation of a Scheme expression, the implementation must keep track of two things: (1) what to evaluate and (2) what to do with the value.

Continuation 即为其中的(2)，即表达式被求值以后，接下来要对表达式做的计算。R5RS 中 continuation 的定义为：

The continuation represents an entire (default) future for the computation.

比如 (+ (* 2 3) (+ 1 7)) 表达式中，(* 2 3)的 continuation 为：保存 (* 2 3) 计算出的值 6，然后计算 (+ 1 7) 的值，最后将两表达式的值相加，结束；(+ 1 7) 的 continuation 为：保存 (+ 1 7) 的值 8，将其与前面计算出的 6 相加，结束。

Scheme 中的 continuation 是 first-class 的，也就是说它可以被当做参数进行传递和返回；并且 Scheme 中可以将 continuation 视为一个 procedure，也就是说可以调用 continuation 执行后续的运算。

call/cc

每个表达式在求值的时候，都会有一个对应的 current continuation，它在等着当前表达式求值完毕然后把值传递给它。那么如何捕捉 current continuation 呢？这就要用到 Scheme 中强大的 call/cc 了。call/cc 的全名是 call-with-current-continuation ，它可以捕捉当前环境下的 current continuation 并利用它做各种各样的事情，如改变控制流，实现非本地退出(non-local exit)、协程(coroutine)、多任务(multi-tasking)等，非常方便。注意这里的 continuation 将当前 context 一并打包保存起来了，而不只是保存程序运行的位置。下面我们来举几个例子说明一下 call/cc 的用法。

current continuation

我们先来看个最简单的例子 —— 用它来捕捉 current continuation 并作为 procedure 调用。call/cc 接受一个函数，该函数接受一个参数，此参数即为 current continuation。以之前 (+ (* 2 3) (+ 1 7)) 表达式中 (* 2 3) 的 continuation 为例：

1
2
3
4
5

(define cc #f)
(+ (call/cc (lambda (return)
                (set! cc return)
                (* 2 3)))
   (+ 1 7))

我们将 (* 2 3) 的 current continuation (用(+ ? (+ 1 7))表示) 绑定给 cc 变量。现在 cc 就对应了一个 continuation ，它相当于过程 (define (cc x) (+ (x) (+ 1 7)))，等待一个值然后进行后续的运算：

1
2
3
4
5
6

> cc
#<continuation>
> (cc 10)
18
> (cc (* 2 3))
14

这个例子很好理解，我们下面引入 call/cc 的本质 —— 控制流变换。在 Scheme 中，假设 call/cc 捕捉到的 current continuation 为 cc(位于 lambda 中)，如果 cc 作为过程 直接或间接地被调用（即给它传值），call/cc 会立即返回，返回值即为传入 cc 的值。即一旦 current continuation 被调用，控制流会跳到 call/cc 处。因此，利用 call/cc，我们可以摆脱顺序执行的限制，在程序中跳来跳去，非常灵活。下面我们举几个 non-local exit 的例子来说明。

Non-local exit

Scheme 中没有 break 和 return 关键字，因此在循环中如果想 break 并提前返回的话就得借助 call/cc。比如下面的例子寻找传入的 list 中是否包含 5：

1
2
3
4
5
6
7
8
9
10
11
12

(define (do-with element return)
  (if (= element 5)
      (return 'find-five)
      (void)))
(define (check-lst lst)
  (call/cc (lambda (return)
             (for-each (lambda (element)
                        (do-with element return)
                        (printf "~a~%" element))
                      lst)
             'not-found)))

测试：

1
2
3
4
5
6
7
8
9

> (check-lst '(0 2 4))
0
2
4
'not-found
> (check-lst '(0 3 5 1))
0
3
'find-five

check-lst 过程会遍历列表中的元素，每次都会将 current continuation 传给 do-with 过程并进行调用，一旦do-with 遇到 5，我们就将结果传给 current continuation (即 return)，此时控制流会马上跳回 check-lst 过程中的 call/cc 处，这时候就已经终止遍历了（跳出了循环）。call/cc 的返回值为 'find-five，所以最后会在控制台上打印出 'find-five。

我们再来看一个经典的 generator 的例子，它非常像 Python 和 ES 6 中的 yield，每次调用的时候都会返回 list 中的一个元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

(define (generate-one-element-at-a-time lst)
  ;; Hand the next item from a-list to "return" or an end-of-list marker
  (define (control-state return)
    (for-each
     (lambda (element)
               (set! return (call/cc
                              (lambda (resume-here)
                                ;; Grab the current continuation
                               (set! control-state resume-here)
                               (return element)))))
     lst)
    (return 'you-fell-off-the-end))
  ;; This is the actual generator, producing one item from a-list at a time
  (define (generator)
    (call/cc control-state))
  ;; Return the generator
  generator)
(define generate-digit
  (generate-one-element-at-a-time '(0 1 2)))

调用：

1
2
3
4
5
6
7
8

> (generate-digit)
0
> (generate-digit)
1
> (generate-digit)
2
> (generate-digit)
'you-fell-off-the-end

注意到这个例子里有两个 call/cc，大家刚看到的时候可能会有点晕，其实这两个 call/cc 各司其职，互不干扰。第一个 call/cc 负责保存遍历的状态（从此处恢复），而 generator 中的 call/cc 才是真正生成值的地方（非本地退出）。其中一个需要注意的地方就是 control-state，它在第一次调用的时候还是个 procedure，在第一次调用的过程中它就被重新绑定成一个 continuation，之后再调用 generator 生成器的时候，控制流就可以跳到之前遍历的位置继续执行下面的过程，从而达到生成器的效果。

阴阳谜题

continuation 环境嵌套。后面有时间专开一篇分析～

1
2
3
4
5

(let* ((yin
         ((lambda (cc) (display #\@) cc) (call-with-current-continuation (lambda (c) c))))
       (yang
         ((lambda (cc) (display #\*) cc) (call-with-current-continuation (lambda (c) c)))))
    (yin yang))

call/cc与数理逻辑

这里简单提一下 call/cc 与类型系统和数理逻辑的联系。call/cc 的类型是 ((P → Q) → P) → P，通过 Curry-Howard 同构，它可以对应到经典逻辑中的 Peirce’s law：

$$((P \to Q) \to P) \to P$$

Peirce’s law 代表排中律 $P \land \lnot P$，这条逻辑无法在 λ演算所对应的直觉逻辑中表示（直觉逻辑中双重否定不成立），因此 call/cc 无法用 λ表达式定义。通常我们用扩展后的 $\lambda \mu \ calculus$ 来定义 call/cc，$\lambda \mu \ calculus$ 经 Curry-Howard 同构可以得到经典逻辑。

References

• The Scheme Programming Language, 4th Edition
• Short introduction to call-with-current-continuation
• The Revised Revised Revised Revised Revised Report on the Algorithmic Language Scheme (R5RS)
• The Racket Guide, 10.3 Continuations
• Call-with-current-continuation, Wikipedia
• The Continuation Passing Transform and the Yoneda Embedding
• What is continuation-passing style in functional programming? - Quora