プロセス計算

プロセス計算（プロセスけいさん、英: Process calculus）またはプロセス代数（プロセスだいすう、英: Process algebras）は、計算機科学において並行システムを形式的にモデリングする各種手法の総称。プロセス計算は、独立エージェントやプロセスの集まりにおける相互作用/通信/同期を抽象的に記述するツールである。また、プロセス記述を操作・分析可能にする代数学的規則も提供し、プロセス間の等価性について（双模倣性を使った）形式的推論を可能とする。主な具体例としては、CSP、CCS、ACP がある^[1]。近年ではこれら以外に π計算(英語)、アンビエント計算、PEPA などもある。

基本機能

プロセス計算には非常に様々な手法が存在するが（分子の相互作用の研究に特化し、確率論的振る舞いやタイミング情報を扱うものもある）、全てのプロセス計算に共通する機能もいくつか存在する^[2]。

独立したプロセス間の相互作用を、共有変数の更新ではなく通信（メッセージパッシング）として表現する。
プロセスやシステムの記述に少数のプリミティブとそれらプリミティブを組み合わせた演算子を使う。
プロセス演算子の代数学的規則を定義し、プロセスの表現を方程式を解くように操作可能とする。

プロセスの数学

プロセス計算を定義するには、通信手段を提供することを目的とした「名前（name）」または「通信路（channel）」を始点とする。多くの実装で、通信路内には効率向上のための複雑な構造があるが、理論モデルではそれらは抽象化によって消え去る。名前に加えて、古いプロセスから新たなプロセスを形成する手段が必要である。そして、以下のような演算子が一般に存在する^[3]。

プロセス群の並列合成（parallel composition）
データの送受信にどの通信路を使うかの指定
相互作用の逐次化
相互作用点の隠蔽
再帰またはプロセス複製

並列合成

2つのプロセス ${\mathit {P}}$ と ${\mathit {Q}}$ の並列合成は $P\vert Q$ のように記述され、逐次型計算モデルとプロセス計算の重要な違いとなっている。並列合成は ${\mathit {P}}$ と ${\mathit {Q}}$ における計算を同時並行的かつ独立に進めることを可能にする。しかし同時に相互作用も可能で、同期や ${\mathit {P}}$ から ${\mathit {Q}}$ （あるいは逆）への通信路による情報の受け渡しが可能である。エージェントやプロセスは1度に複数の通信路と接続可能である。

通信路は同期型と非同期型がある。同期通信路の場合、メッセージを送ったエージェントは相手がそのメッセージを受け取るのを待つ。非同期通信路ではそのような同期は不要である。一部のプロセス計算（特にπ計算）では、通信路そのものをメッセージとして（他の）通信路経由で送信することができ、プロセス間の連結トポロジーを変更できる。また一部のプロセス計算では、計算途中に通信路を生成することができる。

通信

相互作用は情報の流れる方向が決まっている場合が多い。すなわち、入力と出力は双対的相互作用プリミティブとして区別される。プロセス計算では一般に入力演算子（例えば $x(v)$ ）と出力演算子（例えば $x\langle y\rangle$ ）を定義して、それらを区別する。これらには相互作用点として名前がつけられ（ここでは ${\mathit {x}}$ ）、双対的相互作用プリミティブとして同期に使われる。

情報を交換するには、出力プロセスから入力プロセスに情報が流れるということになる。出力プリミティブには送信すべきデータを指定する。 $x\langle y\rangle$ の場合、 ${\mathit {y}}$ がそのデータである。同様に入力はデータを受信することを期待し、1つ以上の束縛変数を受信データと置換するためのプレースホルダーとして用いる。 $x(v)$ の場合、 ${\mathit {v}}$ がそれである。一回の相互作用で交換できるデータの種類の選択は、個々のプロセス計算の大きな特徴の1つである。

逐次合成

場合によっては、相互作用を時間的に順番に行いたいことがある。例えば、「まず ${\mathit {x}}$ でデータを受信し、そのデータを ${\mathit {y}}$ に送信する」というようなアルゴリズム記述はよくある。逐次合成（Sequential composition）はそのようなプロセスで使われる。これは他の計算モデルでもよく使われる。プロセス計算では逐次化演算子は一般に入力や出力と結びついていることが多い。例えば、プロセス $x(v)\cdot P$ は、入力を ${\mathit {x}}$ で待ち受ける。そして入力があったときだけプロセス ${\mathit {P}}$ を起動し、その際に受信データは ${\mathit {x}}$ によって識別子 ${\mathit {v}}$ と置換されている。

リダクション意味論

プロセス計算の計算の本質を含む操作的リダクション規則は、並列合成、逐次化、入力、出力のみで与えられる。リダクションの詳細は個々のプロセス計算で異なるが、本質はほぼ同じである。リダクション規則は次の通りである。

x\langle y\rangle \cdot P\;\vert \;x(v)\cdot Q\longrightarrow P\;\vert \;Q[^{y}\!/\!_{v}]

このリダクション規則は次のように解釈される。

プロセス $x\langle y\rangle \cdot P$ はメッセージ ${\mathit {y}}$ を通信路 ${\mathit {x}}$ に送出する。双対的に、プロセス $x(v)\cdot Q$ は通信路 ${\mathit {x}}$ でメッセージを受信する。
メッセージが送信されると $x\langle y\rangle \cdot P$ はプロセス ${\mathit {P}}$ となり、 $x(v)\cdot Q$ はプロセス $Q[^{y}\!/\!_{v}]$ となる。すなわち ${\mathit {Q}}$ におけるプレースホルダー ${\mathit {v}}$ は ${\mathit {x}}$ における受信データ ${\mathit {y}}$ で置換される。

