Continuation

Continuation

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

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

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

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

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

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

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

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

這兩行代碼彼此之間沒(méi)有依賴關(guān)系，因此編譯器可以隨意的重新安排它們的執(zhí)行順序?？墒侵灰肅PS重寫它，編譯器就必須順序執(zhí)行了，因?yàn)橹貙懞蟮拇a存在依賴關(guān)系了。

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

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

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

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

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