アクターモデルの歴史

コンピュータサイエンスにおいて、アクターモデルは1973 年に初めて公開された並行計算の数学的モデルです。

アクター モデルを定義する際の基本的な課題は、グローバル状態が提供されなかったため、これまでのすべての計算モデルで行われていたように、計算ステップを 1 つのグローバル状態から次のグローバル状態に移行するものとして定義できなかったことです。

1963 年、人工知能の分野で、ジョン マッカーシーは状況計算の論理に状況変数を導入しました。マッカーシーとヘイズ (1969) は、状況は「ある瞬間における宇宙の完全な状態」と定義しています。この点で、マッカーシーの状況はグローバル状態を持たないため、アクター モデルでの使用には適していません。

アクターの定義から、ローカルな決定、アクターの作成、メッセージの送信、メッセージの受信、次に受信したメッセージへの応答方法の指定など、多数のイベントが発生することがわかります。このようなイベントの部分的な順序付けは、アクター モデルで公理化されており、物理学との関係が調査されています (アクター モデル理論を参照)。

Hewitt (2006) によると、アクター モデルは、数学的論理、集合論、代数などに基づいた他の計算モデルとは対照的に、物理学に基づいています。物理学、特に量子物理学と相対論的物理学は、さまざまな方法でアクター モデルに影響を与えました。1 つの問題は、アクター システムについて何が観察できるかということです。この質問には、量子物理学の基礎を構築する際に発生したものと同様の理論的および観察的課題を提起するため、明確な答えはありません。アクター システムについて具体的に言うと、通常、アクターへのメッセージの到着順序が決定される詳細を観察することはできません (同時計算における不確定性を参照)。これを行おうとすると、結果に影響し、不確定性を他の場所に押しやる可能性さえあります。たとえば、電子機器における準安定性を参照してください。アクター計算の調停プロセスの内部を観察する代わりに、結果を待ちます。

アクター モデルは、以前の計算モデルに基づいて構築されます。

Alonzo Churchのラムダ計算は、最も初期のメッセージ パッシングプログラミング言語と見なすことができます(Hewitt、Bishop、および Steiger 1973、Abelson および Sussman 1985を参照)。たとえば、以下のラムダ式は、leftSubTreeおよびrightSubTreeのパラメータが指定されている場合、ツリー データ構造を実装します。このようなツリーにパラメータ メッセージ"getLeft"が指定されると、leftSubTreeが返され、同様にメッセージ"getRight"が指定されると、 rightSubTreeが返されます。

λ(左サブツリー、右サブツリー)
   λ(メッセージ)
     メッセージ == "getLeft"の場合、 leftSubTree
      、メッセージ == "getRight"の場合、 rightSubTree

しかし、ラムダ計算のセマンティクスは、呼び出されたラムダ式の本体にパラメータの値を代入する変数代入を使用して表現されていました。代入モデルは、変化するリソースの共有機能を許可しないため、並行性には適していません。ラムダ計算に触発されて、プログラミング言語Lispのインタープリタは、環境と呼ばれるデータ構造を使用して、呼び出されたラムダ式の本体にパラメータの値を代入する必要がないようにしました。これにより、共有データ構造の更新の影響を共有できるようになりましたが、並行性は提供されませんでした。

Simula 67 は、離散イベント シミュレーション アプリケーションに触発されて、計算にメッセージ パッシングを使用する先駆者となりました。これらのアプリケーションは、以前のシミュレーション言語では大規模でモジュール化されていませんでした。各時間ステップで、大規模な中央プログラムは、そのステップで対話したシミュレーション オブジェクトの状態に応じて変化する各シミュレーション オブジェクトの状態を調べて更新する必要がありました。Kristen NygaardとOle-Johan Dahlは、各オブジェクトにメソッドを持たせ、他のオブジェクトからのメッセージに基づいてそのオブジェクトのローカル状態を更新するというアイデアを開発しました (1967 年の IFIP ワークショップで初めて説明されました) 。さらに、継承を持つオブジェクトのクラス構造も導入しました。彼らの革新により、プログラムのモジュール性が大幅に向上しました。

