第 20 章 續(xù)延(continuation)

第 20 章 續(xù)延(continuation)

續(xù)延是在運(yùn)行中被暫停了的程序：即含有計(jì)算狀態(tài)的單個(gè)函數(shù)型對(duì)象。當(dāng)這個(gè)對(duì)象被求值時(shí)，就會(huì)在它上次停下來(lái)的地方重新啟動(dòng)之前保存下來(lái)的計(jì)算。對(duì)于求解特定類型的問題，能夠保存程序的狀態(tài)并在之后重啟是非常有用的。例如在多進(jìn)程中，續(xù)延可以很方便地表示掛起的進(jìn)程。而在非確定性的搜索問題里，續(xù)延可以用來(lái)表示搜索樹中的節(jié)點(diǎn)。

要一下子理解續(xù)延或許會(huì)有些困難。本章分兩步來(lái)探討這個(gè)主題。本章的第一部分會(huì)先分析續(xù)延在 Scheme 中的應(yīng)用，這門語(yǔ)言內(nèi)置了對(duì)續(xù)延的支持。一旦說(shuō)清楚了續(xù)延的行為，第二部分將展示如何使用宏在 Common Lisp 程序里實(shí)現(xiàn)續(xù)延。第 21-24 章都將用到這里定義的宏。

20.1 Scheme 續(xù)延

Scheme 和 Common Lisp 在幾個(gè)主要方面存在著不同，其中之一就是：前者擁有顯式的續(xù)延支持。本節(jié)展示的是續(xù)延在Scheme 中的工作方式。([示例代碼 20.1] 列出了 Scheme 和 Common Lisp 間一些其他的區(qū)別。)

續(xù)延是一個(gè)代表著計(jì)算的將來(lái)的函數(shù)。不管是哪一個(gè)表達(dá)式被求值，總會(huì)有誰(shuí)在翹首以待它將要返回的值。例如，在

(/ (- x 1) 2)

中，當(dāng)求值 (- x 1) 時(shí)，外面的 / 表達(dá)式就在等著這個(gè)值，同時(shí)，還有另外一個(gè)式子也在等著它的值，依此類推下去，最后總是回到 toplevel 上 print 正等在那里。

無(wú)論何時(shí)，我們都可以把續(xù)延視為帶一個(gè)參數(shù)的函數(shù)。如果上面的表達(dá)式被輸入到 toplevel，那么當(dāng)子表達(dá)式 (- x 1) 被求值時(shí)，續(xù)延將是：

(lambda (val) (/ val 2))

也就是說(shuō)，接下來(lái)的計(jì)算可以通過(guò)在返回值上調(diào)用這個(gè)函數(shù)來(lái)重現(xiàn)。如果該表達(dá)式在下面的上下文中出現(xiàn)

