¿Por qué funcionan las camas elásticas?

La razón por la que 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 mucha más escritura para explicar cómo se supone que esto debe tener algún tipo de sentido. Porque realmente no lo hace. Las funciones y los enteros son tipos de objetos totalmente diferentes.

Así que vamos a recorrer ese bucle while, con cuidado:

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

Inicialmente, foo es igual a loopy(0) . ¿Qué es loopy(0) ? Bueno, es menos de 10000000, por lo que obtenemos 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 lo mismo que loopy(1) . Como 1 aún es inferior a 10000000, eso devuelve function(){return loopy(2)} , que luego asignamos a foo .

foo sigue siendo una función, por lo que seguimos adelante ... hasta que eventualmente foo sea igual a function(){return loopy(10000000)} . Esa es una función, por lo que hacemos foo = foo() una vez más, pero esta vez, cuando llamamos a loopy(10000000) , x no es menos de 10000000, por lo que solo obtenemos x. Dado que 10000000 tampoco es una función, esto también finaliza el ciclo while.

Kevin señala de manera sucinta cómo funciona este fragmento de código en particular (además de por qué es bastante incomprensible), pero quería agregar información sobre cómo funcionan las 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 a countdown(3) , analicemos cómo se vería la pila de llamadas sin el 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 countdown está en tail position (no hay nada más que hacer que devolver el resultado de la llamada), por lo que no se asigna un marco de pila. Sin TCO, la pila explota incluso para n ligeramente grande.

El trampolín evita esta restricción insertando una envoltura alrededor de la función countdown . Entonces, countdown no realiza llamadas recursivas y en su lugar devuelve inmediatamente una función para llamar. Aquí hay una implementación de ejemplo:

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 función countdownHop abandona el control directo de lo que sucede a continuación, en lugar de eso, devuelve una función a la que llama que describe lo que desea que suceda a continuación. La función del trampolín toma esto y lo llama, luego llama a la función que devuelve, y así sucesivamente hasta que no haya un "siguiente paso". Esto se denomina trampolín porque el flujo de control "rebota" entre cada llamada recursiva y la implementación del trampolín, en lugar de la función que se repite directamente. Al abandonar el control sobre quién realiza la llamada recursiva, la función del trampolín puede garantizar que la pila no sea demasiado grande. Nota al margen: esta implementación de trampoline omite los valores de retorno por simplicidad.

Puede ser difícil saber si esta es una buena idea. El rendimiento puede sufrir debido a cada paso de asignar un nuevo cierre. Las optimizaciones inteligentes pueden hacer esto 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.

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

Contrasta esto con tu 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 otra cosa.

  

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

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

  

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

Sí, este es exactamente el mal necesario del bucle. Uno podría escribir trampoline sin mutación también, pero requeriría una recursión 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 del trampolín hace aún mejor.

El punto de trampolín es abstraer la llamada recursiva de 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 función trampoline , que luego se puede optimizar en un solo lugar para usar un bucle.