KL1 による分散 KL1 言語処理系の実装 Distributed KL1 Implementation in KL1

G96P073-6 高木祐介上田研究室 Yusuke TAKAGI, Ueda Lab.

2000 年 2 月 8 日

概要

ネットワーク環境の普及につれ、分散プログラミングに対する需要が高まっている。しかし、逐次手続き型言語による分散処理の記述は非常に煩雑である。

並行論理型言語は、実行の各単位が並行に実行され、プロセス間通信を宣言的に記述できる。また、分散処理は並行処理の一例なので、並行論理型言語で分散処理を記述するのはごく自然なことであろう。

KL1 は、並行論理型言語 GHC を基にした、実用的な並列論理型言語である。既存の標準言語処理系 KLIC の定める並列 KL1 では、並列のための限られた分散処理と、 Unix レベルのソケット通信を記述することができるが、一般の分散処理を言語レベルで記述することはできない。

本研究では、 KL1 を分散化するために、分散 KL1 の極小部分集合 dKL1 を定め、 KLIC を利用して、 dKL1 の言語処理系 dKLIC を実装した。

dKL1 に近い KLIC/KL1 を実装言語に選んだために、 dKLIC 実装の本質部分に集中でき、実装の手間は少なかった。また、 dKL1 の定める十分広いクラスのプログラムに対して、機械翻訳を行うアルゴリズムを示すことができた。

1 keywords

並行論理型言語、 KL1、分散言語処理系。 Concurrent Logic Language, KL1, Distributed Implementation.

2 並行と並列、分散

並列 ⊂ 分散 ⊂ 並行

並行 (concurrent) とは、論理的な独立性を表します。並行なプロセスは、タイムシェアリングによって独立に動いても良いし、どんな順番でも、異なる計算機で動かしてもかまいません。

並列 (parallel) とは、物理的な同時性を表します。並列プロセスは、複数のプロセッサや複数の計算機によって同時に動きます。並列に実行されるプロセスは、並行でなければなりません。また、 1 台のプロセッサは同時に複数のプロセスを動かせないので、並列プロセスは分散されていなければなりません。プロセスの間で通信があると、その部分は並列ではなく逐次 (sequential) に動きます。なぜなら、送信は受信前に終わり、受信は送信後に始まるからです。

分散 (distributed) とは、物理的な場所の違いを表します。分散されるプロセスは、大部分が並行であるべきです。なぜなら、並行でないプロセスを分散すると通信量が多くなり、効率が悪いからです。例外として、チャットプログラムのように、通信自体が目的である分散プロセスがあります。

3 GHC と KL1、 dKL1

Concurrency Language
concurrent  GHC
parallel  KL1
distributed dKL1, KL1j

Guarded Horn Clauses (GHC) は、並行論理型言語の 1 つです。逐次論理型言語の Prolog に似た構文を持っていますが、ゴールの実行や節の選択に優先度が決まっていません。並行拡張された逐次言語では並行性を明記しますが、並行論理型言語では逆に逐次性を明記します。例えば、 Unix/C では fork システムコールによって並行なプロセスを生成しますが、 GHC では変数を共有することによってゴールを同期させます。

KL1 は、 GHC に基づく並列論理型言語です。 GHC の並行性に加えて、プログラムの論理的な意味を変えない並列のためのプラグマが拡張されています。

dKL1 は、 KL1 を拡張した分散論理型言語です。分散プラグマを拡張して、遠隔述語呼び出しができるようにしました。 dKL1 は KL1j という分散 KL1 の部分集合です。

4 KL1 の言語処理系

Language  Implementations
KL1  (PIM), KLIC, KLIJava, etc.
dKL1, KL1j  dKLIC, KL1j

KL1 の言語処理系として、並列推論マシン (PIM) 上の言語処理系、 Unix/C 上の KLIC、 Java 上の KLIJava などがあります。 KLIC は、最初の汎用 KL1 言語処理系で、事実上 KL1 の標準を定めています。

KL1 を含む分散 KL1 の言語処理系として、 Java 上の KL1j、 KLIC 上の dKLIC があります。 dKLIC は、歴史の浅い分散 KL1 の実装技術を固め、まだ実装されていない KL1j のコンパイラを実装する助けとなるように、 KL1j の極小部分集合を実動できる言語処理系を目指しています。

5 KL1 の文法

KL1 では、変数を束縛する値は型付きですが、変数自体は型がありません。単一代入であり、束縛済みの変数が別の値に束縛されることはありません。また、論理変数であり、束縛前は未定義という状態を持ちます。変数を値に束縛することを具体化と言います。