(define (f1 w)
  (let ((y (f2 w)))
    (if (integer? y) (list 'a y) 'b)))

(define (f2 x)
  (/ (- x 1) 2))

并且 f1 在toplevel 下被調(diào)用，那么當(dāng) (- x 1) 被求值時(shí)，續(xù)延將等價(jià)于

(lambda (val)
  (let ((y (/ val 2)))
    (if (integer? y) (list 'a y) 'b)))

在 Scheme 中，續(xù)延和函數(shù)同樣是第一類對(duì)象。你可以要求 Scheme 返回當(dāng)前的續(xù)延，然后它將為你生成一個(gè)只有單個(gè)參數(shù)的函數(shù)，以表示未來(lái)的計(jì)算。你可以任意長(zhǎng)時(shí)間地保存這個(gè)對(duì)象，然后在你調(diào)用它時(shí)，它將重啟當(dāng)它被創(chuàng)建時(shí)所發(fā)生的計(jì)算。

1. 在 Common Lisp 眼中，一個(gè)符號(hào)的 symbol-value 和 symbol-function 是不一樣的，而 Scheme 對(duì)兩者不作區(qū)分。在 Scheme 里面，變量只有唯一對(duì)應(yīng)的值，它可以是個(gè)函數(shù)，也可以是另一種對(duì)象。因此，在 Scheme 中就不需要 #' 或者 funcall 了。Common Lisp 的：

   (let ((f #'(lambda (x) (1+ x)))) (funcall f 2))

在 Scheme 中將變成：

(let ((f (lambda (x) (1+ x))))
  (f 2))

1. 由于 Scheme 只有一個(gè)名字空間，因而它沒有必要為各個(gè)名字空間專門設(shè)置對(duì)應(yīng)的賦值操作符(例如 defun 和 setq )。取而代之，它使用 define ，define 的作用和 defvar 大致相當(dāng)，同時(shí)用 set! 替代了 setq 。在用 set! 為全局變量賦值前，必須先用 define 創(chuàng)建這個(gè)變量。

2. 在 Scheme 中，通常用 define 定義有名函數(shù)，它行使著 defun 和 defvar 在 Common Lisp 中的功能。Common Lisp 的：

   (defun foo (x) (1+ x))

有兩種可能的 Scheme 翻譯：

(define foo (lambda (x) (1+ x)))
(define (foo x) (1+ x))

1. 在 Common Lisp 中，函數(shù)的參數(shù)按從左到右的順序求值。而在 Scheme 中，有意地不對(duì)求值順序加以規(guī)定。(并且語(yǔ)言的實(shí)現(xiàn)者對(duì)于忘記這點(diǎn)的人幸災(zāi)樂禍。)

2. Scheme 不用 t 和 nil ，相應(yīng)的，它有 #t 和 #f ?？樟斜?，()，在某些實(shí)現(xiàn)里為真，而在另一些實(shí)現(xiàn)里為假。

3. cond 和 case 表達(dá)式里的默認(rèn)子句在 Scheme 中帶有 else 關(guān)鍵字，而不是 Common Lisp 中的 t 。

4. 某些內(nèi)置操作符的名字被改掉了：consp 成了 pair? ，而 null 則是 null? ，mapcar (幾乎) 是 map ，等等。通常根據(jù)上下文，應(yīng)該能看出這些操作符的意思。

[示例代碼 20.1]： Scheme 和 Common Lisp 之間的一些區(qū)別

續(xù)延可以理解成是一種廣義的閉包。閉包就是一個(gè)函數(shù)加上一些指向閉包創(chuàng)建時(shí)可見的詞法變量的指針。續(xù)延則是一個(gè)函數(shù)加上一個(gè)指向其創(chuàng)建時(shí)所在的整個(gè)棧的指針。當(dāng)續(xù)延被求值時(shí)，它返回的是使用自己的棧拷貝算出的結(jié)果，而沒有用當(dāng)前棧。如果某個(gè)續(xù)延是在 T1 時(shí)刻創(chuàng)建的，而在 T2 時(shí)刻被求值，那么它求值時(shí)使用的將是 T1 時(shí)刻的棧。

Scheme 程序通過(guò)內(nèi)置操作符 call-with-current-continuation (縮寫為 call/cc) 來(lái)訪問當(dāng)前續(xù)延。當(dāng)一個(gè)程序在一個(gè)單個(gè)參數(shù)的函數(shù)上調(diào)用 call/cc 時(shí)：

(call-with-current-continuation
  (lambda (cc)
    ...))

這個(gè)函數(shù)將被傳進(jìn)另一個(gè)代表當(dāng)前續(xù)延的函數(shù)。通過(guò)將 cc 的值存放在某個(gè)地方，我們就可以保存在 call/cc 那一點(diǎn)上的計(jì)算狀態(tài)。

在這個(gè)例子里，我們 append 出一個(gè)列表，列表的最后一個(gè)元素是一個(gè) call/cc 表達(dá)式的返回值：

> (define frozen)
FROZEN
> (append '(the call/cc returned)
  (list (call-with-current-continuation
      (lambda (cc)
        (set! frozen cc)
        'a))))
(THE CALL/CC RETURNED A)

這個(gè) call/cc 返回了 a ，但它首先將續(xù)延保存在了全局變量 frozen 中。

調(diào)用 frozen 會(huì)導(dǎo)致在 call/cc 那一點(diǎn)上的舊的計(jì)算重新開始。無(wú)論我們傳給 frozen 什么值，這個(gè)值都將作為 call/cc 的值返回：

> (frozen 'again)
(THE CALL/CC RETURNED AGAIN)

續(xù)延不會(huì)因?yàn)楸磺笾刀猛辍Ｋ鼈兛梢员恢貜?fù)調(diào)用，就像任何其他的函數(shù)型對(duì)象一樣：

> (frozen 'thrice)
(THE CALL/CC RETURNED THRICE)

當(dāng)我們?cè)谀承┢渌挠?jì)算里調(diào)用一個(gè)續(xù)延時(shí)，我們可以更清楚地看到所謂返回到原先的棧上是什么意思：

> (+ 1 (frozen 'safely))
(THE CALL/CC RETURNED SAFELY)

這里，緊接著的 + 當(dāng) frozen 調(diào)用時(shí)被忽略掉了。后者返回到了它首次被創(chuàng)建時(shí)的棧上：先經(jīng)過(guò) list ，然后是 append ，直到 toplevel。如果 frozen 像正常函數(shù)調(diào)用那樣返回了一個(gè)值，那么上面的表達(dá)式將在試圖給一個(gè)列表加 1 時(shí)產(chǎn)生一個(gè)錯(cuò)誤。

各續(xù)延并不會(huì)每人都分到自己的一份棧的拷貝。它們可能跟其他續(xù)延或者當(dāng)前正在進(jìn)行的計(jì)算共享一些變量。在下面這個(gè)例子里，兩個(gè)續(xù)延共享了同一個(gè)棧：

> (define froz1)
FROZ1
> (define froz2)
FROZ2
> (let ((x 0))
  (call-with-current-continuation
    (lambda (cc)
      (set! froz1 cc)
      (set! froz2 cc)))
  (set! x (1+ x))
  x)
1

因此調(diào)用任何一個(gè)都將返回后繼的整數(shù)：

> (froz2 ())
2
> (froz1 ())
3

由于 call/cc 表達(dá)式的值將被丟棄，所以無(wú)論我們給 froz1 和 froz2 什么參數(shù)都無(wú)關(guān)緊要。

現(xiàn)在能保存計(jì)算的狀態(tài)了，我們可以用它做什么呢？第 21-24 章致力于使用續(xù)延的應(yīng)用。這里將要考察一個(gè)比較簡(jiǎn)單的例子，它能夠體現(xiàn)出使用保存狀態(tài)編程的特色：假設(shè)有一組樹，我們想從每棵樹都取出一個(gè)元 素，組成一個(gè)列表，直到獲得一個(gè)滿足某種條件的組合。

樹可以用嵌套列表來(lái)表示。第 5.6 節(jié)上描述了一種將一類樹表示成列表的方法。這里我們采用另一種方法，允許內(nèi)部節(jié)點(diǎn)帶有(原子的) 值，以及任意數(shù)量的孩子。在這種表示方法里，內(nèi)部節(jié)點(diǎn)變成了一個(gè)列表；其 car 包含保存在這個(gè)節(jié)點(diǎn)上的值，其 cdr 包含該節(jié)點(diǎn)孩子的表示。例如，[示例代碼 20.2] 里顯示的兩棵樹可以被表示成：

(define t1 '(a (b (d h)) (c e (f i) g)))
(define t2 '(1 (2 (3 6 7) 4 5)))

a 1

b c 2

d e f g 3 4 5

h i 6 7

(a) t1 (b) t2

[示例代碼 20.2]： 兩棵樹

[示例代碼 20.3]： 用續(xù)延來(lái)遍歷樹

(define (dft tree)
  (cond ((null? tree) ())
    ((not (pair? tree)) (write tree))
    (else (dft (car tree))
      (dft (cdr tree)))))

(define *saved* ())

(define (dft-node tree)
  (cond ((null? tree) (restart))
    ((not (pair? tree)) tree)
    (else (call-with-current-continuation
        (lambda (cc)
          (set! *saved*
            (cons (lambda ()
                (cc (dft-node (cdr tree))))
              *saved*))
          (dft-node (car tree)))))))

(define (restart)
  (if (null? *saved*)
    'done
    (let ((cont (car *saved*)))
      (set! *saved* (cdr *saved*))
      (cont))))

(define (dft2 tree)
  (set! *saved* ())
  (let ((node (dft-node tree)))
    (cond ((eq? node 'done) ())
      (else (write node)
        (restart)))))

[示例代碼 20.3] 中的函數(shù)能在這樣的樹上做深度優(yōu)先搜索。在實(shí)際的程序里，我們可能想要在遇到節(jié)點(diǎn)時(shí)用它們做一些事。這里只是打印它們。為了便于比較，這里給出的函數(shù) dft 實(shí)現(xiàn)了通常的深度優(yōu)先遍歷：

> (dft t1)
ABDHCEFIG()

函數(shù) dft-node 按照同樣的路徑遍歷這棵樹，但每次只處理一個(gè)節(jié)點(diǎn)。當(dāng) dft-node 到達(dá)一個(gè)節(jié)點(diǎn)時(shí)，它跟著節(jié)點(diǎn)的 car 走，并且在 saved 里壓入一個(gè)續(xù)延來(lái)瀏覽其 cdr 部分。

> (dft-node t1)
A

調(diào)用 restart 可以繼續(xù)遍歷，作法是彈出最近保存的續(xù)延并調(diào)用它。

> (restart)
B

最后，所有之前保存的狀態(tài)都用完了，restart 通過(guò)返回 done 來(lái)通告這一事實(shí)：

.
.
.
> (restart)
G
> (restart)
DONE

最后，函數(shù) dft2 把我們剛剛手工完成的工作干凈漂亮地一筆帶過(guò)：

> (dft2 t1)
ABDHCEFIG()

注意到在dft2 的定義里沒有顯式的遞歸或迭代：后繼的節(jié)點(diǎn)被打印出來(lái)，是因?yàn)橛?restart 引入的續(xù)延總是返回到 dft-node 中同樣的 cond 子句那里。

這種程序的工作方式就跟采礦差不多。它先調(diào)用 dft-node 初步挖出一個(gè)礦坑。一旦返回值不是 done ，dft-node 后面的代碼將調(diào)用 restart 將控制權(quán)發(fā)回到棧上。這個(gè)過(guò)程會(huì)一直持續(xù)，直到到返回值表明礦被采空。這時(shí)，dft2 將不再打印返回值，而是返回 #f 。使用續(xù)延的搜索方式帶來(lái)了一種編寫程序的新思路：將合適的代碼放在棧上，然后不斷地返回到那里來(lái)獲得結(jié)果。

如果我們只是想同時(shí)遍歷一棵樹，就像 dft2 里那樣，那么實(shí)在沒有必要使用這種技術(shù)。dft-node 的優(yōu)勢(shì)在于，可以同時(shí)運(yùn)行它的多個(gè)實(shí)例。假設(shè)有兩棵樹，并且我們想要以深度優(yōu)先的順序生成其中元素的叉積。

> (set! *saved* ())
()
> (let ((node1 (dft-node t1)))
  (if (eq? node1 'done)
    'done
    (list node1 (dft-node t2))))
(A 1)
> (restart)
(A 2)
.
.
.
> (restart)
(B 1)
.
.
.

借助常規(guī)技術(shù)，我們必須采取顯式的措施來(lái)保存我們?cè)趦煽脴渲械奈恢谩６ㄟ^(guò)續(xù)延，則能非常自然地維護(hù)兩個(gè)正在進(jìn)行的遍歷操作的狀態(tài)。對(duì)于諸如本例的簡(jiǎn)單情形，要保存我們?cè)跇渲械奈恢眠€不算太難。樹是持久性的數(shù)據(jù)結(jié)構(gòu)，所以我們至少有辦法找到 "我們?cè)跇渲械奈恢?。續(xù)延的過(guò)人之處在于，即使沒有持久性的數(shù)據(jù)結(jié)構(gòu)與之關(guān)聯(lián)，它同樣可以在任何的計(jì)算過(guò)程中輕松保存我們的位置。這一計(jì)算甚至也不需要具有有限數(shù)量的狀態(tài)，只要重啟它們有限次就行了。

正如第24 章將要展示的，這兩種考慮被證實(shí)在 Prolog 的實(shí)現(xiàn)中至關(guān)重要。在 Prolog 程序里，"搜索樹" 并非真正的數(shù)據(jù)結(jié)構(gòu)，而只是程序生成結(jié)果的一種隱式方式。而且這些樹經(jīng)常是無(wú)窮大的，這種情況下，我們不能指望在搜索下一棵樹之前把整棵樹都搜完，所以只得想個(gè)辦法保存我們的位置，除此之外別無(wú)選擇。

20.2 續(xù)延傳遞宏

雖然 Common Lisp 沒有提供 call/cc ，但是再加把勁，我們就可以像在 Scheme 里那樣做到同樣的事情了。

本節(jié)展示如何用宏在 Common Lisp 程序中構(gòu)造續(xù)延。Scheme 的續(xù)延給了我們兩樣?xùn)|西：

1. 續(xù)延被創(chuàng)建時(shí)所有變量的綁定。

2. 計(jì)算的狀態(tài) 從那時(shí)起將要發(fā)生什么。

在一個(gè)詞法作用域的 Lisp 里，閉包給了我們前者。可以看出我們也能使用閉包來(lái)獲得后者，辦法是把計(jì)算的狀態(tài)同樣也保存在變量綁定里。

[示例代碼 20.4] 續(xù)延傳遞宏

(defvar *actual-cont* #'values)

(define-symbol-macro \*cont\*
  *actual-cont*)

(defmacro =lambda (parms &body body)
  '#'(lambda (\*cont\* ,@parms) ,@body))

(defmacro =defun (name parms &body body)
  (let ((f (intern (concatenate 'string
            "=" (symbol-name name)))))
    '(progn
      (defmacro ,name ,parms
        '(,',f \*cont\* ,,@parms))
      (defun ,f (\*cont\* ,@parms) ,@body))))

(defmacro =bind (parms expr &body body)
  '(let ((\*cont\* #'(lambda ,parms ,@body))) ,expr))

(defmacro =values (&rest retvals)
  '(funcall \*cont\* ,@retvals))

(defmacro =funcall (fn &rest args)
  '(funcall ,fn \*cont\* ,@args))

(defmacro =apply (fn &rest args)
  '(apply ,fn \*cont\* ,@args))

[示例代碼 20.4] 給出的宏讓我們能在保留續(xù)延的情況下，進(jìn)行函數(shù)調(diào)用。這些宏取代了幾個(gè)內(nèi)置的 Common Lisp form，它們被用來(lái)定義函數(shù)，進(jìn)行函數(shù)調(diào)用，以及返回函數(shù)值。

如果有函數(shù)需要使用續(xù)延，或者這個(gè)函數(shù)所調(diào)用的函數(shù)要用到續(xù)延，那么該函數(shù)就該用=defun 而不是 defun 定義。=defun 的語(yǔ)法和 defun 相同，但其效果有些微妙的差別。=defun 定義的并不是單單一個(gè)函數(shù)，它實(shí)際上定義了一個(gè)函數(shù)和一個(gè)宏，這個(gè)宏會(huì)展開成對(duì)該函數(shù)的調(diào)用。(宏定義必須在先，原因是被定義的函數(shù)有可能會(huì)調(diào)用自己。) 函數(shù)的主體就是傳給=defun 的那個(gè)，但還另有一個(gè)形參，即 cont ，它被連接在原有的形參列表上。在宏展開式里，cont 會(huì)和其他參數(shù)一同傳給這個(gè)函數(shù)。所以

(=defun add1 (x) (=values (1+ x)))

宏展開成

(progn (defmacro add1 (x)
    '(=add1 \*cont\* ,x))
  (defun =add1 (\*cont\* x)
    (=values (1+ x))))

當(dāng)調(diào)用add1 時(shí)，實(shí)際被調(diào)用的不是函數(shù)而是個(gè)宏。這個(gè)宏會(huì)展開成一個(gè)函數(shù)調(diào)用，但是另外帶了一個(gè)參數(shù)：cont。所以，在調(diào)用 =defun 定義的操作符的時(shí)候，cont 的當(dāng)前值總是被默默地傳遞著。

那 cont 有什么用呢？它將被綁定到當(dāng)前的續(xù)延。=values 的定義顯示了這個(gè)續(xù)延的用場(chǎng)。只要是用 =defun 定義的函數(shù)，都必須通過(guò) =values 來(lái)返回值，或者調(diào)用另一個(gè)使用 =values 的函數(shù)。=values 的語(yǔ)法與 Common Lisp 的values 相同。如果有個(gè)帶有相同數(shù)量參數(shù)的 =bind 等著它的話，它可以返回多值， 但它不能返回多值到 toplevel。

參數(shù) cont 告訴那個(gè)由 =defun 定義的函數(shù)對(duì)其返回值做什么。當(dāng) =values 被宏展開時(shí)，它將捕捉 cont ，并用它模擬從函數(shù)返回值的過(guò)程。表達(dá)式

(=values (1+ n))

會(huì)展開成

(funcall \*cont\* (1+ n))

在 toplevel 下，cont 的值是 #'values，這就相當(dāng)于一個(gè)真正的 values 多值返回。當(dāng)我們?cè)?toplevel 下調(diào)用 (add1 2) 時(shí)，這個(gè)調(diào)用的宏展開式與下式等價(jià)

(funcall #'(lambda (\*cont\* n) (=values (1+ n))) \*cont\* 2)

cont 的引用在這種情況下將得到全局綁定。因而，=values 表達(dá)式在宏展開后將等價(jià)于下式

(funcall #'values (1+ n))

即把在 n 上加 1，并返回結(jié)果。

在類似 add1 的函數(shù)里，我們克服了重重困難，不過(guò)是為了模擬 Lisp 進(jìn)行函數(shù)調(diào)用和返回值的過(guò)程：

> (=defun bar (x)
  (=values (list 'a (add1 x))))
BAR
> (bar 5)
(A 6)

關(guān)鍵在于，現(xiàn)在有了 "函數(shù)調(diào)用" 和 "函數(shù)返回" 可供差遣，而且如果愿意的話，我們還可以把它們用在其他地方。

我們之所以能獲得續(xù)延的效果，要?dú)w功于對(duì) cont 的操控。雖然 cont 的值是全局的，但這個(gè)全局變量很少用到：cont 幾乎總是一個(gè)形參，它被 =values 以及用 =defun 定義的宏所捕捉。例如在 add1 的函數(shù)體里，cont 就是一個(gè)形參而非全局變量。這個(gè)區(qū)別是很重要的，因?yàn)槿绻?cont 不是一個(gè)局部變量的話這些宏將無(wú)法工作。 [示例代碼 20.4] 中的第三個(gè)宏，=bind ，其用法和 multiple-value-bind 相同。它接受一個(gè)參數(shù)列表，一個(gè)表達(dá)式，以及一個(gè)代碼體：參數(shù)將被綁定到表達(dá)式返回的值上，而代碼體在這些綁定下被求值。倘若一個(gè)由 =defun 定義的函數(shù)，在被調(diào)用之后，需要對(duì)另一個(gè)表達(dá)式進(jìn)行求值，那么就應(yīng)該使用=bind 宏。

> (=defun message ()
  (=values 'hello 'there))
MESSAGE

> (=defun baz ()
  (=bind (m n) (message)
    (=values (list m n))))
BAZ
> (baz)
(HELLO THERE)

注意到 =bind 的展開式會(huì)創(chuàng)建一個(gè)稱為 cont 的新變量。baz 的主體展開成：

(let ((\*cont\* #'(lambda (m n)
        (=values (list m n)))))
  (message))

然后會(huì)變成：

(let ((\*cont\* #'(lambda (m n)
        (funcall \*cont\* (list m n)))))
  (=message \*cont\*))

由于 cont 的新值是 =bind 表達(dá)式的代碼體，所以當(dāng) message 通過(guò)函數(shù)調(diào)用 cont 來(lái) "返回" 時(shí)，結(jié)果將是去求值這個(gè)代碼體。盡管如此(并且這里是關(guān)鍵)，在=bind 的主體里：

#'(lambda (m n)
  (funcall \*cont\* (list m n)))

作為參數(shù)傳遞給=baz 的cont 仍然是可見的，所以當(dāng)代碼的主體求值到一個(gè)=values 時(shí)，它將能夠返回到最初的主調(diào)函數(shù)那里。所有閉包環(huán)環(huán)相扣：每個(gè)cont 的綁定都包含了上一個(gè)cont 綁定的閉包，它們串成一條鎖鏈，鎖鏈的盡頭指向那個(gè)全局的值。

在這里，我們也可以觀察到更小規(guī)模的同樣現(xiàn)象：

> (let ((f #'values))
  (let ((g #'(lambda (x) (funcall f (list 'a x)))))
    #'(lambda (x) (funcall g (list 'b x)))))
#<Interpreted-Function BF6326>
> (funcall * 2)
(A (B 2))

本例創(chuàng)建了一個(gè)函數(shù)，它是含有指向g 的引用的閉包，而g 本身也是一個(gè)含有到f 的引用的閉包。第 6.3 節(jié)上的網(wǎng)絡(luò)編譯器中曾構(gòu)造過(guò)類似的閉包鏈。

剩下兩個(gè)宏，分別是=apply 和=funcall ，它們適用于由=lambda 定義的函數(shù)。注意那些用=defun 定義出來(lái)的"函數(shù)"，因?yàn)樗鼈兊恼鎸?shí)身份是宏，所以不能作為參數(shù)傳給apply 或funcall。解決這個(gè)問題的方法類似于第 8.2 節(jié)上提到的技巧。也就是把調(diào)用包裝在另一個(gè)=lambda 里面：

> (=defun add1 (x)
  (=values (1+ x)))
ADD1
> (let ((fn (=lambda (n) (add1 n))))
  (=bind (y) (=funcall fn 9)
    (format nil "9 + 1 = ~A" y)))
"9 + 1 = 10"

[示例代碼 20.5] 總結(jié)了所有因續(xù)延傳遞宏而引入的限制。如果有函數(shù)既不保存續(xù)延，也不調(diào)用其他保存續(xù)延的函數(shù)，那它就沒有必要使用這些特殊的宏。比如像list 這樣的內(nèi)置函數(shù)就沒有這個(gè)需要。

[示例代碼 20.6] 中把來(lái)自[示例代碼 20.3] 的代碼? 從Scheme 翻譯成了Common Lisp，并且用續(xù)延傳遞宏代替了Scheme 續(xù)延。以同一棵樹為例，dft2 和之前一樣工作正常：

?譯者注：這段代碼與原書有一些出入：首先 (setq?saved?nil) 被改為 (defvar?saved?nil)；其次將restart 改為re-start 以避免和Common Lisp 已有的符號(hào)沖突，并且將re-start 的定義放在dft-node 的定義之前以確保后者在編譯時(shí)可以找到re-start 的定義。

1. 一個(gè)用=defun 定義的函數(shù)的參數(shù)列表必須完全由參數(shù)名組成。

2. 使用續(xù)延，或者調(diào)用其他做這件事的函數(shù)的函數(shù)，必須用=lambda 或=defun 來(lái)定義。

3. 這些函數(shù)必須終結(jié)于用=values 來(lái)返回值，或者調(diào)用其他遵守該約束的函數(shù)。

4. 如果一個(gè)=bind ，=values ，或者=funcall 表達(dá)式出現(xiàn)在一段代碼里，它必須是一個(gè)尾調(diào)用。任何在=bind 之后求值的代碼必須放在其代碼體里。所以如果我們想要依次有幾個(gè)=bind ，它們必須被嵌套：

[示例代碼 20.5] 續(xù)延傳遞宏的限制

(=defun foo (x)
  (=bind (y) (bar x)
    (format t "Ho ")
    (=bind (z) (baz x)
      (format t "Hum.")
      (=values x y z))))

[示例代碼 20.6] 使用續(xù)延傳遞宏的樹遍歷

(defun dft (tree)
  (cond ((null tree) nil)
    ((atom tree) (princ tree))
    (t (dft (car tree))
      (dft (cdr tree)))))

(defvar *saved* nil)

(=defun re-start ()
  (if *saved*
    (funcall (pop *saved*))
    (=values 'done)))

(=defun dft-node (tree)
  (cond ((null tree) (re-start))
    ((atom tree) (=values tree))
    (t (push #'(lambda () (dft-node (cdr tree)))
        *saved*)
      (dft-node (car tree)))))

(=defun dft2 (tree)
  (setq *saved* nil)
  (=bind (node) (dft-node tree)
    (cond ((eq node 'done) (=values nil))
      (t (princ node)
        (re-start)))))

> (setq t1 '(a (b (d h)) (c e (f i) g))
  t2 '(1 (2 (3 6 7) 4 5)))
(1 (2 (3 6 7) 4 5))
> (dft2 t1)
ABDHCEFIG
NIL

和 Scheme 里一樣，我們?nèi)匀豢梢员４娑嗦繁闅v的狀態(tài)，盡管這個(gè)例子會(huì)顯得有些冗長(zhǎng)：

> (=bind (node1) (dft-node t1)
  (if (eq node1 'done)
    'done
    (=bind (node2) (dft-node t2)
      (list node1 node2))))
(A 1)
> (re-start)
(A 2)
.
.
.
> (re-start)
(B 1)
.
.
.

通過(guò)把詞法閉包編結(jié)成串，Common Lisp 程序得以構(gòu)造自己的續(xù)延。幸運(yùn)的是，這些閉包是由 [示例代碼 20.4] 中血汗工廠給出的宏編織而成的，用戶可以不用關(guān)心它們的出處，而直接享用勞動(dòng)成果。

第21–24 章都以某種方式依賴于續(xù)延。這些章節(jié)將顯示續(xù)延是一種能力非凡的抽象。它可能不會(huì)很快，如果是在語(yǔ)言層面之上，用宏實(shí)現(xiàn)的話，其性能可能會(huì)更會(huì)大打折扣。但是，我們基于續(xù)延構(gòu)造的抽象層可以大大加快某些程序的編寫速度，而且提高編程效率也有著其實(shí)際意義。

20.3 Code-Walker 和 CPS Conversion

從前一節(jié)里描述的宏，我們看到了一種折衷。只有用特定的方式編寫程序，我們才能施展續(xù)延的威力。

[示例代碼 20.5] 的第 4 條規(guī)則意味著我們必須把代碼寫成

(=bind (x) (fn y)
  (list 'a x))

而不能是

(list 'a ; wrong
  (=bind (x) (fn y) x))

真正的 call/cc 就不會(huì)把這種限制強(qiáng)加于程序員。call/cc 可以捕捉到所有程序中任意地方的續(xù)延。盡管我們也能實(shí)現(xiàn)具有 call/cc 所有功能的操作符，但那還要做很多工作。本節(jié)會(huì)大略提一下，如果真要這樣做的話，還有哪些事有待完成。

Lisp 程序可以轉(zhuǎn)換成一種稱為 "continuation-passingstyle" (續(xù)延傳遞風(fēng)格) 的形式。經(jīng)過(guò)完全的 ?? 轉(zhuǎn)換的程序是不可讀的，但我們可以通過(guò)觀察被部分轉(zhuǎn)換了的代碼來(lái)體會(huì)這個(gè)過(guò)程的思想。下面這個(gè)用于求逆列表的函數(shù)：

(defun rev (x)
  (if (null x)
    nil
    (append (rev (cdr x)) (list (car x)))))

產(chǎn)生的等價(jià)續(xù)延傳遞版本：

(defun rev2 (x)
  (revc x #'identity))

(defun revc (x k)
  (if (null x)
    (funcall k nil)
    (revc (cdr x)
      #'(lambda (w)
        (funcall k (append w (list (car x))))))))

在 continuation-passingstyle 里，函數(shù)得到了一個(gè)附加的形參(這里是k)，其值將是當(dāng)前的續(xù)延。這個(gè)續(xù)延是個(gè)閉包，它代表了對(duì)函數(shù)的當(dāng)前值應(yīng)該做些什么。在第一次遞歸時(shí)，續(xù)延是 identity；此時(shí)函數(shù)的任務(wù)就是返回其當(dāng)前的值。在第二次遞歸時(shí)，續(xù)延將等價(jià)于

#'(lambda (w)
  (identity (append w (list (car x)))))

也就是說(shuō)要做的事就是追加一個(gè)列表的 car 到當(dāng)前的值上，然后返回它。

一旦可以進(jìn)行 CPS 轉(zhuǎn)換，實(shí)現(xiàn) call/cc 就易如反掌了。在帶有 ?? 轉(zhuǎn)換的程序里，當(dāng)前的整個(gè)續(xù)延總是存在的，這樣 call/cc 就可以實(shí)現(xiàn)成一個(gè)簡(jiǎn)單的宏，將一些函數(shù)作為一個(gè)參數(shù)來(lái)和它一起調(diào)用就好了。

為了做 CPS 轉(zhuǎn)換，我們需要 code-walker，它是一種能夠遍歷程序源代碼樹的程序。為 Common Lisp 編寫 code-walker 并非易事。要真正能有用，code-walker 的功能不能僅限于簡(jiǎn)單地遍歷表達(dá)式。它還需要相當(dāng)了解表達(dá)式的作用。例如，code-walker 不能只是在符號(hào)的層面上思考。比如，符號(hào)至少可以代表，它本身，一個(gè)函數(shù)，變量，代碼塊名稱，或是一個(gè) go 標(biāo)簽。code-walker 必須根據(jù)上下文，分辨出符號(hào)的種類，并進(jìn)行相應(yīng)的操作。

由于編寫code-walker 超出了本書的范圍，所以本章里描述的宏只是最現(xiàn)實(shí)的替代品。本章中的宏將用戶跟構(gòu)建續(xù)延的工作分離開了。如果有用戶編寫了相當(dāng)接近于 ?? 的程序，這些宏可以做其余的事情。第4 條規(guī)則實(shí)際上說(shuō)的是：如果緊接著=bind 表達(dá)式的每樣?xùn)|西都在其代碼體里，那么在 cont 的值和=bind 主體中的代碼之間，程序有足夠的信息用來(lái)構(gòu)造當(dāng)前的續(xù)延。

=bind 宏故意寫成這樣以使得這種編程風(fēng)格看起來(lái)自然些。在實(shí)踐中由續(xù)延傳遞宏所引入的各種限制還是可以容忍的。

備注：

【注2】由=defun 產(chǎn)生的函數(shù)被有意地賦予了intern 了的名字，好讓這些函數(shù)能夠被 trace 。如果沒有必要做trace 的話，用gensym 來(lái)作為它們的名字應(yīng)該會(huì)更安全些。

【注3】譯者注：原文是 "cont 的值是 identity"，這是錯(cuò)誤的。并且原書勘誤修正了[示例代碼 20.4] 中對(duì)應(yīng)的 cont 定義，這里譯文也隨之做了修改。

【注4】譯者注：原書中在這里還有一句話："at's why cont is given its initial value in a setq instead of a defvar： the latter would also proclaim it to be special." 原作者假設(shè)cont 全局變量是詞法作用域的，但這違反了Common Lisp 標(biāo)準(zhǔn)。為了能在現(xiàn)代Common Lisp 實(shí)現(xiàn)上運(yùn)行這些代碼，譯文采納了C???? 上給出的一個(gè)解決方案，使用符號(hào)宏來(lái)模擬詞法變量。具體參見[示例代碼 20.4] 中修改過(guò)的代碼。