极客时间已完结课程限时免费阅读

39 | 编程范式游记（10）- 逻辑编程范式

39 | 编程范式游记（10）- 逻辑编程范式-极客时间

39 | 编程范式游记（10）- 逻辑编程范式

2018-02-13 陈皓 来自北京
《左耳听风》
课程介绍

讲述：杨超

时长04:35大小4.19M

你好，我是陈皓，网名左耳朵耗子。
这节课重点介绍 Prolog 语言。Prolog（Programming in Logic）是一种逻辑编程语言，它创建在逻辑学的理论基础之上，最初被运用于自然语言等研究领域。现在它已被广泛地应用在人工智能的研究中，可以用来建造专家系统、自然语言理解、智能知识库等。
Prolog 语言最早由艾克斯马赛大学（Aix-Marseille University）的 Alain Colmerauer 与 Philippe Roussel 等人于 20 世纪 60 年代末研究开发的。1972 年被公认为是 Prolog 语言正式诞生的年份，自 1972 年以后，分支出多种 Prolog 的方言。
最主要的两种方言为 Edinburgh 和 Aix-Marseille。最早的 Prolog 解释器由 Roussel 建造，而第一个 Prolog 编译器则是 David Warren 编写的。
Prolog 一直在北美和欧洲被广泛使用。日本政府曾经为了建造智能计算机而用 Prolog 来开发 ICOT 第五代计算机系统。在早期的机器智能研究领域，Prolog 曾经是主要的开发工具。
20 世纪 80 年代 Borland 开发的 Turbo Prolog，进一步普及了 Prolog 的使用。1995 年确定了 ISO Prolog 标准。
有别于一般的函数式语言，Prolog 的程序是基于谓词逻辑的理论。最基本的写法是定立对象与对象之间的关系，之后可以用询问目标的方式来查询各种对象之间的关系。系统会自动进行匹配及回溯，找出所询问的答案。
Prolog 代码中以大写字母开头的元素是变量，字符串、数字或以小写字母开头的元素是常量，下划线（_）被称为匿名变量。

Prolog 的语言特征

逻辑编程是靠推理，比如下面的示例：
program mortal(X) :- philosopher(X).
philosopher(Socrates).
philosopher(Plato).
philosopher(Aristotle).
mortal_report:-
write('Known mortals are:'), nl, mortal(X),
write(X),nl,
fail.
我们可以看到下面的几个步骤。
先定义一个规则：哲学家是人类。
然后陈述事实：苏格拉底、亚里士多德、柏拉图都是哲学家。
然后，我们问，谁是人类？于是就会输出苏格拉底、亚里士多德、柏拉图。
下面是逻辑编程范式的几个特征。
逻辑编程的要点是将正规的逻辑风格带入计算机程序设计之中。
逻辑编程建立了描述一个问题里的世界的逻辑模型。
逻辑编程的目标是对它的模型建立新的陈述。
通过陈述事实——因果关系。
程序自动推导出相关的逻辑。

经典问题：地图着色问题

我们再来看一个经典的四色地图问题。任何一个地图，相邻区域不能用相同颜色，只要用四种不同的颜色就够了。
首先，定义四种颜色。
color(red).
color(green).
color(blue).
color(yellow).
然后，定义一个规则：相邻的两个地区不能用相同的颜色。
neighbor(StateAColor, StateBColor) :- color(StateAColor), color(StateBColor),
StateAColor \= StateBColor. /* \= is the not equal operator */
最前面的两个条件：color(StateAColor) 和 color(StateBColor) 表明了两个变量 StateAColor 和 StateBColor。然后，第三个条件： StateAColor \= StateBColor 表示颜色不能相同。
接下来的事就比较简单了。我们描述事实就好了，描述哪些区域是相邻的事实。
比如，下面描述了 BW 和 BY 是相邻的。
germany(BW, BY) :- neighbor(BW, BY).
下面则描述多个区 BW、 BY、 SL、 RP、 和 ND 的相邻关系：
germany(BW, BY, SL, RP, HE) :- neighbor(BW, BY), neighbor(BW, RP), neighbor(BW, HE).
于是，我们就可以描述整个德国地图的相邻关系了。
germany(SH, MV, HH, HB, NI, ST, BE, BB, SN, NW, HE, TH, RP, SL, BW, BY) :-
neighbor(SH, NI), neighbor(SH, HH), neighbor(SH, MV),
neighbor(HH, NI),
neighbor(MV, NI), neighbor(MV, BB),
neighbor(NI, HB), neighbor(NI, BB), neighbor(NI, ST), neighbor(NI, TH),
neighbor(NI, HE), neighbor(NI, NW),
neighbor(ST, BB), neighbor(ST, SN), neighbor(ST, TH),
neighbor(BB, BE), neighbor(BB, SN),
neighbor(NW, HE), neighbor(NW, RP),
neighbor(SN, TH), neighbor(SN, BY),
neighbor(RP, SL), neighbor(RP, HE), neighbor(RP, BW),
neighbor(HE, BW), neighbor(HE, TH), neighbor(HE, BY),
neighbor(TH, BY),
neighbor(BW, BY).
最后，我们使用如下语句，就可以让 Prolog 推导到各个地区的颜色。
?- germany(SH, MV, HH, HB, NI, ST, BE, BB, SN, NW, HE, TH, RP, SL, BW, BY).

