不動點

在正式討論不可運算的函式之前，倒是可以重新瞭解一下〈Y Combinator〉，在那一連串如同魔術般的推導過程之後，得到了像是密宗文字般的 f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n)))，是的，它可以達到想要的遞迴效果，然而，到底這串文字是什麼東西？

Y Combinator

〈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〉裏不一樣？哪裏導錯了呢？

Y？Z？

沒有導錯！這才是 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 的函式，就可以停止這個循環，這就是遞迴的停止條件設定了。