π-calculus は、80 年代の終わりごろに Milner らによって提案された並行計算のモデルの一つです。そこでは、プロセスと呼ばれる複数の独立した主体が、通信チャネルと呼ばれるデータの通り道を介して値をやりとりしながら、計算を行っていきます。π-calculus にはいろいろな変種があるのですが、ここではとりあえず次のような構成要素からなるものを考えましょう。
たとえば
x![123] | (x?[v] . result![v])だったら、「チャネル x に 123 という整数を送る」というプロセスと「x から値 v を受け取り、それを result というチャネルに送る」というプロセスを並行して実行するという意味です。ですから、これを実行すると x で一回通信が起こって
result![123]という結果が得られます。
π-calculus では、チャネル自体を値として送受信することもできます。たとえば、
(new c . (x![c] | (c?[v] . print![v]))) | (x?[d] . d!["abc"])というプロセスは、「新しいチャネル c を作ってそれを x に送っておき、c から値 v が来たらそれを print に送る」という動作と、「x からチャネル d を受け取って、それに "abc" という文字列を送る」という動作を並行して行います。これを実行すると、まず x で通信が起こって
(c?[v] . print![v]) | c!["abc"]となり、次に c で通信が起こって
print!["abc"]となります。
π-calculus の最大の特徴は、この「チャネル自体も値としてやりとりできる」という点にあります。この考え方をさらに押し進めていくと、実は整数や文字列などの値も、チャネルとその上での通信だけで表せてしまうことが知られています。つまり、λ-calculus ですべてのものがλ式として表されているのと同様に、π-calculus ではすべてのものをプロセスで表す（encode する）ことができるのです。
たとえば bool 値をプロセスで表してみるとどうなるでしょうか。データ型としての bool は、「true」と「false」の二つの定数で構成されます。そこで「true」をあらわすプロセスとしては、二つのチャネル t, f を受け取り、t のほうに空の値を送信する
true?[t,f] . t![]を考えます。「false」をあらわすプロセスとしては、二つのチャネル t, f を受け取り、f のほうに空の値を送信する
false?[t,f] . f![]を考えます。すると、たとえば「if x then P else Q」という条件文は、
new t . new f . (x![t,f] | (t?[] . P) | (f?[] . Q))とあらわせます。もし x が true だったら t のほうに値が送られてくるので P が実行されるし、もし x が false だったら f のほうに値が送られてきて Q が実行されますから、確かにうまく行きそうです。if 文さえあれば and とか or とかの演算を作るのも簡単です。
ただし、このままだとちょっとまずいことが起きます。上のように true や false を定義しても、これらは一回値が来ると消えてなくなってしまいますから、何回も使うためにはそれだけの数のプロセスを用意しておかないといけません。これでは使われる回数があらかじめわからない場合困ってしまいます。そのため、一般的な π-calculus には、replication と呼ばれる無限個の複製を作る operator が存在します。
記号が output と同じ ! なのでちょっと紛らわしいのですが、replication を使えば、先の true と false も
!(true?[t,f] . t![]) | !(false?[t,f] . f![])のように、何度使っても大丈夫なように表すことができます。replication があると、再帰的な計算を行うプロセスも表すことができます。たとえば
!(fact?[n,r] . (if n=0 then r![1] else (new c . (fact![n-1,c] | (c?[x] . r![n * x])))))とか
!(fib?[n,r] . (if n<2 then r![1] else (new c . new d . (fib![n-1,c] | fib![n-2,d] | (c?[x] . d?[y] . r![x+y])))))とかいった感じです。
もちろん = や + などの整数演算は、また別に定義しておかないといけません。余裕のある人は自分で考えてみると良い練習になると思います（実は λ-calculus 全体が π-calculus の上で自然に encode できるので、bool や int が表せるのは当たり前なのですが）。
（以下作成中）