Langphilia! / KL1 / Distributed KL1 / DKLIC4, 2002-01-11

DKLIC v4: 宣言型広域分散計算環境

従来の分散型言語処理系や分散ミドルウェアは手続き型言語の拡張であり、 逐次プログラムのシームレスな分散化が行えない。
並行論理型言語KL1は、

• 本質的に並列・分散を含む並行処理を記述するための言語であり、 ネットワーク透過な静的意味論を持っているので、 逐次プログラムのシームレスな分散化が可能である。
• 並行論理型言語のうち最も単純なFlat GHCに基づいているので、
  • Flat GHCで蓄積された静的解析の適用が容易であると期待できる。
  • 単純な分散環境の基盤として強い候補である。

DKLICとは

DKLICはKL1に基づく宣言型広域分散計算環境である。

• 述語呼び出しまたはサーバへのメッセージによって 動的にプロセスが生成され、
• 述語呼び出しまたはサーバへのメッセージの引数として 共有変数を渡すことによって動的に通信路が生成される。

+----------+
|   O.............................
|   .      |                  +--.-------+
|   .      |                  |  .       |
|   ..O    |                  |  O       |
|     .    |                  |          |
|     .    |   +----------+ ......O      |
+-----.----+   |          | . |       O  |
      .        |  O.......... |          |
      .        |          |   +----------+
      .............O      |
      .        |          |
      ............O       |
               +----------+

+-+
| |  ホスト
+-+

O    プロセス
...  通信路

宣言型で楽なネットワークプログラミング。 非決定的な通信順序・同期の抽象化。

• 宣言型 vs 手続き型
• 変数 vs load/store
• イベントモデル vs read/write
• 分散論理変数 vs send/receive

ホスト間通信の仕組み

ユーザプロセスは実行系 DKLIC Runtime にホスト間通信を要求する。 Runtimeはユーザプロセスの要求に応じてソケットを管理する。

+----------+      +----------+
|          |      |          |
| Runtime ========== Runtime |
|    .     |      |     .    |
|    .     |      |     .    |
|    O     |      |     O    |
|          |      |          |
+----------+      +----------+

+-+
| |  ホスト
+-+

O    ユーザプロセス
...  通信路
===  ソケット

方針：単純な実装

• KLIC処理系を基盤として利用する。 KLIC処理系の広域分散機能は手続き型ソケットのみであるため、 拡張する必要がある。
• DKLIC処理系自体をKL1によって記述する。 移植性も期待している。
• 様々なサービス（分散機能）を提供する個々のサーバはなるべく小さくする。 Unixのコマンドのように、組み合わせて便利に使う。

DKLIC言語処理系の構成

KL1 program  KLIC  C program   cc   binary

                   Runtime/C -----> Runtime/bin
Runtime/KL1 -----> Runtime/C -----> Runtime/bin
user   /KL1 -----> user   /C -----> user   /bin

DKLIC Runtimeの組み込みサーバ

基本サーバ

• unix, klicio 拡張サーバへの接続
• dklic ユーザ定義サーバへの接続

拡張サーバ

• ServSock
• file_io
• merge
• naming ユーザ定義サーバの登録・検索
• exec 述語移送・実行
• sandbox 故障検出
• agentspace エージェント環境

Layers

1. machine, IP, ethernet
2. unix, TCP, socket
3. klicio, KLIC実行系
4. modeio, 変数表, 基本サーバ
5. 拡張サーバ
6. ユーザ定義サーバ
7. アプリケーション

組み込みサーバへのメッセージ

unix, klicio Stream

+stdin / +stdout / +stderr -Result

Result = normal(^File) 標準入力・出力・エラー出力 File: file_ioサーバを開く

+connect2 +inet(+Host, +Port) -Result

Result = normal(^I, ^O) 手続き型ソケット : file_ioサーバを開く

+bind +inet(+Port) -Result

Result = normal(^ServSock) 手続き型サーバソケット ServSock を開く

dklic Local

+bind +inet(+Port) -Result

