Given a calculus, one of the things that I always want to see is how it can do
some kind of meaningful computation. The easiest way to do that is to start building numbers and basic arithmetic.
To be able to do this, we’re going to need one more bit of
syntax. What we want to do is specify a condition. There is, of course, a way to do
that in π-calculus, but I don’t want to go into detail about how to do that yet. So what I’m going to do is allow, is a message receive operation, to specify a specific value
for the received message; and say that in the reduction rules, a message send will match with a message receive if either the receive uses an unbound variable name,
or the receive specifies a concrete value which is identical to the value in the send:
- Syntax: Our concrete receive will just place the value in quotes:
?in("v"). - Reduction rule:
?a("x").P|!a(y).Q → P|Qif “x”==y.
The way that we do numbers in π-calculus is based on the way that we do numbers in λ-calculus. So we’ll start by reviewing the basics of how we do numbers in λ-calculus: it’s called church numerals.
Church numerals represent numbers are functions with two parameters, “s” and “z”. A number N is a function which applies its “s” parameter to its “z” parameter N times – you can think of it as N copies of “s” followed by one copy of “z”. So:
- 0 ≡
λs z. z - 1 ≡
λs z. s z - 2 ≡
λs z. s (s z) - 3 ≡
λs z. s (s (s z)) - …
So now, we want to translate that basic concept into π-calculus. In λ, the basic single-step operation is function application, and the basic values are all functions. In π-calculus, the basic single-step operation is messaging, and the basic values are all communication channel names. So what we’ll do is translate church numerals into processes. A number N will be a process which sends N “s” messages, followed by one “z” message. We need to add one extra parameter in π-calculus: the place to send the message to
- 0 ≡
?in(t,s,z).!t(z).∅ - 1 ≡
?in(t,s,z).!t(s).!t(z).∅ - 2 ≡
?in(t,s,z).!t(s).!t(s).!t(z).∅ - 3 ≡
?in(t,s,z).!t(s).!t(s).!t(s).!t(z).∅ - …
Now, suppose we want to write an adder. An adder will be a process which takes an input message containing the “in” ports of two numbers X and Y, and then behaves the same as
the process “X + Y”.
The first part is easy: it needs to receive a message containing the in ports of “X” and “Y”:
Adder≡?in(x,y).???
After it gets X and Y, it should look exactly like a number process. Each number process starts by receiving a message on its input channel, which contains a tuple of three values: t, s, and z.
Adder≡?in(x,y).?in(t,s,z).???
Once it’s got its channels, the sum process should send (X+Y) “s”s, followed by one “z” to “t”. The way that we’ll make it to that is to use three parts:
- First, we need to invoke X (that is, send its “(t,s,z)” message to its input channel). But we can’t just have it send its “s” and “z” messages to “t” – because then, it would send “z” after only X “s”s. So we create a new port, “xt”, and invoke x, using the new “xt” in place of t.
- Next, we add a replicated process in parallel, which takes any “s” messages sent to “xt”,
and forwards them to “t”. So now, the two processes together give us a process
which sends X “s” messages to “t”. But after X “s” messages have been sent,
and “X” sends its “z”, that won’t get forwarded: the replicated process will
only forward “s”s. - Finally, we add a process in parallel with the other two which receives a “z” message from “xt”. When it
does, it invokes Y, using “(t,s,z)”. So now, the three processes together
will send X “s”s to “t”; then the “z” on “xt” will cause Y “s”s to be sent to “t”, followed by one “z”. So it sends X+Y “s”s, followed by 1 “z” – which is exactly the behavior of a the process for the number “X+Y”.
So, our completed adder is:
Adder≡?in(x,y).?in(t,s,z).new(xt).{!x(xt,s,z).∅
| *(?xt("s").!t(s).∅)
| ?xt("z").!y(t,s,z).∅ }
An exercise for interested people: try writing multiplication. Since multiplication
is just repeated addition, it shouldn’t be too hard – it’s just re-applying the
same tricks I just showed for addition.
Ok, here goes my suggestion.
Mult = ?in(x,y).?in(t,s,z).new(xt,yt).
{ !x(xt,s,z).0
| *(?xt(“s”).{ !y(yt,s,z)
| *(!yt(“s”).t(s).0)
| ?yt(“z”).0 })
| ?xt(“z”).t(z).0 }
It think it would be more elegant to try to recursively use Adder instead of that inner-cycle for processing Y, but for now I stick to this solution.
The identation got screwed up… 😐
Let me try to make it more easy to read.
Mult = ?in(x,y).?in(t,s,z).new(xt,yt).
{ !x(xt,s,z).0
| *(?xt(“s”).{ !y(yt,s,z)| *(!yt(“s”).t(s).0)| ?yt(“z”).0 })
| ?xt(“z”).t(z).0 }
I’m still not glad with this, because I’m just re-inventing the Adder internaly…
The problem is… how do we “invoke” our functions?
We already know that we can define numbers this way
1 ≡ ?in(t,s,z).!t(s).!t(z).∅
2 ≡ ?in(t,s,z).!t(s).!t(s).!t(z).∅
But we can’t simply do: (Adder|1|2)
I’m a bit confused with that…
I’m curious about your definition of numbers. Somehow it seems more natural to me to send on two channels, rather than sending two values on one channel:
0 = ?in.(s,z,v).!z(v).0
1 = ?in.(s,z,v).!s(v).!z(v).0
2 = ?in.(s,z,v).!s(v).!s(v).!z(v).0
etc.
then addition is a bit simpler:
Adder = ?in(x,y).?in(s,z,v).new(z’).{ !x(s,z’,v) | ?z'(v).!y(s,z,v) }
There is that extraneous v floating around, but that’s not a big deal (especially if we can send a unit value). This way we don’t have to add a receiving pattern match, also.
Clayton:
The problem with using multiple channels is that it’s harder to build processes will well-defined concurrency behavior. We want to be sure that all of the “s” messages are recieved and handled appropriately before the “z” message. The numbers will get simpler with multiple channels, but the processes that use
them will get more complicated.
Okay, this is right where I got lost before, but I think I’m a little bit better this time.
Numbers… still confuse me. I understand perfectly how they are defined, I’m just confused as to how they are used. How do you *invoke* the number 1?
I think my big problem is that you use the ?in channel as a generalized channel name. You’re not actually identifying a channel named in, but a generic channel that receives input. So, in reality it would be something like this:
0=?zero(t,s,v).!t(v).∅
1=?one(t,s,v).!t(s).!t(v).∅
And so on.
So then, to call Adder, you’d do something like:
Adder(one,two).∅
Which would then expand into:
?in(t,s,z).new(xt).{!one(xt,s,z).∅ | *(?xt(“s”).!t(s).∅)
| ?xt(“z”).!two(t,s,z).∅ }
Is this right? Or is there something major I’m missing here?
Also! Correct me if I’m wrong, but it seems like Adder needs some explicit syncing as well. It’s relying on all the replications of the second parallel process ( *(?xt(“s”).!t(s).∅ ) to completely finish before the third parallel process ( ?xt(“z”).!(two(t,s,z).∅ ) finishes.
I don’t think this is guaranteed currently. The syncing seems nontrivial, though. I’ll have to think on it today.
Here’s mine (with no nulls):
Mult=?in(x,y).?in(t,s,z).new(xt, yt).{
!x(xt, s, z) |
*(?xt(“s”).!y(yt, s, z)) |
*(?yt(“s”).!t(s)) |
!t(z)
}
Oops, I forgot to put the z after everything else. It should be }.!t(z) at the end, not |!t(z)} .
And here I am replying to myself again. I realized that I had some assumptions that might not be true. I was just ignoring messages I didn’t care about and using {*(?in(“s”))}.p to get every s before doing p. Do those work?
Anyway, here’s my latest attempt. I’ve tried to deal with the syncing problem that Xanthir brought up by counting the z’s and making sure the last z is accepted after the last s is sent:
Mult=?in(x,y).?in(t,s,z).new(xt, yt, zt).{
!x(xt, s, z).?xt(“z”) |
!x(zt, s, z).?zt(“z”).!t(z) |
*(?xt(“s”).!y(yt, s, z)) |
*(?yt(“s”).!t(s) + ?yt(“z”).?zt(“s”)) |
}
If that’s wrong, I give up (for today).
All right, so I think this will work for Adder. It actually did turn out to be trivial in the end. I’m assuming that the *(P) can eventually eliminate itself.
Adder≡?in(x,y).?in(t,s,z).new(xt).{!x(xt,s,z).∅
| *(?xt(“s”).!t(s)).!sync().∅
| ?sync().!y(t,s,z).∅ }