簡單的Functional Programming in Javascript練習

Thu, 01 May 2008 20:04:08 +0800

之前看過蔡學鏞關於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的能力，計算的結果是靠傳進去的函數「捕捉」然後呈現出來的...以後再來試作一些比較實用的例子)