アクターモデル

アクターモデルとは、1973年、カール・ヒューイット、Peter Bishop、Richard Steiger が発表した並行計算の数学的モデルの一種。アクターモデルでは、並行デジタル計算の汎用的基本要素として「アクター」という概念を導入している。アクターモデルは並行性の理論的理解のフレームワークとして使われるほか、並行システムの実装の理論的基礎としても利用されてきた。

1. 歴史
-----

アクターモデルはそれ以前の計算モデルとは異なり、物理法則を発想の基本としている。他にも、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 に率いられたチームはアクターモデルに基づくメッセージパッシングを使用したコンピュータアーキテクチャを構築した。

日本では、米澤明憲らの研究が有名である。

2. 基本概念
-------

アクターモデルの基本は「全てのものはアクターである」という哲学である。これはオブジェクト指向プログラミングにおける「全てのものはオブジェクトである」という考え方と似ているが、オブジェクト指向ソフトウェアでは基本的に逐次的に実行するのに対して、アクターモデルでは本質的に並行性を備えている点が異なる。

アクターは並行的に受信するメッセージに対応した以下のような振る舞いを備えた計算実体である:

アクターに有限個のメッセージを送信する。
有限個の新たなアクターを生成する。
次に受信するメッセージに対する動作を指定する。これらの振る舞いには逐次性は前提とされておらず、並列的にこれらを実行する。

他のアクターとの通信は非同期に発生する。

メッセージを送信する相手のアクターはアドレスによって指定される。結果として、アクターはアドレスのあるアクターとのみ通信可能であり、他のアクターのアドレスは以下のような方法で獲得される:

受信したメッセージ内にアドレスが書いてある。
そのアクターが何らかの方法で既に相手のアドレスを知っている。
そのアクターは生成したアクターである。アクターモデルは、アクター自体およびアクター間の計算の本質的並行性を特徴とし、メッセージ内にアクターのアドレスを含め、相互のやりとりは到着順が保証されない直接的非同期メッセージパッシングのみである。

3. 形式体系
-------

長年にわたり、アクターモデルを理解するための形式体系が開発されてきた。以下のようなものがある:

アクターシステムの法則
遷移意味論アクターモデルのメッセージパッシング機能を完全には形式化していない点でアクターモデルそのものには対応していない形式体系として、以下のようなものがある:

いくつかのアクター代数系

4. 応用
-----

アクターモデルは、各種並行システムのモデリングや理解のフレームワークとして利用可能である。以下のような例がある:

TTCNはアクターモデルにある程度基づいている。TTCN では、アクターとはテスト部品であり、パラレルテスト部品 と主要テスト部品がある。テスト部品はメッセージを送受信し、通信相手をアドレスで識別する。各テスト部品は固有の動作ツリーを持ち、並行的に動作し、他のテスト部品を動的に生成する。組み込み言語機能により受信したメッセージの種類に対応した動作を記述できる。

5. アクターモデル以前
------------

アクターモデルは、それ以前の以下のような計算モデルの上に構築された。

ラムダ計算計算可能性を論じるときに使われる計算モデルSimula最初のオブジェクト指向言語。ただし、真の並行性はなく、コルーチンを使用している。Smalltalkアラン・ケイはヒューイットのPlannerに影響を受けてSmalltalk-71を考案したが、それとは別にSimulaやLisp、Logoの要素と自分のメッセージパッシングのアイデアを組み合わせたSmalltalk-72をダン・インガルスらとともに開発していた。ヒューイットはAltoで動くSmalltalk-72のデモを見てそのアイデアに興味を引かれたが、メッセージパッシング方式の複雑さは気に入らなかった。メッセージパッシングに基づいた並行計算の数学的モデルはSmalltalk-72よりも単純化すべきであるとの考えが生まれた。なお、Smalltalk-72やそれ以降の-76、-80には、Simulaになかった特徴として、整数などの基本的データ型もメッセージの受け手とした点が挙げられる。ペトリネットアクターモデル以前に広く使われていた並行計算用モデル。しかし、ペトリネットは制御フローはモデル化できるが、データフローをモデル化できないという弱点があった。また、ヒューイットが指摘した問題として、動作の同時性がある。ペトリネットでの不可分な計算ステップはトークンが入力箇所から消え、「同時に」出力箇所に出現することになっている。ヒューイットはこのような特徴を前提としたモデルでは実際の並行システムにそぐわないと考えた。

