Exprimant Y en termes de ski-combinants en javascript

Question

J'étais en train de jouer avec les cominateurs en JavaScript et j'étais fier de (espérons-le) que de faire fonctionner S lorsque je suis tombé sur Wikipedia en disant: "Le combinateur y peut être exprimé dans le ski-calculus comme: y = s (k (sii)) ( S (s (ks) k) (k (sii))) ", donc j'ai dû essayer ça:

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

Qu'est-ce que je fais mal? Est-ce que je ne traduis pas correctement cette expression? Y a-t-il quelque chose qui ne va pas avec la façon dont je vais à ce sujet? Est-ce même un sens? La plupart de ce qui doit être lu sur des trucs comme celui-ci donne juste envie de mon cerveau, donc l'intérêt de cet exercice était principalement de voir si je comprenais la notation (et je serais donc en mesure de le traduire en JavaScript).

Oh, et, au fait: ce qui m'a fait lire et jouer à nouveau, c'est que ce que prototype.js implémente en tant que prototype.k est en fait le combinateur i. Quelqu'un a-t-il remarqué?

Answer 1

Le problème ici est que vous utilisez un langage de programmation strictement évalué. Le combinateur Y, à peu près comme tout autre combinateur de points fixes, ne fonctionnera correctement que lorsque vos fonctions sont appelées par le besoin, ou «paresseusement évaluées».

Je connais un moyen de contourner cela (Un de mes professeurs l'a examiné il y a quelque temps), mais cela rendra votre code complètement illisible.

Ci-dessous, j'ai montré ce qui se passe exactement, en espérant que vous puissiez voir pourquoi JavaScript ne peut pas gérer une implémentation simple de Ski-Calculus.

---

C'est quoi Y On dirait qu'après JavaScript a évalué votre expression de ski:

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

Voyons maintenant ce qui se passe si vous le nourrissez votre fonction function (fac) { ... }. Appelons cette fonction f:

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

Étant donné que la première fonction anonyme est appliquée à un argument, elle sera évaluée à ce sujet:

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

Dans une langue paresseusement évaluée, l'argument de f serait maintenant laissé seul, et f lui-même serait évalué. Cependant, parce que JavaScript est un langage strictement évalué (ou `` appel par valeur ''), il veut savoir quel argument il doit passer pour fonctionner f avant d'exécuter cette fonction. Alors évaluons cet argument, d'accord?

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

Je suppose que maintenant vous commencez à voir maintenant où les choses tournent mal et comment le combinateur y fonctionne réellement. Dans tous les cas, votre machine JavaScript manquera d'espace de pile, car il essaie de créer une pile infinie d'appels à f.