並行制約プログラミング
Relational Language、Concurrent Prolog、Guarded Horn Clauses (GHC)とGHCの拡張であるKL1、PARLOG、Strandなどの並行論理プログラミング言語は、並行制約プログラミング言語の一種としてとらえることができる。 多くの言語はホーン節にガードを導入した形式でプログラムを記述するが、それらのガード部は制約の観測を行うask部と制約の追加を行うtell部の組み合わせとして一般化できる。
1987年にMichael Maherはより抽象化された並行論理プログラミングの論理的解釈を与え、並行論理プログラミングでの通信と同期とを制約ストア(変数値に関する部分情報の格納場所)と受信したい情報との含意(implication)の関係として定式化した 。Vijay Saraswatらはこれらの解釈を特定のデータ領域に限定しない制約全般に広げ、より一般化された並行制約プログラミングの計算理論が整備された。
並行制約プログラミングはその後さらに拡張され、離散変化を扱う時間並行制約プログラミング(Timed Concurrent Constraint Programming)や、離散・連続の両変化を扱うハイブリッド並行制約プログラミング(Hybrid Concurrent Constraint Programming)などが生まれた。
並行制約プログラミングが他の多くのプログラミングパラダイムと異なる部分は、通常の手続型言語のような「値を格納」するという考え方ではなく「制約を格納」する、という考え方である。制約(例えば"X ≧ 10")は特定の変数に対する部分情報を表している。計算中、システムの状態は制約ストア(store)と呼ばれる制約の集合で表される。プロセスは制約ストアに別の制約(例えば"X ≦ 20")を追加(tell)することでシステムの状態を変更し、制約ストアの観測(ask)を行い与えられた制約が制約ストアの内容から導き出せるか調べることで同期と通信を行う。
プロセス計算(process calculi)の立場でみた場合、並行制約プログラミングは以下のオペレータから構成される。
追加(tell):制約を追加する
観測(ask):制約が制約ストアから導き出せるか問い合わせる
並列合成(Parallel Composition):プロセスを並行に組み合わせる
隠蔽(hiding、restrictionやlocalityとも呼ばれる):ローカル変数を導入し他のプロセスとのインタフェースを制限する
例えば、並行論理プログラミングは、並行制約プログラミングをエルブラン領域(Herbrand universe)という有限木で表されるデータ領域に適用し、制約を等号制約(ユニフィケーション)のみに制限したものと見なすことができ、プログラムを以下の節の集まりで表現したものととらえることができる。
ここでhは原子論理式、Bは原子論理式の集まりでプロセスの並列合成を表す。ask、tellはそれぞれ制約の観測と追加の集まりである。