6. メッセージパッシング意味論
----------------

アクターモデルはメッセージパッシングの意味論でもある。

6.1. 無制限の非決定性に関する議論
-------------------

最初の並行プログラムは割り込みハンドラであった。コンピュータは通常処理の最中に外部からの情報を受け取る必要が生じた。そこで、情報が到着すると、コンピュータは割り込まれ、割り込みハンドラと呼ばれる特別なコードが呼び出されて情報をバッファに取り込み、逐次的に処理できるようにする。

この並行プログラムは、バッファを使って同期的に通信した逐次プログラムを並列に並べたものであった。共有メモリを伴う並列性は並行性制御という問題を生じた。元々は、これは1つのコンピュータ上の排他制御の一種であると考えられていた。相互排他問題を解決するため、最初にエドガー・ダイクストラがセマフォを開発し、アントニー・ホーア[1974]と Per Brinch Hansen がモニタを開発した。。

初期の計算モデルは数学に基づいており、状態によって計算「ステップ」を表現した。各計算ステップは、ある状態から別の状態への遷移である。このような状態遷移的手法は、非決定性のものを含む有限状態機械などのオートマタ理論へと発展していった。非決定性オートマトンには有限の非決定性があり、マシンが初期状態から動作開始したとき常に停止するなら、停止するときの状態数は有限である。

エドガー・ダイクストラは、この非決定的な状態遷移手法の研究を進めた。ダイクストラのモデルでは、逐次命令列の実行に無制限の時間が掛かる可能性があるとしても、状態定義が適切であれば有限の状態数で停止するとされた[Dijkstra 1976]。ヒューイットはこのダイクストラのモデルで提供できなかったサービスの保証をアクターモデルでは提供するとした。

ヒューイットの言う無制限の非決定性は、並行性の特徴であり、共有リソースの衝突の仲裁の結果として、サービスの遅延が無制限に発生することを意味する。ヒューイットは調停回路と呼ばれる計算回路が安定するのにかかる時間に制限はないと主張した。調停回路はコンピュータが外部からの入力をクロックとは非同期的に処理する状況で使われる。そのため、あるメッセージがコンピュータによって受け取られるまでにかかる時間には際限がなく、その間にコンピュータが遷移する状態数にも制限がない。

アクターモデルでは、Will Clinger が領域理論を使った数学的モデルで無制限の非決定性を導入している。アクターモデルには、グローバルな状態という概念はない。

6.2. 直接通信と非同期性
--------------

アクターモデルではメッセージをバッファに蓄える必要はない。この点はかつての並行計算のモデルとは明確に異なっている。バッファがないという点は当初から誤解されがちで、議論となる問題である。なぜならば、アクターモデルでのメッセージは単に送られる。受信側と同期的なハンドシェイクをする必要はない。

6.3. アドレスを伴うアクター生成は可変なトポロジーを可能にする
---------------------------------

アクターモデルの自然な発展として、メッセージ内のアドレスが含まれるようになった。パケット通信[1961 and 1964]に影響され、ヒューイットは形式が固定されていない通信を使った新たな並行計算のモデルを提案した。例えば、メッセージは空でもよい。もちろん、送信側が受信側に新たなアクセスすべきアドレスを伝えたい場合、通信によってそれが伝えられる。

計算によっては、メッセージを受け取った側からの応答を得たい場合がある。そのためには、//resumption//と呼ばれる別のアクターのアドレス付きでメッセージを送る。受信者は応答メッセージを resumpiton に送信する。

