7

私は JavaScript でコンビネータをいじっていて、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 が Prototype.K として実装しているものは、実際には I コンビネータであるということでした。誰か気づいた？

4

1 に答える 1

6

ここでの問題は、厳密に評価されたプログラミング言語を使用していることです。Yコンビネータは、他の固定小数点コンビネータとほとんど同じように、関数が必要に応じて呼び出された場合、または「遅延評価」された場合にのみ適切に機能します。

私はこれを回避する方法を知っています（私の教授の1人が少し前にそれを調べました）が、それはあなたのコードを完全に読めなくします。

以下に、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それ自体が評価されます。fただし、JavaScriptは厳密に評価された言語（または「値による呼び出し」）であるため、関数を実際に実行する前に、関数に渡す必要のある引数を知りたいと考えています。では、その議論を評価しましょう。

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

今、あなたは物事がどこでうまくいかないのか、そしてY-combinatorが実際にどのように機能するのかを見始めていると思います。いずれにせよ、JavaScriptマシンは、への呼び出しの無限のスタックを構築しようとしているため、スタックスペースを使い果たしますf。

于 2011-09-10T00:57:56.557 に答える