我接过你保存拯救的世界。

穷人的 Goto

先来看一段 Scheme 代码

1
2
3
(define (f c)
  (c 2)
  3)

这是一个接受函数作为参数的函数，结果返回 3 。

1
2
(f (lambda x x))
; => 3

似乎无论接受什么函数，结果都只能返回 3 。真的是这样吗？

1
2
(call/cc f) ;; 接下来就是见证奇迹的时刻
; => 2

如果还是不相信，请移步 biwascheme 亲自测试 。

So, what happens?

魔法发生在 call/cc 上面。

The function call-with-current-continuation, abbreviated call/cc, is a control operator.

Taking a function f as its only argument, call/cc takes the current continuation (i.e., a “snapshot” of the current control context or control state of the program) as an object and applies f to it.

—— 《维基百科》

call/cc 能够将当前后继（Continuation）打包，传给参数。当调用该后继时，call/cc 返回后继接收到的参数。

这么说可能有点抽象，回到开头的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
(call/cc f)
;; call/cc 打包当前后继为 current-continuation
(f current-continuation)
;; 按 Applicative-order 展开
;;(define (f c)
;; (c 2)
;;  3)
((current-continuation 2) 3)
;; 当调用后继时，call/cc 完成，返回值为后继接收到的参数。
;; 程序返回到 (call/cc f)
;; current-continuation 接收到的参数是 2
;; (call/cc f) 执行完成返回 2
2

所以这是一种 goto 吗？

是的，一种超级 goto ，或者说穷人的 goto 。

区别是 call/cc 是一个函数，并不是特定的语法保留字。而且 call/cc 是更通用的控制结构，可以用于实现 generator / enumrator 等控制结构。

迭代器

用 call/cc 定义的迭代器效果如下。

1
2
3
4
5
6
7
(define generate-digit
  (generate-one-element-at-a-time '(0 1 2)))

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

定义为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(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-with-current-continuation
                              (lambda (resume-here)
                                ;; Grab the current continuation
                               (set! control-state resume-here)
                               (return element)))))
     lst)
    (return 'you-fell-off-the-end))

  (define (generator)
    (call-with-current-continuation control-state))

  ;; Return the generator 
  generator)

理解这个例子需要的前置知识有迭代器，Scheme 的语法，Scheme 的 lambda ，Scheme 的 foreach 迭代。在没有理解上述知识时这个例子是非常晦涩难懂的。要讲清楚这些知识需要大量例子，请自行恶补。理解之后就只差临门一脚了。

这个例子需要循序渐进的看

1
2
3
4
5
6
7
8
(define (generate-one-element-at-a-time lst)

  ;; ...
  ;; ...
  ;; ...
  
  ;; Return the generator 
  generator)

generate-one-element-at-a-time 接受一个列表，然后返回 generator 的调用结果。

generator 的定义是

1
2
3
4
5
6
7
8
9
10
11
(define (generate-one-element-at-a-time lst)

  ;; ...
  ;; ...
  ;; ...
  
    (define (generator)
      (call-with-current-continuation control-state))

  ;; Return the generator 
  generator)

generator 是定义在 generate-one-element-at-a-time 的内部函数。Scheme 允许在函数中定义函数。

generator 的定义是 call/cc 一个 control-state 函数。

再看 control-state 函数

