Hongzheng ChenBlog

Prolog入门

Feb 16th, 2019 0 #pl

本文内容整理自剑桥大学2011-12年David Evans开设的Prolog课程讲义。

Prolog(Programming in Logic)就是暴力美学的代表，一阶逻辑暴搜解决所有问题。

编程方式分类

  • 命令式(imperative)

    Formulate a “how to compute it” recipe

int sum(int[] list ) {
    int result = 0;
    for(int i=0; i<list.length; ++i) {
        result += list[i];
    }
    return result;
}
  • 函数式(functional)

    Again formulate a “how to compute it” recipe

(* The sum of the empty list is zero and
the sum of the list with head h and tail
t is h plus the sum of the tail. *)
fun sum([]) = 0
    | sum(h::t) = h + sum(t);
  • 逻辑式(logic) 
    % the sum of the empty list is zero
sum([],0).
% the sum of the list with head H and
% tail T is N if the sum of the list T
% is M and N is M + H
sum([H|T],N) :- sum(T,M), N is M+H.

也即陈述式(declarative)的方法

  • 不是怎么去计算结果
  • 而是关于结果正确的事实(this is true about the result)

简介

graph LR a["Questions"] -- "Prolog(Facts+Rules)" --> b["Answers"]

Prolog来源于NLP，现代的Prolog解释器都采用虚拟机

  • Colmerauer, A., Kanoui, H., Roussel, P. and Pasero, R., Un systeme de communication homme-machine en français”, Groupe de Recherche en Intelligence Artificielle, Université d’Aix-Marseille, 1973
  • David H. D. Warren, An abstract Prolog instruction set, Technical Note 309, SRI International, Menlo Park, CA, October 1983

Prolog特点

  • 符号运算
  • 递归、回溯
  • 推理与模式匹配
  • 没有特定运行顺序，没有控制语句
  • 人工智能领域常用，构建数据库

开源Prolog编译器SWI-Prolog

基本语法

事实、规则、目标，都用谓词表示

数据类型与声明

数据有三种类型

  • 常量：1，3.14，tigger
  • 变量：X，A_variable，_
  • 复合项(compound terms)：plus(4,mult(1,9))（前缀表示法）

写法为头部 :- 主体 .，:-即为if的意思

  • rule(X,Y) :- part1(X), part2(X,Y). rule为真，若part1和part2都为真
  • rule2(X) :- thing(X,Z), thang(Z). 存在Z使得thing和thang都为真

注意全称特称量词不显性表达出来

Prolog通过从句(clause)的名字和参数量(arity)来区分，如rule(rule/0)和rule(A)(rule/1)指代不同的东西

列表

  • 原生支持，可包含不同类型元素
  • 管道(pipe)符|用来代指列表的尾部，如?- [H|T]=[1,2,3,4].
    会得到H=1, T=[2,3,4].
  • 头尾函数
first([H|_],H).

last([H],H).
last([_|T],H) :- last(T,H).

len([],0).
len([_|T],N) :- len(T,M), N is M+1.

测试

Prolog里用=作为测试声明(test assertion)，不是赋值，而是验证两者如last([1,2,3],A), A=3.

?- A = 1+2.
A = 1+2.
?- 1+2 = 3.
false.

Prolog的核心只包含非常少的语义，算术操作和其他操作是同级别的，不会得到特别对待

is算子告诉Prolog

  • 数值(numerically)计算右侧的表达式
  • 与左侧验证(unify)表达式

搜索

Prolog采用深搜寻找答案

剪枝(cut)

example :- pre, !, post cut总是成功的，pre的部分随意回溯，但一旦通过!符号，回溯只能在post进行，而不能再回到!之前

p(X) :- a(X).
p(X) :- b(X), c(X), !, d(X), e(X).
p(X) :- f(X).
a(1). b(1). c(1). d(2). e(2). f(2).
      b(2). c(2).
  1. 统一(unify)p(X)为a(X)，实例化(instantiate)X=1满足
  2. 统一p(X)为b(X), c(X), !, d(X), e(X)（新的目标goal）
    • 实例化X=1，用事实b(1)统一b(X)
    • 目标变为c(1), !, d(1), e(1)
    • c(1)为事实，目标变为!, d(1), e(1)
    • !强制执行，前面的条件不能再改变
    • 然而不存在d(1)，因此fail
  3. 前面不能再改变，搜索终止

使用

  • swipl打开交互界面
  • [user].创建多行声明
  • 生成一个结果后，按;获取下一个
  • cat test.pl读文件
  • trace用来跟踪执行

参考资料

  • Ivan Bratko, Addison Wesley, PROLOG Programming for Artificial Intelligence (3rd or 4th ed)
    • Provides an alternative angle on the basics
    • Examines problem solving with Prolog in detail
    • Not all of the textbook is directly relevant
  • Leon Sterling and Ehud Shapiro, The Art of Prolog (2nd ed), MIT Press
    • Hard to get, but another angle
  • Richard O’Keeffe, The Craft of Prolog, MIT Press
    • Rather hard core
    • Beyond the scope of this course but quite neat
  • William F. Clocksin, Christopher S. Mellish, Programming in Prolog (5th ed), Springer

Related posts