並行プログラミング入門 ―Rust、C、アセンブリによる実装からのアプローチ

8章8章　並行計算モデル

　我々は、「1章　並行性と並列性」にて並行性について定義を与えたが、ここで行った定義はきわめて抽象度の高い定義であり、実際、どのように並行に計算が実行されていくかについてまでは明確に定義していない。そこで本章では、代表的な2つの並行計算モデルを提示し、並行処理についての形式的な定義を示す。形式的とはつまり、三者三様に解釈されるのではなく、誰が読んでも同一の意味と捉えられるような定義の方法である。

　本章で提示する並行計算モデルは、アクターモデル（actor model）、π計算（π-calculus）の2つである。π計算は、プロセス間のデータ交換にチャネルという通信路を用いて行う並行計算方式である。一方、アクターモデルではチャネルを用いず、アクター（本書で言うところのプロセス）同士が直接通信を行ってデータを交換する方式となる。アクターモデルとπ計算はメッセージの交換を主として計算を進めていくため、共有メモリ方式の並行プログラミングと対比して、メッセージパッシング（message passing）方式と大別されることもある。

　本章では、並行計算モデルを解説する前に、導入としてλ計算（λ-calculus）について説明し、束縛変数と自由変数、α変換、β簡約などについての基礎的な説明を行う。λ計算自体は、並行プログラミングを学ぶ上で本質的に不要かもしれないが、λ計算の持つ形式的な記述能力とその考え方は、並行プログラミングの意味を厳密に捉えるための助けとなるだろう。その後、λ計算をベースとしたアクターモデルについて説明し、最後にπ計算について解説する。

8.1　数学的表記

　並行計算モデルの説明を行う前に、本章で用いる数学的表記の一覧を次の表に列挙する。