Continuation

Continuation

continuation對于編程，就像是達(dá)芬奇密碼對于人類歷史一樣：它揭開了人類有史以來最大的謎團(tuán)。好吧，也許沒有那么夸張，不過它們的影響至少和當(dāng)年發(fā)現(xiàn)負(fù)數(shù)有平方根不相上下。

我們對函數(shù)的理解只有一半是正確的，因?yàn)檫@樣的理解基于一個錯誤的假設(shè)：函數(shù)一定要把其返回值返回給調(diào)用者。按照這樣的理解，continuation就是更加廣義的函數(shù)。這里的函數(shù)不一定要把返回值傳回給調(diào)用者，相反，它可以把返回值傳給程序中的任意代碼。continuation就是一種特別的參數(shù)，把這種參數(shù)傳到函數(shù)中，函數(shù)就能夠根據(jù)continuation將返回值傳遞到程序中的某段代碼中。說得很高深，實(shí)際上沒那么復(fù)雜。直接來看看下面的例子好了：

int i = add(5, 10);
int j = square(i);

add這個函數(shù)將返回15然后這個值會賦給i，這也是add被調(diào)用的地方。接下來i的值又會被用于調(diào)用square。請注意支持惰性求值的編譯器是不能打亂這段代碼執(zhí)行順序的，因?yàn)榈诙€函數(shù)的執(zhí)行依賴于第一個函數(shù)成功執(zhí)行并返回結(jié)果。這段代碼可以用Continuation Pass Style（CPS）技術(shù)重寫，這樣一來add的返回值就不是傳給其調(diào)用者，而是直接傳到square里去了。

int j = add(5, 10, square);

在上例中，add多了一個參數(shù)：一個函數(shù)，add必須在完成自己的計(jì)算后，調(diào)用這個函數(shù)并把結(jié)果傳給它。這時square就是add的一個continuation。上面兩段程序中j的值都是225。

這樣，我們學(xué)習(xí)到了強(qiáng)制惰性語言順序執(zhí)行兩個表達(dá)式的第一個技巧。再來看看下面IO程序（是不是有點(diǎn)眼熟？）：

System.out.println("Please enter your name: ");
System.in.readLine();

這兩行代碼彼此之間沒有依賴關(guān)系，因此編譯器可以隨意的重新安排它們的執(zhí)行順序。可是只要用CPS重寫它，編譯器就必須順序執(zhí)行了，因?yàn)橹貙懞蟮拇a存在依賴關(guān)系了。

 System.out.println("Please enter your name: ", System.in.readLine);

這段新的代碼中println需要結(jié)合其計(jì)算結(jié)果調(diào)用readLine，然后再返回readLine的返回值。這使得兩個函數(shù)得以保證按順序執(zhí)行而且readLine總被執(zhí)行（這是由于整個運(yùn)算需要它的返回值作為最終結(jié)果）。Java的println是沒有返回值的，但是如果它可以返回一個能被readnLine接受的抽象值，問題就解決了?。ㄗg者：別忘了，這里作者一開始就在Java的基礎(chǔ)上修改搭建自己的語言）當(dāng)然，如果一直把函數(shù)按照這種方法串下去，代碼很快就變得不可讀了，可是沒有人要求你一定要這樣做?？梢酝ㄟ^在語言中添加語法糖的方式來解決這個問題，這樣程序員只要按照順序?qū)懘a，編譯器負(fù)責(zé)自動把它們串起來就好了。于是就可以任意安排代碼的執(zhí)行順序而不用擔(dān)心會失去FP帶來的好處了（包括可以用數(shù)學(xué)方法來分析我們的程序）！如果到這里還有人感到困惑，可以這樣理解，函數(shù)只是有唯一成員的類的實(shí)例而已。試著重寫上面兩行程序，讓println和readLine編程這種類的實(shí)例，所有問題就都搞清楚了。
到這里本章基本可以結(jié)束了，而我們僅僅了解到continuation的一點(diǎn)皮毛，對它的用途也知之甚少。我們可以用CPS完成整個程序，程序里所有的函數(shù)都有一個額外的continuation作為參數(shù)接受其他函數(shù)的返回值。還可以把任何程序轉(zhuǎn)換為CPS的，需要做的只是把當(dāng)中的函數(shù)看作是特殊的continuation（總是將返回值傳給調(diào)用者的continuation）就可以了，簡單到完全可以由工具自動完成（史上很多編譯器就是這樣做的）。

一旦將程序轉(zhuǎn)為CPS的風(fēng)格，有些事情就變得顯而易見了：每一條指令都會有一些continuation，都會將它的計(jì)算結(jié)果傳給某一個函數(shù)并調(diào)用它，在一個普通的程序中這個函數(shù)就是該指令被調(diào)用并且返回的地方。隨便找個之前提到過的代碼，比如說add(5,10)好了。如果add屬于一個用CPS風(fēng)格寫出的程序，add的continuation很明顯就是當(dāng)它執(zhí)行結(jié)束后要調(diào)用的那個函數(shù)?？墒窃谝粋€非CPS的程序中，add的continuation又是什么呢？當(dāng)然我們還是可以把這段程序轉(zhuǎn)成CPS的，可是有必要這樣做嗎？
事實(shí)上沒有必要。注意觀察整個CPS轉(zhuǎn)換過程，如果有人嘗試要為CPS程序?qū)懢幾g器并且認(rèn)真思考過就會發(fā)現(xiàn)：CPS的程序是不需要棧的！在這里完全沒有函數(shù)需要做傳統(tǒng)意義上的“返回”操作，函數(shù)執(zhí)行完后僅需要接著調(diào)用另外一個函數(shù)就可以了。于是就不需要在每次調(diào)用函數(shù)的時候把參數(shù)壓棧再將它們從中取出，只要把這些參數(shù)存放在一片內(nèi)存中然后使用跳轉(zhuǎn)指令就解決問題了。也完全不需要保留原來的參數(shù)：因?yàn)檫@種程序里的函數(shù)都不返回，所以它們不會被用第二次！
簡單點(diǎn)說呢，用CPS風(fēng)格寫出來的程序不需要棧，但是每次調(diào)用函數(shù)的時候都會要多加一個參數(shù)。非CPS風(fēng)格的程序不需要額外的參數(shù)但又需要棧才能運(yùn)行。棧里面存的是什么？僅僅是參數(shù)還有一個供函數(shù)運(yùn)行結(jié)束后返回的程序指針而已。這個時候你是不是已經(jīng)恍然大悟了？對啊，棧里面的數(shù)據(jù)實(shí)際上就是continuation的信息！棧上的程序返回指針實(shí)質(zhì)上就是CPS程序中需要調(diào)用的下一個函數(shù)！想要知道add(5, 10)的continuation是什么？只要看它運(yùn)行時棧的內(nèi)容就可以了。
接下來就簡單多了。continuation和棧上指示函數(shù)返回地址的指針其實(shí)是同一樣?xùn)|西，只是continuation是顯式的傳遞該地址并且因此代碼就不局限于只能返回到函數(shù)被調(diào)用的地方了。前面說過，continuation就是函數(shù)，而在我們特制的語言中函數(shù)就是類的實(shí)例，那么可以得知棧上指向函數(shù)返回地址的指針和continuation的參數(shù)是一樣的，因?yàn)槲覀兯^的函數(shù)（就像類的一個實(shí)例）其實(shí)就是指針。這也意味著在程序運(yùn)行的任何時候，你都可以得到當(dāng)前的continuation（就是棧上的信息）。

好了，我們已經(jīng)搞清楚當(dāng)前的continuation是什么了。接下來要弄明白它的存在有什么意義。只要得到了當(dāng)前的continuation并將它保存起來，就相當(dāng)于保存了程序的當(dāng)前狀態(tài)：在時間軸上把它凍結(jié)起來了。這有點(diǎn)像操作系統(tǒng)進(jìn)入休眠狀態(tài)。continuation對象保存了足夠的信息隨時可以從指定的某個狀態(tài)繼續(xù)運(yùn)行程序。在切換線程的時候操作系統(tǒng)也是這樣做的。唯一的區(qū)別在于它保留了所有的控制權(quán)利。當(dāng)請求某個continuation對象時（在Scheme語言中是通過調(diào)用call-with-current-continuation函數(shù)實(shí)現(xiàn)的）得到的是一個存有當(dāng)前continuation的對象，也就是棧對象（在CPS中也就是下一個要執(zhí)行的函數(shù)）。可以把這個對象保存做一個變量中（或者是存在磁盤上）。當(dāng)以該continuation對象“重啟”該程序時，程序的狀態(tài)就會立即“轉(zhuǎn)換”為該對象中保存的狀態(tài)。這一點(diǎn)和切換回一個被暫停的線程或是從系統(tǒng)休眠中喚醒很相像，唯一不同的是continuatoin對象可以反復(fù)的這樣使用。當(dāng)系統(tǒng)喚醒后，休眠前保存的信息就會銷毀，否則你也可以反復(fù)的從該點(diǎn)喚醒系統(tǒng)，就像乘時光機(jī)回到過去一樣。有了continuation你就可以做到這一點(diǎn)！

那么continuation在什么情況下有用呢？有一些應(yīng)用程序天生就沒有狀態(tài)，如果要在這樣的系統(tǒng)中模擬出狀態(tài)以簡化工作的時候，就可以用到continuation。最合適的應(yīng)用場合之一就是網(wǎng)頁應(yīng)用程序。微軟的ASP.NET為了讓程序員更輕松的編寫應(yīng)用程序，花了大量的精力去模擬各種狀態(tài)。假如C#支持continuation的話，那么ASP.NET的復(fù)雜度將減半：因?yàn)橹灰涯骋粫r刻的continuation保存起來，下次用戶再次發(fā)起同樣請求的時候，重新載入這個continuation即可。對于網(wǎng)絡(luò)應(yīng)用的程序員來說就再也沒有中斷了：輕輕松松程序就從下一行開始繼續(xù)運(yùn)行了！對于一些實(shí)際問題來說，continuation是一種非常有用的抽象工具。如今大量的傳統(tǒng)胖客戶端（見瘦客戶端）正紛紛走進(jìn)網(wǎng)絡(luò)，continuation在未來將扮演越來越重要的角色。