並行論理プログラミング（へいこうろんり?、英: 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=[].
他のプログラミングパラダイムとの比較
手続型プログラミング

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

時間変化する計算状態を意識する必要がないという点で、並行論理プログラミングは関数型プログラミングによく似ている。