Será que as otimizações chamada cauda JVM proibir?

Question

Vi esta citação sobre a questão: O que é uma boa linguagem funcional sobre a qual construir um serviço web

Scala, em particular, não suporta a eliminação tail-call, exceto em funções auto-recursiva, o que limita os tipos de composição que você pode fazer (esta é uma limitação fundamental do JVM).

Isso é verdade? Se assim for, o que é sobre a JVM que cria essa limitação fundamental?

Answer 1

Este post:?. recursão ou iteração poderia ajudar

Em suma, otimização de chamada de cauda é difícil de fazer na JVM por causa do modelo de segurança ea necessidade de sempre ter um rastreamento de pilha disponível. Estes requisitos podem, em teoria, ser apoiada, mas provavelmente exigiria um novo bytecode (ver proposta informal John Rose ).

Há também uma discussão mais Sun bug # 4726340 , onde a avaliação (de 2002) extremidades:

Eu acredito que isso poderia ser feito, no entanto, mas não é uma tarefa pequena.

Atualmente, há algum trabalho acontecendo no Da Vinci Máquina projeto. O status do subprojeto chamada de cauda é listado como "proto 80%"; é improvável que fazê-lo em Java 7, mas acho que ele tem uma chance muito boa em Java 8.

Answer 2

A limitação fundamental é simplesmente que a JVM não fornece chamadas de cauda em seu código de byte e, consequentemente, não há nenhuma maneira direta para uma linguagem construída sobre a JVM para fornecer cauda chama a si mesmo. Existem soluções que podem alcançar um efeito similar (por exemplo trampolining) mas eles vêm com o custo de sepultura terrível desempenho e ofuscar o código intermediário gerado o que torna um depurador inútil.

Assim, a JVM não pode suportar qualquer linguagem de programação funcional com qualidade de produção até Sun implementar chamadas de cauda no próprio JVM. Eles vêm discutindo isso há anos, mas eu duvido que nunca vai implementar chamadas de cauda:. Ele vai ser muito difícil, porque eles têm prematuramente otimizado sua VM antes de implementar essa funcionalidade básica, e esforço da Sun está focada fortemente em linguagens dinâmicas, em vez de linguagens funcionais

Por isso há um argumento muito forte que Scala não é uma verdadeira linguagem de programação funcional:. Línguas têm considerado chamadas cauda como uma característica essencial, pois Scheme foi introduzido pela primeira vez há 30 anos

Answer 3

Scala 2.7.x suportes tail-call otimização de auto-recursão (a própria função chamada) de métodos finais e funções locais.

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

Uma boa quantidade de informações sobre o estado de Scala recursão pode ser encontrado em rich Dougherty blogue .

Answer 4

Além do papel ligado em Lambda The Ultimate (a partir do link mmyers postado acima), John Rose de Sun tem um pouco mais a dizer sobre otimização de chamada de cauda.

http://blogs.oracle.com/jrose/entry/tail_calls_in_the_vm

Ouvi dizer que ele pode ser implementado no dia JVM. suporte chamada de cauda entre outras coisas estão sendo analisados ??no Da Vinci máquina.

http://openjdk.java.net/projects/mlvm/

Answer 5

Todas as fontes apontam para a JVM sendo incapaz de otimizar no caso de recursão de cauda, ??mas ao ler Java ajuste de desempenho (2003, O'reilly) eu encontrei o autor alegando que ele pode conseguir maior desempenho recursão através da implementação de cauda recursão.

Você pode encontrar a sua reivindicação na página 212 (procurar 'recursão de cauda' que deveria ser o segundo resultado). O que dá?