出力操作の継続として ${\mathit {P}}$ ができる範囲は、プロセス計算の特徴に大きく影響する。

隠蔽

プロセスが、ある相互作用点との間に形成できるコネクションの数は制限されない。しかし、相互作用点における干渉は発生しうる。コンパクトで最小なシステムを合成する際、干渉を抑えることは重要である。隠蔽（Hiding）操作はエージェントの合成と並行して、相互作用点間のコネクションの制御を可能にする。隠蔽の表し方は様々である。例えばπ計算では、 ${\mathit {P}}$ における名前 ${\mathit {x}}$ の隠蔽は $(\nu \;x)P$ と表され、CSP では $P\setminus \{x\}$ のように表される。

再帰と複製

ここまで説明した操作は有限の相互作用だけであり、停止しない場合も含む完全な計算を表すには不十分である。再帰（Recursion）操作と複製（Replication）操作は、有限の記述で無限の振る舞いを表せる。再帰は逐次モデルでもよく使われる。複製 $!P$ は、可算無限個のプロセス ${\mathit {P}}$ の並列合成を表すと理解できる。

!P=P\vert !P

Nullプロセス

プロセス計算には一般に相互作用点を持たない Null プロセスも含まれる（ ${\mathit {nil}}$ 、 $0$ 、 ${\mathit {STOP}}$ 、 $\delta$ など様々な表記法がある）。Null プロセスは何もせず、再帰的なプロセス生成の始点（または終点）として使われる。

歴史

20世紀前半、非形式的な概念だった「計算可能関数」を表現する形式手法として、μ再帰関数、チューリングマシン、ラムダ計算などが提案された。これらは相互に変換可能であり、等価であることから、チャーチ＝チューリングのテーゼが提唱された。もう1つの特徴はあまり言及されない。これらはいずれも「逐次的」計算のモデルだったのである。計算機科学の次の段階の発展において、並行性と通信を明確に表現できる計算の記法の確立が必要とされた。そのような状況で生まれたのが、プロセス計算、ペトリネット、アクターモデルなどの並行性モデルである。

プロセス計算の研究は、ロビン・ミルナーが1973年から1980年にかけて行った Calculus of Communicating Systems (CCS) の研究が最初であった。アントニー・ホーアの Communicating Sequential Processes (CSP) は1978年に発表され、そこから1980年代初めにかけて完全なプロセス計算の研究が行われた。CCS と CSP をさらに発展させようという研究も行われた。1982年、Jan Bergstra と Jan Willem Klop は後に Algebra of Communicating Processes (ACP) と呼ばれるものの研究を開始し、「プロセス代数（Process algebra）」という用語を生み出した^[1]。CCS と CSP と ACP がプロセス計算のファミリーを形成し、その後の様々なプロセス計算の源流となっている。

他の並行性モデルとの関係

history monoid は、相互に通信するプロセスの履歴を表現できる汎用的な free object である。その場合、プロセス計算は一定の方式で history monoid 上に課された形式言語である^[要出典]。すなわち、history monoid は同期を含めたイベントの並びだけを記録するが、その際の状態遷移は記録しない。従って、history monoid にとってのプロセス計算は、free monoid にとっての形式言語と同じである（形式言語は、クリーネ閉包で生成可能なアルファベットの有限長文字列の集合の部分集合である）。

ペトリネットやアクターモデルといった他の並行計算モデルとの違いは、通信路を使った通信を行う点である。通信路を含めたのは、それによってある種の代数学的手法が可能になるためであり、それによってプロセスを代数学的に理解しやすくなっている。

脚注

^ ^a ^b J.C.M. Baeten: A brief history of process algebra, Rapport CSR 04-02, Vakgroep Informatica, Technische Universiteit Eindhoven, 2004年
^ Benjamin Pierce: “Foundational Calculi for Programming Languages”, The Computer Science and Engineering Handbook, pp. 2190-2207, CRC Press, ISBN 0-8493-2909-4.
^ Baeten, J.C.M.; Bravetti, M. (August 2005). "A Generic Process Algebra". Algebraic Process Calculi: The First Twenty Five Years and Beyond (BRICS Notes Series NS-05-3). Bertinoro, Forl`ı, Italy: BRICS, Department of Computer Science, University of Aarhus.

参考文献

Matthew Hennessy: Algebraic Theory of Processes, The MIT Press, ISBN 0-262-08171-7.
C. A. R. Hoare: Communicating Sequential Processes, Prentice Hall, ISBN 0-13-153289-8.
- 同書は Jim Davis（Oxford University Computing Laboratory）が改訂しており、Using CSP というサイトからPDFファイルをダウンロード可能。
Robin Milner: A Calculus of Communicating Systems, Springer Verlag, ISBN 0-387-10235-3.
Robin Milner: Communicating and Mobile Systems: the Pi-Calculus, Springer Verlag, ISBN 0-521-65869-1.

[baeten2004-1] J.C.M. Baeten: A brief history of process algebra, Rapport CSR 04-02, Vakgroep Informatica, Technische Universiteit Eindhoven, 2004年

[2] Benjamin Pierce: “Foundational Calculi for Programming Languages”, The Computer Science and Engineering Handbook, pp. 2190-2207, CRC Press, ISBN 0-8493-2909-4.

[3] Baeten, J.C.M.; Bravetti, M. (August 2005). "A Generic Process Algebra". Algebraic Process Calculi: The First Twenty Five Years and Beyond (BRICS Notes Series NS-05-3). Bertinoro, Forl`ı, Italy: BRICS, Department of Computer Science, University of Aarhus.

[1]

[2]

[3]