アクターモデルとプロセス計算の歴史

アクターモデルとプロセス計算は、興味深い歴史と共進化を共有しています。

1973年に初めて発表されたアクターモデル^[1]は、並行計算の数学的モデルです。アクターモデルは、「アクター」を並行デジタル計算の普遍的なプリミティブとして扱います。つまり、受信したメッセージに応じて、アクターはローカルな決定を下し、より多くのアクターを作成し、より多くのメッセージを送信し、次に受信したメッセージにどのように応答するかを決定します。

順次プロセスの構成に基づく以前のアプローチとは対照的に、アクター モデルは本質的に並行なモデルとして開発されました。アクター モデルでは、順次性は、アクター モデル理論で説明されているように、並行計算から派生した特殊なケースでした。

ロビン・ミルナーが同年に発表した並行性に関する最初の研究^[2]も、通信プロセスの数学的意味論を、コンピュータとメモリの相互作用を含むさまざまな相互作用エージェントを理解するためのフレームワークとして位置付けている点で注目に値します。モデリングのフレームワークはスコットのドメインモデルに基づいており、シーケンシャルプロセスに基づいていません。彼の研究は、次の点でアクターモデルと異なっていました。

• アクターの数が動的に変化することを可能にするアクターモデルとは対照的に、プロセスの数は固定されています。
• メッセージで渡せる唯一の量は整数と文字列であり、アクターのアドレスをメッセージで渡すことができるアクターモデルとは対照的である。
• プロセスは固定されたトポロジを持ちますが、アクターモデルではトポロジの変更が可能です。
• メッセージの送信と受信の間に無制限の時間が経過する可能性があるアクター モデルとは対照的に、通信は同期的です。
• セマンティクスは、無制限の非決定性を備えたアクター モデルとは異なり、制限付きの非決定性を提供します。ただし、制限付きの非決定性では、サーバーがクライアントへのサービスを保証することは不可能であり、クライアントが飢餓状態になる可能性があります。

ミルナーは後に円周率計算に関する研究でこれらの制限のいくつかを削除しました(下記の「ミルナーら」のセクションを参照)。

1978年にトニー・ホーアが出版したオリジナルのコミュニケーション・シーケンシャル・プロセスは、アクター・モデルとは異なっており、次のように述べている。^[3]

この論文では、入力と出力がプログラミングの基本プリミティブであり、通信する連続プロセスの並列構成が基本的なプログラム構造化方法であることを示唆しています。ダイクストラのガード付きコマンドの開発と組み合わせると、これらの概念は驚くほど多用途になります。これらの使用法は、さまざまな一般的なプログラミング演習のサンプル ソリューションで説明されています。

...

提案された言語で表現されたプログラムは、単一のメイン ストアを持つ従来のマシンと、入出力チャネルで接続されたプロセッサの固定ネットワークの両方で実装可能であることを意図しています (ただし、さまざまなケースではまったく異なる最適化が適切です)。したがって、これはかなり静的な言語です。プログラムのテキストによって、同時に動作するプロセス数の上限が決まります。再帰やプロセス値変数の機能はありません。その他の点でも、この言語は、より斬新な機能の説明に必要な最小限にまで簡素化されています。

...

この論文では、入力、出力、および並行性は、多くのよく知られた、あるいはあまり知られていないプログラミング概念の基礎となるプログラミングの基本要素とみなすべきであると提案しました。しかし、これらの基本要素がプログラミング言語の他の概念を完全に置き換えることができると結論付けるのは不当です。より複雑な構造 (プロシージャやモニターなど) が頻繁に役立ち、その特性がより簡単にも証明可能で、一般的な場合よりも効率的に実装できる場合、プログラミング言語にその構造の特別な表記法を含める強い理由があります。構造をより単純な基礎となる基本要素で定義できるという事実は、その構造を含めることが言語の残りの部分と論理的に一貫していることを保証するのに役立ちます。

