愉悅的scheme之旅(4)--Delimited Continuations

前言

我以前也寫過一篇介紹的delimited continuation的文章，但是只在我的群裡面發過。今天，把它翻出來，進行修訂，補充。

當然，由於本人水平有限，如有錯誤還請指出。

shift/reset初介紹

scheme中談的最多的控制流結構，肯定是callcc。雖然callcc這種full continuation很強大，但有的時候並不實用，與此相對的delimited continuation（除callcc外的一般都是，又稱partial continuation）卻實用很多。

這篇文章主要介紹racket中的delimited continuation：shift/reset

首先，在racket裡面加入：

(require racket/control)n

然後開始測試下面的代碼：

(reset 1) n(reset (+ 1 2)) n

結果分別是1和3，因此我們可以推導出當只存在reset的時候 (reset E) => E

shift的形式，(shift k E) k代表continuation，E代表表達式，並且shift只能在reset塊內使用。

(reset (+ shift k 2) 3)n

這段代碼的結果為2，可以看到，我們完全忽略了那個k，並且，shift具有非本地退出的作用。

(reset (... shift k E) ...)=> E

那麼k是什麼呢，k是限制在reset範圍內的continuation。

callcc捕獲的continuation，一般是全局範圍內的，比如下面的代碼：

(+ 2 (+ 1 (call/cc (lambda (k) (k 1)))))n

可以看到 k=(lambda (x) (+ 2 (+1 x))),並且沒有任何範圍限制，而對於shift來說，reset就是用來限制shift捕獲範圍的工具。

(reset (+ 2 (+ 1 (shift k (k 1)))))n

k=(lambda (x) (reset (+ 2 (+ 1 x))))

(+ 2 (reset (+ 1 (shift k (k 1)))))n

k=(lambda (x) (reset (+ 1 x)))

(+ 2 (+ 1 (reset (shift k (k 1)))))n

k=(lambda (x) (reset x))

除了捕獲範圍的區別，shift/reset和call/cc相比沒有逃逸性，也就是你call一個callcc所捕獲的continuation，就不會返回了，而call一個shift/reset產生的continuation照樣會正常返回。

(define escaper (void))n(call/cc (lambda (k) (set! escaper k)))n(+ 1 (escaper 3))n

這段代碼中，escaper=(lambda (x) x),我們調用escaper，會直接跳轉continuation所在位置，而不會返回值與1相加，下面我們看看shift/reset是怎樣的表現。

(require racket/control)n(define escaper (void))n(reset (shift k (set! escaper k)))n(+ 1 (escaper 3))n

返回了我們期望的4，也就是說callcc所捕獲的continuation，你是不可以把它當函數看的，而shift/reset可以，因為函數比較方便組合，所以shift/reset實用性更高。

測試：寫出下面代碼的執行結果

(+ 1 (reset (+ 2 (shift k (k (k 2))))))n

(reset (+ 1 (shift a (a 1)) (shift b (b (b 1)))))n

如果你能想到答案，就繼續往下看。

yield return -- callcc所帶來的問題

我曾經看過一個人用callcc實現yield return（generator），就excited不行了，現在看看，那個時候還是too young too simple，sometimes naive。

請看代碼:

(define (make-generator lst)n (define (control return)n (for-each (lambda (e)n (call/cc (lambda (r)n (set! control r)n (return e)))) lst))n (define (generator) (call/cc control))n generator)n(define a (make-generator (1 2 3 4)))n(a)n(a)n(a)n(a)n

的確是很美妙的代碼，但是還是存在問題的，比如說你把(a)換成(cons (a) (a))試一試。

並不能得到期望的(1 . 2)，而是陷入了死循環！！

原因就是callcc非常的dirty，既不限制捕獲範圍，生成的continuation又不是函數。

(require racket/control)n(define (make-generator lst)n (define (control)n (reset (for-each (lambda (x)n (shift k (set! control (lambda () (k (void)))) x))n lst)))n (lambda () (control)))n(define a (make-generator (1 2 3 4)))n(cons (a) (a))n

shift/reset大勝利！

奇淫技巧--用shift/reset實現的演算法

cps變換是一種經典的演算法，一般實現它需要把函數寫成continuation-passing-style的樣子，看wangyin的那40行代碼就明白了，哎，你說什麼？用shift/reset可以寫的更簡單！

(define (cps exp)n (match expn [(? symbol? x) x]n [`(lambda (,x) ,expr) `(lambda (,x k)n ,(reset `(k ,(cps expr))))]n [`(,rator ,rand) (let ((t (gensym)))n (shift kn `(,(cps rator) ,(cps rand) (lambda (,t) ,(k t)))))]))n(cps (lambda (x) (lambda (y) ((x x) (y y)))))n

這段代碼可是花了我好長時間才想出來的。

感謝@qww6 指出的問題，這段代碼中的錯誤已經修復。

最後

還需要更新。