logo标签列表

什么是统一算法？

algorithmf#functional-programmingprologunification
5
我知道这可能听起来有些奇怪，但我的问题是：“什么是统一算法”。 我正在尝试开发一个类似于Prolog的F#应用程序。它应该在进行查询时接受一系列事实并对其进行处理。
有人建议我开始实现一个好的统一算法，但我对此一无所知。
如果您想更深入地了解我的要求，请参考this问题。
非常感谢，圣诞快乐。
1
你有没有试过阅读关于这个主题的Wikipedia文章？它可能会给你一个很好的起点。 - Björn Pollex
3个回答
5
如果你有两个带有变量的表达式，那么统一算法会尝试匹配这两个表达式，并为变量提供赋值，使得这两个表达式相同。
例如，如果你用 F# 表示表达式：
type Expr = 
  | Var of string              // Represents a variable
  | Call of string * Expr list // Call named function with arguments

并且有两个像这样的表达式：

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

然后，统一算法应该给您一个分配：
"x" -> Call("woo", [ Var("z") ]

这意味着，如果你替换两个表达式中的“x”变量的所有出现，替换的结果将是相同的表达式。如果你有调用不同函数的表达式（例如Call("foo", ...)和Call("bar", ...)），那么该算法将告诉你它们不可统一。在维基百科上也有一些解释，如果你搜索互联网，你肯定会找到一些有用的描述（甚至可能是类似于F#的某些函数语言的实现）。
看来你是我的F#大师Petricek先生...再次感谢 :) 啊，圣诞快乐。 - Andry
1
Tomas给出了一个很好的解释。正如他所指出的，互联网上可以找到很好的资源。早期的人工智能书籍，比如Prolog鼎盛时期（约1986-1992年），有时也会有非常好的解释和LISP代码，可以适应F#。 - TechNeilogy
2
我发现Baader和Snyder的工作非常有价值。特别是，他们描述了几种合一算法（包括使用并查集的Martelli和Montanari近线性算法），并且描述了语法合一和各种语义合一。
一旦你进行了统一，你还需要回溯。 Kiselyov / Shan / Friedman的LogicT框架对此会有所帮助。
1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接