http://www.ps.uni-sb.de/~duchier/python/continuations.html
A continuation is a procedure that takes the value
of the current expression and computes the rest of the computation.
Continuation是一種非常古老的程序結構,關于它的理論分析可謂淵源流長,參見
http://library.readscheme.org/page6.html
continuation簡單的說起來就是entire default future of a computation,
即對程序"接下來要做的事情"所進行的一種建模. 這一概念在理論上當然存在著巨大的價值,
至少它使得我們有一種手段把程序未來的運行過程明確的表達出來(給它取了個名字), 從而有可能對之作進一步的分析.
continuation是對未來的完整描述, 這對于理論分析而言是有很多方便之處的,
正如統計學中最常見的分析工具是分布函數而不是密度函數一樣. 實際上任何程序都可以通過所謂的CPS(Continuation Passing
Style)變換而轉換為使用continuation結構, 例如
int foo(int x){
return x+1;
}
==>
void foo(int x,Continuation c){
c.continueWith(x+1);
}
使用continuation的函數不"返回"值,而是把值作為一個參數傳遞給continuation從而"繼續"處理值. 在傳統的軟件理論中,
程序本身在運行期是固定不變的, 我們只需要記錄下執行點(excution
point)的信息(例如指針位置和堆棧內容)即足以完整的描述程序未來的運行情況,
因此continuation有時也被看作是"帶參數的goto", 是goto語句的一種函數形式.
在函數式語言中, continuation的引入是非常自然的過程, 考察如下函數調用
h(g(k(arg)))
根據函數的結合律, 我們可以定義復合函數 m = h(g(.)), 它自然的成為 k(arg)的continuation.
在理論上我們有可能利用泛函分析的一些技術實現對于continuation(復合函數)的化簡, 但實踐已經證明這是極為艱難的,
主要是我們的程序不可避免的要涉及到程序與數據的糾纏.
在引入continuation概念之后, 程序運行的表述是非常簡單的:
continuation.proceed();
針對串行程序,我們可以建立更加精細的運行模型。
while(continuation.hasNextStep())
continuation.proceedOneStep();
只要以某種方式構造出一種continuation closure(這意味著我們能夠通過單一變量來表示程序未來的運行結構), 我們就有可能在某個層面上以如上方式實現對程序的一種簡潔的描述.
如果我們的眼界開闊一些, 不拘泥于構造語言級別通用的continuation結構(這需要以抽象的方式定義并保存任意程序的完整運行狀態),
而是考察"對程序未來運行的整體結構進行建模"這一更寬廣的命題, 我們很快就能發現大量對于continuation概念的應用.
例如實現AOP(Aspect Oriented
Programming)的interceptor時所經常使用的MethodInvocation對象.
class MyInterceptor implements MethodInterceptor{
public Object invoke(MethodInvocation invocation){
doSomeThingBeforeRawMethodCall();
return invocation.proceed();
}
}
在網絡編程中, 一種常用的設計模式是Observer模式, 即注冊監聽器(listener)來處理接收到的網絡指令.
在一些比較復雜的網絡協議中, 網絡指令之間往往存在一定的關聯, 我們可以通過建立一個龐大的有限自動機來描述所有指令之間的關聯規則,
也可以采用如下方式動態的實現對于監聽器的調整.
class ACommandListener{
public void onEvent(Event event, FutureListeners futureListeners){
handleEvent(event);
futureListeners.clear();
futureListeners.add("BCommand", new BCommandListener());
futureListeners.add("CCommand", new CCommandListener());
}
}
這種方式可以看作是對程序未來運行結構的一種動態調整. 實際上沿著這種方式深入下去, 我們甚至可以建立一種完整的動態工作流(workflow)機制.
最近struts和webwork步cocoon和rife的后塵, 相繼引入了對web
continuation的支持, 在后臺程序中實現了對于page flow的完整描述, 這無疑是一些非常有趣的工作. 例如現在我們可以編寫
void onRequest(){
funcA();
Input input = sendPageAndWait("collectionInfoFromUser.jsp");
handleInput(input);
}
在調用sendPageAndWait的時候, web框架會保存當前函數調用的continuation,
向用戶返回頁面collectionInfoFromUser.jsp, 等待用戶提交表單之后,
web框架重新激活我們所保存的continuation, 繼續執行我們的函數. 這種做法與系統調用和線程調度等機制是非常類似的.
有些人認為這種基于continuation的方式可以自然的解決在session中保存并清理變量的問題, 這顯然是一種大材小用的做法,
而且事實上使用一種通用的continuation 實現很有可能在無意中保存了過多的臨時變量, 從而對系統性能造成極大的損害. 有趣的是,
在Mach3.0中對系統線程所作的一項改進即稱為continuation,
其動因恰在于避免保留線程堆棧,希望使用完全無狀態的continuation函數.(參見Uresh Vahalia的經典著作"UNIX
Internals"
http://www.china-pub.com/computers/common/info.asp?id=12731).
在傳統的系統調用實現中
syscall_l(argl)
{
...
thread_block();
f2(arg);
return;
}
f2(arg){
...
return;
}
thread_block()函數會阻塞住當前系統調用過程, 并自動保存所有堆棧變量, 等待內核重新把控制權返回給調用函數. 在使用continuation函數的方式中, 我們需要顯式的存取狀態變量,
syscall_1(arg1)
{
...
save arg1 and any other state information;
thread_block(f2); // thread_block(void * (contiuationFunc));
/* not reached */
}
f2()
{
restore argl and any other state information;
...
thread_syscall_return(status);
}
在這種方式中thread_block()并不返回到調用者。線程恢復執行時,內核把控制權傳遞給f2().
函數thread_syscall_return()用來從系統調用返回到用戶級。"整個過程對用戶是透明的,用戶所看到的只是從系統調用一個同步返回
". 在Linux系統內核中所使用的bottom_half機制也是基于類似的原理.