Kevin mostra sucintamente como esse trecho de código específico funciona (junto com o motivo de ser bastante incompreensível), mas eu queria adicionar algumas informações sobre como os trampolins em geral funcionam.
Sem otimização de chamada de ponta (TCO), cada chamada de função adiciona um quadro de pilha à pilha de execução atual. Suponha que tenhamos uma função para imprimir uma contagem regressiva de números:
function countdown(n) {
if (n === 0) {
console.log("Blastoff!");
} else {
console.log("Launch in " + n);
countdown(n - 1);
}
}
Se chamarmos countdown(3)
, vamos analisar como a pilha de chamadas ficaria sem 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
Com o TCO, cada chamada recursiva para countdown
está em posição final (não resta mais nada a fazer além de retornar o resultado da chamada) para que nenhum quadro de pilha seja alocado. Sem o TCO, a pilha explode mesmo para% de n
.
O trampolim contorna essa restrição inserindo um wrapper em torno da função countdown
. Em seguida, countdown
não executa chamadas recursivas e, em vez disso, retorna imediatamente uma função para chamar. Aqui está um exemplo de implementação:
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 ter uma ideia melhor de como isso funciona, vamos ver a pilha de chamadas:
> 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
Em cada etapa, a função countdownHop
abandona o controle direto do que acontece a seguir, em vez de retornar uma função para chamar que descreve o que gostaria acontecer em seguida. A função trampolim então pega e chama, então chama qualquer função que retorna, e assim por diante até que não haja o "próximo passo". Isso é chamado de trampolim porque o fluxo de controle "salta" entre cada chamada recursiva e a implementação do trampolim, em vez da função ser diretamente recorrente. Ao abandonar o controle sobre quem faz a chamada recursiva, a função do trampolim pode garantir que a pilha não fique muito grande. Nota lateral: esta implementação de trampoline
omite a devolução de valores para simplificar.
Pode ser complicado saber se é uma boa ideia. O desempenho pode sofrer devido a cada etapa que aloca um novo fechamento. Otimizações inteligentes podem tornar isso viável, mas você nunca sabe. O Trampolim é mais útil para contornar os limites de recursão, por exemplo, quando uma implementação de idioma define um tamanho máximo de pilha de chamada.