第十三章 跳轉
=============
Scheme的一個顯著標志是它支持跳轉或者`nonlocal control`。特別是Scheme允許程序控制跳轉到程序的任意位置，相比之下條件語句和函數調用的限制要更多一些。Scheme的`nonlocal control`操作符是一個名為`call-with-current-continuation`的過程。下面我們會看到如何用這個操作符創建一些驚人的控制效果。
## 13.1 call-with-current-continuation
`call-with-current-continuation`用`current-continuation`來調用它的參數（一個只有一個參數的過程）【在調用時傳入參數`current-continuation`，譯者注】。這就是這個操作符名字的解釋了。但是由于這個名字太長，故通常縮寫為`call/cc`[1]。
一個程序執行到任意一點的當前續延【即`current-continuation`，譯者注】是該程序的后半部分【即將要被執行的部分，譯者注】。因此在程序：
```scheme
(+ 1 (call/cc
(lambda (k)
(+ 2 (k 3)))))
```
中，“后邊部分”——從`call/cc`程序的角度來看，是如下的帶有一個“洞”的程序（“洞”用`[]`表示）：
```scheme
(+ 1 [])
```
也就是說，該程序的“續延”是一個把`1`和填到這個“洞”里的東西加起來的程序。
這就是`call/cc`參數被調用的情況。記住`call/cc`的參數是過程：
```scheme
(lambda (k)
(+ 2 (k 3)))
```
這個過程的把“續延”（現在綁定在`k`上）`apply`到參數`3`上。這就是這個續延與眾不同之處。“續延”調用突然放棄了它自己的計算并把當前的計算換成了`k`中保存的程序。也就是說，這個程序中加`2`的操作被放棄了，然后`k`的參數`3`直接被發送到了那個帶“洞”的程序：
```scheme
(+ 1 [])
```
然后程序就簡單的變成：
```scheme
(+ 1 3)
```
然后返回`4`。即：
```scheme
(+ 1 (call/cc
(lambda (k)
(+ 2 (k 3)))))
```
上面的例子叫做“‘退出’續延”，用來退出某個計算過程（這里是`(+ 2 [])`的計算）。這是一個很有用的功能，但是Scheme的續延可以用來返回到前面放棄計算的地方，然后多次調用它們。程序的“后半部分”意味著一個續延不論我們調用的次數和時間都存在，這也讓`call/cc`更加強大和令人迷惑。看一個簡單的例子，在解釋器里輸入以下代碼：
```scheme
(define r #f)
(+ 1 (call/cc
(lambda (k)
(set! r k)
(+ 2 (k 3)))))
=> 4
```
后面的表達式和剛才一樣返回了`4`，不同之處在于這次我們把續延`k`保存到了全局變量`r`里。
現在我們在`r`中永久保存了這個續延。如果我們以一個數字為參數調用它，就會返回數字加1后的結果：
```scheme
(r 5)
=> 6
```
注意`r`會放棄它自己的續延，打個比方我們把對`r`的調用放在一個上下文中：
```scheme
(+ 3 (r 5))
=> 6
```
因此`call/cc`提供的續延是一種“放棄”的續延。
## 13.2 “退出”續延
“退出”續延是`call/cc`最簡單的用法，而且在退出函數或循環時非常有用。考慮一個過程`list-product`接收一個數字列表并把所有的數乘起來。一個直觀的遞歸定義可以這樣寫：
```scheme
(define list-product
(lambda (s)
(let recur ((s s))
(if (null? s) 1
(* (car s) (recur (cdr s)))))))
```
這個方法有一個問題。如果列表中有一個數是0，而且0后面還有很多元素，那么結果是可以預知的。如果這樣上面的代碼會在得出結果前產生很多無意義的遞歸調用。這就是“退出”續延大顯身手的時候。用`call/cc`，我們可以這樣重寫這個過程：
```scheme
(define list-product
(lambda (s)
(call/cc
(lambda (exit)
(let recur ((s s))
(if (null? s) 1
(if (= (car s) 0) (exit 0)
(* (car s) (recur (cdr s))))))))))
```
如果遇到一個為0的元素，續延`exit`就會以參數0被調用，這樣就防止了更多的調用`recur`。
## 13.3 樹匹配
一個更加復雜的例子是把續延用于解決兩個樹是否有相同邊緣（就是相同的元素（葉節點）有相同的順序）的問題上。如：
```scheme
(same-fringe? '(1 (2 3)) '((1 2) 3))
=> #t
(same-fringe? '(1 2 3) '(1 (3 2)))
=> #f
```
純粹的函數式解決方案是把兩個樹都抹平然后看結果是否一樣。
```scheme
(define same-fringe?
(lambda (tree1 tree2)
(let loop ((ftree1 (flatten tree1))
(ftree2 (flatten tree2)))
(cond ((and (null? ftree1) (null? ftree2)) #t)
((or (null? ftree1) (null? ftree2)) #f)
((eqv? (car ftree1) (car ftree2))
(loop (cdr ftree1) (cdr ftree2)))
(else #f)))))
(define flatten
(lambda (tree)
(cond ((null? tree) '())
((pair? (car tree))
(append (flatten (car tree))
(flatten (cdr tree))))
(else
(cons (car tree)
(flatten (cdr tree)))))))
```
然而，這樣會遍歷整個樹來進行抹平操作，而且還要再做一遍這樣的操作【遍歷被抹平后生成的列表，譯者注】才能找到不匹配的元素。退一步講，即使最好的抹平算法也需要`cons`（直接修改輸入的樹是不可以的）
我們可以用`call/cc`來解決這個問題，不需要遍歷，也不需要用`cons`來拼接。每個樹會被`map`到一個生成器——一個帶有內部狀態的過程，按照葉節點在樹中出現的順序從左到右連續的輸出葉節點。
```scheme
(define tree->generator
(lambda (tree)
(let ((caller '*))
(letrec
((generate-leaves
(lambda ()
(let loop ((tree tree))
(cond ((null? tree) 'skip)
((pair? tree)
(loop (car tree))
(loop (cdr tree)))
(else
(call/cc
(lambda (rest-of-tree)
(set! generate-leaves
(lambda ()
(rest-of-tree 'resume)))
(caller tree))))))
(caller '()))))
(lambda ()
(call/cc
(lambda (k)
(set! caller k)
(generate-leaves))))))))
```
當一個`tree->generator`創建的生成器被調用時，這個生成器會把調用的續延存在`caller`中，這樣它就知道當找到葉節點時把它發送給誰。然后它調用一個內部定義的函數`generate-leaves`，該函數會從左到右循環遍歷這個樹。當循環到一個葉節點時，該函數就使用`caller`來返回該葉節點作為生成器的結果，但是它會記住后續的循環（被`call/cc`捕獲為一個續延）并保存到`generate-leaves`變量，下次生成器被調用時，循環從剛才終端的地方恢復，這樣它可以尋找下一個葉節點。
注意`generate-leaves`做的最后一件事情，在循環結束后，它返回一個空列表給`caller`。由于空列表不是一個合法的葉節點，我們可以用它來告訴生成器沒有葉節點需要生成了。
過程`same-fringe?`把樹作為參數來創建生成器，然后交替調用這兩個生成器。只要一找到兩個不同的葉節點就會返回失敗。
```scheme
(define same-fringe?
(lambda (tree1 tree2)
(let ((gen1 (tree->generator tree1))
(gen2 (tree->generator tree2)))
(let loop ()
(let ((leaf1 (gen1))
(leaf2 (gen2)))
(if (eqv? leaf1 leaf2)
(if (null? leaf1) #t (loop))
#f))))))
```
很容易看到每個樹只被遍歷了最多一次，在遇到不匹配的情況時，只會遍歷最左邊的那個不匹配節點【？】。而且沒有用到`cons`。
## 13.4 協程
上面用到的生成器是一些有趣而普遍的過程概念。每次生成器被調用時，它都恢復計算，而且當它返回前會把它的續延保存在一個內部變量中這樣這個生成器可以再次恢復。我們可以對生成器進行推廣，這樣他們可以相互恢復其他的生成器，并且互相傳遞結果。這樣的過程叫協程。
我們將會看到一個協程作為一元過程，其主體可以包含`resume`調用，`resume`是一個兩參數的過程，可以被一個協程用來繼續執行另一個協程（帶著一個轉換值）。宏`coroutine`定義一個這樣的協程過程，一個變量名作為協程的初始參數，內容作為協程。
```scheme
(define-macro coroutine
(lambda (x . body)
`(letrec ((+local-control-state (lambda (,x) ,@body))
(resume
(lambda (c v)
(call/cc
(lambda (k)
(set! +local-control-state k)
(c v))))))
(lambda (v)
(+local-control-state v)))))
```
調用這個宏可以創建一個協程（我們叫為`A`），這個協程可以有一個參數。`A`有一個內部變量叫做`+local-control-state`來保存任意時刻這個協程接下來的計算。當調用`resume`時——也就是調用另一個協程`B`時——當前協程會更新它的`+local-control-state`變量為之后的計算，然后停止，然后跳到恢復了的協程`B`，當協程`A`之后恢復時，它的計算會從它`+local-control-state`變量里存放的續延開始。
### 13.4.1 用協程進行樹匹配
用協程會進一步簡化樹匹配的操作。匹配過程被編寫為一個協程，該協程依賴另外兩個協程提供各自的葉節點。
```scheme
(define make-matcher-coroutine
(lambda (tree-cor-1 tree-cor-2)
(coroutine dont-need-an-init-arg
(let loop ()
(let ((leaf1 (resume tree-cor-1 'get-a-leaf))
(leaf2 (resume tree-cor-2 'get-a-leaf)))
(if (eqv? leaf1 leaf2)
(if (null? leaf1) #t (loop))
#f))))))
```
葉生成器協程會記住把它的節點返回給誰：
```scheme
(define make-leaf-gen-coroutine
(lambda (tree matcher-cor)
(coroutine dont-need-an-init-arg
(let loop ((tree tree))
(cond ((null? tree) 'skip)
((pair? tree)
(loop (car tree))
(loop (cdr tree)))
(else
(resume matcher-cor tree))))
(resume matcher-cor '()))))
```
現在過程`same-fringe?`可以這樣寫：
```scheme
(define same-fringe?
(lambda (tree1 tree2)
(letrec ((tree-cor-1
(make-leaf-gen-coroutine
tree1
matcher-cor))
(tree-cor-2
(make-leaf-gen-coroutine
tree2
matcher-cor))
(matcher-cor
(make-matcher-coroutine
tree-cor-1
tree-cor-2)))
(matcher-cor 'start-ball-rolling))))
```
不幸的是Scheme的`letrec`語句如果想解析它引入的詞法變量的相互遞歸調用，必須得把這個引用包圍在一個`lambda`里。所以我們得這么寫：
```scheme
(define same-fringe?
(lambda (tree1 tree2)
(letrec ((tree-cor-1
(make-leaf-gen-coroutine
tree1
(lambda (v) (matcher-cor v))))
(tree-cor-2
(make-leaf-gen-coroutine
tree2
(lambda (v) (matcher-cor v))))
(matcher-cor
(make-matcher-coroutine
(lambda (v) (tree-cor-1 v))
(lambda (v) (tree-cor-2 v)))))
(matcher-cor 'start-ball-rolling))))
```
注意在這個版本的`same-fringe`里完全沒有調用`call/cc`的痕跡。宏`coroutine`幫助我們處理了所有的協程。
-----------------
[1]: 如果你的Scheme沒有`call/cc`這個縮寫，那么在你的初始化代碼里加入`(define call/cc call-with-current-continuation)`，這樣可以減少敲擊鍵盤造成的手部勞損：）
