制約論理プログラミング

制約論理プログラミング

制約論理プログラミング（Constraint Logic Programming: CLP）は、制約プログラミングの考え方を論理プログラミングに導入することで生まれたプログラミングパラダイムです。これは、問題の対象間の関係を「制約」として宣言的に記述することで、問題解決をより柔軟かつ効率的に行うことを目指します。

概要

制約プログラミングは、問題の対象間の関係を制約として記述する宣言的なアプローチを採用しており、これは述語を用いて関係を記述する論理プログラミングと共通の特徴を持っています。論理プログラミングは、エルブラン領域におけるユニフィケーションによる等号制約を扱う制約プログラミングと見なすことができ、制約論理プログラミングはその自然な拡張となっています。多くのProlog処理系には、制約論理プログラミングの機能やライブラリが提供されています。

制約論理プログラミングは、スケジューリング、要員計画、輸送、資源割り当て、アナログ回路設計、トレーディングなど、多岐にわたる分野に応用されています。プログラムはPrologと同様の形式で記述され、節のボディ部に制約を含めることができます。これらの制約は、手続き型言語の代入文とは異なり、関係性を表現します。

例えば、`parallel_register(50, I, 10, 25)`というプログラムを実行すると、`I = 7`という結果が得られます。プログラムの実行は、規則が順次呼び出されることで進み、途中で現れた制約は制約ストアに格納され、制約評価系によって簡約化されます。

歴史

制約のソフトウェアへの応用は、1963年の対話型グラフィックシステムSKETCHPADに遡ります。プログラミング言語への応用としては、1980年にSteeleらによって開発されたCONSTRAINTSがあり、制約を変数間の関係の規則として記述し、局所制約伝播によって変数の値を決定していました。

1972年にカルメラウアらによって開発されたPrologは、関係の宣言的な表現を汎用プログラミング言語に導入し、論理プログラミングの概念をもたらしました。Prologは、エルブラン領域を対象とした限定的なものでしたが、後に実数や有理数など、より多くの領域での制約を扱うように拡張されました。カルメラウアによるProlog II (1980) は、制約という言葉を明示的に使用した最初の論理プログラミング言語であり、Prolog III (1987) などの制約論理プログラミング言語へと発展しました。

1987年、IBMのJafferとLassezらは制約論理プログラミングスキーマCLP(X)を発表し、制約論理プログラミングの理論化を行いました。CLP(X)に基づいて、実数領域を扱うCLP(R)や有限領域を扱うCLP(FD)などの言語が開発されました。また、CHIP(Constraint Handling In Prolog)やCALなど、多くの制約論理プログラミング言語が開発され、制約論理プログラミングの機能を持つProlog処理系も多数作成されています。

並行して、並行論理プログラミングも制約論理プログラミングの影響を受け、制約で並行処理を制御する並行制約プログラミングとして理論化されました。

領域

制約論理プログラミングにおける制約は、特定の領域に関するものです。領域ごとに制約の指定方法や処理方法が異なります。一般的な領域としては、木、有限領域、ブール領域、算術領域（有理数や実数など）があります。

木 (tree)

論理プログラミングでは、任意の有限木を表す項を基本データとして扱うため、制約論理プログラミングでも木は基本的な計算領域として扱うことができます。ユニフィケーションによる等号制約が基本的な制約となります。

有限領域 (Finite Domains)

有限領域は、有限集合に関する制約を扱う領域です。多くの制約充足問題はこの領域で表現できます。変数の値として有限領域の要素を取り、特定の範囲内の整数などが代表的な例です。

算術領域 (Arithmetic Domain)

算術領域には、整数領域、有理数領域、実数領域などがあります。扱える制約は代数式で表される代数制約で、線型制約と非線型制約に大別されます。線型制約はシンプレックス法などで効率的に解くことができ、多くの制約論理プログラミング言語でサポートされています。

ブール領域 (Boolean Domain)

ブール領域は、真偽値の制約だけを扱う領域です。制約は一般的な論理演算子で構成される等式として表現されます。制約処理方法としては、Booleの変数除去に基づいたブーリアン・ユニフィケーションなどがあります。

処理系

以下に制約論理プログラミング言語の例を挙げます。

B-Prolog
CHIP V5
Ciao Prolog
ECLiPSe
GNU Prolog
Mozart
SICStus Prolog
YAP Prolog
CAL
CHAL
GDCC
Cu Prolog

並行制約プログラミング

並行制約プログラミングは、制約論理プログラミングと並行論理プログラミングの研究から生まれたパラダイムです。制約の出力と入力を複数のプロセスで行うことで、並行処理を実現します。

Constraint Handling Rules (CHR)

Constraint Handling Rules (CHR) は、ユーザ定義の制約を記述できる宣言型プログラミング言語です。多重集合の書換え規則に基づいて制約を処理し、ルールによって制約をより単純な制約に書き換えることで解を求めます。

もう一度検索