Langphilia! /
KL1 /
Distributed KL1 /
DKLIC4, 2001-10-01
DKLIC v4 (2001-06) における分散論理変数の資源管理
- DKLICとは
- 分散変数とは
- 分散GCの必要性
- DKLICの変数通信プロトコル
- 変数輸出入表のGC
- Generic Object
- 実装段階のロードマップ
DKLICとは
既存の分散プログラミング機構としては、次のようなものがある。
- ソケットは遠隔プロセスと通信するための機構である。
サービスを要求するクライアントと、サービスを提供するサーバから成る
クライアント・サーバモデルに基づいている。
ソケットはBSDに由来するが、Cのソケットインタフェイスは
System V系, Windowsへ移植され、実質標準化された。
Javaは、ソケットへのインタフェイスを言語レベルで定義したことによって、
Java実行系の動作する環境であれば
OS非依存でソケットを利用できることを保証した。
- RPC (Remote Procedure Call) やJava RMIは、
手続き・関数呼び出しの形で遠隔のサービスを受ける機構である。
ソケットへの入力が手続き・関数の引数、
ソケットからの出力が関数の値としてある程度透明化される。
透明化が不完全であるのは、
オブジェクトに対して参照・逆参照操作が明示されるためである。
- CORBAやJiniは分散オブジェクトを管理し、遠隔のサービスを受ける機構である。
RPCとの本質的な差は、ネーミング(登録・検索)サービスによる
capabilityの取得にあると思われる。集中サーバのない完全なP2Pを達成するには、
最初に接続するホストを
個々のサーバント(=サーバ+クライアント)が自力で検出する必要があるが、
P2Pモデルで有名なNapsterもGnutellaも*完全には*この条件を満たしていない。
(DHCPのゲートウェイ自動検出は、この条件を満たしている?)
- モバイルエージェントは、エージェント(実行状態を含む
プロセス)の移動によって、通信を透明化する機構である。
RPCやORBとの差は、通信されるメッセージが単なるデータではなく
プロセスである点と、エージェントが自律的に計算・移動を行う点にある。
これらの分散プログラミング機構の既存実装は、
CやJavaなど手続き型のプログラミング言語に基づいており、
参照のネットワーク透過性が不十分である。
Distributed-Ozは、並行論理プログラミングの流れを汲んでおり
ネットワーク透過であるが、KL1言語と異なり静的解析を採り入れていない。
静的解析は分散実行コードの最適化や証明に大きく役立つと期待できる。
DKLICは、KLIC処理系上の分散ミドルウェアである。
DKLIC自体はKLIC/KL1(+C)言語によって分散APIを実装したものであり、
KLIC翻訳系によって実行ライブラリを生成する。
KLIC実行系をノード内の下位処理系とし、
DKLIC実行系がノード間通信を処理することによって、
ネットワーク透過な並行論理・並行制約プログラミングを実現する(希望)。
DKLICは、動的プロセス生成・動的ネットワーク構成を可能にする
最低級論理ネットワーク=極小分散プログラミング機構を目指している。
分散変数とは
KL1言語におけるデータは項によって表される。
項とはLispで言うS式であり、ツリー型のデータ構造である。
KLIC/KL1言語の項は、次の4種類である。
- 原子値 ⊃ 記号, 整数
- 複合値 ⊃ コンス, ファンクタ
- Generic Data Object ⊃
float, vector, string, module, predicate, goal, ..
- 変数 ⊃ 単なる未定義変数,
{中断原因変数 ⊃ 中断ゴール, Generic Consumer/Generator Object}
これらのうち前3種は単なる値であるので、KL1項を認識する字句解析器と
その結果からツリー構造を生成する構文解析器が相手方にあれば、
項を表現する文字列そのままをネットワークに流して良い。
しかし、KL1言語の変数は単なる単一代入変数ではなく、
未定義値を取り得る論理変数であるので、変数を輸出入・束縛するプロトコルと
文脈依存の変数輸出入表が通信当事者間に必要である。
これら輸出入された変数を分散変数と呼ぶ。
- KL1項の文字列表現 → KLIC.info
- KLIC/KL1項のメモリ表現 → 関田大吾, Inside KLIC
分散GCの必要性
分散GCが無ければ、
未定義変数同士を単一化して終了したプロセスへ無駄な通信が起こる。
+------------+ X=[] +---------+
| append( |----------->| | append(X,Y,Z) :- X=[] |
| [1,2,..], | Y=[a|Y1] | Z=Y | Z = Y.
| [a,b,..], |----------->| | append(X,Y,Z) :- X=[A|X1] |
| Z ) | Z=[a|Z1] | | Z = [A|Z1],
| |<-----------| | append(X1,Y,Z1).
+------------+ +---------+
X=[ ] を受け取った瞬間に Z=Y を送り出せば良いか?
→ X=[ ] を受け取る前に Y=[a,..] を受け取ってしまったら?
--> X = [1|X1] X を抹消, X1を登録
<-- Z = [1|Z1] Z を抹消, Z1を登録
--> Y = [a|Y1] Y を抹消, Y1を登録
--> X1 = [2|X2] X1を抹消, X2を登録
<-- Z1 = [2|Z2] Z1を抹消, Z2を登録
--> Y1 = [b|Y2] Y1を抹消, Y2を登録
--> X2 = [] X2を抹消
<-- Z2 = [a,b|Y2] Z2を抹消 分散変数同士の単一化でない
分散変数の出現が線形(読み書き1本ずつ)であり、
X=[ ] を受け取るまで Y=[a,..] を受け取らない場合は、
小手先の誤魔化しが効く。
--> X = [1|X1] X を抹消, X1を登録
<-- Z = [1|Z1] Z を抹消, Z1を登録
--> X1 = [2|X2] X1を抹消, X2を登録
<-- Z1 = [2|Z2] Z1を抹消, Z2を登録
--> X2 = [] X2を抹消
<-- Z2 = Y Z2を抹消, Yを抹消(特別な場合)
しかし、線形でなくなるとダメ。
append(X,Y,Z) :- X=[] |
print(Y),
Z = Y.
DKLICの変数通信プロトコル
- 下位ネットワークはTCP/IP、
パケットの紛失や追い越しがない事を前提とする。
ソケット、従ってクライアント・サーバモデルの使用を仮定する。
- まず、クライアントがサーバへ文字列「DKLICP 2001-10 client\n」
(「\n」はLineFeed)を送信する。
この文字列を受けとったサーバは、
クライアントへ文字列「DKLICP 2001-10 server\n」を送信する。
それ以降、クライアント・サーバは以下の規則に従ってKL1項をやりとりする。
個々のKL1項は文字列「.\n」(ピリオド、LineFeed)によって終端する。
この文字列は終端子であって項の一部ではない。
- 変数以外の項は、その項を表現する文字列そのままをネットワークに流す。
輸入側は文字列を字句解析・構文解析し、項のツリー構造を復元する。
複合値は、その要素に対して再帰的に規則を適用する。
- 新しい変数 X を輸出する時は「NEW_#」という文字列をネットワークに流す。
ここで、# は未使用の非負整数である。
輸出側・輸入側は (#,X) を輸出入表に登録する。
それ以降、# が X のIDとなる。
- 分散変数 X を送信する時は「_#」という文字列をネットワークに流す。
ここで、# は X のIDである。
- 分散変数 X がノード内で具体値 Y に具体化されたら、
具体化ゴール「_#=Y」をネットワークに流す。
ここで、# は X のIDである。
送信側・受信側は (#,X) を輸出入表から抹消する。
それ以降、# は X のIDではなく、未使用となる。
- 分散変数 X がノード内で他の分散変数 Y と単一化されたら、
単一化ゴール「_#X=_#Y」をネットワークに流す。
ここで、#X, #Y はそれぞれ X, Y のIDであり、#X>#Yである。
送信側・受信側は (#X,X) を輸出入表から抹消する。
それ以降、#X は X のIDではなく、未使用となる。
- 分散変数 X への参照がノード内に無くなったら、
GCメッセージ「_#=_」をネットワークに流す。
ここで、# は X のIDである。
送信側・受信側は (#,X) を輸出入表から抹消する。
それ以降、# は X のIDではなく、未使用となる。
- ここでのクライアント・サーバモデルはつなぐ側とつながれる側の区別であって、
サービスの提供方向は問題でない。どうせ分散変数によって、
動的に論理ネットワークを構成するのだから。
P2Pのサーバントならば相対的につなぎつながれ合う。
- 「DKLICP」はプロトコル名、「2001-10」はバージョン。
- 将来の拡張 →
XML対応。字句解析・構文解析を不要・容易にする具体値通信プロトコル。
記号輸出入管理 ⊂ 項輸出入cache。
- 重複のないIDの割り付け → GUID ?
- 単一化ゴール _#X=_#Y はどちらが X,Y でも理論上は構わないが、
#X>#Y としておくと常に小さな数が使われやすくなる →
輸出入表=配列のインデクスが小さな非負整数に集中しやすい。
- NEW が必要なのは、X を抹消するメッセージが相手に届く前に
相手が X を送信する可能性があるためである。
- 輸出入表に (#,X) が登録されていない時に _# を受信したら、
それは受信側で抹消した X が送信側で抹消される前のメッセージである。
このようなメッセージを正しく解釈するために、抹消メッセージの送信側は
次の NEW_# を受信するまで「抹消」した (#,X) を保持しておかなければならない。
X (#,X) (#,X) X=a
X (#,X) msg(_#) --> <-- _#=a ( , ) X=a
X (#,X) _#=a <-- --> msg(_#) ( , ) X=a msg(a)と解釈しなければならない
X=a ( , ) ( , ) X=a
従って、# を未使用として即座に再利用すると、ID重複の恐れがある。
ストリームのIDをコンスのcdrに即時再利用するには、
同一IDについて新旧2つの状態を記憶しなければならない可能性がある。
(入出力モード解析によって、
状態記憶の省略の安全性を保証することができる場合がある。
要するに、同一IDの異なる状態を含むメッセージがすれ違わなければ良い。)
ストリーム X = [a,b,c, ..]
--> _#X = [a|_#X]
--> _#X = [b|_#X]
--> _#X = [c|_#X] 安全 ← パケットの追い越しはない
--> _#X = [a|_#X]
<-- _#X = [b|_#X]
--> _#X = [c|_#X] 安全(同期通信)
_#X=[a|_#X] --> <-- _#X=[b|_#X]
_#X=[b|_#X] <-- --> _#X=[a|_#X] 不安全
- 抹消メッセージの受信側は (#,X) を即座に抹消して良い
← パケットの追い越しはない。
抹消メッセージに対する返事として _#=_ を送信してやると、
抹消メッセージの送信側も (#,X) を本当に抹消して良いタイミングが分かる。
または、できるだけ早く次の NEW_# を送信してやるのが望ましい。
X (#,X) (#,X) X=a
X (#,X) msg(_#) --> <-- _#=a (#,a) X=a 本当には抹消しない
X (#,X) _#=a <-- --> msg(_#) (#,a) X=a msg(a)と解釈する
X=a ( , ) _#=_ --> (#,a) X=a
X=a ( , ) --> _#=_ (#,a) X=a
X=a ( , ) ( , ) X=a 本当に抹消して良い事が分かる
変数輸出入表のGC
DKLICの分散GCはノード内GCとノード間GCから成る。
ノード内GCはKLIC実行系 (copying GC) に任せる。
ノード間GCは、ノードを跨った分散変数を構成する資源のGCを行う。
分散変数 X の一部を成すノード内変数を X' とすると、
- 分散変数 X が抹消されると、
輸出入表から X' への参照が無くなり、ノード内GCが X' をGCする。
X" (#,X) <-- _#=a ( , ) X'=a
X" (#,X) _#=a <-- ( , ) X'=a 必要に応じてノード内GCが X' をGCする
X"=a ( , ) ( , ) X'=a
- ノード内から分散変数 X への参照が無くなると、
ユーザプロセス (mutator) から X' への参照が無くなり、
ノード間GCが分散変数 X を抹消する。
X" (#,X) (#,X) X'
X" (#,X) <-- _#=_ ( , )
X" (#,X) _#=_ <-- ( , )
従って、ノード間GCは X' のノード内GCを検出しなければならない。
KLIC実行系はGCをユーザプロセスに通知しないので、
ノード間GCにはKLIC実行系組み込みのシステムプロセスか、
ユーザプロセスとしての制限を受けないGeneric Objectを利用しなければならない。
Generic ObjectはKLIC処理系に手を加えずに
KLIC/KL1言語を拡張するための機構であるので、
KLIC処理系自体の改造が必要でなければGeneric Objectを利用すべきである。
Generic Object
- generic:new(variable_table, T,..)
- add(ID, X) 新しい分散変数 ID とノード内の参照 X を登録する
- get(ID, X) ノード内変数 X の分散変数としての ID を得る
- bind(ID, X) 分散変数 ID を具体値 X に具体化し、ID を抹消する
- unify(ID1, ID2) 分散変数 ID1, ID2 を単一化し、ID1 を抹消する
- kill(ID) 分散変数 ID を抹消する
分散変数の個数(変数輸出入表のサイズ)は動的に増減する。
- サイズを縮めるのはGC時のみで良い。
それ以外の時にサイズを縮めた輸出入表を再割り当てすると、
メモリの消費を早めてしまう。
- 自分でmalloc, reallocすると、KLICのGCの恩恵を受けることができない。
- オブジェクト内部に表本体を持つと、
サイズ変更=再割り当ての度にオブジェクト全体のアドレスが変わってしまう →
表本体はオブジェクトとは別に割り当て、その参照をオブジェクトに保持する。
- +1, -1 では再割り当てが頻繁過ぎる
→ ×2, ÷2 する (cf. java.util.Vector)。
実装段階のロードマップ
- 未定義変数同士の単一化を検出しない。
_#X=_#Y を送信するのは X (=Y) への参照が無くなった時のみ。
ノード内から X への参照が無くなった時、
X=Y であるような分散変数 Y があれば _#X=_#Y, _#Y=_ を、
そうでなければ _#X=_ を送信する。
この版は正しく動くが、不要な (#X,X) によって空間を浪費し、
X に関して無駄な通信が起こる可能性がある(append/3など)。
- 未定義変数同士の単一化を検出し、
早期に単一化ゴールを送信する。
未定義変数同士の単一化を検出できるようにKLICを改造すると、
この版の実装が容易になるかも知れない。
分散変数同士の単一化を検出するために、あれば嬉しいかも知れないガード述語は
- anyTwoElemsUnified(+Variables, -Index1, -Index2)
変数の配列 Variables の要素のうち2つが単一化されると、
単一化された2つの変数のインデクスを返す。
variable_table(V,S) :- anyTwoElemsUnified(V,I1,I2) | ..
alternatively.
variable_table(V,S) :- S = [add(X,ID) | S1] | ..
:
variable_table(V,S) :- S = [kill(ID) | S1] | ..
- unified(?X, -Result)
中断原因変数 X が他の中断原因変数と単一化されると、
variable:unbound/2 に準じた Result = {X,Address1,Address2} を返す。
u(X) :- unified(X, Result) | ..
variable_table(X1,..,Xn) :- u(X1), .., u(Xn).
Copyright 2001, TAKAGI Yusuke.