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.