Sempre que há uma discussão sobre uma nova linguagem de programação direcionada à JVM, inevitavelmente há pessoas dizendo coisas como:
"A JVM não suporta otimização de chamada de cauda, portanto, prevejo muitas pilhas explosivas"
Existem milhares de variações sobre esse tema.
Agora eu sei que alguma linguagem, como o Clojure, por exemplo, tem uma construção recorrente especial que você pode usar.
O que não entendo é: qual é a gravidade da falta de otimização de chamada de cauda? Quando devo me preocupar com isso?
Minha principal fonte de confusão provavelmente vem do fato de que o Java é uma das linguagens mais bem-sucedidas de todos os tempos e algumas das linguagens da JVM parecem estar indo muito bem. Como isso é possível se a falta de TCO é realmente de qualquer preocupação?
fonte
GOTO
, a JVM não. E o x86 não é usado como uma plataforma de interoperabilidade. A JVM não possuiGOTO
e um dos principais motivos para a escolha da plataforma Java é a interoperabilidade. Se você deseja implementar o TCO na JVM, precisa fazer algo na pilha. Gerencie você mesmo (ou seja, não use a pilha de chamadas da JVM), use trampolins, use exceções comoGOTO
algo assim. Em todos esses casos, você se torna incompatível com a pilha de chamadas da JVM. É impossível ser compatível com a pilha com Java, ter TCO e alto desempenho. Você tem que sacrificar um desses três.Respostas:
Considere isso, digamos que nos livramos de todos os loops em Java (os escritores do compilador estão em greve ou algo assim). Agora queremos escrever fatorial, para que possamos corrigir algo assim
Agora estamos nos sentindo bem espertos, conseguimos escrever nosso fatorial mesmo sem loops! Porém, quando testamos, notamos que, com qualquer número de tamanho razoável, estamos recebendo erros de fluxo de pilha, pois não há TCO.
Em Java real, isso não é um problema. Se algum dia tivermos um algoritmo recursivo de cauda, podemos transformá-lo em um loop e ficar bem. No entanto, e os idiomas sem loops? Então você está apenas de mangueira. É por isso que o clojure tem essa
recur
forma, sem ela, nem está completa (não há como fazer loops infinitos).A classe de linguagens funcionais direcionadas à JVM, Frege, Kawa (Scheme) e Clojure está sempre tentando lidar com a falta de chamadas de cauda, porque nessas linguagens, o TC é a maneira idiomática de fazer loops! Se traduzido para Scheme, esse fatorial acima seria um bom fatorial. Seria muito inconveniente se o loop de 5000 vezes causasse uma falha no programa. Isso pode ser contornado, porém, com
recur
formulários especiais, anotações sugerindo a otimização de auto chamadas, trampolins, o que for. Mas todos impõem resultados de desempenho ou trabalho desnecessário ao programador.Agora, o Java também não sai de graça, já que há mais no TCO do que apenas recursão, e as funções recursivas mutuamente? Eles não podem ser traduzidos diretamente para loops, mas ainda não são otimizados pela JVM. Isso torna espetacularmente desagradável tentar escrever algoritmos usando recursão mútua usando Java, pois se você deseja desempenho / intervalo decentes, precisa fazer magia negra para ajustá-lo aos loops.
Portanto, em resumo, isso não é um grande negócio para muitos casos. A maioria das chamadas de cauda processa apenas um stackframe de profundidade, com coisas como
ou é recursão. No entanto, para a classe de CT que não se encaixa nisso, toda linguagem da JVM sente a dor.
No entanto, há uma razão decente para que ainda não tenhamos TCO. A JVM nos fornece rastreamentos de pilha. Com o TCO, eliminamos sistematicamente os quadros de pilha que sabemos que estão "condenados", mas a JVM pode realmente desejá-los posteriormente para um rastreamento de pilha! Digamos que implementemos um FSM como este, em que cada estado chama o seguinte. Apagaríamos todos os registros dos estados anteriores para que um retorno nos mostrasse qual estado, mas nada sobre como chegamos lá.
Além disso, e mais premente, grande parte da verificação de bytecode é baseada em pilha, eliminando o que nos permite verificar que o bytecode não é uma perspectiva agradável. Entre isso e o fato de o Java ter loops, o TCO parece um pouco mais problemático do que vale para os engenheiros da JVM.
fonte
As otimizações de chamadas de cauda são importantes principalmente por causa da recursão da cauda. No entanto, há um argumento sobre por que é realmente bom que a JVM não otimize chamadas de cauda: Como o TCO reutiliza uma parte da pilha, um rastreamento de pilha de uma exceção fica incompleto, dificultando um pouco a depuração.
Existem maneiras de contornar as limitações da JVM:
Isso pode precisar de um exemplo maior. Considere um idioma com encerramentos (por exemplo, JavaScript ou similar). Podemos escrever o fatorial como
Agora podemos fazer com que ele retorne um retorno de chamada:
Isso agora funciona em um espaço de pilha constante, o que é meio bobo porque, de qualquer maneira, é recursivo da cauda. No entanto, essa técnica é capaz de nivelar todas as chamadas finais no espaço de pilha constante. E se o programa estiver no CPS, isso significa que o callstack é constante no geral (no CPS, todas as chamadas são chamadas finais).
Uma grande desvantagem dessa técnica é que é muito mais difícil depurar, um pouco mais difícil de implementar e com menos desempenho - veja todos os fechamentos e indiretos que estou usando.
Por esses motivos, seria muito preferível que a VM implementasse uma linguagem de chamada de chamada final, como Java, que tenha boas razões para não oferecer suporte a chamadas de chamada não precisaria usá-la.
fonte
return foo(....);
no métodofoo
(2) concordam totalmente, é claro. Ainda assim, aceitamos rastreamento incompleto de loops, atribuições (!), Seqüências de instruções. Por exemplo, se você encontrar um valor inesperado em uma variável, certamente deseja saber como ele chegou lá. Mas você não reclama de traços ausentes nesse caso. Porque, de alguma forma, está gravado em nossos cérebros que: a) acontece apenas nas chamadas b) acontece em todas as chamadas. Ambos não fazem sentido, IMHO.Uma parcela significativa de chamadas em um programa são chamadas finais. Toda sub-rotina tem uma última chamada, portanto, toda sub-rotina tem pelo menos uma chamada de cauda. As chamadas de cauda têm as características de desempenho,
GOTO
mas a segurança de uma chamada de sub-rotina.Ter chamadas de cauda adequadas permite gravar programas que, de outra forma, não podem ser gravados. Tome, por exemplo, uma máquina de estado. Uma máquina de estado pode ser implementada diretamente, fazendo com que cada estado seja uma sub-rotina e cada transição de estado seja uma chamada de sub-rotina. Nesse caso, você faz a transição de estado para estado para estado, fazendo ligação após ligação após ligação, e na verdade nunca mais retorna! Sem chamadas de cauda apropriadas, você explodiria imediatamente a pilha.
Sem o PTC, você deve usar
GOTO
trampolins ou exceções como controle de fluxo ou algo parecido. É muito mais feio, e não tanto uma representação direta 1: 1 da máquina de estado.(Observe como evitei habilmente usar o exemplo chato de "loop". Este é um exemplo em que os PTCs são úteis mesmo em um idioma com loops.)
Eu deliberadamente usei o termo "Chamadas de cauda apropriadas" aqui em vez de TCO. O TCO é uma otimização de compilador. PTC é um recurso de linguagem que requer que todo compilador execute o TCO.
fonte
The vast majority of calls in a program are tail calls.
Não se "a grande maioria" dos métodos chamados realizar mais de uma chamada própria.Every subroutine has a last call, so every subroutine has at least one tail call.
Esta é trivialmente demonstrável como falsa:return a + b
. (A menos que você está em alguma linguagem insano onde operações aritméticas básicas são definidas como chamadas de função, é claro.)Qualquer pessoa que diga isso (1) não entende a otimização de chamada de cauda, ou (2) não entende a JVM, ou (3) ambos.
Vou começar com a definição de chamadas finais da Wikipedia (se você não gosta da Wikipedia, aqui está uma alternativa ):
No código abaixo, a chamada para
bar()
é a chamada final defoo()
:A otimização da chamada final ocorre quando a implementação do idioma, vendo uma chamada final, não usa a invocação normal do método (que cria um quadro de pilha), mas cria uma ramificação. Isso é uma otimização porque um quadro de pilha requer memória e requer ciclos de CPU para enviar informações (como o endereço de retorno) para o quadro e porque se supõe que o par de chamada / retorno requer mais ciclos de CPU do que um salto incondicional.
O TCO é frequentemente aplicado à recursão, mas esse não é seu único uso. Nem é aplicável a todas as recursões. O código recursivo simples para calcular um fatorial, por exemplo, não pode ser otimizado para chamada de cauda, porque a última coisa que acontece na função é uma operação de multiplicação.
Para implementar a otimização da chamada de cauda, você precisa de duas coisas:
É isso aí. Como já observei em outro lugar, a JVM (como qualquer outra arquitetura completa de Turing) tem um salto. Por acaso há um goto incondicional , mas a funcionalidade pode ser facilmente implementada usando uma ramificação condicional.
A parte da análise estática é o que é complicado. Dentro de uma única função, não há problema. Por exemplo, aqui está uma função Scala recursiva de cauda para somar os valores em um
List
:Essa função se transforma no seguinte código de código:
Observe o
goto 0
no final. Por comparação, uma função Java equivalente (que deve usar umIterator
para imitar o comportamento de quebrar uma lista do Scala em um cabeçalho e final) se transforma no seguinte bytecode. Note-se que as duas últimas operações são agora uma invocação , seguido por um retorno explícito do valor produzido por essa invocação recursiva.Otimização de chamada de cauda de uma única função é trivial: o compilador pode ver que não há nenhum código que utiliza o resultado da chamada, para que ele possa substituir a invocação com um
goto
.Onde a vida fica complicada é se você tiver vários métodos. As instruções de ramificação da JVM, ao contrário das de um processador de uso geral, como o 80x86, são limitadas a um único método. Ainda é relativamente simples se você tiver métodos particulares: o compilador é livre para incorporar esses métodos conforme apropriado, para otimizar as chamadas finais (se você está se perguntando como isso pode funcionar, considere um método comum que use a
switch
para controlar o comportamento). Você pode até estender essa técnica a vários métodos públicos da mesma classe: o compilador alinha os corpos do método, fornece métodos de ponte pública e as chamadas internas se transformam em saltos.Mas, esse modelo é quebrado quando você considera métodos públicos em diferentes classes, principalmente à luz de interfaces e carregadores de classes. O compilador no nível da fonte simplesmente não possui conhecimento suficiente para implementar otimizações de chamada de cauda. No entanto, diferentemente das implementações "bare-metal", a * JVM (possui as informações para fazer isso, na forma do compilador Hotspot (pelo menos, o ex-compilador Sun). Não sei se ele realmente executa otimizações de chamada de cauda, e suspeite que não, mas poderia .
O que me leva à segunda parte da sua pergunta, que vou reformular como "devemos nos importar?"
Claramente, se o seu idioma usa a recursão como único primitivo para a iteração, você se importa. Porém, linguagens que precisam desse recurso podem implementá-lo; o único problema é se um compilador para essa linguagem pode produzir uma classe que pode chamar e ser chamada por uma classe Java arbitrária.
Fora desse caso, vou convidar votos negativos dizendo que é irrelevante. A maior parte do código recursivo que eu vi (e trabalhei com muitos projetos de gráficos) não é otimizável por chamada de cauda . Como o fatorial simples, ele usa recursão para construir o estado, e a operação da cauda é uma combinação.
Para um código otimizável por chamada de cauda, geralmente é simples traduzir esse código em um formato iterável. Por exemplo, essa
sum()
função que mostrei anteriormente pode ser generalizada comofoldLeft()
. Se você olhar a fonte , verá que ela é realmente implementada como uma operação iterativa. Jörg W Mittag teve um exemplo de uma máquina de estado implementada por meio de chamadas de função; existem muitas implementações de máquinas de estado eficientes (e de manutenção) que não dependem de chamadas de função sendo convertidas em saltos.Vou terminar com algo completamente diferente. Se você pesquisar no Google a partir de notas de rodapé no SICP, poderá acabar aqui . Eu pessoalmente acho que um lugar muito mais interessante do que ter meu compilador substituir
JSR
porJUMP
.fonte
return foo(123);
possa ser melhor executada incorporando-a dofoo
que gerando código para manipular a pilha e executar um salto, mas não vejo por que a chamada de cauda seria diferente de uma chamada comum em a esse respeito.