A JVM impede otimizações de chamada final?

99

Eu vi esta citação sobre a pergunta: Qual é uma boa linguagem funcional para construir um serviço da web?

Scala, em particular, não oferece suporte à eliminação de chamadas finais, exceto em funções autorrecursivas, o que limita os tipos de composição que você pode fazer (esta é uma limitação fundamental da JVM).

Isso é verdade? Em caso afirmativo, o que há na JVM que cria essa limitação fundamental?

java jvm scala tail-recursion Jason Dagit
fonte

Respostas:

74

Este post: Recursão ou Iteração? pode ajudar.

Resumindo, a otimização da chamada final é difícil de fazer na JVM devido ao modelo de segurança e à necessidade de sempre ter um rastreamento de pilha disponível. Esses requisitos poderiam, em teoria, ser suportados, mas provavelmente exigiriam um novo bytecode (consulte a proposta informal de John Rose ).

Também há mais discussão no bug # 4726340 da Sun , onde a avaliação (de 2002) termina:

Acredito que isso poderia ser feito mesmo assim, mas não é uma tarefa fácil.

Atualmente, há algum trabalho em andamento no projeto da Máquina Da Vinci . O status do subprojeto da chamada final é listado como "proto 80%"; é improvável que chegue ao Java 7, mas acho que tem uma boa chance no Java 8.

Michael Myers
fonte
Não segui bem a explicação. Achei que a otimização da chamada final foi implementada pelo compilador. Supondo que você tenha uma função que pode ser otimizada pela chamada final pelo compilador, você também pode ter uma função não recursiva equivalente que implemente a mesma funcionalidade usando um loop, correto? Se sim, isso não poderia ser feito pelo compilador. Não estou conseguindo acompanhar a dependência do JVM. Como isso se compara a um compilador Scheme que gerou código i386 nativo?
Gautham Ganapathy
4
@Gautham: Minha declaração sobre a depuração referia-se ao uso de trampolins como uma solução alternativa para a falta de eliminação de chamada final na JVM. A eliminação da chamada de cauda pode e foi implementada no JVM (Arnold Schaighofer fez no OpenJDK e também no LLVM), portanto, não há dúvida se isso pode ou não ser feito. O CLR da Microsoft tem, é claro, apoiado a eliminação de chamadas finais por 10 anos e o lançamento do F # demonstrou que é uma virada de jogo. Acho que a resposta é que a JVM há muito estagnou.
JD
3
Este é um equívoco comum e uma desculpa freqüentemente repetida, mas está incorreto. Há vários anos está bem estabelecido que a segurança por inspeção de pilha (e o fornecimento de rastreamentos de pilha úteis) não é incompatível com chamadas de cauda adequadas. Por exemplo, veja este papel a partir de 2004. citeseerx.ist.psu.edu/viewdoc/... downvoting, como a resposta está incorreta.
Justin Sheehy
5
@JustinSheehy: O que está incorreto? A pergunta era: "A JVM impede otimizações de chamada final?" E a resposta é: "Não, mas é difícil."
Michael Myers
5
você sabe se em java8 isso está incluído?
nachokk
27

A limitação fundamental é simplesmente que a JVM não fornece chamadas finais em seu código de bytes e, conseqüentemente, não há uma maneira direta para uma linguagem construída sobre a JVM fornecer chamadas finais em si. Existem soluções alternativas que podem atingir um efeito semelhante (por exemplo, trampolim), mas elas têm um custo grave de desempenho terrível e ofuscamento do código intermediário gerado, o que torna um depurador inútil.

Portanto, a JVM não pode suportar nenhuma linguagem de programação funcional com qualidade de produção até que a Sun implemente as chamadas finais na própria JVM. Eles vêm discutindo isso há anos, mas duvido que algum dia implementem chamadas finais: será muito difícil porque eles otimizaram prematuramente sua VM antes de implementar essa funcionalidade básica, e o esforço da Sun está fortemente focado em linguagens dinâmicas em vez de linguagens funcionais.

Portanto, há um argumento muito forte de que Scala não é uma linguagem de programação funcional real: essas linguagens consideram as chamadas finais como um recurso essencial desde que Scheme foi introduzido pela primeira vez, há 30 anos.

JD
fonte
5
Hence there is a very strong argument that Scala is not a real functional programming language - o argumento é bastante fraco. Claro que tail calls [as] an essential featuresim, e ótimo se o hardware subjacente (ou máquina virtual) oferecer suporte direto. Mas são detalhes de implementação.
Ingo
8
@Ingo: Somente se você não considerar o estouro de pilha em seu programa em tempo de execução visto pelo usuário como um problema significativo. De acordo com seu rastreador de bug, até o próprio compilador Scala foi atormentado por estouro de pilha. Então, mesmo os desenvolvedores de Scala mais experientes ainda estão errando ...
JD
7
É normal ser um defensor de, digamos, F #. Mas eu observei você por um longo tempo (mesmo anos antes na usenet) por ser hostil a tudo que não seja F #, e ainda assim suas elaborações mostram que você não sabe do que está falando. Como aqui: seu argumento parece ser que uma linguagem onde posso escrever um programa que aborta com estouro de pilha não é funcional? Mas não poderia o mesmo argumento ser feito para linguagens onde posso provocar estouro de pilha? Conseqüentemente, o próprio F # sagrado não contaria como funcional.
Ingo
7
@Ingo: Vários idiomas na programação funcional, como recursão mútua e estilo de passagem de continuação, podem exigir a eliminação de chamada final para funcionar. Sem ele, seus programas estourarão. Se uma linguagem não pode executar código funcional idiomático de forma confiável, ela é funcional? A resposta é um julgamento, como você diz, mas uma distinção importante na prática. Martin Trojer acaba de publicar um post interessante sobre isso: martinsprogrammingblog.blogspot.com/2011/11/…
JD
2
ainda assim, só porque a JVM (lamentavelmente, sem dúvida) não pode fazer chamadas finais, isso não significa que a eliminação das chamadas finais seja impossível. Isso é como se alguém declarasse que cálculos de ponto flutuante só são possíveis em computadores com FPUs.
Ingo de
22

Scala 2.7.x suporta otimização de chamada final para auto-recursão (uma função que chama a si mesma) de métodos finais e funções locais.

O Scala 2.8 pode vir com suporte de biblioteca para trampolim também, que é uma técnica para otimizar funções recursivas mutuamente.

Uma boa quantidade de informações sobre o estado da recursão de Scala pode ser encontrada no blog de Rich Dougherty .

Daniel C. Sobral
fonte
Você pode, por favor, atualizar a pergunta sobre o status atual do scala?
om-nom-nom
@ om-nom-nom AFAIK, nada mudou, nem no lado do Scala, nem no lado da JVM.
Daniel C. Sobral
0

Todas as fontes apontam para a JVM ser incapaz de otimizar no caso de recursão de cauda, ​​mas ao ler o ajuste de desempenho do Java (2003, O'reilly), descobri que o autor afirma que pode alcançar um desempenho de recursão maior implementando recursão de cauda.

Você pode encontrar sua afirmação na página 212 (procure por 'recursão da cauda', deve ser o segundo resultado). O que da?

pensador
fonte
A IBM oferece suporte a alguma forma de TCO em sua implementação JVM (como uma otimização, portanto, sem garantias). Talvez os autores do ajuste de desempenho do Java pensassem que esse recurso seria eventualmente implementado por todas as JVMs. ibm.com/developerworks/java/library/j-diag8.html
llemieng