メッセージにアクターのアドレスを含めることによって、アクター間の関係は可変なトポロジーを形成することができる。

6.4. 本来的な並行性
------------

逐次的プロセスの合成に基づく従来の手法とは異なり、アクターモデルは並行的なモデルとして開発された。アクターモデルでの逐次性はアクターモデル理論で説明されるように並行計算の特殊ケースである。

6.5. メッセージ受信の順番は不同
------------------

アクターモデルで送信された順番にメッセージが受信されるべきだという要求にたいしてヒューイットは反論した。出力の順序付けが必要なら、その機能を持つキューの役割をするアクターを導入すればよい。キュー・アクターは到着したメッセージをFIFO順にキューイングする。そのため、アクター X がアクター Y にメッセージ M1 を送り、X がその後に受け取ったメッセージに対応して新たにメッセージ M2 を Y に送った場合、M1 は M2 より先に Y に到着するとは限らない。

この点でアクターモデルはパケット通信システムを反映している。パケット通信ではパケットが送信順に受信されることを保証していない。受信順を保証しないことで、パケット通信はパケットをバッファリングしたり、様々な経路でパケットを送信したり、パケットを再送したりといった最適化を可能としている。

例えば、アクターはメッセージ処理をパイプライン化できる。つまり、メッセージ M1 を処理するにあたって、アクターは次のメッセージの処理に影響を与えることができ、結果として M1 の処理が完了する前に次のメッセージ M2 の処理を開始できる。これはパイプライン化することもできるというだけであって、必ずそうしなければならないということではない。メッセージをパイプライン化するかどうかはエンジニアリング上のトレードオフの問題である。外部から見てアクターがメッセージ処理をパイプライン化しているかどうか分かるだろうか？ パイプライン化可能なアクターの定義には曖昧さは全くない。もちろん、パイプライン化を不要なところで行う可能性は存在し、その場合の動作は予期しないものとなる。

6.6. 局所性
--------

アクターモデルの重要な特徴の1つとして、局所性がある。

局所性とは、メッセージを処理するときにアクターがメッセージを送信できる相手はアドレスを知っているものに限られるということを意味する。

また、複数の位置を同時に変更することがないことも局所性と称する。この点は他の並行性モデルとは異なる。例えばペトリネットモデルではトークンは同時に複数の場所から削除され、別の複数の場所に配置される。

6.7. 合成性
--------

合成性とは、アクターシステム群から大きなシステムを構成できることを意味する。これはモジュール性という観点で重要であり、Gul Agha の学位論文や Gul Agha、Ian Mason、Scott Smith、Carolyn Talcottで展開された。

6.8. 振る舞い
---------

「振る舞い; behavior」の導入により、アクターのメッセージ処理を数学的関数として記述できるようになった。振る舞いは並行性における共有を数学的にモデル化する機構を提供する。

6.9. 数理論理学との関係
--------------

アクターモデルの開発と数理論理学との関係は興味深い。その開発の主要な動機として、Planner言語の開発で生じた制御構造問題を扱い、理解するという目的があった。アクターモデルが定義されたとき、「計算は推論に内包される」という Kowalski の主張に関連するモデルの能力を理解するという重要な目標があったのである。ヒューイットと Agha[1991]は、結果として生まれたシステムにおける計算ステップがその前のステップからの推論ではないという意味で、演繹的ではないと指摘した。

6.10. マイグレーション
--------------

マイグレーションとは、アクターが位置を変更可能であることを意味する。例えば、米澤明憲は学位論文で郵便局をアクターモデルでモデル化した。客をアクターとし、郵便局内で位置を変えながら何らかの処理をして出て行くというものである。マイグレートするアクターは位置アクターを導入することでモデル化できる。位置アクターはアクターのマイグレーションに応じて変化する。しかし、このモデル化は議論を呼び、現在も研究対象となっている。

7. アクターモデルの重要性
--------------

ハードウェアは各種並行性を取り入れつつある。このような並行性は指数関数的に増大しつつある。

