Langphilia! / KL1 / Distributed KL1 / DKLIC4, 2001-10-01

DKLIC v4 (2001-06) における分散論理変数の資源管理


  1. DKLICとは
  2. 分散変数とは
  3. 分散GCの必要性
  4. DKLICの変数通信プロトコル
  5. 変数輸出入表のGC
  6. Generic Object
  7. 実装段階のロードマップ

DKLICとは

既存の分散プログラミング機構としては、次のようなものがある。

  1. ソケットは遠隔プロセスと通信するための機構である。 サービスを要求するクライアントと、サービスを提供するサーバから成る クライアント・サーバモデルに基づいている。 ソケットはBSDに由来するが、Cのソケットインタフェイスは System V系, Windowsへ移植され、実質標準化された。 Javaは、ソケットへのインタフェイスを言語レベルで定義したことによって、 Java実行系の動作する環境であれば OS非依存でソケットを利用できることを保証した。
  2. RPC (Remote Procedure Call) やJava RMIは、 手続き・関数呼び出しの形で遠隔のサービスを受ける機構である。 ソケットへの入力が手続き・関数の引数、 ソケットからの出力が関数の値としてある程度透明化される。 透明化が不完全であるのは、 オブジェクトに対して参照・逆参照操作が明示されるためである。
  3. CORBAやJiniは分散オブジェクトを管理し、遠隔のサービスを受ける機構である。 RPCとの本質的な差は、ネーミング(登録・検索)サービスによる capabilityの取得にあると思われる。集中サーバのない完全なP2Pを達成するには、 最初に接続するホストを 個々のサーバント(=サーバ+クライアント)が自力で検出する必要があるが、 P2Pモデルで有名なNapsterもGnutellaも*完全には*この条件を満たしていない。 (DHCPのゲートウェイ自動検出は、この条件を満たしている?)
  4. モバイルエージェントは、エージェント(実行状態を含む プロセス)の移動によって、通信を透明化する機構である。 RPCやORBとの差は、通信されるメッセージが単なるデータではなく プロセスである点と、エージェントが自律的に計算・移動を行う点にある。

これらの分散プログラミング機構の既存実装は、 CやJavaなど手続き型のプログラミング言語に基づいており、 参照のネットワーク透過性が不十分である。 Distributed-Ozは、並行論理プログラミングの流れを汲んでおり ネットワーク透過であるが、KL1言語と異なり静的解析を採り入れていない。 静的解析は分散実行コードの最適化や証明に大きく役立つと期待できる。

DKLICは、KLIC処理系上の分散ミドルウェアである。 DKLIC自体はKLIC/KL1(+C)言語によって分散APIを実装したものであり、 KLIC翻訳系によって実行ライブラリを生成する。 KLIC実行系をノード内の下位処理系とし、 DKLIC実行系がノード間通信を処理することによって、 ネットワーク透過な並行論理・並行制約プログラミングを実現する(希望)。 DKLICは、動的プロセス生成・動的ネットワーク構成を可能にする 最低級論理ネットワーク=極小分散プログラミング機構を目指している。

分散変数とは

KL1言語におけるデータは項によって表される。 項とはLispで言うS式であり、ツリー型のデータ構造である。 KLIC/KL1言語の項は、次の4種類である。

  1. 原子値 ⊃ 記号, 整数
  2. 複合値 ⊃ コンス, ファンクタ
  3. Generic Data Object ⊃ float, vector, string, module, predicate, goal, ..
  4. 変数 ⊃ 単なる未定義変数, {中断原因変数 ⊃ 中断ゴール, Generic Consumer/Generator Object}

これらのうち前3種は単なる値であるので、KL1項を認識する字句解析器と その結果からツリー構造を生成する構文解析器が相手方にあれば、 項を表現する文字列そのままをネットワークに流して良い。

しかし、KL1言語の変数は単なる単一代入変数ではなく、 未定義値を取り得る論理変数であるので、変数を輸出入・束縛するプロトコルと 文脈依存の変数輸出入表が通信当事者間に必要である。 これら輸出入された変数を分散変数と呼ぶ。

