This page looks plain and unstyled because you're using a non-standard compliant browser. To see it in its best form, please visit upgrade to a browser that supports web standards. It's free and painless.

Fillano's Learning Notes 會員登入 會員註冊

23 五月, 2008 08:00

Javascript的Continuation與Continuation Passing Style真有趣

由 Fillano(馮旭平) 發表於 [ Javascript學習日誌 ]
(2136) 閱讀,  (0) 引用,  (0) 回應 ,  推文( 0 )

之前在找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會更好玩....）

02 五月, 2008 20:00

把簡單的javascript改成functional programming的風格練習

由 Fillano(馮旭平) 發表於 [ Javascript學習日誌 ]
(2494) 閱讀,  (0) 引用,  (0) 回應 ,  推文( 0 )

繼續練習把javascript改成functional programming的風格...

先試著把之前寫的依照我需要的格式產生表格的javascript改成pure functional programming的風格，包含currying以及把所有敘述盡量改成lambda calculus。

首先是這個產生表格的函數最早的模樣： 

function draw(target, values) {
	var row0 = target.insertRow(-1);
	for (var j=0; j<values.length; j++) {
		var cell0 = row0.insertCell(-1);
		cell0.innerHTML += (j+1);
	}

	var row0 = target.insertRow(-1);
	for (var j=0; j<values.length; j++) {
		var cell0 = row0.insertCell(-1);
		cell0.style.fontSize = 12;
		cell0.innerHTML += values[j];
	}
}
var t = document.getElementById("target");
draw(t, [0.23,0.351,0.3481,1.382]);

接著先做一次currying，讓這個函數可以用每次接受一個參數的方式來操作： 

function drawc(target){
	return function(values) {
		var row0 = target.insertRow(-1);
		for (var j=0; j<values.length; j++) {
			var cell0 = row0.insertCell(-1);
			cell0.innerHTML += (j+1);
		}

		var row0 = target.insertRow(-1);
		for (var j=0; j<values.length; j++) {
			var cell0 = row0.insertCell(-1);
			cell0.style.fontSize = 12;
			cell0.innerHTML += values[j];
		}
	};
}
drawc(document.getElementById("target"))([0.23,0.351,0.3481,1.382]);

其實沒做多大更動，只是把之前的function body改成一個以第二個參數為唯一參數的匿名函數，然後回傳這個匿名函數。上面的例子drawc函數會回傳一個函數，我直接就用([0.23,0.351,0.3481,1.382])呼叫這個函數並且傳入values參數，實際應用時可以把這個動作再推遲，例如傳給另一個函數處理，或是先存起來等需要的時候再傳values參數給他完成動作等等。

接下來把整個function body改寫成lambda calculus： 

function drawcl(target){
	return function(values) {
		(function(row0){
			(function(j){
				if(j<values.length) {
					(function(cell0){
						cell0.innerHTML += j+1;
					})(row0.insertCell(-1));
					arguments.callee(j+1);
				}
			})(0);
		})(target.insertRow(-1));

		(function(row0){
			(function(j){
				if(j<values.length) {
					(function(cell0){
						cell0.style.fontSize = 12;
						cell0.innerHTML += values[j];
					})(row0.insertCell(-1));
					arguments.callee(j+1);
				}
			})(0);
		})(target.insertRow(-1));
	};
}
drawcl(document.getElementById("target"))([0.23,0.351,0.3481,1.382]);

從這個過程可以看出幾個修改的原則：

  1. 把變數改成匿名函數的參數，把與這個變數相關的運算移到匿名函數裡面，變數名變成參數名，然後等號(assign)右側的敘述放在呼叫函數的參數運算中。
  2. 把iteration的運算改成匿名函數的遞迴，控制條件當作匿名函數的參數傳給他，然後在函數中判斷是否要停止遞迴
  3. 額外的技巧，與fp無關：在javascript中，可以利用arguments.callee來讓匿名函數做遞迴

恩恩，經過嘗試以後，感覺並不是很困難。有空的話再來做更複雜的例子。

以下是在表格border="1" cellpadding="1" cellspacing="0" id="target"的條件中測試跑出來的表格內容：
fp

沒意外的話，應該三個畫面都一樣。

01 五月, 2008 20:04

簡單的Functional Programming in Javascript練習

由 Fillano(馮旭平) 發表於 [ Javascript學習日誌 ]
(1857) 閱讀,  (0) 引用,  (0) 回應 ,  推文( 0 )