KL1 の文法は、 Prolog に似ています。大きな違いは、節のガードとボディがコミット演算子（|）によって分けられていることです。

          Head :- Guard | Body.

ガード部に現れるゴールは、条件を表します。ガードゴールが全て成功しない限り、その節は選択されません。ガードゴールが変数を具体化することはありません。

ボディ部に現れるゴールは、節が選択されたときに生成されるサブゴールです。 KL1 の個々の節は、 if 文のような形をしているわけです。

KL1 には、 Prolog と違ってバックトラックの仕組みがありません。どの節も選択できないゴールは、中断されます。中断の原因となった変数が具体化されると、ゴールは実行待ち状態に戻ります。

6 分散プラグマ

プロセスを分散させることによって、複数のプロセスを並列に実行したり、分散環境における通信を簡単に記述したりすることができます。

手続き型言語と違って、並行論理型言語では記述の最小単位であるゴールをプロセスと見なすことができます。なぜなら、各ゴールは並行であり、ゴールの引数は未定義かもしれない論理変数だからです。一方、手続き型言語の文をプロセスと見なすのは難しいでしょう。

従って、遠隔述語を呼び出し、遠隔でゴールを実行することができれば、並行論理型言語を分散化したと言うことができます。

そこで、 KL1j は、以下のような分散プラグマを提唱しました。 Goal@node(URL) URL は以下のような文字

列である。

"kl1://Host:Port"

ここで、 Host はホスト名ないし IP アドレス、 Port はポート番号である。

KL1j は、プロセス間の通信路に名前を付けるという大きな分散機能も提唱しましたが、これは分散プラグマより高級な機能なので dKLIC はサポートしません。

7 遠隔呼び出しの仕組み

スタブ–スケルトン・モデルは、分散環境の透過性を提供します。クライアントは遠隔呼び出しのつもりでスタブを呼び出し、サーバはクライアントから呼び出されたつもりで、実はスケルトンから呼び出されます。分散に必要な通信は、スタブとスケルトンが行います。 (cf. OHP “Stub-Skeleton Framework for Remote Call”)

dKLIC は、 KLIC によって記述してあります。 KLIC には、分散プラグマがありませんが、 Unix レベルのソケット通信があります。ソケット通信をスタブとスケルトンの中に閉じ込めれば、 dKLIC で記述されたユーザプログラムは通信を気にする必要がありません。

dKL1 に近い KL1 によって実装を行ったので、 Java で記述された KL1j ほど多くの事を考えなくて済みました。考えなければならないのは、スタブとスケルトンを KLIC によって記述する事だけでした。

8 dKLIC の実装

スタブとスケルトンが行う事は、 KL1 項の直列化と、変数の管理です。

KLIC のソケットにはバイト列しか流せないので、 KL1 項を流すには直列化しなければなりません。直列化には、変数を変数名で表す事も含まれるので、直列化層は変数管理層の上に実装します。 (cf. OHP “Layers in dKLIC”)

また、 KLIC では未定義変数を識別できないので、 dkLIC は変数を管理識別しなければなりません。

あるサーバ (cf. OHP “Predicate server/1”) を考えたとき、クライアントの連続した要求に対して、サーバの返事は違う順序で返ってくるかもしれません。なぜなら、 KL1 のゴール実行順序は非決定的だからです。

サーバの返事が、どの要求に対するものなのかを識別するために、 dKLIC は未定義変数を識別しなければなりません。なぜなら、クライアントの要求とは未定義変数で表され、サーバの返事は変数の具体化で表されるからです。 (cf. OHP “Communication and Reduction for server/1”)

9 変数表

変数を管理識別するため、 dKLIC は変数表を実装しました。変数表は、変数名と KLIC の変数を対応づける辞書です。

変数表に変数名を与えると、対応する KLIC 変数が返ってきます。逆に KLIC 変数を与えると、新しい変数名が返ってきます。

KLIC では未定義変数を識別できず、以前に登録した変数を同定できないため、 KLIC 変数を与えるたびに新しい対応を登録してしまいます。 KLIC 変数は単一代入なので、変数表が巨大になりやすい事を除けば、問題はありません。

新しい対応を登録していくため、変数表は単調増加します。変数表は、ソケットの両端に張りつけて使います。

クライアントが KLIC 変数を流そうとすると、スタブが変数表を参照して変数名を送信します。スケルトンは変数名を受信すると、変数表を参照して KLIC 変数をサーバに渡します。