分散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の変数通信プロトコル

  1. 下位ネットワークはTCP/IP、 パケットの紛失や追い越しがない事を前提とする。 ソケット、従ってクライアント・サーバモデルの使用を仮定する。
  2. まず、クライアントがサーバへ文字列「DKLICP 2001-10 client\n」 (「\n」はLineFeed)を送信する。 この文字列を受けとったサーバは、 クライアントへ文字列「DKLICP 2001-10 server\n」を送信する。 それ以降、クライアント・サーバは以下の規則に従ってKL1項をやりとりする。 個々のKL1項は文字列「.\n」(ピリオド、LineFeed)によって終端する。 この文字列は終端子であって項の一部ではない。
  3. 変数以外の項は、その項を表現する文字列そのままをネットワークに流す。 輸入側は文字列を字句解析・構文解析し、項のツリー構造を復元する。 複合値は、その要素に対して再帰的に規則を適用する。
  4. 新しい変数 X を輸出する時は「NEW_#」という文字列をネットワークに流す。 ここで、# は未使用の非負整数である。 輸出側・輸入側は (#,X) を輸出入表に登録する。 それ以降、# が X のIDとなる。
  5. 分散変数 X を送信する時は「_#」という文字列をネットワークに流す。 ここで、# は X のIDである。
  6. 分散変数 X がノード内で具体値 Y に具体化されたら、 具体化ゴール「_#=Y」をネットワークに流す。 ここで、# は X のIDである。 送信側・受信側は (#,X) を輸出入表から抹消する。 それ以降、# は X のIDではなく、未使用となる。
  7. 分散変数 X がノード内で他の分散変数 Y と単一化されたら、 単一化ゴール「_#X=_#Y」をネットワークに流す。 ここで、#X, #Y はそれぞれ X, Y のIDであり、#X>#Yである。 送信側・受信側は (#X,X) を輸出入表から抹消する。 それ以降、#X は X のIDではなく、未使用となる。
  8. 分散変数 X への参照がノード内に無くなったら、 GCメッセージ「_#=_」をネットワークに流す。 ここで、# は X のIDである。 送信側・受信側は (#,X) を輸出入表から抹消する。 それ以降、# は X のIDではなく、未使用となる。

変数輸出入表のGC

DKLICの分散GCはノード内GCとノード間GCから成る。 ノード内GCはKLIC実行系 (copying GC) に任せる。 ノード間GCは、ノードを跨った分散変数を構成する資源のGCを行う。 分散変数 X の一部を成すノード内変数を X' とすると、

従って、ノード間GCは X' のノード内GCを検出しなければならない。 KLIC実行系はGCをユーザプロセスに通知しないので、 ノード間GCにはKLIC実行系組み込みのシステムプロセスか、 ユーザプロセスとしての制限を受けないGeneric Objectを利用しなければならない。 Generic ObjectはKLIC処理系に手を加えずに KLIC/KL1言語を拡張するための機構であるので、 KLIC処理系自体の改造が必要でなければGeneric Objectを利用すべきである。

Generic Object

vart2.c

分散変数の個数(変数輸出入表のサイズ)は動的に増減する。

実装段階のロードマップ

  1. 未定義変数同士の単一化を検出しない。 _#X=_#Y を送信するのは X (=Y) への参照が無くなった時のみ。 ノード内から X への参照が無くなった時、 X=Y であるような分散変数 Y があれば _#X=_#Y, _#Y=_ を、 そうでなければ _#X=_ を送信する。 この版は正しく動くが、不要な (#X,X) によって空間を浪費し、 X に関して無駄な通信が起こる可能性がある(append/3など)。
  2. 未定義変数同士の単一化を検出し、 早期に単一化ゴールを送信する。 未定義変数同士の単一化を検出できるようにKLICを改造すると、 この版の実装が容易になるかも知れない。 分散変数同士の単一化を検出するために、あれば嬉しいかも知れないガード述語は

Copyright 2001, TAKAGI Yusuke.