軟件開發詳解：從Continuation說起

2019-11-18 11:58:55

字體：大中小

來源：轉載

供稿：網友

　　說起Continuation，象我這樣的大多數從C, Basic, Pascal起步的程序員可能都不清楚。但是這個概念在functional language 社區卻好象是常識一樣，很多人在討論問題的時候總是假設你已經知道了continuation的基本概念，什么Call-CC什么的都不加解釋就直接引用。于是，假如不知道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。
　　
　　經典的應用有：exception，back-tracking算法, coroutine等。
　　
　　應用continuation對付exception是很明顯的，只要給可能拋出異常的函數一個外面try的地方的continuation record，這個函數就可以在需要的時候直接返回到try語句的地方。
　　
　　Exception-handling也可以利用continuation。c++等語言普遍采用的是碰到exception就直接中止當前函數的策略，但是，還有一種策略是答應resume，也就是說，出現了異常之后，有可能異常處理模塊修復了錯誤發生的地方然后選擇恢復執行被異常中斷了的代碼。被異常中斷的代碼可以取得當前的continuation，傳遞給異常處理模塊，這樣當resume的時候可以直接跳到出現異常的地方。
　　
　　Back-tracking算法也可以用類似的方法，在某些地方保存當前的continuation，然后以后就可以從其它的函數跳回當前的語句。
　　
　　Coroutine是一個并行計算的模型。它讓兩個進程可以交替執行。典型的coroutine的應用例子如consumer-PRodUCer。比如說：
　　
　　Code:Producer ( c ):
　　
　　Loop:
　　
　　Produce;
　　
　　CallCC c
　　
　　Consumer( p ):
　　
　　Loop:
　　
　　Consume;
　　
　　Callcc p
　　
　　這兩個線程接受對方的continuation，在需要交出控制的時候，就把自己的continuation傳遞給對方。如此，兩者就可以交替執行，而不需要返回。
　　
　　Continuation機制的優化始終不是一個trivial的問題，實際上采取continuation的語言不多。而且，continuation調用方式依靠垃圾收集，也不是c/c++這類中低級的語言所愿意采用的。
　　
　　不過，continuation的思想仍然是有其用武之地的。有一種設計的風格叫做continuation-passing-style。它的基本思想是：當需要返回某些數據的時候，不是直接把它當作函數的返回值，而是接受一個叫做continuation的參數，這個參數就是一個call-back函數, 它接受這個數據，并做需要做的事情。
　　
　　舉個例子：
　　
　　Code:X = f();
　　
　　Print x;
　　
　　把它變成continuation-passing-style, 則是：
　　
　　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++中的拷貝構造很多時候是具有副作用的，作為程序員，不知道自己寫的的副作用到底是否被執行了，被執行了幾次，總不是一個舒適事。
　　
　　而continuation-passing-style，不依靠于任何偏僻的語言特性，也不會引入任何的模棱兩可，也許可以作為一個設計時的選擇。舉個例子, 對于字符串的拼接，假如使用continuation-passing-style如下：
　　
　　Code:Template<class F>
　　
　　Void concat(const string& s1, const string& s2, F ret){
　　
　　String s(s1);
　　
　　S.append(s2);
　　
　　ret(s);//此處，本來應該是return(s)，但是我們把它變成ret(s)。
　　
　　}
　　
　　我們就可以很安心地說，我們此處沒有引入任何不必要的拷貝，不論什么編譯器。
　　
　　當然，continuation style的問題是，它不如直接返回值直觀，類型系統也無法保證你確實調用了ret(s)。而且，它需要一個function object，c++又不支持lamda，定義很多trivial的functor也會讓程序變得很難看。
　　
　　利弊如何，還要自己權衡。

上一篇：Jar文件包間接及Jar命令開發實例詳解

下一篇：對象引用是怎樣嚴重影響垃圾收集器