Tail call optimization

Erlang, enquanto derivação funcional de Prolog, não possui loop reiterativo e resolve suas reiterações com recursão.

Porém as aplicações em Erlang são feitas para funcionar ininterruptamente por semanas ou anos, imagine então como ficaria a memória com o empilhamento de chamadas de função!

Para resolver isso, Erlang usa um recurso chamado tail call optimization.

Sempre que o fluxo de execução chega à última chamada da função (chamada last call ou tail call), antes da execução desta chamada, a função é removida da pilha de memória e a memória usada por ela já se torna candidata à coleta de lixo (garbage collection).

Vamos a um exemplo. Tomemos a implementação body recursive de fatorial:

fact(0) -> 1;
fact(N) when N > 0 -> N * fact(N-1).

Agora vamos executar: fact(5). – O que acontece?

• 5 casa com o guarda N > 0, então entramos na segunda assinatura da função fact/1.
• 5 é vinculado a N. A pilha contém fact(5) e N = 5.
• É identificada a chamada a erlang:'-'/2 passando os parâmetros 5 e 1.
• A chamada retorna 4, então é identificada a chamada a fact(4).
• 4 casa com o guarda N > 0, então entramos na segunda assinatura da função fact/1.
• 4 é vinculado a N. A pilha contém fact(5), N = 5, fact(4) e N = 4.
• É identificada a chamada a erlang:'-'/2 passando os parâmetros 4 e 1.
• A chamada retorna 3, então é identificada a chamada a fact(3).
• 3 casa com o guarda N > 0, então entramos na segunda assinatura da função fact/1.
• 3 é vinculado a N. A pilha contém fact(5), N = 5, fact(4), N = 4, fact(3) e N = 3.
• É identificada a chamada a erlang:'-'/2 passando os parâmetros 3 e 1.
• A chamada retorna 2, então é identificada a chamada a fact(2).
• 2 casa com o guarda N > 0, então entramos na segunda assinatura da função fact/1.
• 2 é vinculado a N. A pilha contém fact(5), N = 5, fact(4), N = 4, fact(3), N = 3, fact(2) e N = 2.
• É identificada a chamada a erlang:'-'/2 passando os parâmetros 2 e 1.
• A chamada retorna 1, então é identificada a chamada a fact(1).
• 1 casa com o guarda N > 0, então entramos na segunda assinatura da função fact/1.
• 1 é vinculado a N. A pilha contém fact(5), N = 5, fact(4), N = 4, fact(3), N = 3, fact(2), N = 2, fact(1) e N = 1.
• É identificada a chamada a erlang:'-'/2 passando os parâmetros 1 e 1.
• A chamada retorna 0, então é identificada a chamada a fact(0).
• 0 (zero) casa com a primeira assinatura da função, fact(0).
• A pilha contém fact(5), N = 5, fact(4), N = 4, fact(3), N = 3, fact(2), N = 2, fact(1), N = 1 e fact(0).^†
• fact(0) retorna 1 e é desempilhado.
• Na pilha de fact(1) é reconhecida a last call erlang:'*'/2 com os parâmetros 1 e 1, então fact(1) é desempilhado, assim como suas variáveis.
• Neste ponto tempos na pilhas: fact(5), N = 5, fact(4), N = 4, fact(3), N = 3, fact(2), N = 2 e 1*1.
• 1*1 retorna 1 e é desempilhado.
• Na pilha de fact(2) é reconhecida a last call erlang:'*'/2 com os parâmetros 2 e 1, então fact(2) é desempilhado, assim como suas variáveis.
• 2*1 retorna 2 e é desempilhado.
• Na pilha de fact(3) é reconhecida a last call erlang:'*'/2 com os parâmetros 3 e 2, então fact(3) é desempilhado, assim como suas variáveis.
• 3*2 retorna 6 e é desempilhado.
• Na pilha de fact(4) é reconhecida a last call erlang:'*'/2 com os parâmetros 4 e 6, então fact(4) é desempilhado, assim como suas variáveis.
• 4*6 retorna 24 e é desempilhado.
• Na pilha de fact(5) é reconhecida a last call erlang:'*'/2 com os parâmetros 5 e 24, então fact(4) é desempilhado, assim como suas variáveis.
• 5*24 retorna 120 e é desempilhado.

^†Agora repare como a pilha ficou sobrecarregada com poucas chamadas… imagine com fact(200)!

Essa foi uma implementação body recursive, que não aproveita as vantagens da tail call optimization. Vamos então a uma implementação tail recursive:

