第 20 章續延(continuation) · On Lisp 中文版

## 第 20 章續延(continuation) 續延是在運行中被暫停了的程序：即含有計算狀態的單個函數型對象。當這個對象被求值時，就會在它上次停下來的地方重新啟動之前保存下來的計算。對于求解特定類型的問題，能夠保存程序的狀態并在之后重啟是非常有用的。例如在多進程中，續延可以很方便地表示掛起的進程。而在非確定性的搜索問題里，續延可以用來表示搜索樹中的節點。要一下子理解續延或許會有些困難。本章分兩步來探討這個主題。本章的第一部分會先分析續延在 Scheme 中的應用，這門語言內置了對續延的支持。一旦說清楚了續延的行為，第二部分將展示如何使用宏在 Common Lisp 程序里實現續延。第 21-24 章都將用到這里定義的宏。 ### 20.1 Scheme 續延 Scheme 和 Common Lisp 在幾個主要方面存在著不同，其中之一就是：前者擁有顯式的續延支持。本節展示的是續延在Scheme 中的工作方式。([示例代碼 20.1] 列出了 Scheme 和 Common Lisp 間一些其他的區別。) 續延是一個代表著計算的將來的函數。不管是哪一個表達式被求值，總會有誰在翹首以待它將要返回的值。例如，在 ~~~ (/ (- x 1) 2) ~~~ 中，當求值 (- x 1) 時，外面的 / 表達式就在等著這個值，同時，還有另外一個式子也在等著它的值，依此類推下去，最后總是回到 toplevel 上 print 正等在那里。無論何時，我們都可以把續延視為帶一個參數的函數。如果上面的表達式被輸入到 toplevel，那么當子表達式 (- x 1) 被求值時，續延將是： ~~~ (lambda (val) (/ val 2)) ~~~ 也就是說，接下來的計算可以通過在返回值上調用這個函數來重現。如果該表達式在下面的上下文中出現 ~~~ (define (f1 w) (let ((y (f2 w))) (if (integer? y) (list 'a y) 'b))) (define (f2 x) (/ (- x 1) 2)) ~~~ 并且 f1 在toplevel 下被調用，那么當 (- x 1) 被求值時，續延將等價于 ~~~ (lambda (val) (let ((y (/ val 2))) (if (integer? y) (list 'a y) 'b))) ~~~ 在 Scheme 中，續延和函數同樣是第一類對象。你可以要求 Scheme 返回當前的續延，然后它將為你生成一個只有單個參數的函數，以表示未來的計算。你可以任意長時間地保存這個對象，然后在你調用它時，它將重啟當它被創建時所發生的計算。 1. 在 Common Lisp 眼中，一個符號的 symbol-value 和 symbol-function 是不一樣的，而 Scheme 對兩者不作區分。在 Scheme 里面，變量只有唯一對應的值，它可以是個函數，也可以是另一種對象。因此，在 Scheme 中就不需要 #' 或者 funcall 了。Common Lisp 的： (let ((f #'(lambda (x) (1+ x)))) (funcall f 2)) 在 Scheme 中將變成： ~~~ (let ((f (lambda (x) (1+ x)))) (f 2)) ~~~ 1. 由于 Scheme 只有一個名字空間，因而它沒有必要為各個名字空間專門設置對應的賦值操作符(例如 defun 和 setq )。取而代之，它使用 define ，define 的作用和 defvar 大致相當，同時用 set! 替代了 setq 。在用 set! 為全局變量賦值前，必須先用 define 創建這個變量。 2. 在 Scheme 中，通常用 define 定義有名函數，它行使著 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 中，函數的參數按從左到右的順序求值。而在 Scheme 中，有意地不對求值順序加以規定。(并且語言的實現者對于忘記這點的人幸災樂禍。) 2. Scheme 不用 t 和 nil ，相應的，它有 #t 和 #f 。空列表，()，在某些實現里為真，而在另一些實現里為假。 3. cond 和 case 表達式里的默認子句在 Scheme 中帶有 else 關鍵字，而不是 Common Lisp 中的 t 。 4. 某些內置操作符的名字被改掉了：consp 成了 pair? ，而 null 則是 null? ，mapcar (幾乎) 是 map ，等等。通常根據上下文，應該能看出這些操作符的意思。 [示例代碼 20.1]： Scheme 和 Common Lisp 之間的一些區別續延可以理解成是一種廣義的閉包。閉包就是一個函數加上一些指向閉包創建時可見的詞法變量的指針。續延則是一個函數加上一個指向其創建時所在的整個棧的指針。當續延被求值時，它返回的是使用自己的棧拷貝算出的結果，而沒有用當前棧。如果某個續延是在 T1 時刻創建的，而在 T2 時刻被求值，那么它求值時使用的將是 T1 時刻的棧。 Scheme 程序通過內置操作符 call-with-current-continuation (縮寫為 call/cc) 來訪問當前續延。當一個程序在一個單個參數的函數上調用 call/cc 時： ~~~ (call-with-current-continuation (lambda (cc) ...)) ~~~ 這個函數將被傳進另一個代表當前續延的函數。通過將 cc 的值存放在某個地方，我們就可以保存在 call/cc 那一點上的計算狀態。在這個例子里，我們 append 出一個列表，列表的最后一個元素是一個 call/cc 表達式的返回值： ~~~ > (define frozen) FROZEN > (append '(the call/cc returned) (list (call-with-current-continuation (lambda (cc) (set! frozen cc) 'a)))) (THE CALL/CC RETURNED A) ~~~ 這個 call/cc 返回了 a ，但它首先將續延保存在了全局變量 frozen 中。調用 frozen 會導致在 call/cc 那一點上的舊的計算重新開始。無論我們傳給 frozen 什么值，這個值都將作為 call/cc 的值返回： ~~~ > (frozen 'again) (THE CALL/CC RETURNED AGAIN) ~~~ 續延不會因為被求值而用完。它們可以被重復調用，就像任何其他的函數型對象一樣： ~~~ > (frozen 'thrice) (THE CALL/CC RETURNED THRICE) ~~~ 當我們在某些其他的計算里調用一個續延時，我們可以更清楚地看到所謂返回到原先的棧上是什么意思： ~~~ > (+ 1 (frozen 'safely)) (THE CALL/CC RETURNED SAFELY) ~~~ 這里，緊接著的 + 當 frozen 調用時被忽略掉了。后者返回到了它首次被創建時的棧上：先經過 list ，然后是 append ，直到 toplevel。如果 frozen 像正常函數調用那樣返回了一個值，那么上面的表達式將在試圖給一個列表加 1 時產生一個錯誤。各續延并不會每人都分到自己的一份棧的拷貝。它們可能跟其他續延或者當前正在進行的計算共享一些變量。在下面這個例子里，兩個續延共享了同一個棧： ~~~ > (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 ~~~ 因此調用任何一個都將返回后繼的整數： ~~~ > (froz2 ()) 2 > (froz1 ()) 3 ~~~ 由于 call/cc 表達式的值將被丟棄，所以無論我們給 froz1 和 froz2 什么參數都無關緊要。現在能保存計算的狀態了，我們可以用它做什么呢？第 21-24 章致力于使用續延的應用。這里將要考察一個比較簡單的例子，它能夠體現出使用保存狀態編程的特色：假設有一組樹，我們想從每棵樹都取出一個元素，組成一個列表，直到獲得一個滿足某種條件的組合。樹可以用嵌套列表來表示。第 5.6 節上描述了一種將一類樹表示成列表的方法。這里我們采用另一種方法，允許內部節點帶有(原子的) 值，以及任意數量的孩子。在這種表示方法里，內部節點變成了一個列表；其 car 包含保存在這個節點上的值，其 cdr 包含該節點孩子的表示。例如，[示例代碼 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]：用續延來遍歷樹 ~~~ (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] 中的函數能在這樣的樹上做深度優先搜索。在實際的程序里，我們可能想要在遇到節點時用它們做一些事。這里只是打印它們。為了便于比較，這里給出的函數 dft 實現了通常的深度優先遍歷： ~~~ > (dft t1) ABDHCEFIG() ~~~ 函數 dft-node 按照同樣的路徑遍歷這棵樹，但每次只處理一個節點。當 dft-node 到達一個節點時，它跟著節點的 car 走，并且在 *saved* 里壓入一個續延來瀏覽其 cdr 部分。 ~~~ > (dft-node t1) A ~~~ 調用 restart 可以繼續遍歷，作法是彈出最近保存的續延并調用它。 ~~~ > (restart) B ~~~ 最后，所有之前保存的狀態都用完了，restart 通過返回 done 來通告這一事實： ~~~ . . . > (restart) G > (restart) DONE ~~~ 最后，函數 dft2 把我們剛剛手工完成的工作干凈漂亮地一筆帶過： ~~~ > (dft2 t1) ABDHCEFIG() ~~~ 注意到在dft2 的定義里沒有顯式的遞歸或迭代：后繼的節點被打印出來，是因為由 restart 引入的續延總是返回到 dft-node 中同樣的 cond 子句那里。這種程序的工作方式就跟采礦差不多。它先調用 dft-node 初步挖出一個礦坑。一旦返回值不是 done ，dft-node 后面的代碼將調用 restart 將控制權發回到棧上。這個過程會一直持續，直到到返回值表明礦被采空。這時，dft2 將不再打印返回值，而是返回 #f 。使用續延的搜索方式帶來了一種編寫程序的新思路：將合適的代碼放在棧上，然后不斷地返回到那里來獲得結果。如果我們只是想同時遍歷一棵樹，就像 dft2 里那樣，那么實在沒有必要使用這種技術。dft-node 的優勢在于，可以同時運行它的多個實例。假設有兩棵樹，并且我們想要以深度優先的順序生成其中元素的叉積。 ~~~ > (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) . . . ~~~ 借助常規技術，我們必須采取顯式的措施來保存我們在兩棵樹中的位置。而通過續延，則能非常自然地維護兩個正在進行的遍歷操作的狀態。對于諸如本例的簡單情形，要保存我們在樹中的位置還不算太難。樹是持久性的數據結構，所以我們至少有辦法找到 "我們在樹中的位置"。續延的過人之處在于，即使沒有持久性的數據結構與之關聯，它同樣可以在任何的計算過程中輕松保存我們的位置。這一計算甚至也不需要具有有限數量的狀態，只要重啟它們有限次就行了。正如第24 章將要展示的，這兩種考慮被證實在 Prolog 的實現中至關重要。在 Prolog 程序里，"搜索樹" 并非真正的數據結構，而只是程序生成結果的一種隱式方式。而且這些樹經常是無窮大的，這種情況下，我們不能指望在搜索下一棵樹之前把整棵樹都搜完，所以只得想個辦法保存我們的位置，除此之外別無選擇。 ### 20.2 續延傳遞宏雖然 Common Lisp 沒有提供 call/cc ，但是再加把勁，我們就可以像在 Scheme 里那樣做到同樣的事情了。本節展示如何用宏在 Common Lisp 程序中構造續延。Scheme 的續延給了我們兩樣東西： 1. 續延被創建時所有變量的綁定。 2. 計算的狀態從那時起將要發生什么。在一個詞法作用域的 Lisp 里，閉包給了我們前者。可以看出我們也能使用閉包來獲得后者，辦法是把計算的狀態同樣也保存在變量綁定里。 * * * **[示例代碼 20.4] 續延傳遞宏** ~~~ (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] 給出的宏讓我們能在保留續延的情況下，進行函數調用。這些宏取代了幾個內置的 Common Lisp form，它們被用來定義函數，進行函數調用，以及返回函數值。如果有函數需要使用續延，或者這個函數所調用的函數要用到續延，那么該函數就該用=defun 而不是 defun 定義。=defun 的語法和 defun 相同，但其效果有些微妙的差別。=defun 定義的并不是單單一個函數，它實際上定義了一個函數和一個宏，這個宏會展開成對該函數的調用。(宏定義必須在先，原因是被定義的函數有可能會調用自己。) 函數的主體就是傳給=defun 的那個，但還另有一個形參，即 *cont* ，它被連接在原有的形參列表上。在宏展開式里，*cont* 會和其他參數一同傳給這個函數。所以 ~~~ (=defun add1 (x) (=values (1+ x))) ~~~ 宏展開成 ~~~ (progn (defmacro add1 (x) '(=add1 \*cont\* ,x)) (defun =add1 (\*cont\* x) (=values (1+ x)))) ~~~ 當調用add1 時，實際被調用的不是函數而是個宏。這個宏會展開成一個函數調用，但是另外帶了一個參數：*cont*。所以，在調用 =defun 定義的操作符的時候，*cont* 的當前值總是被默默地傳遞著。那 *cont* 有什么用呢？它將被綁定到當前的續延。=values 的定義顯示了這個續延的用場。只要是用 =defun 定義的函數，都必須通過 =values 來返回值，或者調用另一個使用 =values 的函數。=values 的語法與 Common Lisp 的values 相同。如果有個帶有相同數量參數的 =bind 等著它的話，它可以返回多值，但它不能返回多值到 toplevel。參數 *cont* 告訴那個由 =defun 定義的函數對其返回值做什么。當 =values 被宏展開時，它將捕捉 *cont* ，并用它模擬從函數返回值的過程。表達式 ~~~ (=values (1+ n)) ~~~ 會展開成 ~~~ (funcall \*cont\* (1+ n)) ~~~ 在 toplevel 下，*cont* 的值是 #'values，這就相當于一個真正的 values 多值返回。當我們在 toplevel 下調用 (add1 2) 時，這個調用的宏展開式與下式等價 ~~~ (funcall #'(lambda (\*cont\* n) (=values (1+ n))) \*cont\* 2) ~~~ *cont* 的引用在這種情況下將得到全局綁定。因而，=values 表達式在宏展開后將等價于下式 ~~~ (funcall #'values (1+ n)) ~~~ 即把在 n 上加 1，并返回結果。在類似 add1 的函數里，我們克服了重重困難，不過是為了模擬 Lisp 進行函數調用和返回值的過程： ~~~ > (=defun bar (x) (=values (list 'a (add1 x)))) BAR > (bar 5) (A 6) ~~~ 關鍵在于，現在有了 "函數調用" 和 "函數返回" 可供差遣，而且如果愿意的話，我們還可以把它們用在其他地方。我們之所以能獲得續延的效果，要歸功于對 *cont* 的操控。雖然 *cont* 的值是全局的，但這個全局變量很少用到：*cont* 幾乎總是一個形參，它被 =values 以及用 =defun 定義的宏所捕捉。例如在 add1 的函數體里，*cont* 就是一個形參而非全局變量。這個區別是很重要的，因為如果 *cont* 不是一個局部變量的話這些宏將無法工作。 [示例代碼 20.4] 中的第三個宏，=bind ，其用法和 multiple-value-bind 相同。它接受一個參數列表，一個表達式，以及一個代碼體：參數將被綁定到表達式返回的值上，而代碼體在這些綁定下被求值。倘若一個由 =defun 定義的函數，在被調用之后，需要對另一個表達式進行求值，那么就應該使用=bind 宏。 ~~~ > (=defun message () (=values 'hello 'there)) MESSAGE > (=defun baz () (=bind (m n) (message) (=values (list m n)))) BAZ > (baz) (HELLO THERE) ~~~ 注意到 =bind 的展開式會創建一個稱為 *cont* 的新變量。baz 的主體展開成： ~~~ (let ((\*cont\* #'(lambda (m n) (=values (list m n))))) (message)) ~~~ 然后會變成： ~~~ (let ((\*cont\* #'(lambda (m n) (funcall \*cont\* (list m n))))) (=message \*cont\*)) ~~~ 由于 *cont* 的新值是 =bind 表達式的代碼體，所以當 message 通過函數調用 *cont* 來 "返回" 時，結果將是去求值這個代碼體。盡管如此(并且這里是關鍵)，在=bind 的主體里： ~~~ #'(lambda (m n) (funcall \*cont\* (list m n))) ~~~ 作為參數傳遞給=baz 的*cont* 仍然是可見的，所以當代碼的主體求值到一個=values 時，它將能夠返回到最初的主調函數那里。所有閉包環環相扣：每個*cont* 的綁定都包含了上一個*cont* 綁定的閉包，它們串成一條鎖鏈，鎖鏈的盡頭指向那個全局的值。在這里，我們也可以觀察到更小規模的同樣現象： ~~~ > (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)) ~~~ 本例創建了一個函數，它是含有指向g 的引用的閉包，而g 本身也是一個含有到f 的引用的閉包。第 6.3 節上的網絡編譯器中曾構造過類似的閉包鏈。剩下兩個宏，分別是=apply 和=funcall ，它們適用于由=lambda 定義的函數。注意那些用=defun 定義出來的"函數"，因為它們的真實身份是宏，所以不能作為參數傳給apply 或funcall。解決這個問題的方法類似于第 8.2 節上提到的技巧。也就是把調用包裝在另一個=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] 總結了所有因續延傳遞宏而引入的限制。如果有函數既不保存續延，也不調用其他保存續延的函數，那它就沒有必要使用這些特殊的宏。比如像list 這樣的內置函數就沒有這個需要。 [示例代碼 20.6] 中把來自[示例代碼 20.3] 的代碼? 從Scheme 翻譯成了Common Lisp，并且用續延傳遞宏代替了Scheme 續延。以同一棵樹為例，dft2 和之前一樣工作正常： ?譯者注：這段代碼與原書有一些出入：首先 (setq?*saved*?nil) 被改為 (defvar?*saved*?nil)；其次將restart 改為re-start 以避免和Common Lisp 已有的符號沖突，并且將re-start 的定義放在dft-node 的定義之前以確保后者在編譯時可以找到re-start 的定義。 1. 一個用=defun 定義的函數的參數列表必須完全由參數名組成。 2. 使用續延，或者調用其他做這件事的函數的函數，必須用=lambda 或=defun 來定義。 3. 這些函數必須終結于用=values 來返回值，或者調用其他遵守該約束的函數。 4. 如果一個=bind ，=values ，或者=funcall 表達式出現在一段代碼里，它必須是一個尾調用。任何在=bind 之后求值的代碼必須放在其代碼體里。所以如果我們想要依次有幾個=bind ，它們必須被嵌套： * * * **[示例代碼 20.5] 續延傳遞宏的限制** ~~~ (=defun foo (x) (=bind (y) (bar x) (format t "Ho ") (=bind (z) (baz x) (format t "Hum.") (=values x y z)))) ~~~ * * * **[示例代碼 20.6] 使用續延傳遞宏的樹遍歷** ~~~ (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 里一樣，我們仍然可以保存多路遍歷的狀態，盡管這個例子會顯得有些冗長： ~~~ > (=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) . . . ~~~ 通過把詞法閉包編結成串，Common Lisp 程序得以構造自己的續延。幸運的是，這些閉包是由 [示例代碼 20.4] 中血汗工廠給出的宏編織而成的，用戶可以不用關心它們的出處，而直接享用勞動成果。第21–24 章都以某種方式依賴于續延。這些章節將顯示續延是一種能力非凡的抽象。它可能不會很快，如果是在語言層面之上，用宏實現的話，其性能可能會更會大打折扣。但是，我們基于續延構造的抽象層可以大大加快某些程序的編寫速度，而且提高編程效率也有著其實際意義。 ### 20.3 Code-Walker 和 CPS Conversion 從前一節里描述的宏，我們看到了一種折衷。只有用特定的方式編寫程序，我們才能施展續延的威力。 [示例代碼 20.5] 的第 4 條規則意味著我們必須把代碼寫成 ~~~ (=bind (x) (fn y) (list 'a x)) ~~~ 而不能是 ~~~ (list 'a ; wrong (=bind (x) (fn y) x)) ~~~ 真正的 call/cc 就不會把這種限制強加于程序員。call/cc 可以捕捉到所有程序中任意地方的續延。盡管我們也能實現具有 call/cc 所有功能的操作符，但那還要做很多工作。本節會大略提一下，如果真要這樣做的話，還有哪些事有待完成。 Lisp 程序可以轉換成一種稱為 "continuation-passingstyle" (續延傳遞風格) 的形式。經過完全的 ?? 轉換的程序是不可讀的，但我們可以通過觀察被部分轉換了的代碼來體會這個過程的思想。下面這個用于求逆列表的函數： ~~~ (defun rev (x) (if (null x) nil (append (rev (cdr x)) (list (car 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 里，函數得到了一個附加的形參(這里是k)，其值將是當前的續延。這個續延是個閉包，它代表了對函數的當前值應該做些什么。在第一次遞歸時，續延是 identity；此時函數的任務就是返回其當前的值。在第二次遞歸時，續延將等價于 ~~~ #'(lambda (w) (identity (append w (list (car x))))) ~~~ 也就是說要做的事就是追加一個列表的 car 到當前的值上，然后返回它。一旦可以進行 CPS 轉換，實現 call/cc 就易如反掌了。在帶有 ?? 轉換的程序里，當前的整個續延總是存在的，這樣 call/cc 就可以實現成一個簡單的宏，將一些函數作為一個參數來和它一起調用就好了。為了做 CPS 轉換，我們需要 code-walker，它是一種能夠遍歷程序源代碼樹的程序。為 Common Lisp 編寫 code-walker 并非易事。要真正能有用，code-walker 的功能不能僅限于簡單地遍歷表達式。它還需要相當了解表達式的作用。例如，code-walker 不能只是在符號的層面上思考。比如，符號至少可以代表，它本身，一個函數，變量，代碼塊名稱，或是一個 go 標簽。code-walker 必須根據上下文，分辨出符號的種類，并進行相應的操作。由于編寫code-walker 超出了本書的范圍，所以本章里描述的宏只是最現實的替代品。本章中的宏將用戶跟構建續延的工作分離開了。如果有用戶編寫了相當接近于 ?? 的程序，這些宏可以做其余的事情。第4 條規則實際上說的是：如果緊接著=bind 表達式的每樣東西都在其代碼體里，那么在 *cont* 的值和=bind 主體中的代碼之間，程序有足夠的信息用來構造當前的續延。 =bind 宏故意寫成這樣以使得這種編程風格看起來自然些。在實踐中由續延傳遞宏所引入的各種限制還是可以容忍的。備注：【注2】由=defun 產生的函數被有意地賦予了intern 了的名字，好讓這些函數能夠被 trace 。如果沒有必要做trace 的話，用gensym 來作為它們的名字應該會更安全些。【注3】譯者注：原文是 "*cont* 的值是 identity"，這是錯誤的。并且原書勘誤修正了[示例代碼 20.4] 中對應的 *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." 原作者假設*cont* 全局變量是詞法作用域的，但這違反了Common Lisp 標準。為了能在現代Common Lisp 實現上運行這些代碼，譯文采納了C???? 上給出的一個解決方案，使用符號宏來模擬詞法變量。具體參見[示例代碼 20.4] 中修改過的代碼。