第十六章 繼續(xù)

簡介

本章介紹的是Scheme中特有的數(shù)據(jù)類型——繼續(xù)（Continuation）。由于其他程序設(shè)計(jì)語言并沒有這種數(shù)據(jù)類型，因此它難于理解。當(dāng)下，你并不需要徹底理解清楚，只需要大致了解。

我會講解廣義的繼續(xù)和簡短地介紹Continuation-Passing-Style(CPS)，然后再講解Scheme中的繼續(xù)。我認(rèn)為通過這種方式理解繼續(xù)會比較容易。

廣義繼續(xù)

繼續(xù)是在返回到頂層（Top level）之前所需要執(zhí)行的計(jì)算。實(shí)際上，繼續(xù)存在于計(jì)算的每時每刻。以(* 3 (+ 1 2))為例，在求值完(+ 1 2)后，應(yīng)該計(jì)算{ (* 3 []) }乘以3。然而，大多數(shù)語言都不顯式地這么做，程序員對此并不熟悉。

Continuation-Passing-Style(CPS)

簡單的CPS

CPS是一種編程風(fēng)格，在這種風(fēng)格中，把依賴于當(dāng)前函數(shù)結(jié)果的后續(xù)函數(shù)作為參數(shù)傳遞給當(dāng)前函數(shù)。[代碼1]展示了以CPS編寫的加法和乘法。在k+和k*中，k是后續(xù)函數(shù)。

[代碼1]

(define (return x)
  x)

(define (k+ a b k)
  (k (+ a b)))

(define (k* a b k)
  (k (* a b)))

[例1]演示了如何使用CPS計(jì)算(* 3 (+ 1 2))。

[例1]

(k+ 1 2 (lambda (x) (k* x 3 return)))

Scheme的普通形式中，值在括號內(nèi)被計(jì)算并向括號外傳遞。與此相反，CPS中，值向括號內(nèi)傳遞。如[例1]中，k+把(+ 1 2)的值傳遞給(lambda (x) (k* x 3 return))，而k*把(* (+ 1 2) 3)的結(jié)果傳給return。

以CPS編寫遞歸函數(shù)

遞歸函數(shù)同樣可以以CPS編寫。[代碼2]展示了計(jì)算階乘的函數(shù)如何用普通方式編寫（fact）和以CPS編寫(kfact)。

[代碼2]

;;; normal factorial
(define (fact n)
  (if (= n 1) 
      1
      (* n (fact (- n 1)))))

;;; CPS factorial
(define (kfact n k)
  (if (= n 1) 
      (k 1)
      (kfact (- n 1) (lambda (x) (k (* n x))))))

[例2]將3與4的階乘相加。

[例2]

;;; normal
(+ 3 (fact 4))

;;; CPS
(kfact 4 (lambda (x) (k+ x 3 return)))

[代碼3]演示了如何分別用普通方式和CPS編寫計(jì)算表中元素之積的函數(shù)。在CPS函數(shù)中，后繼函數(shù)存儲在局部變量break中，因此當(dāng)元素乘以0時，可以立即退出。

[代碼3]

;;; normal
(define (product ls)
  (let loop ((ls ls) (acc 1))
    (cond
     ((null? ls) acc)
     ((zero? (car ls)) 0)
     (else (loop (cdr ls) (* (car ls) acc))))))

;;; CPS
(define (kproduct ls k)
  (let ((break k))
    (let loop ((ls ls) (k k))
      (cond
       ((null? ls) (k 1))
       ((zero? (car ls)) (break 0))
       (else (loop (cdr ls) (lambda (x) (k (* (car ls) x)))))))))

[例3]將100與'(2 4 7)的積相加。

[例3]

