Por que os Trampolins funcionam?

103

Eu tenho feito JavaScript funcional. Eu tinha pensado que Otimização de chamada de cauda tinha sido implementado, mas como se vê eu estava errado . Assim, eu tive que me ensinar Trampolining . Depois de ler um pouco aqui e em outros lugares, consegui fazer o básico e construir 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. Eu tenho a idéia de executar novamente a função em um loop while em vez de usar um loop recursivo. Exceto, tecnicamente, minha função base já possui um loop recursivo. Não estou executando a função loopy de 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 até uma maneira de entender isso? Ou é apenas um hack que de alguma forma funciona? Eu fui capaz de fazer o meu caminho através de todo o resto, mas este me deixou perplexo.

    
por Ucenna 11.10.2016 / 06:43
fonte

3 respostas

88

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.

    
por 11.10.2016 / 06:53
fonte
173

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.

    
por 11.10.2016 / 08:41
fonte
17

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.

    
por 11.10.2016 / 18:36
fonte