As a refresher for me, and to give some examples to help you guys understand it, I’m going to go through a couple of examples of interesting things you can build with π-calculus. We’ll start with a simple way of building mutable storage.
Before getting started, I’m going to be annoying and change the syntax a bit. Typeset π-calculus uses a channel name by itself for “receive message on channel”, and the channel name with an overbar for “send message on channel”. In yesterdays post, I used the unmarked channel name for receive, and added a “*” prefix for send. Playing with that, I find it very hard to read. So I’m going to start using a prefix for all uses of channel names: “?” for receive, and “!” for send.
First,we’ll try to build a storage cell. A storage cell is a process that can store a value; and it provides channels that you can use to either receive a copy of its current value, or send it a new value.
Let’s start with a very naive attempt at a cell.
Cell[val]= (νread,write)( !read(val).Cell[val] + ?write(v).Cell[v])
What that says is: “Cell” is a shorthand for a process expression which is parametric in a value, called “$val”. Cell introduces its own read and write channels, and then either allows a client to read (which means cell writes to the channel that others might want to read from), followed by recursively invoking “Cell” on the same value; or it allows a client to update the value by writing a value to its “write” channel (in which case Cell reads from the channel and then recursively invokes cell with the new value.)
So this is a simple updatable storage cell. Almost.
What’s wrong with it? A couple of things about the channel names:
- The (νread,write) creates two channels, local to the Cell process. That
means that no one outside of the cell process can see them! They’re initially scoped
to Cell, and there’s no method inside of Cell to send the channel name outside of its
name-scope. So it’s a storage cell, but no one can ever actually read it or write to it.
- The ν that creates the channel is inside of the part that is invoked
recursively. So each time that “Cell” is invoked, it creates new channel names.
So, how can we fix that? Let’s start by fixing the second problem, and make it always use the same names. We’ll split it into two different definitions: one which creates a new cell (and allocates its channel names), and one which takes the channels that it should use or read and write.
NewCell[val]=(νread,write)Cell[read,write,val] Cell[read,write,val]= !read(val).Cell[read,write,val] + ?write(v).Cell[read,write,v])
Now we’ve got a cell which creates its channels once, and then just keeps reusing the same channels. That’s a good start. Now, the remaining problem is that we don’t have any way to tell a client what the names o the channels are. To fix that, we’ll just add a parameter to
NewCell, which is the name of a channel where we should send the names of the read and write channels.
NewCell[creator,initval]=(νread,write)(Cell[read,write,initval] | !creator(read,write)) Cell[read,write,val]=( !read(val).Cell[read,write,val] + ?write(v).Cell[read,write,v])
So now, we’re in good shape. We can create a storage cell. When we create it, it gets one set of channel names for reading and writing, and it sends those back to whoever created the cell, so that they’ll be able to read from and write to it.
How would we use it? Let’s just throw together a bit of code.
(ν me)( NewCell[me,0] | ?me(r,w).!w(7).?r(x).!out(x) )
This creates a new cell; receives a message from the cell containing its read and write channels; then it sets the cell contents to 7; reads the cell contents into a variable “x”,
and sends the contents it just read to an output channel.