Pi Calculus
goodmath | November 13, 2009 A couple of people pointed out that in my wednesday post about Go, I
completely left out the concurrency stuff! That's what I get for rushing the
post - I managed to leave out one of the most interesting subjects! Go
provides very strong support for communicating processes.
I haven't done a lot of hacking with the concurrency stuff yet - so my
impressions of it are still very preliminary. But my early impressions are
very good.
A lot of people have been talking about Go as a language for distributed
computation. I don't think that's correct: Go programs run in a single, shared
address…
goodmath | May 13, 2007 Sorry for the slow pace of things around here lately; life interferes sometimes. I've mentioned my fathers illness before; things took a drastic change for the worse a week ago, which made things more than a little bit crazy. Of course, life wouldn't be life in things happened one at a time; so naturally, my asthma picked now to act up as well, so I've been coughing my lungs out. It's been a fun week, really.
Anyway, I've been wanting to look a bit more at Pica. I've been thinking about how a
named process definition looks, and what it does. The type part of a definition is
relatively…
goodmath | May 1, 2007 Before diving off into real content, the name of my little π-calculus monstrosity has been chosen. As several people recommended in the comments, I'm going to go with Pica.
So, today, we're going to take the dive, and start looking at some interesting semantics of the language. The goal of this is still to work on Pica's type system: I want
to work towards a first draft of what a process type will look like. But to figure out what a process type should look like, we need to think about how process abstractions will be
defined and used in Pica, what control structures are going to look like…
goodmath | April 29, 2007 Since my post on datatypes for my π-calculus language, I've gotten a bunch of
questions from people who (I guess) picked up on the series after the original post where
I said that the idea of the series was to see if I could create a programming language
based on it. The questions are all variations on "Why design another programming language? Do you really think anyone will ever use it?"
I'll answer the second question first. Of course I realize that the chances that anyone
but me, and maybe a couple of readers, will ever use it are close to zero. But that's not the point.
Which brings us…
goodmath | April 23, 2007 Before moving on, there's one question that I thought was important enough to promote up to the front page, instead of just answering it in the comments. A commenter asked about process replication, !P, wanting to know if it terminates.
The answer comes in two parts.
!P does process creation on demand. It's not an infinite parallel group of processes; it's just a way of writing that there are as many of P as you need. So you can think of it like tape cells in a Turing machine: we never say that a Turing machine tape is infinitely long; but there's always enough cells. !P isn't an infinite…
goodmath | April 18, 2007 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…
goodmath | April 17, 2007 As I did with my first attempt at explaining π-calculus, I think that before getting into any of the deep semantics, it's good to look at a few examples of things you can build with π-calculus. But before getting to the meat of the post, I'll give you the answer the puzzle I left in the last post. What's wrong with the example I gave for "Hello world" yesterday?
As a reminder, the question was: Assume "out" is the name for a channel that is read by a process that prints whatever it receives to the standard output. What's wrong with the following process as an implementation of "Hello World…
goodmath | April 16, 2007 Now that things are settling down a little bit, I wanted to get back to the stuff I was writing about π-calculus. But looking back at what I've already written, I think I did a terrible job of introducing it. So I'm going to start over, and try to be more clear.
I'll start with a basic refresher of what π-calculus is for, and a bit of history for where it came from.
When computer networks first appeared and came into relatively widespread use, one of the problems that smart people recognized quite quickly is that communicating systems are fundamentally different from the kinds of…
goodmath | March 24, 2007 Ok. So I'm still tweaking syntax, to try to find a way of writing π-calculus in a way that's
easy for me to write in my editor, and for you to read in your browser. Here's the latest version:
Sequential Composition: Process1.Process2.
Send expressions: !channel(tuple).Process
Receive expressions: ?channel(tuple).Process
New channel expression new(name,...) { Process }
Process duplication expression: *(Process)
Parallel composition: Process1 | Process2.
Choice composition: Process1 + Process2.
Null process: ∅
So, in this syntax, the final version of the storage cell from yesterdays…
goodmath | March 22, 2007 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…