Há alguma chamada final (TCO) de mecanismo JavaScript otimizado?

91

Eu tenho um algoritmo de pathfinding recursivo que implementei em JavaScript e gostaria de saber se algum (todos?) Navegadores possivelmente obteriam exceções de estouro de pilha.

javascript functional-programming tail-recursion clofresh
fonte
2
É realmente um algoritmo recursivo ou um algoritmo iterativo implementado com recursão? Meu entendimento é que o TCO só pode ajudar com o último.
nmichaels
1
Só quero acrescentar que o TCO não é onlyuma otimização. O suporte deve ser parte da especificação da linguagem, não o compilador / interpretador, pois o código escrito em um interpretador / compilador com TCO provavelmente não funcionaria em um interpretador / compilador sem TCO.
Hoffmann
1
Você pode ver o suporte atual e vê-lo evoluir entre os motores na tabela de compatibilidade ES6 da Kangax aqui: kangax.github.io/compat-table/es6/…
Roy Tinker

Respostas:

47

A especificação ECMAScript 4 iria originalmente adicionar suporte para TCO, mas foi descartada:

Não há mais chamadas finais em JavaScript?

Pelo que eu sei, nenhuma implementação amplamente disponível de JavaScript atualmente faz TCO automático. Isso pode ser útil para você, no entanto:

Otimização de chamada final

Essencialmente, o uso do padrão de acumulador produz o mesmo efeito.

Tim Sylvester
fonte
1
Apenas um FYI, Rhino tem TCO automático junto com Continuações no modo "interpretado" (opt = -1) wiki.apache.org/cocoon/RhinoWithContinuations
Mark Porter
5
(desculpe por trolling) ECMAScript 6 incluiu TCO, denominado Chamadas de cauda adequadas na especificação.
gelado de
@sclv: Qual é a referência do trampolim?
bukzor
39
O padrão do acumulador não produz o mesmo efeito que o TCO. Ele simplesmente transforma algoritmos recursivos em forma recursiva de cauda. Este é um pré-requisito para que o TCO seja possível, mas não é um substituto para ele. Você ainda vai explodir em uma linguagem que não otimiza chamadas finais.
Marcelo Cantos
"nenhuma implementação amplamente disponível de JS atualmente faz TCO automático" isso está incorreto no Nó 6.2.0, se você passar a sinalização certa
Janus Troelsen
26

Não há alegria no momento, mas felizmente chamadas finais adequadas estão programadas para Harmony (ECMAScript versão 6) http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls

Sr. Orador
fonte
1
@MarkWilbur A questão era especificamente sobre navegadores , nem todas as implementações existentes de ECMAScript.
Código inútil
1
@UselessCode Não, esta pergunta é sobre "mecanismos Javascript", então ... não apenas navegadores
BT
1
@BT Existem de fato muitos ambientes JS sem navegadores, e o título usa os "mecanismos Javascript" mais genéricos, mas o corpo da pergunta especifica "... gostaria de saber se algum (todos?) Navegadores possivelmente ficariam em pilha exceções de estouro. "
Código inútil de
Tenho que rebater "mas o título diz ...". Eu acho que porque ele menciona ambos, a questão é sobre ambos. Mas você está certo se está dizendo que isso não torna a resposta obsoleta.
BT
4
@MarkWilbur Até onde eu sei, o nó usa a mesma versão do v8 do cromo - que atualmente não suporta o TCO. Eu tinha uma essência com o JS e o assembler otimizado que o V8 atual produz - gist.github.com/mcfedr / 832e3553964a014621d5
mcfedr
12

Quase todos os navegadores que você encontrar irão vomitar em "demasiada recursão". Aqui está uma entrada no rastreador de bug V8 que provavelmente será uma leitura interessante.

Se for simples auto-recursão, provavelmente vale a pena o esforço para usar a iteração explícita em vez de esperar pela eliminação da chamada final.

Hank Gay
fonte
O bug foi finalmente aceito. Está sob o título épico: "Feature Request Harmony". Esperançosamente, isso significa que eles planejam adicioná-lo ao suporte ES6 no V8.
Txangel
Você pode votar no suporte de TCO no Internet Explorer aqui: wpdev.uservoice.com/forums/257854-internet-explorer-platform/…
Roy Tinker
12

A otimização da chamada final será suportada no modo estrito ECMAScript 6 no futuro. Verifique http://www.2ality.com/2015/06/tail-call-optimization.html para obter detalhes.

Verifique http://kangax.github.io/compat-table/es6/ para obter suporte de mecanismo atual.

No momento (18-07-2019), os seguintes mecanismos são compatíveis com a otimização da chamada final:

  • Safari> = 10
  • iOS> = 10
  • Kinoma XS6
  • Duktape 2.3

suporte se "recursos experimentais de JavaScript" -flag estiver ativado:

  • Nó 6.5
  • Chrome 54 / Opera 41 A versão atual da tabela de compatibilidade não a lista mais
Simon Zyx
fonte
3

A otimização da chamada Tail agora está disponível em LispyScript, que compila em JavaScript. Você pode ler mais sobre isso aqui .

Santosh
fonte
E quanto à recursão mútua?
gato
2

Atualmente, nenhuma implementação de JavaScript reconhece recursão de cauda. Mudanças estão sendo feitas no ECMAScript 6 e, como outros já disseram, há um tíquete em aberto no V8 .

Aqui você pode ver o assembler gerado pelo V8 para uma função de recursão final:

Exemplo de como o V8 compila a recursão

Compare isso com a forma como o Clang compilou a mesma função em C

Exemplo de recursão da cauda do compilador C

O V8 retém a chamada recursiva, enquanto o compilador C reconheceu a recursão final e a transformou em um loop.

mcfedr
fonte
"Atualmente, nenhuma implementação de JS reconhece recursão de cauda." isso está incorreto no Nó 6.2.0, mas você precisa passar um sinalizador
Janus Troelsen