Relation to Pi Calculus

[Roger Price]

David Van Horn wrote [1]

> I've heard that Erlang is essentially an implementation of the untyped
> pi calculus.  Is this a fair characterization?  Which variant of the pi
> calculus most closely resembles Erlang (eg, asynchronous pi, distributed
> pi, seal, join, etc.)?  Could someone provide examples of Erlang
> primitives that closely rememble the pi calculus primitives: input,
> output, and restriction?

Sorry for the much delayed comment - Richard Carlsson has already
explained [2] that Erlang is a lot larger than the pi calculus. Although
Erlang is not in itself an implementation of an untyped pi calculus, I
have found that it is a excellent vehicle for implementing emulators of pi
calculi "hardware".

I implemented a subset of Pierce and Turner's Pict [3] using the
equivalences

      Pi calculus   |     Erlang
     ---------------+-------------
    input process   |   explicit fun
    output process  |   argument to function
       path         |   Erlang process

My subset is asynchronous, higher-order, polyadic and concurrent with
automatic compile-time typing à la ML.  It is not deterministic,
polymorphic (except for a few list operations), linear or sequenced. There
is no sub-typing.  Although the implementation is potentially
distributable over more than one processor, I do not do this.

Erlang gives remarkably good performance.  My first implementation was a
denotational semantics based interpreter in SML/NJ at 30 reductions/sec on
a 1GHz Intel PC.  I re-wrote this in John Reppy's Concurrent ML and
achieved 300-500 reductions/sec [4].  I re-wrote again to issue Erlang
source code and achieved 10000 reductions per second for simple programs
such as factorial(n), n=1000.  On a more ambitious program with heavy
animated graphics such as ant raids [5], I get up to 3000 reductions per
second.

Some notes on the emulator:

All Erlang processes run the same program which waits to receive explicit
funs and arguments, and applies them eagerly.  Although there are
typically 2500 Erlang processes active at any one time, the pi calculus
concurrency is often only 20.

I rolled my own garbage collection of no-longer-needed paths.  A path has
an average life of less than one second. Erlang's own garbage collection
seems to thrash on long runs: I fixed this by setting
erlang:system_flag(fullsweep_after,0).

Debugging in the pi calculus is _difficult_.  When 2000 identical Erlang
processes talk themselves in a spaghetti deadlock, you need all the help
you can get. I added a lot of extra code and data structure to help out,
but this slows things down.

I would be very interested to hear of other attempts to use Erlang to
implement pi calculi.

Roger

[1] http://www.erlang.org/ml-archive/erlang-questions/200310/msg00108.html
[2] http://www.erlang.org/ml-archive/erlang-questions/200310/msg00141.html
[3] http://www.cis.upenn.edu/~bcpierce/papers/pict-design.ps
[4] To be fair, Concurrent ML is a _synchronous_ language and the
    additional engineering needed for asynchronous one-way
    communication really slows things down.
[5] "Swarm Intelligence", Eric Bonabeau, Marco Dorigo, Guy Theraulz,
    chapter 2.2.3.