Y in Form von SKI-Kombinatoren in JavaScript ausdrücken

Question

Ich habe in JavaScript mit Cominators herumgespielt und war stolz darauf, (hoffentlich) S zum Laufen zu bringen, als ich auf Wikipedia stieß und sagte: "Der Y-Kombinator kann im SKI-Kalkül ausgedrückt werden als: Y= S (K (SII))) (S (S (KS) K) (K (SII))) ", also musste ich das versuchen:

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

Was mache ich falsch?Übersetze ich diesen Ausdruck nicht richtig?Stimmt etwas nicht, wie ich das mache?Macht es überhaupt Sinn?Das meiste, was über solche Dinge zu lesen ist, bringt mein Gehirn dazu, explodieren zu wollen. Daher bestand der Sinn dieser Übung für mich hauptsächlich darin, zu sehen, ob ich die Notation verstanden habe (und sie somit in JavaScript übersetzen könnte).

Oh, und übrigens: Was mich wieder zum Lesen und Fummeln gebracht hat, war das, was prototype.js als Prototype.K implementiert, ist eigentlich der I-Kombinator.Hat jemand bemerkt?

Answer 1

Das Problem hierbei ist, dass Sie eine streng evaluierte Programmiersprache verwenden. Der Y-Kombinator funktioniert wie jeder andere Festkomma-Kombinator nur dann ordnungsgemäß, wenn Ihre Funktionen nach Bedarf aufgerufen oder "träge ausgewertet" werden.

Ich kenne eine Möglichkeit, dies zu umgehen ( einer meiner Professoren hat nachgeforscht es vor einiger Zeit ), aber es wird Ihren Code völlig unlesbar machen.

Unten habe ich gezeigt, was genau los ist, in der Hoffnung, dass Sie sehen können, warum JavaScript eine einfache Implementierung von SKI-Kalkül nicht bewältigen kann.

---

So sieht Y aus, nachdem JavaScript Ihren SKI-Ausdruck ausgewertet hat:

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

Nun wollen wir sehen, was passiert, wenn Sie Ihre Funktion function (fac) { ... } eingeben. Nennen wir diese Funktion f:

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

Da die erste anonyme Funktion auf ein Argument angewendet wird, wird sie wie folgt ausgewertet:

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

In einer träge ausgewerteten Sprache würde das Argument für f jetzt in Ruhe gelassen und f selbst ausgewertet. Da JavaScript jedoch eine streng evaluierte Sprache (oder "Call-by-Value") ist, möchte es wissen, welches Argument an die Funktion f übergeben werden muss, bevor diese Funktion tatsächlich ausgeführt wird. Lassen Sie uns dieses Argument bewerten,

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

Ich denke, jetzt sehen Sie, wo etwas schief geht und wie der Y-Kombinator tatsächlich funktioniert. In jedem Fall wird Ihrem JavaScript-Computer der Stapelspeicherplatz ausgehen, da versucht wird, einen unendlichen Stapel von Aufrufen für f zu erstellen.