Quando não há TCO, quando se preocupar em explodir a pilha?

14

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?

Cedric Martin
fonte
4
se você tem recursividade profundo o suficiente para explodir a pilha sem TCO então você vai ter um problema mesmo com TCO
catraca aberração
18
@ratchet_freak Isso é um absurdo. O Scheme nem sequer possui loops, mas, como a especificação exige suporte ao TCO, a iteração recursiva sobre um grande conjunto de dados não é mais cara que um loop imperativo (com o bônus de que a construção do Scheme retorna um valor).
precisa saber é o seguinte
6
@ratchetfreak O TCO é um mecanismo para tornar as funções recursivas escritas de uma certa maneira (isto é, recursivamente na cauda) ser completamente incapaz de explodir a pilha, mesmo que quisessem. Sua declaração faz sentido apenas para recursões que não são escritas de forma recursiva; nesse caso, você está correto e o TCO não irá ajudá-lo.
Evicatos
2
Última vez que olhei, o 80x86 também não otimiza a chamada de chamada (nativa). Mas isso não impediu que os desenvolvedores de idiomas portassem idiomas que o utilizam. O compilador identifica quando pode usar um salto versus um jsr e todos estão felizes. Você pode fazer o mesmo em uma JVM.
Kdgregory
3
@ kdgregory: Mas o x86 tem GOTO, a JVM não. E o x86 não é usado como uma plataforma de interoperabilidade. A JVM não possui GOTOe 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 como GOTOalgo 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.
Jörg W Mittag

Respostas:

16

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

int factorial(int i){ return factorial(i, 1);}
int factorial(int i, int accum){
  if(i == 0) return accum;
  return factorial(i-1, accum * i);
}

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 recurforma, 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 recurformulá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

return foo(bar, baz); // foo is just a simple method

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.

Daniel Gratzer
fonte
2
O maior problema é o verificador de código de bytes, que é completamente baseado na inspeção de pilha. Esse é um erro grave na especificação da JVM. Há 25 anos, quando a JVM foi projetada, as pessoas já disseram que seria melhor ter a linguagem de código de bytes da JVM segura em primeiro lugar, em vez de deixá-la insegura e depois confiar na verificação do código de bytes após o fato. No entanto, Matthias Felleisen (uma das figuras principais da comunidade Scheme) escreveu um documento demonstrando como as chamadas finais podem ser adicionadas à JVM, preservando o verificador de código de bytes.
Jörg W Mittag
2
Curiosamente, o J9 JVM pela IBM que executam TCO.
Jörg W Mittag
1
@jozefg Curiosamente, ninguém se importa com entradas de stacktrace para loops, portanto, o argumento stacktrace não retém água, pelo menos para funções recursivas de cauda.
Ingo
2
@MasonWheeler Esse é exatamente o meu ponto: o stacktrace não informa em qual iteração aconteceu. Você pode ver isso apenas indiretamente, inspecionando variáveis ​​de loop, etc. Então, por que você deseja várias entradas de rastreamento de pilha hundert de uma função recursiva de cauda? Apenas o último é interessante! E, como com loops, você pode determinar qual recursão era inspecionando varaibles locais, valores de argumento, etc.
Ingo
3
@ Ingo: Se uma função apenas se repetir, o rastreamento da pilha pode não mostrar muito. Se, no entanto, um grupo de funções for mutuamente recursivo, um rastreamento de pilha às vezes pode mostrar bastante.
Supercat
7

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:

  1. A recursão simples da cauda pode ser otimizada para um loop pelo compilador.
  2. Se o programa estiver no estilo de passagem contínua, é trivial usar o "trampolim". Aqui, uma função não retorna o resultado final, mas uma continuação que é então executada do lado de fora. Essa técnica permite que um gravador de compilador modele o fluxo de controle arbitrariamente complexo.

Isso pode precisar de um exemplo maior. Considere um idioma com encerramentos (por exemplo, JavaScript ou similar). Podemos escrever o fatorial como

def fac(n, acc = 1) = if (n <= 1) acc else n * fac(n-1, acc*n)

print fac(x)

Agora podemos fazer com que ele retorne um retorno de chamada:

def fac(n, acc = 1) =
  if (n <= 1) acc
  else        (() => fac(n-1, acc*n))  // this isn't full CPS, but you get the idea…

var continuation = (() => fac(x))
while (continuation instanceof function) {
  continuation = continuation()
}
var result = continuation
print result

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.

