Esprimendo Y in termini di SKI-Combinators in JavaScript

Question

Stavo giocherellando con Cominators in JavaScript ed ero orgoglioso (si spera) di far funzionare S quando mi sono imbattuto in Wikipedia che dice: "Il combinatore Y può essere espresso nel calcolo SKI come: Y= S (K (SII)) (S (S (KS) K) (K (SII))) ", quindi ho dovuto provarlo:

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

Cosa sto facendo di sbagliato?Non sto traducendo correttamente quell'espressione?C'è qualcosa di sbagliato in come sto andando a riguardo?Ha anche senso?La maggior parte di ciò che si legge su cose del genere fa solo venire voglia al mio cervello di esplodere, quindi il punto di questo esercizio per me era principalmente vedere se capivo la notazione (e sarei quindi in grado di tradurla in JavaScript).p>

Oh, a proposito: quello che mi ha fatto leggere e armeggiare di nuovo è stato che ciò che prototype.js implementa come Prototype.K è in realtà il combinatore I.Qualcuno l'ha notato?

Answer 1

Il problema qui è che stai usando un linguaggio di programmazione rigorosamente valutato. Il combinatore Y, più o meno come qualsiasi altro combinatore a punto fisso, funzionerà correttamente solo quando le tue funzioni vengono chiamate per necessità o "valutate pigramente".

Conosco un modo per aggirare questo problema ( uno dei miei professori ha esaminato tempo fa ), ma renderà il tuo codice completamente illeggibile.

Di seguito ho mostrato cosa sta succedendo esattamente, sperando che tu possa capire perché JavaScript non è in grado di gestire un'implementazione diretta del calcolo SKI.

---

Ecco come appare Y dopo che JavaScript ha valutato la tua espressione SKI:

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

Ora vediamo cosa succede se gli inserisci la tua funzione function (fac) { ... }. Chiamiamo quella funzione f:

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

Poiché la prima funzione anonima viene applicata a un argomento, verrà valutata in questo:

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

In un linguaggio valutato pigramente, l'argomento di f sarebbe ora lasciato da solo e lo stesso f verrebbe valutato. Tuttavia, poiché JavaScript è un linguaggio rigorosamente valutato (o "chiamata per valore"), desidera sapere quale argomento deve passare alla funzione f prima di eseguire effettivamente quella funzione. Quindi valutiamo questo argomento, vero?

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

Immagino che ora tu stia iniziando a vedere dove le cose vanno storte e come funziona effettivamente il combinatore Y. In ogni caso, la tua macchina JavaScript esaurirà lo spazio dello stack, perché sta cercando di creare uno stack infinito di chiamate a f.