Expressando Y em termos de SKI-Combinators em JavaScript

Question

Eu estava brincando com Cominators em JavaScript e estava orgulhoso (espero) de fazer S funcionar quando me deparei com a Wikipedia dizendo: "O combinador Y pode ser expresso no cálculo SKI como: Y= S (K (SII)) (S (S (KS) K) (K (SII))) ", então eu tive que tentar isso:

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

O que estou fazendo de errado?Não estou traduzindo essa expressão corretamente?Há algo de errado em como estou fazendo isso?Isso faz sentido?A maior parte do que posso ler sobre coisas como essa só faz meu cérebro querer explodir, então o objetivo deste exercício era principalmente ver se eu entendia a notação (e, portanto, seria capaz de traduzi-la para JavaScript).

Ah, e a propósito: o que me fez ler e mexer novamente foi que o que prototype.js implementa como Prototype.K é na verdade o combinador I.Alguém percebeu?

Answer 1

O problema aqui é que você está usando uma linguagem de programação estritamente avaliada. O combinador Y, bem como qualquer outro combinador de ponto fixo, só funcionará corretamente quando suas funções forem chamadas por necessidade ou 'avaliadas lentamente'.

Eu conheço uma maneira de contornar isso ( um de meus professores investigou há um tempo ), mas tornará seu código completamente ilegível.

A seguir, mostrei o que está acontecendo exatamente, esperando que você possa ver por que o JavaScript não consegue lidar com uma implementação direta do cálculo do SKI.

---

Esta é a aparência do Y depois que o JavaScript avaliou sua expressão SKI:

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

Agora vamos ver o que acontece se você alimentá-lo com sua função function (fac) { ... }. Vamos chamar essa função f:

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

Uma vez que a primeira função anônima é aplicada a um argumento, ela será avaliada da seguinte forma:

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

Em uma linguagem avaliada vagarosamente, o argumento para f seria deixado sozinho e o próprio f seria avaliado. No entanto, como JavaScript é uma linguagem estritamente avaliada (ou 'chamada por valor'), ele deseja saber qual argumento precisa passar para a função f antes de realmente executar essa função. Então, vamos avaliar esse argumento, vamos?

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

Acho que agora você está começando a ver onde as coisas dão errado e como o combinador Y realmente funciona. Em qualquer caso, sua máquina JavaScript ficará sem espaço de pilha, porque está tentando construir uma pilha infinita de chamadas para f.