Por que os trampolins funcionam?

104

Eu tenho feito algum JavaScript funcional. Eu pensava que a Otimização de chamada de cauda havia sido implementada, mas, como se vê, eu estava errado. Assim, eu tive que me ensinar trampolim . Depois de ler um pouco aqui e em outros lugares, consegui entender o básico e construí meu primeiro trampolim:

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

Meu maior problema é que não sei por que isso funciona. Tenho a ideia de executar novamente a função em um loop while, em vez de usar um loop recursivo. Exceto que tecnicamente minha função base já possui um loop recursivo. Não estou executando a loopyfunção base , mas estou executando a função dentro dela. O que está impedindo foo = foo()de causar um estouro de pilha? E não é foo = foo()tecnicamente mutante, ou estou faltando alguma coisa? Talvez seja apenas um mal necessário. Ou falta alguma sintaxe.

Existe alguma maneira de entender isso? Ou é apenas algum truque que de alguma forma funciona? Eu fui capaz de fazer o meu caminho através de todo o resto, mas este me deixou perplexo.

Ucenna
fonte
5
Sim, mas isso ainda é recursão. loopynão transborda porque não se chama .
tkausl
4
"Eu pensava que o TCO havia sido implementado, mas, no fim, eu estava errado." Foi pelo menos no V8 na maioria dos cenários. Você pode usá-lo, por exemplo, em qualquer versão recente do Node, dizendo ao Node para habilitá-lo na V8: stackoverflow.com/a/30369729/157247 O Chrome o possui (atrás de uma bandeira "experimental") desde o Chrome 51.
TJ Crowder,
125
A energia cinética do usuário é transformada em energia potencial elástica à medida que o trampolim afunda, depois volta à energia cinética à medida que se recupera.
user253751
66
@immibis, em nome de todos que vieram aqui sem verificar qual site do Stack Exchange era esse, obrigado.
user1717828
4
@jpaugh você quis dizer "pulando"? ;-)
Hulk

Respostas:

89

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

Muitos idiomas 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 realmente não. Funções e números inteiros são tipos totalmente diferentes de objetos.

Então, vamos passar por 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 chegamos function(){return loopy(1)}. Esse é um valor verdadeiro, e é uma função, para que o loop continue.

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

fooainda é uma função, então continuamos ... até que foo seja igual a function(){return loopy(10000000)}. Essa é uma função, então fazemos foo = foo()mais uma vez, mas desta vez, quando chamamos loopy(10000000), x não é inferior a 10000000, portanto, apenas recebemos x de volta. Como 10000000 também não é uma função, isso encerra o loop while.

Kevin
fonte
1
Comentários não são para discussão prolongada; esta conversa foi movida para o bate-papo .
yannis
É realmente apenas um tipo de soma. Às vezes conhecido como uma variante. Os idiomas dinâmicos os suportam com bastante facilidade porque todos os valores são marcados, enquanto outros idiomas digitados estaticamente exigirão que você especifique que a função retorna uma variante. Trampolins são facilmente possíveis em C ++ ou Haskell, por exemplo.
GManNickG 12/10
2
@GManNickG: Sim, é isso que eu quis dizer com "muito mais digitação". Em C, você teria que declarar uma união, declarar uma estrutura que marque a união, empacote e descompacte a estrutura em uma das extremidades, empacote e descompacte a união em uma das extremidades e (provavelmente) descobrir quem é o proprietário da memória na qual a estrutura habita . O C ++ provavelmente é menos código que isso, mas conceitualmente não é menos complicado que o C, e ainda é mais detalhado que o Javascript do OP.
Kevin
Claro, não estou contestando isso, apenas acho que a ênfase que você coloca em ser estranho ou não fazer sentido é um pouco forte. :)
GManNickG
173

Kevin aponta sucintamente como esse trecho de código específico funciona (junto com o motivo pelo qual é bastante incompreensível), mas eu queria adicionar algumas informações sobre como os trampolins em geral funcionam.

Sem otimização de chamada de cauda (TCO), toda 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 ligarmos countdown(3), vamos analisar como ficaria a pilha de chamadas sem o 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 countdownestá na posição final (não há mais nada a fazer além de retornar o resultado da chamada), portanto, nenhum quadro de pilha é alocado. Sem o TCO, a pilha explode para um pouco maior n.

O trampolim contorna essa restrição inserindo um invólucro em torno da countdownfunção. Em seguida, countdownnão realiza chamadas recursivas e 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 noção melhor de como isso funciona, vejamos 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 countdownHopfunção abandona o controle direto do que acontece a seguir, em vez disso, retorna uma função para chamar que descreve o que gostaria que acontecesse a seguir. 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 "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 diretamente recorrente. Ao abandonar o controle sobre quem faz a chamada recursiva, a função trampolim pode garantir que a pilha não fique muito grande. Nota lateral: esta implementação trampolineomite os valores retornados por simplicidade.

Pode ser complicado saber se essa é 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 é útil principalmente para contornar limites rígidos de recursão, por exemplo, quando uma implementação de idioma define um tamanho máximo de pilha de chamadas.

Jack
fonte
18

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 a sua versão de trampoline, onde o caso de recursão é quando a função retorna outra função, e o caso base é quando retorna outra coisa.

O que está impedindo foo = foo()de causar um estouro de pilha?

Não se chama mais. Em vez disso, ele retorna um resultado (na minha implementação, literalmente a Result) que indica se deve continuar a recursão ou se deve ocorrer .

E não é foo = foo()tecnicamente mutante, ou estou faltando alguma coisa? Talvez seja apenas um mal necessário.

Sim, este é exatamente o mal necessário do loop. Pode-se escrever trampolinesem mutação também, mas 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 idéia do que a função trampolim faz ainda melhor.

O objetivo do trampolim é abstrair a chamada recursiva da função que deseja usar a recursão em um valor de retorno e fazer a recursão real em apenas um local - a trampolinefunção, que pode ser otimizada em um único local para usar um ciclo.

Bergi
fonte
foo = foo()é uma mutação no sentido de modificar o estado local, mas geralmente considero que a reatribuição como você não está realmente modificando o objeto de função subjacente, está substituindo-o pela função (ou valor) que ele retorna.
JAB
@ JAB Sim, eu não quis sugerir a mutação do valor que foocontém, apenas a variável é modificada. Um whileloop requer algum estado mutável se você deseja finalizar, neste caso a variável fooou x.
Bergi 11/10
Eu fiz algo assim há algum tempo atrás nesta resposta a uma pergunta do Stack Overflow sobre otimização de chamada de cauda, ​​trampolins etc.
Joshua Taylor
2
Sua versão sem mutação converteu uma chamada recursiva de fnem uma chamada recursiva para trampoline- não tenho certeza se isso é uma melhoria.
Michael Anderson
1
@MichaelAnderson É apenas para demonstrar a abstração. Claro que um trampolim recursivo não é útil.
Bergi 13/10/19