しかし、Simula は真の並行性ではなくコルーチン制御構造を使用しました。

Alan Kay は、Smalltalk -71 の開発において、Plannerのパターン指向呼び出しにおけるメッセージ パッシングの影響を受けていました。Hewitt は Smalltalk-71 に興味を持ちましたが、 global、sender、received、reply-style、status、reply、operator selectorなど、多くのフィールドを使用した呼び出しを含む通信の複雑さにうんざりしていました。

1972 年にケイは MIT を訪れ、シーモア・パパートのLogo研究と、子供にプログラミングを教えるために使われる「小人」計算モデルを基にした Smalltalk-72 のアイデアについて話し合いました。しかし、Smalltalk-72 のメッセージ パッシングは非常に複雑でした。言語のコードは、インタープリタからは単なるトークンのストリームとして認識されていました。ダン・インガルスは後に次のように説明しています。

プログラム内で最初に遭遇したトークンは、動的コンテキストで検索され、後続のメッセージの受信者が決定されます。名前の検索は、現在のアクティベーションのクラス ディクショナリから開始されます。そこで失敗すると、そのアクティベーションの送信者に移動し、送信者チェーンを上っていきます。トークンのバインディングが最終的に見つかると、その値が新しいメッセージの受信者になり、インタープリタはそのオブジェクトのクラスのコードをアクティブ化します。

そのため、Smalltalk-72 のメッセージ パッシング モデルは、特定のマシン モデルとプログラミング言語の構文に密接に結びついており、並行処理には適していませんでした。また、システムは自己ブートストラップされていましたが、言語構造はEvalメッセージに応答するオブジェクトとして正式に定義されていませんでした (以下の説明を参照)。このため、メッセージ パッシングに基づく並行計算の新しい数学モデルは Smalltalk-72 よりも単純なはずだと考える人もいました。

Smalltalk 言語のその後のバージョンは、主にプログラムのメッセージ パッシング構造で Simula の仮想メソッドを使用するという道をたどりました。しかし、Smalltalk-72 は整数、浮動小数点数などのプリミティブをオブジェクトにしました。Simula の作者は、そのようなプリミティブをオブジェクトにすることを検討しましたが、主に効率上の理由で控えました。Java は最初、整数、浮動小数点数などのプリミティブ バージョンとオブジェクト バージョンの両方を持つという方法を使用しました。C #プログラミング言語(および Java 1.5 以降の Java のバージョン) は、ボクシングとアンボクシングを使用するという、それほどエレガントではないソリューションを採用しました。これは、以前に一部のLisp実装 で使用されていたバリエーションです。

Smalltalk システムは、ビットマップ ディスプレイ、パーソナル コンピューティング、クラス ブラウザー インターフェイスなど、さまざまな点で革新をもたらし、大きな影響力を持つようになりました。詳細については、Kay のThe Early History of Smalltalkを参照してください。^[1] 一方、MIT での Actor の取り組みは、より高レベルの並行性の科学とエンジニアリングの開発に重点を置き続けました。(Smalltalk の後のバージョンにいくつかの種類の Actor 並行性を組み込む方法について、後に開発されたアイデアについては、Jean-Pierre Briot の論文を参照してください。)

アクター モデルが開発される前は、非決定論的計算をモデル化するためにペトリ ネットが広く使用されていました。しかし、ペトリ ネットには重要な制限があることが広く認識されていました。それは、制御フローはモデル化できますが、データ フローはモデル化できないことです。そのため、ペトリ ネットは簡単には構成できず、モジュール性が制限されていました。Hewitt は、ペトリ ネットのもう 1 つの難点である同時動作を指摘しました。 つまり、ペトリ ネットの計算の原子ステップは、トークンが遷移の入力プレースから同時に消え、出力プレースに現れる遷移です。この種の同時性を備えたプリミティブを使用することの物理的根拠は、彼にとって疑問に思えました。これらの明らかな難しさにもかかわらず、ペトリ ネットは並行性をモデル化する一般的なアプローチであり続け、現在でも活発に研究されています。

