Some ways of calculating factorial with Erlang
We use Erlang to write a program that calculate factorial. Sequential Erlang is a functional language. We calculate a factorial by recursion as usual:
Given a non-zero integer N, fact of N is N multiply by fact of (N - 1).
Yet the function fact1 is not tail recursive. We do the optimization part by passing an accumulator as
additional argument.
Is fact2 scalable? The code is plainly sequential; the execution time would remain the same whether fact2 is run on one-core or multicores machine.
There are several ways for parallelizing this code, for instance, dividing [1..N] into smaller ranges to which they can be evaluated concurrently. Nevertheless in the following, let's see a classical (not necessary efficient!) implementation of factorial.
We have three types of Erlang processes, a customer who needs to obtain fact of N, sends N and its address to the rec_factorial service. the rec_factorial on receiving a tuple (N, Cust), creates a helper process rec_customer that on receiving an integer K, sends the result N*K to Cust. rec_fact then sends to itself a message for evaluating the factorial of N - 1, and sends the result to the rec_customer it has just created.
This version creates N rec_cust processes that waits on a incoming integer to start the work. It can be seen that the actual evaluation happens when N decrease to 0. At that time, the last created rec_cust receiving value 1 from rec_fact and kicks in the chain of rec_custs which was created before it. Eventually this chain collapsed to the first created rec_cust that sends the fact N to the customer!
We use Erlang to write a program that calculate factorial. Sequential Erlang is a functional language. We calculate a factorial by recursion as usual:
Given a non-zero integer N, fact of N is N multiply by fact of (N - 1).
fact1(0) -> 1;
fact1(N) when N >= 0 -> N * fact (N-1)
Yet the function fact1 is not tail recursive. We do the optimization part by passing an accumulator as
additional argument.
fact2(N) when N >= 0 -> fact2(N, 1).
fact2(0, Acc) -> Acc;
fact2(N, Acc) -> fact (N-1, Acc * N).
Is fact2 scalable? The code is plainly sequential; the execution time would remain the same whether fact2 is run on one-core or multicores machine.
There are several ways for parallelizing this code, for instance, dividing [1..N] into smaller ranges to which they can be evaluated concurrently. Nevertheless in the following, let's see a classical (not necessary efficient!) implementation of factorial.
We have three types of Erlang processes, a customer who needs to obtain fact of N, sends N and its address to the rec_factorial service. the rec_factorial on receiving a tuple (N, Cust), creates a helper process rec_customer that on receiving an integer K, sends the result N*K to Cust. rec_fact then sends to itself a message for evaluating the factorial of N - 1, and sends the result to the rec_customer it has just created.
fact(N) ->
Fact = spawn(fun rec_fact/0),
Fact ! {N, self()},
receive
Ret -> Ret
end.
rec_fact() ->
receive
{N, Cust} when N == 0 ->
Cust ! 1;
{N, Cust} ->
C = spawn(fun() -> rec_cust(Cust, N) end),
self() ! {N - 1, C}
end,
rec_fact().
rec_cust(Cust, N) ->
receive
K ->
Cust ! N * K
end.
This version creates N rec_cust processes that waits on a incoming integer to start the work. It can be seen that the actual evaluation happens when N decrease to 0. At that time, the last created rec_cust receiving value 1 from rec_fact and kicks in the chain of rec_custs which was created before it. Eventually this chain collapsed to the first created rec_cust that sends the fact N to the customer!