1978 年版の CSP は、以下の点でアクター モデルと異なっていました [Clinger 1981]。

• CSP の並行性プリミティブは入力、出力、保護されたコマンド、並列構成でしたが、アクター モデルは非同期の一方向メッセージングに基づいています。
• 実行の基本単位は、基本的に同時実行であるアクター モデルとは対照的に、順次プロセスでした。マルチプロセッサ コンピューターは本質的に同時実行であるため、順次実行には問題があります。
• プロセスには固定された通信トポロジがありましたが、アクターには動的に変化する通信トポロジがありました。固定されたトポロジを持つことは、変化する状況に動的に適応する能力を妨げるため、問題があります。
• プロセスは並列合成を使用して階層的に構造化されましたが、アクターはフューチャーを使用して非階層的な実行を作成できました[Baker and Hewitt 1977]。階層的な並列合成は、作成者よりも長く存続するプロセスを作成する機能を排除するため、問題があります。また、メッセージ パッシングは、アクター モデルで並列性を生成するための基本的なメカニズムです。より多くのメッセージを送信すると、より多くの並列性の可能性が生成されます。
• 通信は同期でしたが、アクター通信は非同期でした。同期通信は、相互作用するプロセスが離れている可能性があるため、問題があります。
• 通信はプロセス間で行われ、アクター モデルでは通信はアクターに対して一方向です。プロセス間の同期通信は、プロセスが複数のプロセスを待機する必要があるため、問題があります。
• データ構造は数値、文字列、配列で構成されていましたが、アクター モデルではデータ構造はアクターでした。データ構造を数値、文字列、配列に制限すると、プログラム可能なデータ構造が禁止されるため、問題があります。
• メッセージには数字と文字列が含まれますが、アクター モデルではメッセージにアクターのアドレスを含めることができます。メッセージでアドレスを許可しないと、既知のプロセスと通信する機能を別のプロセスに提供できないため、通信の柔軟性が損なわれ、問題が生じます。
• CSP のモデルは意図的に制限された非決定性[Francez、Hoare、Lehmann、de Roever 1979] を持ちましたが、Actor モデルは制限のない非決定性を持っていました。Dijkstra [1976] は、制限のない非決定性を持つプログラミング言語は実装できないと Hoare を確信させました。その結果、CSP を使用して実装されたサーバーが複数のクライアントにサービスを提供できることを保証することができませんでした。

チューリング講演^[4]でミルナーは次のように述べています。

さて、純粋なラムダ計算は、項と変数という 2 種類のものだけで構成されています。プロセス計算で同じ経済性を実現できるでしょうか? Carl Hewitt は、Actors モデルで、ずっと以前にこの課題に応えました。彼は、値、値の演算子、プロセスはすべて同じ種類のもの、つまりActorであるべきだと宣言しました。この目標は、表現の同質性と完全性を意味するため、私に強い印象を与えました... しかし、代数計算の観点からこの目標を達成する方法がわかるまでには長い時間がかかりました... したがって、Hewitt の精神に従えば、最初のステップは、項で表されたり名前でアクセスされるすべてのもの (値、レジスタ、演算子、プロセス、オブジェクト) がすべて同じ種類のものであることを要求することです。つまり、すべてプロセスである必要があります。その後、名前によるアクセスを計算の原材料と見なします...

2003 年、ケン・カーンは円周率計算についてのメッセージの中で次のように回想しています。

円周率計算は同期 (ハンドシェイク) 通信に基づいています。約 25 年前、私は Carl Hewitt 氏と Robin Milner 氏 (CCS と円周率計算で有名) と夕食を共にしたのですが、彼らは同期通信プリミティブと非同期通信プリミティブについて議論していました。Carl 氏は郵便局の比喩を使い、Robin 氏は電話を使いました。両者とも、一方が他方で実装可能であることをすぐに認めました。