小结

Prolog 这种逻辑编程，把业务逻辑或是说算法抽象成只关心规则、事实和问题的推导这样的标准方式，不需要关心程序控制，也不需要关心具体的实现算法。只需要给出可以用于推导的规则和相关的事实，问题就可以被通过逻辑推导来解决掉。是不是很有意思，也很好玩？
如果有兴趣，你可以学习一下，这里推荐两个学习资源：
Prolog Tutorial
Learn Prolog Now!
以下是《编程范式游记》系列文章的目录，方便你了解这一系列内容的全貌。
01 | 编程范式游记：起源
02 | 编程范式游记：泛型编程
03 | 编程范式游记：类型系统和泛型的本质
04 | 编程范式游记：函数式编程
05 | 编程范式游记：修饰器模式
06 | 编程范式游记：面向对象编程
07 | 编程范式游记：基于原型的编程范式
08 | 编程范式游记：Go 语言的委托模式
09 | 编程范式游记：编程的本质
10 | 编程范式游记：逻辑编程范式
11 | 编程范式游记：程序世界里的编程范式
分享给需要的人，Ta购买本课程，你将得29元
生成海报并分享

赞 18

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
38 | 编程范式游记（9）- 编程的本质
下一篇
40 | 编程范式游记（11）- 程序世界里的编程范式
unpreview
 写留言

精选留言(11)

  • neohope
    2018-06-19
    看《七周七语言》的时候，初步学习过Prolog，有个不错的入门英文教程：http://www.amzi.com/，上面的例子还蛮有意思的。说实话Prolog对我来说，不像是在编程，而更像是在做线性规划：根据限制和初始条件，找到解。十分感兴趣这个推导过程Prolog是如何实现的。耗哥这方面有推荐的读物吗？感谢：） 个人感觉，在这个推导过程中，其实比起些现在这些通过统计学、神经网络及大数据喂出来的怪兽，比如NLP、google翻译、人工智能什么的，感觉这个逻辑简单，更适合入门一些。
    展开
    25
  • minghu6
    2018-03-12
    prolog确实在解决一些需要频繁回溯的问题上相当好用，是真正的描述规则，然后自动求解的人性化语言。
    7
  • 一墨
    2020-06-06
    难得看到这么短小的皓哥:) 也猜到回复肯定不会多, 因为理解到和用到的人少嘛:) 在此贡献一点点,作为皓粉的投名状. 之前做过一个项目, 里面用到基于C/C++的iSAT库求解Boolean Satisfaction Problem. iSAT的使用方法也是 (1) 先描述一些限制条件, 如文中所说到陈述事实; (2) 调用iSAT库进行求解, 该库内部使用BDD算法得到一个不违反限制条件的解或者没有解, (3) 根据iSAT返回的计算结果判断回到 (1)修改限制条件继续执行, 或是找到满意的计算结果停止计算. 除本文提到的着色问题以外,这一类问题其实有很多(参考NP问题), 我将其归纳为具有明确限制的启发式问题, 其最明显的特征是有规范的数学定义, 变量X离散且取值范围有限. 由于是离散的, 所以不能保证有最优解, 只有近似最优解. 至于实际应用嘛, 和算法的应用类似, 只要能把某一类问题简化为这一类问题的数学格式, 就可以套用这一类问题的通用解法, 也即是可以使用逻辑编程的范式, 不需要过多关注内部实现
    展开
    5
  • 靠人品去赢
    2019-06-24
    你好，看完觉得Prolog这类语言，我只管业务，不管实现的。入门可能会简单，隐藏了许多技术细节，但实际上效率会不高，如果没有对应的活跃社区提供相关库的话。就害怕像“人人都是产品经理”，那样，弄了很多不知道技术边界的人导致各种各样的问题。
    4
  • Johnny
    2020-04-27
    看完这节课，突然想重新学一下离散数学里的数理逻辑部分了。
    3
  • edisonhuang
    2019-06-27
    逻辑编程很类似推理中的三段论，首先给出大前提，然后给出小前提，最后推导结论。 大前提哲学家都是人，小前提苏格拉底是哲学家，结论就是苏格拉底也是人 基于逻辑的编程让我们关注真正的事，忽略控制
    3
  • 钱
    2020-02-29
    还是这么好玩的语言，这是怎么玩到的？
    2
  • ZhengSJ
    2022-08-28 来自北京
    L. Suresh _et al._, “Building Scalable and Flexible Cluster Managers Using Declarative Programming,” 2020, pp. 827–844. Accessed: May 25, 2022. [Online]. Available: [https://www.usenix.org/conference/osdi20/presentation/suresh](https://www.usenix.org/conference/osdi20/presentation/suresh) 一篇文章，基于逻辑编程范式的调度系统设计，在思考这种方式是不是还可以应用到更多的领域。
    展开
  • limix
    2022-05-15
    这个很不错，之前看逻辑学，找到谓词逻辑的实用场景了，非常感谢
  • seedjyh
    2021-10-20
    这四色问题，prolog是打算用遍历穷举吗
  • 圆耳朵熊猫
    2020-09-30
    刷新认知了，居然还能这样玩