amon
fonte
1
"À medida que o TCO reutiliza uma parte da pilha, um rastreamento de pilha de uma exceção fica incompleto" - sim, mas um rastreamento de pilha de um loop também está incompleto - ele não registra com que freqüência o loop foi executado. - Infelizmente, mesmo que a JVM ofereça suporte a chamadas de cauda adequadas, ainda é possível optar por não participar, durante a depuração, por exemplo. E, em seguida, para produção, habilite o TCO para garantir que o código seja executado com 100.000 ou 100.000.000 de chamadas finais.
Ingo
1
@ No. Ingo (1) Quando os loops não são implementados como recursão, não há justificativa para que eles apareçam na pilha (chamada de cauda, ​​salto, chamada). (2) O TCO é mais geral do que a otimização da recursão da cauda. Minha resposta usa a recursão como exemplo . (3) Se você estiver programando em um estilo que depende do TCO, desativar essa otimização não é uma opção - o TCO completo ou rastreamentos completos de pilha são um recurso de linguagem ou não. Por exemplo, o Scheme consegue equilibrar as desvantagens do TCO com um sistema de exceção mais avançado.
amon
1
(1) concordo plenamente. Mas pelo mesmo raciocínio, não há lógica para manter centenas e milhares de entradas de rastreamento de pilha que todas apontam return foo(....);no método foo(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.
Ingo
(3) Discordo. Não vejo razão para que seja impossível depurar meu código com um problema de tamanho N, para alguns N pequenos o suficiente para escapar da pilha normal. E então, para ativar e desativar o TCO - eliminando efetivamente a restrição no tamanho do probem.
Ingo
@Ingo “Discordo. Não vejo razão para que seja impossível depurar meu código com um problema de tamanho N, para alguns N pequenos o suficiente para se livrar da pilha normal. ”Se o TCO / TCE for uma transformação de CPS, altere-o off excederá a pilha e travará o programa, portanto, nenhuma depuração seria possível. O Google se recusou a implementar o TCO no V8 JS, devido a esse problema que ocorreu incidentalmente . Eles desejam uma sintaxe especial para que o programador possa declarar que realmente deseja o TCO e a perda do rastreamento da pilha. Alguém sabe se as exceções também são danificadas pelo TCO?
Shelby Moore III
6

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, GOTOmas 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 GOTOtrampolins 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.

Jörg W Mittag
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.)
Mason Wheeler
1
"Adicionar dois números é adicionar dois números." Exceto por idiomas onde não está. E a operação + no Lisp / Scheme, em que um único operador aritmético pode receber um número arbitrário de argumentos? (+ 1 2 3) A única maneira sensata de implementar isso é como uma função.
Evicatos
1
@Mason Wheeler: O que você quer dizer com inversão de abstração?
Giorgio
1
@MasonWheeler Essa é, sem dúvida, a entrada da Wikipedia mais ondulada sobre um assunto técnico que eu já vi. Eu vi algumas entradas duvidosas, mas isso é apenas ... uau.
Evicatos
1
@MasonWheeler: Você está falando sobre as funções de tamanho da lista nas páginas 22 e 23 do On Lisp? A versão de chamada final é cerca de 1,2x mais complicada, nem perto de 3x. Também não estou claro o que você quer dizer com inversão de abstração.
Michael Shaw
4

"A JVM não suporta otimização de chamada de cauda, ​​portanto, prevejo muitas pilhas explosivas"

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 ):

Na ciência da computação, uma chamada de cauda é uma chamada de sub-rotina que acontece dentro de outro procedimento como sua ação final; pode produzir um valor de retorno que é retornado imediatamente pelo procedimento de chamada

No código abaixo, a chamada para bar()é a chamada final de foo():

private void foo() {
    // do something
    bar()
}

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.

public static int fact(int n) {
    if (n <= 1) return 1;
    else return n * fact(n - 1);
}

Para implementar a otimização da chamada de cauda, ​​você precisa de duas coisas:

  • Uma plataforma que suporta ramificação, além de chamadas de subtrotina.
  • Um analisador estático que pode determinar se a otimização da chamada de cauda é possível.

É 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:

def sum(acc:Int, list:List[Int]) : Int = {
  if (list.isEmpty) acc
  else sum(acc + list.head, list.tail)
}

Essa função se transforma no seguinte código de código:

public int sum(int, scala.collection.immutable.List);
  Code:
   0:   aload_2
   1:   invokevirtual   #63; //Method scala/collection/immutable/List.isEmpty:()Z
   4:   ifeq    9
   7:   iload_1
   8:   ireturn
   9:   iload_1
   10:  aload_2
   11:  invokevirtual   #67; //Method scala/collection/immutable/List.head:()Ljava/lang/Object;
   14:  invokestatic    #73; //Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
   17:  iadd
   18:  aload_2
   19:  invokevirtual   #76; //Method scala/collection/immutable/List.tail:()Ljava/lang/Object;
   22:  checkcast   #59; //class scala/collection/immutable/List
   25:  astore_2
   26:  istore_1
   27:  goto    0

Observe o goto 0no final. Por comparação, uma função Java equivalente (que deve usar um Iteratorpara 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.

public static int sum(int, java.util.Iterator);
  Code:
   0:   aload_1
   1:   invokeinterface #64,  1; //InterfaceMethod java/util/Iterator.hasNext:()Z
   6:   ifne    11
   9:   iload_0
   10:  ireturn
   11:  iload_0
   12:  aload_1
   13:  invokeinterface #70,  1; //InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
   18:  checkcast   #25; //class java/lang/Integer
   21:  invokevirtual   #74; //Method java/lang/Integer.intValue:()I
   24:  iadd
   25:  aload_1
   26:  invokestatic    #43; //Method sum:(ILjava/util/Iterator;)I
   29:  ireturn

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 switchpara 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 como foldLeft(). 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 JSRpor JUMP.

kdgregory
fonte
Se existisse um código de operação de chamada de cauda, ​​por que a otimização de chamada de cauda exigiria outra coisa senão observar em cada local de chamada se o método que fez a chamada precisaria executar qualquer código posteriormente? Pode ser que, em alguns casos, uma instrução como return foo(123);possa ser melhor executada incorporando-a do fooque 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.
Supercat
@ supercat - Não tenho certeza qual é a sua pergunta. O primeiro ponto deste post é que o compilador não pode saber como será o quadro de pilha de todas as callees em potencial (lembre-se de que o quadro de pilha contém não apenas os argumentos da função, mas também suas variáveis ​​locais). Suponho que você poderia adicionar um código de operação que verifica os quadros compatíveis com o tempo de execução, mas isso me leva à segunda parte do post: qual é o valor real ?
Kdgregory