トニー・ホーア、スティーブン・ブルックス、AW・ロスコーはCSPの理論を開発し、現代形式に洗練させました。^[5] CSPの理論バージョンを開発する際に採用されたアプローチは、ロビン・ミルナーの通信システム計算（CCS）の研究に大きく影響を受けており、その逆も同様です。長年にわたり、CSPとCCSの両方に取り組んでいる研究者の間で多くの実りある意見交換が行われてきました。

ウィル・クリンガー[1981]は、無制限の非決定性を具体化した並行計算のための最初の表示的アクターモデルを開発した。ビル・コーンフェルドとカール・ヒューイット[1981]は、アクターモデルが大規模な並行性を包含できることを示した。アガは、並行計算の基本モデルとしてアクターを開発した。アクターの抽象化と構成の表現、および非同期通信ツリーに基づくアクターの操作的意味論の開発に関する彼の研究は、ミルナーの通信システム計算(CCS)に関する研究に明確に影響を受けた。^[6]そしてクリンガーの研究。

π計算は、ミルナーが上で述べたアクター モデルに部分的にヒントを得たもので、プロセスの動的な作成と、異なるプロセス間での名前の受け渡しを可能にすることで、プロセス計算に動的トポロジーを導入しました。しかし、ミルナーとホーアの目標である代数計算の実現は、アクター モデルからの重大な逸脱を招きました。プロセス計算における通信は、アクター モデルのように直接的ではなく、チャネルを介して間接的に行われます (アクター モデルとプロセス計算を参照)。対照的に、アクター モデルに関する最近の研究 [Hewitt 2006、2007a] では、表示モデルと表現定理に重点が置かれています。

それでも、アクターモデルとプロセス計算の間には興味深い共進化があります。MontanariとTalcott ^[7]は、アクターモデルとπ計算が互いに互換性があるかどうかを議論しました。SangiorgiとWalker ^[要出典]は、制御構造をメッセージ受け渡しのパターンとして扱うアクターの動作^[8]が、π計算を使用してモデル化できることを示しました。

アクター モデル用の代数法則が開発されていますが、シリアライザーに送信されたメッセージの配信を保証するという重要な特性は捉えられていません。たとえば、次のようになります。

• ガスパリとザヴァッタロ^{[9] [10]}
• アガとタティ^[11]

• 指示的意味論の歴史
• アクターモデルの歴史

