5

少し奇妙に聞こえるかもしれませんが、私の質問は「統一アルゴリズムとは」です。さて、私は F# で Prolog のように動作するアプリケーションを開発しようとしています。一連の事実を取得し、クエリを作成するときにそれらを処理する必要があります。

優れた統合アルゴリズムの実装を開始するように提案されましたが、これについての手がかりがありませんでした。

私がやりたいことをもう少し深く知りたい場合は、この質問を参照してください。

どうもありがとうございました。メリークリスマス。

4

3 に答える 3

5

変数を含む 2 つの式がある場合、統合アルゴリズムは 2 つの式を一致させようとし、2 つの式が同じになるように変数を割り当てます。

たとえば、F# で式を表現した場合:

type Expr = 
  | Var of string              // Represents a variable
  | Call of string * Expr list // Call named function with arguments

そして、次のような 2 つの式がありました。

Call("foo", [ Var("x"),                 Call("bar", []) ])
Call("foo", [ Call("woo", [ Var("z") ], Call("bar", []) ])

次に、統合アルゴリズムによって次の割り当てが与えられます。

"x" -> Call("woo", [ Var("z") ]

これは、2 つの式で出現する "x" 変数をすべて置き換えると、2 つの置換の結果が同じ式になることを意味します。異なる関数 (Call("foo", ...)と などCall("bar", ...)) を呼び出す式がある場合、アルゴリズムはそれらが単一化できないことを通知します。

WikiPediaにもいくつかの説明があり、インターネットを検索すると、役立つ説明がきっと見つかります (F# に似た関数型言語での実装もあるかもしれません)。

于 2010-12-18T10:25:06.223 に答える
2

Baader と Snyderの研究が最も有益であることがわかりました。特に、それらはいくつかの統合アルゴリズム (共用体検索を使用した Martelli と Montanari のニアリニア アルゴリズムを含む) について説明し、構文上の統合とさまざまな種類の意味上の統合の両方について説明しています。

統合したら、後戻りも必要になります。Kiselyov/Shan/Friedman のLogicT フレームワークがここで役に立ちます。

于 2011-08-02T08:26:44.473 に答える
1

明らかに、破壊的な統合は、純粋な機能的な統合よりもはるかに効率的ですが、F-sharpish もはるかに少なくなります。それが求めているパフォーマンスであれば、おそらく WAM のサブセットを何らかの形で実装することになるでしょう:

http://en.wikipedia.org/wiki/Warren_Abstract_Machine

そして、おそらくこれが役立つでしょう：

http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.3203

于 2010-12-18T13:50:46.913 に答える