制約論理プログラミング

制約論理プログラミング（せいやくろんりプログラミング、英: constraint logic programming）は制約プログラミングの一種で、制約という問題表現・解決の考え方を導入することによって論理プログラミングを拡張したプログラミングパラダイムである。論理プログラミングの持っている宣言的な表現力に制約の考え方を導入し、より一般化したものとも言うことができる。

概要

問題の対象間の関係を制約（例えば V=I*R ）という形で宣言的に記述する制約プログラミングの考え方は、述語という形で関係を宣言的に記述する論理プログラミングと多くの特徴を共有している。理論的に、論理プログラミングはエルブラン領域(Herbrand universe)という有限木で表される領域上でのユニフィケーションによる等号制約を扱う制約プログラミングと見なすことができ、制約論理プログラミングはその自然な拡張となっている。論理プログラミングの代表的な言語であるProlog処理系の多くには、何らかの制約論理プログラミングの機能やライブラリが用意されている。
制約論理プログラミングの応用分野は、スケジューリング、要員計画・輸送・資源割り当て、アナログ回路設計、トレーディングなどさまざまなものがある。
一般に、制約論理プログラムはPrologなどの論理プログラムと同様の形式で記述するが、節（clause）のボディ部に制約を含めることができる。以下の例では V = I*R などが制約である。手続型言語の代入文とは異なり、これらの式は関係を表現している。
register(V,I,R) :- V = I*R.     % オームの法則parallel_register(V,I,R1,R2) :- I1+I2=I, register(V,I1,R1), register(V,I2,R2).  % 並列回路serial_register(V,I,R1,R2)   :- V1+V2=V, register(V1,I,R1), register(V2,I,R2).  % 直列回路
例えば、上記のプログラムで ?- parallel_register(50,I,10,25). を実行すると I = 7 が結果として返る。
プログラムの実行は、論理プログラムと同じように、規則が順次呼び出されることで行われる。途中で現れた制約（例えば I1+I2=I ）は、いったんシステム内部の制約ストアと呼ばれる領域に格納され、順次内部の制約評価系でより単純な形に簡約化が行われる（例えば I1+I2=I & 50=I1*10 → 5+I2=I ）。

歴史

制約をソフトウェアに応用する試みは、初期の対話型グラフィックシステムであるSKETCHPAD(1963)にまでさかのぼることができる。 プログラミング言語への応用としては、Steeleらにより開発されたCONSTRAINTS(1980)  があり、制約を変数間の関係の規則として記述し、局所制約伝播（local constraints propagation）により変数の値を順次決めていくことで、制限された範囲ではあるが制約を扱うことができた。
1972年にカルメラウアらにより開発されたPrologは、関係の宣言的な表現という視点を汎用プログラミング言語に持ち込むことに成功し、論理プログラミングという考え方をもたらした。しかしそれはエルブラン領域(Herbrand universe)を対象とした限定されたもので、実数や有理数など他の領域のデータの扱いは通常の関数型言語や手続型言語と変わりがなかった。Prologは、論理プログラミングの宣言的な性格を活かしつつ表現力や処理効率を上げるため、より多くの領域での一般的な制約を扱うように拡張された。カルメラウアによるProlog Ⅱ(1980)は制約という言葉を明示的に使用した最初の論理プログラミング言語である。  これはさらにProlog Ⅲ(1987)などの制約論理プログラミング言語に発展した。 IBMのJafferやLassezらは1987年に制約論理プログラミングスキーマCLP(X)を発表し、制約論理プログラミングの理論化を行った。CLP(X)に基づき実数領域の制約を扱うCLP(R)、有限領域を扱うCLP(FD)などの各種言語が開発された。また、CHIP(Constraint Handling In Prolog)やCALなど多くの制約論理プログラミング言語が開発された。また制約論理プログラミングの機能を持つProlog処理系も多数作成されている。 これらの制約論理プログラミングの研究と並行して、論理プログラミングの並行処理への応用として1980年代に研究された並行論理プログラミングも制約論理プログラミングの影響を受け、制約で並行処理を制御する並行制約プログラミングとして理論化が行われた。

領域

制約論理プログラミングにおける制約は何らかの特定の領域（Domain）に関するものである。対象とする領域ごとに制約の指定方法や処理方法は異なる。制約論理プログラミングでの一般的な領域としては、論理プログラミングの基本的な計算領域である木以外に、有限領域、ブール領域、有理数や実数などを扱う算術領域がある。

有限領域

有限領域（Finite Domains）は、有限集合について制約を扱う領域である。多くの制約充足問題はこの領域で表現することができる。変数の値として有限領域の要素をとるもので、特定の範囲内の整数などがその代表である。個々の変数について、例えば1から5までの整数であれば X::[1..5] （あるいは X::[1,2,3,4,5] ）のように領域が指定される。数値以外であれば X::[george,mary,john] のような形になる。 有限領域での制約としては算術式による制約や記号的制約などが使われ、言語により指定方法は異なる。以下は古典的な覆面算 SEND+MORE=MONEY を解くプログラムの例である。
sendmore(Digits) :-
    Digits = [S,E,N,D,M,O,R,Y],        % 変数生成
    Digits :: [0..9],                  % 変数の領域を定義
    S #\= 0,                           % 制約: S, M は 0 ではない
    M #\= 0,
    alldifferent(Digits),              % 制約: 要素はそれぞれ異なった値となる
    1000*S+100*E+10*N+D + 1000*M+100*O+10*R+E
      #= 10000*M+1000*O+100*N+10*E+Y,  % 制約: SEND+MORE=MONEY
    labeling(Digits).                  % 探索開始
有限領域では、制約の一貫性チェックにより各変数の取りえる領域が変化した場合、その変化を制約伝播により他の関連する変数の領域に反映し、解の範囲を順次狭めていくことで最終的な解を求めることが多い。全体の一貫性が取れなくなった場合はバックトラックを行い途中からやり直す。

ブール領域

ブール領域（Boolean Domain）は真偽値の制約だけを扱う領域である。制約は一般的な論理演算子で構成される等式として表現される。制約処理方法としては、Booleの変数除去に基づいたブーリアン・ユニフィケーションやSL-導出（SL-resolution）のブール式への応用など様々なものがある。Prolog ⅢやCHIP(Constraint Handling In Prolog)などの処理系ではブール領域の制約を扱うことができる。

セマンティック

制約論理プログラミングの論理的意味や操作的意味、不動点意味論上の分析はIBMのJafferやLassezらにより与えられている。以下では操作的意味について扱う。

並行制約プログラミング

並行制約プログラミング(Concurrent Constraint Programming)は、制約論理プログラミングの研究と並行論理プログラミングの研究とから生まれた、並行プログラミングのためのパラダイムである。並行制約プログラミングでは並行論理プログラミングをより一般化し、制約の出力(追加, tell)と入力(観測, ask)を行う複数のプロセス（エージェント）でプログラミングを行う。 並行制約プログラミングは、制約充足系（constraint solver）の記述ではなく、複数のプロセス（エージェント）の制御やプロセス間通信の記述を目的としている。