Skip to content

Instantly share code, notes, and snippets.

Last active February 20, 2016 05:03
Show Gist options
  • Save ijt/39a0c22cb369da7c04b6 to your computer and use it in GitHub Desktop.
Save ijt/39a0c22cb369da7c04b6 to your computer and use it in GitHub Desktop.
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.
%% Translated by Issac Trotts (2016)
%% with help from Amiramix on StackOverflow.
main(_) ->
Self = self(),
GenPid = spawn(fun() -> generate(Self, 2) end),
%% 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),
{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}),
send(Receiver, Msg) ->
Receiver ! Msg.
%% Send the sequence of integers starting at N to the process Next.
generate(Next, N) ->
ready ->
send(Next, {number, N, self()}),
generate(Next, N+1);
{new_next, NewNext} ->
generate(NewNext, N)
%% 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) ->
{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()})
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment