Lambda the Ultimate

There does seem to be a shortage of illustrative practical examples of the pi-calculus (although I haven't read Milner's book - perhaps there's more there). I've seen a few small examples associated with the Nomadic Pict project, but nothing I'd consider comparable to the classic CSP examples. Maybe if I get some time I'll take a page out of Chris Rathman's book, and try tackling a translation of Hoare's introductory examples into the pi-calculus (although that obviously wouldn't take full advantage of the mobile parts of the pi-calculus).

I don't like the Dining Philosophers or Santa Claus problems. They're not at all representative of the problems that I encounter when writing concurrent programs in a structured way. I suggest we ignore these tricky algorithms and instead learn from Hoare and Brinch-Hansen how to write simple programs that don't need them.

Having said that, I am a sucker for a code snippet, so I've written some interpretations of the Santa Claus problem. The first is a Lisp program that simulates the reindeer and elf processes in order to boil the scheduler down to its essense:

(defun run ()
  (loop (let-helpers-return)
        (schedule-activities)))

(defvar *reindeer* 0 "The number of reindeer waiting for Santa.")
(defvar *elves*    0 "The number of elves waiting for Santa.")

(defun let-helpers-return ()
  (setf *reindeer* (max *reindeer* (random 10)))
  (setf *elves*    (max *elves* (random 11))))

(defun schedule-activities ()
  (cond ((= *reindeer* 9)
         (print 'deliver-presents)
         (setf *reindeer* 0))
        ((>= *elves* 3)
         (print 'make-toys)
         (decf *elves* 3))))

here I find it interesting to consider the least complexity I'd have to add in order to make this truly concurrent. select() anyone?

The second is a port to Erlang that represents each actor as a process:

-module(santa).
-compile(export_all).
-import(lists, [foreach/2]).

%%
%% setup & initialization
run() ->
    Santa = spawn_link(fun() -> santa([], []) end),
    spawn_n(fun() -> random_seed(), reindeer_loop(Santa) end, 9),
    spawn_n(fun() -> random_seed(), elf_loop(Santa)      end, 10).

spawn_n(F, 0) -> ok;
spawn_n(F, N) -> spawn_link(F), spawn_n(F, N-1).

random_seed() -> {A,B,C} = now(), random:seed(A, B, C).

%%
%% The santa process
santa(Rs, Es) ->
    if length(Rs) == 9 ->
	    io:format("deliver presents~n"),
	    broadcast(Rs, take_holiday),
	    santa([], Es);
       length(Es) >= 3 ->
	    io:format("make toys~n"),
	    [A,B,C|Es1] = Es,
	    broadcast([A,B,C], take_holiday),
	    santa(Rs, Es1);
       true ->
	    receive
		{reindeer_ready, R} -> collect_events([R|Rs], Es);
		{elf_ready, E}      -> collect_events(Rs, [E|Es])
	    end
    end.

broadcast(Ps, M) -> foreach(fun(P) -> P ! M end, Ps).

%% Collect all messages that are already waiting
collect_events(Rs, Es) ->
    receive
	{reindeer_ready, R} -> collect_events([R|Rs], Es);
	{elf_ready, E}      -> collect_events(Rs, [E|Es])
    after 0 -> santa(Rs, Es)
    end.

%%
%% The reindeer and elf processes
reindeer_loop(Santa) ->
    holiday(),
    Santa ! {reindeer_ready, self()},
    receive take_holiday -> reindeer_loop(Santa) end.

elf_loop(Santa) ->
    holiday(),
    Santa ! {elf_ready, self()},
    receive take_holiday -> elf_loop(Santa) end.

holiday() ->
    Time = random:uniform(1000),
    receive after Time -> ok end.

I'm not sure if I should have included some more artificial concepts (elf-groups, door-openings, etc) so perhaps this is not a faithful implementation. I also don't know how the code compares with other authors since they don't seem to have included complete source listings...