在JavaScript中使用SKI組合器表示Y

Question

我在JavaScript中擺弄Cominators，並且當我偶然發現維基百科說：「Y組合器可以在SKI-積分爲：Y = S（K（SII））（S（S（KS）K）（K（SII）））」，所以我不得不嘗試：

var I = function (x) { 
      return x; 
     }; 

var K = function (x) { 
     return function(){ 
      return x;} 
     }; 

var S = function (x) { 
      return function (y) { 
       return function (z) { 
        return x(z)(y(z)); 
       } 
      } 
     }; 

var Y = S (K(S(I)(I))) (S(S(K(S))(K)) (K(S(I)(I)))); 

Y; //evals to: 
//function (z) {return x(z)(y(z));} 

//And this (lifted from Crockford's Site): 
var factorial = Y(function (fac) { 
    return function (n) { 
     return n <= 2 ? n : n * fac(n - 1); 
    }; 
}); //fails: 
//RangeError: Maximum call stack size exceeded 

我在做什麼錯？我是不是正確地翻譯這個表達式？我是如何解決這個問題的？它有意義嗎？大部分關於這樣的東西的東西只是讓我的大腦想要爆炸，所以這個練習的重點主要是看看我是否理解了符號（因此可以將它翻譯成JavaScript）。

哦，順便說一句：讓我讀&又一次擺弄的是prototype.js作爲Prototype.K實現的實際上是I combinator。有沒有人注意到？

Answer 1

這裏的問題是您正在使用嚴格評估的編程語言。與其他任何定點組合器相似，Y組合器只能在需要時調用函數或「懶惰評估」時正常工作。

我知道解決此問題的一種方法（one of my professors looked into it a while ago），但它會使您的代碼完全無法讀取。

下面我已經展示了究竟發生了什麼，希望你能明白爲什麼JavaScript不能處理SKI微積分的直接實現。

---

這是Y看起來像JavaScript的評估您的SKI-表達後：

var Y = function (q) { 
    return (function(p){return q(p(p))})(function(p){return q(p(p))}); 
}; 

現在讓我們看看，如果你給它的功能function (fac) { ... }會發生什麼。讓我們來調用該函數f：現在

var factorial = f(
    (function(p){return f(p(p))})(function(p){return f(p(p))}) 
); 

在懶洋洋地評價語，參數f會：

var factorial = (function(p){return f(p(p))})(function(p){return f(p(p))}); 

由於第一個匿名函數應用到一個參數，它會評估這個被單獨留下，並且f本身將被評估。但是，由於JavaScript是嚴格評估的語言（或「按值調用」），因此它希望知道在實際運行該函數之前需要將哪個參數傳遞到函數f。那麼我們來評估一下這個論點吧？

var factorial = f(f(
     (function(p){return f(p(p))})(function(p){return f(p(p))}) 
    ) 
); 

我想現在你已經開始看到現在出現問題的地方，以及Y-combinator如何實際工作。在任何情況下，您的JavaScript機器都將耗盡堆棧空間，因爲它試圖構建一個無限次的調用棧到f。