PARLOG

PARLOG
パラダイム	並行論理プログラミング
登場時期	1983年
設計者	Keith Clark、Steve Gregory
型付け	動的型付け
主な処理系	PARLOG for Windows, 他
影響を受けた言語	Prolog、Relational Language、Concurrent Prolog、Guarded Horn Clauses
影響を与えた言語	Guarded Horn Clauses、KL1、Strand、PCN
	テンプレートを表示

■カテゴリ / ■テンプレート

PARLOG (PARallel LOGic) は、Concurrent Prologに影響を受けたKeith ClarkとSteve Gregoryにより設計された並行論理プログラミング言語である。複雑なRelational Languageの仕様を整理した後継言語として提案された。1983年に最初のバージョンが発表され、その後1986年に改良版が発表された。言語の特性や細かいシンタックスはそれぞれ異なる。

概要

PARLOGは並行プログラミングのためのプログラミング言語で、論理変数を介して通信を行う複数の軽量プロセスのネットワークとしてプログラムを記述する。 PARLOGではホーン節にガードを導入した以下のような規則の集まりでプログラムを記述する。":"はコミット演算子と呼ばれる。ガード部がない(Guardでの条件が"true"のみ)場合、ガード部とコミット演算子は省略できる。

Head <- Guard : Body.

HeadとGuardはプロセス書き換えのための条件、Bodyは書き換え後のプロセスを表す。条件を満たす規則が複数ある場合はどれか1つが選択される。Prologなどと異なり、コミット後のバックトラックを行わない。Body部は逐次/並行の2通りの実行方法が指定できる。

p , q　　　並行AND：p,qを並行実行
p & q　　　逐次AND：p,qを逐次実行(pが成功した場合のみqを実行)

例えば、 (p, q) & r は、p と q を並行に実行し、両者が成功したとき r を実行する。

プロセス間の通信にはプロセスで共有する論理変数を使用する。書き換え規則の適用に十分な情報がなければ書き換えを中断し、判断に必要な情報が得られるまで待つことで、プロセス間の同期が行われる。多くの場合、プロセス間の通信には論理変数を含んだリストで表現されたストリームを用いる。論理変数を共有するプロセスの数に制限はないため、ストリーム通信は1対1だけではなく1対Nのブロードキャストなど、様々な形態が可能である。

それぞれの述語には入出力のモード宣言が付加される。"?"は入力モード、"^"は出力モードを表す。ヘッド部の同一化の際、アクセスモードが入力モードに指定されている引数は入力のみができ、呼び出し側の変数を変数以外の項に具体化しようとする試みは中断させられる。出力モードとして指定された項が実際に出力されるのは節が選択された後である。

プログラム例

1983年版のPARLOGと1986年に改良されたPARLOGとでは、言語の特性や細かいシンタックスがそれぞれ異なる。 1983年版PARLOGのプログラムの例を以下に示す。 append(x, y, z)は x と y の2つのリストを連結したリストが z であるという関係を表している。Prologと異なり、英小文字で始まる項が変数を表す。relationはモード宣言を示し、複数の組み合わせを指定できる。

relation append(?,?,^)
relation append(?,^,?)
relation append(?,?,?)

append([], y, y).
append([u|x], z, [u|z]) :- append(x, y, z)

1986年版では複雑だった言語仕様を整理し、より効率的な実行が可能になった。1986年版PARLOGのプログラムの例を以下に示す。Prolog同様、英大文字で始まる項が変数を表す。 merge(Xs?,Ys?,Zs^)はXsとYsの2本のストリームをマージして1本のストリームZsにする。modeはモード宣言を示し1述語に1つのみ指定できる。

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

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

PARLOGによるプロセス間の同期の機能は、kernel PARLOGというモード宣言を持たない単純な標準形式に変換することで実現された。PARLOGでモード宣言が果たしていた役割は、特殊な単方向のユニフィケーションを入力側はガード部に、出力側はボディ部に付加することで実現され、ガード部で中断が行われる。例えば、上記プログラムの最初の節はkernel PARLOGで以下の形式に変換された。

merge(X,Ys,Z)<-
  [A|Xs] <= X :  Z = [A|Zs] ,merge(Xs,Ys,Zs).

<= は一方向のユニフィケーションを表し、Xが[A|Xs]のようなリストの形になっていない場合は中断し、他のプロセスにより[A|Xs]の形に具体化された場合に実行を再開する。この時点でXs自体は具体化されていなくてもかまわないため、リストの先頭からインクリメンタルに具体化されるストリームを素直に処理できる。

参考文献

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. 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.
Shapiro, E.. The Family of Concurrent Logic Programming Languages. ACM Computing Surveys, Vol.21, No.3, September 1989.

概要

プログラム例

関連項目

参考文献