TCO (Tail Call Optimization) - Ruby

Recentemente escrevi um artigo sobre Recursão em Ruby e algumas pessoas me pediram para complementar o artigo falando sobre TCO (Tail Call Optimization). Como é um assunto interessante, achei melhor escrever este novo artigo complementar sobre o assunto.

Contextualizando

Quando implementamos recursão para por exemplo, calcular o fatorial de um número:

def factorial(number)
  number == 1 ? 1 : number * factorial(number - 1)
end

Se passarmos como parâmetro um número muito grande, por exemplo 11.000, provavelmente teremos um problema de estouro de pilha.

factorial(11_000)
irb(main):012:0> factorial(11_000)
Traceback (most recent call last):
       16: from (irb):5:in `factorial'
       15: from (irb):5:in `factorial'
       14: from (irb):5:in `factorial'
       13: from (irb):5:in `factorial'
       12: from (irb):5:in `factorial'
       11: from (irb):5:in `factorial'
       10: from (irb):5:in `factorial'
        9: from (irb):5:in `factorial'
        8: from (irb):5:in `factorial'
        7: from (irb):5:in `factorial'
        6: from (irb):5:in `factorial'
        5: from (irb):5:in `factorial'
        4: from (irb):5:in `factorial'
        3: from (irb):5:in `factorial'
        2: from (irb):5:in `factorial'
        1: from (irb):5:in `factorial'
SystemStackError (stack level too deep)

Então para evitar problemas e gargalos no processamento o erro SystemStackError (stack level too deep) é disparado antes mesmo de executar método recursivamente.

Lembrando que Stack significa pilha, e uma pilha é uma estrutura de dados, em que assim como uma pilha de pratos por exemplo, o ultimo a entrar será o primeiro a sair (LIFO - Last In First Out).

Como podemos resolver este problema?

Para resolver este problema e conseguirmos executar o método de forma recursiva podemos usar como estratégia o TCO (Tail Call Optimization).

O que é TCO (Tail Call Optimization)?

TCO é uma estratégia utilizada para otimizar a execução de pilhas de chamadas e prevenir do estouro de pilha ao usar a recursão.

A estratégia consiste em transformar as pilhas de chamadas dos métodos tail-recursive em loops, o que evita a sobrecarga de chamadas de função recursivas. Ou seja, a pilha deixa de "existir" e passa ser uma sobrescrita das chamadas.

O que é uma pilha de chamada?

Uma pilha de chamadas é onde será armazenada as informações sobre as chamadas recursivas do método. Ou seja, para cada chamada método de forma recursiva será adicionado uma nova chamada à pilha de chamadas.

Então quando o número de itens na pilha de chamadas ultrapassa o tamanho permitido, ocorre estouro de pilha.

E como funciona o TCO (Tail Call Optimization)?

Para que seja possível utilizar essa estratégia é necessário 2 passos:

1 - O método recursivo precisa ser criado ou modificado para ser um método tail-recursive

Em nosso exemplo, precisaremos motificar o método e a forma como é feito cálculo, e assim, transformá-lo em tail-recursive, ficando da seguinte forma:

def factorial(number, accumulator=1)
  return accumulator if number <= 1

  factorial(number - 1, accumulator * number)
end

O que mudou?

1. Foi adicionado mais 1 argumento na assinatura do método para servir como acumulador do resultado;
2. O acumulador será inicializado igual a 1 para garantir que na segunda vez que o método for chamado, seu valor seja o mesmo passado para number inicialmente;
3. O acumulador (ou seja, o resultado) será retornado quando o number for igual ou menor a 1;
4. Fazendo essas mudanças garantimos que a última chamada será o próprio método sem depender de outro fator ou variável;
5. E assim garantimos que tail (calda, ultima chamada) seja o próprio método (acredito que seja esse o significado do nome Tail Call Optimization) e aconteça a sobrescrita das chamadas ;

2 - O Tail Call Optimization precisa estar habilitado no Ruby

Por padrão, o tail call optimization não é habilitado no Ruby. Então para que o método tail-recursive funcione corretamente precisamos habilitar (caso não seja habilitado o erro SystemStackError (stack level too deep) continuará acontecendo).

Para habilitar o TCO no ruby

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

Agora sim o método factorial(11_000) será executado com sucesso.

Para facilitar segue todo o código:

def factorial(number, accumulator=1)
  return accumulator if number <= 1

  factorial(number - 1, accumulator * number)
end

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

factorial(11_000)

Conclusão

O uso de Tail Call Optimization é uma estratégia que não iremos usar no dia a dia, mas é importante conhecer para caso precisar.

Referências:

• https://nithinbekal.com/posts/ruby-tco/
• https://reinteractive.com/posts/214-tail-call-optimisation-in-ruby-mri
• https://ruby-doc.org/core-3.1.0/RubyVM/InstructionSequence.html#method-c-compile_option
• https://ruby-doc.org/core-3.1.0/SystemStackError.html
• https://riptutorial.com/ruby/example/30381/tail-recursion
• https://www.youtube.com/watch?v=6Tblgvvit4E
• https://harfangk.github.io/2017/01/01/how-to-enable-tail-call-recursion-in-ruby.html
• https://stackoverflow.com/questions/824562/does-ruby-perform-tail-call-optimization
• https://dev.to/edisonywh/recursion-tail-call-optimization-and-recursion-2enh