Por que Java não tem otimização para recursão de cauda?

84

Pelo que li: O motivo é porque não é fácil determinar qual método será realmente chamado, já que temos herança.

No entanto, por que o Java não tem pelo menos uma otimização de recursão de cauda para métodos estáticos e aplica a maneira correta de chamar métodos estáticos com o compilador?

Por que o Java não oferece suporte algum para a recursão da cauda?

Não tenho certeza se há alguma dificuldade aqui.

Em relação à duplicação sugerida , como explicado por Jörg W Mittag 1 :

  • The other question asks about TCO, this one about TRE. TRE is much simpler than TCO.
  • Also, the other question asks about what limitations the JVM imposes on language implementations that wish to compile to the JVM, this question asks about Java, which is the one language that is not restricted by the JVM, since the JVM spec can be changed by the same people who design Java.
  • And lastly, there isn't even a restriction in the JVM about TRE, because the JVM does have intra-method GOTO, which is all that's needed for TRE

1 Formatação adicionada para chamar os pontos criados.

    
por InformedA 04.02.2015 / 09:40
fonte

5 respostas

121

Como explicado por Brian Goetz (arquiteto de linguagem Java da Oracle) neste vídeo :

in jdk classes [...] there are a number of security sensitive methods that rely on counting stack frames between jdk library code and calling code to figure out who's calling them.

Qualquer coisa que alterasse o número de quadros na pilha quebraria isso e causaria um erro. Ele admite que essa foi uma razão estúpida e, portanto, os desenvolvedores do JDK já substituíram esse mecanismo.

Ele ainda menciona que não é uma prioridade, mas essa recursão de cauda

will eventually get done.

N.B. Isso se aplica ao HotSpot e ao OpenJDK, outras VMs podem variar.

    
por 04.02.2015 / 14:35
fonte
22

O Java não tem otimização de chamada final pelo mesmo motivo que a maioria das linguagens imperativas não o tem. Os loops imperativos são o estilo preferido da linguagem, e o programador pode substituir a recursão da cauda por loops imperativos. A complexidade não vale a pena para um recurso cujo uso é desencorajado por uma questão de estilo.

Essa coisa em que os programadores às vezes escrevem em um estilo FP em linguagens imperativas só entrou em voga nos últimos 10 anos ou mais, depois que os computadores começaram a escalar em núcleos em vez de GHz. Mesmo agora, não é tão popular. Se eu sugerisse substituir um laço imperativo com recursão de cauda no trabalho, metade dos revisores de código riria e a outra metade daria uma olhada confusa. Mesmo em programação funcional, você geralmente evita a recursão da cauda, a menos que outras construções, como as de alta ordem, não se encaixem perfeitamente.

    
por 04.02.2015 / 14:17
fonte
5

O Java não possui otimização de chamadas altas porque a JVM não possui um bytecode para chamadas finais (para algum ponteiro de função estaticamente desconhecido , por exemplo, um método em alguma vtable).

Parece que por razões sociais (e talvez técnicas), adicionar uma nova operação de bytecode na JVM (o que a tornaria incompatível com versões anteriores dessa JVM) é terrivelmente difícil para o proprietário da especificação da JVM.

Razões técnicas para não incluir um novo bytecode na especificação da JVM incluem o fato de que as implementações reais da JVM são peças de software terrivelmente complexas (por exemplo, devido às muitas otimizações JIT que ele está fazendo).

Chamadas de cauda para alguma função desconhecida requerem a substituição do quadro de pilha atual por um novo, e essa operação deve ficar na JVM (não é apenas uma questão de alterar o compilador de geração de bytecode).

    
por 04.02.2015 / 14:22
fonte
4

A menos que uma linguagem possua uma sintaxe especial para fazer uma chamada final (recursiva ou não) e um compilador irá reclamar quando uma chamada final for solicitada, mas não puder ser gerada, a chamada "opcional" ou otimização de recursão na cauda produzirá situações onde um trecho de código pode exigir menos de 100 bytes de pilha em uma máquina, mas mais de 100.000.000 bytes de pilha em outra. Tal diferente deve ser considerado qualitativo e não meramente quantitativo.

Espera-se que as máquinas possam ter tamanhos de pilha diferentes e, portanto, é sempre possível que o código funcione em uma máquina, mas que a pilha seja acionada em outra. Geralmente, no entanto, o código que funcionará em uma máquina, mesmo quando a pilha é artificialmente restrita, provavelmente funcionará em todas as máquinas com tamanhos de pilhas "normais". Se, no entanto, um método que recorre a 1.000.000 de profundidade for otimizado em uma máquina, mas não em outra, a execução na máquina anterior provavelmente funcionará mesmo que sua pilha seja excepcionalmente pequena e falhe na última, mesmo que sua pilha seja incomumente grande .

    
por 04.02.2015 / 23:03
fonte
1

Eu acho que a recursão de chamada de cauda não é usada em Java principalmente porque isso alteraria os rastreamentos de pilha e, portanto, dificultaria muito a depuração de um programa. Acho que um dos principais objetivos do Java é permitir que os programadores depurem facilmente seu código, e o rastreamento de pilha é essencial para isso, especialmente em um ambiente de programação altamente orientado a objetos. Como a iteração poderia ser usada, o comitê de idiomas deve ter percebido que não vale a pena adicionar recursão de cauda.

    
por 07.06.2017 / 15:43
fonte