陈颂光
全栈工程师,承接从编译器到网站的各类软件开发与咨询,也可以聊历史哲学。
关注我的 GitHub

Prolog概览

Prolog作为一种逻辑型编程语言,对于大多数程序员而言大概是最异类的语言。Prolog被奉“写做什么而非怎么做”的所谓的第四代语言(声明式语言)而曾获寄予厚望,Prolog曾与Lisp并列为两大人工智能语言,有美Lisp欧Prolog的说法。虽然人工智能在上世纪八十年代后淡出加上Prolog自身的硬伤而随之失色。今天,Prolog的影响还远不如Lisp,不仅未能像Lisp在其它领域杀出血路,而且除SQL(和Erlang一点点)外对其它语言影响甚微。然而,Prolog在某些试验性场合仍有其方便之处,而且了解Prolog对开阔眼界大有好处。

Prolog程序由数据库和查询组成。数据库由事实(被认为真的命题)和规则(从真命题导出其它真命题的方法,不过事实也可看作前提为永真式的规则)组成。查询则是一个句子,Prolog实现将尝试找出它为真的条件。

使用Prolog

Prolog实现 特点
SWI-Prolog 工具和库较丰富
GNU Prolog 附有限域约束求解器
YAP 以性能为卖点

另外,可以在浏览器上试用Prolog

为统一起见,以下主要介绍命令行下用法,IDE或编辑器插件的用法应该更明显。如欲交互式地用Prolog:

  1. 只用运行已安装Prolog实现的解释器,例如用命令gprologyap(可用选项见文档),然后就处于查询模式(提示符为?-)。
  2. 现在可以输入一个查询后回车。输入文件结束符(Ctrl-D)会导致退出。
  3. 系统进行查询。如果长时间没响应,可以按中断它(Ctrl-C),然后会给出处理方式供选择。 - 如果成功则输出已实例化变量的值(没有则yes)。
    • 如果出现提示,可输入;(重复第3步以寻找其它实例化)或回车(回到第2步)。
    • 回到第2步。
      • 否则输出no,回到第2步。

以下例子演示了各情况:

   ?- 1==1 .
yes
   ?- 1==2 .
no
   ?- [X,y,Z]=[z,Y,z].
X = Z = z,
Y = y
   ?- X=y;X=z.
X = y ? ;
X = z
   ?- X=y;X=z.
X = y ? 
yes

为了导入数据库,在查询模式中输入[文件名].(从文件读入prolog源)或[user].(从标准输入,录入结束后输入文件结束符(Ctrl-D)返回查询模式)。

UNIX系统中也可以用脚本方式使用Prolog。

词法

空白

空白包括空格、制表符、回车、换行等,还有注释,可作为分隔符,分词后便被忽略。其中注释分为两类:

  • %到所在行结束
  • /**/,中间不含*/

简单项

常量

原子

原子可表示为

  • 由字母、数字、下划线组成,以小写字母开始
  • 由# $ & * + - . / : < = > ? @ ^ ~ \中一个或多个组成的序列(除了/*
  • ;[]{}
  • 由单引号包围的字符序列,其中可用转义序列
