Wyrażanie Y w terminach kombinatorów SKI w JavaScript

Question

Miałem do czynienia z kominiarkami w JavaScript i byłem dumny z (miejmy nadzieję), że S zadziałało, gdy natknąłem się na Wikipedię, mówiąc: "Kombinator Y można wyrazić w SKI- rachunek jako: Y = S (K (SII)) (S (S (KS) K) (K (SII)))”, więc musiałem spróbować:

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 

Co robię źle? Czy nie tłumaczę poprawnie tego wyrażenia? Czy coś jest nie tak z tym, jak to robię? Czy to ma nawet sens? Większość tego, co można przeczytać o takich rzeczach, po prostu sprawia, że ​​mój mózg chce eksplodować, więc celem tego ćwiczenia było przede wszystkim sprawdzenie, czy rozumiem notację (a zatem będę w stanie przetłumaczyć ją na JavaScript).

Aha, a przy okazji: co sprawiło, że przeczytałem: & Fiddling ponownie to, co prototype.js implementuje jako Prototype.K jest faktycznie I combinator. Czy ktoś zauważył?

Answer 1

Problem polega na tym, że używasz ściśle ocenianego języka programowania. Kombinator Y, podobnie jak każdy inny kombinator punktowy, będzie działał poprawnie tylko wtedy, gdy twoje funkcje będą wywoływane w razie potrzeby lub "leniwie oceniane".

Wiem sposób obejścia tego (one of my professors looked into it a while ago), ale spowoduje to, że twój kod będzie całkowicie nieczytelny.

Poniżej dokładnie opisałem, co się dzieje, mając nadzieję, że widzisz, dlaczego JavaScript nie radzi sobie z prostą implementacją SKI-calculus.

---

To co Y wygląda po JavaScript ocenia swoją Wyciąg wyrażenie:

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

Teraz zobaczmy, co się stanie, jeśli karmisz to czynność function (fac) { ... }. Nazwijmy tę funkcję f:

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

Ponieważ pierwsza funkcja anonimowa stosuje się do argumentu, zostanie oceniona w ten sposób:

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

W leniwie ocenianego języku argument do f będzie teraz pozostać w spokoju, a sama ocena zostanie oszacowana. Jednakże, ponieważ JavaScript jest ściśle ocenianym językiem (lub "wartością wywołania po wartości"), chce on wiedzieć, jaki argument musi przejść do funkcji f przed uruchomieniem tej funkcji. Więc, oceńmy ten argument, dobrze?

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

Chyba teraz zaczynasz widzieć teraz gdzie coś pójdzie nie tak i jak Y-syntezatora faktycznie działa. W każdym razie twój JavaScript będzie miał mało miejsca na stosie, ponieważ próbuje zbudować nieskończony stos wywołań na f.