Concurrent Prolog

Concurrent Prolog
パラダイム	並行論理プログラミング
登場時期	1983年
設計者	Ehud Y. Shapiro
型付け	動的型付け
主な処理系	Logix
影響を受けた言語	Relational Language
影響を与えた言語	PARLOG、Guarded Horn Clauses、KL1、Strand、Oz、CHR、Janus、AKL

Concurrent Prologは、1983年に発表された並行論理プログラミング言語である。イスラエルWeizmann研究所のEhud Shapiroにより設計された。それ以前に開発されたRelational Languageをより単純化し、制限を緩めた言語で、その後の並行論理プログラミング言語に大きな影響を与えた。また、並行論理プログラミングでの様々なプログラミング手法がConcurrent Prolog上で開発された。

概要

Concurrent PrologはPrologから派生した並行プログラミングと並列実行のためのプログラミング言語で、論理変数を介して通信を行う複数の軽量プロセスのネットワークとしてプログラムを記述する。多くの並行プログラミング言語が逐次処理言語に並行実行の機能を追加したものであるのに対して、Concurrent Prologは並行実行が基本で、並行処理を素直に記述できる。

Concurrent Prologの派生言語として、組み込み述語のみをガード部に記述できるように制限してより単純化した Flat Concurrent Prolog（FCP）がある。1983年の発表以降、Shapiroにより様々なFCPのバリエーションが提案され、分析されている。

Concurrent Prologではホーン節にガードを導入した以下のような規則(Clause)の集まりでプログラムを記述する。"|"はコミット演算子と呼ばれる。G はガード部、B はボディ部と呼ばれる。Head、G、Bはそれぞれ原子論理式である。ガード部の条件がない場合、ガード部とコミット演算子は省略できる。

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

Headとガード部はプロセス書き換えのための条件、ボディ部は書き換え後のプロセスを表す。生成されたプロセスは全て並行に実行される。また、各プロセスごとの書き換え条件のチェックも複数の節で並行に実行してよく、コミット時にただ1つの節が選択される（コミッティッド・チョイス）。Prologと異なりバックトラックの機能はない。

プロセス間の通信にはプロセス間で共有する論理変数を使用する。多くの場合、プロセス間の通信には論理変数を含んだリストで表現されたストリームを用いる。ストリームは [<メッセージ>|<変数>] のようなリストで実現する。 論理変数を共有するプロセスの数に制限はないため、ストリーム通信は1対1だけではなく1対Nのブロードキャストなど、様々な形態が可能である。

簡単なプログラム例を以下に示す。2本のストリームをマージして1本のストリームにするプログラムで、Prologと同様、A や Xs など英大文字や"_"で始まる項は変数を表す。mergeの最初の2引数が入力ストリーム、最後が出力ストリームである。

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)を用いる。読み出し専用標記は"?"で表され、任意の変数に付与することができる。読み出し専用標記が付加された変数へのアクセスは入力モードだけが許され、読み出し専用変数を変数以外の項に具体化しようとする試みは中断させられる。つまり、これにより変数が具体化されるまで待つという同期と、変数毎のデータ入出力の方向性の指定とができる。例えば、上記プログラムの最初の節では、最初の引数が[A|Xs]のようなリストの形になっていない場合は中断し、他のプロセスにより[A|Xs]の形に具体化された(具体的に値が決まった)場合に実行を再開する。この時点でXs自体は具体化されていなくても構わないため、リストの先頭からインクリメンタルに具体化されるストリームを素直に処理できる。

また、ガードの実行(ヘッドとガード部の実行)で行われた変数への書き込みは、その後の失敗により変更される可能性があるため、どれか1つの節がコミットされるまで他のプロセスに公開されない。例えば、上記マージプログラムの最初の節での [A|Zs] と2番目の節での [A|Zs] とは値が異なる可能性がある。Concurrent Prologでは、ガード実行時に節ごとで変数の値が異なる多重環境を管理する必要があり、全ての節の並行実行を行う際に管理が複雑になる。

プログラム例

以下にConcurrent Prologのプログラム例を示す。

待ち行列

FIFOの待ち行列を管理するプログラムの例を以下に示す。ストリームSに enqueue(X) のメッセージを送るとXの内容が待ち行列の最後に追加され、dequeue(X) のメッセージを送ると待ち行列の先頭要素がXに返される。待ち行列の表現には、2つのリストの差分で１つのデータの並びを表現する差分リストのテクニックが使用されている。

queue(S) :- queue(S, Z, Z).

queue([dequeue(X)|S], [X|NewHead], Tail) :- queue(S?, NewHead, Tail).
queue([enqueue(X)|S], Head, [X|NewTail]) :- queue(S?, Head, NewTail).
queue([], _, _).

前出のマージプロセスと組み合わせることで、複数のプロセスからの dequeue/enqueue のメッセージを処理することができ、クライアントサーバモデルでのサーバプロセスのように使うことができる。

素数生成

エラストテネスのふるいを使い素数生成を行うプログラム例を示す。

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

gen_primes/2を実行すると、integers/3とsift/2の2つのプロセスが生成される。integers/3はMaxまでの自然数のストリームを生成し、sift/2はそれをふるいにかけ素数のストリームをPrimesに返す。integers/3とsift/2とはそれぞれ並行して動き、integers/3で生成された自然数のストリームは変数Nsを介して順次sift/2に渡される。読み出し専用標記により変数Nsによるintegers/3からsift/2へのデータフローの方向が表現され、プロセス間の同期はストリームの各要素が具体化されるまで待つという形で自然に表現される。

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

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

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

filter(Prime,[X|Xs1],[X|Ys1]) :- 0 is X mod Prime | filter(Prime,Xs1?,Ys1).
filter(Prime,[X|Xs1],Ys0    ) :- otherwise        | filter(Prime,Xs1?,Ys0).
filter(_,    [],     []).

応用

Logix

Flat Concurrent Prolog（FCP）の開発環境として、UNIXのシェル風の機能とコンパイラ、デバッガを組み合わせたLogixと呼ばれるシステムが作成された。Logix自身もFCPを使って記述され、C言語で作成されたエミュレータ上で動作する。Logixで使用できる言語は、 FCP(:,?) と呼ばれるFCPの中で最も表現力の高いバリエーションに、プログラムを見やすくするための糖衣構文を付加したものである。また、Guarded Horn Clausesのフラット版である Flat GHC のエミュレーション機能も含む。

関連項目

• 並行論理プログラミング
• 論理プログラミング
• 並行プログラミング
• Prolog

参考文献

• Clark, K, L. and Gregory, S. PARLOG: a parallel logic programming language. Research Report DOC 83/5, Imperial College, London. 1983.
• 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. Doctoral Thesis. Information Engineering Course, University of Tokyo, 1986 (PDF)
• Silverman, W., Hirsch, M.,Houri, A. and Shapiro, E. The Logix System User Manual Version 2.0. Technical Report CS-21, Weizmann Institute of Science, 1993
• Silverman, W., Hirsch, M.,Houri, A. and Shapiro, E. Logix Supplement to User Manual for System 2.2. Weizmann Institute of Science, 1990.
• 古川 康一,溝口 文雄(編), 並列論理型言語GHCとその応用 (知識情報処理シリーズ). 共立出版 1987, ISBN 978-4320022669
• 竹内 彰一, 論理型並列プログラミング言語 : Concurrent Prolog. コンピュータソフトウェア Vol.1 No.2 pp.131-143 1984.

外部リンク

• Extended Flat Concurrent Prolog(efcp)とLogixのページ