軟件開發詳解：從Continuation說起

　　說起Continuation象我這樣的大多數從C Basic Pascal起步的程序員可能都不清楚但是這個概念在functional language 社區卻好象是常識一樣很多人在討論問題的時候總是假設你已經知道了continuation的基本概念什麼CallCC什麼的都不加解釋就直接引用於是如果不知道continuation到底指的是什麼簡直就無法理解他們在說什麼
　　
　　於是最近花了點時間研究了continuation的概念
　　
　　剛才恍然小悟了MonadCont的實現機制作為慶祝在此和大家共享一下我的理解然後再回頭討論一下continuation在imperative語言和C++中的可能應用
　　
　　所謂continuation其實本來是一個函數調用機制
　　
　　我們熟悉的函數調用方法都是使用堆棧采用Activation record或者叫Stack frame來記錄從最頂層函數到當前函數的所有context一個frame/record就是一個函數的局部上下文信息包括所有的局部變量的值和SP PC指針的值（通過靜態分析某些局部變量的信息是不必保存的特殊的如尾調用的情況則不需要任何stack frame不過邏輯上我們認為所有信息都被保存了）函數的調用前往往伴隨著一些push來保存context信息函數退出時則是取消當前的record/frame恢復上一個調用者的record/frame
　　
　　象pascal這樣的支持嵌套函數的則需要一個額外的指針來保存父函數的frame地址不過無論如何在任何時候系統保存的就是一個後入先出的堆棧一個函數一旦退出它的frame就被刪除了
　　
　　Continuation則是另一種函數調用方式它不采用堆棧來保存上下文而是把這些信息保存在continuation record中這些continuation record和堆棧的activation record的區別在於它不采用後入先出的線性方式所有record被組成一棵樹（或者圖）從一個函數調用另一個函數就等於給當前節點生成一個子節點然後把系統寄存器移動到這個子節點一個函數的退出等於從當前節點退回到父節點
　　
　　這些節點的刪除是由garbage collection來管理如果沒有引用這個record則它就是可以被刪除的
　　
　　這樣的調用方式和堆棧方式相比的好處在哪裡呢？
　　
　　最大的好處就是它可以讓你從任意一個節點跳到另一個節點而不必遵循堆棧方式的一層一層的return方式比如說在當前的函數內你只要有一個其它函數的節點信息完全可以選擇return到那個函數而不是循規蹈矩地返回到自己的調用者你也可以在一個函數的任何位置儲存自己的上下文信息然後在以後某個適當的時刻從其它的任何一個函數裡面返回到自己現在的位置
　　
　　Scheme語言有一個CallCC (call with current continuation)的機制也就是說取得當前的continuation傳遞給要call的這個函數這個函數可以選擇在適當的時候直接return到當前的continuation
　　
　　經典的應用有exceptionbacktracking算法 coroutine等
　　
　　應用continuation對付exception是很明顯的只要給可能拋出異常的函數一個外面try的地方的continuation record這個函數就可以在需要的時候直接返回到try語句的地方
　　
　　Exceptionhandling也可以利用continuationc++等語言普遍采用的是遇到exception就直接中止當前函數的策略但是還有一種策略是允許resume也就是說出現了異常之後有可能異常處理模塊修復了錯誤發生的地方然後選擇恢復執行被異常中斷了的代碼被異常中斷的代碼可以取得當前的continuation傳遞給異常處理模塊這樣當resume的時候可以直接跳到出現異常的地方
　　
　　Backtracking算法也可以用類似的方法在某些地方保存當前的continuation然後以後就可以從其它的函數跳回當前的語句
　　
　　Coroutine是一個並行計算的模型它讓兩個進程可以交替執行典型的coroutine的應用例子如consumerproducer比如說
　　
　　Code:Producer ( c ):
　　
　　Loop:
　　
　　Produce;
　　
　　CallCC c
　　
　　Consumer( p ):
　　
　　Loop:
　　
　　Consume;
　　
　　Callcc p
　　
　　這兩個線程接受對方的continuation在需要交出控制的時候就把自己的continuation傳遞給對方如此兩者就可以交替執行而不需要返回
　　
　　Continuation機制的優化始終不是一個trivial的問題實際上采取continuation的語言不多而且continuation調用方式依賴垃圾收集也不是c/c++這類中低級的語言所願意采用的
　　
　　不過continuation的思想仍然是有其用武之地的有一種設計的風格叫做continuationpassingstyle它的基本思想是當需要返回某些數據的時候不是直接把它當作函數的返回值而是接受一個叫做continuation的參數這個參數就是一個callback函數 它接受這個數據並做需要做的事情
　　
　　舉個例子
　　
　　Code:X = f();
　　
　　Print x;
　　
　　把它變成continuationpassingstyle 則是
　　
　　f(print)
　　
　　F()函數不再返回x 而是接受一個函數然後把本來要返回的x傳遞給這個函數
　　
　　這個例子也許看上去有點莫名其妙為什麼這麼做呢？對Haskell這樣的語言一個原因是
　　
　　當函數根據不同的輸入可能返回不同類型的值時用返回值的話就必須設計一個額外的數據結構來處理這種不同的可能性比如
　　
　　一個函數f(int)的返回值可能是一個int 兩個float或者三個complex那麼我們可以這樣設計我們的函數f
　　
　　Code:F:: Int > (Int>a) > (Float>Float>a) > (Complex>Complex>Complex>a) > a
　　
　　這個函數接受一個整形參數三個continuation回調用來處理三種不同的返回情況最後返回這三個回調所返回的類型
　　
　　另一個原因對模擬imperative風格的monad可以在函數中間迅速返回（類似於C裡面的return或者throw)
　　
　　對於C++我想除了處理不同返回類型的問題另一個應用可以是避免返回值的不必要拷貝雖然c++現在有NRV優化但是這個優化本身就很含混各個編譯器對NRV的實現也不同C++中的拷貝構造很多時候是具有副作用的作為程序員不知道自己寫的的副作用到底是否被執行了被執行了幾次總不是一個舒服事
　　
　　而continuationpassingstyle不依賴於任何偏僻的語言特性也不會引入任何的模稜兩可也許可以作為一個設計時的選擇舉個例子 對於字符串的拼接如果使用continuationpassingstyle如下
　　
　　Code:Template<class F>
　　
　　Void concat(const string& s const string& s F ret){
　　
　　String s(s);
　　
　　Sappend(s);
　　
　　ret(s);//此處本來應該是return(s)但是我們把它變成ret(s)
　　
　　}
　　
　　我們就可以很安心地說我們此處沒有引入任何不必要的拷貝不論什麼編譯器
　　
　　當然continuation style的問題是它不如直接返回值直觀類型系統也無法保證你確實調用了ret(s)而且它需要一個function objectc++又不支持lamda定義很多trivial的functor也會讓程序變得很難看
　　
　　利弊如何還要自己權衡

From:http://tw.wingwit.com/Article/program/Java/hx/201311/25683.html