並行論理プログラミング

提供: miniwiki
2018/8/19/ (日) 17:24時点におけるAdmin (トーク | 投稿記録)による版 (1版 をインポートしました)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内、検索

並行論理プログラミング（へいこうろんり－、英: Concurrent Logic Programming）は、論理プログラミングにおける並列性及び論理プログラミングによる並行処理の記述の研究から生まれた、並行プログラミングのためのパラダイムである。論理プログラミングでは述語論理式をゴール(Goal)の書き換え規則と見なし、ゴールの書き換えによって処理を行う。それに対し、並行論理プログラミングでは各ゴールをプロセスと見なして並行に書き換えを行い、ゴール間で共有する論理変数を通信チャネルとして情報交換や同期を行う。

概要

通常、並行論理プログラミングではホーン節にガードを導入した以下のような形式でプログラムを記述する。 

Head :- Guard | Body.

このガード付きホーン節は、エドガー・ダイクストラのガード付きコマンドと同様のものである。ゴール書き換えにはヘッドとガードの条件を満たす規則が使用され、この選択は永続的なものとしてコミットされる。条件を満たす規則が複数ある場合はどれか1つが選択される (don't-care non-determinism/indeterminate)。ガードの条件を満たす規則がない場合、ゴールの書き換えは中断され、ガードの条件を満たすような入力を受け取った後に書き換えが行われる。これらによりゴール間の同期が表現できる。この同期機構はコミッティッド・チョイス (committed-choice) とも呼ばれる。コミット後に書き換えられたボディ部の各ゴールは並行したプロセスと見なされる。

Prologなどと異なり、並行論理プログラミング言語ではコミット後のバックトラックを行わないため履歴の管理が不要になり、より効率のよい処理系の実装が可能になる。並行論理プログラミングは、通常の論理プログラミングから探索の機能を取り除き、代わりに並行実行の制御の機能を付加したものととらえることができる。また、定理証明系として見た場合、不完全だが健全な証明系と見なすことができる[1][2]。

並行論理プログラミングの考え方を取り入れた言語としては、Relational Language、Concurrent Prolog、Guarded Horn Clauses (GHC)とGHCの拡張であるKL1、PARLOG、Strandなどがある。 これらの言語では、多くの場合ストリームで通信を行う動的なプロセスの集まりでプログラムを構成する。そのためこれらの言語の処理方式はストリーム並列とも呼ばれる。

理論的には、並行論理プログラミングは並行制約プログラミングをエルブラン領域(Herbrand universe)に適用したものであり、制約出力を等号制約("=")のみに制限したものと見なすことができる。

並行論理プログラミングの特徴は以下の通りである。

  • 逐次実行ではなく並行実行が基本。並行処理を素直に記述できる。
  • 並列・分散環境でそのまま実行できる。
  • 動的にプロセスを生成できる。
  • 動的に通信チャネルを生成でき、他のプロセスに転送できる。
  • 通信ネットワークの動的な再構成が可能である。
  • 様々な形態のプロセス間通信を表現できる。
  • 理論的な背景を持ち、明確な意味論を持つ。
  • 効率のよい実装が可能である。
  • 記号処理ができる。

プログラミング

並行論理プログラミングでは、導出時のゴールをプロセス、共通論理変数を通信チャネルと見なし、論理変数を介して通信を行う複数のプロセスのネットワークとしてプログラムを記述する。 並行論理プログラミングのプログラムは、一般に以下のガード付きのホーン節(Horn clause)の集まりで表現される。"|"はコミット演算子と呼ばれる。G はガード部、B はボディ部と呼ばれる。Head、G、Bはそれぞれ原子論理式である。 

Head :- G1, ..., Gn| B1, ..., Bm.  (n,m≧0)

宣言的には、"|"、","は共にANDを表し、通常のホーン節と同様の意味を持つ[1]。 ゴールの書き換え規則として見た場合、HeadとG1, ..., Gnは書き換えのための条件、B1, ..., Bmは書き換え後のゴールを表す。書き換えを繰り返すことで、全てのゴールが何もしないゴール"true"まで書き換えられて実行が終了するとすると、この書き換えは簡約化 (reduction) と解釈できる。複数のゴールは並行に書き換えてよく、書き換え規則の適用に十分な情報がなければ書き換えは中断する。また、各ゴールについて書き換え条件のチェックも複数の節で並行に実行してよく、コミット時にただ1つの節が選択される(コミッティッド・チョイス)。

プロセス

論理プログラミングのプロセス的解釈に従うと、ゴールの原子論理式 p(T1, …, Tk)は、プログラムの状態が p/k (kは引数の数)、データの状態が T1, …, Tk であるプロセスと見なすことができる。

プロセスモデルと並行論理プログラミングの計算モデルとの対応は以下のようになる[3]。

プロセスモデル 並行論理プログラミングにおける実装
プロセス ゴールの原子論理式
プロセスネットワーク ゴール集合
プロセス動作の指示 ガード付きホーン節
通信チャネル 共通論理変数
通信 制約（情報）の追加[4]と観測[5]（共通論理変数の具体化）
同期 共通論理変数が判断に必要なだけ具体化するのを待つ
停止 True.
プロセス状態の変更 B.
並行したm個のプロセスの生成 B1, ..., Bm.

論理変数

C言語などのプログラミング言語の変数は値の格納場所であって、計算が進むに従って内容が変化する。論理プログラミングでの変数は数学的な変数に近いもので、何らかの値につけた名前である。値は決まっているか決まっていないかのいずれかで、プログラムの実行に従い徐々に論理変数を使わずに表現できる具体的な値を持つようになる。値は一度決まってしまえばその後変わることはない。並行論理プログラミングの強力さの多くはこれらの論理変数の性質による。 値が変わることはない性質により、従来言語で並行プログラミングを行う際に問題になる、共有変数の値更新に伴う煩雑なクリティカルセクションの問題をプログラマーが意識する必要はなくなる。 また、変数自身に不定の概念が含まれているため、ストリームのように先頭の要素からインクリメンタルに決まり残りの要素が不定のデータを、例えば[data|X](Xは論理変数)のように論理変数を含めたリストとして自然に表現できる。 並行論理プログラミングでは通信チャネルとして論理変数を使うが、同時に他のプロセスに論理変数を含めたデータを送ることもできるため、他プロセスに通信チャネル自身をデータと同じように渡すことができる。並行論理プログラミング言語では、通信チャネルは第一級のオブジェクトである。

ガード

ヘッドとガード部はプロセス書き換えのための条件を指定する。条件の指定方法は言語により異なるが、一般的には制約の観測を行うAsk部と制約の追加を行うTell部からなる。Ask部は、その実行が新たな制約を出力しないことを条件として指定する。つまりAsk部は制約の観測のみを行うことができ、値が決まっていない外部の変数を具体化しようとする(具体的な値を与える)など制約を出力する可能性がある場合、値が決まるまで書き換えを中断する。このようなAskは Blocking Ask と呼ばれる。Tell部は、コミット時に制約を出力してもよいが、その実行が今までの結果と矛盾しないことを条件として指定するために使用する。ガードのTell部における制約の出力は矛盾の検査と制約の追加をアトミックに行うため Atomic Tell と呼ばれる。ガード以外での制約の追加は、その実施を遅延できるため Eventual Tell と呼ばれる。

プロセス間の通信

並行論理プログラミングではプロセス間で共有する論理変数を通信チャネルと見なす。1つの変数を共有するプロセスの数には制限がなく、あるプロセスが変数を具体化すると、共有する他のプロセスに伝わり計算に影響を及ぼす。具体化は段階的に行ってもよく、また複数のプロセスが別々の部分を具体化してもかまわない。データの生成プロセスと消費プロセスが事前に決まっている必要はない。これらの特性より、方向の決まった1対1の単純なストリーム通信やメッセージパッシングにとどまらない、様々な形態の通信が可能になる[3]。

プログラム例

エラストテネスのふるいを使い素数生成を行うGuarded Horn Clauses (GHC) のプログラム例を示す。Prologと同様、MaxやPrimesなどの英大文字で始まる項は変数を表す。 

gen_primes(Max,Primes) :- gen(2,Max,Ns), sift(Ns,Primes).

gen_primes/2を実行すると、gen/3とsift/2の2つのプロセスが生成される。gen/3はMaxまでの自然数のストリームを生成し、sift/2はそれをふるいにかけ素数のストリームをPrimesに返す。gen/3とsift/2とはそれぞれ並行して動き、gen/3で生成された自然数のストリームは変数Nsを介して順次sift/2に渡される。プロセス間の同期は、ストリームの各要素が具体化(Instantiation)されるまで待つ、という形で自然に表現される。

gen/3、sift/2の各プログラムはそれぞれ以下のようになる。gen/3は、自然数のストリームを順次生成しMaxを超えたら終了する。sift/2は、2,3,5,7,..などの各素数の倍数をストリームから取り除くfilterプロセス(ふるい)を順に生成しながら、求まった素数を順次ストリームの要素として返す。各filterプロセスは変数を介して直列につながれていくため、自然数のストリームから素数のみのストリームを求めることができる。 

gen(N0,Max,Ns0) :- N0=<Max | Ns0=[N0|Ns1], N1:=N0+1, gen(N1,Max,Ns1).
gen(N0,Max,Ns0) :- N0 >Max | Ns0=[].

sift([Prime|Xs1],Zs0) :- Zs0=[Prime|Zs1], filter(Prime,Xs1,Ys), sift(Ys,Zs1).
sift([],         Zs0) :- Zs0=[].

filter(Prime,[X|Xs1],Ys0) :- X mod Prime=\=0 | Ys0=[X|Ys1], filter(Prime,Xs1,Ys1).
filter(Prime,[X|Xs1],Ys0) :- X mod Prime=:=0 |              filter(Prime,Xs1,Ys0).
filter(_,    [],     Ys0) :-                   Ys0=[].

他のプログラミングパラダイムとの比較

手続型プログラミング

手続型プログラミングでは同じ変数が時々刻々とその値を変えていく。論理変数を用いる並行論理プログラミングでは、値は一度決まってしまえばその後変わることはない。時間と共に変化する計算状態が条件判断に影響を与えることはないので、計算順序についての自由度が大きく上がる。また煩雑でバグが発生しやすい共有変数更新時のクリティカルセクションの問題も意識しなくてよくなる。

関数型プログラミング

時間変化する計算状態を意識する必要がないという点で、並行論理プログラミングは関数型プログラミングによく似ている。計算の背景となる意味論が明確であるという共通点もある。関数型プログラミングとの違いの1つは、並行論理プログラミングの非決定性である。ガード条件を満たす節が複数ある場合、選択は非決定的に行われる。実行時やコンパイル時の自由度が上がり、より効率的な実行ができる可能性がある。関数型プログラムはどんなハードウェア上でも同じ計算をするが、並行論理プログラミングで複数のプロセッサを用いた計算を行う場合、よりプロセッサ間通信が少なくなる節を優先して選ぶなど、最適化の幅が広がる。

論理型プログラミング

prologなどの論理型プログラミング言語の考え方は、ホーン節を基本にし宣言的な解釈が可能なこと、項(term)という共通のデータ形式を用いること、論理変数を用いることなど、並行論理プログラミングとよく似ている。シンタックスもほぼ同じである。実際、多くの並行論理プログラミング言語のプロトタイプはprolog上で作成された。しかし論理型プログラミング言語が持つデータの流れ(入出力)の方向性の無さ、探索機能など、大きく違った部分も多い。多くの並行論理プログラミング言語は、並行実行の機能を除けば、一般の論理型プログラミング言語より低レベルな言語と言うこともできる。

プログラミング手法

並行論理プログラミングでの基本的なプログラミング手法を以下に示す。並行論理プログラミングの表現力の大きさは、広範囲の並行プログラミングの手法をサポートしていることにある[6][3]。

  • ストリーム通信[7]： 生産者[8]、消費者[9]、変換器[10]、頒布者[11]、併合器[12]
  • 未完成メッセージ[13]　
  • 有限長バッファ通信[14]
  • 差分リスト[15]
  • ショートサーキット[16]
  • 黒板モデル[17]

ストリーム通信

論理変数を内部に含むリストを使い、先頭の要素からインクリメンタルに決まるストリームを構成できる。 1つのストリームで、以下のような様々なストリーム通信のパターンが構成できる。

構成 内容 例
1対1 生成プロセスと消費プロセスが直接通信。 producer1(Stream), consumer1(Stream)
1対N 複数の消費プロセスへのブロードキャスト。 producer1(Stream), consumer1(Stream), consumer2(Stream)
N対1 ストリームの異なった部分を生成プロセスが具体化。 producer1(Stream), producer2(Stream), consumer1(Stream)
N対M 上記の組み合わせ。

ひとつのプロセスは、複数のストリームを1本にマージするマージプロセスのように複数のストリームを受け取ったり、1本のストリームを内容に応じて複数のストリームに分けるディストリビュータプロセスのように複数のストリームを送り出したりすることもできる。

ストリームの生成プロセス、消費プロセス、ストリーム内容を変換/フィルターするプロセス、ディストリビュータプロセス、マージプロセスなどを組み合わせることで、様々なデータ駆動プログラムを作ることができる。プロセスのネットワークは静的にも動的にも構成できる。

未完成メッセージ

未完成メッセージ、あるいは応答箱付きメッセージ[18]と呼ばれる手法では、変数を含んだメッセージをデータとして送ることで、1本のストリームを双方向に使うことができる。送った変数は新たな共有変数になり、通信チャネルとして使える。例えば、応答が必要なメッセージを変数を含んだ形でストリーム上に流し、受信側で変数を具体化することで応答を送信側に返すことができる。応答自身を未完成メッセージにすれば、双方向の通信を必要なだけ続けることもできる。未完成メッセージは、マージプロセスなどを通信経路内に含んでいても問題なくやり取りができ、どのような経路を来たかに関係なく結果は送信元に返される。 また、一般的には未完成メッセージを用いることにより、通信ネットワークの動的な再構成が可能になる。

有限長バッファ通信

未完成メッセージを用いると有限長バッファ通信も表現できる。通常のストリーム通信は、[<メッセージ>|<変数>] のようにメッセージと変数が共に送られ、この変数が新たな共有変数となることで連続したメッセージを送り続けることができる。通常は送信側でメッセージと変数を共に作成するが、受信側でバッファ長分の変数を作成し、送信側にメッセージを設定してもらうことで有限長バッファ通信を実現できる。受信側でメッセージを読み出すごとに新たな共有変数を作成することで、バッファ長以上のメッセージが送られないことが保証できる。 有限長バッファ通信でバッファ長を1にすれば、受信側の要求で送信側がデータを送信する要求駆動型の制御が実現できる。

差分リスト

データの並びを2つのリストの差分で表現する差分リストの考え方は論理プログラミング全般で用いられるテクニックであり、並行にリストを構築していく場合にも有効に利用できる。差分リストでは、例えば [a,b|X]と Xの2つの差分で [a,b]を表現する。差分リストを用いると、2つの差分リスト [a,b|X]、Xと [c,d|Y]、Yの連結は、X=[c,d|Y]とした差分リスト [a,b,c,d|Y]、Yとして簡単に求まる。 差分リストの長所は以下の2点である。

  • リストの連結が定数時間でできる
  • リストの連結に副作用を用いない

通常のリストを副作用なしで連結すると(例えばLISPでのAPPEND関数の動作)、リストのコピーが必要なため先頭のリスト長に比例した時間が掛かる。通常のリストを副作用を用いて直接書き換えると(例えばC言語などでの線形リスト処理)、定数時間で連結することが可能だが、リストを読み書きする他の並行プロセスがある場合に複雑な同期処理が必要になり、効率的な並行処理ができない。論理プログラミングで使われる差分リストではこれらの問題が生じない。 並行論理プログラミングでは、多数のプロセスで部分的なリストを並行して構築し、1つのリストにまとめたい場合に差分リストが使われる。

ショートサーキット

一連のプロセスが終了したかどうかを確認するためにはショートサーキットテクニックと呼ばれる手法が用いられる。この方法では確認したいプロセスを共通変数でチェーン状につなぎ、各プロセス終了時に隣り合った共通変数を「短絡」させることで全体の終了を検出する。以下の例では、例えばprocess2(..,Mid2,Mid3) が終了した際に内部で Mid2=Mid3を実行する。 

process(..,Start,End) :- process1(..,Start,Mid2), process2(..,Mid2,Mid3), ..., processN(..,MidN,End).

process(..,Start,End) 実行時にStart の値として'ok'を入れておけば、process1〜processN が全て終了した時にEnd の値が'ok'に具体化され、全体の終了が検出できる。この手法は、複数のプロセスのグループを逐次的に実行したり、全てのプロセスにストリームのデータが行き渡ったかを確認するなど、グローバルな状態の検出と制御に利用できる。

黒板モデル

多くの独立したプログラムが黒板と呼ばれる共通のデータ領域で情報のやり取りしながら問題を解決していく黒板モデルの考え方は、人工知能の分野で古くから使われてきた。この考え方は並行論理プログラミングでも有効に活用できる。黒板は1つのプロセスとして表現され、内部に情報を保存し、複数の並行プロセスからの要求に応じアトミックに更新する。他の複数のプロセスからの要求はストリームとしてマージプロセスを介して黒板プロセスに送られ、結果は未完成メッセージを用いて送信元のプロセスに返される。情報の読み取り、更新を1つのプロセス内で行うことで、整合性を保った更新を行うことができる。黒板にあたるプロセスはクライアントサーバモデルでのサーバに当たる役割をするため、サーバプロセスと呼ばれることもある。

並行論理プログラミング言語

Relational Languageから発展した並行論理プログラミング言語は、それぞれ非常によく似た構文と考え方を持つが、プロセス間の同期をとるための中断のメカニズムは言語ごとにそれぞれ異なる。 また、各言語のバリエーションとして、ガードからユーザ定義のプログラムを呼び出せないようにガードの記述を制限し、ガード部の計算構造をフラット(Flat)にした言語がある。ガードはアトミックに動作できるため、プログラムの長さは増加するが効率のよい処理系の実装が可能になる。

Relational Language

Relational LanguageはClarkとGregoryが1981年に提案した言語で[19]、その後の並行論理プログラミング言語の基礎となった。HoareのCSPの考え方をIC-Prologに取り入れて拡張し、コミッティッド・チョイスによる非決定的な節の選択機構を持っていた。またストリームによる通信を行うことができた。しかしガード中のゴールは評価時に変数を含んではならないことや、通信にはリストを用いたストリームしか使えないなど、制限が多かった。1つの述語の入出力モード宣言を複数指定でき、また並列実行と逐次実行の両方をサポートするなど、言語仕様も複雑だった。入出力モード宣言の制約は厳格に守る必要があり、1つのストリームを入力と出力の双方向に使う不完全メッセージの技法なども使うことができなかった。 言語の特徴を以下にまとめる。 

* 同期の表現方法　　　モード宣言(厳格) (述語単位で指定)
* 制約の入出力　　　　Blocking AskとEventual Tell
* プロセス間通信　　　ストリーム
* 実行形態　　　　　　並行実行と逐次実行
* その他の特徴　　　　不完全メッセージ使用不可、言語仕様が非常に複雑、制限が多い

Concurrent Prolog

Relational Languageを参考にして、Shapiroは1983年に単純で表現力の高いConcurrent Prologを提案した[20]。通信にはストリームだけでなく任意の項が使えるようになり、ガードの記述の制限もなくなった。不完全メッセージなどの技法も使うことができ、通信チャネルを第一級のオブジェクトとして扱えるようになった。また、Relational Languageは並行実行と逐次実行の両方の機能を含んでいたが、Concurrent Prologは全てを並行に実行することを前提にすることで非常に単純化された仕様になった。Concurrent PrologはShapiroにより様々なバリエーションが提案され、分析されている[3]。 2つのストリームをマージし1つのストリームにするマージプロセスのプログラム例を以下に示す。 

merge([A|Xs],Ys,[A|Zs]) :- true | merge(Xs?,Ys,Zs).
merge(Xs,[A|Ys],[A|Zs]) :- true | merge(Xs,Ys?,Zs).
merge([],Ys,Ys) :- true | true.
merge(Xs,[],Xs) :- true | true.

Concurrent Prologでは、中断のメカニズムとして読み出し専用標記 (Read Only Annotation)を用いる。読み出し専用標記は"?"で表され、任意の変数に付与することができる。読み出し専用変数を変数以外の項に具体化しようとする試みは中断させられる。つまり、読み出し専用標記が付加された変数へのアクセスは入力モードだけが許される。これにより変数が具体化されるまで待つという同期と、変数毎のデータ入出力の方向性の指定とができる。 また、ガードの実行(ヘッドとガード部の実行)で行われた変数への書き込みは、その後の失敗により変更される可能性があるため、どれか1つの節がコミットされるまで他のプロセスに公開されない。つまりConcurrent Prologのガードには制約の追加を行うTell部(Atomic Tell)が含まれる。Concurrent Prologでは、ガード実行時に節ごとで変数の値が異なる多重環境を管理する必要があり、全ての節の並行実行を行う際に管理が複雑になる。 言語の特徴を以下にまとめる。 

* 同期の表現方法　　　読み出し専用標記　(変数単位で指定)
* 制約の入出力　　　　Blocking AskとAtomic Tell
* プロセス間通信　　　任意の項を使用可能
* 実行形態　　　　　　並行実行
* その他の特徴　　　　言語仕様が単純、多重環境の管理が必要、Atomic Tellにより表現力が高い

PARLOG

PARLOG (PARallel LOGic) は、Concurrent Prologに影響を受けたClarkとGregoryにより、複雑なRelational Languageの仕様を整理した後継言語として提案された。1983年に最初のバージョンが発表され[21]、その後1986年に改良版が発表された[22]。言語の特性や細かいシンタックスはそれぞれ異なる。 PARLOGはRelational Languageと同様、並行実行と逐次実行の両方の機能を持っており、言語仕様はConcurrent PrologやGHCと比べて複雑である。 1986年版でのマージプロセスのプログラム例を以下に示す。":"はコミット演算子を表す。 

mode merge(Xs?,Ys?,Zs^).

merge([A|Xs],Ys,[A|Zs]) <- true : merge(Xs,Ys,Zs).
merge(Xs,[A|Ys],[A|Zs]) <- true : merge(Xs,Ys,Zs).
merge([],Ys,Ys) <- true : true.
merge(Xs,[],Xs) <- true : true.

PARLOGでは、中断のメカニズムとしてモード宣言を用いる。"?"は入力モード、"^"は出力モードを表す。ヘッド部の同一化の際、アクセスモードが入力モードに指定されているゴール中の変数を変数以外の項に具体化しようとする試みは中断させられる。また、出力モードとして指定された項が実際に出力されるのは節が選択された後である。PARLOGの機能はkernel PARLOGというモード宣言を持たない単純な標準形式に変換することで実現される。PARLOGでモード宣言が果たしていた役割は、特殊な単方向のユニフィケーションを入力側はガード部に、出力側はボディ部に付加することで実現され、ガード部で中断が行われる。kernel PARLOGでのガードの規則はGHCの規則と同じ意味を持つ。kernel PARLOGのガードには制約の追加を行うTell部がなく制約の観測を行うAsk部のみのため、多重環境の問題はない。kernel PARLOGに変換できないプログラムをエラーとすることでAsk部のみであることを保証する。kernel PARLOGに変換できるPARLOGプログラムの出力モードは入力可能として扱われ、不完全メッセージなどの技法も使用できる。ただしガード部の安全性のチェックをコンパイル時に行っているため、Concurrent PrologやGHCでは数行で書ける自分自身のメタインタプリタをPARLOGでは素直に書くことができない。 言語の特徴を以下にまとめる。 

* 同期の表現方法　　　モード宣言(制限を緩和) (述語単位で指定)
* 制約の入出力　　　　Blocking AskとEventual Tell
* プロセス間通信　　　任意の項を使用可能
* 実行形態　　　　　　並行実行と逐次実行
* その他の特徴　　　　ガードの安全性をコンパイル時にチェック、言語仕様が複雑で多機能、多重環境の管理が不要

Guarded Horn Clauses と KL1

Guarded Horn Clauses (GHC) は、上田により1984年末に設計され1985年に発表された[23]。Concurrent Prologの検討のため処理系の作成を行っている際、Concurrent Prologの多重環境の問題に気付き、それを解決する言語として設計した。GHCもConcurrent Prolog同様、並行実行以外の機能を含まない単純化された仕様を持つ。 マージプロセスのプログラム例を以下に示す。 

merge([A|Xs],Ys,Zs0) :- true | Zs0=[A|Zs], merge(Xs,Ys,Zs).
merge(Xs,[A|Ys],Zs0) :- true | Zs0=[A|Zs], merge(Xs,Ys,Zs).
merge([],Ys,Zs) :- true | Zs=Ys.
merge(Xs,[],Zs) :- true | Zs=Xs.

GHCでは、中断のメカニズムとして入力ガード (Input Guard)を用いる。GHCはモード宣言や読み出し専用標記などの特別な表記法を用いない。ヘッド及びガード部での同一化の際、ゴール中の変数を具体化するような試みは中断させられる。ガードでは、ゴール中の変数は入力モードでしかアクセスできない。GHCのガードは制約の追加を行うTell部がなく制約の観測を行うAsk部のみのため、多重環境の問題はない。出力となる変数の具体化はボディ部のユニフィケーションで行う。モード宣言がないため、不完全メッセージなどの技法は問題なく使用できる。

KL1 (Kernel Language 1) は、GHCのフラット版であるFlat GHCをもとに近山により設計され、第五世代コンピュータプロジェクトでハードウェアと応用ソフトウェアとの間をつなぐ核言語として、並列マシンのオペレーティングシステムやKL1を含む様々な言語処理系、各種応用プログラムの作成に利用された。KL1では、論理的並行性の記述にはGHCの機能をそのまま使い、それを複数のマシンに分散する物理的並行性(並列性)をそれに付加するプラグマとして追加することで、論理的並行性と物理的並行性を別々に指定可能にし、プログラムの正しさに影響を与えることなく負荷分散の仕方などを変えられるように設計された。また複数のプロセスの実行制御、資源管理、例外処理を行うため「荘園」と呼ばれる機能が追加された。荘園は外部からの制御ストリームによって起動/停止/再起動/実行放棄や使用可能な計算機資源の制御を行う機能で、荘園自身をネストすることもできる。この機能は、オペレーティングシステムなどのシステムプログラミングのために使われ、またオペレーティングシステム自身のデバッグのための仮想マシン環境としても使用された[24]。 言語の特徴を以下にまとめる。 

* 同期の表現方法　　　入力ガード　(節単位で指定)
* 制約の入出力　　　　Blocking AskとEventual Tell
* プロセス間通信　　　任意の項を使用可能
* 実行形態　　　　　　並行実行
* その他の特徴　　　　ガードの安全性を実行時にチェック、言語仕様が単純、多重環境の管理が不要、比較的使用実績多い

Strand

Strand（STReam AND-Parallelism）は、Fosterらにより1989年に発表された商用ベースの言語である[6]。ガード部に組み込み述語のみを記述できるフラットな言語で、プログラムはFlat GHCとよく似たものとなる。この言語はErlang開発初期にベース言語として使われた[6]。マージプロセスのプログラム例を以下に示す。 

merge([A|Xs],Ys,Zs0) :- true | Zs0:=[A|Zs], merge(Xs,Ys,Zs).
merge(Xs,[A|Ys],Zs0) :- true | Zs0:=[A|Zs], merge(Xs,Ys,Zs).
merge([],Ys,Zs) :- true | Zs:=Ys.
merge(Xs,[],Zs) :- true | Zs:=Xs.

Strandでは、中断のメカニズムとしてGHCと同じ入力ガード (Input Guard)を用いる。GHCと同様、多重環境の問題はない。出力となる変数の具体化はボディ部のみで行い、GHCと異なりユニフィケーションではなく代入":="を用いる。KL1と同様、物理的並列性などはプラグマ付加で指定することができる。 言語の特徴を以下にまとめる。 

* 同期の表現方法　　　入力ガード　(節単位で指定)
* 制約の入出力　　　　Blocking AskとEventual Tell(Initialize)
* プロセス間通信　　　任意の項を使用可能
* 実行形態　　　　　　並行実行
* その他の特徴　　　　ガードの安全性を実行時にチェック、言語仕様が単純、多重環境の管理が不要

その他の言語

並行論理プログラミングから派生したプログラミング言語のいくつかを以下に示す。

  • AKL (Andorra Kernel Language/Agent Kernel Language)
D.H.Warrenの提案したAND並列実行とOR並列実行の統合モデルであるAndorra Modelをもとにしたプログラミング言語。並行処理を記述しやすいGHC等の言語とPrologの探索機能とをあわせ、並行制約プログラミング言語としての機能を追加した[25]。
AKLのアイデアをもとに、オブジェクト指向や関数型プログラミング、制約プログラミングなどの考え方を組み合わせたマルチパラダイム言語処理系とその言語モデル。
  • PCN (Program Composition Notation)
Strandの研究者らが設計した、複数のプログラムを並列環境や分散環境で組み合わせるための言語。並行論理プログラミング言語に手続型言語の変数や{}によるブロック表現などを取り入れたプログラミング言語で、C言語やFortranのプログラムを呼び出すことができた[26]。
  • CC++
C++に並行論理プログラミングでの論理変数と同じような機能を持つsync変数やsyncオブジェクトなどを追加したもの[27]。

歴史

複数の通信しあうプロセスの集まりでプログラムを構成するという考え方は、1977年にKahnとMcQueenから[28]、 1978年にHoareから提案された[29]。

KahnとMcQueenが提案したものは、複数のプロセスがストリームを介して通信を行う言語で、プロセス間の非同期通信とプロセスの動的生成を許し、プロセス自体は決定的な動作を行うものだった。Hoareが提案したものはガード付きコマンドの考えに基づいたCSPで、この時点ではプロセスの動的生成や非同期通信などの機能は含まれていなかった。 1979年にvan Emdenとde Luceanaは、KahnとMcQueenのモデルを論理プログラミングに適用し、導出時のゴールをプロセス、共通論理変数を通信チャネルと見なす、論理プログラミングのプロセス的解釈を与えた[30]。

ClarkとGregoryは1981年にRelational Languageを提案した[19]。Clarkらはその前に並行実行の機能をPrologに追加したIC-Prologという言語を開発したが、制御機構が複雑になりうまくいかないことが分かった。IC-Prologからバックトラックの機能を取り除きCSPのアイデアを取り入れたRelational Languageは、非同期通信やプロセスの動的生成の機能を含むもので、その後の並行論理プログラミング言語の基礎になった。 ShapiroはRelational Languageをより単純化し、ガードの制限を緩めたConcurrent Prologを1983年に発表した[20]。同時に並行論理プログラミングでの様々なプログラミング手法がConcurrent Prolog上で開発された。 Concurrent Prologに影響を受けたClarkらは、Relational Languageの後継言語であるPARLOGを設計した[21]。

第五世代コンピュータプロジェクトで並列マシンの核言語の検討をしていた上田は、Concurrent Prologを分析する過程で問題点を見つけ、さらに単純化したGuarded Horn Clauses (GHC)という言語を1985年に発表し[23]、 これを拡張したKL1 (Kernel Language 1) は並列マシンのオペレーティングシステムや言語処理系、様々な応用プログラムの作成に利用された[24]。 GHCはPARLOGにも影響を与え、最終的にGHCとPARLOGは非常に似たものとなった。 Fosterらはこれらの言語の研究成果を取り入れ、GHCによく似たStrandという商用ベースの言語を1989年に発表した。この言語はErlang開発初期にベース言語として使われた[6]。

これらの並行論理プログラミングの研究と並行して、論理プログラミングに様々な制約条件を取り入れる制約論理プログラミングの考え方が生まれた。これが並行論理プログラミングと結び付き、制約の出力(追加, Tell)と入力(観測, Ask)で並行実行を制御する並行制約プログラミング(Concurrent Constraint Programming)として統合され、Saraswatらによって計算理論が整備された[31]。

脚注

  1. ↑ 1.0 1.1 古川 康一,溝口 文雄(編) 並列論理型言語GHCとその応用 (知識情報処理シリーズ)
  2. ↑ 近山 隆, KL1入門.
  3. ↑ 3.0 3.1 3.2 3.3 Shapiro, E.. The Family of Concurrent Logic Programming Languages
  4. ↑ 英: tell
  5. ↑ 英: ask
  6. ↑ 6.0 6.1 6.2 6.3 Foster, I.,and Tayler, S.(ed) Strand: New Concepts in Parallel Programming
  7. ↑ 英: stream
  8. ↑ 英: producer
  9. ↑ 英: consumer
  10. ↑ 英: transducer
  11. ↑ 英: distributer
  12. ↑ 英: merger
  13. ↑ 英: imcomplete-message
  14. ↑ 英: bounded buffer
  15. ↑ 英: difference list
  16. ↑ 英: short-circuit
  17. ↑ 英: blackboard
  18. ↑ 英: messages with reply boxes
  19. ↑ 19.0 19.1 Clark, K. L., and Gregory, S. A relational language for parallel programming
  20. ↑ 20.0 20.1 Shapiro, E. A subset of Concurrent Prolog and its interpreter
  21. ↑ 21.0 21.1 Clark, K, L. and Gregory, S. PARLOG: a parallel logic programming language
  22. ↑ Clark, K. L., and Gregory, S. PARLOG: Parallel programming in logic
  23. ↑ 23.0 23.1 Ueda, K. Guarded Horn Clauses 1985
  24. ↑ 24.0 24.1 近山 隆, オペレーティングシステムPIMOSと核言語KL1
  25. ↑ Janson S. and Haridi S.,Programming Paradigms of the Andorra Kernel Language Logic Programming: Proceedings of the 1991 International Symposium 1991.
  26. ↑ Chandy,K.M. and S.Taylor, The Composition of Concurrent Programs,in Proceedings Supercomputing '89, Reno, Nevada, Nov.13-17, ACM. 1989.
  27. ↑ Chandy,K.M., Kesselman C., Mani K. and Kesselman C.C., CC++: A Declarative Concurrent Object Oriented Programming Notation 1992.
  28. ↑ Kahn, G., and MacQueen, D. Coroutines and networks of parallel processes
  29. ↑ Hoare, C. A. R. Communicating sequential processes
  30. ↑ van Emden, M. H., and de Lucena, G. J. Predicate logic as a language for parallel programming
  31. ↑ Saraswat, V. A., and Rinard M. Concurrent Constraint Programming 1990

参考文献

  • Clark, K. L., and Gregory, S. A relational language for parallel programming. In Proceedings of the ACM Conference on Functional Languages and Computer Architecture. ACM. 1981.
  • Clark, K. L., McCabe, F. G., and Gregory, S. IC-PROLOG-Language features. In Logic Programming, K. L. Clark and S.A. Tarnlund, Eds. Academic Press, London. 1982.
  • Clark, K, L. and Gregory, S. PARLOG: a parallel logic programming language. Research Report DOC 83/5, Imperial College, London. 1983.
  • Clark, K. L., and Gregory, S. PARLOG: Parallel programming in logic. ACM Trans. Program. Lang. Syst. 8, 1, l-49, ACM. 1986.
  • Dijkstra, E. W. Guarded commands, nondeterminacy, and formal derivation of programs. Commun. ACM 18,8 (Aug.), ACM. 1975.
  • Foster, I.,and Tayler, S.(ed) Strand: New Concepts in Parallel Programming. Prentice Hall 1990, ISBN 978-0138505875
  • Hoare, C. A. R. Communicating sequential processes. Commun. ACM 21,8 (Aug.), ACM. 1978.
  • Kahn, G., and MacQueen, D. Coroutines and networks of parallel processes. In Information Processing 77, Proceedings of the ZFZP Congress, B. Gilchrist, Ed. North-Holland, Amsterdam. 1977.
  • Shapiro, E. A subset of Concurrent Prolog and its interpreter. ICOT Tech. Rep. TR-003,ICOT, Tokyo. 1983.
  • Shapiro, E.. The Family of Concurrent Logic Programming Languages. ACM Computing Surveys, Vol.21, No.3, September 1989.
  • Ueda, K. Guarded Horn Clauses. ICOT Technical Report TR-103, ICOT, Tokyo. 1985.
  • Ueda, K. Guarded Horn Clauses. (pdf) Doctoral Thesis. Information Engineering Course, University of Tokyo, 1986.
  • van Emden, M. H., and de Lucena, G. J. Predicate logic as a language for parallel programming. In Logic Programming, K. L. Clark and S. A. Tarnlund, Eds. Academic Press, London. 1982.
  • Saraswat, V. A. Concurrent constraint programming languages. Ph.D. thesis, Dept. of Computer Science, Carnegie-Mellon University. 1989.
  • Saraswat, V. A., and Rinard M. Concurrent Constraint Programming. In Proceedings of Seventeenth ACM Symposium on Principles of Programming Languages, January 1990
  • 近山 隆, KL1入門. 1991.
  • 近山 隆, オペレーティングシステムPIMOSと核言語KL1. (pdf) 1992.
  • 上田 和紀, 並列プログラミング. ICOT Technical Manual TM-782, ICOT, Tokyo. 1989.
  • 上田 和紀, 並行論理プログラミング言語　GHC/KL1. (pdf) 2000.
  • 古川 康一,溝口 文雄(編) 並列論理型言語GHCとその応用 (知識情報処理シリーズ) 共立出版 1987, ISBN 978-4320022669

関連項目

外部リンク



「http:///http:///mymemo.xyz/mymemo.xyz/wiki/index.php?title=並行論理プログラミング&oldid=111313」から取得