Por que os Trampolins funcionam?

A razão pela qual seu cérebro está se rebelando contra a função loopy() é que ele é de um 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!
    }
};

Muitas linguagens nem permitem que você faça coisas assim, ou pelo menos exigem muito mais digitação para explicar como isso deve fazer algum sentido. Porque isso não acontece. Funções e inteiros são tipos totalmente diferentes de objetos.

Então, vamos analisar esse loop while com cuidado:

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

Inicialmente, foo é igual a loopy(0) . O que é loopy(0) ? Bem, é menos que 10000000, então recebemos function(){return loopy(1)} . Esse é um valor geral, e é uma função, então o loop continua.

Agora chegamos a foo = foo() . foo() é o mesmo que loopy(1) . Como 1 ainda é menor que 10000000, isso retorna function(){return loopy(2)} , que então atribuímos a foo .

foo ainda é uma função, então continuamos ... até que foo seja igual a function(){return loopy(10000000)} . Essa é uma função, por isso fazemos foo = foo() mais uma vez, mas desta vez, quando chamamos loopy(10000000) , x não é menor que 10000000, então recuperamos x. Como 10000000 também não é uma função, isso também encerra o loop while.

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.

Talvez seja mais fácil entender se o trampolim é implementado com um tipo de retorno dedicado (em vez de abusar de uma função):

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 isso com sua versão de trampoline , em que o caso de recursão é quando a função retorna outra função e o caso base é quando ela retorna algo diferente.

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

Não se chama mais. Em vez disso, ele retorna um resultado (na minha implementação, literalmente, um Result ) que transmite a continuação da recursão ou a quebra.

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

Sim, isso é exatamente o mal necessário do loop. Pode-se escrever trampoline sem mutação também, mas isso exigiria recursão novamente:

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

Ainda assim, mostra a ideia do que a função de trampolim faz ainda melhor.

O ponto de trampolim é abstrair a chamada recursiva da cauda da função que deseja usar a recursão em um valor de retorno e fazer a recursão real em apenas um lugar - a função trampoline , que pode então ser otimizado em um único lugar para usar um loop.