在正式討論不可運算的函式之前,倒是可以重新瞭解一下〈Y Combinator〉,在那一連串如同魔術般的推導過程之後,得到了像是密宗文字般的 f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n)))
,是的,它可以達到想要的遞迴效果,然而,到底這串文字是什麼東西?
〈Y Combinator〉的推導過程,老實說是有點作弊,為了讓事情一開始不要太複雜,用到了 JavaScript 的一些特性,但也讓推導過程稍微迂迴了一些,現在已經玩過這麼多次的 lambda 演算了,就來全部用箭號函式重做一遍,也許就能瞭解到什麼。
同樣地,假設想要解決 let fact = n => n < 2 ? 1 : n * fact(n - 1)
這個遞迴函式,然而不使用 let
,為了能綁定 fact
這個名稱,就讓 fact
成為參數,也就是 fact => n => n < 2 ? 1 : n * fact(n - 1)
。
現在的問題是,誰來給這個箭號函式一個真正的遞迴函式,以便讓 fact
參數可以參考?若真的存在 get_R
,可產生需要之函式,遞迴函式就可以這麼解決:
(f =>
f(get_R())
)(fact => n => n < 2 ? 1 : n * fact(n - 1))
問題在於 get_R
從哪來,若希望 get_R
從參數來:
(f =>
(get_R => f(get_R()))(get_R)
)(fact => n => n < 2 ? 1 : n * fact(n - 1))
問題顯然沒有解決,只是將 get_R
來源問題繼續往右推而已,那就不要馬上用 get_R
來呼叫,將 get_R => f(get_R())
當成是引數,傳入另一個匿名函式:
(f =>
(p => p())(get_R => f(get_R()))
)(fact => n => n < 2 ? 1 : n * fact(n - 1))
左邊 p()
呼叫沒有傳入,這樣的話右邊 get_R
不會有值,那就將 p
當成是 p
呼叫時的引數:
(f =>
(p => p(p))(get_R => f(get_R(get_R)))
)(fact => n => n < 2 ? 1 : n * fact(n - 1))
接著套用 p
:
(f =>
(get_R => f(get_R(get_R)))(get_R => f(get_R(get_R)))
)(fact => n => n < 2 ? 1 : n * fact(n - 1))
get_R
名稱有點長,改成 x
好了:
(f =>
(x => f(x(x)))(x => f(x(x)))
)(fact => n => n < 2 ? 1 : n * fact(n - 1))
f => (x => f(x(x)))(x => f(x(x)))
就是 Y Combinator 了!咦?長得跟〈Y Combinator〉裏不一樣?哪裏導錯了呢?
沒有導錯!這才是 lambda 演算裏的 Y Combinator,只不過,試著執行上頭的程式並傳入一個數字的話,遞迴卻不會終止,最後達到 JavaScript 環境的遞迴堆疊上限,產生錯誤訊息才停止。
原因在於 JavaScript 的執行環境中,會先執行 x(x)
,結果值傳入 f
,而不是令整個 x(x)
被 fact
參考,在判定 n < 2
之後才執行,這問題跟〈是的!不是!〉是類似的,因為 JavaScript 並不支援惰性求值,若要能有這個效果,必須自行實現。
也就是令 x(x)
成為 n => x(x)(n)
,JavaScript 還是會先執行,然後結果是產生一個 n => x(x)(n)
函式物件,只有在 n < 2
時才會呼叫此函式物件,這樣就能避免堆疊錯誤。
(f =>
(x => f(n => x(x)(n)))(x => f(n => x(x)(n)))
)(fact => n => n < 2 ? 1 : n * fact(n - 1))
f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n)))
就長得跟〈Y Combinator〉中最後的結果一樣了,這個形式是 Y Combinator 的衍生,稱為 Z Combinator,本質上還是 Y Combinator,因此在具備一級函式特性的程式語言中,雖然實現出來的其實是 Z Combinator,然而,多還是以 Y Combinator 來稱呼它。
總之,就還是都稱呼它們為 Y Combinator 吧!現在重點來了,在導證過程中,出現的 (p => p(p))(get_R => f(get_R(get_R)))
代表了什麼呢?get_R
實際上存在嗎?你真的找出來 get_R
嗎?不!沒有!
Y Combinator 從沒有真正產生 get_R
,它只是一再地拖延,從沒給予真正的 get_R
,那套用函式之後,Y Combinator 到底給了你什麼?因為一路上都是使用〈Y Combinator〉的成果,就還是以 f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n)))
來試試看吧!
在套用 f
之後:
(x => f(n => x(x)(n)))(x => f(n => x(x)(n)))
繼續套用 x
:
f(n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n))
也就是傳入 f
的其實是:
n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n)
如果在 f
中用某個數字套用 n
:
(x => f(n => x(x)(n)))((x => f(n => x(x)(n))))
繼續套用 x
:
f(n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n))
現在傳入 f
的其實是:
n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n)
發現了嗎?無論怎麼套用,最後傳入 f
的一定是 n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n)
,你找到了 f
的不動點(Fixed-point)。
若有個函式 f(x)
,有個值 v
令 f(v)
結果仍為 v
,v
就是 f(x)
的不動點,例如,0 和 1 是函式 f(x) = square(x)
的不動點,因為 f(0)
為 0,f(1)
為 1。
Y Combinator 可以為 f
產生不動點,也就是 n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n)
,無論執行再多次,還是得到 n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n)
,這就是 Y Combinator 可以拖延,從不面對 get_R
真正來源的原因,每當你試圖呼叫傳入 f
的函式,它就傳給你 n => (x => f(n => x(x)(n)))((x => f(n => x(x)(n))))(n)
,如此 x
值從何而來就不重要了。
如果你想打破砂鍋問到底,若是人力運算,算到死它都不會交代 x
從何而來(也就不可能回答 x
是否存在),如果是現代的電腦計算,就是看什麼時候堆疊錯誤發生,那就別打破砂鍋問到底了,適可而止,給個邊界,不再執行傳入 f
的函式,就可以停止這個循環,這就是遞迴的停止條件設定了。