並行論理プログラミング
並行論理プログラミング(へいこうろんり-、英: Concurrent Logic Programming)は、論理プログラミングにおける並列性及び論理プログラミングによる並行処理の記述の研究から生まれた、並行プログラミングのためのパラダイムである。論理プログラミングでは述語論理式をゴール(Goal)の書き換え規則と見なし、ゴールの書き換えによって処理を行う。それに対し、並行論理プログラミングでは各ゴールをプロセスと見なして並行に書き換えを行い、ゴール間で共有する論理変数を通信チャネルとして情報交換や同期を行う。
データの並びを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つのリストにまとめたい場合に差分リストが使われる。
ヘッドとガード部はプロセス書き換えのための条件を指定する。条件の指定方法は言語により異なるが、一般的には制約の観測を行うAsk部と制約の追加を行うTell部からなる。Ask部は、その実行が新たな制約を出力しないことを条件として指定する。つまりAsk部は制約の観測のみを行うことができ、値が決まっていない外部の変数を具体化しようとする(具体的な値を与える)など制約を出力する可能性がある場合、値が決まるまで書き換えを中断する。このようなAskは Blocking Ask と呼ばれる。Tell部は、コミット時に制約を出力してもよいが、その実行が今までの結果と矛盾しないことを条件として指定するために使用する。ガードのTell部における制約の出力は矛盾の検査と制約の追加をアトミックに行うため Atomic Tell と呼ばれる。ガード以外での制約の追加は、その実施を遅延できるため Eventual Tell と呼ばれる。
同時に並行論理プログラミングでの様々なプログラミング手法がConcurrent Prolog上で開発された。 Concurrent Prologに影響を受けたClarkらは、Relational Languageの後継言語であるPARLOGを設計した。
第五世代コンピュータプロジェクトで並列マシンの核言語の検討をしていた上田は、Concurrent Prologを分析する過程で問題点を見つけ、さらに単純化したGuarded Horn Clauses (GHC)という言語を1985年に発表し、 これを拡張したKL1 (Kernel Language 1) は並列マシンのオペレーティングシステムや言語処理系、様々な応用プログラムの作成に利用された。 GHCはPARLOGにも影響を与え、最終的にGHCとPARLOGは非常に似たものとなった。 Fosterらはこれらの言語の研究成果を取り入れ、GHCによく似たStrandという商用ベースの言語を1989年に発表した。この言語はErlang開発初期にベース言語として使われた。
これらの並行論理プログラミングの研究と並行して、論理プログラミングに様々な制約条件を取り入れる制約論理プログラミングの考え方が生まれた。これが並行論理プログラミングと結び付き、制約の出力(追加, Tell)と入力(観測, Ask)で並行実行を制御する並行制約プログラミング(Concurrent Constraint Programming)として統合され、Saraswatらによって計算理論が整備された。