第十六章 繼續(xù)

簡(jiǎn)介

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

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

廣義繼續(xù)

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

Continuation-Passing-Style(CPS)

簡(jiǎn)單的CPS

CPS是一種編程風(fēng)格，在這種風(fēng)格中，把依賴于當(dāng)前函數(shù)結(jié)果的后續(xù)函數(shù)作為參數(shù)傳遞給當(dāng)前函數(shù)。[代碼1]展示了以CPS編寫(xiě)的加法和乘法。在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的普通形式中，值在括號(hào)內(nèi)被計(jì)算并向括號(hào)外傳遞。與此相反，CPS中，值向括號(hào)內(nèi)傳遞。如[例1]中，k+把(+ 1 2)的值傳遞給(lambda (x) (k* x 3 return))，而k*把(* (+ 1 2) 3)的結(jié)果傳給return。

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

遞歸函數(shù)同樣可以以CPS編寫(xiě)。[代碼2]展示了計(jì)算階乘的函數(shù)如何用普通方式編寫(xiě)（fact）和以CPS編寫(xiě)(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編寫(xiě)計(jì)算表中元素之積的函數(shù)。在CPS函數(shù)中，后繼函數(shù)存儲(chǔ)在局部變量break中，因此當(dāng)元素乘以0時(shí)，可以立即退出。

[代碼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在這樣簡(jiǎn)單的情況中并不實(shí)用，但在一些像是自然語(yǔ)言解析和邏輯編程等復(fù)雜程序中非常有用，因?yàn)榕c通常的編程風(fēng)格相比，CPS可以更靈活地改變后續(xù)過(guò)程。

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

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

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

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

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

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

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

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

函數(shù)call-with-current-continuation (call/cc)接受一個(gè)參數(shù)。該參數(shù)是一個(gè)函數(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ù)并沒(méi)有被調(diào)用，語(yǔ)句的行為與普通S-表達(dá)式相同。另一方面，在情況[2]中，繼續(xù)以2作為參數(shù)被調(diào)用。在這種情況中，繼續(xù)的參數(shù)跳過(guò)了call/cc的處理，并逃逸至call/cc的外部。這種情況中，k是一個(gè)一元函數(shù)，等價(jià)于(lambda (x) (* 3 x))。

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

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

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

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

使用call/cc拋出值

從一個(gè)計(jì)算過(guò)程中逃逸出來(lái)，是使用當(dāng)前繼續(xù)的最容易的方法。[代碼5]演示了搜索樹(shù)（嵌套表）的函數(shù)。如果函數(shù)在樹(shù)中找到obj，那么它返回該對(duì)象，否則返回#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]演示了一個(gè)支持拋出的語(yǔ)法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

生成器

我會(huì)講解如何用call/cc實(shí)現(xiàn)一個(gè)樹(shù)匹配的生成器。生成器以一個(gè)樹(shù)為參數(shù)返回一個(gè)函數(shù)，每次調(diào)用這個(gè)返回的函數(shù)時(shí)，它會(huì)返回后續(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]給出了生成器的定義。這個(gè)和原始版本基本上相同，但有略微的修改。

[代碼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被寫(xiě)為loop，結(jié)合上下文，改為rec)

注釋解釋

編號(hào) 解釋

• 1.定義本地變量return。
• 2.使用letrec定義continue。continue將當(dāng)前葉子返回到前面，將當(dāng)前繼續(xù)賦給continue，并停止。
• 3.用rec定義命名let。
• 4.使用cond實(shí)現(xiàn)分支
• 5.如果是空表，什么也不做
• 6.如果是序?qū)Γf歸地將序?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)。簡(jiǎn)而言之，它可以被如下的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)是葉子，且過(guò)程結(jié)束了，(rec (cdr tree))在下一次函數(shù)調(diào)用時(shí)開(kāi)始運(yùn)行。如果過(guò)程在[ ]之后結(jié)束，繼續(xù)的參數(shù)將不起作用。

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

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

一個(gè)常規(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)樹(shù)為'((1 2) 3)時(shí)，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ì)算過(guò)程，因此，用于多任務(wù)同時(shí)執(zhí)行的協(xié)程（Coroutine）可以使用繼續(xù)來(lái)實(shí)現(xiàn)。

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

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

process-queue

過(guò)程的隊(duì)列。

(coroutine thunk)

在process-queue末尾添加thunk。

(start)

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

(pause)

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

42 – 61行顯示如何使用它。一個(gè)顯示數(shù)字例程和一個(gè)顯示字母例程相互調(diào)用對(duì)方，結(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)心，有朝一日你終會(huì)明白。

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