Pro*_*sch 113 prolog logic-programming minikanren
当我想阅读逻辑编程时,我总是偶然发现两种"主要"方式来做到这一点:
我现在感兴趣的是:两者之间的主要技术差异是什么？它们在方法和实现方面是非常相似的,还是采用完全不同的逻辑编程方法？他们来自哪些数学分支,理论基础是什么？
Wil*_*yrd 265
首先,请允许我赞美你的精美pw0n1e图标.
这是一个棘手的问题,主要是因为miniKanren和Prolog都有很多变种.miniKanren和Prolog实际上是语言系列,这使得很难比较它们的功能,甚至在实践中如何使用它们.因此,请谨慎对待我要说的一切:如果我说Prolog使用深度优先搜索,请注意许多Prolog实现支持其他搜索策略,并且替代搜索策略也可以在元编码 - 解释水平.尽管如此,miniKanren和Prolog仍有不同的设计理念,并做出不同的权衡.
Prolog是符号人工智能编程的两种经典语言之一(另一种经典语言是Lisp).Prolog擅长实现基于符号规则的系统,其中声明性知识以一阶逻辑编码.该语言针对这些类型的应用程序的表现力和效率进行了优化,有时以牺牲逻辑纯度为代价.例如,默认情况下,Prolog不会在统一中使用"发生检查".从数学/逻辑的角度来看,这种统一版本是不正确的.然而,发生检查是昂贵的,并且在大多数情况下,缺少发生检查不是问题.这是一个非常务实的设计决策,Prolog使用深度优先搜索,并使用cut(!)来控制回溯.我敢肯定,当在20世纪70年代的硬件上运行时,这些决定是绝对必要的,今天在处理大问题时,以及处理大量(通常是无限的!)搜索空间时非常有用.
Prolog支持许多"超逻辑"或"非逻辑"特征,包括用于算术运算的变量的投影assert和retract投影,is等等.其中许多功能可以更轻松地表达复杂的控制流程,并操纵Prolog的全球事实数据库.Prolog的一个非常有趣的特性是Prolog代码本身存储在事实的全局数据库中,并且可以在运行时查询.这使得编写元解释器变得微不足道,这些元解释器在解释下修改Prolog代码的行为.例如,可以使用改变搜索顺序的元解释器在Prolog中编码广度优先搜索.这是一种非常强大的技术,在Prolog世界之外并不为人所知."Prolog的艺术"详细描述了这种技术.
为改进Prolog实现付出了巨大的努力,其中大部分是基于Warren Abstract Machine(WAM).WAM使用副作用模型,其中值被破坏性地分配给逻辑变量,这些副作用在回溯时被撤消.通过扩展WAM的指令,可以将许多功能添加到Prolog中.这种方法的一个缺点是,如果没有对WAM的充分理解,Prolog实施文件可能难以阅读.另一方面,Prolog实现者有一个讨论实现问题的通用模型.在Prolog的同时进行了大量的研究,最终在20世纪90年代的安道尔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和microKanren的标准实现不包含任何突变或其他副作用,只有一个例外:某些版本的miniKanren使用指针相等来比较逻辑变量.我认为这是一种"良性效应",尽管许多实现通过将计数器传递给实现来避免这种影响.还没有全球事实数据库.miniKanren的实现理念受到函数式编程的启发:应避免使用变异和效果,并且所有语言结构都应该遵循词法范围.如果你仔细看看实现,你甚至可能会看到几个monad.搜索实现基于组合和操纵惰性流,再次不使用突变.这些实施选择导致了与Prolog相比的非常不同的权衡.在Prolog中,变量查找是恒定时间,但回溯需要撤消副作用.在miniKanren变量查找更昂贵,但回溯是"免费的".事实上,由于流的处理方式,miniKanren没有回溯.
miniKanren实现的一个有趣的方面是代码本质上是线程安全的 - 至少在理论上 - 可以简单地并行化.当然,并行化代码而不使其变慢并不是微不足道的,因为必须为每个线程或进程提供足够的工作来弥补并行化的开销.不过,这是miniKanren实施的一个领域,我希望能得到更多的关注和实验.
miniKanren使用发生检查进行统一,并使用完整的交错搜索而不是深度优先搜索.交叉搜索比深度优先搜索使用更多内存,但在某些情况下可以找到答案,其中深度优先搜索将永远发散/循环.miniKanren 不支持一些额外的逻辑操作符- conda,condu以及project,例如. conda并且condu可用于模拟Prolog的剪切,project并可用于获取与逻辑变量关联的值.
的存在conda,condu以及project---和轻松修改搜索策略的能力---允许程序员使用miniKanren作为嵌入式序幕象语言.对于Clojure的'core.logic'用户来说尤其如此,其中包括许多类似Prolog的扩展.miniKanren的这种"实用"用法似乎占miniKanren在工业中的大部分用途.想要将基于知识的推理系统添加到用Clojure或Python或JavaScript编写的现有应用程序的程序员通常不会对在Prolog中重写其整个应用程序感兴趣.在Clojure或Python中嵌入一个小的逻辑编程语言更具吸引力.据推测,嵌入式Prolog实现也可以用于此目的.我怀疑miniKanren作为一种嵌入式逻辑语言已经变得流行,因为它的核心实现微小而且纯粹,以及自"The Reasoned Schemer"发布以来出现的会谈,博客文章,教程和其他教育材料.
除了使用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,disequality约束,标称逻辑编程),使其更易于编写不平凡的方案,作为关系.在实践中,我从不使用miniKanren的任何超逻辑功能,我将所有的miniKanren程序都写成关系.最有趣的关系程序是Scheme子集的关系解释器.这些解释器具有许多有趣的能力,例如生成一百万个计划程序,这些程序可以评估列表(I love you),或者平凡地生成quines(计算自己的程序).
miniKanren进行了一些权衡,以实现这种关系式编程,这与Prolog所做的权衡非常不同.随着时间的推移,miniKanren增加了更多的符号约束,真正成为一种面向符号的约束逻辑编程语言.在许多情况下,这些符号约束使得避免使用类似condu和的超逻辑运算符变得切实可行project.在其他情况下,这些符号约束是不够的.更好地支持符号约束是miniKanren研究的一个活跃领域,以及如何将更大和更复杂的程序作为关系编写的更广泛的问题.
简而言之,miniKanren和Prolog都有有趣的功能,实现和用途,我认为值得学习两种语言的想法.还有其他非常有趣的逻辑编程语言,例如Mercury,Curry和Gödel,每种语言都有自己的逻辑编程.
我将以一些miniKanren资源结束:
主要的miniKanren网站:http://minikanren.org/
关于关系编程和miniKanren的访谈,包括与Prolog的比较:http: //www.infoq.com/interviews/byrd-relational-programming-minikanren
干杯,
- 将
暂定答案:
AFAIK,"The Reasoned Schemer"以Scheme-y语法和函数编程风格引入了基本逻辑编程,特别是将常量目标"#u"(失败)和"#s"(suceeed)添加到布尔值"#t" "和"#f".它使用与Prolog:统一和回溯搜索相同的逻辑编程方法.我会看看周末是否有时间从书架上取回那本书.数学分支是限制形式的一阶逻辑,在这种情况下是Horn条款,以及Resolution Unfication.请参阅:计算逻辑:过去的记忆和未来的挑战 John Alan Robinson和Robert Kowalski 早期的逻辑编程冷启动.