Category Archives: Pi Calculus

The Go I Forgot: Concurrency and Go-Routines

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.

Continue reading

Process Declarations in Pica

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 straightforward: a process is defined by a set of externally visible channels; each channel is defined by a type. In a named definition, there are two types of channels to think about. One is a set of channels supplied to the process when it’s created; the other is a set of channels created by the process, but which are ‘exported’: that is, made visible to other processes. The type of a process is a tuple of all of the channels which the process exports the outside world.

Continue reading

Moving on: π-calculus and common programming idioms

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. So that’s what I’m going to do in this post: ramble on a bit about what processes are really going to end up looking like. Just a warning: this post is definitely on the half-baked side – it’s much more of a train-of-thought/brainstorming thing than the things I usually post.

Continue reading

Why am I doing this Pi-Calculus Language Thing?

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?”

Continue reading

Process Equivalence in π-calculus

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 replication of P; it’s a notation for “enough copies of P”. So when you’re done using replicas of P, you can think of !P disappearing.
  • Often in π-calculus, we actually don’t worry about termination of every process. You can think of it in terms of garbage collection: we’re running some group of processes to perform a computation. When they’re done, they terminate. Any process which has no ports that are reachable by any other active process can simply be collected.

The next place to go in our exploration of π-calculus is considering just what it really means for two processes to be equivalent. The fundamental equivalence relation in
π-calculus is called bisimulation. The idea of bisimulation is roughly a kind of observational equivalence: two processes are equivalent under bisimulation if they exhibit the same visible behavior under all tests by an external observer.

Continue reading

Numbers Using Processes and Messages: Part 1, Addition

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.

Continue reading

The π-Calculus Storage Cell

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”?

new(in).{ *(?in(x).!out(x).∅)
| !in(hello).!in(world).∅ }

Continue reading

Back to π-Calculus: a better introduction

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.

Continue reading

More π-Calculus Games

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:

  1. Sequential Composition: Process1.Process2.
  2. Send expressions: !channel(tuple).Process
  3. Receive expressions: ?channel(tuple).Process
  4. New channel expression new(name,...) { Process }
  5. Process duplication expression: *(Process)
  6. Parallel composition: Process1 | Process2.
  7. Choice composition: Process1 + Process2.
  8. Null process:

So, in this syntax, the final version of the storage cell from yesterdays post

NewCell[creator,initval]=new(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])

Now, let’s try to use π-calculus to do something that actually involves real concurrency.

Continue reading

Building Things in π-Calculus: Storage Cells

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.

Continue reading