之前看過蔡學鏞關於F#的介紹，覺得很有意思，於是在網上找了一些資料看看。在wikipedia關於Lambda Calculus的介紹中，發現他把Javascript也歸類於Functional Languages:

....Modern functional languages, building on the lambda calculus, include Lisp, Scheme, ML, ECMAScript (the most common implementation being JavaScript) and Haskell.
(Lambda Calculus)

為了嘗試跟練習，就試著把Wikipedia解釋Continuation-passing style中用Scheme寫的例子來改寫成Javascript試試看；

第一個例子是計算兩個數字平方合的平方，例子中的Scheme程式如下...

這個是direct style的寫法： 

(define (pyth x y)
 (sqrt (+ (* x x) (* y y))))

同樣的計算，改成continuation passing style的寫法： 

(define (pyth x y k)
 (* x x (lambda (x2)
         (* y y (lambda (y2)
                 (+ x2 y2 (lambda (x2py2)
                           (sqrt x2py2 k))))))))

改成Javascript版本的direct style： 

function pyth(x,y) {
	return sqrt(x*x+y*y);
}
function sqrt(x) {
	return x*x;
}
alert(pyth(2,3));

改成javascript版本的continuation passing style： 

function pyth1(x,y,k) {
	(function(x2){
		(function(y2){
			(function(x2py2){
				k(sqrt(x2py2));
			})(x2+y2);
		})(y*y);
	})(x*x);
}
function sqrt(x) {
	return x*x;
}
pyth1(2,3,function(x){alert(x);});

第二個例子是階乘...

Scheme的direct style： 

(define (factorial n)
 (if (= n 0)
     1
     (* n (factorial (- n 1)))))

Scheme的continuation passing style： 

(define (factorial n k)
  (= n 0 (lambda (b)
          (if b
             (k 1)
             (- n 1 (lambda (nm1)
                     (factorial
                      nm1
                      (lambda (fnm1)
                       (* n fnm1 k))))))))

Javascript的direct style： 

function factorial(n) {
	if(n==0) {
		return 1;
	} else {
		return n*factorial(n-1);
	}
}
alert(factorial(5));

Javascript的continuation passing style： 

function factorial1(n, k) {
	(function(b){
		if(b) {
			k(1);
		} else {
			(function(nm1){
				factorial1(nm1,function(fnm1){k(n*fnm1);});
			})(n-1);
		}
	})(n==0);
}
factorial1(5,function(x){alert(x);});

第三個例子還是階乘，但是改成呼叫一個外部的函數來遞迴...

Scheme的direct style： 

(define (factorial n) (f-aux n 1))
(define (f-aux n a)
 (if (= n 0)
     a
     (f-aux (- n 1) (* n a))))

Scheme的continuation passing style： 

(define (factorial n k)
 (f-aux n 1 k))
(define (f-aux n a k)
 (= n 0 (lambda (b)
         (if b
             (k a)
             (- n 1 (lambda (nm1)
                     (* n a (lambda (nta)
                             (f-aux nm1 nta k)))))))))

Javascript的direct style： 

function factorial(n) {
	return f_aux(n,1);
}
function f_aux(n, a) {
	if(n==0) {
		return a;
	} else {
		return f_aux(n-1, n*a);
	}
}
alert(factorial(5));

Javascript的continuation passing style： 

function factorial1(n, k) {
	f_aux1(n, 1, k);
}
function f_aux1(n, a, k) {
	(function(b){
		if(b) {
			k(a);
		} else {
			(function(nm1) {
				(function(nta){
					f_aux1(nm1, nta, k);
				})(n*a);
			})(n-1);
		}
	})(n==0);
}
factorial1(5, function(x){alert(x);});

我沒學過Lisp或Scheme，不過這幾個例子算是淺顯易懂，所以把他依照Scheme的程式的邏輯結構直接一對一地改成Javascript並沒有太大的困難，更有趣的是，直接「翻譯」成javascript以後，完全可以正常執行，一點都不用改。

這裡看得到Javascript的functional programming language的特色：用函數做為參數、用匿名函數實現lambda calculus等，不過沒有用到返回函數這個特色，另外似乎也沒有明顯展現lexical scope的特色。恩恩，果然javascript在設計上是有functional programming的能力的。
(當然，這些例子也可以看出，javascript也可以用continuation passing style來改寫，讓它具備continuation的能力，計算的結果是靠傳進去的函數「捕捉」然後呈現出來的...以後再來試作一些比較實用的例子)

Site Meter