制約論理プログラミング
カルメラウアによるProlog II(1980)は制約という言葉を明示的に使用した最初の論理プログラミング言語である。 これはさらにProlog III(1987)などの制約論理プログラミング言語に発展した。 IBMのJafferやLassezらは1987年に制約論理プログラミングスキーマCLP(X)を発表し、制約論理プログラミングの理論化を行った。CLP(X)に基づき実数領域の制約を扱うCLP(R)、有限領域を扱うCLP(FD)などの各種言語が開発された。また、CHIP(Constraint Handling In Prolog)やCALなど多くの制約論理プログラミング言語が開発された。また制約論理プログラミングの機能を持つProlog処理系も多数作成されている。 これらの制約論理プログラミングの研究と並行して、論理プログラミングの並行処理への応用として1980年代に研究された並行論理プログラミングも制約論理プログラミングの影響を受け、制約で並行処理を制御する並行制約プログラミングとして理論化が行われた。
問題の対象間の関係を制約(例えば V=I*R )という形で宣言的に記述する制約プログラミングの考え方は、述語という形で関係を宣言的に記述する論理プログラミングと多くの特徴を共有している。理論的に、論理プログラミングはエルブラン領域(Herbrand universe)という有限木で表される領域上でのユニフィケーションによる等号制約を扱う制約プログラミングと見なすことができ、制約論理プログラミングはその自然な拡張となっている。論理プログラミングの代表的な言語であるProlog処理系の多くには、何らかの制約論理プログラミングの機能やライブラリが用意されている。
制約論理プログラミングの応用分野は、スケジューリング、要員計画・輸送・資源割り当て、アナログ回路設計、トレーディングなどさまざまなものがある。
一般に、制約論理プログラムはPrologなどの論理プログラムと同様の形式で記述するが、節(clause)のボディ部に制約を含めることができる。以下の例では V = I*R などが制約である。手続型言語の代入文とは異なり、これらの式は関係を表現している。
例えば、上記のプログラムで ?- parallel_register(50,I,10,25). を実行すると I = 7 が結果として返る。
プログラムの実行は、論理プログラムと同じように、規則が順次呼び出されることで行われる。途中で現れた制約(例えば I1+I2=I )は、いったんシステム内部の制約ストアと呼ばれる領域に格納され、順次内部の制約評価系でより単純な形に簡約化が行われる(例えば I1+I2=I & 50=I1*10 → 5+I2=I )。
制約論理プログラミングの論理的意味や操作的意味、不動点意味論上の分析はIBMのJafferやLassezらにより与えられている。以下では操作的意味について扱う。