Relation to Pi Calculus
Thu Nov 27 23:09:52 CET 2003
David Van Horn wrote 
> 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  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
I implemented a subset of Pierce and Turner's Pict  using the
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 . 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 , I get up to 3000 reductions per
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
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.
 To be fair, Concurrent ML is a _synchronous_ language and the
additional engineering needed for asynchronous one-way
communication really slows things down.
 "Swarm Intelligence", Eric Bonabeau, Marco Dorigo, Guy Theraulz,
More information about the erlang-questions