Esprimendo Y in termini di Combinatori SKI in JavaScript

Question

Stavo armeggiando con i Cominator in JavaScript ed ero orgoglioso di (si spera) riuscendo a far funzionare S quando mi sono imbattuto in Wikipedia dicendo: "Il combinatore Y può essere espresso nello SKI- calcolo come: Y = S (K (SII)) (S (S (KS) K) (K (SII)))", così ho dovuto provare che:

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 

che cosa sto facendo di sbagliato? Non sto traducendo correttamente quell'espressione? C'è qualcosa di sbagliato in come sto andando su questo? Ha senso? La maggior parte di ciò che si deve leggere su cose del genere fa desiderare al mio cervello di esplodere, quindi il punto di questo esercizio per me è stato principalmente quello di vedere se ho compreso la notazione (e sarei quindi in grado di tradurla in JavaScript).

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

Answer 1

Il problema è che si sta utilizzando un linguaggio di programmazione strettamente valutato. Il combinatore Y, praticamente come qualsiasi altro combinatore a virgola fissa, funzionerà correttamente solo quando le funzioni vengono chiamate in base alle necessità o "valutate pigramente".

Sono a conoscenza di un modo per aggirare questo problema (one of my professors looked into it a while ago), ma renderà il codice completamente illeggibile.

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

---

Questo è ciò che appare come Y dopo JavaScript valutato il vostro SCI-espressione:

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

Ora vediamo cosa succede se si alimentano la funzione function (fac) { ... }. Chiamiamo questa funzione f:

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

Dal momento che la prima funzione anonima viene applicata a un argomento, sarà valutata in questo:

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

In un linguaggio pigramente valutato, l'argomento per f sarebbe ora essere lasciato da solo, e sarebbe stato valutato f stesso. Tuttavia, poiché JavaScript è un linguaggio strettamente valutato (o 'call-by-value'), vuole 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 ora che stai iniziando a vedere ora dove le cose vanno male, e come funziona il combinatore Y. In ogni caso, la tua macchina JavaScript esaurirà lo spazio di stack, perché sta cercando di creare una serie infinita di chiamate su f.