Expresando Y en términos de SKI-Combinators en JavaScript

Question

Estaba jugando con Cominators en JavaScript y estaba orgulloso de (con suerte) hacer que S funcionara cuando me topé con Wikipedia diciendo: "El combinador Y se puede expresar en el cálculo SKI como: Y= S (K (SII)) (S (S (KS) K) (K (SII))) ", así que tuve que probar eso:

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é estoy haciendo mal?¿No estoy traduciendo esa expresión correctamente?¿Hay algún problema con la forma en que lo hago?¿Tiene sentido siquiera?La mayor parte de lo que se debe leer sobre cosas como esta solo hace que mi cerebro quiera explotar, por lo que el objetivo de este ejercicio para mí fue principalmente ver si entendía la notación (y así podría traducirla a JavaScript).

Ah, y por cierto: lo que me hizo leer y jugar de nuevo fue que lo que prototype.js implementa como Prototype.K es en realidad el combinador I.¿Alguien lo ha notado?

Answer 1

El problema aquí es que está utilizando un lenguaje de programación estrictamente evaluado. El combinador Y, al igual que cualquier otro combinador de punto fijo, solo funcionará correctamente cuando sus funciones sean llamadas por necesidad o 'evaluadas de forma perezosa'.

Conozco una forma de evitar esto ( uno de mis profesores examinó hace un tiempo ), pero hará que su código sea completamente ilegible.

A continuación, he mostrado lo que está sucediendo exactamente, con la esperanza de que pueda ver por qué JavaScript no puede manejar una implementación sencilla de SKI-calculus.

---

Así es como se ve Y después de que JavaScript evaluó su expresión SKI:

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

Ahora veamos qué sucede si lo alimenta con su función function (fac) { ... }. Llamemos a esa función f:

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

Dado que la primera función anónima se aplica a un argumento, se evaluará en esto:

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

En un lenguaje evaluado con pereza, el argumento de f ahora se dejaría solo, y f en sí mismo sería evaluado. Sin embargo, debido a que JavaScript es un lenguaje estrictamente evaluado (o 'llamada por valor'), quiere saber qué argumento necesita pasar a la función f antes de ejecutar esa función. Así que evaluemos ese argumento, ¿de acuerdo?

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

Supongo que ahora estás empezando a ver dónde van las cosas mal y cómo funciona realmente el combinador Y. En cualquier caso, su máquina JavaScript se quedará sin espacio de pila, porque está intentando construir una pila infinita de llamadas a f.