アクターモデル

アクターモデル（）とは、1973年、カール・ヒューイット、Peter Bishop、Richard Steiger が発表した並行計算の数学的モデルの一種。アクターモデルでは、並行デジタル計算の汎用的基本要素として「アクター」という概念を導入している。アクターモデルは並行性の理論的理解のフレームワークとして使われるほか、並行システムの実装の理論的基礎としても利用されてきた。
歴史.
アクターモデルはそれ以前の計算モデルとは異なり、物理法則を発想の基本としている。他にも、LISP言語、Simula言語、ケーパビリティ・システム、パケット通信、初期のSmalltalkなどの影響を受けている。アクターモデルは「数百・数千のマイクロプロセッサから構成され、個々にローカルメモリを持ち、高性能通信ネットワークで通信を行う並列コンピュータが近い将来登場するとの予測」から開発された。その後、Webサービスやメニイコアアーキテクチャを活用した超並行性にも範囲を広げてきた。
ヒューイットの1973年の論文に続いて、Irene Greif はアクターモデルの操作的意味論を開発した。2年後、Henry Baker とヒューイットはアクターシステムの公理的法則群を発表した。1981年、William Clinger は Power Domains に基づいたアクターモデルの表示的意味論を発表。1985年、Gul Agha は Clinger の意味論に基づいた遷移ベースの意味論モデルを構築した。これらにより、が完成した。
アクターモデルをソフトウェアとして実装する作業は MIT の Message Passing Semantics Group で行われた。また、カリフォルニア工科大学の Chuck Seitz と MIT の Bill Dally に率いられたチームはアクターモデルに基づくメッセージパッシングを使用したコンピュータアーキテクチャを構築した。
日本では、米澤明憲らの研究が有名である。
基本概念.
アクターモデルの基本は「全てのものはアクターである」という哲学である。これはオブジェクト指向プログラミングにおける「全てのものはオブジェクトである」という考え方と似ているが、オブジェクト指向ソフトウェアでは基本的に逐次的に実行するのに対して、アクターモデルでは本質的に並行性を備えている点が異なる。
アクターは並行的に受信するメッセージに対応した以下のような振る舞いを備えた計算実体（Computational Entity）である:
これらの振る舞いには逐次性は前提とされておらず、並列的にこれらを実行する。
他のアクターとの通信は非同期に発生する（すなわち、送信側アクターはメッセージが受信されるのを待たずに次の計算に移行する）。
メッセージを送信する相手のアクターはアドレスによって指定される（これをアクターの「メールアドレス」とも呼ぶ）。結果として、アクターはアドレスのあるアクターとのみ通信可能であり、他のアクターのアドレスは以下のような方法で獲得される:
アクターモデルは、アクター自体およびアクター間の計算の本質的並行性を特徴とし、メッセージ内にアクターのアドレスを含め、相互のやりとりは到着順が保証されない直接的非同期メッセージパッシングのみである。
形式体系.
長年にわたり、アクターモデルを理解するための形式体系が開発されてきた。以下のようなものがある:
アクターモデルのメッセージパッシング機能を完全には形式化していない点でアクターモデルそのものには対応していない形式体系として、以下のようなものがある:
応用.
アクターモデルは、各種並行システムのモデリングや理解のフレームワークとして利用可能である。以下のような例がある:
アクターモデル以前.
アクターモデルは、それ以前の以下のような計算モデルの上に構築された。
メッセージパッシング意味論.
アクターモデルはメッセージパッシングの意味論でもある。
無制限の非決定性に関する議論.
最初の並行プログラムは割り込みハンドラであった。コンピュータは通常処理の最中に外部（キーボード、ネットワークなど）からの情報を受け取る必要が生じた。そこで、情報が到着すると、コンピュータは割り込まれ、割り込みハンドラと呼ばれる特別なコードが呼び出されて情報をバッファに取り込み、逐次的に処理できるようにする。
この並行プログラムは、バッファを使って同期的に通信した逐次プログラムを並列に並べたものであった。共有メモリを伴う並列性は並行性制御という問題を生じた。元々は、これは1つのコンピュータ上の排他制御の一種であると考えられていた。相互排他問題を解決するため、最初にエドガー・ダイクストラがセマフォを開発し、アントニー・ホーア[1974]と Per Brinch Hansen がモニタを開発した。（[Hewitt and Atkinson 1979]、[Atkinson 1980]）。
初期の計算モデル（チューリングマシン、ラムダ計算など）は数学に基づいており、状態によって計算「ステップ」を表現した。各計算ステップは、ある状態から別の状態への遷移である。このような状態遷移的手法は、非決定性のものを含む有限状態機械などのオートマタ理論へと発展していった。非決定性オートマトンには有限の非決定性があり、マシンが初期状態から動作開始したとき常に停止するなら、停止するときの状態数は有限である。
エドガー・ダイクストラは、この非決定的な状態遷移手法の研究を進めた。ダイクストラのモデルでは、逐次命令列の実行に無制限の時間が掛かる可能性があるとしても、状態定義が適切であれば有限の状態数で停止するとされた[Dijkstra 1976]。ヒューイットはこのダイクストラのモデルで提供できなかったサービスの保証をアクターモデルでは提供するとした。
ヒューイットの言うは、並行性の特徴であり、共有リソースの衝突の仲裁の結果として、サービスの遅延が無制限に発生することを意味する（タイムアウトなど、サービスを打ち切る仕様でない場合）。ヒューイットはと呼ばれる計算回路が安定するのにかかる時間に制限はないと主張した。調停回路はコンピュータが外部からの入力（キーボードからの入力、ディスクアクセス、ネットワークからの受信など）をクロックとは非同期的に処理する状況で使われる。そのため、あるメッセージがコンピュータによって受け取られるまでにかかる時間には際限がなく、その間にコンピュータが遷移する状態数にも制限がない。
アクターモデルでは、Will Clinger が領域理論を使った数学的モデルで無制限の非決定性を導入している。アクターモデルには、グローバルな状態という概念はない。
直接通信と非同期性.
アクターモデルではメッセージをバッファに蓄える必要はない。この点はかつての並行計算のモデルとは明確に異なっている。バッファがないという点は当初から誤解されがちで、議論となる問題である。なぜならば、アクターモデルでのメッセージは（IPのパケットのように）単に送られる。受信側と同期的なハンドシェイクをする必要はない。
アドレスを伴うアクター生成は可変なトポロジーを可能にする.
アクターモデルの自然な発展として、メッセージ内のアドレスが含まれるようになった。パケット通信[1961 and 1964]に影響され、ヒューイットは形式が固定されていない通信を使った新たな並行計算のモデルを提案した。例えば、メッセージは空でもよい。もちろん、送信側が受信側に新たなアクセスすべきアドレスを伝えたい場合、通信によってそれが伝えられる。
計算によっては、メッセージを受け取った側からの応答を得たい場合がある。そのためには、"resumption"（再開）と呼ばれる別のアクターのアドレス付きでメッセージを送る（継続またはスタックフレームとも呼ばれる）。受信者は応答メッセージを resumpiton に送信する。
メッセージにアクターのアドレスを含めることによって、アクター間の関係は可変なトポロジーを形成することができる。
本来的な並行性.
逐次的プロセスの合成に基づく従来の手法とは異なり、アクターモデルは並行的なモデルとして開発された。アクターモデルでの逐次性はアクターモデル理論で説明されるように並行計算の特殊ケースである。
メッセージ受信の順番は不同.
アクターモデルで送信された順番にメッセージが受信されるべきだという要求にたいしてヒューイットは反論した。出力の順序付けが必要なら、その機能を持つキューの役割をするアクターを導入すればよい。キュー・アクターは到着したメッセージをFIFO順にキューイングする。そのため、アクター X がアクター Y にメッセージ M1 を送り、X がその後に受け取ったメッセージに対応して新たにメッセージ M2 を Y に送った場合、M1 は M2 より先に Y に到着するとは限らない。
この点でアクターモデルはパケット通信システムを反映している。パケット通信ではパケットが送信順に受信されることを保証していない。受信順を保証しないことで、パケット通信はパケットをバッファリングしたり、様々な経路でパケットを送信したり、パケットを再送したりといった最適化を可能としている。
例えば、アクターはメッセージ処理をパイプライン化できる。つまり、メッセージ M1 を処理するにあたって、アクターは次のメッセージの処理に影響を与えることができ、結果として M1 の処理が完了する前に次のメッセージ M2 の処理を開始できる。これはパイプライン化することもできるというだけであって、必ずそうしなければならないということではない。メッセージをパイプライン化するかどうかはエンジニアリング上のトレードオフの問題である。外部から見てアクターがメッセージ処理をパイプライン化しているかどうか分かるだろうか？ パイプライン化可能なアクターの定義には曖昧さは全くない。もちろん、パイプライン化を不要なところで行う可能性は存在し、その場合の動作は予期しないものとなる。
局所性.
アクターモデルの重要な特徴の1つとして、局所性がある。
局所性とは、メッセージを処理するときにアクターがメッセージを送信できる相手はアドレスを知っているものに限られるということを意味する。
また、複数の位置を同時に変更することがないことも局所性と称する。この点は他の並行性モデルとは異なる。例えばペトリネットモデルではトークンは同時に複数の場所から削除され、別の複数の場所に配置される。
合成性.
合成性（Compositionality）とは、アクターシステム群から大きなシステムを構成できることを意味する。これはモジュール性という観点で重要であり、Gul Agha の学位論文や Gul Agha、Ian Mason、Scott Smith、Carolyn Talcottで展開された。
振る舞い.
「振る舞い; behavior」の導入により、アクターのメッセージ処理を数学的関数として記述できるようになった。振る舞いは並行性における共有を数学的にモデル化する機構を提供する。
数理論理学との関係.
アクターモデルの開発と数理論理学との関係は興味深い。その開発の主要な動機として、Planner言語の開発で生じた制御構造問題を扱い、理解するという目的があった。アクターモデルが定義されたとき、「計算は推論に内包される」という Kowalski の主張に関連するモデルの能力を理解するという重要な目標があったのである。ヒューイットと Agha[1991]は、結果として生まれたシステムにおける計算ステップがその前のステップからの推論（演繹）ではないという意味で、演繹的ではないと指摘した。
マイグレーション.
マイグレーション（Migration）とは、アクターが位置を変更可能であることを意味する。例えば、米澤明憲は学位論文で郵便局をアクターモデルでモデル化した。客をアクターとし、郵便局内で位置を変えながら何らかの処理をして出て行くというものである。マイグレートするアクターは位置アクターを導入することでモデル化できる。位置アクターはアクターのマイグレーションに応じて変化する。しかし、このモデル化は議論を呼び、現在も研究対象となっている。
アクターモデルの重要性.
ハードウェアは各種並行性を取り入れつつある（マルチコアマイクロプロセッサのような局所的並行性、様々なコンピュータネットワークなどの非局所的並行性）。このような並行性は指数関数的に増大しつつある。
カール・ヒューイットよれば、アクターモデルはコンピュータ（および通信）アーキテクチャ、並行プログラミング言語、Webサービスに関する以下のような問題に直面している:
アクターモデルの考え方はマルチエージェントシステムにも見られる。エージェントシステムは多くの場合アクターモデルに何らかの制限を課している点が異なり、自発的で自律的であることが要求される。