Quais limitações a JVM impõe à otimização de chamada de cauda

O Clojure não executa a otimização de chamada de cauda por si só: quando você tem uma função recursiva de cauda e deseja otimizá-la, deve usar o formulário especial recur. Da mesma forma, se você tiver duas funções recursivas mutuamente, poderá otimizá-las apenas usando trampoline.

O compilador Scala é capaz de executar o TCO para uma função recursiva, mas não para duas funções recursivas mutuamente.

Sempre que li sobre essas limitações, elas sempre foram atribuídas a alguma limitação intrínseca ao modelo da JVM. Não sei praticamente nada sobre compiladores, mas isso me deixa um pouco confuso. Deixe-me pegar o exemplo de Programming Scala. Aqui a função

def approximate(guess: Double): Double =
  if (isGoodEnough(guess)) guess
  else approximate(improve(guess))

é traduzido para

0: aload_0
1: astore_3
2: aload_0
3: dload_1
4: invokevirtual #24; //Method isGoodEnough:(D)Z
7: ifeq
10: dload_1
11: dreturn
12: aload_0
13: dload_1
14: invokevirtual #27; //Method improve:(D)D
17: dstore_1
18: goto 2

Então, no nível do bytecode, é preciso apenas goto. Nesse caso, de fato, o trabalho árduo é realizado pelo compilador.

Que facilidade da máquina virtual subjacente permitiria ao compilador lidar com o TCO mais facilmente?

Como uma observação lateral, eu não esperaria que as máquinas reais fossem muito mais inteligentes que a JVM. Ainda assim, muitos idiomas que são compilados com código nativo, como Haskell, parecem não ter problemas com a otimização de chamadas de cauda (bem, o Haskell pode ter algumas vezes devido à preguiça, mas esse é outro problema).

Agora, não sei muito sobre Clojure e pouco sobre Scala, mas vou tentar.

Primeiro, precisamos diferenciar entre chamadas de cauda e recursão de cauda. A recursão da cauda é realmente fácil de transformar em um loop. Com chamadas de cauda, ​​é muito mais difícil impossível no caso geral. Você precisa saber o que está sendo chamado, mas com polimorfismo e / ou funções de primeira classe, você raramente sabe disso; portanto, o compilador não pode saber como substituir a chamada. Somente em tempo de execução, você conhece o código de destino e pode pular para lá sem alocar outro quadro de pilha. Por exemplo, o fragmento a seguir possui uma chamada final e não precisa de espaço na pilha quando otimizado adequadamente (incluindo o TCO), mas não pode ser eliminado ao compilar para a JVM:

function forward(obj: Callable<int, int>, arg: int) =
    let arg1 <- arg + 1 in obj.call(arg1)

Embora seja apenas um pouco ineficiente aqui, existem estilos de programação completos (como o Continuation Passing Style ou CPS) que têm toneladas de chamadas finais e raramente retornam. Fazer isso sem o TCO completo significa que você só pode executar pequenos pedaços de código antes de ficar sem espaço na pilha.

Que facilidade da máquina virtual subjacente permitiria ao compilador lidar com o TCO mais facilmente?

Uma instrução de chamada de cauda, ​​como na Lua 5.1 VM. Seu exemplo não fica muito mais simples. O meu se torna algo assim:

push arg
push 1
add
load obj
tailcall Callable.call
// implicit return; stack frame was recycled

Como nota de rodapé, eu não esperaria que as máquinas reais fossem muito mais inteligentes que a JVM.

Você está certo, eles não estão. Na verdade, eles são menos inteligentes e, portanto, nem sabem muito sobre coisas como quadros de pilha. É exatamente por isso que se pode fazer truques como reutilizar o espaço da pilha e pular para o código sem pressionar um endereço de retorno.

O Clojure poderia executar a otimização automática da recursão da cauda em loops: certamente é possível fazer isso na JVM, como Scala prova.

Na verdade, foi uma decisão de design não fazer isso - você deve usar explicitamente o recurformulário especial se quiser esse recurso. Consulte o tópico Re: Por que nenhuma otimização de chamada de cauda no grupo do Google Clojure.

Na JVM atual, a única coisa que é impossível fazer é a otimização da chamada de cauda entre diferentes funções (recursão mútua). Isso não é particularmente complexo de implementar (outras linguagens como o Scheme possuem esse recurso desde o início), mas exigiria alterações nas especificações da JVM. Por exemplo, você precisaria alterar as regras sobre a preservação da pilha completa de chamadas de funções.

É provável que uma iteração futura da JVM obtenha esse recurso, embora provavelmente seja uma opção para manter o comportamento compatível com versões anteriores do código antigo. Digamos, a Visualização de Recursos no Geeknizer lista isso para Java 9:

Adicionando chamadas finais e continuações ...

^{Obviamente, os futuros roteiros estão sempre sujeitos a alterações.}

Como se vê, não é tão grande coisa de qualquer maneira. Em mais de dois anos de codificação de Clojure, nunca encontrei uma situação em que a falta de TCO fosse um problema. As principais razões para isso são:

• Você já pode obter recursão rápida da cauda em 99% dos casos comuns com recurou um loop. O caso de recursão de cauda mútua é bastante raro no código normal
• Mesmo quando você precisa de recursão mútua, geralmente a profundidade da recursão é superficial o suficiente para que você possa fazê-lo na pilha de qualquer maneira sem o TCO. Afinal, o TCO é apenas uma "otimização" ....
• Nos casos muito raros em que você precisa de alguma forma de recursão mútua que não consuma pilha, há muitas outras alternativas que podem alcançar o mesmo objetivo: sequências preguiçosas, trampolins etc.

Como nota de rodapé, eu não esperaria que as máquinas reais fossem muito mais inteligentes que a JVM.

Não se trata de ser mais inteligente, mas de ser diferente. Até recentemente, a JVM era projetada e otimizada exclusivamente para uma única linguagem (Java, obviamente), que possui modelos de memória e chamada muito rígidos.

Não apenas não havia gotoponteiros nem ponteiros, nem havia maneira de chamar uma função 'vazia' (que não era um método definido dentro de uma classe).

Conceitualmente, ao direcionar a JVM, um gravador de compilador deve perguntar "como posso expressar esse conceito em termos de Java?". E, obviamente, não há como expressar o TCO em Java.

Observe que eles não são vistos como falhas da JVM, porque não são necessários para Java. Assim que o Java precisou de algum recurso como esse, ele foi adicionado à JVM.

Recentemente, as autoridades Java começaram a levar a sério a JVM como uma plataforma para linguagens não Java, portanto, já conquistaram algum suporte para recursos que não possuem Java equivalente. O mais conhecido é a digitação dinâmica, que já está na JVM, mas não em Java.

Então, no nível do bytecode, é preciso apenas ir. Nesse caso, de fato, o trabalho árduo é realizado pelo compilador.

Você notou que o endereço do método começa com 0? Que todos os métodos de configuração começam com 0? A JVM não permite saltar para fora de um método.

Eu não tenho ideia do que aconteceria com um ramo com deslocamento fora do método, carregado por java - talvez fosse capturado pelo verificador de bytecode, talvez gerasse uma exceção e, na verdade, saltaria para fora do método.

O problema, é claro, é que você não pode realmente garantir onde outros métodos da mesma classe estarão, muito menos métodos de outras classes. Duvido que a JVM garanta alguma garantia sobre onde os métodos serão carregados, embora eu esteja feliz em ser corrigido.