カール・ヒューイットよれば、アクターモデルはコンピュータアーキテクチャ、並行プログラミング言語、Webサービスに関する以下のような問題に直面している:

スケーラビリティ : 局所的・非局所的並行性をスケールアップする努力 透過性 : 局所的並行性と非局所的並行性の間を埋める。透過性に関しては議論が続いている。研究者によっては、並行プログラミング言語による局所的並行性とSOAPによるWebサービスなどの非局所的並行性を明確に分けて扱うべきだとする。しかし、そのような分離は技術の進歩による並行性の移行の際に透過性の問題となって現われる。この隙間を埋めるには、XMLバイナリをJavaなどのデータ型とする必要があるかもしれない。 非一貫性 : 人間の作る情報システムは巨大化するほど一貫性を失う。これは巨大システムの仕様書などの文書にも当てはまる。アクターモデルの考え方はマルチエージェントシステムにも見られる。エージェントシステムは多くの場合アクターモデルに何らかの制限を課している点が異なり、自発的で自律的であることが要求される。

8. 関連項目
-------

データフロー
アクターモデル理論、
マルチエージェントシステム
ニューラルネットワーク
Erlang

9. 脚注
-----

10. 参考文献
--------

Paul Baran. On Distributed Communications Networks IEEE Transactions on Communications Systems. March 1964.
Peter Landin. A Generalization of Jumps and Labels Report. UNIVAC Systems Programming Research. August 1965. Reprinted in Higher Order and Symbolic Computation. 1998.
Edsger Dijkstra Solution of a Problem in Concurrent Programming Control Communications of the ACM. 1965.
Jack Dennis and Earl Van Horn. Programming Semantics for Multiprogrammed Computations CACM. March 1966.
Ole-Johan Dahl and Kristen Nygaard. Class and subclass declarations IFIP TC2 Conference on Simulation Programming Languages. May 1967.
Carl Hewitt. PLANNER: A Language for Proving Theorems in Robots IJCAI 1969
William A. Woods. Transition network grammars for natural language analysis CACM. 1970.
Terry Winograd. Procedures as a Representation for Data in a Computer Program for Understanding Natural Language MIT AI TR-235. January 1971.
Carl Hewitt. Procedural Embedding of Knowledge In Planner IJCAI 1971.
G.M. Birtwistle, Ole-Johan Dahl, B. Myhrhaug and Kristen Nygaard. SIMULA Begin Auerbach Publishers Inc, 1973.
Daniel Bobrow: A Model for Control Structures for Artificial Intelligence Programming Languages IJCAI 1973.
Robin Milner. Processes: A Mathematical Model of Computing Agents in Logic Colloquium 1973.
Carl Hewitt, //et. al.// Actor Induction and Meta-evaluation Conference Record of ACM Symposium on Principles of Programming Languages, January 1974.
Carl Hewitt, //et. al.// Behavioral Semantics of Nonrecursive Control Structure Proceedings of Colloque sur la Programmation, April 1974.
C.A.R. Hoare. Monitors: An Operating System Structuring Concept CACM. October 1974.
Irene Greif and Carl Hewitt. Actor Semantics of PLANNER-73 Conference Record of ACM Symposium on Principles of Programming Languages. January 1975.
Carl Hewitt. How to Use What You Know IJCAI. September, 1975.
Alan Kay and Adele Goldberg. Smalltalk-72 Instruction Manual Xerox PARC Memo SSL-76-6. May 1976.
Edsger Dijkstra. A discipline of programming Prentice Hall. 1976.
Henry Baker and Carl Hewitt The Incremental Garbage Collection of Processes Proceeding of the Symposium on Artificial Intelligence Programming Languages. SIGPLAN Notices 12, August 1977.
Gilles Kahn and David MacQueen. Coroutines and networks of parallel processes IFIP. 1977
米澤明憲 Specification and Verification Techniques for Parallel Programs Based on Message Passing Semantics MIT EECS Doctoral Dissertation. December 1977.
Carl Hewitt. Viewing Control Structures as Patterns of Passing Messages Journal of Artificial Intelligence. June 1977.
Henry Baker. Actor Systems for Real-Time Computation MIT EECS Doctoral Dissertation. January 1978.
C.A.R. Hoare. Communicating sequential processes CACM. August 1978.
Carl Hewitt and Russ Atkinson. Specification and Proof Techniques for Serializers IEEE Journal on Software Engineering. January 1979.
Ken Kahn. A Computational Theory of Animation MIT EECS Doctoral Dissertation. August 1979.
Carl Hewitt, Beppe Attardi, and Henry Lieberman. Delegation in Message Passing Proceedings of First International Conference on Distributed Systems Huntsville, AL. October 1979.
Nissim Francez, C.A.R. Hoare, Daniel Lehmann, and Willem-Paul de Roever. Semantics of nondetermiism, concurrency, and communication Journal of Computer and System Sciences. December 1979.
George Milne and Robin Milner. Concurrent processes and their syntax JACM. April 1979.
Russ Atkinson. Automatic Verification of Serializers MIT Doctoral Dissertation. June, 1980.
Bill Kornfeld and Carl Hewitt. The Scientific Community Metaphor IEEE Transactions on Systems, Man, and Cybernetics. January 1981.
Henry Lieberman. Thinking About Lots of Things at Once without Getting Confused: Parallelism in Act 1 MIT AI memo 626. May 1981.
Henry Lieberman. A Preview of Act 1 MIT AI memo 625. June 1981.
Bill Kornfeld. Parallelism in Problem Solving MIT EECS Doctoral Dissertation. August 1981.
Daniel Theriault. A Primer for the Act-1 Language MIT AI memo 672. April 1982.
Daniel Theriault. Issues in the Design and Implementation of Act 2 MIT AI technical report 728. June 1983.
Henry Lieberman. An Object-Oriented Simulator for the Apiary Conference of the American Association for Artificial Intelligence, Washington, D. C., August 1983
Carl Hewitt and Peter de Jong. Analyzing the Roles of Descriptions and Actions in Open Systems Proceedings of the National Conference on Artificial Intelligence. August 1983.
Carl Hewitt and Henry Lieberman. Design Issues in Parallel Architecture for Artificial Intelligence MIT AI memo 750. Nov. 1983.
Daniel Ingalls. The Evolution of the Smalltalk Virtual Machine in Smalltalk-80: Bits of History, Words of Advice. Addison Wesley. 1983.
Carl Hewitt. The Challenge of Open Systems Byte Magazine. April 1985. Reprinted in //The foundation of artificial intelligence---a sourcebook// Cambridge University Press. 1990.
Carl Manning. Traveler: the actor observatory ECOOP 1987. Also appears in Lecture Notes in Computer Science, vol. 276.
William Athas and Charles Seitz Multicomputers: message-passing concurrent computers IEEE Computer August 1988.
William Athas and Nanette Boden Cantor: An Actor Programming System for Scientific Computing in Proceedings of the NSF Workshop on Object-Based Concurrent Programming. 1988. Special Issue of SIGPLAN Notices.
Jean-Pierre Briot. From objects to actors: Study of a limited symbiosis in Smalltalk-80 Rapport de Recherche 88-58, RXF-LITP, Paris, France, September 1988
William Dally and Wills, D. Universal mechanisms for concurrency PARLE 1989.
W. Horwat, A. Chien, and W. Dally. Experience with CST: Programming and Implementation PLDI. 1989.
Carl Hewitt. Towards Open Information Systems Semantics Proceedings of 10th International Workshop on Distributed Artificial Intelligence. October 23-27, 1990. Bandera, Texas.
米澤明憲編 ABCL: An Object-Oriented Concurrent System MIT Press. 1990.
Carl Hewitt. Open Information Systems Semantics Journal of Artificial Intelligence. January 1991.
Carl Hewitt and Jeff Inman. DAI Betwixt and Between: From "Intelligent Agents" to Open Systems Science IEEE Transactions on Systems, Man, and Cybernetics. Nov./Dec. 1991.
Carl Hewitt and Gul Agha. Guarded Horn clause languages: are they deductive and Logical? International Conference on Fifth Generation Computer Systems, Ohmsha 1988. Tokyo. Also in //Artificial Intelligence at MIT//, Vol. 2. MIT Press 1991.
William Dally, //et al.// The Message-Driven Processor: A Multicomputer Processing Node with Efficient Mechanisms IEEE Micro. April 1992.
S. Miriyala, G. Agha, and Y.Sami. Visulatizing actor programs using predicate transition nets Journal of Visual Programming. 1992.
Carl Hewitt and Carl Manning. Negotiation Architecture for Large-Scale Crisis Management AAAI-94 Workshop on Models of Conflict Management in Cooperative Problem Solving. Seattle, WA. Aug. 4, 1994.
Darrell Woelk. Developing InfoSleuth Agents Using Rosette: An Actor Based Language Proceedings of the CIKM '95 Workshop on Intelligent Information Agents. 1995.
Carl Hewitt and Carl Manning. Synthetic Infrastructures for Multi-Agency Systems Proceedings of ICMAS '96. Kyoto, Japan. December 8–13, 1996.
S. Frolund. Coordinating Distributed Objects: An Actor-Based Approach for Synchronization MIT Press. November 1996.
W. Kim. ThAL: An Actor System for Efficient and Scalable Concurrent Computing PhD thesis. University of Illinois at Urbana Champaign. 1997.
Jean-Pierre Briot. Acttalk: A framework for object-oriented concurrent programming-design and experience 2nd France-Japan workshop. 1999.
N. Jamali, P. Thati, and G. Agha. An actor based architecture for customizing and controlling agent ensembles IEEE Intelligent Systems. 14. 1999.
Don Box, David Ehnebuske, Gopal Kakivaya, Andrew Layman, Noah Mendelsohn, Henrik Nielsen, Satish Thatte, Dave Winer. Simple Object Access Protocol  1.1 W3C Note. May 2000.
M. Astley, D. Sturman, and G. Agha. Customizable middleware for modular distributed software CACM. 44 2001.
Carlos Varela. Worldwide Computing with Universal Actors: Linguistic Abstractions for Naming, Migration, and Coordination PhD thesis. U. of Illinois at Urbana-Champaign. 2001.
N. Venkatasubramanian, C. Talcott, and G. Agha. A formal model for reasoning about adaptive QoS-enabled middleware Formal Methods Europe . 2001.
P. Thati, R. Ziaei, and G. Agha. A Theory of May Testing for Actors Formal Methods for Open Object-based Distributed Systems. March 2002.
P. Thati, R. Ziaei, and G. Agha. A theory of may testing for asynchronous calculi with locality and no name matching Algebraic Methodology and Software Technology. Springer Verlag. September 2002. LNCS 2422.
Gul Agha and Carlos Varela. Worldwide Computing Middleware Practical Handbook on Internet Computing. CRC Press, 2004.
Stephen Neuendorffer. //Actor-Oriented Metaprogramming// PhD Thesis. University of California, Berkeley. December, 2004
Carl Hewitt. The repeated demise of logic programming and why it will be reincarnated What Went Wrong and Why: Lessons from AI Research and Applications. Technical Report SS-06-08. AAAI Press. March 2006.

11. 外部リンク
---------

[1] by Carl Hewitt, Henry Baker. Proceeding of IFIP Working Conference on Formal Description of Programming Concepts. August 1-5, 1977.
[2] by C.A.R. Hoare. Prentice Hall. 1985.
[3] by K. Kahn, Vijay A. Saraswat. in SIGPLAN //Notices//, October 1990. Janus 言語の解説
[4] by Alan Kay. The second ACM conference on history of programming languages. 1993.
[5] by Edward Lee, S. Neuendorffer, M. Wirthlin. Journal of circuits, systems, and computers. 2002.
[6] Paul Mackay による推測