Por que o .NET / C # não otimiza a recursion de chamadas?

Eu encontrei esta pergunta sobre quais idiomas otimizar a recursion da cauda. Por que o C # não otimiza a recursion da cauda, ​​sempre que possível?

Para um caso concreto, por que esse método não é otimizado em um loop ( Visual Studio 2008 de 32 bits, se isso for importante) ?:

private static void Foo(int i) { if (i == 1000000) return; if (i % 100 == 0) Console.WriteLine(i); Foo(i+1); } 

    A compilation JIT é um equilíbrio difícil entre não gastar muito tempo fazendo a fase de compilation (diminuindo assim consideravelmente os aplicativos de curta duração) versus não fazer análises suficientes para manter a aplicação competitiva a longo prazo com uma compilation padronizada antes do tempo .

    Curiosamente, as etapas de compilation do NGen não são direcionadas para serem mais agressivas em suas otimizações. Eu suspeito que isso é porque eles simplesmente não querem ter bugs onde o comportamento é dependente de se o JIT ou NGen foi responsável pelo código da máquina.

    O CLR em si suporta a otimização da chamada final, mas o compilador específico da linguagem deve saber como gerar o opcode relevante e o JIT deve estar disposto a respeitá-lo. O fsc do F # irá gerar os opcodes relevantes (embora, para uma recursion simples, ele possa converter a coisa toda em um loop while diretamente). Csc do c # não.

    Veja esta postagem do blog para alguns detalhes (possivelmente agora desatualizados, dadas as alterações recentes do JIT). Note que o CLR muda para o 4.0 x86, x64 e ia64 irá respeitá-lo .

    Esse envio de comentários do Microsoft Connect deve responder à sua pergunta. Ele contém uma resposta oficial da Microsoft, então eu recomendo ir com isso.

    Obrigado pela sugestão. Nós consideramos a emissão de instruções de chamada de cauda em um número de pontos no desenvolvimento do compilador C #. No entanto, existem algumas questões sutis que nos levaram a evitar isso até agora: 1) Na verdade, existe um custo geral não trivial para o uso da instrução .tail no CLR (não é apenas uma instrução de salto, pois as chamadas finais se tornam em muitos ambientes menos rigorosos, como ambientes de tempo de execução de linguagem funcional em que as chamadas finais são altamente otimizadas). 2) Existem poucos methods C # reais em que seria legal emitir chamadas finais (outras linguagens encorajam padrões de codificação que têm mais recursion de cauda, ​​e muitos que dependem fortemente de otimização de chamada de cauda fazem uma reescrita global (como Transformações Continuação de Passagem) ) para aumentar a quantidade de recursion da cauda). 3) Em parte por causa de 2), os casos em que os methods C # acumulam estouro devido à recursion profunda que deveria ter sido bem-sucedida são bastante raros.

    Tudo o que disse, continuamos a olhar para isso, e podemos em uma versão futura do compilador encontrar alguns padrões onde faz sentido emitir instruções .tail.

    A propósito, como foi apontado, vale a pena notar que a recursion de cauda é otimizada em x64.

    C # não otimiza para recursion de chamada de cauda porque é para isso que F # é!

    Para saber mais sobre as condições que impedem o compilador C # de executar otimizações de chamada de ponta, consulte este artigo: Condições de chamada de retorno do JIT CLR .

    Interoperabilidade entre C # e F #

    C # e F # interoperam muito bem, e como o CLR (Common Language Runtime) do .NET é projetado com essa interoperabilidade em mente, cada linguagem é projetada com otimizações que são específicas para sua intenção e finalidades. Para um exemplo que mostra como é fácil chamar o código F # do código C #, consulte Chamando código F # a partir do código C # ; Para obter um exemplo de chamar funções C # do código F #, consulte Chamando funções C # de F # .

    Para interoperabilidade delegada, consulte este artigo: Delegate interoperabilidade entre F #, C # e Visual Basic .

    Diferenças teórico-práticas entre C # e F #

    Aqui está um artigo que aborda algumas das diferenças e explica as diferenças de design da recursion de chamada de ponta entre C # e F #: Gerando código de chamada de cauda em C # e F # .

    Aqui está um artigo com alguns exemplos em C #, F # e C ++ \ CLI: Recursão de Cauda em Recursão em C #, F # e C ++ \ CLI

    A principal diferença teórica é que o C # é projetado com loops, enquanto o F # é projetado com base nos princípios do cálculo Lambda. Para um livro muito bom sobre os princípios do cálculo Lambda, veja este livro grátis: Estrutura e Interpretação de Programas de Computador, de Abelson, Sussman e Sussman .

    Para um artigo introdutório muito bom sobre chamadas finais em F #, consulte este artigo: Introdução detalhada a chamadas finais em F # . Finalmente, aqui está um artigo que aborda a diferença entre a recursion não-final e a recursion da cauda (em F #): Recursão da cauda versus recursion não-cauda em F afiada .

    Fui informado recentemente que o compilador C # de 64 bits otimiza a recursion da cauda.

    C # também implementa isso. A razão pela qual nem sempre é aplicada, é que as regras usadas para aplicar a recursion da cauda são muito rígidas.

    Você pode usar a técnica de trampolim para funções recursivas de cauda em C # (ou Java). No entanto, a melhor solução (se você simplesmente se preocupa com a utilização da pilha) é usar esse pequeno método auxiliar para agrupar partes da mesma function recursiva e torná-la iterativa, mantendo a function legível.