Constraint Handling Rules
合流性(Confluence)とは、書き換えが可能な部分式が複数存在する際に、どの書き換え規則をどの部分式に適用して書き換えたとしても最終的な結果が合流する(一意に定まる) という性質のことである。合流性の無いプログラムは、最終的な実行結果が実行ごとに異なる可能性がある。一般的な項書き換えシステムと同様、停止性を持つCHRプログラムの合流性には、決定可能な必要条件と十分条件がある。停止性と合流性を持つCHRプログラムはルールの適応順序によらない一貫性のある論理的な意味を持ち、解くべき問題の異なった部分に対してルールを並列に適用できるような、並行してインクリメンタルに問題を解くアルゴリズムをインプリメントできる。
エラストテネスのふるいにより素数を求めるプログラムの例を示す。generate0/1の2つのルールはprime(2)、...、prime(N)のデータを生成し、siftルールは素数のみを選び出す。generate0/1ルールとsiftルールは(もし必要であれば)並行して実行することも可能である。
■カテゴリ / ■テンプレート
Constraint Handling Rules(CHR)は1991年にThom Frühwirthが発表した、ユーザ定義の制約が書けるように設計された宣言型プログラミング言語である 。 多重集合の書き換え規則に基づく制約処理モデルを特徴とし、ルールにより制約をより単純な制約に書き換えることで、様々な制約下での解を求める。CHRはチューリング完全だが、 独立した言語としてではなく既存言語の拡張機能として、主にPrologなどのホスト言語上に実装されたライブラリとして提供される。 CHRの典型的な応用分野はアブダクションなどの推論サービス、マルチエージェントシステム、自然言語処理、スケジューリング、型システム、ソフトウェアのテストと診断、セマンティックウェブなどである。