algorithm - 什么是统一算法？

Question

嗯，我知道这听起来可能有点奇怪，但我的问题是:“什么是统一算法”。好吧，我正在尝试用 F# 开发一个应用程序，使其像 Prolog 一样运行。它应该在进行查询时获取一系列事实并对其进行处理。

有人建议我开始实现一个好的统一算法，但对此一无所知。

请引用this问你是否想更深入地了解我想做的事情。

非常感谢你，圣诞快乐。

Answer 1

如果您有两个带变量的表达式，则统一算法会尝试匹配这两个表达式并为您分配变量以使两个表达式相同。

例如，如果您在 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", ...))，那么算法会告诉您你知道它们不是统一的。

还有一些explanation in WikiPedia如果您在 Internet 上搜索，您一定会找到一些有用的描述(甚至可能是某种类似于 F# 的函数式语言的实现)。