Skip to content

Instantly share code, notes, and snippets.

@ijt ijt/sieve.erl
Last active Feb 20, 2016

Embed
What would you like to do?
Translation of the Go prime sieve to Erlang
#!/usr/bin/env escript
%% -*- mode: erlang -*-
%%! -smp enable -hidden
%%
%% A concurrent prime sieve, inspired by the Go prime sieve
%% with daisy-chained filter processes.
%% https://golang.org/doc/play/sieve.go
%%
%% Translated by Issac Trotts (2016)
%% with help from Amiramix on StackOverflow.
main(_) ->
Self = self(),
GenPid = spawn(fun() -> generate(Self, 2) end),
main_loop(GenPid).
%% Print primes, spawn filters for their multiples. GenPid is initially the
%% Pid of the Generator, but afterwards it is the Pid of the most recently
%% added filter.
main_loop(GenPid) ->
send(GenPid, ready),
receive
{number, Prime, _From} ->
io:format("~B~n", [Prime]),
%% Start a filter for multiples of Prime
Self = self(),
NewFilterPid = spawn(fun() -> filter(Self, GenPid, Prime) end),
%% Tell the previous filter to send its output to this new filter.
send(GenPid, {new_next, NewFilterPid}),
main_loop(NewFilterPid)
end.
send(Receiver, Msg) ->
Receiver ! Msg.
%% Send the sequence of integers starting at N to the process Next.
generate(Next, N) ->
receive
ready ->
send(Next, {number, N, self()}),
generate(Next, N+1);
{new_next, NewNext} ->
generate(NewNext, N)
end.
%% Relay the values received to the next filter in the chain,
%% removing those divisible by the prime P.
%%
%% generator -...-> Prev ---> filter ---> Next -...-> main
%% (P)
%%
filter(Next, Prev, P) ->
receive
{number, N, _From} ->
case N rem P of
0 ->
% N is disqualified, being a multiple of P.
% Notify the generator (via Prev) that we're ready
% to test the next number.
send(Prev, ready);
_ ->
% N passes this filter. Send it up the chain.
send(Next, {number, N, self()})
end,
filter(Next, Prev, P);
{new_next, NewNext} ->
filter(NewNext, Prev, P);
ready ->
% Relay the ready signal on toward the generator.
send(Prev, ready),
filter(Next, Prev, P)
end.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.