Ruby executa otimização de chamada de cauda?

Linguagens funcionais levam ao uso de recursão para resolver muitos problemas e, portanto, muitas delas realizam Tail Call Optimization (TCO). O TCO faz com que chamadas para uma função de outra função (ou de si mesmo; nesse caso, esse recurso também é conhecido como Eliminação de Recursão de Cauda, ​​que é um subconjunto de TCO), como a última etapa dessa função, para não precisar de um novo quadro de pilha, o que diminui a sobrecarga e o uso de memória.

Ruby obviamente "pegou emprestado" uma série de conceitos de linguagens funcionais (lambdas, funções como map e assim por diante, etc.), o que me deixa curioso: Ruby executa otimização de chamada de cauda?

Não, Ruby não executa TCO. No entanto, ele também não executa o TCO.

A especificação da linguagem Ruby não diz nada sobre o TCO. Não diz que você precisa fazer isso, mas também não diz que você não pode fazer isso. Você simplesmente não pode confiar nisso.

Isso é diferente de Scheme, onde a especificação da linguagem requer que todas as implementações devem realizar TCO. Mas também é diferente do Python, onde Guido van Rossum deixou muito claro em várias ocasiões (a última vez apenas alguns dias atrás) que as implementações do Python não deveriam realizar o TCO.

Yukihiro Matsumoto simpatiza com o TCO, mas não quer forçar todas as implementações a apoiá-lo. Infelizmente, isso significa que você não pode confiar no TCO ou, se o fizer, seu código não será mais portável para outras implementações Ruby.

Portanto, algumas implementações Ruby executam o TCO, mas a maioria não. YARV, por exemplo, suporta TCO, embora (no momento) você tenha que descomentar explicitamente uma linha no código-fonte e recompilar a VM, para ativar o TCO - em versões futuras ele estará ativado por padrão, após a implementação provar estábulo. A Parrot Virtual Machine suporta TCO nativamente, portanto, Cardinal poderia facilmente suportá-lo também. O CLR tem algum suporte para TCO, o que significa que IronRuby e Ruby.NET provavelmente poderiam fazer isso. Rubinius provavelmente poderia fazer isso também.

Mas JRuby e XRuby não suportam TCO, e provavelmente não irão, a menos que a própria JVM ganhe suporte para TCO. O problema é este: se você deseja ter uma implementação rápida e uma integração rápida e contínua com o Java, então você deve ser compatível com a pilha do Java e usar a pilha da JVM tanto quanto possível. Você pode implementar facilmente o TCO com trampolins ou estilo de passagem de continuação explícita, mas então você não está mais usando a pilha JVM, o que significa que toda vez que você quiser chamar em Java ou chamar de Java em Ruby, você terá que realizar algum tipo de conversão, que é lenta. Então, XRuby e JRuby escolheram ir com velocidade e integração Java em vez de TCO e continuações (que basicamente têm o mesmo problema).

Isso se aplica a todas as implementações de Ruby que desejam se integrar perfeitamente a alguma plataforma host que não suporta TCO nativamente. Por exemplo, acho que MacRuby vai ter o mesmo problema.

Atualização: Esta é uma boa explicação do TCO em Ruby: http://nithinbekal.com/posts/ruby-tco/

Atualização: você também pode verificar a gem tco_method : http://blog.tdg5.com/introducing-the-tco_method-gem/

No Ruby MRI (1.9, 2.0 e 2.1), você pode ativar o TCO com:

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

Houve uma proposta para ativar o TCO por padrão no Ruby 2.0. Ele também explica alguns problemas que vêm com isso: Otimização da chamada final: habilitar por padrão ?.

Trecho curto do link:

Geralmente, a otimização de recursão de cauda inclui outra técnica de otimização - tradução "chamada" para "pular". Na minha opinião, é difícil aplicar essa otimização porque reconhecer "recursão" é difícil no mundo de Ruby.

Próximo exemplo. a invocação do método fact () na cláusula "else" não é uma "chamada final".

def fact(n) 
  if n < 2
    1 
 else
   n * fact(n-1) 
 end 
end

Se você deseja usar a otimização de chamada final no método fact (), é necessário alterar o método fact () da seguinte maneira (estilo de passagem de continuação).

def fact(n, r) 
  if n < 2 
    r
  else
    fact(n-1, n*r)
  end
end

Pode ter, mas não é garantido:

https://bugs.ruby-lang.org/issues/1256

O TCO também pode ser compilado ajustando algumas variáveis ​​em vm_opts.h antes de compilar: https://github.com/ruby/ruby/blob/trunk/vm_opts.h#L21

// vm_opts.h
#define OPT_TRACE_INSTRUCTION        0    // default 1
#define OPT_TAILCALL_OPTIMIZATION    1    // default 0

Isso se baseia nas respostas de Jörg e Ernest. Basicamente, depende da implementação.

Não consegui fazer a resposta de Ernest funcionar na ressonância magnética, mas é possível. Encontrei este exemplo que funciona para MRI 1.9 a 2.1. Isso deve imprimir um número muito grande. Se você não definir a opção TCO como true, deverá obter o erro "stack too deep".

source = <<-SOURCE
def fact n, acc = 1
  if n.zero?
    acc
  else
    fact n - 1, acc * n
  end
end

fact 10000
SOURCE

i_seq = RubyVM::InstructionSequence.new source, nil, nil, nil,
  tailcall_optimization: true, trace_instruction: false

#puts i_seq.disasm

begin
  value = i_seq.eval

  p value
rescue SystemStackError => e
  p e
end