アクター モデル以前は、同時実行はスレッド、ロック、バッファ(チャネル) という低レベルのマシン用語で定義されていました。アクター モデルの実装では、通常、これらのハードウェア機能が使用されます。ただし、ハードウェア スレッドやロックを公開せずに、モデルをハードウェアに直接実装できない理由はありません。また、計算に関係するアクター、スレッド、ロックの数の間には、必ずしも関係はありません。アクター モデルの実装では、アクターの法則に準拠する限り、スレッドやロックを自由に使用できます。

アクター モデルを定義する際の重要な課題は、実装の詳細を抽象化することでした。

たとえば、次の質問について考えてみましょう。「各アクターには、アクターが受信して処理するまで通信が格納されるキューがありますか?」 Carl Hewitt は、このようなキューをアクター モデルの不可欠な部分として含めることに反対しました。1 つの考慮事項は、このようなキュー自体を、メッセージを受信して​​通信をキューに入れたりキューから出したりするアクターとしてモデル化できるというものでした。もう 1 つの考慮事項は、一部のアクターは実際の実装でこのようなキューを使用しないというものでした。たとえば、アクターは代わりにアービターのネットワークを持つ場合があります。もちろん、アクターが受信した通信のシーケンスという数学的な抽象化は存在します。しかし、このシーケンスは、アクターが動作しているときにのみ現れます。実際、このシーケンスの順序は不確定になる可能性があります (同時計算における不確定性を参照)。

実装の詳細を抽象化する別の例として、解釈の問題があります。「解釈はアクター モデルの不可欠な部分であるべきでしょうか?」解釈の考え方は、アクターは、そのプログラム スクリプトがevalメッセージを処理する方法によって定義されるというものです。(このように、アクターは、Lisp で記述されたevalというメタ循環インタープリタ プロシージャによって「定義」されたLispに類似した方法で定義されます。) Hewitt は、解釈をアクター モデルに不可欠なものにすることに反対しました。1 つの考慮事項は、evalメッセージを処理するために、アクターのプログラム スクリプト自体にプログラム スクリプト (さらに、プログラム スクリプトには ...) があることです。もう 1 つの考慮事項は、一部のアクターは実際の解釈で解釈を使用しないことです。たとえば、アクターはハードウェアで実装される場合があります。もちろん、解釈自体に問題はありません。また、evalメッセージを使用してインタープリタを実装することは、Lisp のモノリシックなインタープリタ アプローチよりもモジュール化され、拡張性があります。

それにもかかわらず、モデルの開発は着実に進みました。1975 年、アイリーン・グライフは博士論文の中で 最初の運用モデルを発表しました。

その後、 Gerald Sussman 氏とGuy Steele 氏はアクターに興味を持ち、 Schemeインタープリターに関する論文を発表し、「『アクター』とラムダ式は実装上同一であることを発見した」と結論付けました。Hewitt 氏によると、ラムダ計算はある種の並列処理を表現できますが、一般的にはアクター モデルで表現される同時実行性は表現できません。一方、アクター モデルはラムダ計算のすべての並列処理を表現できます。

グライフが業務モデルを発表してから 2 年後、カール・ヒューイットとヘンリー・ベイカーが『俳優のための法則』を出版しました。

Hewitt と Baker は、Actor モデルの法則を使用して、関数のように動作するすべての Actor は、Dana Scottによって定義された意味で連続的であることを証明しました(表示的意味論を参照)。

Aki Yonezawa 氏は、Actor の仕様と検証手法を発表しました。Russ Atkinson 氏とCarl Hewitt 氏は、同時実行制御のための共有リソースをカプセル化する効率的なソリューションを提供するシリアライザーの仕様と証明手法に関する論文を発表しました。

