{"id":385,"date":"2007-04-16T08:05:00","date_gmt":"2007-04-16T08:05:00","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/04\/16\/back-to-calculus-a-better-introduction\/"},"modified":"2007-04-16T08:05:00","modified_gmt":"2007-04-16T08:05:00","slug":"back-to-calculus-a-better-introduction","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/04\/16\/back-to-calculus-a-better-introduction\/","title":{"rendered":"Back to π-Calculus: a better introduction"},"content":{"rendered":"

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. <\/p>\n

I’ll start with a basic refresher of what π-calculus is for, and a bit of history for where it came from.<\/p>\n

<\/p>\n

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 computing systems that most of us are familiar with. The tools that we use to model conventional computing systems fail to capture many of the relevant properties of computation in a distributed world; and in fact, worse than just not capturing things, they often get things actively wrong.<\/p>\n

So – some people started looking at more useful and\/or realistic ways of describing
\ncommunicating systems – things called process calculi<\/em>. The first major process calculus that I know of that’s still used today is CSP (Communicating Sequential Processes), first described in 1978 by C. A. R. Hoare. CSP became the basis of a
\nsystem called the transputer<\/a>, and its programming language, Occam<\/a>. <\/p>\n

Just two years later, in 1980, Robin Milner proposed something similar
\nto CSP called CCS – the calculus of communicating systems. The CCS had a stronger formal
\nbasis than CSP, and was somewhat more flexible in some ways. It was a very widely respected and widely used tool – in particular, it became the basis of a major tool for the formal description of network communication protocols, called LOTOS<\/a>. But it had one
\nmajor problem: it was limited to static communication structures<\/em>. What that means
\nis that it described communication over a specific, static network of communication
\nchannels. Using the CCS, you could not add channels, remove channels, or rearrange the
\ninterconnections of communication channels in a system.<\/p>\n

The π-calculus is an extension of the CCS that addresses that limitation, by
\nreplacing static communication channels with channel names<\/em>. Instead of using a
\npredefined network of communication channels, the π-calculus introduced the notion of a
\ndynamic system of named channels, and communication instructions in the π-calculus work
\nin terms of channel names<\/em>, not specific channels. Channel names can be created
\ndynamically, assigned to variables, and passed in messages. With the addition of channel
\nnames, π-calculus could be used to describe many more kinds of communicating systems
\nmuch more easily than could be done in the systems that preceded it.<\/p>\n

So, finally, let’s get down to some syntax. There are only a small number of
\nbasic forms in π-calculus. I’m not going to use Milner’s syntax – it’s too hard to write in HTML. But I’m going to try to be more consistent than last time around. A π-calculus expression is called a process<\/em>. Processes are written using the following forms:<\/p>\n

\n
Send Message:<\/b> !name<\/em>(values<\/em>).Process<\/em><\/code><\/dt>\n
If there is a matching receiver waiting, send the values as a message on the channel named by the value of the name<\/em>.<\/dd>\n
Receive Message:<\/b> ?name<\/em>(values<\/em>).Process<\/em><\/code><\/dt>\n
If there is a matching sender, receive the values that it’s sending as a message on the channel named by the value of name<\/em>.<\/dd>\n
Create Name: <\/b> new(vars<\/em>).Process<\/em><\/code><\/dt>\n
Create a new channel set of channel name, and assign them to the variables. The variables names are scoped<\/em> to the rest of the process definition. <\/dd>\n
Parallel Composition: <\/b>Process1<\/sub><\/em> | Process2<\/sub><\/em><\/code><\/dt>\n
Run both Process1<\/sub><\/em> and Process2<\/sub><\/em> at the same
\ntime.<\/dd>\n
Choice Composition:<\/b>Process1<\/sub><\/em> + Process2<\/sub><\/em><\/code><\/dt>\n
Non-deterministically choose to run either<\/em> Process1<\/sub><\/em> or Process2<\/sub><\/em>. <\/dd>\n
Replication:<\/b> *(Process<\/em>)<\/code><\/dt>\n
Spawn as many copies of a process as necessary. “*(P)<\/code>” is equivalent to “P | *(P)<\/code>“. <\/dd>\n
Null<\/b>: ∅<\/code><\/dt>\n
An empty process. The null process is mainly used to express process termination.<\/dd>\n<\/dl>\n

In addition to those basic structures, I’ll also use “{}”s for grouping.<\/p>\n

As usual for a calculus, we also need to look at reduction rules<\/em>, the rules by which steps in a π-calculus process get evaluated. In π-calculus, reduction is written using →: “A” is reducible to “B” in one step is written “A → B”. The reduction rules are:<\/p>\n

    \n
  • The Fundamental Rule:<\/b> ( !x(z).P | ?x(y).Q ) → P|(Q[z\/y])<\/code>. This rule basically says that given a matching pair of message send and message receive in parallel processes, both the send and the receive can be executed in one step, and the values in the message replace the parameters named in the receiver. (Q[z\/y] means “The process Q with every reference to name “z” replaced with a reference to name “y”.)<\/li>\n
  • The Choice Rule:<\/b> If P→Q<\/code>, then (P+R)→Q<\/code>. This one is a little bit tricky. What it says is: if you have a choice between either process P or process R, and there is a one-step reduction of P to Q, then you can choose P, and do that reduction.<\/li>\n
  • The Parallelism Rule:<\/b> If P→Q<\/code>, then (P|R)→(Q|R)<\/code>. All this says is that if there’s two processes running in
    \nparallel, you can do a one-step reduction of one of the parallel processes without
    \naffecting the other.<\/li>\n
  • The Replication Rule<\/b>: If P→Q<\/code>, then *(P)→Q|*(P)<\/code>. This is just a restatement of what I said earlier about the
    \nmeaning of replication.<\/li>\n
  • Name Binding Rule<\/b>: If P→Q<\/code>, then new(x).P→new(x).Q<\/code>. This just says that introducing a new name around
    \na process doesn’t change the reduceability of the processes inside of it.<\/li>\n<\/ul>\n

    For today, we’ll just do one simple example. Suppose that we’ve got a communication channel named “out”, and any message received by “out” is printed to the standard output. Then we can write a hello world process:<\/p>\n

    \nnew(in).( *(?in(x).!out(x).∅)\n| !in(hello).!in(world).∅ )\n<\/pre>\n
     There are two processes composed in parallel. One is a replicated process – so there are conceptually an infinite number of copies of this instantiated. Each instantiated copy receives one message on the channel named “in”, and then sends it to out. The other process in here sends two messages to “in”: “hello”, and “world”.<\/p>\n
     Here’s an exercise for interested readers. What’s wrong with this process?<\/p>\n","protected":false},"excerpt":{"rendered":"
    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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[50],"tags":[],"class_list":["post-385","post","type-post","status-publish","format-standard","hentry","category-pi-calculus"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-6d","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/385","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=385"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/385\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=385"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=385"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=385"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}