• エドガー・ダイクストラ。 プログラミングの規律、 プレンティス・ホール、1976年。
• Carl Hewitt他 「アクター誘導とメタ評価」ACM プログラミング言語の原理に関するシンポジウム会議記録、1974 年 1 月。
• カール・ヒューイットら 非再帰制御構造の動作セマンティクス、 Colloque sur la Programmation の議事録、1974 年 4 月。
• Irene Greifと Carl Hewitt。PLANNER のアクターセマンティクス -プログラミング言語の原理に関する ACM シンポジウムの会議記録。1975 年 1 月。
• アイリーン・グレイフ。 並列プロセスの通信の意味論、 MIT EECS 博士論文。1975 年 8 月。
• Carl Hewitt と Henry Baker の「アクターと連続関数」、 プログラミング概念の形式的記述に関する IFIP ワーキング カンファレンスの議事録。1977 年 8 月 1 ～ 5 日。
• Carl Hewitt と Henry Baker による並列プロセスの通信の法則IFIP-77、1977 年 8 月。
• Henry Baker と Carl Hewittプロセスの増分ガベージ コレクション、人工知能プログラミング言語に関するシンポジウムの議事録。SIGPLAN 通知 12、1977 年 8 月。
• 米澤明 「メッセージ パッシング セマンティクスに基づく並列プログラムの仕様と検証手法」 MIT EECS 博士論文。1977 年 12 月。
• ヘンリー・ベイカー.リアルタイム計算のためのアクターシステムMIT EECS 博士論文. 1978 年 1 月.
• George Milne とRobin Milner。 並行プロセスとその構文JACM。1979 年 4 月。
• Nissim Francez、CAR Hoare、Daniel Lehmann、および Willem de Roever。非決定性、並行性、および通信のセマンティクス、 Journal of Computer and System Sciences。1979 年 12 月。
• ナンシー・リンチとマイケル・フィッシャー。 同時計算のセマンティクスにおける分散システムの動作の記述について。Springer-Verlag。1979 年。
• ウィル・クリンガー。 アクターセマンティクスの基礎、MIT 数学博士論文。1981 年 6 月。
• JA Bergstra および JW Klop。同期通信情報および制御のためのプロセス代数。1984 年。
• Eike Best .並行動作: シーケンス、プロセス、公理コンピュータサイエンス講義ノート Vol.197 1984 年。
• ルカ・カルデッリ。 ランデブー通信の実装モデル、 同時実行に関するセミナー。コンピュータサイエンスの講義ノート 197。Springer-Verlag。1985
• Robin Milner、Joachim Parrow、David Walker。 モバイル プロセスの計算、コンピュータ サイエンス学部、エディンバラ。レポート ECS-LFCS-89-85 および ECS-LFCS-89-86。1989 年 6 月。それぞれ 1990 年 9 月と 1990 年 10 月に改訂。
• ロビン・ミルナー。 ポリアディックπ計算: チュートリアル エディンバラ大学。LFCS レポート ECS-LFCS-91-180。1991 年。
• 本田耕平さんと所マリオさん。 非同期通信のためのオブジェクト計算 ECOOP 91。
• Benjamin Pierce、Didier Rémy、David Turner。π 計算に基づく型付き高階プログラミング言語。 型理論とコンピュータシステムへの応用に関するワークショップ。京都大学。1993年7月。
• Cédric Fournet とGeorges Gonthier . 再帰的化学抽象マシンと結合計算POPL 1996.
• セドリック・フルネ、ジョルジュ・ゴンティエ、ジャン＝ジャック・レヴィ、リュック・マランジェ、ディディエ・レミ。モバイル エージェントの微積分 CONCUR 1996。
• ジェラール・ブドル。直接法による円周率計算POPL 1997
• 関口達郎さんと米澤明憲さん。 コード モビリティ FMOODS を使用した微積分 1997。
• Luca Cardelli およびAndrew D. Gordon . モバイル アンビエントソフトウェア サイエンスと計算構造の基礎、Maurice Nivat (編)、Lecture Notes in Computer Science、Vol. 1378、Springer、1998 年。
• ロビン・ミルナー。通信とモバイルシステム：π計算ケンブリッジ大学出版局。1999年。
• JCM Baeten. プロセス代数の簡潔な歴史 理論計算機科学。2005 年。(リンクは 2015_26_5_0004 時点で有効)
• JCM Baeten、T. Basten、MA Reniers。通信プロセスの代数、ケンブリッジ大学出版局。2005年。
• He Jifeng および CAR Hoare。同時実行性の理論のリンク、国連大学国際ソフトウェア技術研究所 UNU-IIST レポート No. 328、2005 年 7 月。
• Luca Aceto および Andrew D. Gordon (編集者)。代数的プロセス計算: 最初の 25 年間とプロセス代数のその後。ベルティノーロ、フォルリ、イタリア、2005 年 8 月 1 ～ 5 日。
• カール・ヒューイット。コミットメントとは何か? 物理的、組織的、社会的 COIN@AAMAS。2006 年 4 月 27 日b。
• Carl Hewitt (2007a) 「コミットメントとは何か? 物理的、組織的、社会的 (改訂版)」 Pablo Noriega 他編。LNAI 4386。Springer-Verlag。2007 年。
• Carl Hewitt (2007b)大規模組織コンピューティングには階層化されていない矛盾とリフレクションが必要COIN@AAMAS'07。