Elements of Interaction

Robin Milner's 1991 Turing Award Lecture describing CCS (Calculus for Communicating Systems) and pi-calculus.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Illustrative examples

I'd like to see some illustrative examples of CCS, pi-calclus, and join-calclus. I've read a little about each of them but I don't have any intuition for how to model systems with them, and without an elementary mental model I've been unable to appreciate e.g. JoCaml example programs.

I found the basic CSP examples extremely helpful, like the vending machine that dispenses one chocolate for each coin inserted:

VMS = coin -> choc -> VMS

or the machine that dispenses either a chocolate or a toffee for each coin inserted:

VMCT = coin -> (choc -> VMCT | toffee -> VMCT)

.. and now I have to stop myself from quoting all of the examples of CSP chapter 1. I've mentioned how much I love that book, right? :-)

That'd be nice

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).

Polyphonic C#/C-omega

For a practically looking example in join calculus I would suggest Santa Claus in Polyphonic C#.
While it's not exactly written in join calculus itself, the ideas are directly mappable.


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)

(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:

-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 ->
		{reindeer_ready, R} -> collect_events([R|Rs], Es);
		{elf_ready, E}      -> collect_events(Rs, [E|Es])

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

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

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

elf_loop(Santa) ->
    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...