パターンマッチングの変数置換？

Question

私は推論エンジンを開発しています。これは、基本的に、基本的には特定の瞬間の世界の表現である「事実」があることを意味します。事実（通常は2つだけで、開始状態と目標状態）と一緒に、私は多くのルールを持っています（文字通り特定の問題では数百になるかもしれません）。推論エンジンの目的は、開始状態と一連のルールが与えられれば、受け入れ可能な目標状態の1つに最短経路を見つけることです。これは、DFS、BFS、A *などのいくつかのアルゴリズムで行うことができます。プログラムの基本的な構造は次のとおりです。ルールで

 
fact factname 
    attribute1 = "value"; 
    attribute2 = [ 1, 2, 3]; 
    attribute3 = 4; 
    attribute4 = 7; 
    ... 
endFact 

rule ruleOne 
    equalsto(attribute, "value") or 
    greaterthan(attribute, 5) 
    > 
    remove(attribute); 
endRule 

rule ruleTwo 
    isprimeinteger(attribute) 
    > 
    add(attribute, 1) 
endRule 

、LHS（>前の部分）が「値」と等しい実際factnameですべての属性と一致します。この場合は1つだけですが、多くの場合があります。 これは変数を解決する必要があることを意味します（同じ事実のためにしばしば複数回）。規則のLHSには複数の条件が入れられているか、適切な優先度解析が行われている可能性があります。

問題はこの種の変数を解決する方法がありますか？私が今やっていることは、事実のすべての属性を繰り返し処理することです。基本的には、かなり大きなn-aryツリーを生成しています。これは不均衡でもあります。

は、私は簡単なハッシュテーブルはOになるところ、あなたはO（N）アルゴリズムを使用している

Answer 1

ここには大きな驚きをパターンマッチングのこの種の論文に愛のポインタをいただきたい（1）。ハッシュテーブルは、各属性値に対して対応する属性を格納する。

Answer 2

私はあなたの投稿に統一という単語を使用していないことに気付きました。それはあなたが実装しようとしているアルゴリズムは一般的に呼ばれているものです。記事を参照してくださいWikipedia;スペースやサイクルが重要だった70年代からのものも含まれています。

Answer 3

eduffy has it：これを統一といいます。 Prologは、一般的な場合にしようとしていることを正確に行うように設計されたプログラミング言語であり、統一を使用してその汚い作業を行います。

しかし、PrologでPeano公理を使用して算術演算を実装しようとしている人は、常に最速の方法で取得できるとは限りません。おおよそ同じことをするが、ソルバーが可能な限り迅速に最適なソリューションを見つけるのに役立つヒューリスティックを提供することに重点を置いている「制約プログラミング」言語があります。それらの1つはCometです。