142

当我想阅读逻辑编程时，我总是会偶然发现两种“主要”方法：

  • miniKanren是The Reasoned Schemer中引入的一种迷你语言，由于core.logic而在当时很流行。
  • Prolog，第一个“大”逻辑编程语言。

我现在感兴趣的是：两者之间的主要技术差异是什么？它们在方法和实现上是否非常相似，或者它们采用完全不同的逻辑编程方法？它们来自数学的哪些分支，理论基础是什么？

4

2 回答 2

305

首先，请允许我称赞您的精美 pw0n1e 图标。

这是一个很难回答的问题，主要是因为 miniKanren 和 Prolog 都有很多变体。miniKanren 和 Prolog 是真正的语言家族，这使得很难比较它们的功能，甚至它们在实践中的使用方式。因此，请谨慎对待我要说的一切：如果我说 Prolog 使用深度优先搜索，请注意许多 Prolog 实现支持其他搜索策略，并且替代搜索策略也可以在元编码- 口译员级别。尽管如此，miniKanren 和 Prolog 有不同的设计理念，并做出不同的取舍。

Prolog 是符号人工智能编程的两种经典语言之一（另一种经典语言是 Lisp）。Prolog 擅长实现基于符号规则的系统，其中声明性知识以一阶逻辑编码。该语言针对这些类型的应用程序的表现力和效率进行了优化，有时以牺牲逻辑纯度为代价。例如，默认情况下 Prolog 不使用统一中的“发生检查”。从数学/逻辑的角度来看，这个版本的统一是不正确的。但是，发生检查很昂贵，并且在大多数情况下，缺少发生检查不是问题。这是一个非常务实的设计决策，Prolog 使用深度优先搜索和使用 cut (!) 来控制回溯。我确信这些决定在 1970 年代的硬件上运行时是绝对必要的，而今天在处理大型问题以及处理巨大（通常是无限的！）搜索空间时非常有用。

Prolog 支持许多“超逻辑”或“非逻辑”功能，包括 cutassert和retract，用于算术的变量投影is，等等。许多这些特性使表达复杂的控制流和操纵 Prolog 的全球事实数据库变得更加容易。Prolog 的一个非常有趣的特性是 Prolog 代码本身存储在全局事实数据库中，并且可以在运行时进行查询。这使得编写修改 Prolog 代码在解释下的行为的元解释器变得微不足道。例如，可以使用改变搜索顺序的元解释器在 Prolog 中对广度优先搜索进行编码。这是一种非常强大的技术，在 Prolog 世界之外并不为人所知。“序言的艺术”详细描述了这种技术。

在改进 Prolog 实现方面付出了巨大的努力，其中大部分都基于 Warren Abstract Machine (WAM)。WAM 使用副作用模型，其中值被破坏性地分配给逻辑变量，这些副作用在回溯时被撤消。通过扩展 WAM 的指令，可以将许多功能添加到 Prolog。这种方法的一个缺点是，如果没有对 WAM 的深入了解，Prolog 实现论文可能难以阅读。另一方面，Prolog 实现者有一个共同的模型来讨论实现问题。对并行 Prolog 进行了大量研究，最终在 1990 年代的 Andorra Prolog 中达到顶峰。至少其中一些想法存在于 Ciao Prolog 中。（Ciao Prolog 充满了有趣的想法，其中许多远远超出了 Prolog 的标准。）

Prolog 有一个漂亮的基于统一的“模式匹配”风格的语法，可以产生非常简洁的程序。Prologers 喜欢他们的语法，就像 Lispers 喜欢他们的 s 表达式一样。Prolog 还有一个大型的标准谓词库。由于所有使 WAM 变得快速的工程，有非常强大和成熟的 Prolog 实现。结果，许多基于知识的大型系统完全用 Prolog 编写。

miniKanren 被设计为一种最小逻辑编程语言，具有小型、易于理解和易于破解的实现。miniKanren 最初嵌入在 Scheme 中，在过去十年中已被移植到数十种其他宿主语言中。最流行的 miniKanren 实现是 Clojure 中的“core.logic”，它现在有许多类似 Prolog 的扩展和一些优化。最近，miniKanren 实现的核心进一步简化，产生了一个称为“microKanren”的微小“微内核”。然后可以在这个 microKanren 核心之上实现 miniKanren。将 microKanren 或 miniKanren 移植到新的宿主语言已成为程序员学习 miniKanren 的标准练习。因此，

miniKanren 和 microKanren 的标准实现不包含突变或其他副作用，只有一个例外：某些版本的 miniKanren 使用指针相等来比较逻辑变量。我认为这是一种“良性效应”，尽管许多实现甚至通过在实现中传递一个计数器来避免这种效应。也没有全球事实数据库。miniKanren 的实现理念受到函数式编程的启发：应避免突变和影响，所有语言结构都应尊重词法范围。如果您仔细查看实现，您甚至可能会发现几个 monad。搜索实现基于组合和操作惰性流，再次不使用突变。这些实现选择导致了与 Prolog 中截然不同的权衡。在 Prolog 中，变量查找是常数时间，但回溯需要撤消副作用。在 miniKanren 中，变量查找更昂贵，但回溯是“免费的”。事实上，由于流的处理方式，miniKanren 中没有回溯。