サーバが変数を具体化すると、監視していたスケルトンは変数の具体化ゴールを送信します。具体化ゴールを受信したスタブは、クライアントに変数の具体化を教えます。 (cf. OHP “Communication and Reduction for server/1”)

クライアント側とサーバ側の KLIC 変数は違うものですが、変数表が変数の同一性を保証しています。ソケットの両端にある 2 つの変数表の同一性は、スタブとスケルトンが保証します。

変数表は、（変数名＝ KLIC 変数）という対応を、変数名で逆順に整列したリストとして実装しました。変数名は単調増加する整数から生成するので、逆順に整列されていれば O(1) で新しい対応を登録できるからです。 (cf. OHP “Variable Table for server/1”)

10 直列化

ソケットに KL1 項を流すため、 dKLIC は直列化を行います。

クライアントが KL1 項を流そうとすると、スタブが直列化した結果を送信します。スケルトンは受信したバイト列から、 KL1 項を復元します。

テストとデバッグをしやすいように、直列化の結果は目に見える文字の列にしました。 KLIC には文字列型がありますが、文字列型は二重引用符で囲んで表すため、直列化の結果は文字列ではなく、文字の差分リストで表すことにしました。

差分リストとは、リストを表すポインタの対で、 KL1 で多用されます。リストの最後尾に要素を付け加えるには O(N) の処理が必要ですが、尾が未定義変数である差分リストならば、 O(1) で済みます。

差分リストを使ったことによって、直列化の結果を直接ソケットに流せるようになりました。単なるリストをソケットに流すと、リストの終わりに到達してソケットが閉じてしまいます。

また、 KL1 項の一部を直列化した結果がどこからどこまでなのかを差分リストで表すことができるようになりました。再帰的な構文を持つ KL1 項を再帰的に処理しやすくなりました。

直列化の結果が、プログラムテキストと同じ文字の列なので、そこから KL1 項を復元するには、 KL1 プログラムを読み取る技法が必要です。

dKLIC では、 LL(1) という技法を使いました。 LL(k) は、 k 文字先読みすることによってトップダウンに文法を解析する手法です。形式文法とその解析手法については、広く知られているので、ここでは説明を省略します。

       Local                           Remote
       remote call - - - - - - - -> predicate
            ||                          ||   meta-call
           stub ==================== skeleton
                socket communication

図 1: Stub-Skeleton Framework for Remote Predicate Call

            Layer 3:  Remote Predicate Call
            Layer 2:  Marshalling / Unmarshalling
            Layer 1:  Variable Table

図 2: Layers in dKLIC Implementation

       Client
+-------------------+
|    Remote Call    |
|      in dKL1      |
+-------------------+
          V  dKLIC Compiler
+-------------------+
|     Stub Call     |
|     with Stub     |
|    in KLIC/KL1    |
+-------------------+
          V   KLIC Compiler
+-------------------+
|   Machine Code    |
| executed at Local |
+-------------------+

                                        Server
                              +-------------------------+
                              | Remote-Called Predicate |
                              |         in dKL1         |
                              +-------------------------+
                                           V  dKLIC Compiler
                              +-------------------------+
                              |  Meta-Called Predicate  |
                              |      with Skeleton      |
                              |       in KLIC/KL1       |
                              +-------------------------+
                                           V   KLIC Compiler
                              +-------------------------+
                              |      Machine Code       |
                              |   executed at Remote    |
                              +-------------------------+

図 3: Client-Server in dKL1

              server(Queue) :- Queue = [] |
                true.
              server(Queue) :- Queue = [Request|Q] |
                Request = answer,
                server(Q).

図 4: Predicate server/1

                   Local   Remote
Client        Stub                Skeleton        Server
              Marshall
Remote-Call  -----------------------------> Meta-Call
                                                Reduction
Answer       <----------------------------- Instantiation
                                  Marshall
                   server(_0)
server(Queue)     --------------->
  @node(Remote).                           server(Queue).
                   _0 = [_1|_2]              ||
Queue=[Request|Q] --------------->         :- Queue = [Request|Q] |
                  <---------------           Request = answer,
                      _1 = answer            server(Q).
                   _2 = []                     ||
Q=[]              --------------->         :- Q = [] |
                                             true.

図 5: Communication and Reduction for server/1

                ["_2"=Q, "_1"=Request, "_0"=Queue]

図 6: Variable Table for server/1