terça-feira, agosto 28, 2007

Programação dinâmica & Concorrência

Como havia falado no post anterior, eis aqui a implementação de um processo servidor de resultados para cálculo de Fibonacci, juntamente com um "cache" dos resultados prévios.

-module(fibserver).
-export([fibserver/0, fibserver/1, fib/1, start/0]).

fibserver() ->
% Start the Fibonacci Server with some basic pre-defined values...
fibserver([{0,0}, {1,1}]).

fibserver(Values) ->
receive
{getValue, ReqPid, X} ->
ValueExists = lists:keymember(X, 1, Values),
if
ValueExists ->
{value, {_, V}} = lists:keysearch(X, 1, Values);
true ->
V = notFound
end,
% Send to the request process the atom notFound, or the Fibonacci of X.
ReqPid ! V,
fibserver(Values);
{putValue, ValueTuple} ->
fibserver(Values ++ [ValueTuple])
end.

fib(N) ->
% Ask the server for the Fibonacci of N...
fibServer ! {getValue, self(), N},
receive
% If the value doesn't exist yet, then...
notFound ->
% ...calculate it...
FibN = fib(N - 1) + fib(N - 2),
% ...update the server with this new value...
fibServer ! {putValue, {N, FibN}},
% ...return the calculated value.
FibN;
X ->
% The value was already in the server.
X
end.

start() ->
% Just start the process identified by the atom 'fibServer',
% as the execution of the fibserver:fibserver/0,
% that means, module fibserver, function fibserver
% that receives zero parameters.
register(fibServer, spawn(fibserver, fibserver, [])).

Coloquei alguns comentários, mas para o total entendimento do código, você deve ter uma noção básica sobre Erlang, qualquer dúvida só postar.

Para testar:
$ erl
Erlang (BEAM) emulator version 5.5.2 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.5.2 (abort with ^G)
1> c(fibserver).
{ok,fibserver}
2> fibserver:start().
true
3> fibserver:fib(1000).
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

O resultado é praticamente instantâneo :)

PS.: me esqueci de comentar como sair do shell do Erlang, basta pressionar Control-C, e então "a[enter]", ou então executar a função halt().

quarta-feira, agosto 22, 2007

Brincando com Erlang

Ultimamente tenho visto muitos posts comentando sobre a linguagem Erlang, que é uma linguagem funcional para programação concorrente, embora alguns defendam que também é orientada à objeto, já que Erlang oferece envio de mensagens como método para sincronização e comunicação entre processos, e orientação à objeto, na teoria, nada mais é do que troca de mensagens entre os objetos.

Como tive uma cadeira na faculdade sobre programação funcional (recomendo a todos aprenderem uma linguagem funcional ou de paradigma diferente do imperativo) usando Haskell, e gostei muito, resolvi começar a brincar com Erlang, que já tem um framework web e um banco de dados super escalável!

Para começar, instalei o pacote "erlang" no Debian Etch, muito simples.

Então vamos para nosso primeiro programa, "hello world" ou Fibonacci? Ok, ok...

  1. Crie um arquivo chamado hello.erl, com o seguinte código:
    -module(hello).
    -export([hello/0]).

    hello() -> io:format("Hello world!~n").
  2. Chame o interpretador Erlang com o comando "erl";
  3. Compile o programa:
    c(hello).
  4. Isto deve gerar um aviso {ok, hello};
  5. Vamos executar:
    hello:hello().
  6. Pronto, satisfeito?

Agora vamos ver como implementar o cálculo de Fibonacci de um número em Erlang, repare que o nome do arquivo deve ser fibonacci.erl, combinando com o nome do módulo:
-module(fibonacci).
-export([fib/1]).

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N - 1) + fib(N - 2).

Reparem que há um pattern matching nos 2 casos básicos, e após a implementação recursiva para qualquer N > 1, com base disso podemos diminuir um pouco o código:

fib(N) when N =< 1 -> N;
fib(N) -> fib(N - 1) + fib(N - 2).

A chamada desde código após a compilação é trivial, por exemplo:
fibonacci:fib(10)

O código em Haskell é muito semelhante (como não seria com esse pingo de código? :D)

fib n
| n <= 1 = n
| otherwise = fib (n-1) + fib (n-2)

Vá brincando, tente números mais altos, com 50 já vai demorar bastante o resultado, o que me sugestiona implementar algum mecanismo de programação dinâmica, uma idéia para um próximo post é implementar isso usando um processo servidor de resultados, exercitando então o mecanismo de troca de mensagens.

Finalizo por aqui, e clique aqui se quiser conferir a lista dos 500 primeiros valores para a série de Fibonacci.