匿名函數遞迴又一章
Tue, 11 Nov 2008 18:00:15 +0800很久以前寫過關於匿名函數遞迴的方法，用的是arguments屬性。不過後來發現其實不用那麼麻煩。還有一個簡單的方法，以及應用函數語言技巧的方法，可以拿來應用在匿名函數遞迴上。
javascript的function expression其實還有一個作法，讓你可以命名匿名函數，這樣在做匿名函數遞迴時就可以不用到arguments。
var a = (function f(x) {
if (x>1) {
return x * f(x-1);
} else {
return 1;
}
})(5);
alert(a);
上面的function expression中，把function命名為f，但是他只作用在()裡面，不會對外面的scope產生影響，所以如果在alert(a)之後呼叫f會出現函數未定義的錯誤。
這幾天回頭看了一下Lambda Calculus的資料，裡面提到第一印象中Lambda Calculus似乎無法做出遞迴結構，但其實可以利用Y Combinator來做。這個作法很有趣。
按照定義，Y combinator：
Y = λ g. (λ x. g (x x)) (λ x. g (x x))
這樣的結構改成javascript就會變成：
var Y = function(g) {
return (function(x) {
return g(function() {
return x(x);
});
})(function(x) {
return g(function() {
return x(x);
});
});
};
如果我想傳一個參數給函數，那需要調整一下這個Y combinator，讓他接受參數：
var Y = function(g) {
return (function(x) {
return g(function(n) {
return x(x)(n);
});
})(function(x) {
return g(function(n) {
return x(x)(n);
});
});
};
這樣傳需要遞迴的函數給Y時，會返回一個可以接受一個參數的函數。
做階乘的函數，可以抽象為：
var g = function(f,n){
if(n==0) {
return 1;
} else {
return n*f(f,n-1);
}
};
alert(g(g,5));
使用時，還必須把g傳給自己，才能做出遞迴。這樣做就無法匿名，否則無法傳遞g給自己做參數了。
先把把上面過程curry化備用：
var g = function(f){
return function(n){
if (n==0) {
return 1;
} else {
return n*f(f)(n-1);
}
};
};
alert(g(g)(5));
使用Y combinator，他會為傳入的函數做出遞迴結構，先不用匿名函數做，比較清楚：
var g = function(f){
return function(n){
if (n==0) {
return 1;
} else {
return n*f(n-1);
}
};
};
var Y = function(g) {
return (function(x) {
return g(function(n) {
return x(x)(n);
});
})(function(x) {
return g(function(n) {
return x(x)(n);
});
});
};
alert(Y(g)(5));
透過Y，可以在每次遞迴中把g函數裡面的f展開為f(f)，並且把g函數傳遞給自己，最後傳回一個遞迴的函數。接著傳遞參數n給這個產生的函數，就可以計算出遞迴的結果。
再來用匿名函數的方法做（跟前面等義，只是把g改成匿名函數）：
var Y = function(g) {
return (function(x) {
return g(function(n) {
return x(x)(n);
});
})(function(x) {
return g(function(n) {
return x(x)(n);
});
});
};
alert(Y(function(f){
return function(n){
if (n==0) {
return 1;
} else {
return n*f(n-1);
}
};
})(5));
有趣吧？
使用上，可以用Y combinator產生遞迴函數來用：
var Y = function(g) {
return (function(x) {
return g(function(n) {
return x(x)(n);
});
})(function(x) {
return g(function(n) {
return x(x)(n);
});
});
};
var fact = Y(function(f){
return function(n){
if (n==0) {
return 1;
} else {
return n*f(n-1);
}
};
});
alert(fact(5));
接著試試看費氏數列，不使用Y combinator的狀況，必須這樣寫：
var f = function(f,n) {
if(n==0) {
return 0;
} else if(n==1) {
return 1;
} else if(n>1) {
return f(f,n-1) + f(f,n-2);
}
};
alert(f(f,5));
現在可以用Y combinator來產生費氏數列函數：
var fab = Y(function(f){
return function(n){
if(n==0) {
return 0;
} else if(n==1) {
return 1;
} else if(n>1) {
return f(n-1) + f(n-2);
}
};
});
alert(fab(5));
已經把自己弄糊塗了，稍微整理一下關於Y的思考：
var f = function(n) {
if(n==0) {
return 1;
} else {
return n * f(n-1);
}
};
alert(f(5));
var g = function(f, n) {
if(n==0) {
return 1;
} else {
return n * f(n-1);
}
};
alert(g(f,5));
g = function(f) {
return function(n) {
if(n==0) {
return 1;
} else {
return n * f(n-1);
}
};
};
alert(g(f)(5));
var fact = g(f);
alert(fact(5));
var Y = function (g) {return g(f);}
用有名字的函數做都不是問題，使用Y combinator的關鍵在於匿名也能做出這樣的結構。第一步做出階乘的函數f。然後調整一下結構，做出一個函數g，接受f作為參數，這樣是為了匿名函數無法呼叫自己，所以把他移出去作成一個參數。接著把g做curry化。這樣做我們會發現，g(f)實際上會返回遞迴的階乘函數f。把這個過程展開，可以得出下面的結構：
var b = (function (x){
return function(n) {
if(n==0) {
return 1;
} else {
return n * x(x)(n-1);
}
};
})(function (x){
return function(n) {
if(n==0) {
return 1;
} else {
return n * x(x)(n-1);
}
};
});
alert(b(5));
g與f的差別，在於f靠呼叫f來達成遞迴，g靠傳入f並讓f遞迴，但是g與f的結構一樣，其實能完成的計算也一樣。所以可以靠不斷傳入g做為g的參數而返回計算階乘的函數來構成遞迴。這個過程可以靠一個匿名函數的結構達成，遞迴的地方，則由f改成g(g)，產生的函數可以接收n來做階乘計算，在這個函數中又用g(g)來遞迴。我們把匿名函數上半部看成g，下半部傳入的函數叫做g1的話，執行第一次遞迴迭代的是g，之後則是g1。依序為g(g1)->g1(g1)->g1(g1)->g1(g1)......最後就可以計算出階乘的答案。關鍵其實就在於傳入的函數參數，返回的計算函數，計算函數中的遞迴結構把上述過程再度重現。
最後來看Y Combinator怎麼運作：
var Y = function(g) {
return (function(x) {
return g(function(n) {
return x(x)(n);
});
})(function(x) {
return g(function(n) {
return x(x)(n);
});
});
};
其實是一樣的邏輯結構。只要稍微調整過g，把他傳給Y，產生的就是g的遞迴版本函數。關鍵還是在於x(x)(n)。另外，可以看出三個等價的函數f、g(f)、Y(g)。差別在於，前兩個不是匿名函數，最後一個傳入的參數可以是匿名函數。如果不想靠Y Combinator，也可以把這樣的結構展開，用b這個函數的方法來達成。
2008-11-12 18:12 補充：
這篇的靈感其實來自於wikipedia上關於Lambda Calculus的說明：
http://en.wikipedia.org/wiki/Lambda_calculus
另外也用到currying：
http://en.wikipedia.org/wiki/Currying
這兩篇在wikipedia上有中文版本，內容也相當完整。
其實寫這篇的時候，雖然做出結果，但是覺得沒有把他考慮清楚，就重新想了一遍，所以內容前後有一些地方有重複甚至有些矛盾的。不過還是把他當作一個紀錄啦。
2008-11-12 23:02
阿，還有一些參考資料是關於continuation passing style：
http://en.wikipedia.org/wiki/Continuation_passing_style
總之，這篇其實講functional language大於平常的javascript programming。既然Crockford在他的書中提到：「JavaScript是第一個躍上主流的lambda語言。」，有機會還是會想嘗試看看他屬於這一部份的特性。