關(guān)于
本文是系列文章中的第八篇扣墩，
在上一篇中塞祈，我們介紹了continuation的概念级解，還介紹了Lisp中威力強大的call/cc，它提供了first-class continuation熄攘，最后我們用call/cc實現(xiàn)了python中的generator和yield。
call/cc賦予了我們很強的表達(dá)能力彼念，Lisp中的異常處理機制也很人性化挪圾。
例如，Common Lisp: Condition_system逐沙，
由于call/cc可以捕捉到異常處的continuation哲思，
我們就可以手動調(diào)用這個continuation，
讓程序從錯誤的位置以給定狀態(tài)重新開始執(zhí)行吩案，
甚至結(jié)合REPL還可以詢問用戶棚赔，讓用戶輸入這個狀態(tài)。
其他語言的try/catch是無法做到這一點的务热，
我們拿到錯誤時忆嗜，出現(xiàn)錯誤的那個環(huán)境已經(jīng)被丟棄了，無法恢復(fù)崎岂，
那么除了提示用戶程序崩潰了就沒有別的辦法了捆毫。
call/cc這么強大，更堅定了我們實現(xiàn)它的想法冲甘，
本文就從實現(xiàn)的角度來看call/cc绩卤。
尾調(diào)用
In computer science, a tail call is a subroutine call performed as the final action of a procedure.
如果在某個函數(shù)的末尾調(diào)用了另一個函數(shù)，這個調(diào)用就稱為尾調(diào)用江醇。
我們舉個例子吧濒憋，
(define (f a)
(display a)
(g 2))
(define (g b)
(display b))
(f 1)
我們看到，函數(shù)f的末尾調(diào)用了函數(shù)g陶夜，(g 2)凛驮。
尾調(diào)用有什么好處呢？
一個基本的事實是条辟，如果g是f的尾調(diào)用黔夭，g就可以不返回到f中，
而直接返回到f該返回的地方羽嫡。
因為g是f的尾調(diào)用本姥，g后面沒有其他調(diào)用了，
(g 2)調(diào)用結(jié)束后就可以不必返回到f的函數(shù)體中了杭棵，而是直接返回到(f 1)處婚惫。
因此，調(diào)用g的時候，調(diào)用椣认希可以不增加艰管，而是直接廢棄f的調(diào)用環(huán)境即可。
注意蒋川，我們上面提到的是『不必返回到f的函數(shù)體中』蛙婴，
因為不是每個語言都可以做到這一點，
這個語言特性尔破，稱為尾調(diào)用優(yōu)化（tail call optimization）街图。
調(diào)用棧和調(diào)用圖
調(diào)用棧對我們來說是一個耳熟能詳?shù)拿~，
可是我們有沒有考慮過懒构，為什么調(diào)用構(gòu)成了一個『棽图茫』呢？
有這么多的數(shù)據(jù)結(jié)構(gòu)胆剧，為什么不是一個隊列絮姆，不是一個樹，不是一個圖呢秩霍？
是因為函數(shù)的調(diào)用和返回機制篙悯，恰好可以用幀（frame）的壓棧和彈棧來描述。
可是铃绒，尾調(diào)用優(yōu)化鸽照，開始動搖了這一點，
為了能返回到調(diào)用者該返回的地方颠悬，調(diào)用棧有的時候可能會彈出兩次矮燎，或者彈出更多次。
進(jìn)一步赔癌，我們再來看call/cc的場景诞外，它使得程序可以直接跳轉(zhuǎn)到之前的某個狀態(tài)，
根本上改變了壓棧彈棧的規(guī)則灾票，跳過去以后峡谊，以全新的狀態(tài)重新開始執(zhí)行。
然而刊苍，發(fā)生跳轉(zhuǎn)時的狀態(tài)還不能丟棄既们，因為有可能再跳回來。
因此班缰，call/cc讓調(diào)用不再構(gòu)成一個棧贤壁，而是構(gòu)成了一個調(diào)用圖悼枢。
CPS
在這些復(fù)雜場景中埠忘，為了能顯式的表示執(zhí)行過程，
將程序轉(zhuǎn)化為CPS（continuation passing style）是一種常用的辦法，
CPS是一種程序的書寫風(fēng)格莹妒，經(jīng)常作為編譯器的一種中間表示名船。（IR
; 調(diào)用風(fēng)格
(define (f x)
(+ (g x) 1))
(define (g x)
(* x 2))
(f 1)
; CPS
(define (f x cont)
(g x (lambda (v)
(cont (+ v 1)))))
(define (g x cont)
(cont (* x 2)))
(f 1 display)
我們發(fā)現(xiàn)寫成CPS之后，每個函數(shù)多了一個cont參數(shù)旨怠，
用來表示該函數(shù)調(diào)用表達(dá)式的continuation渠驼，
我們調(diào)用一個函數(shù)，就應(yīng)該把它相應(yīng)的continuation顯式的傳給它鉴腻。
例如迷扇，我們在f中調(diào)用了g，那么我們就將(g x)的continuation傳給了g爽哎，即(lambda (v) (cont (+ v 1)))蜓席。
除此之外，我們還發(fā)現(xiàn)课锌，CPS是一個尾調(diào)用形式厨内，
因此程序的執(zhí)行就變成了continuation的不斷變換生長。
開始動手術(shù)
為了實現(xiàn)call/cc渺贤，首先我們要把解釋器改造成CPS形式雏胃，
然后再將continuation拿出來包裝一下，提供給用戶使用志鞍。
我們先進(jìn)行第一步改造瞭亮，CPS，
回憶一下固棚，為了實現(xiàn)詞法作用域街州，我們給解釋器中每個函數(shù)末尾加上了參數(shù)env，用于表示被求值表達(dá)式的環(huán)境玻孟。這次也相似唆缴，我們給每個函數(shù)加上了新的參數(shù)cont，用于表示被求值表達(dá)式的continuation黍翎，這樣我們就可以將解釋器改造成CPS形式了面徽。
下一步改造我們要實現(xiàn)call/cc了，它直接使用了這些包含cont參數(shù)的函數(shù)匣掸，限于篇幅趟紊，CPS形式的解釋器我們就略過了，這里我們只是先看一下handle-decision-tree的樣子吧碰酝，
(define (handle-decision-tree tree exp env cont)
(if (null? tree)
(error 'handle-decision-tree "failed to make decision")
(let* ((head (car tree))
(predicator (car head))
(decision (cadr head)))
(predicator exp env
(lambda (predicate-result)
(if predicate-result
(if (not (list? decision))
(decision exp env cont)
(handle-decision-tree decision exp env cont))
(handle-decision-tree (cdr tree) exp env cont)))))))
實現(xiàn)call/cc
將解釋器轉(zhuǎn)換成CPS之后霎匈，我們就可以將cont進(jìn)行包裝了，
下面的實現(xiàn)中送爸，我們將cont包裝成了一個內(nèi)部的數(shù)據(jù)結(jié)構(gòu)continuation铛嘱。
（和閉包一樣暖释，continuation從實現(xiàn)的角度來看也是一個數(shù)據(jù)結(jié)構(gòu)
然后，把這個數(shù)據(jù)結(jié)構(gòu)提供給用戶墨吓，就可以讓用戶代碼實現(xiàn)自定義跳轉(zhuǎn)了球匕。
為了實現(xiàn)這一點，我們在解釋器中判斷是否調(diào)用了continuation帖烘，來做相應(yīng)的處理亮曹。
handle-decision-tree增加了兩個分支，is-continuation?秘症，is-continuation-call?照卦。
#lang racket
; tool
(struct closure
(param body env))
(struct continuation
(cont))
(define (create-frame)
(make-hash))
(define (extend-frame frame key value)
(hash-set! frame key value))
(define (extend-env env frame)
(cons frame env))
(define (get-symbol-value env key)
(let lookup-env
((env env))
(if (null? env)
(error 'get-symbol-value "failed to find symbol")
(let ((head-frame (car env)))
(if (hash-has-key? head-frame key)
(hash-ref head-frame key '())
(lookup-env (cdr env)))))))
(define (handle-decision-tree tree exp env cont)
(if (null? tree)
(error 'handle-decision-tree "failed to make decision")
(let* ((head (car tree))
(predicator (car head))
(decision (cadr head)))
(predicator exp env
(lambda (predicate-result)
(if predicate-result
(if (not (list? decision))
(decision exp env cont)
(handle-decision-tree decision exp env cont))
(handle-decision-tree (cdr tree) exp env cont)))))))
; env & cont
(define *env* `(,(create-frame)))
(define *cont* (lambda (v)
(display v)))
; main
(define (eval-exp exp env cont)
(handle-decision-tree
`((,is-symbol? ,eval-symbol)
(,is-self-eval-exp? ,eval-self-eval-exp)
(,is-continuation? ,eval-continuation)
(,is-list?
((,is-lambda? ,eval-lambda)
(,is-call/cc? ,eval-call/cc)
(,is-continuation-call? ,eval-continuation-call)
(,is-function-call-list? ,eval-function-call-list))))
exp env cont))
(define (is-symbol? exp env cont)
(display "is-symbol?\n")
(cont (symbol? exp)))
(define (eval-symbol exp env cont)
(display "eval-symbol\n")
(cont (get-symbol-value env exp)))
(define (is-self-eval-exp? exp env cont)
(display "is-self-eval-exp?\n")
(cont (number? exp)))
(define (eval-self-eval-exp exp env cont)
(display "eval-self-eval-exp\n")
(cont exp))
(define (is-continuation? exp env cont)
(display "is-continuation?\n")
(cont (continuation? exp)))
(define (eval-continuation exp env cont)
(display "eval-continuation\n")
(cont exp))
(define (is-list? exp env cont)
(display "is-list?\n")
(cont (list? exp)))
(define (is-lambda? exp env cont)
(display "is-lambda?\n")
(cont (eq? (car exp) 'lambda)))
(define (eval-lambda exp env cont)
(display "eval-lambda\n")
(let ((param (caadr exp))
(body (caddr exp)))
(cont (closure param body env))))
(define (is-call/cc? exp env cont)
(display "is-call/cc?\n")
(cont (eq? (car exp) 'call/cc)))
(define (eval-call/cc exp env cont)
(display "eval-call/cc\n")
(let ((fn (cadr exp))
(data-cont (continuation cont)))
(eval-function-call-list `(,fn ,data-cont) env cont)))
(define (is-continuation-call? exp env cont)
(display "is-continuation-call?\n")
(eval-exp (car exp) env
(lambda (value)
(cont (continuation? value)))))
(define (eval-continuation-call exp env cont)
(display "eval-continuation-call\n")
(eval-exp (car exp) env
(lambda (data-cont)
(let ((wrapped-cont (continuation-cont data-cont)))
(eval-exp (cadr exp) env
(lambda (arg)
(wrapped-cont arg)))))))
(define (is-function-call-list? exp env cont)
(display "is-function-call-list?\n")
(cont #t))
(define (eval-function-call-list exp env cont)
(display "eval-function-call-list\n")
(eval-exp (car exp) env
(lambda (clos)
(eval-exp (cadr exp) env
(lambda (arg)
(let ((body (closure-body clos))
(lexical-env (closure-env clos))
(param (closure-param clos))
(frame (create-frame)))
(extend-frame frame param arg)
(let ((executing-env (extend-env lexical-env frame)))
(eval-exp body executing-env cont))))))))
測試
(eval-exp '1 *env* *cont*)
(display "\n\n")
(eval-exp '(lambda (x) x)
*env* *cont*)
(display "\n\n")
(eval-exp '((lambda (x) x)
1)
*env* *cont*)
(display "\n\n")
(eval-exp '((lambda (x)
((lambda (y) x)
2))
1)
*env* *cont*)
(display "\n\n")
(eval-exp '((lambda (x)
((lambda (f)
((lambda (x)
(f 3))
2))
(lambda (z) x)))
1)
*env* *cont*)
(display "\n\n")
(eval-exp '(call/cc (lambda (k)
1))
*env* *cont*)
(display "\n\n")
(eval-exp '(call/cc (lambda (k)
(k 2)))
*env* *cont*)
要點分析
（1）eval-call/cc時會創(chuàng)建一個continuation，
然后用這個continuation作為參數(shù)調(diào)用call/cc的參數(shù)乡摹。
（call/cc的參數(shù)窄瘟，就是后面的(lambda (k) 1)，因此k就是這個continuation
; (call/cc (lambda (k) 1))
(define (eval-call/cc exp env cont)
(display "eval-call/cc\n")
(let ((fn (cadr exp))
(data-cont (continuation cont)))
(eval-function-call-list `(,fn ,data-cont) env cont)))
（2）eval-continuation-call會解開continuation的包裝趟卸，得到內(nèi)部包含的cont蹄葱，
然后用這個cont作為參數(shù)求值表達(dá)式，
這樣就實現(xiàn)了锄列，表達(dá)式求值完以后跳轉(zhuǎn)到產(chǎn)生cont位置的效果图云。
(define (eval-continuation-call exp env cont)
(display "eval-continuation-call\n")
(eval-exp (car exp) env
(lambda (data-cont)
(let ((wrapped-cont (continuation-cont data-cont)))
(eval-exp (cadr exp) env
(lambda (arg)
(wrapped-cont arg)))))))
（3）(call/cc ...)表達(dá)式中，如果k沒有被調(diào)用邻邮，那么(call/cc ...)的值竣况，就是call/cc參數(shù)函數(shù)的返回值，即(call/cc (lambda (k) 1)) = 1筒严。
這一點看起來很難實現(xiàn)丹泉，實則不然。
我們只需要巧妙的指定(lambda (k) 1)的continuation鸭蛙，
讓它就是(call/cc (lambda (k) 1))的continuation即可摹恨。
這一點體現(xiàn)在eval-call/cc中，我們直接將cont原封不動的傳給了eval-function-call-list
(define (eval-call/cc exp env cont)
...
(eval-function-call-list `(,fn ,data-cont) env cont)))
下文
Lisp語言真是博大精深娶视，寫到這里我們甚至還沒有提及它最重要的語言特性——宏晒哄，
Lisp宏提供了一種元編程的手段，同像性讓Lisp元編程異常強大肪获，
然而寝凌，把宏說清楚也頗費筆墨，因此孝赫，我打算在適當(dāng)?shù)臅r候單獨討論它较木。
本系列標(biāo)題為『柯里化的前生今世』，意在通過柯里化引入種種有趣的概念青柄，
目前為止伐债，我們討論了高階函數(shù)预侯，閉包，continuation泳赋，這些可以看做『柯里化的前生』，
我們不但理解了這些概念喇喉，還實現(xiàn)了它們祖今，算是小有收獲吧。
使用Racket也有一段日子了拣技，對它也逐漸從陌生到熟悉千诬，
可是偏執(zhí)卻容易讓人誤入歧途，錯過其他風(fēng)景膏斤，
下文我們將開啟新的旅程了徐绑，Let's go !
參考
continuation passing style
Compiling with Continuations
An Introduction to Scheme and its Implementation
