Prolog 和 miniKanren 在逻辑编程方面的主要技术区别是什么? [英] What are the main technical differences between Prolog and miniKanren, with respect to logic programming?

问题描述

如今，当我想阅读逻辑编程时，我总是会偶然发现两种主要"方法:

When I want to read up on logic programming I always stumble over two "main" ways to do it nowadays:

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

• miniKanren, a minilanguage introduced in The Reasoned Schemer and popular at the moment due to core.logic.
• Prolog, the first "big" logic programming language.

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

What I'm interested in now: What are the principal technical differences between the two? Are they very similar in approach and implementation, or do they take completely different approaches to logic programming? Which branches of mathematics do they come from, and what are the theoretical foundations?

推荐答案

首先，请允许我赞美你的 pw0n1e 图标.

First, allow me to compliment you on your fine pw0n1e icon.

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

This is a tricky question to answer, largely because there are so many variants of both miniKanren and Prolog. miniKanren and Prolog are really families of languages, which makes it difficult to compare their features, or even how they are used in practice. Because of this, please take everything I'm about to say with caution: if I say that Prolog uses depth-first search, be aware that many Prolog implementations support other search strategies, and that alternate search strategies can also be encoded at the meta-interpreter level. Still, miniKanren and Prolog have different design philosophies, and make different trade-offs.

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

Prolog is one of the two classic languages for symbolic artificial intelligence programming (the other classic language being Lisp). Prolog excels at implementing symbolic rule-based systems in which declarative knowledge is encoded in first-order logic. The language is optimized for expressiveness and efficiency for these types of applications, sometimes at the expense of logical purity. For example, by default Prolog does not use the "occur check" in unification. From a math/logic standpoint, this version of unification is incorrect. However, the occur check is expensive, and in most cases the lack of the occur check is not a problem. This is a very pragmatic design decision, as is Prolog's use of depth-first search, and use of cut (!) to control backtracking. I'm sure these decisions were absolutely necessary when running on the hardware of the 1970s, and today are very useful when working on large problems, and when dealing with huge (often infinite!) search spaces.

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

Prolog supports many "extra-logical" or "non-logical" features, including cut, assert and retract, projection of variables for arithmetic using is, and so forth. Many of these features make it easier to express complex control flow, and to manipulate Prolog's global database of facts. One very interesting feature of Prolog is that Prolog code is itself stored in the global database of facts, and can be queried against at run time. This makes it trivial to write meta-interpreters that modify the behavior of Prolog code under interpretation. For example, it is possible to encode breadth-first search in Prolog using a meta-interpreter that changes the search order. This is an extremely powerful technique that is not well known outside of the Prolog world. 'The Art of Prolog' describes this technique in detail.

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

Tremendous effort has gone into improving Prolog implementations, most of which are based on the Warren Abstract Machine (WAM). The WAM uses a side-effecting model in which values are destructively assigned to logic variables, with these side-effects being undone upon backtracking. Many features can be added to Prolog by extending the instructions of the WAM. One disadvantage of this approach is that Prolog implementation papers can be difficult to read without a solid understanding of the WAM. On the other hand, Prolog implementer have a common model for discussing implementation issues. There has been a great deal of research in parallel Prolog, culminating in Andorra Prolog in the 1990s. At least some of these ideas live on in Ciao Prolog. (Ciao Prolog is full of interesting ideas, many of which go far beyond the Prolog standard.)

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

Prolog has a beautiful unification-based "pattern-matching"-style syntax that results in very succinct programs. Prologers love their syntax, just like Lispers love their s-expressions. Prolog also has a large library of standard predicates. Due to all of the engineering that has gone into making the WAM fast, there are very capable and mature Prolog implementations. As a result, many large knowledge-based systems have been written entirely in Prolog.

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

miniKanren was designed as a minimal logic programming language, with a small, easily understandable, and easily hackable implementation. miniKanren was originally embedded in Scheme, and has been ported to dozens of other host languages over the past decade. The most popular miniKanren implementation is 'core.logic' in Clojure, which now has many Prolog-like extensions and a number of optimizations. Recently the core of the miniKanren implementation has been simplified even further, resulting in a tiny "micro kernel" called "microKanren." miniKanren can then be implemented on top of this microKanren core. Porting microKanren or miniKanren to a new host language has become a standard exercise for programmers learning miniKanren. As a result, most popular high-level languages have at least one miniKanren or microKanren implementation.

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

The standard implementations of miniKanren and microKanren contain no mutation or other side-effects, with a single exception: some versions of miniKanren use pointer equality for comparison of logic variables. I consider this a "benign effect," although many implementations avoid even this effect by passing a counter through the implementation. There is also no global fact database. miniKanren's implementation philosophy is inspired by functional programming: mutation and effects should be avoided, and all language constructs should respect lexical scope. If you look carefully at the implementation you might even spot a couple of monads. The search implementation is based on combining and manipulating lazy streams, once again without using mutation. These implementation choices lead to very different trade-offs than in Prolog. In Prolog, variable lookup is constant time, but backtracking requires undoing side-effects. In miniKanren variable lookup is more expensive, but backtracking is "free." In fact, there is no backtracking in miniKanren, due to how the streams are handled.

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

