日本ソフトウェア科学会第 31 回大会 (2014 年度) 講演論文集

アクターモデルに基づく並行文脈指向プログラミング機構の実装と評価
竹野 創平

渡部 卓雄

本研究ではアクターモデルにおける新たな文脈指向プログラミングの枠組みとして並行文脈指向プログラミングの概念とその実現手法を提案する。提案する手法は、自己反映計算を用いることでユーザーのプログラムと分離した形で文脈指向プログラミングのための機構を導入することを可能にしている。提案する機構は Erlang を用いて実装し、その予備評価を行った。

In this paper, we propose a new notion of concurrent context-oriented programming based on the Actor model and its implementation method. In the implementation, we use reflection to provide the mechanism for context-oriented programming
separated from user program. The mechanism is implemented on Erlang, and we evaluate its performance.

セージを送信することによって情報を伝えるため、共1 はじめに有状態の変更に伴う問題を避けることができる。また

近年、CPU に内蔵されたコアの性能向上は鈍化して一部のアクターが失敗しても残りのアクターが実行おり、多数のコアで構成された CPU が一般的になっを続けるようにすることで、高い信頼性を持つ分散シている。またコンピューティング能力やストレージをステムを構築することができる。

インターネットを介し柔軟に提供するクラウドサービ

本研究においてアクターモデルと共に扱う文脈指スが一般化した現在、複数台のコンピュータを用意す向プログラミングは、時間や位置によって変化する何ることも容易になっている。多数のコアを活用するたらかの状態を文脈とみなし、文脈に依存した振る舞い

めの並行プログラミングには通常スレッドが利用さをモジュールにまとめるプログラミング手法である。

れるが、スレッドを利用した並行プログラミングは共例えばモバイル・アプリケーションにおいては時間や有した状態が任意の時点で他のスレッドに変更され位置によってしばしばアプリケーションに求められるる可能性を考えなければならない。さらにデッドロッ

振る舞いが変わるが、文脈指向プログラミングによっクが起こらないことや各スレッドにコンピューティンてこの振る舞いをモジュール化することができる。

グ・リソースが十分に配分されることなども考えなけ

最近ではモバイル端末においても複数のコアが載ればない。これらのことから、スレッドを利用した並ることが一般的になってきており、加えてモバイル端行プログラミングは困難を伴う。このような困難を避末同士が相互に通信する形でアプリケーションが目的けつつ並行プログラミングを行なうためのモデルとを達成するというパターンも頻繁に現れている。従っして、アクターモデルがある。アクターモデルでは並て、並行性をアクターモデルの形を取り入れた文脈指行に動作するいくつかのアクターによって計算システ向プログラミング機構を用意することで、この種のムが表現される。アクター同士は状態を共有せずメッアプリケーションを直接的に記述することが可能になる。

An Implementation of Concurrent Context-Oriented Programming System based on the Actor Model
Souhei Takeno, 東京工業大学大学院計算工学専攻, Dept. ofComputer Science, Tokyo Institute of Technology.

考えられ、それに依存した振る舞いをモジュール化す

2 背景と関連研究ることでアプリケーションを変更に対してよりモジュ2. 1 アクターモデル

ラにすることができる。

アクターモデルとは、Agha らによって提案された並行計算のモデルの一つである [2]。最近では Erlangや Scala といった言語がこのモデルに基づいたプログラミング手法を提供している。

2. 3 アクターモデルにおける文脈指向プログラミング
アクターモデルに文脈指向プログラミングを導入

アクターモデルにおいて、システムはアクターといしようとすると、文脈をどのように取り扱うかを考えう独立した並行に動作する計算主体の集まりで構成さる必要がある。前述したようにアクターモデルにおいれる。システムは、アクターが相互にメッセージを非てアクターは独立した計算主体であり、メッセージの同期的に送信する（応答を待たない）ことで全体とし送信によってのみ状況が共有される。そのため文脈はて目的を達成する。アクターモデルにおける通信の基各アクターの状態としてシステム全体に分散して存礎が非同期であるのは、アクターが独立した計算主体在することになり、それぞれのアクターの文脈依存のであることによる。通信が同期的である場合、送信元振る舞いはアクターの保持する文脈によって決定されが送信先からの応答を待つという依存関係が生じる。

ることになる。

アクターはそれぞれアドレスと振る舞いを持つ。アアクターが検知した文脈の変化はメッセージ送信にドレスはメッセージの送信先を指定するために用いらよって他のアクターに共有されていく。アクターモデれる一意な識別子である。アクターはアドレスを知っルでは各アクターのメッセージはそれぞれシーケンているときに限りそのアクターに対してメッセージをシャルに処理されるため、文脈を変更が他のメッセー送信することができる。振る舞いは受信したメッセー

ジの処理に割り込んで行われることはない。これはあジをどのように処理するかというもので、アクターのる時点でシステム全体のスナップショットを撮ったと生成時に関数として与えることが多い。アクターは実き、それぞれのアクターは異なる文脈を持ちうるとい

行時にはメッセージ・キューを持ち、届いたメッセーうことを意味する。

ジはキューに入る。メッセージは順次このキューから取り出されて処理される。

アクターモデルに基づいた言語上で文脈指向プログラミングを提供するものとしては ContextErlang [4] がある。ContextErlang は Erlang で実質的なアプリケー

2. 2 文脈指向プログラミング

ションを実装する際に使われるフレームワークであ

文脈指向プログラミング（Context-Oriented Program-る OTP の一部のモジュールを拡張することで文脈指ming: COP）とは、実行時の状態を文脈という概念で向プログラミングを提供している。ContextErlang で抽象化し、文脈に依存するソフトウェアの振る舞いをはアクターは自分自身の文脈を自由に変更する権限モジュール化するプログラミング手法である [3]。こを持っており、また他のアクターの文脈を変更したいの背景には、文脈に依存した振る舞いは既存のまとめ場合は明示的にそのためのメッセージを送る。つま方ではモジュールにまたがって存在しがちであるといり、ContextErlang においては文脈は各アクターごとうことがある。に別々に存在するものであり、必要なときにプログラ

文脈の具体例として、モバイル端末であればネットマーが明示的に同期する想定になっている。これはアワークにつながっているかどうかをオンラインまたはクターごとに個別に文脈指向プログラミングを行なオフラインとして文脈にすることが考えられる。例え

うための機能を提供しているとも言える。

ばモバイル端末上に搭載されたインスタントメッセン
ジャーアプリケーションであれば、オンラインかオフラインかによって提供する機能が大きく変わることがrOOpAsA

rsm
Bpq

B(a)
図1

CX
fun(X)->E end
E(E)send(E, E)
new(E)
become(E)self()mqt

Et(b)メッセージの送り手と受け手の文脈が異なる２つの

図2✂ ✁✄✂☎✁✄✂✆✁✝✞✄✂✆✁✟✠✄✂✡☛☞✌✍✎✏✄✂✑✒✓✌✔✕✖✄✂✑✒✓✌✔✗✘✔☎✙✄✂✑✒✓✌✚✛✔✑✜✢✣✄

Simple Actor Language on Erlang

ケースすなわちメッセージ・スケジューリングを調整する必要がある。本研究では広域自己反映計算を用いてこの3 並行文脈指向プログラミング問題を解決し、並行文脈指向プログラミングを実現すアクターモデルのように並列・分散環境を前提としる手法を提案する。

たモデルにおいても、アクター個別的でない文脈指向プログラミングを行いたい。いくつかの文脈指向プロ

4 並行文脈指向プログラミングの実現

グラミング言語では、文脈はシステム全体に共有されアクターモデルにおける並行文脈指向プログラミており、古いものから新しいものに時系列で変化してングの実現を、特定のアクターモデルに基づく言語いく。並行プログラミングを行いつつ文脈をこのように比較的依存しない形で行いたい。そのためには核に大域的なものと見なす文脈指向プログラミングを、となる言語が必要最小限のものが好ましい。 そこで並行動作する計算主体ごとに行なう文脈指向プログ

Simple Actor Language [6] を利用する。本研究では簡ラミングと対比して並行文脈指向プログラミングと単のため Simple Actor Language を実装するのではな呼ぶことにする。

く、Simple Actor Language に相当する言語を Erlang

アクターモデルにおける文脈指向プログラミング
では文脈はアクターごとに分散して存在しているた言語のサブセットによって定義し、これを利用した（図 2）。

め、素朴な実装ではメッセージを送信するアクターの文脈と受信するアクターの文脈が異なるというケー

4. 1 文脈の定義

スが発生する（図 1 [6]）。これは、アクターごとに文文脈指向プログラミングを導入するために、文脈を脈指向プログラミングを行なう場合にはよいが、文脈抽象データ型として定義する。文脈は内容を表すアトをシステム全体に共有された状態として捉える並行ムを与えて作成できる。作成した文脈から内容を取得

文脈指向プログラミングには都合が悪い。

することができる。文脈同士は古いか新しいかの比較単純な解決として、メッセージを送信するアクターができる。の文脈をメッセージに添付して、メッセージを受信す

内部的には文脈は内容を表すラベルと文脈が生成るアクターが常にこの文脈に同期するという方法がされた時刻を持つ。時刻により文脈に全順序がつく。

考えられる。しかしながら、この方法ではメッセージ文脈の内容が違えば時刻は異なるものとする。

を受信するアクターの文脈が、メッセージに添付された文脈より新しいものであったとしても、受信する4. 2 文脈に求められる性質アクターの文脈が書き換えられてしまう。つまりアク並行文脈指向プログラミングを実現するためには、ターの文脈の変化が必ずしも時系列順にならない。

アクターごとに保持されている文脈を、アクター間この問題を解決し並行文脈指向プログラミングをで共有された状態と見なせるようにする必要がある。

提供するためには、文脈を持つアクターを包括的にそのためには、アクターがメッセージを送受信する際管理し、それらのアクターのメッセージの処理順序、に他のアクターの文脈が同じであることと、アクターの文脈がそれぞれ観測された順序に変化することが性はあるが、それは届いた場合に修正することで対応求められる。整理すると、文脈が以下の三つの性質をする。

保つことを意味する。

2 の場合は新しい文脈で既に処理したメッセージを1. メッセージが送信されたとき、受信するアクターまだ処理していなかったものとして取り消すために計の文脈は送信するアクターの文脈と同じである。

算を巻き戻した後、届いたメッセージを送信元のアク2. メッセージが受信されたとき、送信したアクターターの文脈に同期して処理する。計算を巻き戻すたの文脈は受信したアクターの文脈と同じである。

めには、既に処理したメッセージのリストとその時々3. アクターの文脈は古いものから新しいものにしのアクターの状態が必要である。つまりログを残すか変化しない。

必要がある。注意すべき点として、巻き戻すべきメッ

この一貫性をグループメタアクターがメッセージスセージが処理される中で他のアクターにメッセージケジューリングをコントロールすることで実現する。

を送信していた場合は、それも取り消す必要がある。

これには一貫性が崩れたとき修正する楽観的な方法

この取り消しは再帰的な処理になる。さらに送信したとあらかじめ一貫性が崩れないようにする悲観的なメッセージを取り消すためにはメッセージを一意に識方法の２つが考えられる。本研究では両方を検討した

別するための ID が必要になる。ID は send を置き換結果、楽観的な方法を採用した。

えることでメッセージ送信の際に生成し、文脈と同様にメッセージに添付する。

4. 3 一貫性の保持方法
1 と 2 の性質を保つためにはメッセージの送信元の4. 4 ログ文脈を知る必要がある。そのためにメッセージ送信操計算を巻き戻すためのログはそれぞれのアクターご作 send の機能を拡張することでメッセージの送信時とに必要になる。さらにアクターが処理したメッセーに送信元のアクターの文脈をメッセージに添付する。

ジ一つ一つに対して、そのメッセージを取り消すため

この添付データは３つ組タプルの３つ目のフィールドに必要な情報を残す必要がある。それは文脈や ID とに埋め込まれるため、アプリケーションのメッセージいった添付情報を含めたメッセージ自体と、メッセー自体と混同されることはない。添付された文脈もメッ

ジ処理前のアクターの状態とメッセージ処理後のアセージ・キューに保存される。

クターの状態、そしてメッセージ処理中に他のアクグループメタアクターがメッセージ・キューからターに送信したメッセージの ID のリストである。アメッセージを取り出したときに、メッセージを送信しクターが持つ状態はここでは振る舞いと文脈である。

たアクターの文脈と受信したアクターの文脈を比較する。このとき、図 1 で示したように３つの場合が4. 5 計算の巻き戻しある。

まずはあるアクターによって処理された一つのメッ

1. 新しい文脈のメッセージが古い文脈のアクターに届く場合

2. 古い文脈のメッセージが新しい文脈のアクターに届く場合

セージ M1 を取り消すことについて考える。これはメッセージ M1 の処理によって起きたことを取り消した後、M1 をメッセージ・キューに戻すことで行われる。例えば、メッセージ M1 によってアクターの文脈

3. 文脈が同じである場合

C1 が C2 に更新されたのなら、メッセージ M1 を取

まず 3 の場合はそのままメッセージを処理すればり消した結果、アクターの文脈は C1 になっていなけ良い。

ればならない。アクターの振る舞いについても同様で

1 の場合は単純に受信するアクターの文脈を新しいある。一般的に言って、アクターが状態を持つとき、ものに更新してからメッセージを処理すれば良い。こメッセージの処理によって状態が変化したならばそのの後に更新する前の元の文脈のメッセージが届く可能状態を元に戻す必要がある。メッセージ M1 を処理す

リスト 1OA

B

C

取り消すべきメッセージを決定する処理

messages_to_cancel m =foldl (++) [m] [ messages_to_cancel m’ | m’ <- ms]
where ms = m の 処 理 中 に 送 信 し た メ ッ セ ー ジ ++m以降に処理したメッセージ巻き戻したい。そのためには A の二つ目のメッセージを取り消すことを考えればよい。そこから関連して取り消されるメッセージが取り消すべきメッセージの全てになる。
一般的に M を取り消す際に一緒に取り消すメッセージを決定する処理!

messages to cancel は、リストの内包表記と畳み込みを使って上のように書ける。このうち M からメッ✂ ✁✄☎✆✝✞✟✠✡☛✂ ✁✄☎✆☞✆✌

セージ送信によって派生したメッセージ以外がメッセージ・キューに戻すべきメッセージとなる。†1

4. 5. 1 ログを切り捨てる仕組み
計算を巻き戻すためのログは計算が進むにつれて大きくなる。実行に伴い無制限にログが増えないようにするためには、ある時点でそれ以上は巻き戻らないる中で他のアクターにメッセージ M2 が送信されていというような境目を見つけそれ以前を破棄する必要た場合、メッセージ M2 も処理されてないことにするがある必要があるため、取り消す。ただし、これは取り消す計算の巻き戻しは古い文脈のメッセージを受け取るべきメッセージ M1 から派生したメッセージなので、ことによって起きる。従ってある文脈 C より古い文メッセージ・キューには戻さず捨てる。M2 の取り消脈のメッセージを受け取ることがないということが分しから派生したメッセージがあった場合も M1 から派

かれば、文脈 C より古い文脈で生成されたログは不生したメッセージなので同様に捨てる。加えて M1 以要ということになり切り捨てることができる。

降に処理されたメッセージがあった場合それらも取り

4. 5. 2 自己反映計算による実装

消す。

自己反映計算（Reflection）とは、一般にプログラ具体例として上の図のような状況がある。ここでアムがプログラム自身について行なう計算のことを指クターは最初から文脈を持っている。時間が進むと文す [5]。自己反映計算が可能な言語においては、プロ脈の観測を担当するアクター O によってまず白色のグラム自身を表現するデータがあり実行時にそれを参新しい文脈が観測され、その後黒色の新しい文脈が観照することができる。またこれを変更することでプロ測される。時間が進むと古い白色の文脈のアクター Cグラム自身の動作を変更することができる。アクターから送信されたメッセージが、新しい黒色の文脈のアモデルにおいて自己反映計算を実現するための機構

クター A に届いて計算の巻き戻しが行われる。このが提案されている [6]。この機構では、メッセージの巻き戻しで取り消される全てのメッセージが図に記さ送信、メッセージ・キューの保持などをグループ・メれている。

タアクターと呼ばれるアクターが実行する。これま例においてはアクター A を白色の文脈のメッセージ（A の一つ目のメッセージ）が処理された直後まで†1 実際の実装ではこの二つを同時におこなっている。

図4
図3

アプリケーションシステム

文脈指向プログラミング機構によるオーバーヘッド張された広域自己反映機構を使った実装とした。そので述べてきた機能はメッセージ送信プリミティブの拡結果、拡張によるオーバーヘッドにより実行時間が 4張とグループ・メタアクターの振る舞いの変更によっ倍前後になることが分かった（図 3）。て実現できる。これらは自己反映計算によって実現さ

4. 6. 2 応用例

れるため、言語処理系に手を加えることなく、またア並行文脈指向プログラミング機構のアプリケーショプリケーションのプログラムに余計な記述をすることンとして、次のようなシステムが考えられる。状況となく文脈指向プログラミングを行なうことができる。

して、学会・カンファレンスなど、あるテーマについて発表・議論が行われる場を想定する。このテーマ

4. 6 予備評価と応用例は順々に移り変わっていく。それぞれのテーマに対し

4. 6. 1 予備評価て、聴衆はモバイル端末からサーバーへコメントを投実装した機構の実行性能の予備評価を行った。

稿できる。サーバーはコメントを集積する。集積され測定には 2.5GHz の Intel Core i5 と 8GB の RAM

たコメントは同期的にスクリーンにタイムラインのから成る環境を用い、Erlang OTP R16B03-1 を SMPような形で映し出される。ただし、コメントは単純に(Symmetrical Multi Processor) オプションをオフにし時系列で表示されるのではなく、テーマごとに分けらて Mac OS X 10.8.5 上で実行した。測定はそれぞれ３れて視覚化される。

回ずつ行いその平均を結果として用いる。

このシステムでは、聴衆のモバイル端末それぞれ性能評価には thread-ring [1] を用いる。thread-ringがサーバーから見て一つのアクターを持つ。モバイ

はある固定数のアクターを作成し、それらがリングル端末の内部では、ネットワーク通信が発生する処理状に参照を持つようにする。このリングのいずれかはユーザーとのインタラクションの処理とは並行しのアクターに対して自然数（トークン）をメッセージて行われるため、複数のアクターがモバイル端末上送信する。するとアクターはこのトークンをデクリに存在することになる。サーバーはユーザーからコメントしながら次のアクターに渡していく。トークンメントを受け取る一つのアクターとして表現される。

が 1 になった時点でアクターはプログラムを終了さ受け取ったコメントを加えた描画が計算され、スクせる。例えばトークンが 100 でリングの長さが 20 のリーンに送られる（図 4）。

場合、メッセージがリングを 5 周してプログラムは終了する。

このシステムにおいて、今どのテーマが扱われているかを文脈と見做すことができる。このテーマはサー

評価は Erlang をラップする形で定義された Simple

バー側で切り替えられ、同時に文脈の切り替えとしてActor Language を言語として、自己反映機構を導入しモバイル端末にブロードキャストされる。通常であれた実装と、これを文脈指向プログラミングのために拡ば、様々な要因により過去のテーマについてのコメン

トを受け取る可能性を考慮してプログラムしなればとが挙げられる。これによって巻き戻し不可能なアプならない。しかし、並行文脈指向プログラミングにおリケーションにも並行文脈指向プログラミングを利用いては他のアクターと文脈は共有されていると考えすることができるようになると考えられる。てプログラムすることができるため、この可能性を考慮する必要はなく、プログラムが簡潔になる。

謝辞
本研究の一部は JSPS 科研費 24500033 の助成を受5 まとめと今後の課題けている．

本研究ではアクターモデル上での新たな文脈指向プログラミングの枠組みとして並行文脈指向プログ参考文献

ラミングを提案した。単純なアクターモデルに基づく[1] Computer Language Benchmarks Game.
http://
benchmarksgame.alioth.debian.org/.
[2] Agha and Abdulnabi, G.: Actors: a model of concurrent
computation in distributed systems, (1985).
[3] Hirschfeld, R., Costanza, P., and Nierstrasz, O.: Contextoriented Programming, Journal of Object Technology,Vol. 7, No. 3(2008), pp. 125–151.
[4] Salvaneschi, G., Ghezzi, C., and Pradella, M.: ContextErlang: Introducing Context-oriented Programming in
the Actor Model, Proceedings of the 11th Annual International Conference on Aspect-oriented Software Development, AOSD ’12, ACM, 2012, pp. 191–202.
[5] Smith, B. C.: Reflection and Semantics in Lisp, Proceedings of the 11th ACM SIGACT-SIGPLAN Symposiumon Principles of Programming Languages, ACM, 1984,
pp. 23–35.
[6] Watanabe, T.: Towards a Compositional Reflective Architecture for Actor-based Systems, Proceedings of the 2013
Workshop on Programming Based on Actors, Agents, andDecentralized Control, AGERE! ’13, New York, NY, USA,ACM, 2013, pp. 19–24.

言語上で広域自己反映計算を用いてそれを実現する手法を提案、実装した。実装した機構のオーバーヘッドを測定するとともに、具体的な応用例としてモバイ
ル・アプリケーションを利用したシステムを挙げた。
今後の課題としては、応用例を実際のアプリケーションとして実装してみることで、並行文脈指向プログラミングの可能性を探ることが挙げられる。そのために、まずモバイル端末上でアクターモデルを利用できるようにすることが必要になる。またモバイル端末とサーバーの通信も同様にアクターモデルの枠組みで行なうことも必要になる。これらが実現できれば、並行文脈指向プログラミングの適用範囲もまた広がるのではないかと考えられる。また別の方向として、並行文脈指向プログラミングを悲観的に実現するこ