Skip to content
agosto 17, 2008 / cassiomarques

Um pouco de Erlang, programação funcional e recursividade

Comecei a estudar um pouco de Erlang recentemente. A linguagem realmente é bem diferente daquilo que estou acostumado, principalmente por ser um linguagem totalmente funcional e possuir certos conceitos que em um primeiro momento realmente podem confundir a cabeça de quem está mais acostumado com linguagens imperativas.
Na verdade, eu já acabei usando diversos conceitos de programação funcional em Ruby e até mesmo em Javascript. A existência de closures ajuda muito para que isso seja possível e para muitos problemas uma solução funcional pode se apresentar a mais natural.
Entretanto, em Erlang a coisa é diferente. Tudo é baseado em programação funcional.
Uma das estrututas de dados mais comumente utilizadas em praticamente qualquer linguagem de programação são as listas. Quer essas listas sejam representadas por simples arrays ou por estruturas mais complexas como listas encadeadas, as listas estão presentes sempre que desejamos realizar qualquer tipo de operação sobre conjuntos.

Em Erlang, as listas são representadas através de estruturas do tipo [el1, el2, el3, …, eln], onde eli pode assumir formas mais complexas, como em Lista = [{banana, 3}, {pera, 5}]. Neste exemplo estamos representando, por exemplo, uma lista de compras que contém 3 bananas e 5 pêras. O problema é não confundir as palavras “banana” e “pera” com strings ou variáveis: neste exemplo, banana e pera são atoms, ou seja, apenas identificadores para elementos da lista.
Outro detalhe importante é que em Erlang um símbolo somente será considerado como uma variável se começar por uma letra maiúscula.

Mas vamos ver então em detalhes como Erlang opera sobre listas!

Vamos partir de um exemplo bastante simples. Suponha que você possui uma lista de números inteiros e deseja calcular o produtório desta lista, ou seja, sair multiplicando número por número até chegar em um total.

Em uma linguagem imperativa como C, isso poderia facilmente ser feito assim:

#include <stdio.h>

