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

Question

Estaba jugando con Cominators en JavaScript y estaba orgulloso (con suerte) de que S funcionara cuando me encontré con Wikipedia diciendo: "El combinador Y se puede expresar en el SKI- cálculo como: Y = S (K (SII)) (S (S (KS) K) (K (SII)))", por lo que tenía que probar que:

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 algo de malo en cómo voy sobre esto? ¿Tiene sentido? La mayor parte de lo que se debe leer sobre cosas como esta solo hace que mi cerebro quiera explotar, así que el objetivo de este ejercicio fue principalmente para ver si entendía la notación (y así podría traducirla a JavaScript).

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

Answer 1

El problema aquí es que está utilizando un lenguaje de programación estrictamente evaluado. El Y-combinator, más o menos como cualquier otro combinador de punto fijo, solo funcionará correctamente cuando sus funciones sean llamadas por necesidad o "evaluadas de forma ocasional".

Conozco una forma de evitar esto (one of my professors looked into it a while ago), 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 directa de SKI-calculus.

---

Esto es lo que parece después de Y JavaScript evalúa su SKI-expresión:

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

Ahora vamos a ver lo que pasa si le da de comer a su función function (fac) { ... }. Vamos a llamar a esa función f:

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

Desde la primera función anónima se aplica a un argumento, que será evaluado en esto:

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

En un lenguaje perezosamente evaluado, el argumento a f sería ahora quedarse solo, y f sí mismo sería evaluado. Sin embargo, como JavaScript es un lenguaje estrictamente evaluado (o 'call-by-value'), quiere saber qué argumento necesita pasar a la función f antes de ejecutar realmente esa función. Entonces, 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á empezando a ver ahora dónde van las cosas mal y cómo funciona realmente el Y-combinator. En cualquier caso, su máquina de JavaScript se quedará sin espacio en la pila, porque está tratando de crear una pila infinita de llamadas al f.