Javascript的Continuation與Continuation Passing Style真有趣

 Fri, 23 May 2008 08:00:43 +0800

之前在找Functional Programming的資料時,在Lambda Calculus的資料裡面有提到一點,就是因為Lambda Calculus把所有的運算變成函數運算,沒有使用到變數,所以不會保存狀態,所以可以在執行中紀錄執行環境,中斷並跳出以後,恢復執行環境,繼續進行尚未完成的計算。

接著再找如何可以達到這樣的功能,就找到了關於Continuation的資料。如果執行環境不支援這樣的功能,還可以透過Continuation Passing Style來達成需要的功能。聽起來好像不錯,但是仔細研究了一下,又似乎不是這麼回事。感覺上Continuation跟Continuation Passing Style似乎不能當作同義詞,不論實作或是應用都有一些不太一樣。

wikipedia上面有提到關於Continuation的主題,另外有一篇提到Continuation Passing Style的文章,可以參考一下。


關於Continuation

Javascript....應該說ECMA-262 Edition3裡面並沒有支援Continuation。所以想要嘗試的話,得另外找方法。Rhino這個用java開發的javascript直譯器倒是透過一個Continuation物件來讓它可以做到Continuation。用法也很簡單:

var k = new Continuation();

這樣在變數k裡面就保存了產生Continuation物件時的執行環境,之後只要透過呼叫:

k();

就可以恢復執行環境,完成剩餘的運算。

找了一下說明,Continuation物件會保存堆疊及變數,所以其實不用Lambda Calculus來寫也不影響它的功能。接下來寫一個小小的例子來測試一下continuation的功能,另外還使用了Rhino提供的serialze的功能。把之前用過的continuation passing style的階乘例子稍微改了一下:

function factorial1(n, k) {
f_aux1(n, 1, k);
}
function f_aux1(n, a, k) {
var ret;
(function(b){
if(b) {
k();
} else {
(function(nm1) {
(function(nta){
f_aux1(nm1, nta, k);
})(n*a);
})(n-1);
}
})(n==0);
print(a+","+n);
}
factorial1(5,function(){var k=new Continuation();serialize(k,"fact1.ser");java.lang.System.exit(0);});

在Rhino中執行了這個例子後,就會跳出Rhino的執行環境。接著再進入Rhino,執行以下幾行程式:

js> var k = deserialize("fact1.ser");
js> k();
120,0
120,1
60,2
20,3
5,4
1,5
js>
(說明:js>是直譯器環境的prompt,這裡為了看到跟直譯器環境一樣的結果,把它也放進來,這並不是程式的一部分喔)

從顯示出來的結果可以看出,程式在遞迴最內層的f_aux1函數裡面計算出結果時記錄了執行的環境,用serialize函數存起來,然後再次進入Rhino時,用deserialize函數來取回記錄的執行環境,然後繼續執行下去,就從遞迴得最內圈一層一層離開,離開時會執行print(a+","+n)顯示傳進來的a與n參數。

有一些著名的專案使用Rhino以及其Continuation的能力,來構成處理流程的核心,這些專案包括Apache Software Foundation的Cocoon以及Spring的Spring Web Flow。(....其實都沒用過,只是找Continuation資料時發現的啦)


關於Continuation Passing Style

上面的例子其實也同時用了Continuation Passing Style。簡單地說,Contiuation Passing Style就是傳入一個函數做為函數的參數,在運算完成時不直接處理運算結果,而呼叫這個傳進來的函數處理接下來的運算。在找相關資料時,有看到一篇討論Javascript使用Continuation Passing Style的文章,很值得參考:Continuation-Passing Style and why JavaScript developers might be interested in it

之前的文章也有提到,一些google api在設計上會使用continuation passing style,讓我們寫一個函數或物件傳入google api的函數,用來處理google api產生的結果,從這方面來看,也可以把continuation passing style理解成一種callback函數吧?


Mozilla Javascript 1.7與1.8的iterator與generator

為什麼在這裡提到這個呢?雖然不是continuation,但是這個有趣的規格提供了一種方法讓我們更方便處理迭代中的狀態(Pythoners跟CShapers應該很熟悉這個東西吧)。這種處理方式讓我們可以跳離迭代/迴圈來處理一些計算再回去繼續迭代,感覺在結構上跟Continuation有一些異曲同工之妙。Javascript 1.7使用了yield的語法,Javascript 1.8則進一步用generator expression來簡化它的使用方法。請參見New in JavaScript 1.7以及New in JavaScript 1.8這兩篇文章的介紹。

看起來ECMA262 Edition4也有機會加入這些規格,讓我們寫起程式更靈活。(還有很多有趣的東西,像是array comprehension、let等等,不過如果能加上bind會更好玩....)