JavaScriptのSKI-CombinatorsでYを表現する

Question

私はJavaScriptでCominatorsを抱いていて、Wikipediaを見つけたときにSがうまく動作することを誇りに思っていました。「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が実装しているのは実際には私のコンビネータです。誰か気づいた？

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 = (function(p){return f(p(p))})(function(p){return f(p(p))}); 

最初の無名関数を引数に適用されているので、それはこのに評価されます：遅延評価言語で

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

、引数fになり、今単独で放置され、f自体が評価される。しかし、JavaScriptは厳密に評価された言語（または '値による呼び出し'）なので、実際にその関数を実行する前に、関数fに渡す必要のある引数を知りたいと考えます。それでは、その議論を評価しましょうか？

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

ここで、状況が間違っているところ、そしてY-コンビネータが実際にどのように動作するかを見てきたと思います。いずれにしても、JavaScriptマシンはスタック空間を使い果たします。なぜなら、それはfへの呼び出しの無限スタックを構築しようとしているからです。