[原]重新开始学习Scheme（4）：难学却重要的Scheme特性

这一篇将讲述[原]重新开始学习Scheme（1） 里的first class continuation。关于continuation这个单词的翻译，有那么几种，有“延续”、“继续”、“续延”。个人认为，“续延”应当算是最好的了。这个翻译是由裘宗燕老师提出来的。

Continuation是由Scheme引入函数式编程中的。这个概念相当重要，但是理解起来却比较困难——也许对于我来说困难，但对于别人来说并不一定是这样。说它重要，是因为应用面比较广，比如协作例程、异常处理；还可以模拟别的编程语言里的return、实现无条件跳转等。其最大，也是最广泛的应用之一就是用于web服务器的开发。

在对任意一个Scheme表达式求值时，必须记录两件事：

1. 对什么求值
2. 对求出的值做什么

第二件事便是continuation。

这个定义相当简单。例如：

对于表达式(if (null? x) (quote ()) (cdr x))有六个continuations，分别等待如下值：

1. (if (null? x) (quote ()) (cdr x))的值
2. (null? x)的值
3. null?的值
4. x的值
5. cdr的值
6. x的值

其中，(cdr x)的值没有列出来是因为她就是第一个continuation等待的值。从这里可以看出，continuation是一个计算环境，它在等待一些计算，只有这些计算完成后，才能进行该计算环境相关的计算。也就是说，continuation是一个函数。

Scheme允许用call-with-current-continuation函数（间写为call/cc）对任意表达式的continuation进行捕捉。call/cc必须以一个函数p为参数，而函数p又必须只有一个参数k，这个参数k就是被捕获的continuation，也是一个函数。call/cc构造当前的continuation并传递给p。每当k被应用于一个值，它就返回call/cc的continuation的值，而这个值最终就是应用call/cc的值——或者说是(call/cc p)的值。例如：

(call/cc
  (lambda (k)
    (* 5 4)))

(call/cc
  (lambda (k)
    (* 5 (k 4))))

(+ 2
   (call/cc
     (lambda (k)
       (* 5 (k 4)))))

第一个例子中，call/cc捕获的continuation就是返回一个值，并将其传递给匿名函数。这个匿名函数并没有使用k，因此，其结果为20。第二个例子中的continuation与第一个相同，只不过在匿名函数中将continuation应用于4，因此结果为4。第三个例子中的continuation是对其等待的值进行+2操作，因此，结果为6。

上有个例子：

