3.3 Continuations(延续)

对每一个 Scheme 表达式进行求值时，Scheme 实现必须对两件事保持跟踪：(1)求值的对象;(2)如何处理结果。思考下面的表达式中(null? x)的求值

(if (null? x) (quote ()) (cdr x))

Scheme 实现首先对(null? x)进行求值，然后以该结果为基础，再来决定对(quote ())或者(cdr x)进行求值。在这里，“求值的对象”是(null? x)，“怎么处理结果”就是决定对(quote ())和(cdr x)两者的其中之一进行求值。我们把"如何处理结果"称之作计算的延续(continuations).

因此，求值任何表达式的任何一个点上，都有一个延续存在，接下来要么完成计算，要么继续计算。我们假设x的值是(a b c)，在求值(if (null? x) (quote ()) (cdr x))的过程中，我们可以分解出6个延续，它们正在等待下面的值：

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

(cdr x)的延续并没有列出来，因为它与正在等待(if (null? x) (quote ()) (cdr x))的延续是同一个。

Scheme 允许使用函数（过程） call/cc（call-with-current-continuation）来捕获任意表达式的延续。call/cc有一个参数p，p必须是一个函数。call/cc将当前延续构造为一个对象实体，然传递给p。而延续本身表现为一个函数k。每当k应用到某个值上，它就将该值返回到call/cc当初捕获延续的地方。[译注]行为表现上就是乘着时光机器回到了过去，在那里有一个延续等待某个值进行下一步计算，然而它得到的值是你传递给k的值，而不是原本应该得到的值。大约可以这样理解：call/cc相当于调试程序时，在某个地方下个断点，执行到该点时，你人为干预程序的执行修改了某个变量的值，接下来的结果就不一样了。

如果p在不调用k的情况下返回，则该过程（函数）返回的值将成为应用call/cc的值。

思考下面简单的例子：

(call/cc
  (lambda (k)
    (* 5 4))) => 20

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

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

在第一例子中，延续被捕获，并且绑定到k，然而k从未被使用，所以，(* 5 4)就是整个表达式的值；第二个例子中，延续在乘法运算之前就被调用了，所以结果就是传递给k的参数 4；最后一个例子中，延续等待某个值来加上2,它得到的值是4((k 4)), 所以结果就是 6，乘法运算没有机会执行。

下面是一个稍微复杂一些的例子，展示了使用call/cc从递归中非本地退出

(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)))]))))))

(product '(1 2 3 4 5)) => 120
(product '(7 3 8 0 1 9 5)) => 0

product函数的作用是将一个列表中所有的数相乘，当递归过程中遇到 0 时，剩下的运算就没有必要再进行下去了，因为结果总是 0. [译注]Scheme 没有专门的循环结构，不象其它语言一样可以使用 break 从循环中跳出，Scheme 实现迭代算法的唯一方式就是递归，call/cc提供了一种从递归中直接跳出的途径。如果没有 call/cc，程序将不得不傻傻地等待列表被遍历一遍。所以 call/cc是挺重要的。

Each of the continuation invocations above returns to the continuation，而控制权依然保留在传递给call/cc的匿名函数中。下面的例子则是在函数已经返回后再来使用延续。

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

这种调用call/cc所捕获的延续的方法可以描述为“取值，绑定到x，并将x的值应用于(lambda (ignore) "hi")的值。由于(lambda (k) k)只是简单地返回其参数，所以x被绑定到延续本身；该延续被应用到(lambda (ignore) "hi")所产生的匿名函数上。其效果是x再一次被绑定到该匿名函数，并且将该匿名函数作为参数传递给自己。该匿名函数忽略其参数并返回"hi"。

下面的例子是上面例子的一个变体，就其体量来说它可能是最令人困惑的 Scheme 程序；你可能很容易猜到它将返回什么，但是确实需要一些思考才能弄清楚为什么会这样

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

和前面的例子一样call/cc的返回值是它自己的延续，延续将被应用到匿名函数(lambda (x) x)上面，所以，call/ccreturns a second time with this value. 然后匿名函数(lambda (x) x)被应用到它自身，产生了另外一个一模一样的匿名函数，最后，该匿名函数再次被应用到参数"HEY!"，最后的结果就是"HEY!".

以这种方式应用call/cc并不总是令人困惑的。思考下面的阶乘函数factorial，factorial在递归的”基本情况“分支里，在返回 1 之前将延续保存在另一个顶级（全局）变量 retry里。

(define retry #f)

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

这个阶乘函数和预期的阶乘函数一样工作正常，除了它具有对retry进行赋值的副作用。

(factorial 4) => 24
(retry 1) => 24
(retry 2) => 48

绑定到 retry 的延续可以描述为：将值乘以1,再乘以2, 再乘以3,最后乘以4。如果我们传递给延续不同的值，即不是1的值，我们们改变最终的结果。

(retry 2) => 48
(retry 5) => 120

这种机制是用call/cc实现断点的基础，每次遇到断点时都保存断点的延续，以便可以从断点处重新启动计算（如果需要可以多次重启）。

延续可以用来实现各种形式的多任务。下面定义了一个简单的“轻量级多线程”机制，允许多个计算交错进行。由于它是非抢占式的，所以它要求每个线程自愿“暂停”，以便其它线程能够运行。

(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)))))

下面，轻量级线程将合作打印出无限的"hey!"行

(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) => hey!
           hey!
           hey!
           hey!
           ......

有关通过 call/cc 实现抢占式多线程引擎的细节，请参见12.11节.

练习 3.3.1 Use call/cc to write a program that loops indefinitely, printing a sequence of numbers beginning at zero. Do not use any recursive procedures, and do not use any assignments.

练习 3.3.2 Rewrite product without call/cc, retaining the feature that no multiplications are performed if any of the list elements are zero.

练习 3.3.3 What would happen if a process created by lwp as defined above were to terminate, i.e., simply return without calling pause? Define a quit procedure that allows a process to terminate without otherwise affecting the lwp system. Be sure to handle the case in which the only remaining process terminates.

练习 3.3.4 Each time lwp is called, the list of processes is copied because lwp uses append to add its argument to the end of the process list. Modify the original lwp code to use the queue data type developed in Section 2.9 to avoid this problem.

练习 3.3.5 The light-weight process mechanism allows new processes to be created dynamically, although the example given in this section does not do so. Design an application that requires new processes to be created dynamically and implement it using the light-weight process mechanism.