最初の Actor の出版から 8 年後、Will Clinger は ( Irene Greif 1975、Gordon Plotkin 1976、Michael Smyth 1978、Henry Baker 1978、Francez、Hoare、Lehmann、de Roever 1979、およびMilneとMilnor 1979 の研究を基に)ドメイン理論を使用して無制限の非決定性を組み込んだ最初の満足のいく数学的表示的モデルを1981 年の博士論文で発表しました ( Clinger のモデルを参照)。その後、Hewitt [2006] は到着時間で図を拡張し、技術的に単純で理解しやすい表示的モデルを構築しました。表示的意味論の歴史を参照。

• アクターモデルとプロセス計算の歴史
• 指示的意味論の歴史
• 俳優モデル中史
• 俳優モデルその後の歴史

• カール・ヒューイット、ピーター・ビショップ、リチャード・シュタイガー (1973)。「人工知能のためのユニバーサル・モジュラー・アクター形式」IJCAI: 235–245。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
• マッカーシー、ジョン (1963)。「状況、行動、因果律」。技術レポートメモ(2)。スタンフォード大学人工知能研究所。
• マッカーシー、ジョン、ヘイズ、パトリック (1969)。「人工知能の観点から見たいくつかの哲学的問題」。機械知能(4)。エダンバラ大学出版局: 463–502。CiteSeerX  10.1.1.85.5082。
• ハイゼンベルク、ヴェルナー (1971)。物理学とその先：出会いと対話。AJ ポメランズ訳。ニューヨーク：ハーパー＆ロウ。pp. 63–64。ISBN 978-0061316227。
• Hewitt, Carl; Bishop, Peter; Greif, Irene; Smith, Brian; Matson, Todd; Steiger, Richard (1974 年 1 月)。「アクター誘導とメタ評価」。第1回 ACM SIGACT-SIGPLAN シンポジウム「プログラミング言語の原理」の議事録 - POPL '73。pp. 153–168。CiteSeerX 10.1.1.104.295。doi :  10.1145 /512927.512942。S2CID  33611569。
• カール・ヒューイット（1974年4月）。 「非再帰的制御構造の動作セマンティクス」。Colloque Sur la Programmation の議事録: 385–407。ISBN 9783540068594。
• Greif, Irene; Hewitt , Carl (1975 年 1 月)。「PLANNER-73 のアクター セマンティクス」。プログラミング言語の原理に関する第 2 回 ACM SIGACT-SIGPLAN シンポジウム議事録 - POPL '75。pp. 67–77。doi :10.1145/512976.512984。S2CID 18178340  。
• Hewitt, Carl (1975 年 9 月)。「知っていることの活用方法」。人工知能に関する第 4 回国際合同会議の議事録。1 : 189–198。
• グライフ、アイリーン (1975)。並行言語コミュニケーションの意味論(Ph.D.)。MIT EECS。
• Baker, Henry; Hewitt, Carl (1977年8 月)。「プロセスの増分ガベージ コレクション」。人工知能プログラミング言語シンポジウムの議事録: 55–59。doi :10.1145/800228.806932。hdl :  1721.1 / 41969。S2CID 1557419。^{[永久リンク切れ‍ ]}
• Hewitt, Carl; Baker, Henry (1977 年 8 月)。「並列プロセスの通信に関する法則」。国際情報処理連盟。HDL : 1721.1 /41962。
• 米沢 亜紀 (1977).メッセージパッシングセマンティクスに基づく並列プログラムの仕様と検証技術(Ph.D.). MIT EECS .
• ビショップ、ピーター (1977)。『非常に大きなアドレス空間を持つモジュール式拡張コンピュータ システム』 (Ph.D.)。MIT EECS。
• Hewitt, Carl (1977年6月). 「制御構造をメッセージ通過パターンとして見る」. Journal of Artificial Intelligence . 8 (3): 323–364. doi :10.1016/0004-3702(77)90033-9. hdl : 1721.1/6272 .
• ベイカー、ヘンリー (1978)。リアルタイム計算のためのアクターシステム(Ph.D.)。MIT EECS。
• Hewitt, Carl; Atkinson, Russ (1979 年 1 月)。「シリアライザーの仕様と証明手法」。IEEE Transactions on Software Engineering : 10–23。doi : 10.1109 /TSE.1979.234149。hdl : 1721.1/ 5756。S2CID 15272353  。
• カーン、ケン (1979)。アニメーションの計算理論(Ph.D.)。MIT EECS。
• Hewitt, Carl、Attardi, Beppe、Lieberman, Henry (1979 年 10 月)。「メッセージ パッシングにおける委任」。第 1 回国際分散システム会議の議事録。アラバマ州ハンツビル。
• アトキンソン、ラス (1980)。シリアライザーの自動検証(Ph.D.)。MIT。
• Kornfeld, Bill; Hewitt, Carl (1981 年 1月)。「科学コミュニティのメタファー」(PDF)  。IEEE Transactions on Systems, Man, and Cyber​​netics。11 : 24–33。doi : 10.1109 /TSMC.1981.4308575。hdl : 1721.1/5693。S2CID 1322857。
• リーバーマン、ヘンリー (1981 年 5 月)。「混乱せずに一度に多くのことを考える: 第 1 幕の並列処理」。MIT AI メモ(626) 。hdl :1721.1/6351。
• リーバーマン、ヘンリー (1981 年 6 月)。「第 1 幕のプレビュー」。MIT AI メモ(625) 。hdl :1721.1/6350。
• バーバー、ジェリー (1981)。知識オフィスシステムにおける変化についての推論(Ph.D.)。MIT EECS。
• コーンフェルド、ビル (1981)。問題解決における並列性(Ph.D.)。MIT EECS。
• Clinger, Will (1981).アクター意味論の基礎(Ph.D.). MIT 数学.
• Theriault, Daniel (1982 年 4 月)。「Act-1 言語入門」。MIT AI メモ(672) 。hdl :1721.1/5675。
• Lieberman, Henry; Hewitt, Carl (1983年6 月)。「オブジェクトのライフタイムに基づくリアルタイム ガベージ コレクター」。Communications of the ACM。26 ( 6): 419。CiteSeerX 10.1.1.123.5055。doi : 10.1145 /358141.358147。S2CID 14161480  。 
• Theriault, Daniel (1983 年 6 月)。「Act 2 の設計と実装に関する問題」。MIT AI 技術レポート(728) 。hdl :1721.1/6940。
• リーバーマン、ヘンリー (1983 年 8 月)。「養蜂場のオブジェクト指向シミュレータ」(PDF)。アメリカ人工知能協会会議。ワシントン DC
• Hewitt, Carl; de Jong, Peter ( 1983 年 8 月)。「オープン システムにおける記述とアクションの役割の分析」。人工知能に関する全国会議の議事録。hdl :1721.1/5649。
• Jammer, M. (1985)。「EPR 問題の歴史的発展」。P. Lahti、P. Mittelstaedt (編)。現代物理学の基礎に関するシンポジウム: アインシュタイン-ポドルスキー-ローゼン理論実験の 50 年。シンガポール: World Scientific。pp. 129–149。
• ファイン、A. (1986)。『不安定なゲーム：アインシュタインの実在論と量子論』シカゴ：シカゴ大学出版局。ISBN 978-0226249476。
• Hewitt, Carl; Lieberman, Henry (1983 年 11 月)。「人工知能のための並列アーキテクチャの設計上の問題」。MIT AI メモ(750) 。hdl :1721.1/5653。
• フックス、クリストファー (2002)。「量子情報としての量子力学 (そしてもう少しだけ)」。A. クレニコフ (編)。量子理論: 基礎の再構築。ベクショー: ベクショー大学出版局。
• Hewitt, Carl (2006 年 4 月 27 日)。「コミットメントとは何か? 物理的、組織的、社会的」(PDF)。COIN @AAMAS。