转义序列 意义
'' 单引号
\换行 相当于没有
\a 铃响
\b 退格
\f 进纸
\n 换行
\r 回车
\t 制表符
\v 垂直制表符
\xhh\ 十六制表示为hh的字符(可以有多个h)
\ooo\ 八进制表示为ooo的字符(可以有多个o)
\\ 反斜杠
\' 单引号
\" 双引号
\` 反引号
数值

整数的表示:

形式 意义
十进制数
0o… 八进制数
0x… 十六进制数
0b… 二进制数
0’c 字符c的值,其中c为单引号引用中容许的字符或转义序列

浮点数的表示为至少一个十进制数字、可选的小数点、至少一个十进制数字、可选的E(可接符号+-)、至少一个十进制数字。

数值前可加-使之取负值。

变量

由字母、数字、下划线组成,以大写字母或下划线开始,其中_表示匿名变量(可以认为是能匹配但不会实例化)。严格地说,每个匿名变量对应不同的变量,两个非匿名变量对应相同变量当且仅当它们同名。

复合项

复合项由称为函子的原子、(、由,分隔的若干项、)组成。

其中,.(首项,余下项组成的列表)用于表示非空列表([]表示空列表)。为方便见,用[项0,...,项n|余项].(项0,...,.(项n,余项))的语法糖,用[项0,...,项n].(项0,...,.(项n,[]))的语法糖。用"字符序列"表示作为各字符对应数值组成的列表。

另外,表达式项1 运算符 项2运算符(项1,项2)的语法糖,可用运算符如下:

优先级 类型 运算符
1200 xfx :- –>
1200 fx :- ?-
1100 xfy ;
1050 xfy ->
1000 xfy ,
700 xfx = = == == @< @=< @> @>= is =:= == < =< > >= =..
500 yfx + - /\ \/
400 yfx * / // rem mod « »
200 xfx **
200 xfy ^
200 fy \ -
100 xfx @
50 xfx :

其中,xfx表示二元不结合、yfx表示二元左结合、xfy表示二元右结合、fx表示一元不结合、fy表示一元可结合。

相应地,Prolog的类型只有原子、整数、浮点数、变量和复合项(它们互不相交)。

语法

Prolog程序由一系列子句和导言组成。

子句

每个子句定义用户定义过程的一个子句。

规则

每个规则是以:-为函子的复合项,通常写成形如:

结论:-前提.

其中结论和前提为项。对应用户定义过程的名称和元数同结论的函子和参数个数。(原子的元数为0,名称为它自己)

事实

事实就是前提恒真的规则。每个事实可直接表示为一个项(除了以:-为函子的复合项),以句号.结束。事实.相当于

事实:-true.

导言

导言用于改变prolog的行为。

导言 用途
dynamic(Pred/Arity). 容许在运行期修改用户定义过程(可重复,首个应出现在过程的首个子句前)
multifile(Pred/Arity). 容许用户定义过程有来自不同文件的子句(可重复,在每个来源文件都要有这导言且各文件指定的dynamic属性同)
discontiguous(Pred/Arity). 容许文件中用户定义过程的子句间夹杂其它用户定义过程的子句(可重复,首个应出现在过程的首个子句前)
op(Priority,Associativity,Atom). 设置运算符的优先级和结合性。优先级为0意味失去运算符地位。
char_conversion(Char1,Char2). 把没被引用的Char1换成Char2。
initialization(Goal). 程序加载完就执行查询(可以有多个)。
include(File). 以读入文件的内容取代此导言。
ensure_loaded(File). 保证文件被加载过一次。

查询

每个查询(目标)表示为一个项。用于交互式Prolog的查询模式或initialization导言的参数。

如果你还是觉得有点虚,看看一个例子。过程append定义如下:

append([],X,X).
append([H|T],X,[H|Y]):-append(T,X,Y).

这基本上重复了列表拼接的定义(前一行说空列表与列表X拼接得X,后一行说),相当直观自然。虽然我们没做多少事,但以下看到过程append有多种用途(而这只是小试牛刀):

   ?- append([1,2],[3,4,5],X).%拼接
X = [1,2,3,4,5]
   ?- append([1,2],[3,4,5],[1,2,3,4,5]).%判断是否拼接
yes
   ?- append([1,2],[3,4,5],[1,2,3,4]).
no
   ?- append([1,2],X,[1,2,3,4,5]).%取后缀
X = [3,4,5]
   ?- append(X,[3,5],[1,2,3,4,5]).%取前缀
no
   ?- append(X,Y,[1,2,3]).%拆分列表
X = [],
Y = [1,2,3] ? ;
X = [1],
Y = [2,3] ? ;
X = [1,2],
Y = [3] ? ;
X = [1,2,3],
Y = [] ? ;
no

快速排序是另一个例子:

partition(X,[],L,U).
partition(X,[H|T],[H|L],U):-X>H,partition(X,T,L,U).
partition(X,[H|T],L,[H|U]):-X<=H,partition(X,T,L,U).
qsort([],[]).
qsort([H|T],Y):-partition(H,T,L,U),qsort(L,LL),qsort(U,UU),append(LL,[H|UU],Y).

过程

每个过程有由一个谓词标识,谓词由名称Perd和元数Arity决定,以下用Perd/Arity形式表示。

控制结构

名称 谓词 意义
true/0 总是成功
fail/0 总是失败
,/2 当且仅当所有参数作为子目标都成功时才成功
;/2 当且仅当某个参数作为子目标都成功时才成功
蕴涵 ->/2 ,类似,但后一子目标失败后不重试前一子目标
剪枝 !/0 成功,但以后不让回溯到它之前
抛出 throw/1 抛出其参数,然后回退到可处理它最近的catch(没有则发生错误)
捕获 catch/3 类似于call首个参数,但有抛出时,抛出项与次参数可合一的话call末参数
调用 call/1 当且仅当其参数作为子目标成功时才成功

一个特殊情况是,’;’(‘->’(If,Then),Else)成功当且仅当If与Then同为成功或If失败但Else成功。

控制结构和内置谓词也可能通过抛出错误项应对错误,包括:

错误项 说明
instantiation_error 不该是变量的地方仍是变量
type_error(ValidType,Culprit) Culprit被期望为ValidType(atom、body、callable、character、compound、constant、integer、list、number、variable之一)
domain_error(ValidDomain,Culprit) Culprit被期望为ValidDomain(character_code_list、character_list、close_option、flag_value、io_mode、not_less_than_zero、operator_priority、operator_specifier、prolog_flag、read_option、source_sink、stream_or_alias、stream_option、stream_position、write_option之一)
existence_error(ObjectType,Culprit) Culprit被期望为存在的ObjectType(operator、past_end_of_stream、procedue、static_procedure、source_sink、stream之一)
permission_error(Operation,ObjectType,Culprit) 对ObjectType的Culprit的操作Operator(access_clause、create、input、modify、open、output、reposition之一)被拒
representation_error(Flag) 超出实现的限制Flag(character、character_code、exceeded_max_arity、flag之一)
calculation_error(Error) 计算错误Error(overflow、underflow、zero_divide、undefined之一)
resource_error(Resource) 因资源Resource不足无法继续执行
syntax_error 语法错误
system_error 下面依赖于实现

由于过于繁杂,具体错误条件请参阅文档。

在控制结构中剪枝最不好把握,禁止回溯本身就不像声明而像命令,它可用于提高效率或改变语义,以下给一些例子:

%否定的一种粗糙的实现
my_not(G):-call(G),!,fail.
my_not(G).
%绝对值的一种实现(其实X<0可省去,这样写是为举出一个!不改变语义的例子)
my_abs(X,X):-X>=0,!.
my_abs(X,Y):-X<0,Y is -X.

内置谓词

为方便叙述,我们用以下标记指出参数的特点:

模式 意义
+ 参数应已实例化
? 参数应已实例化或为变量
@ 参数应不被过程改动
- 参数应为变量且在过程成功时实例化

项的处理

项的合一

谓词 意义
'='(?term,?term) Prolog合一
'\='(?term,?term) Prolog不可合一
unify_with_occurs_check(?term,?term) 最一般合一

类型测试

谓词 意义
var(@term) 变量
atom(@term) 原子
integer(@term) 整数
real(@term) 浮点数
atomic(@term) 原子、整数或浮点数
compound(@term) 复合项
nonvar(@term) 非变量
number(@term) 整数或浮点数

项的比较

谓词 意义
'=='(@term,@term) 项恒等
'\=='(@term,@term) 项不恒等
'@<'(@term,@term) 项小于
'@=<'(@term,@term) 项不大于
'@>'(@term,@term) 项大于
'@>='(@term,@term) 项不小于

在项的比较中,先比较类型,从小到大为:

类型 类型内比较规则
变量 取决于实现
浮点数 数值比较
整数 数值比较
原子 字典序
复合项 依次比较参数个数、函子、各参数(递归)

项的创建和分解

谓词 意义
functor(Term-nonvar,Name+constant,Arity+integer) 创建项
functor(Term@nonvar,Name?constant,Arity?integer) 提取函子和元数
arg(N+integer,Term+compound_term,Arg?term) 提取参数
'=..'(Term+nonvar,List?list) 项转换为列表
'=..'(Term-nonvar,List+list) 列表转换为项
copy_term(?term,?term) 重命名后合一

算术

谓词 意义
is(Result?term,Expression+nonvar) 求值
'=:='(E1+nonvar,E2+nonvar) 数值相等(有一个浮点数则另一个亦转换为浮点数)
'=\='(E1+nonvar,E2+nonvar) 数值不相等(有一个浮点数则另一个亦转换为浮点数)
'<'(E1+nonvar,E2+nonvar) 数值小于(有一个浮点数则另一个亦转换为浮点数)
'=<'(E1+nonvar,E2+nonvar) 数值不小于(有一个浮点数则另一个亦转换为浮点数)
'>'(E1+nonvar,E2+nonvar) 数值大于(有一个浮点数则另一个亦转换为浮点数)
'>='(E1+nonvar,E2+nonvar) 数值不小于(有一个浮点数则另一个亦转换为浮点数)

其中,表达式中可用的运算符有:

运算符/元数 运算
'+'/2 数值加法,有参数为浮点数则结果为浮点数
'-'/2 数值减法,有参数为浮点数则结果为浮点数
'*'/2 数值乘法,有参数为浮点数则结果为浮点数
'//'/2 整数除法(向下取整还是向零取整取决于实现)
'/'/2 数值除法,有参数为浮点数则结果为浮点数
rem/2 整数求余
mod/2 整数求模
'-'/1 数值的相反数
abs/1 数值的绝对值
sqrt/1 数值的平方根
sign/1 数值的符号,非负为1,负为-1
float_truncate/2 浮点数的截断(后一参数为留下的有效二进制位数)
float_round/2 浮点数的舍入(后一参数为留下的有效二进制位数)
float_integer_part/1 浮点数的整数部分(向零取整)
float_fractional_part/1 浮点数的小数部分
float/1 把数值转换为浮点数
floor/1 把数值转换为整数,向下取整
truncate/1 把数值转换为整数,向零取整
round/1 把数值转换为整数,四舍五入
ceiling/1 把数值转换为整数,向上取整
'**'/2 数值的幂,结果为浮点数
sin/1 数值的正弦,结果为浮点数
cos/1 数值的余弦,结果为浮点数
atan/1 数值的反正切,结果为浮点数,在-π/2到π/2之间
exp/1 数值的指数,结果为浮点数
log/1 数值的自然对数,结果为浮点数
'>>'/2 整数的按位右移(算术还是逻辑取决于实现)
'<<'/2 整数的按左移
'/\\'/2 整数的按位与
'\\/'/2 整数的按位或
'\\'/1 整数的按位取反

子句

谓词 意义
clause(+head,?body) 获取体
current_predicate(?predicate_indicator) 获取谓词
asserta(@clauses) 增加首选子句
assertz(@clauses) 增加末选子句
retract(+clause) 删除子句
abolish(@predicate_indicator) 删除动态过程的所有子句

打包和控制

谓词 意义
findall(Term@term,Goal@callable_term,Bag?list) Bag与call(Goal),X=Term.各次成功时X的实例组成的列表合一
bagof(Template@term,Goal+callable_term,Instances?list) Instances与对应于Goal在一组自由变量取值下各次成功的Template的非空列表合一,Goal没成功过则失败,回溯时考虑下一组自由变量取值
setof(Template@term,Goal+callable_term,Instances?list) 与bagof类似,但去掉重复项
fail_if(@callable_term) 作为子目标调用其参数,当且仅当这子目标失败时成功。有的实现写作+。
once(+callable_term) 类似于call,但回溯时总失败(即子目标至多被调用一次)。
repeat 总是成功,用于实现循环的效果。如repeat,fail.是个死循环。

常数处理

谓词 意义
atom_length(+atom,?integer) 获取原子中字符数
atom_concat(?atom,?atom,+atom) 分裂原子
atom_concat(+atom,+atom,-atom) 拼接原子
sub_atom(+atom,?integer,?integer,?atom) 获取子原子及其位置与长度
atom_chars(+atom,+list) 获取组成原子的字符列表
atom_chars(+atom,-list) 获取组成原子的字符列表
atom_chars(-atom,+list) 由字符列表构造原子
atom_codes(+atom,+list) 获取组成原子的字符代码列表
atom_codes(+atom,-list) 获取组成原子的字符代码列表
atom_codes(-atom,+list) 由字符代码列表构造原子
char_code(+character,+character_code) 获取字符的代码
char_code(+character,-character_code) 获取字符的代码
char_code(-character,+character_code) 获取字符代码对应字符
number_chars(+number,+list) 获取组成数值表示的字符列表
number_chars(+number,-list) 获取组成数值表示的字符列表
number_chars(-number,+list) 由组成数值表示的字符列表解析数值
number_codes(+number,+list) 获取组成数值表示的字符代码列表
number_codes(+number,-list) 获取组成数值表示的字符代码列表
number_codes(-number,+list) 由组成数值表示的字符代码列表解析数值

系统相关

谓词 意义
halt 退出Prolog系统
halt(@integer) 退出Prolog系统并返回一个值给调用者
current_prolog_flag(?flag,?term) 获取Prolog系统的当前参数
set_prolog_flag(@flag,@term) 设置Prolog系统的参数
参数 可能值 默认值 可变性 用途
char_conversion on/off on + 非引用字符进行变换
debug on/off off + 不用按标准
max_arity 依赖于实现 依赖于实现 - 复合项的最大参数个数
undefined_predicate error/fail/warning error + 执行无定义子句的过程的后果
bounded true/false 依赖于实现 - 整数运算的结果范围是否有界,false的话没有下两项
max_integer 依赖于实现 依赖于实现 - 整数运算的结果范围的最大值
min_integer 依赖于实现 依赖于实现 - 整数运算的结果范围的最小值
integer_rounding_function down/toward_zero 依赖于实现 - 整数除法和求余的行为

I/O

由于较繁杂且不太体现Prolog特色,本文略,见文档。

应用举例

八皇后问题

八皇后问题是一个经典的约束求解问题,要求在8×8的国际象棋棋盘上放8个皇后使它们间都不能发生攻击。

position(0). position(1). position(2). position(3). position(4). position(5). position(6). position(7).
positions([]).
positions([H|T]):-position(H),positions(T).
board(X):-X=[R0,R1,R2,R3,R4,R5,R6,R7],positions(X).
not_in(X,[]).
not_in(X,[H|T]):-'=\\='(X,H),not_in(X,T).
distinct([]).
distinct([H|T]):-not_in(H,T),distinct(T).
diag_down([],[],I).
diag_down([X|Z],[Y|W],I):-Y is X-I,J is I+1,diag_down(Z,W,J).
diag_up([],[],I).
diag_up([X|Z],[Y|W],I):-Y is X+I,J is I+1,diag_up(Z,W,J).
acceptable(X):-board(X),distinct(X),diag_down(X,Y,0),distinct(Y),diag_up(X,Z,0),distinct(Z).

上面我们的acceptable过程只是描述了解应满足的条件,而且即使算上辅助过程的代码也相当简洁。这样结果就马上出来,而且很快可求出全部解:

   ?- acceptable(X).
X = [0,4,7,5,2,6,1,3] ?
   ?- findall(X,acceptable(X),L).
L = [[0,4,7,5,2,6,1,3],[0,5,7,2,6,3,1,4],[0,6,3,5,7,1,4,2],[0,6,4,7,1,3,5,2],[1,3,5,7,2,0,6,4],[1,4,6,0,2,7,5,3],[1,4,6,3,0,7,5,2],[1,5,0,6,3,7,2,4],[1,5,7,2,0,3,6,4],[1,6,2,5,7,4,0,3],[1,6,4,7,0,3,5,2],[1,7,5,0,2,4,6,3],[2,0,6,4,7,1,3,5],[2,4,1,7,0,6,3,5],[2,4,1,7,5,3,6,0],[2,4,6,0,3,1,7,5],[2,4,7,3,0,6,1,5],[2,5,1,4,7,0,6,3],[2,5,1,6,0,3,7,4],[2,5,1,6,4,0,7,3],[2,5,3,0,7,4,6,1],[2,5,3,1,7,4,6,0],[2,5,7,0,3,6,4,1],[2,5,7,0,4,6,1,3],[2,5,7,1,3,0,6,4],[2,6,1,7,4,0,3,5],[2,6,1,7,5,3,0,4],[2,7,3,6,0,5,1,4],[3,0,4,7,1,6,2,5],[3,0,4,7,5,2,6,1],[3,1,4,7,5,0,2,6],[3,1,6,2,5,7,0,4],[3,1,6,2,5,7,4,0],[3,1,6,4,0,7,5,2],[3,1,7,4,6,0,2,5],[3,1,7,5,0,2,4,6],[3,5,0,4,1,7,2,6],[3,5,7,1,6,0,2,4],[3,5,7,2,0,6,4,1],[3,6,0,7,4,1,5,2],[3,6,2,7,1,4,0,5],[3,6,4,1,5,0,2,7],[3,6,4,2,0,5,7,1],[3,7,0,2,5,1,6,4],[3,7,0,4,6,1,5,2],[3,7,4,2,0,6,1,5],[4,0,3,5,7,1,6,2],[4,0,7,3,1,6,2,5],[4,0,7,5,2,6,1,3],[4,1,3,5,7,2,0,6],[4,1,3,6,2,7,5,0],[4,1,5,0,6,3,7,2],[4,1,7,0,3,6,2,5],[4,2,0,5,7,1,3,6],[4,2,0,6,1,7,5,3],[4,2,7,3,6,0,5,1],[4,6,0,2,7,5,3,1],[4,6,0,3,1,7,5,2],[4,6,1,3,7,0,2,5],[4,6,1,5,2,0,3,7],[4,6,1,5,2,0,7,3],[4,6,3,0,2,7,5,1],[4,7,3,0,2,5,1,6],[4,7,3,0,6,1,5,2],[5,0,4,1,7,2,6,3],[5,1,6,0,2,4,7,3],[5,1,6,0,3,7,4,2],[5,2,0,6,4,7,1,3],[5,2,0,7,3,1,6,4],[5,2,0,7,4,1,3,6],[5,2,4,6,0,3,1,7],[5,2,4,7,0,3,1,6],[5,2,6,1,3,7,0,4],[5,2,6,1,7,4,0,3],[5,2,6,3,0,7,1,4],[5,3,0,4,7,1,6,2],[5,3,1,7,4,6,0,2],[5,3,6,0,2,4,1,7],[5,3,6,0,7,1,4,2],[5,7,1,3,0,6,4,2],[6,0,2,7,5,3,1,4],[6,1,3,0,7,4,2,5],[6,1,5,2,0,3,7,4],[6,2,0,5,7,4,1,3],[6,2,7,1,4,0,5,3],[6,3,1,4,7,0,2,5],[6,3,1,7,5,0,2,4],[6,4,2,0,5,7,1,3],[7,1,3,0,6,4,2,5],[7,1,4,2,0,6,3,5],[7,2,0,5,1,4,6,3],[7,3,0,2,5,1,6,4]]

数独是另一个类似问题,读者不妨一试。以下是一种解法(虽然性能很差):

candidate(1).
candidate(2).
candidate(3).
candidate(4).
candidate(5).
candidate(6).
candidate(7).
candidate(8).
candidate(9).
all_candidate([]).
all_candidate([H|T]):-candidate(H),all_candidate(T).
length([],0).
length([H|T],Y):-length(T,X),Y is X+1.
unit(X):-length(X,9),all_candidate(X).

all_unit([]).
all_unit([H|T]):-unit(H),all_unit(T).
board(X):-length(X,9),all_unit(X).

not_in(E,[]).
not_in(E,[H|T]):-E=\=H,not_in(E,T).
no_repeat([]).
no_repeat([H|T]):-not_in(H,T),no_repeat(T).
all_no_repeat([]).
all_no_repeat([H|T]):-no_repeat(H),all_no_repeat(T).

transpose([[C11,C12,C13,C14,C15,C16,C17,C18,C19],[C21,C22,C23,C24,C25,C26,C27,C28,C29],[C31,C32,C33,C34,C35,C36,C37,C38,C39],
	   [C41,C42,C43,C44,C45,C46,C47,C48,C49],[C51,C52,C53,C54,C55,C56,C57,C58,C59],[C61,C62,C63,C64,C65,C66,C67,C68,C69],
	   [C71,C72,C73,C74,C75,C76,C77,C78,C79],[C81,C82,C83,C84,C85,C86,C87,C88,C89],[C91,C92,C93,C94,C95,C96,C97,C98,C99]],
	  [[C11,C21,C31,C41,C51,C61,C71,C81,C91],[C12,C22,C32,C42,C52,C62,C72,C82,C92],[C13,C23,C33,C43,C53,C63,C73,C83,C93],
	   [C14,C24,C34,C44,C54,C64,C74,C84,C94],[C15,C25,C35,C45,C55,C65,C75,C85,C95],[C16,C26,C36,C46,C56,C66,C76,C86,C96],
	   [C17,C27,C37,C47,C57,C67,C77,C87,C97],[C18,C28,C38,C48,C58,C68,C78,C88,C98],[C19,C29,C39,C49,C59,C69,C79,C89,C99]]).

squares([[C11,C12,C13,C14,C15,C16,C17,C18,C19],[C21,C22,C23,C24,C25,C26,C27,C28,C29],[C31,C32,C33,C34,C35,C36,C37,C38,C39],
         [C41,C42,C43,C44,C45,C46,C47,C48,C49],[C51,C52,C53,C54,C55,C56,C57,C58,C59],[C61,C62,C63,C64,C65,C66,C67,C68,C69],
         [C71,C72,C73,C74,C75,C76,C77,C78,C79],[C81,C82,C83,C84,C85,C86,C87,C88,C89],[C91,C92,C93,C94,C95,C96,C97,C98,C99]],
	[[C11,C12,C13,C21,C22,C23,C31,C32,C33],[C14,C15,C16,C24,C25,C26,C34,C35,C36],[C17,C18,C19,C27,C28,C29,C37,C38,C39],
	 [C41,C42,C43,C51,C52,C53,C61,C62,C63],[C44,C45,C46,C54,C55,C56,C64,C65,C66],[C47,C48,C49,C57,C58,C59,C67,C68,C69],
	 [C71,C72,C73,C81,C82,C83,C91,C92,C93],[C74,C75,C76,C84,C85,C86,C94,C95,C96],[C77,C78,C79,C87,C88,C89,C97,C98,C99]]).

solve(X):-board(X),all_no_repeat(X),transpose(X,Y),all_no_repeat(Y),squares(X,Z),all_no_repeat(Z).

如:

   ?- solve([[6,5,9,7,8,4,2,3,1],[8,1,2,3,5,6,4,7,9],[4,3,7,1,9,2,6,8,5],[X,9,6,8,4,7,5,2,3],[2,7,4,5,3,9,8,1,6],[3,8,5,2,6,1,9,4,7],[5,2,3,9,7,8,1,6,4],[9,6,8,4,1,3,7,5,2],[7,4,1,6,2,5,3,9,Z]]).
X = 1,
Z = 8 ? 
yes

这些问题虽是游戏性质,但工程和规划中有很多实际的约束求解问题,同样可以用Prolog处理(编译器设计只是一例)。

语言处理

上下文无关语法在Prolog中可以直截了当地表示。下例中我们用Prolog解析基本的算术表达式语法并求值之。

evaluate_primitive([X],X):-number(X).
evaluate_primitive(['('|T],S):-append(E,[')'],T),evaluate(E,S).
evaluate_multiplicative(X,Y):-evaluate_primitive(X,Y).
evaluate_multiplicative(X,Y):-append(A,['*'|B],X),evaluate_primitive(A,AA),evaluate_primitive(B,BB),Y is AA*BB.
evaluate_multiplicative(X,Y):-append(A,['/'|B],X),evaluate_primitive(A,AA),evaluate_primitive(B,BB),Y is AA/BB.
evaluate_additive(X,Y):-evaluate_multiplicative(X,Y).
evaluate_additive(X,Y):-append(A,['+'|B],X),evaluate_multiplicative(A,AA),evaluate_multiplicative(B,BB),Y is AA+BB.
evaluate_additive(X,Y):-append(A,['-'|B],X),evaluate_multiplicative(A,AA),evaluate_multiplicative(B,BB),Y is AA-BB.
evaluate(X,Y):-evaluate_additive(X,Y).

这里有些重复劳动,这是因为我们并未用Prolog扩展部分中专门的谓词。现在看看效果:

   ?- evaluate([4],X).
X = 4 ? 
yes
   ?- evaluate([4,'+',8],X).
X = 12 ? 
yes
   ?- evaluate([4,'+',8,'*',3],X).
X = 28 ? 
yes
   ?- evaluate([4,'*','(',8,'+',3,')'],X).
X = 44 ? 
yes

同理,可用Prolog处理自然语言,实现机器翻译、问答系统……。

数据库

关系式数据库可以轻易地在Prolog表示,把每个表对应于一个谓词,每个行对应于一个事实即可。例如书表(含书名、作者、出版年)可能有这个样子:

book('Programming fortran','Mary',1999).
book('Cobol is back','Tom',2003).
book('Prolog in a nutshell','Sue',2016).

人表(含人名、国家)可能有这个样子:

person('Sue','US').
person('Mary','UK').
person('Tom','US').
person('Li','CN').

假如我们想找美国人写的书的书名和作者,可如下查询:

   ?- book(Name,Author,_),person(Author,'US').
Author = 'Tom',
Name = 'Cobol is back' ? ;
Author = 'Sue',
Name = 'Prolog in a nutshell'

大家想必看出这正是表的连接,它不比SQL更困难,可能更干净。关系式数据库的其它操作也可类似处理。

另外,其它数据库模型,从键值对、树状到一般的网状,在Prolog都可方便地表示。例如语义网就颇适合用Prolog处理。

局限性

既然包含算术的一阶谓词逻辑已经无疑是不可判定的,这就注定了Prolog的能力。Prolog虽叫逻辑型语言,但与通常的逻辑不尽一致(Prolog的一个更限制性的变种Datalog与逻辑更一致,但为了可终止性,在能力上甚至不是图灵完备)。

  • Prolog回答否的意思并不是说假,而是用当前数据库无法证明,可见Prolog的否定语义与逻辑中不同。只有在封闭世界假设(由于存在不可证明的真命题,它是错的)下两者才是一致的。特别地,双重否定后不完全与原来相同。例如,设过程animal只有子句animal(human).,则查询animal(X),X=cat.失败,而\+(\+animal(X)),X=cat.却成功并把X实例化为cat。
  • 可逆性是Prolog的一个与众不同的特性,例如用append谓词可以把两个表接起来,也可把一个表拆开。可惜在内置谓词中已经由于对效率的妥协没能坚守这一点,你不能用16 is X*Y.穷举16的因子分解。
  • 规则friend(X,Y):-friend(Y,X).在逻辑上完全合理(不过在说朋友是一种对称的关系),但在Prolog中它会导致查询不终止。同时,Prolog中规则的顺序也会影响可终止性和结果,这也与逻辑不一致。

由于我们给的线索不足,Prolog只能用很一般的方法求解,自然不能期望它运行得很快。Prolog执行查询基本上是在进行深度优先搜索,为了防止进入无希望的分支人们开始用剪枝这种过程型的做法,这又违背了逻辑型编程的初衷。

即使如此,Prolog的表达能力已经可以满足很多实际情况(非A则B往往不是真的需要作为结论),因此在小规模实验中相当有用(程序静态分析、定理证明、语言处理、语义网等)。顶多要进入产品时才用其它语言重写以保证性能就是了,毕竟现在机器比人便宜多了。

总结

Prolog的梦也是人工智能的梦,在梦中只用告诉机器要做什么而不用告之怎么做,然后机器自动地把事情做好。现实是残酷的,人们只能明知不可为而为之。也许,做什么和怎么做之间正是思维与存在的差别。