(call/cc (lambda (day-16) (day-16 "天下第一奇招 — Racket 的 Continuation — 2")))

2018鐵人賽

cchuang0425

2017-12-20 22:42:54

2535 瀏覽

天下第一奇招 — Racket 的 Continuation — 2

我們的第一個 continuation 應用
Racket 的 continuation 與 Scheme 的差別
左右互搏又來了！

1. 我們的第一個 continuation 應用

完成了昨天相當困難的解釋（解釋 Continuation 比解釋哲學還困難！）我們要來實作一些經典範例。首先先看這個範例程式：

(define check-negative
  (lambda (lst)
    (call/cc
      (lambda (esp)
        (for-each 
          (lambda (element)
            (if (< element 0)
              (esp element)
              (void)))
          lst)
        "no negative"))))

(define input1 '(1 2 5 -1 0 3))
(check-negative input1)

(define input2 '(1 2 3 4 5))
(check-negative input2)

還記得我們昨天第一個範例嗎：

(+ 5 (call/cc
       (lambda (escape)
         (escape 5))))  ;; 10

當我們把 5 傳給 escape 時，這時整個 expression 語義等於 (+ 5 5)，換句話說，這樣一個 Continuation 的結構，像是這樣的概念：((lambda (x) (+ 5 x)) 5)。因此，我們在這地方，先把剛剛的 check-negative 的函式忽略 continuation 的區塊，它長的像這樣：

(define check-negative
  (lambda (lst)
    ... ))

在 lambda 區塊裡，它這時處在尚未有任何計算過程的內容。於是我們把 call/cc 加進去：

(define check-negative
  (lambda (lst)
    (call/cc
      (lambda (escape)
        ... ))))

因此，這是一個像是這樣的函式：

((lambda (esp)
  (lambda (lst)
    esp)) ?)

於是我們再看下面的計算：

(for-each 
          (lambda (element)
            (if (< element 0)
              (esp element)
              (void)))
          lst)

這是一個典型的 for-each 迴圈，裡頭 iterate 每一個元素，如果發現它小於 0，就把它傳給 esp。這時候，如果我們發現了 input1 的 -1 時，我們便把它傳進 esp 裡，還記得昨天 R6RS 說到，esp 全名叫 escape procedure，因此它是一個 procedure，接受一個參數，這個參數就是整個 call/cc 的回傳值。而當 call/cc 回傳之後，整個 call/cc 的執行就結束了！換句話說，這個可以說是 Java 裡頭這樣的寫法：

List<int> input = Arrays.asList(1, 2, 5, -1, 0, 3);

for(int it : input){
    if(it < 0){
        return it;
    }
}

因為 Racket 與 Scheme 這類的語言，沒有 break 與 return 關鍵字，因此要執行上述的邏輯時，必須使用 Continuation 來完成，這就是經典的 non-local exit 範例。

2. Racket 的 continuation 與 Scheme 的差別

到目前為止，我們討論的都是 Scheme 的 Continuation 特性（？！）各位若有在 Racket 的文件裡看到資料，會發現 Racket 的 Continuation 全名不太一樣：call-with-composable-continuation。這差在哪裡呢？

我們先寫一段小程式來試試：

(+ 1 (+ 1 (+ 1 (call-with-current-continuation
                (lambda (cc)
                  (cc 0))))))

(+ 1 (+ 1 (+ 1 (call-with-composable-continuation
                (lambda (cc)
                  (cc 0))))))

執行之後，竟會發生這樣的結果：

3
3
  +: contract violation
  expected: number?
  given: #<void>
  argument position: 2nd
  other arguments...:
   1

回顧上一篇，我們可以知道第一個（簡稱 call/cc 的），結果會是 3。然而第二個，按理來說，應該也是 3，而它的確也是 3，但後續竟然發生錯誤？

雖然讀完了 Racket Guide [1]，其中解釋到 Racket 與 Scheme 在 Continuation 的實作觀點上的不同，但我還不太了解它的差異。不過倒發現了一件奇怪的事，按照 Racket Guide 上的說明，捕捉到 Composable Continuation 之後，可以進行更進一步的組合求值運算，但實際寫起來，卻不像文件所說的：

(define cc #f)
(define save-it!
  (lambda ()
    (call-with-composable-continuation
     (lambda (esp)
       (set! cc esp)
       0))))

(+ 1 (+ 1 (+ 1 (save-it!))))  ;; 保存 continuation

(cc 0)  ;; 3
(cc 1)  ;; 4
(cc (cc 0))  ;; 6?

當我們執行到最後一行後，程式發生了錯誤：

3
3
4
3
+: contract violation
  expected: number?
  given: #<void>
  argument position: 2nd
  other arguments...:

換句話說，最後一句是不行的，雖然在 DrRacket 下方的 REPL 操作時，從 保存 continuation 處開始執行，的確會顯示出 6 的結果。但在上方正規程式邏輯裡，卻會發生錯誤。嗯，同樣的，我也還不知道為什麼。

不過，就像 Haskell 銘言一般:

Don't sweat the stuff you don't understand immediately. Keep moving!
別在不懂的地方打轉，繼續讀下去！

3. 左右互搏又來了！

在 Wikipedia 上，有一篇很經典的範例 [2]，作者是 Racket 的開發者 Matthias Felleisen [3]，它是這樣寫的：

;; [LISTOF X] -> ( -> X u 'you-fell-off-the-end)
(define (generate-one-element-at-a-time lst)

  ;; Hand the next item from a-list to "return" or an end-of-list marker
  (define (control-state return)
    (for-each 
     (lambda (element)
               (set! return (call-with-current-continuation
                              (lambda (resume-here)
                                ;; Grab the current continuation
                               (set! control-state resume-here)
                               (return element)))))
     lst)
    (return 'you-fell-off-the-end))
  
  ;; (-> X u 'you-fell-off-the-end)
  ;; This is the actual generator, producing one item from a-list at a time
  (define (generator)
    (call-with-current-continuation control-state))

  ;; Return the generator 
  generator)

(define generate-digit
  (generate-one-element-at-a-time '(0 1 2)))

(generate-digit) ;; 0
(generate-digit) ;; 1
(generate-digit) ;; 2
(generate-digit) ;; you-fell-off-the-end

很複雜吧！我也覺得很複雜，為何說是左右互搏，我們先把程式改寫成本文的編程風格：

(define generate-one-element-at-a-time ;; [LISTOF X] ->
  (lambda (lst)                        ;; (-> X u 'you-fell-off-the-end)
    (define control-state  ;; Hand the next item from a-list
      (lambda (return)     ;; to "return" or an end-of-list marker
        (for-each 
         (lambda (element)
           (set! return (call/cc
                         (lambda (resume-here)
                           (set! control-state resume-here)  ;; Grab the 
                           (return element)))))              ;; current
         lst)                                                ;; continuation
        (return 'you-fell-off-the-end)))

    (define generator
      (lambda ()                   ;; (-> X u 'you-fell-off-the-end)
        (call/cc control-state)))  ;; This is the actual generator,
                                   ;; producing one item from a-list
                                   ;; at a time
    ;; Return the generator 
    generator))

(define generate-digit
  (generate-one-element-at-a-time '(0 1 2)))

(generate-digit) ;; 0
(generate-digit) ;; 1
(generate-digit) ;; 2
(generate-digit) ;; you-fell-off-the-end

這個程式真的很複雜，因此我們一條一條地來說明：

首先，我們看到執行時，每次呼叫 (generate-digit) ，都會將原本傳入的 list 拋一個元素出來，有的人會想，這有什麼? 我 new 一個 Generator 的物件也可以做到這件事。但再仔細想想，函式編程所強調的，便是函式在每次執行時，都是一個全新的狀態，輸入的參數，本身應當是不可變的，結果要不是回傳一個新的值，要不就是產生一些副作用。但現在在此處，我們竟然可以保存函式執行時的狀態！
來到 generate-digit 定義的地方，我們發現它的定義很奇怪: (generate-one-element-at-a-time '(0 1 2))，一般來說，Racket 的 define 所定義的，不是一個純量值(scalar)，就是一個函式，在這裡我們已經轉而使用 (lambda) 定義的風格來表式函式定義，這裡看起來 generate-digit 像是函式，又有點不像是函式，那是什麼？你在 REPL 裡直接叫用 generate-digit 一下就知道
我們在 REPL 裡直接叫用 generate-digit 時，出現了這樣的定義: #<procedure:generator>，一個名為 generator 的函式(procedure)。因此我們要往上看到 generate-one-element-at-a-time 的末了回傳，就是這個 generator 的 lambda。但它的內容是什麼呢？它是一個包裝了 call-with-current-continuation 的函式。於是，我們要來看本體了。
在 generate-one-element-at-a-time 函式裡，我們先不看參數 lst，它的結構說長不長，說短不短，也就是三段，但定義了兩個 lambda，最後回傳其中一個。這有什麼魔法呢？
從 generator 這個 lambda 中，可以發現，control-state 是一個被當成 Continuation 參數的 lambda，而這個 control-state 裡頭，放了個 for-each，用以迭代操作 generate-digit 傳入的 list 內容。這個 for-each 怎麼操作呢？

我們從這篇第一個範例，看到了 non-local exit 的機制，透過 for-each 巡訪 list 的內容，而當判斷到目標值後，將值傳給 escape procedure，以退出這個迴圈操作，因此，我們先把 for-each 裡面的 call/cc 拿掉，會變成什麼樣子：

(define generate-one-element-at-a-time
  (lambda (lst)
    (define control-state
      (lambda (return)
        (for-each 
        (lambda (element)
          (return element))
        lst)
        (return 'you-fell-off-the-end)))

    (define generator
      (lambda ()
        (call/cc control-state)))

    generator))

當我們把 for-each 裡的 call/cc 拿掉後，我們每次呼叫 generate-digit 就只會顯示這 list 的第一個元素，因為每次呼叫時，for-each 都從頭開始執行，然後傳入第一個元素給 return 後，就啟動了 non-local exit 機制。
因此，我們回頭看原本的程式後，可以發現 for-each 執行時，有一個 call/cc，換句話說，這邊有一個機制，告訴 for-each：等等，執行下去前先等一下。然後在這裡，把 for-each 的 escape procedure assign 給 control-state，然後像剛剛那樣子，把一個 element 傳給 return 這個 escape procedure
第一次叫用 for-each 時，是這樣。那第二次呢？因為 control-state 這個 id 已經被 assign 給剛剛 for-each 的 escape procedure: resume-here，因此等於是把 resume-here 丟進 call/cc 區塊裡，於是我們穿過時光遂道，到了 for-each 上回執行完的那個當下。
這時 for-each 傳入第二個元素，依此類推，直到 list 的元素用完後。for-each 結束後，resume-here 不再有作用，就來到了 (return 'you-fell-off-the-end) 這句。

為什麼說這是一個左右互搏，因為在這個結構中，我們使用了兩個 Continuation 彼此呼叫，以達成 generator 的目的。後來，我們再深入思考看看，當一個值被傳進 Continuation 的 escape procedure 時，會啟動一個 abort 程序，使得程式的流程可以從中間跳開，那麼在 for-each 裡，第一個 (set! return ....) 有作用嗎？嗯，我的直覺是沒作用，後來我試過，把它拿掉，只剩下 call/cc，的確可以執行。各位可以試試。

最後我們看一個讓各位燒腦燒過年的例子 [4]：

(let* [(yin ((lambda (foo) (newline) foo)
             (call/cc (lambda (bar) bar))))
       (yang ((lambda (foo) (display "*") foo)
              (call/cc (lambda (bar) bar))))]
  (yin yang))

它會出現什麼結果呢？