;;; normal
(+ 100 (product '(2 4 7)))

;;; CPS
(kproduct '(2 4 7) (lambda (x) (k+ x 100 return)))

盡管CPS在這樣簡單的情況中并不實(shí)用，但在一些像是自然語言解析和邏輯編程等復(fù)雜程序中非常有用，因?yàn)榕c通常的編程風(fēng)格相比，CPS可以更靈活地改變后續(xù)過程。

異常處理（Exception handling）就是這種情況的簡單例子。[代碼4]演示了kproduct的錯誤處理版本，程序中當(dāng)非數(shù)字值出現(xiàn)在輸入表中，在其被打印時，計(jì)算就會終止。

(define (non-number-value-error x)
  (display "Value error: ")
  (display  x)
  (display " is not number.")
  (newline)
  'error)
(define (kproduct ls k k-value-error)
  (let ((break k))
    (let loop ((ls ls) (k k))
      (cond
       ((null? ls) (k 1))
       ((not (number? (car ls))) (k-value-error (car ls)))
       ((zero? (car ls)) (break 0))
       (else (loop (cdr ls) (lambda (x) (k (* (car ls) x)))))))))
;;; valid
(kproduct '(2 4 7) 
      (lambda (x) (k+ x 100 return)) 
      non-number-value-error)
;Value: 156
;;; invalid
(kproduct '(2 4 7 hoge) 
      (lambda (x) (k+ x 100 return)) 
      non-number-value-error)
Value error: hoge is not number.
;Value: error

Scheme中的繼續(xù)

通過上面的講解，你應(yīng)該掌握了繼續(xù)（continuation）。繼續(xù)有下面的性質(zhì)：

1. 存在于整個計(jì)算過程中；
2. 函數(shù)式程序設(shè)計(jì)語言和CPS可以顯式地處理它。

另外，上面例子展示的是閉包鏈（Chain of closure）。

然而，閱讀和編寫CPS程序是痛苦的，以常規(guī)方式來處理繼續(xù)會更方便一點(diǎn)。

因此，Scheme中將繼續(xù)實(shí)現(xiàn)為一級對象（first class object）（這意味這Scheme中的繼續(xù)是個普通數(shù)據(jù)類型），任何時候都可以通過名為call-with-current-continuation來調(diào)用。由于繼續(xù)是普通數(shù)據(jù)類型，你可以隨心所欲地重用?？紤]到call-with-current-continuation名字過長，通常使用其縮略名call/cc。

(define call/cc call-with-current-continuation)

函數(shù)call-with-current-continuation (call/cc)接受一個參數(shù)。該參數(shù)是一個函數(shù)，函數(shù)的參數(shù)接收當(dāng)前繼續(xù)。

下面是例子：

(* 3 (call/cc (lambda (k) (+ 1 2))))     ;? 9      ; [1]
(* 3 (call/cc (lambda (k) (+ 1 (k 2))))) ;? 6      ; [2]

在情況[1]中，繼續(xù)并沒有被調(diào)用，語句的行為與普通S-表達(dá)式相同。另一方面，在情況[2]中，繼續(xù)以2作為參數(shù)被調(diào)用。在這種情況中，繼續(xù)的參數(shù)跳過了call/cc的處理，并逃逸至call/cc的外部。這種情況中，k是一個一元函數(shù)，等價(jià)于(lambda (x) (* 3 x))。

大體來說，當(dāng)前繼續(xù)存儲了從call/cc調(diào)用點(diǎn)到頂層的處理過程。當(dāng)前繼續(xù)可以像其它數(shù)據(jù)類型那樣被存儲起來，并隨心所欲地重用。

(define cc)
  (* 3 (call/cc (lambda (k)
                  (set! cc k)
                  (+ 1 2))))

由于當(dāng)前繼續(xù)是回到頂層的處理過程，它的返回會忽略周圍的S-表達(dá)式。

(+ 100 (cc 3))  ;? 9 
(+ 100 (cc 10)) ;? 30

使用call/cc拋出值

從一個計(jì)算過程中逃逸出來，是使用當(dāng)前繼續(xù)的最容易的方法。[代碼5]演示了搜索樹（嵌套表）的函數(shù)。如果函數(shù)在樹中找到obj，那么它返回該對象，否則返回#f。一旦找到obj，函數(shù)直接將其拋出至最外部。

(define (find-leaf obj tree)
  (call/cc
    (lambda (cc)
       (letrec ((iter
                   (lambda (tree)
                      (cond
                        ((null?  tree) #f)
                        ((pair? tree)
                           (iter (car tree))
                           (iter (cdr tree)))
                        (else
                          (if (eqv? obj tree)
                            (cc obj)))))))
         (iter tree)))))

(find-leaf 7 '(1 (2 3) 4 (5 (6 7))))
;? 7

(find-leaf 8 '(1 (2 3) 4 (5 (6 7))))
;? ()

[例6]演示了一個支持拋出的語法block。

(define-syntax block
  (syntax-rules ()
    ((_ tag e1 ...)
     (call-with-current-continuation
       (lambda (tag)
          e1 ...)))))

[例7]演示了如何使用它。

(block break
   (map (lambda (x)
           (if (positive? x)
           (sqrt x)
           (break x)))
    '(1 2 3)))
;? (1 1.4142135623730951 1.7320508075688772)

(block break
   (map (lambda (x)
           (if (positive? x)
           (sqrt x)
           (break x)))
    '(1 -2 3)))
;? -2

生成器

我會講解如何用call/cc實(shí)現(xiàn)一個樹匹配的生成器。生成器以一個樹為參數(shù)返回一個函數(shù)，每次調(diào)用這個返回的函數(shù)時，它會返回后續(xù)的葉子。生成器的使用方法如下：

(define tr '((1 2) (3 (4 5))))
(define p (leaf-generator tr))

(p) ;=> 1
(p) ;=> 2
(p) ;=> 3
(p) ;=> 4
(p) ;=> 5
(p) ;=> ()  ; finally it returns '()

[代碼6]給出了生成器的定義。這個和原始版本基本上相同，但有略微的修改。

[代碼6]

(define (leaf-generator tree)
  (let ((return '()))                                               ; 1
    (letrec ((continue                                              ; 2
      (lambda ()
        (let rec ((tree tree))                                      ; 3
          (cond                                                     ; 4
           ((null? tree) 'skip)                                     ; 5
           ((pair? tree) (rec (car tree)) (rec (cdr tree)))         ; 6
           (else                                                    ; 7
            (call/cc (lambda (lap-to-go)                            ; 8
                   (set! continue (lambda () (lap-to-go 'restart))) ; 9
                   (return tree))))))                               ;10
        (return '()))))                                             ;11
    (lambda ()                                                  ;12
      (call/cc (lambda (where-to-go)                            ;13
                 (set! return where-to-go)                      ;14
                 (continue)))))))

(譯者注：原文中05，08行中命名let中的rec被寫為loop，結(jié)合上下文，改為rec)

注釋解釋

編號 解釋

• 1.定義本地變量return。
• 2.使用letrec定義continue。continue將當(dāng)前葉子返回到前面，將當(dāng)前繼續(xù)賦給continue，并停止。
• 3.用rec定義命名let。
• 4.使用cond實(shí)現(xiàn)分支
• 5.如果是空表，什么也不做
• 6.如果是序?qū)?，遞歸地將序?qū)Φ腸ar和cdr應(yīng)用于rec。
• 7.如果是葉子，
• 8.調(diào)用call/cc以獲取當(dāng)前狀態(tài)(lap-to-go)
• 9.接著將當(dāng)前狀態(tài)賦給continue。所以除了原有的continue，lap-to-go也包含了當(dāng)前狀態(tài)。簡而言之，它可以被如下的S-表達(dá)式中的[ ]表示。

(lambda ()
   (let rec ((tree tree0))  
      (cond                  
        ((null? tree) '())     
        ((pair? tree) (rec (car tree)) (rec (cdr tree)))  
        (else                                            
           [ ]
    (return '()))))

調(diào)用lap-to-go意味著(car tree)是葉子，且過程結(jié)束了，(rec (cdr tree))在下一次函數(shù)調(diào)用時開始運(yùn)行。如果過程在[ ]之后結(jié)束，繼續(xù)的參數(shù)將不起作用。

• 10.接著函數(shù)將找到的葉子返回到函數(shù)的調(diào)用處。(return tree)應(yīng)該在call/cc中以重啟過程。
• 11.在搜索了全部葉子之后返回空表。
• 12.這是一個返回葉子生成器的生成器。
• 13.首次調(diào)用call/cc
• 14.將表示返回值的當(dāng)前狀態(tài)賦給return。
• 15.然后調(diào)用continue。

由leaf-generator生成的函數(shù)的行為可以通過函數(shù)tree-traverse的行為來估計(jì)。過程停止在軌跡的'*'的注釋處，并使得過程存儲在continue。

一個常規(guī)的遍歷函數(shù)：

(define tree-traverse
  (lambda (tree)
    (cond
     ((null? tree) '_)
     ((pair? tree) (tree-traverse (car tree)) (tree-traverse (cdr tree)))
     (else
      (write tree)))))

當(dāng)樹為'((1 2) 3)時，tree-traverse的軌跡。

> (tree-traverse '((1 2) 3))
|(tree-traverse ((1 2) 3))
| (tree-traverse (1 2))
| |(tree-traverse 1)           
1| |#< void>               ; *
| (tree-traverse (2))
| |(tree-traverse 2)           
2| |< void>                ; *
| (tree-traverse '())
| _
|(tree-traverse (3))
| (tree-traverse 3)            
3| #< void>                ; *
|(tree-traverse '())
|_
_

協(xié)程

因?yàn)槔^續(xù)記錄了后續(xù)計(jì)算過程，因此，用于多任務(wù)同時執(zhí)行的協(xié)程（Coroutine）可以使用繼續(xù)來實(shí)現(xiàn)。

代碼片段7展示了一段交替打印數(shù)字和字母的程序。5 – 22行是隊(duì)列的實(shí)現(xiàn)。(enqueue! queue obj)將一個obj添加在隊(duì)列的末尾。(dequeue! queue)返回隊(duì)列第一個元素并將它刪除。

26 – 38行是協(xié)程的實(shí)現(xiàn)。

process-queue

過程的隊(duì)列。

(coroutine thunk)

在process-queue末尾添加thunk。

(start)

取得process-queue的第一個過程并執(zhí)行它。

(pause)

將當(dāng)前繼續(xù)添加到process-queue的末尾并執(zhí)行隊(duì)列里的第一個過程。這個函數(shù)將控制權(quán)交給另外一個協(xié)程。

42 – 61行顯示如何使用它。一個顯示數(shù)字例程和一個顯示字母例程相互調(diào)用對方，結(jié)果顯示在例7

01:     ;;; abbreviation
02:     (define call/cc call-with-current-continuation)
03:     
04:     ;;; queue
05:     (define (make-queue)
06:       (cons '() '()))
07:     
08:     (define (enqueue! queue obj)
09:       (let ((lobj (list obj)))
10:         (if (null? (car queue))
11:         (begin
12:           (set-car! queue lobj)
13:           (set-cdr! queue lobj))
14:         (begin
15:           (set-cdr! (cdr queue) lobj)
16:           (set-cdr! queue lobj)))
17:         (car queue)))
18:     
19:     (define (dequeue! queue)
20:       (let ((obj (car (car queue))))
21:         (set-car! queue (cdr (car queue)))
22:         obj))
23:     
24:     
25:     ;;; coroutine   
26:     (define process-queue (make-queue))
27:     
28:     (define (coroutine thunk)
29:       (enqueue! process-queue thunk))
30:     
31:     (define (start)
32:        ((dequeue! process-queue)))
33:        
34:     (define (pause)
35:       (call/cc
36:        (lambda (k)
37:          (coroutine (lambda () (k #f)))
38:          (start))))
39:     
40:     
41:     ;;; example
42:     (coroutine (lambda ()
43:              (let loop ((i 0)) 
44:                (if (< i 10)
45:                (begin
46:                  (display (1+ i)) 
47:                  (display " ") 
48:                  (pause) 
49:                  (loop (1+ i)))))))
50:                
51:     (coroutine (lambda ()
52:              (let loop ((i 0)) 
53:                (if (< i 10)
54:                (begin
55:                  (display (integer->char (+ i 97)))
56:                  (display " ")
57:                  (pause) 
58:                  (loop (1+ i)))))))
59:     
60:     (newline)
61:     (start)

(load "cor2.scm")
;Loading "cor2.scm"
1 a 2 b 3 c 4 d 5 e 6 f 7 g 8 h 9 i 10 j  -- done
;Unspecified return value

小結(jié)

本章中，我講解了繼續(xù)。

理解這些概念可能比較困難。但不要擔(dān)心，有朝一日你終會明白。

下一章中，我將介紹惰性求值。