Result = normal(^ServSock) 宣言型サーバソケット ServSock を開く

+connect +inet(+Host, +Port) -Result

Result = normal(^Sock) 宣言型ソケット Sock を開く

ServSock

+accept -Result

Result = normal(Sock) 宣言型/手続き型ソケット Sock を開く

+accept2 -Result

Result = normal(^I, ^O) 手続き型ソケット : file_ioサーバを開く

^file_io

• +getc -C
• +putc +C
• +fflush -Result
• +gett -Term
• +getwt -Result
• +putt / +puttq +Term
• +putwt / +putwtq +WrappedTerm
• +nl

naming

• +register +ServID +Host +Port ユーザ定義サーバを登録する
• +lookup +ServID -normal(-Host, -Port) サーバを検索する
• 近傍のサーバをキャッシュする永続プロセスである
• 登録されたサーバは定期的にnamingへpingして生存を報告する

        検索   通信
unix     --    low  Port -> ServSock  Host:Port -> file_io
dklic    --   high  Port -> ServSock  Host:Port -> Stream
naming  high   --   ID, Host:Port -> 0    ID -> Host:Port

exec

• KL1ソースを移送・コンパイル・実行する
• 述語の中間コードを移送・実行する

sandbox

• 通信に失敗したら、その接続（変数表1対）を切断して失敗を報告する

agentspace

• 未定

    N1                       N2
+-----------+           +-----------+
|  dklic ================== dklic   |
|    .      |           ..../ .     |
|    . L1   |    R...../|     .     |
|    .      ...../      |     . L2  |
|    ....../|           |     .     |
|    O........................O     |
+-----------+     S     +-----------+


:                       :
dklic(L1),              dklic(L2),
                        L2=[bind(SS)],
L1=[connect(R)@N2],     SS=[accept(S)|..],
S=[request(Answer)|..], service(S)..
:                       :

v3までの問題点

• 遠隔述語呼び出しのみでは起動済みの遠隔サーバへ接続できない
  → 遠隔述語呼び出しをサーバへのメッセージという形で定義し直した。
• 変数表のGC
  → IDとエントリの再利用を行なうように実装し直す。
• 未定義変数同士の同一性を検出できず、 未定義変数同士を単一化して終了したプロセスへ無駄な通信が起こる

  append(X,Y,Z) :- X=[]     | Z=Y.
  append(X,Y,Z) :- X=[A|X1] | Z=[A|Z1], append(X1,Y,Z1).
  
  +------------------+   X=[]     +-----+
  |                  |----------->|     |
  | append([],[a],Z) |  Y=[a|Y1]  | Z=Y |
  |                  |----------->|     |
  |                  |  Z=[a|Z1]  |     |
  |                  |<-----------|     |
  +------------------+            +-----+
  

  → 未定義変数の同一性検出を行なう。
• エージェントへの通信が移動経路を経由してしまう

  agent([A|S]) :- agent(S)@node(A).
  
  +----------------+ S=[2|S1]  +---+
  | agent([1,2,3]) |---------->| 1 |
  +----------------+ S1=[3|S2] +---+
                                 |  S1=[3|S2]
                               +---+
                               | 2 |
                               +---+
  

  → 未定義変数の輸出入を第3者に通知する。

未定義変数の同一性検出

1. p(X,Y) :- X=Y | ... は不可能
   ← 未定義変数同士の単一化によって待ちゴール [Inside KLIC] を起こすのは、 メリットが少なくコストパフォーマンスが低い。
   → ユーザプロセスの待つ変数は具体化されるべき（dklicはシステムプロセス）。
2. variable:unbound/2 - GCによって変数のアドレスが変わってしまう [runtime/var.kl1, unbound.kl1]
   → GCのタイミングを検出できないか?
3. Generic Object - 未定義変数同士の同一性検出によって、 変数表エントリの単一参照性が失われる
   → dangling referenceが起こらないことを保証する分散GCが必要

   +------------------+   X=[]     +-----+
   |                  |----------->|     |
   | append([],[a],Z) |   Z=Y      | Z=Y |
   |                  |<-----------|     |
   +------------------+            +-----+
   