1
2
3
4
(define (control-state return)
      (for-each (lambda (...))
                lst)
      (return 'you-fell-off-the-end))

control-state 的定义为对 lst 进行 foreach 操作，也就是对 lst 中每个元素应用 lambda(...) 函数。迭代完成后执行 (return 'you-fell-off-the-end)

这个 lambda 匿名函数是

1
2
3
4
5
6
(define (control-state return)
      (for-each 
       (lambda (element)
                 (set! return (call-with-current-continuation ...))
       lst)
      (return 'you-fell-off-the-end))

(set! return (call-with-current-continuation ...)) 顾名思义，修改 return 的值为 (call-with-current-continuation ...) 的返回值。

把这个 ... 展开

1
2
3
4
5
6
7
8
9
(define (control-state return)
  (for-each 
   (lambda (element)
             (set! return (call-with-current-continuation
                            (lambda (resume-here)
                             (set! control-state resume-here)
                             (return element)))))
   lst)
  (return 'you-fell-off-the-end))

call/cc 中的匿名函数做了两件事。一件是 (set! control-state resume-here) 修改 control-state 的值，另一件是返回 (return element) 的调用结果。

这样整个迭代器就定义完了。接着看调用过程。整个调用过程是这样的

1
2
3
4
(generate-digit) ;; 0
(generate-digit) ;; 1
(generate-digit) ;; 2
(generate-digit) ;; you-fell-off-the-end

一步步来看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
;; 完整定义
;; (define (generate-one-element-at-a-time lst)
;;     (define (control-state return)
;;       (for-each 
;;        (lambda (element)
;;                  (set! return (call-with-current-continuation ;;cc2
;;                                 (lambda (resume-here)
;;                                   ;; Grab the current continuation
;;                                  (set! control-state resume-here)
;;                                  (return element)))))
;;        lst)
;;       (return 'you-fell-off-the-end))
;;   
;;     (define (generator)
;;       (call-with-current-continuation control-state)) ;; cc1;; 
;;
;;   ;; Return the generator 
;;   generator)
(generate-digit) ;; 0
;; 按定义展开
(generate-one-element-at-a-time '(0 1 2))
;; 按定义展开
(generator)
;; 按定义展开
(call-with-current-continuation control-state) ;; cc1
;; 将 cc1 处的后继打包，传给 control-state
(control-state cc1)
;; 按定义展开
(for-each 
       (lambda (element)
                 (set! cc1 (call-with-current-continuation ;;cc2
                                (lambda (resume-here)
                                  ;; Grab the current continuation
                                 (set! control-state resume-here)
                                 (cc1 element)))))
       '(0,1,2))
      (cc1 'you-fell-off-the-end)
;; foreach 第一个元素是 (0,1,2) 中的 0 , 传给 foreach 中的匿名函数
(set! cc1 (call-with-current-continuation ;;cc2
           (lambda (resume-here)
                   ;; Grab the current continuation
                   (set! control-state resume-here)
                   (cc1 0))))
;; 给 cc1 赋值，需要求出后面函数调用的值
(call-with-current-continuation ;;cc2
           (lambda (resume-here)
                   ;; Grab the current continuation
                   (set! control-state resume-here)
                   (cc1 0)))
;; call/cc 调用后面的 lambda 函数， 传递 cc2 处的后继
(lambda (cc2)
        ;; Grab the current continuation
        (set! control-state cc2) ;; 这里修改了 control-state 的定义。
        (cc1 0))
;; 注意到上面在 control-state 函数定义中修改了 control-state 的定义。
(cc1 0)
;; 上面说到调用后继会使得 call/cc 返回。
;; 也就是 cc1 处的 call/cc 返回 0
;; 于是回到 (call-with-current-continuation control-state)
;; 这个 call/cc 返回接收到的参数 0
0
(generate-digit) ;; 1
;; 按定义展开
(generate-one-element-at-a-time '(0 1 2))
;; 按定义展开
(generator)
;; 按定义展开
(call-with-current-continuation control-state) ;; cc1
;; 注意这里的 control-state 已经被改过了。内容为 cc2 处的后继
(cc2 cc1)
;; 回到 cc2 处 (set! cc1 (call-with-current-continuation (lambda (resume-here) ... 
;; cc2 处的 call/cc 返回接收到的参数 cc1
(for-each (set cc1 cc1) ....)
;; 把上一个 cc1 改成新的 cc1
;; for-each 一轮迭代完成，进入下一轮迭代
(lambda (1)
        (set! cc1 (call-with-current-continuation ;;cc2
                   (lambda (resume-here)
                           ;; Grab the current continuation
                           (set! control-state resume-here)
                           (cc1 1)))))
;; (0,1,2) 0 的下一个元素是 1 。 所以 lambda 接受到的元素是 1
;; 执行过程与上面类似。
(lambda (resume-here)
        ;; Grab the current continuation
        (set! control-state resume-here)
        (cc1 1))
;; 执行到 (cc1 1) 。回到 cc1 处的 call/cc
;; 于是回到 (call-with-current-continuation control-state)
;; 这个 call/cc 返回接收到的参数 1
1
(generate-digit) ;; 2
;; 过程类似
(generate-digit) ;; you-fell-off-the-end
;; 回到 for-each
;; for-each 执行完成后执行下一步
;; (cc1 'you-fell-off-the-end)
you-fell-off-the-end

过程还是蛮简单的嘛。可以理解为两个 goto 跳来跳去。

最后

讲了 CPS ，讲了 call/cc ，下一篇文章的内容已经浮出水面。