¿Por qué funcionan los trampolines?

He estado haciendo algunos JavaScript funcionales. Pensé que se había implementado Tail-Call Optimization , pero resultó que estaba equivocado. Por lo tanto, tuve que enseñarme el trampolín . Después de leer un poco aquí y en otros lugares, pude obtener lo básico y construí mi primer trampolín:

/*not the fanciest, it's just meant to
reenforce that I know what I'm doing.*/

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

function trampoline(foo){
    while(foo && typeof foo === 'function'){
        foo = foo();
    }
    return foo;
/*I've seen trampolines without this,
mine wouldn't return anything unless
I had it though. Just goes to show I
only half know what I'm doing.*/
};

alert(trampoline(loopy(0)));

Mi mayor problema es que no sé por qué esto funciona. Tengo la idea de volver a ejecutar la función en un ciclo while en lugar de usar un ciclo recursivo. Excepto, técnicamente mi función base ya tiene un bucle recursivo. No estoy ejecutando la loopyfunción base , pero estoy ejecutando la función dentro de ella. ¿Qué impide que se foo = foo()produzca un desbordamiento de pila? ¿Y no está foo = foo()técnicamente mutando, o me estoy perdiendo algo? Quizás es solo un mal necesario. O alguna sintaxis que me falta.

¿Hay alguna manera de entenderlo? ¿O es solo un truco que de alguna manera funciona? He podido abrirme camino a través de todo lo demás, pero este me tiene confundido.

La razón por la cual su cerebro se está rebelando contra la función loopy()es que es de un tipo inconsistente :

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!
    }
};

Muchos idiomas ni siquiera te permiten hacer cosas como esta, o al menos exigen mucho más tipeo para explicar cómo se supone que esto tiene algún tipo de sentido. Porque realmente no lo hace. Las funciones y los enteros son tipos de objetos totalmente diferentes.

Así que veamos ese ciclo while, con cuidado:

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

Inicialmente, fooes igual a loopy(0). ¿Qué es loopy(0)? Bueno, es menos de 10000000, así que lo tenemos function(){return loopy(1)}. Ese es un valor verdadero, y es una función, por lo que el ciclo continúa.

Ahora llegamos a foo = foo(). foo()es el mismo que loopy(1). Como 1 todavía es inferior a 10000000, eso devuelve function(){return loopy(2)}, que luego asignamos foo.

foosigue siendo una función, así que seguimos adelante ... hasta que eventualmente foo es igual a function(){return loopy(10000000)}. Esa es una función, así que lo hacemos foo = foo()una vez más, pero esta vez, cuando llamamos loopy(10000000), x no es inferior a 10000000, así que solo recuperamos x. Como 10000000 tampoco es una función, esto también finaliza el ciclo while.

Kevin señala sucintamente cómo funciona este fragmento de código en particular (junto con por qué es bastante incomprensible), pero quería agregar información sobre cómo funcionan los trampolines en general .

Sin la optimización de llamada de cola (TCO), cada llamada de función agrega un marco de pila a la pila de ejecución actual. Supongamos que tenemos una función para imprimir una cuenta regresiva de números:

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

Si llamamos countdown(3), analicemos cómo se vería la pila de llamadas sin 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, cada llamada recursiva a countdownestá en posición de cola (no queda nada más que hacer que devolver el resultado de la llamada), por lo que no se asigna ningún marco de pila. Sin TCO, la pila explota incluso un poco más grande n.

El trampolín evita esta restricción insertando un contenedor alrededor de la countdownfunción. Luego, countdownno realiza llamadas recursivas y en su lugar, inmediatamente devuelve una función para llamar. Aquí hay un ejemplo de implementación:

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);
  }
}

Para tener una mejor idea de cómo funciona esto, veamos la pila de llamadas:

> 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

En cada paso, la countdownHopfunción abandona el control directo de lo que sucede a continuación, en cambio devuelve una función para llamar que describe lo que le gustaría que suceda a continuación. La función de trampolín toma esto y lo llama, luego llama a cualquier función que regrese, y así sucesivamente hasta que no haya un "siguiente paso". Esto se llama trampolín porque el flujo de control "rebota" entre cada llamada recursiva y la implementación del trampolín, en lugar de que la función se repita directamente. Al abandonar el control sobre quién hace la llamada recursiva, la función de trampolín puede garantizar que la pila no sea demasiado grande. Nota al margen: esta implementación de trampolineomite valores de retorno por simplicidad.

Puede ser complicado saber si es una buena idea. El rendimiento puede verse afectado debido a que cada paso asigna un nuevo cierre. Las optimizaciones inteligentes pueden hacer que esto sea viable, pero nunca se sabe. El trampolín es principalmente útil para sortear los límites de recursión, por ejemplo, cuando una implementación de lenguaje establece un tamaño máximo de pila de llamadas.

Quizás sea más fácil de entender si el trampolín se implementa con un tipo de retorno dedicado (en lugar de abusar de una función):

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));

Compare esto con su versión de trampoline, donde el caso de recursión es cuando la función devuelve otra función, y el caso base es cuando devuelve algo más.

¿Qué impide que se foo = foo()produzca un desbordamiento de pila?

Ya no se llama a sí mismo. En cambio, devuelve un resultado (en mi implementación, literalmente a Result) que transmite si continuar la recursión o si estallar.

¿Y no está foo = foo()técnicamente mutando, o me estoy perdiendo algo? Quizás es solo un mal necesario.

Sí, este es exactamente el mal necesario del bucle. trampolineTambién se podría escribir sin mutación, pero requeriría recurrencia nuevamente:

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;
}

Aún así, muestra la idea de lo que la función de trampolín hace aún mejor.

El objetivo del trampoling es abstraer la llamada recursiva de la cola de la función que quiere usar la recursión en un valor de retorno, y hacer la recursión real en un solo lugar: la trampolinefunción, que luego se puede optimizar en un solo lugar para usar un lazo.