在逻辑编程方面，Prolog和miniKanren之间的主要技术区别是什么? [英] What are the main technical differences between Prolog and miniKanren, with respect to logic programming?
问题描述
当我想学习逻辑编程时，时下我总是会遇到两种主要"方法:
- miniKanren ，推理的计划者中引入的一种迷你语言.并由于 core.logic 而流行.
- Prolog ，第一种大"逻辑编程语言.
我现在感兴趣的是:两者之间的主要技术区别是什么?它们在方法和实现上是否非常相似，还是对逻辑编程采用完全不同的方法?它们来自哪些数学分支，其理论基础是什么?
首先，请允许我赞美您的pw0n1e图标.
这是一个棘手的问题，主要是因为miniKanren和Prolog的变体太多. miniKanren和Prolog实际上是语言家族，这使得很难比较它们的功能，甚至很难比较它们在实践中的用法.因此，请谨慎处理我要说的一切:如果我说Prolog使用深度优先搜索，请注意，许多Prolog实现都支持其他搜索策略，并且其他搜索策略也可以在meta处进行编码. -解释器级别.不过，miniKanren和Prolog具有不同的设计理念，并会做出不同的取舍.
Prolog是用于符号人工智能编程的两种经典语言之一(另一种经典语言是Lisp). Prolog擅长实现基于符号规则的系统，在该系统中，声明性知识以一阶逻辑编码.该语言针对这些类型的应用程序的表达性和效率进行了优化，有时会牺牲逻辑上的纯正性.例如，默认情况下，Prolog不统一使用出现检查".从数学/逻辑的角度来看，此版本的统一是不正确的.但是，发生检查很昂贵，并且在大多数情况下，缺少发生检查不是问题.这是一个非常务实的设计决策，Prolog使用深度优先搜索以及使用cut(!)来控制回溯也是一个非常务实的设计决策.我确信这些决定在1970年代的硬件上运行时绝对必要，而今天在处理大问题以及处理巨大(通常是无限的！)搜索空间时非常有用.
Prolog支持许多额外逻辑"或非逻辑"功能，包括剪切，assert和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具有漂亮的基于统一的模式匹配"样式的语法，该语法导致程序非常简洁.序言者喜欢他们的语法，就像利珀斯喜欢他们的s表达式一样. Prolog还具有大量的标准谓词库.由于使WAM快速运行的所有工程技术，因此有非常强大且成熟的Prolog实施.结果，许多大型的基于知识的系统已完全用Prolog编写.
miniKanren被设计为一种最小的逻辑编程语言，具有一个小型，易于理解和易于破解的实现. miniKanren最初嵌入在Scheme中，并且在过去十年中已移植到其他数十种宿主语言中. miniKanren最流行的实现是Clojure中的'core.logic'，它现在具有许多类似Prolog的扩展和许多优化.最近，miniKanren实现的核心得到了进一步简化，从而产生了一个名为"microKanren"的微型微内核".然后，可以在此microKanren核心之上实现miniKanren.将microKanren或miniKanren移植到新的宿主语言已成为学习miniKanren的程序员的标准练习.结果，大多数流行的高级语言至少具有一种miniKanren或microKanren实现.
miniKanren和microKanren的标准实现不包含任何突变或其他副作用，只有一个例外:miniKanren的某些版本使用指针相等来比较逻辑变量.我认为这是良性效果"，尽管许多实现甚至通过在实现中传递计数器来避免这种效果.也没有全局事实数据库. miniKanren的实现哲学受到函数式编程的启发:应避免突变和影响，所有语言构造应遵循词汇范围.如果仔细看一下实现，您甚至可能会发现几个monad.搜索实现是基于再次组合和处理惰性流，而又无需使用突变.这些实现选择导致的权衡与Prolog不同.在Prolog中，变量查找是固定时间，但是回溯需要消除副作用.在miniKanren中，变量查找更为昂贵，但回溯是免费的".实际上，由于如何处理流，miniKanren中没有回溯.
miniKanren实现的一个有趣的方面是，该代码本质上是线程安全的，并且-至少从理论上讲-几乎是可并行化的.当然，考虑到每个线程或进程必须有足够的工作来弥补并行化的开销，并行化代码而不使其变得 slower 并非易事.尽管如此，这还是miniKanren实施的一个领域，我希望它将得到更多的关注和实验.
miniKanren使用出现检查进行统一，并使用完整的交织搜索而不是深度优先搜索.交错搜索比深度优先搜索使用更多的内存，但是在深度优先搜索将永远发散/循环的某些情况下，可以找到答案. miniKanren 确实支持一些额外的逻辑运算符，例如conda，condu和project. conda和condu可用于模拟Prolog的切割，project可用于获取与逻辑变量关联的值.
conda，condu和project的存在-以及轻松修改搜索策略的能力-允许程序员使用miniKanren作为类似于Prolog的嵌入式语言.对于Clojure'core.logic'的用户而言尤其如此，其中包括许多类似于Prolog的扩展. miniKanren的实用"用法似乎占miniKanren在工业中的大多数使用.希望将基于知识的推理系统添加到用Clojure或Python或JavaScript编写的现有应用程序中的程序员通常对用Prolog重写其整个应用程序不感兴趣.在Clojure或Python中嵌入一种小型逻辑编程语言更具吸引力.大概，为此目的，嵌入式Prolog实现也将很好地工作.我怀疑miniKanren由于其微小而纯净的内核实现以及自《推理的策划人》发布以来的演讲，博客文章，教程和其他教育材料而成为一种流行的嵌入式逻辑语言.
除了将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))将X和Y与列表对关联，这些列表对在添加时等于(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子集的关系解释器.这些解释器具有许多有趣的功能，例如生成一百万个对列表(I love you)求值的Scheme程序，或平凡地生成quines(对自己求值的程序).
miniKanren为实现这种关系式编程进行了很多折衷，这与Prolog所做的折衷非常不同.随着时间的流逝，miniKanren增加了更多的符号约束，实际上成为了一种面向符号的约束逻辑编程语言.在许多情况下，使用这些符号约束可以避免使用诸如condu和project之类的逻辑运算符.在其他情况下，这些符号约束是不够的.更好地支持符号约束是miniKanren研究的一个活跃领域，也是一个更广泛的问题，即如何编写更大和更复杂的程序作为关系.
我将以miniKanren资源结尾:
miniKanren主要网站: http://minikanren.org/
我对关系编程和miniKanren进行了一次采访，其中包括与Prolog的比较: http://www.infoq.com/interviews/byrd-relational-programming-minikanren
干杯
-将
When I want to read up on logic programming I always stumble over two "main" ways to do it nowadays:
- 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?
First, allow me to compliment you on your fine pw0n1e icon.
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 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 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.
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 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 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.
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.
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 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.
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.
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.
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 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.
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:
The main miniKanren website: http://minikanren.org/
An interview I gave on relational programming and miniKanren, including a comparison with Prolog: http://www.infoq.com/interviews/byrd-relational-programming-minikanren
Cheers,
--Will
这篇关于在逻辑编程方面，Prolog和miniKanren之间的主要技术区别是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