4. 未定義変数が移動したことを通知する輸出入プロトコル

   +----------------+ S=[2|S1]  +---+
   | agent([1,2,3]) |---------->| 1 |
   |                |<----------|   |
   +----------------+ S1->node2 +---+
           |
           | S1=[3|S2]          +---+
           +------------------->| 2 |
                                +---+
   

Generic Object

使い方

• generic:new(+Class, -Object, ?Args)
• generic:GuardMethod(+Object, +Args): -Args
• generic:BodyMethod(+Object, ?Args)
• generic:generic(+Object, +Method(?Args))

3種類

1. Data Object 具体値を持つ
2. Consumer Object 書き込みによって処理が行なわれる
3. Generator Object 読み書きによって処理が行なわれる

KLIC/KL1 プログラムから見ると、Data Object は値, Consumer/Generator Object はゴールの中断原因変数のように見える。

Generic Objectのメソッド

D は Data Object、 C は Consumer Object、 G は Generator Object、 * は3種すべてに共通するメソッド

• D passive_unify
• * active_unify
• G generate
• G suspend
• * print
• * gc
• * regist
• * deallocate
• * close
• D body_generic
• D g_generic
• D compare
• D hash
• * encode
• D shmcopy

KLIC処理系で使われているGeneric Object

*.h は include/klic/ に、 *.c や *.kl1 は runtime/ にある。

• * [g_basic.h, g_extern.h, g_extinl.h, g_methtab.h, generic.h, gobj.h, gobjutil.h, generic.c, gen.kl1]
• D [gd_macro.h, gd_methtab.h, gdobject.h]
• C [gc_macro.h, gc_methtab.h, gcobject.h]
• G [gg_macro.h, gg_methtab.h]

• D float [g_float.h, gfloat.c]
• D vector [g_vector.h, gmvv.c]
• D (byte_)string [g_string.h, gstring.c]
• D module [gmodule.h, gmodule.c]
• D predicate [predinfo.h, gcode.c]
• D pointer [g_pointer.h, gpointer.c]
• D termarray [g_termarray.h, gtermarray.c]
• D goal [goalobj.h, ggoal.c]

• C merge [gmerge.c, gcmerge.kl1]
• C file_io [gio.c]
• C read_hook [ge_readhook.c]
• C reply_hook [ge_replyhook.c]

• G random_numbers [random.c]
• G exref [ge_exref.h, ge_exref.c]
• G shbusy [gg_shbusy.c]
• G shvar [gg_shvar.c]

*.kl1 と *.c の名前が異なるのは、 KLIC翻訳系が生成するファイル名と衝突するのを避けるためだろう。 逆に言うと、*.kl1 と同名の *.c はKLIC翻訳系に生成されたもの。

*.h と *.c の名前が異なるのは意味不明だ。

Generic Objectの作り方

1. % cp klic-3.003/runtime/gfloat.c test/
2. % cd test
3. % sed '/#define GD_CLASS_NAME() float/ s/float/float2/' <gfloat.c >gloat2.c
4. % klic g_float.kl1 gfloat2.c
5. % ./a.out

どのようなGeneric Objectが必要か

• 識別（同一性の検出）が容易な分散論理変数
• ローカルホスト内で参照のなくなった変数をGCできる変数表 （GC前に接続相手への通知が必要）
  ← vector やリストを使うと変数表から変数への参照が残ってしまい、 変数がGCされない。

  append([],Y,Z) :- Y=Z.
  
  +----------+      +----------+
  |{X,Y,Z,,,}========{X,Y,Z,,,}|
  | : : :    | Y=Z  | : : :    |
  | : : :    |      | : : :    |
  | : : :    |      | : : :    |
  |[] Y Z    |      |[] Y=Z    |
  |          |      |          |
  +----------+      +----------+
  

参考文献

• documents/KLIC*.info
• 関田大吾, Inside KLIC
• KLIC処理系ソース