並行制約プログラミング
Constraint Handling Rules(CHR)は1991年にThom Frühwirthが発表した多重集合の書換えに基づく制約処理用プログラミング言語であり 、 主にPrologなどのホスト言語上に実装されたライブラリとして提供される事が多い。CHRは並行プログラミングではなく、さまざまな制約下での解を求める制約充足系(constraint solver)の記述を目的としている。また、通常の並行制約プログラミング言語と異なり、制約は追加(tell)ではなく書き換え(削除/追加)を行う。 CHRの特徴は以下の通りである。
頭部にゴール(制約)の多重集合が書ける
多重集合書換えに基づく言語の中では強力
多くの応用プログラムがある
CHRは単純化規則(Simplification rule)と伝播規則(Propagation rule)の2種類の規則、およびそれを組み合わせた規則("Simpagation" rule)からなる。
単純化規則(Simplification rule)
伝播規則(Propagation rule)
単純化規則は、複数の制約を論理的に等価なより単純な制約に変換する。(例えば、X≦Y, Y≦X ⇔ X=Y.)
伝播規則は、論理的には冗長だが単純化に結び付くような制約を新しく追加する。(例えば、X≦Y, Y≦Z ⇒ X≦Z.)
LMNtal(Linked Multisets of Nodes transformation language、エレメンタル)はGHCの設計者である上田らによって開発された多重集合の書換えに基づく分散処理向け制約処理の言語モデルで、計算を階層的なグラフ構造の書き換えであるとした点に特徴がある。 プロセスやルールは膜によってグループ化され、計算の局所化とグラフの階層化に利用される。循環構造や密に結合したデータ構造を容易に扱うことができ、またチャネルモビリティとプロセスモビリティの両方を備えている。JavaやC言語による言語処理系が開発されている。