Erlang: recursão e guardas

Eu não gastei muito tempo explicando recursão por causa daquilo que disse no começo deste curso: eu considero que quem o está seguindo são programadores experientes. Eu sei que o conceito de recursão pode ser difícil para iniciantes, mas não é aqui o lugar para entrar no b+a=ba da coisa.

O que programadores experientes podem achar estranho é o uso de recursão para quase tudo. “É que recursão consome pilha” você deve estar pensando. E está até certo. Nas linguagens procedurais e nas orientadas a calças, fazer uma recursão muito profunda pode se tornar uma grande dor de cabeça.

Python, por exemplo, tem um limite de recursão interno. Depois de umas milhares de chamadas, o interpretador sobe uma exceção (“RuntimeError: maximum recursion depth exceeded”). Em C, se você estourar a pilha, teu programa morre.

Então Erlang é muito ruim, certo?

Errado.

Erlang aproveita ao máximo a pilha, contanto que o programador dê uma ajudinha. Vamos ver aquela nossa implementação das primeiras aulas novamente?

-module(funcoes).
-export([ler_arquivo/1]).

ler_arquivo(Filename) -ᐳ
    {Status, Fd} = file:open(Filename, [read]),
    ler_arquivo(Status, Fd).

ler_arquivo(error, Reason) -ᐳ
    io:format("Erro '~s' ao abrir o arquivo.", [erlang:atom_to_list(Reason)]);
ler_arquivo(ok, Fd) -ᐳ
    interpretar_linha(file:read_line(Fd), Fd).

interpretar_linha({ok, [$#|Resto]}, Fd) -ᐳ
    interpretar_linha(file:read_line(Fd), Fd);
interpretar_linha({ok, Linha}, Fd) -ᐳ
    io:format("~s", [Linha]),
    interpretar_linha(file:read_line(Fd), Fd);
interpretar_linha(eof, Fd) -ᐳ
    file:close(Fd).

Eu quero que você preste atenção à função interpretar_linha/2. Repare que, enquanto o arquivo não terminar, uma nova chamada a esta função será feita. Se o arquivo tiver 1 milhão de linhas, teremos um milhão de chamadas recursivas.

Em outras linguagens, isso seria o suficiente para fazer um bom estrago. Ou, no mínimo, demorar bastante. Mas não em Erlang, pois interpretar_linha/2 é “tail recursive”.

A versão aportuguesada de “tail recursive” é, segundo a Wikipedia, “recursiva em cauda”. Blerg! O termo melhor, na verdade, é:

Função com cauda recursiva

Qual é o sentido disso?

Vou explicar com um contra-exemplo. Vamos ver uma função que não tem cauda recursiva:

fibo(0) -ᐳ 0;
fibo(1) -ᐳ 1;
fibo(X) -ᐳ
    fibo(X-1) + fibo(X-2).

Quando eu chamo fibo(5), como fica a execução? Fica assim:

fibo(5) -ᐳ fibo(4) + fibo(3);
fibo(4) -ᐳ fibo(3) + fibo(2);
fibo(3) -ᐳ fibo(2) + fibo(1);
fibo(2) -ᐳ fibo(1) + fibo(0);
Retorna 0;
Retorna 1;
Retorna 1;
Retorna 2;
Retorna 3;
…

Ah, desisto. A execução vai longe. A pilha fica crescendo e diminuindo a toda hora. Isso é um exemplo de implementação ruim em Erlang (sim, isso é possível).

Repare na cauda da função, que é a última cláusula da mesma: ela é composta de duas outras chamadas a funções. Ou seja: ela tem que ficar aguardando a execução das outras funções antes de poder sair da pilha (ou melhor: ser desempilhada).

Já na nossa interpretar_linha/2, a última cláusula é apenas uma chamada a outra função. Repare que, depois de chamar a si mesma na última cláusula, aquele “registro de ativação” (que é “a instância da execução da função na pilha”) já pode ir embora. Se o que você (função) retorna é simplesmente uma chamada a outra função, a VM do Erlang é esperta o suficiente para perceber que o que interessa mesmo é o retorno da outra função (cujos argumentos você já, sabiamente, organizou devidamente) e descarta o registro de ativação da função que estava sendo executada.

(Não entendeu? Então relaxe, pegue um café e leia novamente os dois últimos parágrafos.)

(Ainda não entendeu? Então você precisa estudar programação. Sério.)

Assim, se a função tem cauda recursiva, um registro de ativação simplesmente vai sobrepondo o outro na memória, sem gasto de pilha. Na prática, é como implementar um “fibo” iterativo! Por isso mesmo Erlang não se importa em implementar iterações a nível de linguagem (como for, foreach, etc). Contanto que suas funções tenham cauda recursiva, o desempenho será excelente.

E como implementar a sequencia de Fibonacci em Erlang com cauda recursiva? Eu fiz aqui uma versão rascunho de como seria:

-module(fibo).
-export([fibo/1]).

fibo(X) when X ᐸ 1  -ᐳ 0;
fibo(X) -ᐳ
    fibo(X, 1, 0).

fibo(1, _, Anterior) -ᐳ
    % Essa função não é para quando chama-se com X=1, mas
    % quando a fibo(X-1) é chamada e X já é 1, pois está
    % sendo decrementado.
    Anterior;
fibo(X, Atual, Anterior) -ᐳ
    io:format("~p+~p~n", [Atual, Anterior]),
    fibo(X-1, Atual+Anterior, Atual).

Repare que em fibo/3 colocamos um “contador” (o X decrementa-se) e um “acumulador” (Atual vai somando-se com Anterior).

Guardas

O legal é que eu acabei usando um guarda, que é aquele “when X ᐸ 1” na linha 7. Acontece o seguinte: se alguém chamar fibo(-1), por exemplo, meu programa entraria num loop infinito, pois a condição de parada, que é a linha 11 (quando X=1), nunca seria alcançada.

Quando eu vi os guardas pela primeira vez, achei um xunxo miserável. Um remendo estranho. Mas eu ainda não entendia seu propósito. Eles servem para você poder “casar padrões” de maneira mais rica. Afinal, casar com ok, 10 ou #$ é fácil. Difícil é casar um padrão com “X tem que ser maior que um”.

O problema, no começo, é que isso lembra muito um if das linguagens que já conhecemos. Mas não se deixe enganar: isso é uma ferramenta para “casamento de padrões ricos”, digamos assim. Eu tinha a impressão que poderia trocar isso por um if dentro da própria função. Mas isso me levaria ao paradigma procedural, em que eu digo como o programa deve fazer e não o que ele deve fazer!

Se você ainda não teve o “insight mágico” sobre guardas, recomendo reler as lições anteriores. Sério. Lá eu explico o motivo pelo qual dividir o código em várias funções é, em geral, algo muito bom.

De volta à recursão

Nenhuma função definida no segundo exemplo de Fibonacci não tem cauda recursiva e, portanto, podemos calcular o n-ésimo número da sequencia com desempenho de um algoritmo iterativo. Uau!

Repare que nosso algoritmo tem um ponto de parada: quando fibo/3 é chamada com X=1 ela cai na “função de parar” (linha 11), que dá um retorno sem chamar mais ninguém. Experimente removê-la e executar um fibo(2), por exemplo.

…

Coisa linda, não? Recursão infinita, o while(true) do Erlang!

Para abortar, no erl, pressione ctrl+c e aborte (opção “a”).

Resumo

Este artigo foi originalmente escrito em 04/12/2014.