Perché i trampolini funzionano?

Il motivo per cui il tuo cervello si ribella alla funzione loopy() è che è di tipo incoerente :

function loopy(x){
    if (x<10000000){ 
        return function(){ // On this line it returns a function...
            // (This is not part of loopy(), this is the function we are returning.)
            return loopy(x+1)
        }
    }else{
        return x; // ...but on this line it returns an integer!
    }
};

Un bel po 'di lingue non ti permettono nemmeno di fare cose del genere, o almeno richiedono molto più digitazione per spiegare come questo dovrebbe avere senso. Perché in realtà non lo è. Le funzioni e gli interi sono tipi di oggetti completamente diversi.

Quindi esaminiamo il ciclo while, attentamente:

while(foo && typeof foo === 'function'){
    foo = foo();
}

Inizialmente, foo è uguale a loopy(0) . Cos'è loopy(0) ? Bene, è inferiore a 10000000, quindi otteniamo function(){return loopy(1)} . Questo è un valore di verità, ed è una funzione, quindi il ciclo continua.

Ora arriviamo a foo = foo() . foo() è uguale a loopy(1) . Poiché 1 è ancora inferiore a 10000000, restituisce function(){return loopy(2)} , che assegniamo quindi a foo .

foo è ancora una funzione, quindi continuiamo a ... finché finalmente foo è uguale a function(){return loopy(10000000)} . Questa è una funzione, quindi facciamo foo = foo() ancora una volta, ma questa volta, quando chiamiamo loopy(10000000) , x non è inferiore a 10000000, quindi otteniamo x indietro. Poiché anche il 10000000 non è una funzione, anche questo termina il ciclo while.

Kevin sottolinea succintamente come funziona questo particolare frammento di codice (insieme al motivo per cui è abbastanza incomprensibile), ma volevo aggiungere alcune informazioni su come funzionano i in generale .

Senza ottimizzazione tail-call (TCO), ogni chiamata di funzione aggiunge uno stack frame allo stack di esecuzione corrente. Supponiamo di avere una funzione per stampare un conto alla rovescia dei numeri:

function countdown(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    countdown(n - 1);
  }
}

Se chiamiamo countdown(3) , analizziamo l'aspetto dello stack di chiamate senza TCO.

> countdown(3);
// stack: countdown(3)
Launch in 3
// stack: countdown(3), countdown(2)
Launch in 2
// stack: countdown(3), countdown(2), countdown(1)
Launch in 1
// stack: countdown(3), countdown(2), countdown(1), countdown(0)
Blastoff!
// returns, stack: countdown(3), countdown(2), countdown(1)
// returns, stack: countdown(3), countdown(2)
// returns, stack: countdown(3)
// returns, stack is empty

Con TCO, ogni chiamata ricorsiva a countdown si trova in posizione di coda (non rimane altro da fare che restituire il risultato della chiamata) in modo che non venga allocato alcun frame dello stack. Senza TCO, la pila esplode anche con un% din leggermente più grande.

Il trampolino aggira questa restrizione inserendo un wrapper attorno alla funzione countdown . Quindi, countdown non esegue chiamate ricorsive e restituisce immediatamente una funzione da chiamare. Ecco un'implementazione di esempio:

function trampoline(firstHop) {
  nextHop = firstHop();
  while (nextHop) {
    nextHop = nextHop()
  }
}

function countdown(n) {
  trampoline(() => countdownHop(n));
}

function countdownHop(n) {
  if (n === 0) {
    console.log("Blastoff!");
  } else {
    console.log("Launch in " + n);
    return () => countdownHop(n-1);
  }
}

Per avere un'idea migliore di come funziona, diamo un'occhiata allo stack delle chiamate:

> countdown(3);
// stack: countdown(3)
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(3)
Launch in 3
// return next hop from countdownHop(3)
// stack: countdown(3), trampoline
// trampoline sees hop returned another hop function, calls it
// stack: countdown(3), trampoline, countdownHop(2)
Launch in 2
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(1)
Launch in 1
// stack: countdown(3), trampoline
// stack: countdown(3), trampoline, countdownHop(0)
Blastoff!
// stack: countdown(3), trampoline
// stack: countdown(3)
// stack is empty

Ad ogni passo la funzione countdownHop abbandona controlla direttamente ciò che succede dopo, invece restituisce una funzione da chiamare che descrive come come succederà dopo. La funzione trampolino prende quindi questo e lo chiama, quindi chiama qualsiasi funzione che restituisce, e così via fino a quando non c'è un "passo successivo". Questo è chiamato trampolino perché il flusso di controllo "rimbalza" tra ogni chiamata ricorsiva e l'implementazione del trampolino, invece della funzione che ricorre direttamente. Abbandonando il controllo su chi fa la chiamata ricorsiva, la funzione trampolino può garantire che lo stack non diventi troppo grande. Nota a margine: questa implementazione di trampoline omette di restituire i valori per semplicità.

Può essere difficile sapere se questa è una buona idea. Le prestazioni possono soffrire a causa di ogni fase che alloca una nuova chiusura. Ottimizzazioni intelligenti possono renderlo praticabile, ma non si sa mai. Il trampolino è utile soprattutto per aggirare i limiti di ricorsione rigidi, ad esempio quando un'implementazione linguistica imposta una dimensione massima dello stack di chiamata.

Forse diventa più facile capire se il trampolino è implementato con un tipo di ritorno dedicato (invece di abusare di una funzione):

class Result {}
// poor man's case classes
class Recurse extends Result {
    constructor(a) { this.arg = a; }
}
class Return extends Result {
    constructor(v) { this.value = v; }
}

function loopy(x) {
    if (x<10000000)
        return new Recurse(x+1);
    else
        return new Return(x);
}

function trampoline(fn, x) {
    while (true) {
        const res = fn(x);
        if (res instanceof Recurse)
            x = res.arg;
        else if (res instanceof Return)
            return res.value;
    }
}

alert(trampoline(loopy, 0));

Confrontalo con la tua versione di trampoline , dove il caso di ricorsione è quando la funzione restituisce un'altra funzione, e il caso base è quando restituisce qualcos'altro.

What's stopping foo = foo() from causing a stack overflow?

Non si chiama più. Invece, restituisce un risultato (nella mia implementazione, letteralmente un Result ) che trasmette se continuare la ricorsione o se scoppiare.

And isn't foo = foo() technically mutating, or am I missing something? Perhaps it's just a necessary evil.

Sì, questo è esattamente il male necessario del ciclo. Si potrebbe anche scrivere trampoline senza mutazione, ma richiederebbe nuovamente la ricorsione:

function trampoline(fn, x) {
    const res = fn(x);
    if (res instanceof Recurse)
        return trampoline(fn, res.arg);
    else if (res instanceof Return)
        return res.value;
}

Tuttavia, mostra l'idea di ciò che la funzione trampolino fa ancora meglio.

Il punto del trampoling è estrapolare la chiamata ricorsiva di coda dalla funzione che desidera utilizzare la ricorsione in un valore di ritorno e eseguire la ricorsione effettiva in un solo punto: la funzione trampoline , che può quindi essere ottimizzato in un unico punto per utilizzare un ciclo.