(define the-continuation #f)
(define (test)
  (let ((i 0))
    ; call/cc calls its first function argument, passing
    ; a continuation variable representing this point in
    ; the program as the argument to that function.
    ;
    ; In this case, the function argument assigns that
    ; continuation to the variable the-continuation.
    ;
    (call/cc (lambda (k) (set! the-continuation k)))
    ;
    ; The next time the-continuation is called, we start here.
    (set! i (+ i 1))
    i))

通过这个例子可以看出，continuation为什么又叫first class continuation——因为它和函数一样，是一等公民。这个例子里面用到的call/cc是call-with-current-continuation的一个别名。

下面再来看两个比较复杂一点的例子。

例1：

(let ([x (call/cc
          (lambda (k) k))])
  (x (lambda (ignore) "hi")))

这个例子中，call/cc将捕获的continuation传递给(lambda (k) k)，然后将该函数结果绑定到x，由于函数(lambda (k) k)返回k，因此，x被绑定为continuation自身。之后，将x的值应用于对表达式(lambda (ignore) "hi")求值的结果（函数f）。由于x是一个continuation，因此，此时continuation变为对表达式(lambda (ignore) "hi")的求值 ，此时continuation变为将该求值的结果应用到该结果自身。同时，因为x所绑定的continuation改变了，因此x所绑定的值也被修改为这个结果（函数f），并应用到f，即(f f)，因此，结果为"hi"。

例2：

(((call/cc
   (lambda (k) k))
  (lambda (x) x))
 "HEY!")

其实这个例子与例1是一样的，只不过写法不一样而已。但这个例子更具有迷惑性，你可能比较容易猜到结果，却不知道怎么得出这个结果的。我的理解也不一定正确，列在这里供大家参考：

call/cc捕获当前的continuation，因为(lambda (k) k)，所以当前的continuation被返回并直接应用于(lambda (x) x)，此时continuation就变为对(lambda (x) x)求值，然后应用到(lambda (x) x)，最后将结果应用到"HEY!"，即((f f) "HEY!")。

下面这个例子就比较有意思了：

(define retry #f)
(define factorial
  (lambda (x)
    (if (= x 0)
        (call/cc
         (lambda (k)
           (set! retry k)
           1))
        (* x (factorial (- x 1))))))

这里保存了continuation到retry中。那么这个continuation是什么样呢？以(factorial 4)为例：

(* 4 (factorial 3))
(* 4 (* 3 (factorial 2)))
(* 4 (* 3 (* 2 (factorial 1))))
(* 4 (* 3 (* 2 (* 1 (factorial 0)))))
(* 4 (* 3 (* 2 (* 1 (call/cc (lambda (k) (set! retry k) 1))))))

因为(lambda (k) (set! retry k) 1)中并没有应用k，因此，这个continuation应当是，返回当前值（此时为1）并乘以4!，或者说，将4!乘到当前值上。扩展到n的情况，则应当为：以参数为基数，做基数×n!操作。因此(factorial 4)然后(retry n)的结果应该是n*4!。

前面提到continuation的应用如协作例程、异常处理、模拟别的编程语言里的return、实现无条件跳转，下面就来看看。

return语句：

(define (f return)
  (return 2)
  3)
(display (f (lambda (x) x))) ; displays 3
(display (call-with-current-continuation f)) ; displays 2

无条件跳转：

(define product
  (lambda (ls)
    (call/cc
      (lambda (break)
        (let f ([ls ls])
          (cond
            [(null? ls) 1]
            [(= (car ls) 0) (break 0)]
            [else (* (car ls) (f (cdr ls)))]))))))

计算过程中碰到第一个0，该函数便会立刻退出，相当于break的功能。

异常处理：可以参考。因为里面涉及到了其他的一些Scheme特性，而我还没有搞懂，因此暂时不做描述。

协作例程（coroutines）：

;;; A naive queue for thread scheduling.
;;; It holds a list of continuations "waiting to run".
(define *queue* '())
(define (empty-queue?)
     (null? *queue*))

(define (enqueue x)
     (set! *queue* (append *queue* (list x))))

(define (dequeue)
     (let ((x (car *queue*)))
       (set! *queue* (cdr *queue*))
       x))

;;; This starts a new thread running (proc).
(define (fork proc)
     (call/cc
      (lambda (k)
        (enqueue k)
        (proc))))

;;; This yields the processor to another thread, if there is one.
(define (yield)
     (call/cc
      (lambda (k)
        (enqueue k)
        ((dequeue)))))

;;; This terminates the current thread, or the entire program
;;; if there are no other threads left.
(define (thread-exit)
     (if (empty-queue?)
         (exit)
         ((dequeue))))

(define (do-stuff-n-print str)
     (lambda ()
       (let loop ((n 0))
         (when (< n 10)
         (display (format "~A ~A\n" str n))
         (yield)
         (loop (+ 1 n))))))

;;; Create two threads, and start them running.
(fork (do-stuff-n-print "This is AAA"))
(fork (do-stuff-n-print "Hello from BBB"))
(thread-exit)

这个例子稍显繁琐，下面会给出一个简化的实现。这里先说明一下这段代码完成何种功能：其中有一个全局变量queue，并定义了enqueue和dequeue函数来向queue中添加或取出一个元素。(fork proc)首先将当前的continuation插入队列，然后执行proc；而yield是首先将当前的continuation添加到队列尾部，然后将队首的continuation取出来并执行。do-stuff-n-print循环打印格式化后的str字串AAA（题外话：这里有个命名的let，名字为loop，其与内嵌的函数定义一样），每循环一次，就对yield进行求值，先保存当前的continuation（即开始下一次循环），然后取出队首的continuation（即对下当前fork之后的表达式求值），然后执行该求值过程。因此，程序执行第二个fork，即先打印BBB，然后取出队首的continuation，即第二次执行打印AAA的loop，然后是yield——保存AAA的执行——执行BBB的第二次loop——……

这个例子可以简化为：

(define lwp-list '())
(define lwp
  (lambda (thunk)
    (set! lwp-list (append lwp-list (list thunk)))))

(define start
  (lambda ()
    (let ([p (car lwp-list)])
      (set! lwp-list (cdr lwp-list))
      (p))))

(define pause
  (lambda ()
    (call/cc
      (lambda (k)
        (lwp (lambda () (k #f)))
        (start)))))

(lwp (lambda () (let f () (pause) (display "h") (f))))
(lwp (lambda () (let f () (pause) (display "e") (f))))
(lwp (lambda () (let f () (pause) (display "y") (f))))
(lwp (lambda () (let f () (pause) (display "!") (f))))
(lwp (lambda () (let f () (pause) (newline) (f))))
(start)

这段程序的执行永远不会自动停止。其中，lwp将函数放入列表尾部，start函数取出列表的第一个元素（函数）并执行它，pause函数捕获一个continuation，在这个continuation的处理函数中，把一个对该continuation求值的函数，通过lwp函数放入列表中，然后对start函数求值。然后分别将含有打印"h"、"e"、"y"、"!"语句的函数放入列表中。此后调用start函数，其过程如下：

1. 取出函数(lambda () (let f () (pause) (display "h") (f)))
2. 将f绑定为不接受参数的函数，该函数依次执行(pause)、(display "h")和(f)——无限循环
3. 执行(pause)，即将含有(display "h")和(f)作为continuation的函数放入列表尾部
4. 执行(start)
5. 取出函数(lambda () (let f () (pause) (display "e") (f)))
6. 将f绑定为不接受参数的函数，该函数依次执行(pause)、(display "e")和(f)——无限循环
7. 执行(pause)，即将含有(display "e")和(f)作为continuation的函数放入列表尾部
8. 执行(start)
9. 取出函数(lambda () (let f () (pause) (display "y") (f)))
10. 将f绑定为不接受参数的函数，该函数依次执行(pause)、(display "y")和(f)——无限循环
11. 执行(pause)，即将含有(display "y")和(f)作为continuation的函数放入列表尾部
12. 执行(start)
13. 取出函数(lambda () (let f () (pause) (display "!") (f)))
14. 将f绑定为不接受参数的函数，该函数依次执行(pause)、(display "!")和(f)——无限循环
15. 执行(pause)，即将含有(display "!")和(f)作为continuation的函数放入列表尾部
16. 执行(start)
17. 取出函数(lambda () (let f () (pause) (newline) (f)))
18. 将f绑定为不接受参数的函数，该函数依次执行(pause)、(newline)和(f)——无限循环
19. 执行(pause)，即将含有(newline)和(f)作为continuation的函数放入列表尾部
20. 执行(start)
21. 取出函数(lambda () (k #f)))
22. 执行k，即输出"h"，调用(f)
23. 执行(pause)，即将含有(display "h")和(f)作为continuation的函数放入列表尾部
24. 执行(start)
25. 取出函数(lambda () (k #f)))
26. 执行k，即输出"e"，调用(f)
27. 执行(pause)，即将含有(display "e")和(f)作为continuation的函数放入列表尾部
28. 执行(start)
29. 取出函数(lambda () (k #f)))
30. 执行k，即输出"y"，调用(f)
31. 执行(pause)，即将含有(display "y")和(f)作为continuation的函数放入列表尾部
32. 执行(start)
33. 取出函数(lambda () (k #f)))
34. 执行k，即输出"!"，调用(f)
35. 执行(pause)，即将含有(display "!")和(f)作为continuation的函数放入列表尾部
36. 取出函数(lambda () (k #f)))
37. 执行k，即输出换行符，调用(f)
38. 执行(pause)，即将含有(newline)和(f)作为continuation的函数放入列表尾部
39. 回到20

最后，留下一个问题供大家讨论吧——我目前不知道怎么来解释这个问题。这就是著名的阴阳谜题：

(let* ((yin
         ((lambda (cc)
            (display #\@) cc)
          (call/cc
           (lambda (c) c))))
       (yang
         ((lambda (cc)
            (display #\*) cc)
          (call/cc
           (lambda (c) c)))))
    (yin yang))

其结果看起来应当是这样：

@*@**@***@****@*****@******@*******@********@*********@**********@***********@************@*************@**************@***************@****************@*****************@******************@*******************@********************@*********************@**********************@***********************@************************@*************************@**************************@***************************@****************************@*****************************@******************************@*******************************@********************************@*********************************@**********************************@***********************************@************************************@*************************************@**************************************@***************************************@****************************************@*****************************************@******************************************@*******************************************@********************************************@*********************************************@*********************

这段程序的执行永远不会自动停止。

PS. 由于我自己并没有太理解continuation，因此，这篇就更像一个信息的翻译和聚合，并没有太多自己的理解在里面。写完这篇，我对于continuation依然还是懵懵懂懂的，更谈不上运用它。也许随着时间的流逝，随着对Scheme的熟悉，会逐渐熟悉continuation吧。

参考

维基百科call/cc