Erlang (programming language)/Tutorials

Erlang Language Programming Tutorials

Examples

Prime Sieve (parallel with linda type coordination)

   -module(primes).

   % This is a simple linda tuplespace. Here we use it to find primes numbers.
   % This tuple-space can not have duplicate tuples, but with a prime sieve it does
   %  not matter.

   -compile(export_all).

   start() -> start(100).  % defualt value for max is 100
   start(Max) -> 
       io:format("  Loading ~w numbers into matrix (+N) \n ", [ Max ] ),
       Lid = spawn_link( primes, linda, [Max, [], [] ]),
       Sqrt = round(math:sqrt(Max)+0.5),  
       io:format(" Sqrt(~w) + 1 = ~w \n " , [Max,Sqrt] ),  
       io:format(" Tuple space is started ~n ",[]),  
       io:format(" ~w sieves are spawning (+PN) ~n ", [Sqrt] ),
       io:format(" Non prime sieves are being halted (-PN) ~n ", [] ),
       % load numbers into tuplespace 
       % and spawn seive process
       spawn( primes, put_it, [Max, Max, Lid] ).

   sleep(N) ->
       receive
       after N -> time_is_up  
       end.

   start_sieves(Lid) ->
       Lid ! {self(), get, all, pids},  
       receive 
           {lindagram, pids, Pids} -> done
       end,
       start_sieve_loop(Pids).

   start_sieve_loop([]) -> done;
   start_sieve_loop([Pid|Pids]) ->
       receive
       after 100 -> done
       end,
       Pid ! {start},
       start_sieve_loop(Pids).

   spawn_sieves( _Max, Sqrt, _Lid, Sqrt ) -> done;  
   spawn_sieves( Max, Inc, Lid, Sqrt ) ->
       T = 1000,
       Pid = spawn( primes, sieve, [ Max, Inc+Inc, Inc, Lid, T ]),
       Name = list_to_atom("P" ++ integer_to_list(Inc)),
       Lid ! {put, pid, Name},
       register( Name, Pid),
       io:format(" +~s ", [atom_to_list(Name)]),
       spawn_sieves( Max, Inc+1, Lid, Sqrt ).

   put_it(Max, N, Lid) when N =< 1 ->
       Sqrt = round(math:sqrt(Max)+0.5),
       spawn_sieves( Max, 2, Lid, Sqrt );  

   put_it(Max, N,Lid) when N > 1 ->
       receive
       after 0 ->
           Lid ! {put, N, N},
           if 
               N rem 1000 == 0 ->
                   io:format(" +~w ", [N]);
               true -> done
           end,
           put_it(Max, N-1,Lid)
       end.

   % the 2 sieve starts last and has the most to do so it finishes last
   sieve(Max, N, 2, Lid, _T) when N > Max -> 
       io:format("final sieve ~w done, ~n", [2] ),
       Lid ! {dump,output};

   sieve(Max, N, Inc, _Lid, _T) when N > Max ->    
       io:format("sieve ~w done ", [Inc] );

   sieve(Max, N, Inc, Lid, T) when N =< Max ->   
       receive 
       after 
           T -> NT = 0   
       end,
       receive 
           {lindagram,Number} when Number =/= undefined -> 
               clearing_the_queue;
           {exit} -> exit(normal)
       after
           1 -> done 
       end,

       % remove multiple of number from tuple-space
       Lid ! {self(), get, N},
       Some_time = (N rem 1000)==0,
       if Some_time -> io:format("."); true -> done end,

       % remove (multiple of Inc) from sieve-process space
       Name = list_to_atom("P" ++ integer_to_list(N)),
       Exists = lists:member( Name, registered()),
       if 
           Exists ->
               Name ! {exit},
               io:format(" -~s ", [atom_to_list(Name)] );
           true -> done
       end,
       sieve(Max, N+Inc, Inc, Lid, NT).        % next multiple
       
   %% linda is a simple tutple space 
   %%    if it receives no messages for 2 whole seconds it dumps its contents 
   %%    as output and halts

   linda(Max, Keys, Pids) ->
       receive
       {put, pid, Pid} ->
           linda(Max, Keys, Pids++[Pid]);
       {put, Name, Value} ->
           put( Name, Value),
           linda(Max, Keys++[Name], Pids);
       {From, get, Name} ->
           From ! {lindagram, get( Name)},
           erase( Name ),                          % get is a desructive read  
           linda(Max, Keys--[Name],Pids);
       {From, get, all, pids} ->
           From ! {lindagram, pids, Pids},
           linda(Max, Keys, Pids );
       {From, get, pid, Pid} ->
           L1 = length( Pids ),
           L2 = length( Pids -- [Pid]),
           if 
               L1 > L2 ->  % if it exists
                   From ! {lindagram, pid, Pid};
               true -> 
                   From ! {lindagram, pid, undefined}
           end,
           linda(Max, Keys, Pids );
       {dump,output} ->
           io:format(" ~w final primes remain: ~w ~n ", [length(Keys),  lists:sort(Keys) ])
       after (100*Max) -> % if there is not tuple action after some time then print the results
           io:format(" ~w primes remain: ~w ~n ", [length(Keys),  lists:sort(Keys) ])
       end.

Sample Output

c(primes).
primes:start(1000).
 Loading 1000 numbers into matrix (+N)
 Sqrt(1000) + 1 = 32
 Tuple space is started
 32 sieves are spawning (+PN)
 Non prime sieves are being halted (-PN)
 +1000 <0.46.0>
+P2  +P3  +P4  +P5  +P6  +P7  +P8  +P9  +P10  +P11  +P12  +P13  +P14  +P15  +P16   
+P17  +P18  +P19  +P20  +P21  +P22  +P23  +P24  +P25  +P26  +P27  +P28  +P29  +P30  
+P31  -P8  -P6  -P4  -P9  -P12  -P10  -P15  -P15  -P18  -P14  -P21  -P21  -P22  
-P26  -P20  -P24  -P25  -P27  -P28  -P30  -P30  -P16 sieve 31 done sieve 29 done 
sieve 19 done sieve 23 done sieve 11 done sieve 13 done sieve 17 done sieve 7 done 
.sieve 5 done sieve 3 done .final sieve 2 done,
168 final primes remain: 
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,
193,197,199,
211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,
307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,
401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,
503,509,521,523,541,547,557,563,569,571,577,587,593,599,
601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,
701,709,719,727,733,739,743,751,757,761,769,773,787,797, 
809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,
907,911,919,929,937,941,947,953,967,971,977,983,991,997]