int main()  {
  int lista[5] = {3, 5, 7, 2, 8};
  int prod = 1, i = 0;
  for(i = 0; i < 5; ++i) { prod *= lista&#91;i&#93;; }
  printf("Produto = %d\n", prod);
}
&#91;/source&#93;

Até aqui, ok, Basta fazermos um laço e sair multiplicando os números dentro do array <code>prod</code> que representa nossa lista.

Mas e em Erlang, como ficaria isso? Bom, primeiro precisamos entender como Erlang processa os elementos de uma lista. Em Erlang, pode-se assumir que toda e qualquer lista é formada de duas partes: HEAD e TAIL. HEAD é sempre o primeiro elemento da lista, ou seja, um escalar. Já TAIL representa o restante da lista. Assim, na lista [1,2,3,4] temos HEAD = 1 e TAIL = [2,3,4]. Na verdade os nomes HEAD e TAIL são apenas convenções, não é obrigatório que você use estes termos para representar as duas "partes" das listas em Erlang. Mas convenções são boas e facilitam a compreensão do código que escrevemos em qualquer linguagem.
Como podemos então extrair e armazenar em variáveis os valores de HEAD e TAIL de uma lista? Usando <i>pattern matchers</i>. Na verdade, em Erlang todas as atribuições de valores a variáveis são feitas através da utilização de pattern matchers. O operador utilizado para isso é o =. Mas aqui, = tem um significado diferente do que você está acostumado! Sim! Igual não é mais igual e o mundo está perdido... 
A verdade é que em Erlang = não representa necessariamente igualdade. = serve para "casar" padrões. Cada variável pode armazenar um determinado padrão e você pode utilizar o operador = para verificar se este padrão "casa" com algum outro e então fazer associações de valores dentro destes padrões. Assim:

%% Em Erlang, linhas que começam com % são comentários.
%% Todas as linhas que representam "comandos" devem terminar com um ponto 
1> X = 2.

Ok, agora a variável X vale 2. Mas isso porque antes disso não associamos nenhum outro valor a X, ela era uma variável “vazia”, ou, usando a terminologia do Erlang, X era uma unbound variable. Agora, se tentarmos alterar o valor de X, olhe o que acontece:

2> X = 4.
=ERROR REPORT==== 17-Aug-2008::14:34:44 ===
Error in process  with exit value: {{badmatch,4},[{erl_eval,expr,3}]}

** exited: {{badmatch,4},[{erl_eval,expr,3}]} **

Que erro bizarro! Que porcaria de linguagem é essa que não me permite alterar o valor de uma variável? O que ocorre é que Erlang é uma linguagem para processamento paralelo, onde diferentes processos trocam mensagens entre si. Se temos por exemplo 3 processos A, B e C que se comunicam entre si e uma variável X que é usada pelos 3 processos, se A passar o valor para B e este alterá-lo, quando C for usar esta variável pode ser que ocorram resultados inesperados. Por isso Erlang mantém as variáveis imutáveis durante toda sua existência.
Partindo deste princípio, podemos fazer o seguinte:

1> X = 2. %%X era 'unbound' e acabou de receber seu valor (2)
2> X = 1 + 1. %% funciona, porque 1 + 1 representa o mesmo padrão que 2

Ok, vamos parar de enrolar e voltar para a nossa lista, de onde queremos extrair nossas partes HEAD e TAIL.

Podemos usar o operador | (nosso velho amigo ‘pipe’) para fazer o trabalho. Podemos então escrever:

Numeros = [3, 5, 7, 2, 8].
[H|T] = Numeros.

E após isso teremos a variável H armazenando 3 (nosso HEAD) e a variável T armazenando [5, 7 , 2, 8] (o resto da lista ou TAIL).

Para podermos calcular nosso produtório precisamos ainda dar um olhadinha em como funcionam funções em Erlang. O processo todo funciona através da utilização de modules. Um module é um elemento de software onde você pode declarar suas funções. Em seguinda você precisa exportar essas funções para que as mesmas possam ser utilizadas por código fora do módulo. Algo assim:

-module(produtorio).
-export([prod/1]).
prod([H|T]) -> H * prod(T);
prod([])      -> 1.

Na primeira linha estamos fazendo a declaracao de um modulo chamado “produtorio”. Na segunda linha estamos exportando uma função chamada “prod” que recebe um único argumento (por isso o “/1”), para que a função possa ser usada por código em outras partes do programa.
A terceira e quarta linhas definem nossa função prod, a qual efetivamente realiza o nosso cálculo. Para explicar o que está acontecendo aqui, precisamos relembrar alguns conceitos de recursividade.
Uma função recursiva é uma função que, para atingir seu objetivo, realiza chamadas a si mesma. Assim, podemos por exemplo escrever uma função recursiva soma([1,2,3]) como soma(1, soma([2,3])).

Por definição, uma função recursiva deve possuir duas características:
1) Deve possuir uma solução trivial, ou seja, uma situação onde a função pára de chamar a si mesma recursivamente e a pilha de chamadas passa a ser desfeita, até a primeira chamada feita, onde o resultado finalmente é retornado ao ponto do código que fez a chamada a nossa função.
2) A função deve ser escrita de forma que caminhe naturalmente para a solução do problema ou, em outras palavras, a função deve ser convergente, caso contrário as chamadas recursivas ocorrerão infinitamente, levando a um estouro na pilha de chamadas da função.

Essas duas características podem ser facilmente observadas na nossa função prod acima. Na linha

prod([H|T]) -> H * prod(T);

temos a forma em que as chamadas recursivas ocorrerão, o que demonstra claramente que há convergência para a solução. A função recebe uma lista de valores, extraí o primeiro elemento da lista e retorna como resultado desta chamada específica o resultado da multiplicação deste elemento pelo resultado de uma chamada a si mesma, passando o restante da lista (ou TAIL) como argumento. É fácil observar que a cada nova chamada, TAIL diminui, até chegar a 0 (zero) elementos. Essa é a nossa solução trivial, encontrada pela linha

prod([])    -> 1.

Aqui, não é mais necessário realizar chamadas recursivas, pois sabe-se que para a lista vazia basta multiplicar por 1, ou seja, o elemento neutro da multiplição. A partir deste ponto a pilha de chamadas recursivas passa a ser esvaziada até chegarmos à sua basse, ou seja, a primeira chamada feita à função prod().

Por fim, podemos usar nossa função assim (através do erl, o console do Erlang):

1> c(produtorio).
{ok,produtorio}
2> Lista = [3,6,8,4,7].
[3,6,8,4,7]
3> P = produtorio:prod(Lista).
4032
4> 

Em (1) estamos compilando nosso module produtorio para um arquivo com extensão .bean, para que possamos usá-lo por todo nosso programa. Em (2) declaramos uma variável Lista, que representa uma lista de valores sobre os quais desejamos calcular o produtório. Em (3) realizamos efetivamente a chamada à função prod. A sintaxe produtorio:prod indica que a função prod faz parte do module produtorio. Você pode pensar nisso como um esquema de namespaces.
O cálculo ocorre seguindo a seguinte lógica:

