The Pi Calculus II
Posted by John Baez
guest post by Mike Stay
John Baez has been struggling to understand the pi calculus — a formalism for modelling concurrency in computer science.
I’m going to try to explain it nice and slowly. I’ll use the “polyadic asynchronous” variant of the pi calculus.
In the pi calculus, there are mailboxes, each with a name like x
. You should think of the name x
like the key to open the mailbox–if you don’t have the key, you can’t deposit or withdraw messages.
Messages consist of tuples of keys: (x, z, x, y)
is a
typical message. I’ll get to how we deposit and withdraw messages
below.
You can get a new box with the operator, but I’ll spell it “new”. So
new (x) { ... }
creates a context in which the box x
can be used.
The simplest thing you can do is make a deposit:
new (x) { Deposit (x) in x. }
This puts a copy of the key for opening x
in the mailbox. But
there’s nobody to withdraw mail, so it’s pretty useless.
I’ve been saying “you”, but really there are lots of things going on
at once, called “processes”. If two things P
and
Q
are happening at the same time, we write P | Q
. So a slightly more useful setup is:
new (x,y) {
Deposit (x) in x. |
Wait until you can withdraw (z) from x,
then deposit (z) in y.
}
Here there are two mailboxes and two processes.
Now it’s time for some rewrite rules. In the example above, the obvious thing to do is let the deposit trigger the withdrawal; this rule is called “synchronization”. It says
Deposit (z1, z2, ..., zn) in x |
Wait until you can withdraw (y1, y2, ..., yn) from x,
then P
⇒
P { with z1, z2, ..., zn replacing y1, y2, ..., yn }
In this case, n
= 1, so the previous setup evolves under synchronization to
new (x, y) {
Deposit (x) in y.
}
A process can do any number of withdrawals, but only one deposit. So the language describing how to construct a term in the pi calculus is
P ::=
Deposit (y1, y2, ..., yn) in x. |
Wait until you can withdraw
(y1, y2, ..., yn) from x, then P |
P | P |
new (x1, x2, ..., xn) { P } |
Replicate P
The last one of these process constructors is involved in a rewrite rule called replication. It says
Replicate P ⇒ (Replicate P) | P
which means that we can repeat this to get arbitrarily many copies of this process.
Now, of course, they had to make it hard to understand or they wouldn’t get published, so they usually use this shorthand (though I won’t here):
“Deposit (y1, y2, ..., yn) in x.
”
becomes
.
“Wait until you can withdraw (y1, y2, ..., yn) from x, then
P
”
becomes .
“new (x1, x2, ..., xn) { P }
”
becomes .
“Replicate P
”
becomes .
The pi calculus is just as powerful as the lambda calculus; in fact, there’s a straightforward translation of lambda calculus into the pi calculus. The first step of the translation is to move to the “name-passing” variant of lambda calculus.
In the lambda calculus, we have three ways to make a term (here I’m ignoring types, but it’s easy to figure out where they should go):
t ::=
x
(a variable, the base case) |
λx. t
(abstraction–the λ should be a lambda) |
t1 t2
(application)
In the name-passing variant, the term constructors look like this:
t ::=
x
(a variable, the base case) |
λx. t
(abstraction) |
t x
(“small” application) |
Let x be t1 in t2
(new name)
Note that we can only apply terms to variables, not to arbitrary
terms. Why might this be useful? Well, imagine if t1
is
some enormous term; it would save a lot of space to use x
as an abbreviation for or reference to t1
. It’s not too
far off to call x
the “address” of t1
. Only
when x
is being applied to some other variable—like in
x y
—do we replace it by t1
.
To translate from the usual lambda calculus into the name-passing variant, we use the first two term constructors as they are. An application
t1 t2
translates to
Let x be t2 in (t1 x).
Next, we apply each term constructor to a dummy name u
:
x u
(λx.t) u
t x u
(Let x be t1 in t2) u
Finally, we do this embedding into pi calculus:
[[ x u ]] = Deposit (u) in x.
[[ (λx.t) u ]] = Wait to withdraw (x, v) from u, then ([[ t v ]])
[[ t x u ]] = new (v) { [[ t v ]] | Deposit (x, u) in v. }
[[ (Let x be t2 in t1) u ]] =
new (x) {
[[ t1 u ]] |
Replicate (Wait to withdraw (v) from x, then [[ t2 v ]])
}
This has a strong resemblance to the continuation passing style transform, also known as the Yoneda embedding.
Re: The Pi Calculus II
Wow — that was ‘nice and slow’? It flew by so fast I wouldn’t even have noticed it, except for the sonic boom and the lingering smell of burnt neurons!
You have to realize that as a mathematical physicist I deal with familiar, comfortable things like Lagrangians and spinors, not mysterious abstractions like ‘mailboxes’ and ‘addresses’. And since I programmed mainly back when I was in high school, using BASIC in a little room with a line printer, all modern pseudocode looks like extraterrestrial graffiti to me.
But I think I’m sort of roughly getting the point, in a vague impressionistic manner… sort of like I how I can see the trees in this picture, upside-down and woozily distorted:
Let me try to think of some questions…
I’m trying to understand this weird ‘’ or ‘
new
’ operator, as in ‘new (x)
’.At first glance
new (x)
looks like a relative of quantifiers I know and love, like or or , but apparently it’s an operator that opens a new ‘mailbox’ named .What’s a ‘mailbox’? It’s a place where you can store and presumably remove ‘messages’, whatever those are. Well, okay: you say a message consists of a tuple of ‘keys’, where a ‘key’ is the name of a mailbox. Suspiciously circular… but not viciously so.
Anyway, here comes my question. You say:
new (x) { Deposit (x) in x. }
puts a copy of the key for opening
x
in the mailbox. It’s a bit weird to put a key for opening a mailbox inside that very same mailbox — especially if it’s locked — but maybe you’re just trying to freak me out with a self-referential example. So my question is: wouldnew (x) { Deposit (y) in x. }
be a legal thing to say?
I guess that
new (x) { Deposit (x) in y. }
would not be legal, since by saying
new (x)
you’ve opened a mailbox calledx
, but not one calledy
.