# 不動點

December 15, 2021

## Y Combinator

Y Combinator〉的推導過程，老實說是有點作弊，為了讓事情一開始不要太複雜，用到了 JavaScript 的一些特性，但也讓推導過程稍微迂迴了一些，現在已經玩過這麼多次的 lambda 演算了，就來全部用箭號函式重做一遍，也許就能瞭解到什麼。

``````(f =>
f(get_R())
)(fact => n => n < 2 ? 1 : n * fact(n - 1))
``````

``````(f =>
(get_R => f(get_R()))(get_R)
)(fact => n => n < 2 ? 1 : n * fact(n - 1))
``````

``````(f =>
(p => p())(get_R => f(get_R()))
)(fact => n => n < 2 ? 1 : n * fact(n - 1))
``````

``````(f =>
(p => p(p))(get_R => f(get_R(get_R)))
)(fact => n => n < 2 ? 1 : n * fact(n - 1))
``````

``````(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？

``````(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 從沒有真正產生 `get_R`，它只是一再地拖延，從沒給予真正的 `get_R`，那套用函式之後，Y Combinator 到底給了你什麼？因為一路上都是使用〈Y Combinator〉的成果，就還是以 `f => (x => f(n => x(x)(n)))(x => f(n => x(x)(n)))` 來試試看吧！

``````(x => f(n => x(x)(n)))(x => f(n => x(x)(n)))
``````

``````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)
``````

``````(x => f(n => x(x)(n)))((x => f(n => x(x)(n))))
``````

``````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 可以為 `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` 值從何而來就不重要了。