fact(N) when is_integer(N), N >= 0 -> fact(N, 1).

fact(0, Acc) -> Acc;
fact(N, Acc) -> fact(N-1, N*Acc).

[update 2013-07-30]
Acho de difícil leitura o uso da vírgula como operador de conjunção em guardas (coloquei no código apenas porque é o mais usado), então você também pode escrever a função fact/1 assim:

fact(N) when is_integer(N) andalso N >= 0 -> fact(N, 1).

É mais verborrágico, porém mais claro.
[/update]

A função fact/2 não possui guarda pois não será exportada, apenas é consumida por fact/1.

Chamando fact(5):

• 5 é inteiro e maior ou igual a 0, então pode ser tratado pela função fact/1.
• 5 é vinculado a N. Neste ponto temos na filha fact(5) e N = 5.
• É identificada a last call fact/2 com os parâmetros 5 e 1, então fact(5) é desempilhada, assim como suas variáveis.
• 5 é diferente de 0, então caímos na segunda assinatura de fact/2, onde 5 é vinculado a N e 1 é vinculado a Acc.
• Neste ponto temos na pilha: fact(5, 1), N = 5 e Acc = 1.
• É executada a função erlang:'-'/2 com os parâmetros 5 e 1, retornando 4.
• É executada a função erlang:'*'/2 com os parâmetros 5 e 1, retornando 5.
• É identificada a last call fact/2 com os parâmetros 4 e 5, portanto fact(5, 1) é desempilhado, assim como suas variáveis.
• 4 é diferente de 0, então caímos na segunda assinatura de fact/2, onde 4 é vinculado a N e 5 é vinculado a Acc.
• Neste ponto temos na pilha: fact(4, 5), N = 4 e Acc = 5.
• É executada a função erlang:'-'/2 com os parâmetros 4 e 1, retornando 3.
• É executada a função erlang:'*'/2 com os parâmetros 4 e 5, retornando 20.
• É identificada a last call fact/2 com os parâmetros 3 e 20, portanto fact(4, 5) é desempilhado, assim como suas variáveis.
• 3 é diferente de 0, então caímos na segunda assinatura de fact/2, onde 3 é vinculado a N e 20 é vinculado a Acc.
• Neste ponto temos na pilha: fact(3, 20), N = 3 e Acc = 20.
• É executada a função erlang:'-'/2 com os parâmetros 3 e 1, retornando 2.
• É executada a função erlang:'*'/2 com os parâmetros 3 e 20, retornando 60.
• É identificada a last call fact/2 com os parâmetros 2 e 60, portanto fact(3, 20) é desempilhado, assim como suas variáveis.
• 2 é diferente de 0, então caímos na segunda assinatura de fact/2, onde 2 é vinculado a N e 60 é vinculado a Acc.
• Neste ponto temos na pilha: fact(2, 60), N = 2 e Acc = 60.
• É executada a função erlang:'-'/2 com os parâmetros 2 e 1, retornando 1.
• É executada a função erlang:'*'/2 com os parâmetros 2 e 60, retornando 120.
• É identificada a last call fact/2 com os parâmetros 1 e 120, portanto fact(2, 60) é desempilhado, assim como suas variáveis.
• 1 é diferente de 0, então caímos na segunda assinatura de fact/2, onde 1 é vinculado a N e 120 é vinculado a Acc.
• Neste ponto temos na pilha: fact(1, 120), N = 1 e Acc = 120.
• É executada a função erlang:'-'/2 com os parâmetros 1 e 1, retornando 0.
• É executada a função erlang:'*'/2 com os parâmetros 1 e 120, retornando 120.
• É identificada a last call fact/2 com os parâmetros 0 e 120, portanto fact(1, 120) é desempilhado, assim como suas variáveis.
• 0 casa com a primeira assinatura da função fact/2, portanto 120 é vinculado a Acc.
• Neste ponto temos na pilha: fact(0, 120) e Acc = 120.
• A função retorna 120, que é consumido pela chamada original.

Repare que a pilha permaneceu com tamanho constante por todo o processo. É possível executar fact(200) sem estourar a pilha, aumentando apenas o tempo de processamento.

Esta é então a dica para a programação de loops em Erlang: use funções tail recursive, que são aquelas cuja chamada da recursão (da própria função) é a última do procedimento, e armazena a resposta em um acumulador em vez de aguardar o retorno de cada reiteração para processar o próximo resultado.

[]’s
Cacilhας, La Batalema