miniKanren 实现的一个有趣方面是代码本质上是线程安全的，并且——至少在理论上——可以简单地并行化。当然，在不减慢代码的情况下并行化代码并非易事，因为必须为每个线程或进程分配足够的工作来弥补并行化的开销。尽管如此，这是 miniKanren 实现的一个领域，我希望能得到更多的关注和实验。

miniKanren 使用发生检查进行统一，并使用完整的交错搜索而不是深度优先搜索。交错搜索比深度优先搜索使用更多的内存，但在深度优先搜索将永远发散/循环的某些情况下可以找到答案。miniKanren确实支持一些额外的逻辑运算符——例如 conda，、condu和。并且可以用来模拟Prolog的cut，可以用来获取一个逻辑变量关联的值。projectcondaconduproject

conda、condu和的存在project---以及轻松修改搜索策略的能力---允许程序员使用 miniKanren 作为嵌入式 Prolog 语言。对于 Clojure 的“core.logic”用户来说尤其如此，它包括许多类似 Prolog 的扩展。miniKanren 的这种“实用”使用似乎占 miniKanren 在工业中的大部分使用。想要将基于知识的推理系统添加到用 Clojure 或 Python 或 JavaScript 编写的现有应用程序的程序员通常对用 Prolog 重写他们的整个应用程序不感兴趣。在 Clojure 或 Python 中嵌入一种小型逻辑编程语言更具吸引力。据推测，嵌入式 Prolog 实现也可以用于此目的。

除了使用 miniKanren 作为一种在精神上类似于 Prolog 的实用嵌入式逻辑编程语言之外，miniKanren 还被用于“关系”编程的研究。也就是说，在编写表现为数学关系而不是数学函数的程序时。例如，在 Scheme 中，append函数可以附加两个列表，返回一个新列表：函数调用(append '(a b c) '(d e))返回列表(a b c d e)。但是，我们也可以将append其视为三位关系而不是两个参数的函数。然后调用(appendo '(a b c) '(d e) Z)会将逻辑变量Z与列表相关联(a b c d e)。当然，当我们将逻辑变量放在其他位置时，事情会变得更有趣。呼叫与(appendo X '(d e) '(a b c d e))关联，而呼叫X(a b c)(appendo X Y '(a b c d e))associateX和Ywith 成对的列表，当附加时，等于(a b c d e). 例如X=(a b)和Y=(c d e)就是这样一对值。我们也可以写(appendo X Y Z)，这将产生无限多的三元组列表X，，Y和Z这样的附加X到Y产生Z。

这个关系版本append可以很容易地在 Prolog 中表达，并且确实在许多 Prolog 教程中都有展示。在实践中，更复杂的 Prolog 程序倾向于使用至少一些额外的逻辑特征，例如 cut，这会抑制将生成的程序视为关系的能力。相比之下，miniKanren 被明确设计为支持这种风格的关系编程。最新版本的 miniKanren 支持符号约束求解 ( symbolo, numbero,absento，不等式约束，名义逻辑编程），以便更容易将非平凡程序编写为关系。在实践中，我从不使用 miniKanren 的任何额外逻辑功能，并且我将所有 miniKanren 程序都编写为关系。最有趣的关系程序是 Scheme 子集的关系解释器。这些解释器有许多有趣的能力，比如生成一百万个对 list 求值的 Scheme 程序(I love you)，或者生成 quines（对自己求值的程序）。

miniKanren 为启用这种关系型编程进行了许多权衡，这与 Prolog 所做的权衡非常不同。随着时间的推移，miniKanren 增加了更多的符号约束，真正成为一种面向符号的约束逻辑编程语言。在许多情况下，这些符号约束使得避免使用像conduand之类的额外逻辑运算符变得切实可行project。在其他情况下，这些符号约束是不够的。更好地支持符号约束是 miniKanren 研究的一个活跃领域，以及如何将更大和更复杂的程序编写为关系的更广泛的问题。

简而言之，miniKanren 和 Prolog 都有有趣的特性、实现和使用，我认为这两种语言的思想都值得学习。还有其他非常有趣的逻辑编程语言，例如 Mercury、Curry 和 Gödel，它们各自对逻辑编程都有自己的看法。

我将以一些 miniKanren 资源结束：

miniKanren 主网站： http ://minikanren.org/

我对关系编程和 miniKanren 进行了一次采访，包括与 Prolog 的比较：http: //www.infoq.com/interviews/byrd-relational-programming-minikanren

干杯，

- 将要

于 2015-02-17T06:49:08.923 回答
7

暂定答案：

AFAIK，“The Reasoned Schemer”以 Scheme-y 语法和函数式编程风格介绍了基本逻辑编程，特别是在布尔值“#t”中添加了常量目标“#u”（失败）和“#s”（成功） ”和“#f”。它使用与 Prolog 相同的逻辑编程方法：统一和回溯搜索。我会看看周末是否有时间从书架上取回那本书。数学的分支是一种受限形式的一阶逻辑，在这种情况下是 Horn 子句和 Resolution Unfication。请参阅：计算逻辑：约翰·艾伦·罗宾逊 (John Alan Robinson ) 的过去的记忆和未来的挑战和罗伯特·科瓦尔斯基 (Robert Kowalski ) 的逻辑编程的早期，以了解冷启动。

于 2015-02-13T21:21:23.947 回答