One interesting aspect of the miniKanren implementation is that the code is inherently thread-safe and---at least in theory---trivially parallelizable. Of course, parallelizing the code without making it slower is not trivial, given that each thread or process must be given enough work to make up for the overhead of parallelization. Still, this is an area of miniKanren implementation that I hope will receive more attention and experimentation.

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

miniKanren uses the occur check for unification, and uses a complete interleaving search instead of depth-first search. Interleaving search uses more memory than depth-first search, but can find answers in some cases in which depth-first search will diverge/loop forever. miniKanren does support a few extra-logical operators---conda, condu, and project, for example. conda and condu can be used to simulate Prolog's cut, and project can be used to get the value associated with a logic variable.

conda、condu 和 project 的存在——以及轻松修改搜索策略的能力——允许程序员使用 miniKanren 作为嵌入式 Prolog 语言.对于 Clojure 的core.logic"用户来说尤其如此，它包括许多类似 Prolog 的扩展.miniKanren 的这种实用"使用似乎占 miniKanren 在工业中的大部分使用.想要将基于知识的推理系统添加到用 Clojure 或 Python 或 JavaScript 编写的现有应用程序的程序员通常对用 Prolog 重写他们的整个应用程序不感兴趣.在 Clojure 或 Python 中嵌入一种小型逻辑编程语言更具吸引力.据推测，嵌入式 Prolog 实现也可以用于此目的.我怀疑 miniKanren 作为一种嵌入式逻辑语言已经流行起来，因为它的核心实现很小且很纯，还有自The Reasoned Schemer"出版以来出现的演讲、博客文章、教程和其他教育材料.

The presence of conda, condu, and project---and the ability to easily modify the search strategy---allows programmers to use miniKanren as an embedded Prolog-like language. This is especially true for users of Clojure's 'core.logic', which includes many Prolog-like extensions. This "pragmatic" use of miniKanren seems to account for the majority of miniKanren's use in industry. Programmers who want to add a knowledge-based reasoning system to an existing application written in Clojure or Python or JavaScript are generally not interested in rewriting their entire application in Prolog. Embedding a small logic programming language in Clojure or Python is much more appealing. An embedded Prolog implementation would work just as well for this purpose, presumably. I suspect miniKanren has become popular as an embedded logic language because of the tiny and pure core implementation, along with the talks, blog posts, tutorials, and other educational materials that have come out since 'The Reasoned Schemer' was published.

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

In addition to the use of miniKanren as a pragmatic embedded logic programming language similar in spirit to Prolog, miniKanren is being used for research in "relational" programming. That is, in writing programs that behave as mathematical relations rather than mathematical functions. For example, in Scheme the append function can append two lists, returning a new list: the function call (append '(a b c) '(d e)) returns the list (a b c d e). We can, however, also treat append as a three-place relation rather than as a two-argument function. The call (appendo '(a b c) '(d e) Z) would then associate the logic variable Z with the list (a b c d e). Of course things get more interesting when we place logic variables in other positions. The call (appendo X '(d e) '(a b c d e)) associates X with (a b c), while the call (appendo X Y '(a b c d e)) associates X and Y with pairs of lists that, when appended, are equal to (a b c d e). For example X = (a b) and Y = (c d e) are one such pair of values. We can also write (appendo X Y Z), which will produce infinitely many triples of lists X, Y, and Z such that appending X to Y produces Z.

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

This relational version of append can be easily expressed in Prolog, and indeed is shown in many Prolog tutorials. In practice, more complex Prolog programs tend to use at least a few extra-logical features, such as cut, which inhibit the ability to treat the resulting program as a relation. In contrast, miniKanren is explicitly designed to support this style of relational programming. More recent versions of miniKanren have support for symbolic constraint solving (symbolo, numbero, absento, disequality constraints, nominal logic programming) to make it easier to write non-trivial programs as relations. In practice I never use any of the extra-logical features of miniKanren, and I write all of my miniKanren programs as relations. The most interesting relational programs are the relational interpreters for a subset of Scheme. These interpreters have many interesting abilities, such as generating a million Scheme programs that evaluate to the list (I love you), or trivially generating quines (programs that evaluate to themselves).

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

miniKanren makes a number of trade-offs to enable this relational style of programming, which are very different from the trade-offs Prolog makes. Over time miniKanren has added more symbolic constraints, really becoming a symbolically-oriented Constraint Logic Programming language. In many cases these symbolic constraints make it practical to avoid using extra-logical operators like condu and project. In other cases, these symbolic constraints are not sufficient. Better support for symbolic constraints is one active area of miniKanren research, along with the broader question of how to write larger and more complex programs as relations.

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

In short, both miniKanren and Prolog have interesting features, implementations, and uses, and I think it is worth learning the ideas from both languages. There are other very interesting logic programming languages as well, such as Mercury, Curry, and Gödel, each of which has its own take on logic programming.

我将以一些迷你看人资源结束:

I'll end with a few miniKanren resources:

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

The main miniKanren website: http://minikanren.org/

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

An interview I gave on relational programming and miniKanren, including a comparison with Prolog: http://www.infoq.com/interviews/byrd-relational-programming-minikanren

干杯，

--会

这篇关于Prolog 和 miniKanren 在逻辑编程方面的主要技术区别是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！