Chamada 1) HEAD -> 3, TAIL -> [6,8,4,7], retorno -> 3 * prod([6, 8, 4, 7])
Chamada 2) HEAD -> 6, TAIL -> [8,4,7], retorno -> 18 * prod([8,4,7])
Chamada 3) HEAD -> 8, TAIL -> [4, 7], retorno -> 144 * prod([4, 7])
Chamada 4) HEAD -> 4, TAIL -> [7], retorno -> 576 * prod([7])
Chamada 5) HEAD -> 7, TAIL -> [], retorno -> 4032 * prod([])
Chamada 6) Utiliza-se a solução trivial, retornando-se 4032 * 1 e dando fim à cadeia de chamadas recursivas.

Conforme eu for estudando mais coisas sobre Erlang eu vou postando aqui o que achar interessante!

16 Comentários

Deixe um comentário
  1. Ricardo Costa / ago 20 2008 9:41 am

    Gostei do post e fui ler sobre erlang, mas nao deu pra entender muito.

    veja essa função:

    % down/1
    % escreve todos os numeros inteiros de N até 1.

    down(0) -> ok;
    down(N) -> io:format(“~w~n”,[N]), down(N-1).

    —————————
    Agora essa:

    % up/1
    % escreve os numeros inteiros de 1 ate N.

    up(0) -> ok;
    up(N) -> up(N-1), io:format(“~w~n”,[N]).

    —————————-
    As duas sao recursivas, mas nao entendi o fluxo delas, trocando a ordem da chamada com o numero
    decrementado ela muda a ordem com que escreve os numeros.

    se você entendeu, me explica aí, valeu

    • lucas angelo / set 16 2009 2:04 pm

      ola ricardo sou um estudante de ciencia da computação
      e estou encrencado pois o professor passou erlang
      para mim aprender a linguagem em um mes e fazer um jogo
      so que eu to apanhando em como fazer para salvar um
      arquivo pelo compilador erlang e depois gerar o executavel ,se voce puder me ajudar eu agradeceria muito
      gostaria que voce explicasse detalhadamente ,eu estou
      usando a ultima versão do editor erlang para windows

    • lucas angelo / set 16 2009 2:08 pm

      ola ricardo sou um estudante de ciencia da computação
      e estou encrencado pois o professor passou erlang
      para mim aprender a linguagem em um mes e fazer um jogo
      so que eu to apanhando em como fazer para salvar um
      arquivo pelo editor erlang e depois gerar o executavel ,se voce puder me ajudar eu agradeceria muito
      gostaria que voce explicasse detalhadamente ,eu estou
      usando a ultima versão do editor erlang para windows,
      repeti a mensagem nao era compilador é editor

  2. cassiomarques / ago 20 2008 3:12 pm

    Olá Ricardo,

    Para entender essas duas funções e, principalmente, porque a up() apesar de parecer estranha, funciona certinho, você tem que entender a ordem com que as chamadas recursivas ocorrem.

    Qualquer chamada de função dentro do fluxo de um programa funciona como uma espécie de “pilha de chamadas”. Se você tem por exemplo as funções A, B e C, seguindo a seguinte sequência:

    A(n) = B(n + 1);
    B(n) = C(n + 2);
    C(n) = n * 2;

    Quando o programa chegar na função C() você terá 3 funções carregadas na memória. Você pode interpretar isso como se as funções estivessem empilhadas, com A() na base e C() no topo. Como C() não chama nenhuma outra função, ocorre que:

    pilha de funções => A(1), B(2), C(3) => 6
    pilha de funções => A(2), B(2) => 6
    pilha de funçòes => A(2) => 6
    Resultado retornado por A() para o programa => 6
    E o programa continua…

    Percebeu como as chamadas vão sendo “desempilhadas”?

    Para chamadas recursivas acontece exatamente o mesmo. A partir desta noção podemos voltar aos exemplos que você postou. A função down() é trivial. Em pseudo-linguagem, o que ela faz é:

    funcao down(n) {
    se n == 0
    imprime “ok”
    senao {
    imprime n
    chama down(n-1) recursivamente.
    }
    }

    Percebeu como a função primeiro imprime o valor de n para depois chamar down(n-1) ? Essa sequência é muito importante dentro da execução do método. O resultado é que conforme você EMPILHA as chamadas, você imprime os números. Quando chegamos a n = 0, não existem mais chamadas recursivas e a pilha começ a a ser esvaziada, mas neste ponto todos os valores de n já foram impressos.

    O pulo do gato é na função up(). Vejamos ela em pseudo-linguagem:

    funcao up() {
    se n == 0
    imprima “ok”
    senao {
    chama up(n-1) recursivamente
    imprime n
    }
    }

    Como você mesmo disse o que muda aqui é somente a sequência das linhas… Mas isso faz toda a diferença! Para a funcao up(), perceba que a linha que imprime o valor de n vem DEPOIS da chamada recursiva, ou seja, essa linha somente sera executada quando a pilha de chamadas estiver sendo esvaziada! Você pode pensar nisso da seguinte forma: Se você empilhar, nesta sequência, os números (1,2,3,4,5), quando desempilhá-los terá os números na sequência inversa (5,4,3,2,1). Quando você lava pratos, o primeiro a ir pra água é o que está no topo da pilha…

    Assim, a funcao up() só imprime quando estiver “voltando” na pilha de chamadas. Se então você tentar calcular por exemplo o resultado de up(4), a seguinte sequência será executada:

    1) up(4) => empilha
    2) up(3) => empilha
    3) up(2) => empilha
    4) up(1) => empilha
    5) up(0) => ok e comeca a desempilhar
    6) imprime n para a chamada da linha (4), ou seja, 1.
    7) imprime n para a chamada da linha (3), ou seja, 2.
    8) imprime n para a chamada da linha (2), ou seja, 3.
    9) imprime n para a chamada da linha (1), ou seja, 4.

    Espero que você tenha entendido!

    Abraço!

  3. Ricardo Costa / ago 21 2008 4:10 am

    % Valeu, deu pra entender sim. A pilha explica tudo. :)

    ———————————————
    myfunc(N) -> io:format(“~w ~w ~n”,[loop, N]).

    % for/1
    % Um loop tipo for para ir incrementando.

    for(N) -> for(1, N).

    for(N,N) -> myfunc(N);
    for(I,N) -> myfunc(I), for(I+1,N).

    ———————————————
    % pode entao ser feito assim, ne?

    for(0) -> ok;
    for(N) -> for(N-1), myfunc(N).

  4. marcos silva / ago 31 2008 4:34 pm

    pode me apresentar uma solução para a soma da sequencia 1+ 1/1!+1/2!+1/3!+…+1/n!

  5. cassiomarques / set 1 2008 2:11 am

    @marcos,

    %% calcula a seguinte sequencia: 1+ 1/1!+1/2!+1/3!+…+1/n!
    -module(sequencia).
    -export([um_sobre_fatorial/1]).
    -export([fatorial/1]).

    fatorial(0) -> 1;
    fatorial(1) -> 1;
    fatorial(N) -> N * fatorial(N-1).

    um_sobre_fatorial(1) -> 1;
    um_sobre_fatorial(N) -> 1/fatorial(N) + um_sobre_fatorial(N-1).

    Usei duas funções para deixar o código mais simples. A primeira calcula apenas o fatorial e a segunda a sequência em si.

  6. marcos silva / set 2 2008 2:15 pm

    obrigado Cassio Marques, mas você pode me mostrar esse algoritmo com recursividade em “C”

  7. marcos silva / set 2 2008 2:19 pm

    pode me apresentar uma solução para a soma da sequencia 1+ 1/1!+1/2!+1/3!+…+1/n!, recursivo em linguagem “C”. Obrigado.

  8. cassiomarques / set 2 2008 2:28 pm

    @marcos,
    Sinceramente amigo, não vou fazer seu dever de casa não…
    O tópico é sobre Erlang e só respondi sua mensagem anterior porque achei que você estava interessado em saber como resolver o problema usando Erlang.
    Na verdade a sintaxe que utilizei na solução apresentada é bastante parecida com uma solução puramente matemática (afinal de contas Erlang é uma linguagem puramente funcional), logo se você olhar com calma vai entender. Algorítmo é algorítmo, independe de linguagem. Se você conhecer o mínimo de C não deverá ter problemas para traduzir a solução.

  9. marcos silva / set 2 2008 6:50 pm

    na verdade, eu tenho a solução em “C”, Pascal, visualg, delph so busco outros tipos de implementação para catalogar, mas agradeço sua gentileza Good.

  10. Dhérsy Gabreil / nov 4 2008 7:36 am

    Amigo tem como fazer programas em erlang com arquivos?… pode ser text ou bin!

  11. cassiomarques / nov 4 2008 11:54 am

    Sim, é perfeitamente possível trabalhar com arquivos em Erlang. Você pode pesquisar por “Erlang + files” que encontrará muitas referências.

  12. Édipo / maio 3 2009 7:39 am

    Olá Cassio, prabens pelo blog esta muito bom, o mesmo para esse post recentemento começei a ler sobre Erlang tambem, realmente é algo muito interessante, mas você disse que Erlang é uma linguagem puramente funcional, mas isso não seria falso por exemplo no caso de I/O ?

  13. cassiomarques / maio 3 2009 3:55 pm

    @Édipo,

    I/O não promove necessariamente mudança de estado, logo permite programação funcional sem problemas.

  14. Édipo / maio 3 2009 6:23 pm

    HUm, eu achava que sim, estão podemos categorizar Erlang como puramento funcional sem problemas ?

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: