Langphilia! / Study / Programming Languages for Distributed Applications
{Seif Haridi, Peter Van Roy, Per Brand, Christian Schulte}, Programming Languages for Distributed Applications, Invited paper for New Generation Computing, 1998-03-08.
このページは、上記の論文の前半をてきとーに日本語訳したものです。 原文の著作権は原著者にあります。 このページの著作権は私にあります。 翻訳許可はもらっていません。
分散計算は、分散構造、オープンコンピューティング、 失敗耐性、保安性の領域で大きく広がってきた。 しかし、分散アプリケーションを書くのがまだ難しいのは、これらの 領域のモデルをプログラマが明示的に管理しなければならないからだ。 大きな挑戦は、4つのモデルを1つの開発環境へ統合することである。 その環境は、アプリケーションの機能と他の4つの関連領域を きれいに分けることができるべきである。 並行制約プログラミングは並行論理プログラミングの発展であり、 この統合を試みるのに必要な表現力と形式的な基礎を持っている。 まず、我々はアプリケーションの機能と分散構造を分ける環境を 設計し、作り上げた。 また、この環境で協調するツールをいくつかプロトタイプした。 その中には、詳細に設計した共有画像エディタも含まれる。 この環境で実装したDistributed Ozは、分散構造を表現する構造体と ｛オープンコンピューティング、失敗耐性、資源制御｝のための 基本プリミティブをもつ、Ozの拡張である。 Ozは、データフローにより同期を行なう並行オブジェクト指向言語である。 Ozは、高階、状態感知、並行制約計算モデルに基づく。
我々の社会は、コンピュータネットワークを通じて、ますます つながりを強めていく。世界中で情報が行き交うことは普通になった。 TCP/IPプロトコル族の頂点に建つインターネットは、1981年以来 毎年ホスト数が倍になり、1997年には2千万を越えた。 この新しい広域組織で優位に立つアプリケーションは、 キノコのように早く増殖する。 電子メールとネットニュースで始まった協調作業は、 ワークフローと真の分散環境[16, 4]へと変貌を遂げた。 ヘテロで物理的に分かれた情報源が結びつけられている。 タスクはエージェント[17]の手法によって ネットワーク越しに依頼される。 電子商取り引きは安全なプロトコルで行なうことができる。
しかし、この爆発的な成長にも関わらず、 分散計算には大きな挑戦が残っている。それはなぜか？ 分散システムは莫大な数のプロセスの集合であり、 ネットワークで結びつけられている[36, 20, 6]。 これらのプロセスは同一のマシン上にある必要がないことを 強調するために、サイトと呼ぶ。 このようなシステムは、単一のプロセスとは根本的にことなる。 分散システムは本質的に並行かつ非決定的である。 グローバルな情報もグローバルな時間も存在しない。 プロセス間通信の遅延時間は予測不可能である。 局所化された失敗が起きる可能性は高い。 システムが共有されているので、ユーザは他のユーザや 計算エージェントから守られなければならない。
分散アプリケーションは、下にあるシステムの絶え間ない変化に 関わらず、良く知られた行動をするべきである。 アプリケーションは効率が良く、信頼でき、 他のアプリケーションと容易にインタフェースをとれるべきである。 どうすればこの目標を達成できるのか？
現在の技術では、これらの性質を持つ分散アプリケーションを 開発するには、単一マシンのアプリケーションを開発するのに必要な 知識を越える専門的な知識が必要である。 例えば、新しいクライアント-サーバアプリケーションはJava RMI [23, 24]で書くことができる。 既存のアプリケーションはCORBAの実装（例えばOrbix） [27]によって他のアプリケーションに繋げることができる。 しかし、いずれの場合もツールは十分でない。 例えば、分散構造を構成しなおすにはアプリケーションを書き直す必要がある。 さらに、分散構造の設計や失敗耐性の度合のような新しい問題が起きるたびに、 アプリケーションの複雑さが増していく。 それぞれの問題に対処するために、開発者は既知の環境に加えて 複雑な新しいツールを学ばなければならない。 集中システムしか経験したことのない開発者は準備ができていない。
我々は分散計算における4つの大きな問題領域を特定した。 すなわち、分散構造、オープンコンピューティング、失敗耐性、保安性である。 アプリケーションの機能を含めると、アプリケーション設計者は 5つの問題領域を持つことになる：
考えられるアプローチは機能と他の4つの領域を分けるものである（図1を見よ）。 すなわち、アプリケーションのコードの大部分が、 機能を実現するためのものであって欲しい。 他の4つのモデルは、直交した小さな追加であるべきだ。 このアプローチはうまくいくのか？ これは難しい問いであり、我々はまだ完全な答を得ていない。 しかし、ある程度のことは言うことができる。
第1歩は、機能と分散構造を分けることである。 分散システムは、ネットワーク透明であり、 ネットワーク感知もできるべきである。 システムがネットワーク透明であるとは、 分散構造と独立な場合と同じように計算が行なわれることである。 ネットワークを意識せずに、アプリケーションの ほとんど全てをプログラムすることができる。 システムがネットワーク感知できるとは、 プログラマが計算の局所化とネットワークの通信パターンを 完全に制御できることである。 プログラマは計算がどこで行なわれるのかを決め、 データとコードの機動性と再現性を制御する。 このことによって、高い効率を得ることができる。
Distributed Oz計画において設計、実装した言語は、 第1歩を実装する、すなわち機能と分散構造を完全に分けるものだった。 さらなる発展は、他の3つのモデルを切り離すことである。 結果として得られる言語Distributed Ozは、 既存の集中言語Ozに対する保守的な拡張である。 既存のOzプログラムは、ほとんどそのままDistributed Ozに移植できる。 Distributed OzはOzの基本言語意味論（第3節 を見よ）に加えて、4つの拡張機能を提供している：
Distributed Ozでは、アプリケーションの開発は2つの独立な部分に大別できる。 第1に、タスクの論理アーキテクチャのみを考える。 アプリケーションはOzで書かれ、複数サイトに渡る計算の分散は明記されない。 Ozはプログラマから見て、データフロー同期に基づく 並行オブジェクト指向言語である[9]。 プログラマは、1つのサイトで動くアプリケーションの 安全性と生存性（注1）を検証する。 第2に、アプリケーションの効率を上げるために、 ネットワークにおけるアプリケーションの各実体の行動を決める。 特に、実体（オブジェクト）の機動性を決めなければならない。 例えば、特定のサイトに留まるオブジェクトがあり得るし、 他のオブジェクトは（状態キャッシュのような） ある程度の機動性を与えられるかもしれない。
Distributed Ozの実装は、 4つの重要な分散アルゴリズムを拡張したOzの実装である。 その内の3つは仕様言語の実体用に設計したもの、 すなわち変数、オブジェクトレコード、オブジェクト状態である。 変数は変数削除プロトコルを使う （第4.2節を見よ）。 オブジェクトレコードは消極再現プロトコルを使う （第4.3節を見よ）。 オブジェクト状態は機動状態プロトコルを使う （第4.4節を見よ）。 4つ目のプロトコルは、クレジット機構を使った分散ゴミ集めアルゴリズムである （第4.5節を見よ）。 ゴミ集めは共有実体管理の一部なので、他の3つのプロトコルの下にある。
本論文の残りは6つの部分からなる。 第2節で、Distributed Ozによる共有画像エディタの設計を示す。 この節で、実際に機能と分散作業の分け方が見えるだろう。 第3節で、Oz言語とその実行モデルを概観する。 Ozは、論理プログラミングと並行論理プログラミングのコミュニティに深く由来する。 この節で、そのつながりがはっきりするだろう。 第4節で、Distributed Ozとそのアーキテクチャを提示し、 機能と分散構造の分け方を説明する。 4つのプロトコルに焦点を当てる。 すなわち、分散論理変数、オブジェクトレコードの消極再現、 オブジェクト状態の機動性、分散ゴミ集めである。 最後に第5, 6, 7節で、オープンコンピューティング、失敗耐性、 資源制御と保安性を議論する。 この3つの節は他の節よりも思索的である。 なぜなら、システムのまだ発展し続けている部分を記述しているのだから。
機能と分散構造を分けると、 効率的な分散アプリケーションを書くのは非常に単純になる。 我々はこの主張を実証するために、協調作業環境で役立つ 共有画像エディタのプロトタイプを設計、実装した。 このエディタは、任意の数のユーザから見ることができる。 我々は、このエディタが1つの共有仮想環境として振る舞うことを望む。 このため、次のような要求がある（図2を見よ）。 ・全てのユーザは、いつでも図を更新することができる。 ・各ユーザは、自分の更新結果を気にする程の遅延時間なしに見ることができる。 ・更新は、全てのユーザがリアルタイムで見ることができる。 ・さらに、同じ画像の実体を複数のユーザが更新することができる。 これは協調CAD環境で複雑な画像デザインを行なうのに役立つ。 ・最後に、全ての更新は時系列の一貫性があって、 各ユーザは正確に同じ図を見ることになる。 最後の2つの要求は、アプリケーションを面白くするものである。 例えばLBL Whiteboardアプリケーション（注2）で使われている、 各ユーザの画面に対する更新をマルチキャストする手法では、 最後の2つの要求を満たすことができない。
図3は、プロトタイプの論理アーキテクチャである。 分散構造についての仮定は全くない。 図の状態は、オブジェクトの集合として表される。 オブジェクトは、図形や自由曲線のような画像の実体を表す。 ユーザが図を更新すると、新しいオブジェクトが生成されるか、 既存のオブジェクトに状態を変更するメッセージが送られる。 その後、オブジェクトは画面ブロードキャスタに更新を伝える。 ブロードキャスタは全てのユーザに更新を伝え、画面を更新する。 ユーザの入力から画面の更新までの実行経路は単純ではない。 ユーザは共有ストリームを見ることによって、 時系列の一貫性を保証されている。
新しいユーザは、Distributed Ozのオープンコンピューティング 機能を使って、いつでもエディタにつながることができる。 この仕組みは、チケットと呼ばれる単純な文字列に基づく （第5節を見よ）。 チケットを理解するOzプロセスは、言語の実体への参照を得ることができる。 画像エディタは、ユーザ管理オブジェクトに対するチケットを 発行することによって、新しいユーザを加える責任を持つ。 新しいユーザが加わるには、チケットを使ってユーザ管理への参照を得る。 この2つの計算は同じオブジェクトを参照する。 この2つの計算によって、2つのサイト間に透明なつながりができる。 このため、計算空間は共有されている。 計算中に2つのサイト間の参照がなくなったら、 そのサイト間のつながりはゴミ集めによって消される。 こうして、計算中のつながりの生成、消滅は、 つなぎ目を意識させずに行なわれる。
設計に現実味を持たせるために、分散構造を定義しなければならない。 図4は分散構造の一例、クライアント-サーバ構造である。 全てのオブジェクトは移動しない。 オブジェクトは、サーバサイトと各ユーザのサイトに分散している。 これは効率以外の要求を全て満たす。 LANのように遅延時間が短いネットワークではうまく動くが、 例えばスウェーデンと日本のように遠く離れたユーザが 自由曲線や、絶えずフィードバックを必要とする 画像の実体を描こうとすると効率が悪い。 これは、自由曲線が短時間に多くの小線分を描くためである。 我々の実装では、毎秒30個までのイベントが 画像サブシステムからOzプロセスに送られる。 各線分は、描画領域の状態更新と全てのユーザに更新を伝えることを必要とする。 描画領域の状態が遠隔にあると、 1回の更新に数百ミリ秒以上という許せない時間がかかる。
遅延時間の問題を解決するために、分散構造を変更する（図5を見よ）。 設計を洗練して、画像状態と画面ブロードキャスタを 移動しないオブジェクトではなく、自由な機動性を持つ （「キャッシュされる」）オブジェクトとして表す。 洗練の結果、画像状態の部分は、 その状態を変更するサイトにキャッシュされる。 実装には、新しいオブジェクトを生成する呼び出しを いくらか変更する必要がある。 500行超のコードの内10行足らずを変更すれば良い。 この変更によって、自由曲線でローカルな画面を更新するのに ネットワーク上の操作は不要となり、効率は満足できるものとなった。 遠隔のユーザは、ネットワークの遅延時間後に リアルタイムで自由曲線を見ることができる。
エディタの設計をもっと洗練して、 オブジェクトの分散具合いをもっと良くすることができる。 例えば、オブジェクトをキャッシュする設計には2つの問題がある：
プッシュオブジェクトもトランザクションオブジェクトも、 オブジェクト更新の一貫性を保つ： どちらのオブジェクトも状態列によって定義される。 1つの画像状態とその更新は時系列の一貫性を保ったままである。 従って、エディタもまだ協調設計をサポートする。 変更されたのは、状態列の見え方、作られ方である。
いずれかまたは両方のオブジェクトによるエディタの変更は、 仕様か論理アーキテクチャの変更を必要とするかも知れない。 例えば、仕様を緩めて、 わずかに不正な画面を許すようにしなければならないかもしれない。 これはネットワーク透明なプログラミングの限界を示している。 仕様と論理アーキテクチャを与えられて、分散構造の変更によって 効率を無制限に上げることは、一般には不可能である。 いくつかの点で、仕様とアーキテクチャのいずれか または両方を変更しなければならない。
共有画像エディタの設計によって、Distributed Ozで アプリケーションを組み立てるアプローチの2つの部分を示した。 第1に、移動しないオブジェクトを使って アプリケーションを組み立て、テストする。 第2に、注意深くいくつかのオブジェクトを選び、 機動性を変更することによって遅延時間を減らす。 透明性のおかげで、アプリケーションコード自体は非常に小さな変更で済む。 このことは多くの場合、良い結果をもたらす。 しかし、非常に高い効率を得るには、アプリケーションの 仕様やアーキテクチャを変更する必要があるかも知れない。
移動しない設計でも機動性を持つ設計でも、 失敗耐性は陽に考えなければならない別の問題である。 全ての画面イベントのログを、信頼できるサイトに記録すれば良いだろう。 壊れたユーザを消し、新しいユーザにログを圧縮して送れば良い。 失敗耐性用のプリミティブは、第6節で提示する。
一般に、機動性を持つオブジェクトは、 微粒度の機動性（オブジェクト状態のキャッシュ）にも、 粗粒度の機動性（オブジェクトグループの明示的な移送）にも役立つ。 システムが提供しなければならないキーとなる機能は、 機動性の透明な制御、すなわちオブジェクトの機能と独立な制御である。 第3.2節と第4節では、Distributed Ozで これがどう行なわれているかを少し説明する。
Ozは、強力な概念の小さな集合からなる言語である。 この節では、Ozの様々な側面の説明を試みる。 Ozのプログラミングモデルをまとめ、 Prologや並行論理言語との比較を行なう。
Ozは、並行／制約論理プログラミングに由来する。 Oz計画の目標は、宣言的な部分集合だけでなく、 計算の全ての側面に対して強固な基礎を提供することである。 その意味論は完全に定義され、操作的な側面をオープンにすべきである。 例えば、並行性と文の実行によって、 外界に反応するプログラムを書きやすくなる[11]。 真の高階性の結果、コンパクトでモジュール化されたプログラムが得られる。 1級計算空間は、プログラムがシステム内部のエンジンに干渉することを許す。 例えば、独自の検索戦略を持つ、複数の並行1級Prologトップレベルを 簡単にプログラムすることができる[31]。
第3.1節で、核言語とその上に作り上げた抽象を含め、 Ozのプログラミングモデルについてまとめる。 第3.2節では、Ozを分かりやすくするために意味のある例、 すなわち遠隔メソッド呼び出しを取り上げる。 第3.3節では、OzとPrologを比較する。 最後に第3.4節で、並行論理プログラミングの 観点からOzの歴史を眺める。
基本計算モデルは、データフロースレッドから 見られる抽象記憶である（図6を見よ）。 スレッドは文の列を実行し、データの有効性によってブロックされる。 抽象記憶は物理メモリではない。 内部の実体に対して合法な操作のみが許され、 型変換やアドレス計算はない。 抽象記憶は3つの部分からなる： 制約記憶は変数と束縛を含み持ち、 手続き記憶は手続きの定義を含み持ち、 セル記憶は変更可能なポインタ（「セル」）を保持する。 制約記憶と手続き記憶は変化に乏しく、 情報が加わるだけで変更したり消えたりはしない。 スレッドは、制約記憶内のデータの有効性によってブロックされる。
| S ::= | 5つの言語実体 |
local X in S end 未束縛変数
X = f(l1: Y1 ... ln: Yn) レコード、数、など
proc{X Y1 ... Yn} S end | {X Y1 ... Yn} 手続き
{NewCell Y X} | {Exchange X Y Z} 明示状態
thread S end スレッド
| |
| 制御フロー | |
case X==Y then S1 else S2 end 条件文 try S1 catch X then S2 end | raise X end 例外処理 |
スレッドは、Ozプログラミングモデル (OPM) という核言語 （図7[34]を見よ）を実行する。 図中の構造を簡単に説明する。 全ての変数は論理変数であり、 local構造によって定義された明示的なスコープの中で宣言される。 値（レコード、数、など）は明示的に導入され、変数に代入することができる。 手続きはproc構造によって実行時に定義され、変数から参照される。 最初の実引数が手続きを指すまで、手続きの適用はブロックされる。 状態を明示的に生成するNewCellはセル、すなわち ｛制約記憶内を指す変更可能なポインタ｝を生成する。 セルはExchangeによって読まれたり変更されたりする。 スレッドはthread構造によって明示的に生成される。 条件文はcaseキーワードを使い、 制約記憶内の条件が真または偽になるまでブロックされる（注3）。 例外処理は動的なスコープを持ち、try構造とraise構造を使う。
完全なOzは、全ての文をこの基本モデルに変換することによって定義される。 完全なOzは、オブジェクト、クラス、複数実行可能なロック、ポートなどの 表現をサポートしている[34, 40]。 システムはこれらを効率的に実装することが、その定義から期待されている。 次にこれらの表現の概要を定義する。 明確にするために、概念的な単純化を少し行なった。 完全な定義は、[9]に見られる。
この記事の目的は、Ozを完全に説明することではない。 その代わり、面白くて意味のあるプログラムの例によってOzを説明する。 Ozで活性オブジェクトを実装する方法を示し、さらに、同じプログラムが Distributed Ozの遠隔メソッド呼び出しを実装することを示す。 活性オブジェクトは、スレッド（またはプロセス）を関連づけられた オブジェクトであり、アクタや並行論理プロセスに良く似ている。 活性オブジェクト内のメソッド呼び出しは、 明示的に関連スレッドへメッセージを送ることによって行なわれる。 後で見るように、この種のオブジェクトはDistributed Ozで きちんと定義された分散行動を持つ。 Distributed Ozのスレッドは移動しないので、 活性オブジェクトも移動せず、生成されたサイトに留まる。 遠隔サイトからのオブジェクト呼び出しは、 遠隔メソッド呼び出しの良く知られたパラダイムを導く。
あるオブジェクトが、与えられたサイト上の スレッドから呼び出されたものとする。 このオブジェクトは、どこで実行されるのか？ ネットワーク透明なシステムでは、この質問に対していくつかの答があり得る。 Distributed Ozでは、オブジェクトはデフォルトで 機動性を持ち、呼び出したサイトで実行される。 オブジェクトは、呼び出したスレッドの内部で実行される。 これは軽量機動プロトコルにより、オブジェクトの状態ポインタの 経路を呼び出したサイト間で直列化することで実装される （第4節を見よ）。
proc {NewStationary Class Init ?StatObj}
Obj = {New Class Init}
S P = {NewPort S}
N = {NewName}
in
thread
{ForAll S
proc {$ M#R}
thread
try {Obj M} R=N
catch E then R=E end
end
end}
end
proc {StatObj M}
R in
{Send P M#R}
case R==N then skip
else raise R end
end
end
end
全てのメソッドがあるサイトで実行されるような、 移動しないオブジェクトを定義することは可能である。 図8は、手続きNewStationaryを定義する。 クラスClassと初期化メッセージInitを受けとり、手続きStatObjを返す。 「?」は出力引数を表すコメントである。 NewStationary内部では、オブジェクトObj、 ポートPとそれに関連づけられたストリームSが生成される。 Sにメッセージが現れるたびに、サービスを行なうスレッドが生成される。 これを行なうために、高階手続き {ForAll S Proc} が使われている。 Procは1引数手続きである。 このスレッドが、ストリームSにメッセージXが現れるまで待ち、 手続き呼び出し {Proc X} を実行することに注意せよ。 この手続きは、M#Rの対を期待している。 スレッドが起動して、{Obj M} によってオブジェクトを呼び出し、 正常実行を表す無重複の名前Nに、または例外EにRを束縛する。 プログラムスコープを持つ新しい名前Nを使うことによって、 例外と混同が起きないことが保証されるのに注意せよ。 今度は手続きStatObjを考えよう。 StatObjを実行するスレッドは、ポートPに対M#Rを送る。 Mはメッセージ、Rは答を得る論理変数である。 対応するメソッドの実行が正常終了するか例外が返るまで、 スレッドはRを待って中断する。 後者の場合、StatObjを実行したスレッドに例外が投げ直される。
Ozによって、プログラマが実装に関わらずに使える 汎用抽象を提供できることを見よう。 NewStationaryを使うために理解する必要はない。 これは、NewStationaryによって生成されたオブジェクトが 標準手続きNewによって生成されたのと同じOzの意味論を持つためである。
class Counter
attr i
meth init i<-0 end
meth inc i<- @i+1 end
meth get(X) X=@i end
meth error raise some_error end end
end
Obj = {NewStationary Counter init}
{Obj inc}
{Obj inc}
{Print {Obj get($)}}
try {Obj error} catch X then {Print X} end
図9で定義されるCounterクラスは、移動しない実体Objを生成し、 いくつかのメッセージをObjへ送る。 ObjがNewStationaryかNewのどちらで生成されたものでも、 言語上の行動は同じである。 Counterクラスは子孫を持たないので、継承宣言は現れない。 Counterの各実体は、属性iと4つのメソッドを持つ。 属性は、メソッドの中からアクセス、変更できる実体である。 メソッドの定義は、（一般に）レコードであるメソッド頭部と、 selfによる動的束縛が可能な文であるメソッド本体からなる。 属性値へのアクセスは、演算子「@」によって行なわれる。 属性に新しい値を代入するには、演算子「<-」を使う。 従って、メソッドinitはiを0に初期化し、メソッドincはiを増分し、 メソッドgetはiの現値を得、メソッドerrorは何か変な例外some_errorを投げる。 Ozの構文は、式に文を埋め込むことをサポートしている。 文を式として使うには、結果に「$」と印を付ける。 従って、{Print {Obj get($)}} は、 local X in {Obj get(X)} {Print X} end と等価である。
| SICStus Prolog | Oz | |
|---|---|---|
| 制約 | 増分解決の答 | 増分解決に対する質問と答 |
| 制御 | 後戻りとコルーチン | 明示的なデータフロースレッド、カプセル化された検索 |
| 高階 | 呼び出し、言明 | プログラムスコープを持つ1級手続き |
| 状態 | オブジェクト、変更可能変数、言明 | オブジェクト、セル |
OzはPrologの子孫であるという感じが強い（表1を見よ）。 Prologや並行論理プログラミングが今日使われている多くのタスクに、 Ozシステムを使うことができる[22, 31, 12, 35]。 Prolog同様、Ozは宣言的な部分集合を持つ。 Prolog同様、Ozは任意の制約システム（現在実装されているのは 有限領域と、仕様のオープンな構造である）に一般化された。 後述するように、OzはPrologの問題の多くを解決する。 Ozは完全に定義されており、 最高のPrologシステムに匹敵する効率的な実装が行なわれている [11, 25, 38]。 しかし、OzはPrologと多くの共通点を持つ、Prologの包含集合である。 Ozは、Prologの反射構文と、（call/1, assert/1のような）メタ プログラミング機能やユーザ定義構文（演算子宣言）を持たない。
Prologが成功した基礎は、宣言的な部分集合の高級な抽象化、 すなわち1階ホーン節論理とSLDNF解法による[19]。 Prologに不足していたのは、宣言的な部分集合の外部に 同じ基礎を与えようという試みである。 20年間の研究の結果、宣言的な部分集合は強い理解を得たが、 それ以外の部分は部分的にしか理解できていない（注4）。 この結果、Prologに2つの主流が生まれた。 第1に、操作的な側面は宣言的な側面とあまりに深く結び付いているというもの。 制御は単純（深さ優先探索）で、積極的である。 反応が得られるトップレベルは特別な状態を持つ： トップレベルは消極的でプログラムからアクセスできない。 第2に、宣言的な部分集合から外れたものを表現するには、 常に正しいことをするとは限らない制限された アドホックなプリミティブを使う必要があるというもの。 freeze/2は、制限された並行性を持つコルーチンを提供する。 call/1とsetof/3は、制限された高階性を提供する。 これらの問題は全て、Ozで解決されている。
| 並行論理プログラミング | Oz | |
|---|---|---|
| 制約 | AKL以外は、ない | 増分解決に対する質問と答 |
| 制御 | 微粒度の並行性 | 明示的なデータフロースレッド、カプセル化された検索 |
| 高階 | 限定されている | プログラムスコープを持つ1級手続き |
| 状態 | ストリームに基づくオブジェクト | オブジェクト、セル |
Ozは長い歴史を持つ並行論理言語のうち最新のものである。 表2は、Ozと並行論理プログラミング言語の比較である。 並行性を最初に実験した敬うべきIC-Prologシステムは、 コルーチンを使って並行プロセスをシミュレートした。 ここから、Parlog言語とConcurrent Prologが生まれた。 GHCの登場によって不活性ガードの概念が導入され、 並行論理プログラミングはかなり単純化された。 ゴールにマッチする節が実行されるのは、 そのガードが制約記憶に含まれるときのみである。 この定式化と理論的な支えは、MaherとSaraswatによって開拓され、 並行論理プログラミングの強固な基礎となった [21, 30]。 実用面では、Concurrent PrologとGHCのフラット版が、それぞれFCP、 FGHCと呼ばれ、多くの成果の焦点となった[33]。 KL1言語はFGHCから派生し、効率の良いKLICシステムによって実装された。 このシステムは、逐次、並列、分散マシン上で動く[8]。 現在Distributed Ozシステムの実装技術の多く、 特に分散ゴミ集めアルゴリズムは、KLICから借りたものである。
その後の重要な発展はAKL (Andorra Kernel Language) [14]で、ポート形式の明示状態を加え、 並行／制約論理プログラミングを最初に合成した。 AKLは、ネストされた計算空間を使って検索をカプセル化した。 計算空間は、ゴールを関連づけられた制約記憶である。 手続きが知ったこっちゃないガード節の列を定義することによって、 検索が行われる。 局所伝播が節を選べないとき、プログラムは計算空間の クローンを作ることによって、自由に試行することができる。 初期のOzシステム、Oz 1は大きくAKLによっていたが、 高階手続きの概念、1級計算空間によってもっと制御可能な検索、 複合構文、変更可能状態用のセルプリミティブが加えられていた。 Oz 1の並行性は微粒度である。 中断した文はスレッドをフォークし、 メインスレッドの計算は自動的に次の文の実行を続ける。
Oz 1以前の並行論理言語は全て、微粒度の並行性と 暗黙の並列利用を目標に設計された。 現在のOz言語、Oz 2はこのモデルを捨て、 スレッド生成構造によって並行性を明示的に制御することを選んだ。 スレッドの中断と再開はまだ、 論理変数を使ったデータフローに基づいている。 我々の実験によって、並行性の明示でユーザが アプリケーション資源を制御しやすくなることが分かった。 このため、言語はメソッド定義の中で逐次状態のスレッドを作らずに、 効率的で表現力のあるオブジェクト指向モデルを持つ。 また、伝統的な例外処理構造と、最新だが最小でない 単純なデバッグモデルを言語に簡単に加えることができた。 現在のOzシステムの並行性は、ほとんどアプリケーションの論理的並行性を モデル化するのに使われ、潜在的並行性を増やすためには使われない。
| 実体の種類 | プロトコル | 実体 | |
|---|---|---|---|
| 状態なし | 再現性 | 積極的 消極的 |
レコード、手続き、クラス オブジェクトレコード |
| 単一代入 | 削除 | 積極的 消極的 |
論理変数 論理変数 |
| 状態変化する | 局所化 | 機動性を持つ 移動しない | セル、オブジェクト状態 ポート、スレッド |
Distributed Ozは、Ozと同じ言語意味論を持つ。 Distributed Ozは言語の実体全てに分散意味論を定義することによって、 アプリケーションの機能と分散構造を分ける。 分散意味論は、サイトの概念を考慮した言語意味論の拡張である。 分散意味論の定義は、計算が複数サイトに分割されたとき ネットワーク操作を呼び出すものである。 言語の実体は、基本的な3種類に分類することができる（表3を見よ）：
各実体に対するネットワーク操作は予測可能で（注5）、 プログラマにネットワーク通信を管理する能力を与える。 この節の残りでは、言語実体を実装するのに使われる 4種の分散アルゴリズムを提示する。 第4.1節ではアクセス構造の概念を導入し、 複数サイトからアクセス可能な言語実体をモデル化する。 言語実体の分散行動は、そのアクセス構造のノード間の プロトコル、すなわち分散アルゴリズムとして定義される。 第4.2節では分散論理変数の長所を説明し、 変数削除プロトコルによる実装を示す。 第4.3節と第4.4節では、オブジェクトレコード用の消極再現 プロトコル（第4.3節で述べる）とオブジェクト状態用の機動状態 プロトコル（第4.4節で述べる）を使って、予測可能なネットワーク 行動をとる機動オブジェクトを作る方法を示す。 論理変数とオブジェクトのネットワーク行動は、 Distributed Ozの設計ポリシーを最も明確に表す。 最後に第4.5節で、アクセス構造管理の下にある 分散ゴミ集めアルゴリズムを述べる。 もっと詳しい情報は、[40, 39, 10]を参照して欲しい。
| 変数（未束縛） | レコード（とフィールド） | スレッド（と参照） |
| セル（状態ポインタ） | 手続き（と外部参照） |
分散グラフの概念を使って、 単純だが厳密に分散実行をモデル化する。 この節の説明は、本記事を理解するのに十分完全である。 システムの任意の実行状態から、2つの段階を経て分散グラフを得る。 第1歩は分散とは独立である。 実行状態をモデル化したグラフ、すなわち言語グラフの中では、 オブジェクトを除く各言語実体は1つのノードに相当する（図10を見よ）。 オブジェクトは複合実体であり、第4.3節で説明する。
第2歩では、サイトの概念を導入する。 サイトの有限集合を考え、各ノードをサイトに加えてみよう（図11を見よ）。 あるノード、例えばN2が少なくとも1つ以上の 他サイトノードから参照されていたら、 N2はノードの集合、例えば {P1,P2,P3,M} に写像される。 この集合を、元のノードのアクセス構造と呼ぶ。 アクセス構造は、 元のノードを参照するサイト毎に1つあるプロクシノードPiと、 構造全体の管理ノードMが1つ、からなる。 その結果得られる、ローカルノードと必要に応じて アクセス構造を含むグラフを、分散グラフと呼ぶ。 本記事のプロトコル実行のほとんどは、この記法を使う。
各アクセス構造は、システム全体で重複しない全域アドレスをもらう。 全域アドレスは管理サイトをエンコードしたもので、 対（全域アドレス、サイト）がプロクシノードを識別するために使われる。 各サイトで、プロクシを参照する表を引くのに全域アドレスが使われる。 このため、各サイトは最大1つのプロクシを持つという不変条件を持つことができる。 アクセス構造のノード間では、メッセージが送られる。 サイトによって、送信サイトから受信サイトへメッセージが送られる。 メッセージ本体中の全ての参照は、受信サイト上のノードへの参照である。 受信ノードは、アクセス構造の全域アドレスによって識別される。 メッセージが到着すると、受信ノードはサイトの表によって引かれる。
手続きとその他の値（レコード、数、など）は積極的にコピーされ、 アクセス構造を生じることはない（注6）。 手続きは1度だけサイトに送られ（注7）、サイト上のコピーは1つである。 手続きは閉包とコードブロックからなり、 それぞれ全域アドレスを1つもらう。 メッセージは全域アドレスだけを含み持ち、 到着するとすぐに足りないコードブロックと閉包を要求する。
論理変数は、実行順序を強制することなく計算の依存性を表す。 この性質は、分散計算における利点である：
このような利点を現実化する実践分散アルゴリズム、すなわち 有理木の単一化は論理変数の束縛に使われる[10]。 このアルゴリズムは、Distributed Ozの2つの部分に効率的に実装されている： ローカルアルゴリズムと分散アルゴリズムに。 ほとんどの単一化はローカルに行なわれる。 分散アルゴリズムは変数削除、すなわち束縛のみに用いられる。 ここで簡単に説明する。
論理変数に対する2つの基本操作は束縛と、束縛されるまで待つことである。 論理変数Xは、データ構造か他の変数に束縛される。 アルゴリズムは、どちらの場合も同じである。 Xに対して多くの束縛が（1つまたは複数のサイトから）並行に始まると、 1つだけが成功する。 その後、Xが束縛された実体に対して他の束縛を試みる。 デフォルトでは、束縛は積極的に行なう。 つまり、Xを知っている全てのサイトに、新しい値がすぐさま送られる。 このため、束縛された変数はシステムから消えても良いことが保証されている。
例を挙げて束縛アルゴリズムを説明する。 分散グラフにおいて、論理変数はアクセス構造で表される。 図12では、ある変数が3つのサイトに存在している。 サイト2のスレッドが、変数のプロクシに束縛を教え（メッセージ1）、 ブロックされる。 プロクシノードは、管理ノードに変数の束縛を頼む（メッセージ2）。 管理ノードは、全てのプロクシに束縛を教える（メッセージ3）、 すなわち積極的に変数を削除する。 プロクシは束縛を受けとると、全ての待ちスレッドに教える（メッセージ4）。 すると、スレッドは実行を続ける。
論理変数を表すのにアクセス構造を持ち出す必要はない。 もっと高級な、等式と記憶の概念を使う方がずっと理解しやすい。 図13の左半分は集中構成を表し、右半分は分散構成の一例を表している。 各構成は、等式の集合と記憶を持つ。 等式は束縛の実行を要求する。 記憶は変数と、もしあればその束縛を保持する。 分散の場合、各サイトは等式の集合と記憶を持つ。 サイトが1つの場合、分散アルゴリズムは集中アルゴリズムと等価である。 変数は、1つ以上のサイトに存在することができる。 各サイト上の出現は、「プロクシ」と呼ばれる。 変数が束縛されると、各プロクシは同じ束縛を持つ。 図13において、変数Yはサイト2, 3でf(Y1)に束縛される。
アルゴリズムは、アトミックな段階を経て実行される。 各段階で、等式がアルゴリズムを始める、または内部段階が行なわれる。 内部段階では、あるサイトの状態が変わるか、 サイト間でメッセージが送受される。 1つの束縛を完成するには、多くの段階が必要な場合もある。 あらゆる実体は、完成までの段階で多くの束縛を必要とする可能性がある。
分散操作の基本は、全てのプロクシに束縛を送ることである。 例えば、Y1=3という束縛は、Y1の全てのプロクシに3を送る。 この結果、全てのサイトで束縛Y1←3が生じる（図14を見よ）。 これは、1つのサイトを変数の「所有者」とすることで実装されている。 所有者は、プロクシから束縛要求を受けとる。 所有者は最初の要求を承諾し、その値を全てのプロクシに送る。 他の要求は無視される。
論理変数は異なる分散行動を取ることもできるが、 その場合でもネットワーク透明性は満たしている。 上述したように、論理変数はデフォルトでは積極的である。 これは、遅延耐性とサードパーティの独立を極大化する。 しかし、束縛を不要なサイトに送ってしまう可能性がある。 論理変数が消極的であるとは、サイトに要求された時に （つまり、スレッドが値を必要とした時に）のみ、値を送ることである。 消極変数はメッセージの複雑さが軽く、メッセージの数が少なくて済む。 いくつかの場合、例えば短絡技法を使ったバリア同期では、消極変数が好ましい。 積極変数と消極変数は同じ分散単一化アルゴリズムに従い、 ただ1つ、ある簡約ルールのスケジューリングが異なる[10]。 現在Distributed Ozは、積極変数しか提供していない。 両方を提供するには、小さな変更が必要である。 そうすれば、プログラマの注記によって、 変数が積極的か消極的か決めることができるようになる。
Distributed Ozのオブジェクトは、軽量オブジェクト移転プロトコルに従い、 集中オブジェクトの意味論を保っているので、 ネットワークの振る舞いを正確に予測することができる。 機動オブジェクトを持つ既存のシステムは、このようなアルゴリズムを使っていない。 前方参照の連鎖によってオブジェクトを移動している [24, 15, 5]。 メッセージが送られるか、所定時間が過ぎると、この連鎖は短絡される。 この方法でオブジェクトを移動すると、平均はネットワークホップ数で良いが、 最悪の場合ホップ数で非常に悪い (?? This gives good average-case number of network hops when moving an object, but very bad worst-case number of hops. ??)。 Distributed Ozの設計方針は、サードパーティ依存をなくすことである。 このため、前方参照の連鎖は承諾できない。 その代わりに我々が設計した以下の機動プロトコルは、 最悪の場合の振る舞いを大きく改善する。
class Account
attr bal:0
meth trans(Amt)
bal<- @bal+Amt
end
meth getBal(B)
B = @bal
end
end
A={New Account Trans(100)}
分散グラフにおいてオブジェクトは、オブジェクトレコード、 手続き（メソッド）を保持するクラスレコード、セル（状態ポインタを保持する）、 オブジェクトの状態を保持するレコードからなる複合実体として表される。 オブジェクトの分散行動は、これらの部分の行動からなる。 図15は、1つの属性balと2つのメソッドtrans, getBalを持つオブジェクトAである。 オブジェクトは、3つのフィールドを持つオブジェクトレコードとして表される。 stフィールドは状態ポインタを保持し、オブジェクトの状態レコードを指す。 clフィールドが保持するクラスレコードは、 メソッドを実装する手続きtrans, getBalを保持する。 idフィールドは、オブジェクトの重複しない識別子theNameを保持する。 オブジェクトレコードとクラスレコードは変更できない。 しかし、状態ポインタの内容を変えることによって、状態レコードは変更できる。
図16は、サイト1ローカルなオブジェクトAである。 他サイトからAへの参照はない。 図17は、遠隔参照を1つ持つオブジェクトAである。 オブジェクトはアクセス構造の一部となり、 管理ノードがサイト1に、プロクシノードがサイト2にある。 Aを参照するメッセージがサイト1から出ていくと、ローカルオブジェクトAは グローバル（つまり、遠隔参照された）オブジェクトに変形される。 メッセージが出ていく時に、管理ノードMaが生成される。 Aを参照するメッセージがサイト2に着くと、 そこでプロクシノードPa2が生成される。
図18は、スレッドTがサイト2からAを呼び出したところである。 最初サイト2にあるのはプロクシPa2だけで、オブジェクト自体はない。 プロクシは、管理ノードにオブジェクトレコードのコピーを頼む。 すると、管理ノードMcとプロクシPc1を持つ、セルのアクセス構造が生成される。 クラスレコードは積極的にコピーされ、無重複の全域アドレスを持たない。 クラスレコードとセルプロクシを保持したメッセージが、サイト2に送られる。 オブジェクトの状態は、サイト1に残る。
図19は、メッセージが着いたところである。 セルの2番目のプロクシPc2が生成される。 クラスレコードがサイト2にコピーされ、プロクシPa2はオブジェクトレコードAになる。 サイト表が参照するのはオブジェクトレコードになる。 すると機動状態プロトコル（第4.4節を見よ）は、 自動的にセルをサイト2に運ぶ。 サイト表のおかげで、ネットワーク操作はこれだけであり、 以降、オブジェクトを参照するサイト2へのメッセージは オブジェクトレコードのローカルコピーを直接参照する。
図20は、セルがサイト2へ運ばれた後である。 サイト2で新しい状態State2が生成され、 メソッドが終わるとオブジェクトの状態が更新される。 古い状態State1はサイト1に存在し続けるが、もうセルに指されていない。
図21は、サイト1が再びオブジェクトを呼んだところである。 セルはサイト1に帰る。 サイト1で新しい状態State3が生成され、 メソッドが終わるとオブジェクトの状態が更新される。 古い状態State2はサイト2に存在し続けるが、もうセルに指されていない。
ここまでに面白いことがいくつかあった。 第1に、オブジェクトはいつもローカルに実行される。 セルはいつもメソッドが実行を始める前にローカルに移され、 オブジェクトがロックされメソッドを実行している間、 ローカルに留まることが保証されている。 第2に、クラスコードは1つのサイトに1度しか運ばれない。 セルだけが、最初の移動の後も動き回る。 このため、オブジェクトの機動は非常に軽量になっている。 第3に、オブジェクトに対する全ての要求は、セルの管理ノードによって直列化される。 このためプロトコルは単純化されたが、管理サイト依存が生じる。 もっと複雑なプロトコル（ここでは挙げない）なら、 この依存性をなくすことができる[40]。
第4.3節で示した自由機動オブジェクトは、 いくつかの分散アルゴリズムを使う複合実体だった。 オブジェクトレコードは1度だけ消極的に （オブジェクトが最初に呼び出された時に）コピーされ、 メソッドもそれにしたがってコピーされ、 オブジェクトの状態ポインタは要求されたサイト間を動き回る。 オブジェクトのセルアクセス構造の状態ポインタはいつでも、 1つのプロクシにあるか、2つのプロクシ間を移動中かである。 状態ポインタを動かすプロトコル、すなわち機動状態プロトコルは特に面白い。 このプロトコルは、状態の順序の一貫性を保証しなければならない。 連続した状態が異なるサイトにあれば、 状態ポインタをサイト間でアトミックに運ぶ必要がある。 状態ポインタを必要とするサイトは状態ポインタの管理ノードに要求し、 管理ノードは状態ポインタを持つサイトにコマンドを送る。 このため、管理ノードは小さな情報、すなわち状態ポインタを保持するサイト を覚えておく必要がある[40]。
図22は、2つのサイトから参照されているセルCである。 セルの状態ポインタはサイト1にあるが、 スレッドTが操作 {Exchange C X Y} を行なうと、サイト2が状態ポインタを要求する。 このことから分かるように、交換はアトミックに行なわれ、 Yに新しい値（すなわちState2）を入れ、Xを古い状態State1に束縛する。
図23では、(a) プロクシPc2が状態ポインタを要求して 管理ノードMcにGetメッセージを送り、(b) 管理ノードが 状態ポインタを持つ（ことになっている）プロクシPc1に Forwardメッセージを送っている。 このため、管理ノードはすぐに他の要求を受け付けることができる。 状態ポインタの移送が終わるまで待つ必要はない。
図24は、Pc1がPc2に古い状態State1を保持している Contentメッセージを送ったところである。 古い状態はまだサイト1に存在しているが、もうPc1に指されていない。 図25は最後の状況である。 Pc2は状態ポインタを持ち、State2を指している。 XはState1に束縛される。
このプロトコルによって、ネットワークの振る舞いを予測できる。 状態ポインタがサイトを渡るには、最大3ネットワークホップあれば良い。 管理ノードが送信元または受信先サイトにあれば、2で済む。 状態ポインタが要求サイトにあれば、0である。 プロトコルは時系列の一貫性を保っており、 セル交換（状態ポインタの更新）は全域で一貫した順序で行なわれる。
言語実体が遠隔参照されると、アクセス構造が自動的に生成、管理される。 異なるサイト上のノード間でやりとりされたメッセージが 他ノードへの参照を保持していればいつでも、こうしたことが起こる。 ローカルノードへの参照があると、 メモリ管理層はローカルノードをアクセス構造に変換する。 これを、ローカルノードが全域化されたという。 メッセージがネットワーク上にある間、 アクセス構造は1つの管理ノードと1つのプロクシからなる。 メッセージが受信先サイトに着くと、そこに新しいプロクシが生成される。 アクセス構造は、ゴミ集めによって小さくなったり完全に消えたりする。
分散ゴミ集めは、協調する2つの機構によって実装されている： 各サイトの局所ゴミ集めと、全域アドレスを返却させる分散クレジット機構である。 あるノードがサイト上で参照されなくなると、 局所ゴミ集めがクレジット機構に教える。 逆に、あるノードが遠隔参照されなくなると、 クレジット機構が局所ゴミ集めに教える。 局所ゴミ集めは、他サイトに依存せずいつでも呼び出すことができる。 局所ゴミ集めは、中断していないスレッドノードから到達可能なノードや、 遠隔参照されたノードを根とする。
ノードが遠隔参照されなくなると、全域アドレスが返却される。 これは、クレジット機構が局所ゴミ集めに教えてもらうことで行なわれる。 このスキームは、サイト間に渡るサイクルで捨てられたゴミを回復する。 我々のシステムで、異なるオブジェクトやセルの間に出現するのは サイト間に渡るサイクルのみである。 レコードと手続きは共に再現可能なので、 その間のサイクルは1つのサイトに局所化されている。 クレジット機構は、前述の参照数スキーム[28]の メモリ、ネットワーク効率の悪さに悩まされない。
クレジット機構の基本的なアイデアを簡単にまとめる。 各全域アドレスを作る整数（貸し数）は、 クレジット番号を表し、他サイトやメッセージに公開される。 全域アドレスを保持するサイトやメッセージは、 最低1つ全域アドレスのクレジットを持たなければならない。 生成サイトは所有者と呼ばれる。 他サイトは借り手と呼ばれる。 あるノードが遠隔参照されているのは、貸し数が零でない時である。
最初は借り手がいないので、所有者の貸し数は零である。 所有者はそのノードを参照するサイトやメッセージにクレジットを貸し、 貸したクレジットの個数分だけ貸し数を増やす。 メッセージが借り手に届くと、そのクレジットが既存のクレジットに加えられる。 メッセージが所有者に届くと、そのクレジットが所有者の貸し数から引かれる。 借り手がノードを局所参照しなくなると、全てのクレジットが所有者に返される。 これは、局所ゴミ集めによって行なわれる。 所有者の貸し数が零になると、 そのノードは局所参照しかされていないので、全域アドレスが返却される。
セルアクセス構造の場合を考えよう。 管理サイトは所有者であり、セルプロクシを持つ他の全サイトは借り手である。 プロクシは、局所参照されなくなると消える。 そして、そのクレジットが管理者に返される。 そのプロクシが状態ポインタを保持していたら、 状態ポインタも管理サイトに返される。 セルアクセス構造中のサイト間サイクルが消えることに注意せよ。 管理者が全てのクレジットを返却すると、セルは局所セルに戻る。 局所セルは、局所参照されていなければ返却される。 局所セルが（そのセルを参照するメッセージがネットワークを渡って） 全域セルに戻ると、返却したものと無関係に新しい管理ノードが生成される。
分散システムがオープンであるとは、独立に実行中のアプリケーションが 面白い方法で相互に干渉できることである[7]。 これは一般に、システムが共通基盤を共通のフレームワークや言語の形で提供し、 アプリケーションがそれを使って干渉できることである。 典型的な例は、情報交換用の共通情報フォーマットや、 電子商取り引き用の共通プロトコルなどである。 第1の要求は、ネット間で独立に実行を始めたアプリケーションが 接続を確立することができなければならない。 第2の要求は、 アプリケーションが新しく分散計算を始めることができるべきである。