专家系统/Prolog

历史

Prolog 是一种逻辑编程语言。它是一种通用语言，通常与人工智能和计算语言学相关联。它具有一个纯粹的逻辑子集，称为“纯 Prolog”，以及许多非逻辑特性。

它由 Alain Colmerauer 和 Philippe Roussel 约于 1972 年创建，基于 Robert Kowalski 对 Horn 子句的程序解释。它部分受到希望将逻辑作为一种声明性知识表示语言的使用与 1960 年代后期和 1970 年代初在北美流行的知识程序表示方式相协调的愿望的驱动。

第五代计算机系统项目 (FGCS) 为其第一个操作系统开发了 Prolog 的一个变体，名为内核语言，促进了 Prolog 的许多现代发展。

纯 Prolog 最初仅限于使用具有以下形式的 Horn 子句的解析定理证明器

H :- B₁, …, B_n..

定理证明器的应用将此类子句视为过程

显示/解决H, 显示/解决B₁和 … 和B_n.

然而，纯 Prolog 很快得到扩展，包括否定为失败，其中形式为 not(B_i) 的否定条件通过尝试并失败来解决相应的正条件 B_i 来显示。

数据类型

Prolog 的单一数据类型是项。项要么是原子、数字、变量或复合项。

原子示例：x、blue、'Some atom' 和 []。

数字可以是浮点数或整数。许多 Prolog 实现还提供无界整数和有理数。

变量由一个字符串表示，该字符串包含字母、数字和下划线字符，并以大写字母或下划线开头。变量与逻辑中的变量非常相似，因为它们是任意项的占位符。变量可以通过统一进行实例化。单个下划线 (_) 表示匿名变量，表示“任何项”。

复合项具有一个函子和多个参数，这些参数又是项。参数的数量称为项的元数。（原子可以看作是元数为零的复合项的特例。）

项的示例为 f(a,b) 和 p(x,y,z)。某些运算符可以在中缀表示法中使用。例如，项 +(a,b) 和 =(X,Y) 也可以分别写成 a+b 和 X=Y。用户还可以将任意符号序列声明为新的中缀或后缀运算符，以允许特定于领域的表示法。表示法f/n 通常用于表示具有函子f 和元数n 的项。

复合项的特例

• 列表是通过归纳法定义的：原子 [] 是一个列表。具有函子 . (点) 和元数 2 的复合项，其第二个参数是列表，它本身也是一个列表。存在用于表示列表的特殊语法：.(A, B) 等效于 [A|B]。例如，列表 .(1, .(2, .(3, []))) 也可以写成 [1,2,3]。
• 字符串：用引号括起来的字符序列等效于 (数字) 字符代码的列表，通常以本地字符编码或 Unicode 表示（如果系统支持 Unicode）。

Prolog 编程

Prolog 程序描述关系，通过子句来定义。纯 Prolog 限于 Horn 子句，这是谓词逻辑的一个图灵完备子集。子句有两种类型：事实和规则。规则的形式为

Head :- Body.

读作“如果主体为真，则头部为真”。规则的主体包含对谓词的调用，这些谓词称为规则的目标。内置谓词 ,/2 表示目标的合取，而 ;/2 表示析取。合取和析取只能出现在主体中，而不能出现在规则的头部。没有主体的子句称为事实。事实的示例如下

cat(tom).

等效于规则

cat(tom) :- true.

内置谓词 true/0 始终为真。

根据以上事实，可以询问

tom 是猫吗？

?- cat(tom).  
Yes

什么东西是猫？

?- cat(X).  
X = tom

由于许多内置谓词的关联性质，它们通常可以用于多个方向。例如，length/2 可以用来确定列表的长度（length(List, L)，给定一个列表List）以及生成给定长度的列表骨架（length(X, 5)），还可以生成列表骨架及其长度（length(X, L)）。类似地，append/3 可以用来附加两个列表（append(ListA, ListB, X)给定列表ListA和ListB）以及将给定列表拆分为多个部分（append(X, Y, List)，给定一个列表List）。出于这个原因，相对较小的库谓词集足以满足许多 Prolog 程序的需要。所有谓词也可以用来执行单元测试：查询可以嵌入到程序中，并允许自动编译时回归测试。

作为一种通用语言，Prolog 还提供了各种内置谓词来执行常规活动，例如输入/输出、使用图形以及以其他方式与操作系统通信。这些谓词没有赋予关联含义，仅对它们对系统的副作用有用。例如，谓词write/1在屏幕上显示一个项。

评估

Prolog 程序的执行由用户发布的单个目标（称为查询）启动。在逻辑上，Prolog 引擎尝试找到否定查询的解析反驳。Prolog 使用的解析方法称为 SLD 解析。如果否定查询可以被反驳，则查询（在适当的变量绑定到位的情况下）是程序的逻辑结果。在这种情况下，所有生成的变量绑定都将报告给用户，并且查询被认为已成功。在操作上，Prolog 的执行策略可以被认为是其他语言中函数调用的概括，不同之处在于多个子句头可以匹配给定的调用。在这种情况下，系统创建一个选择点，将目标与第一个备选方案的子句头统一，并继续执行该第一个备选方案的目标。如果在执行程序的过程中任何目标失败，则自创建最近的选择点以来进行的所有变量绑定都会被撤消，并且执行将继续执行该选择点的下一个备选方案。这种执行策略称为按时间顺序回溯。例如

sibling(X, Y)      :- parent_child(Z, X), parent_child(Z, Y).

parent_child(X, Y) :- father_child(X, Y).
parent_child(X, Y) :- mother_child(X, Y).

mother_child(trude, sally).

father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).

这导致以下查询被评估为真

?- sibling(sally, erica).
Yes

这是这样得到的：最初，查询 sibling(sally, erica) 唯一匹配的子句头是第一个子句头，因此证明查询等效于证明该子句的主体（在适当的变量绑定到位的情况下），即合取 (parent_child(Z,sally), parent_child(Z,erica))。要证明的下一个目标是此合取的最左边的目标，即 parent_child(Z, sally)。有两个子句头匹配此目标。系统创建一个选择点，并尝试第一个备选方案，其主体是 father_child(Z, sally)。此目标可以使用事实 father_child(tom, sally) 来证明，因此生成了绑定 Z = tom，要证明的下一个目标是上述合取的第二部分：parent_child(tom, erica)。同样，这可以通过相应的事实来证明。由于所有目标都可以被证明，因此查询成功。由于查询不包含任何变量，因此不会向用户报告任何绑定。包含变量的查询，例如

?- father_child(Father, Child).

在回溯上枚举所有有效答案。

注意，在上面给出的代码中，查询 sibling(sally, sally) 也成功了（X = Y）。如果需要，可以插入额外的目标来描述相关的限制。

循环和递归

迭代算法可以通过递归谓词来实现。Prolog 系统通常实现一种称为尾调用优化 (TCO) 的著名优化技术，用于展示尾递归或更普遍地尾调用的确定性谓词：在尾部位置执行调用之前，会丢弃子句的堆栈帧。因此，确定性的尾递归谓词以恒定的堆栈空间执行，就像其他语言中的循环一样。

否定

内置 Prolog 谓词 \+/1 提供否定为失败，这允许非单调推理。规则中的目标 "\+ illegal(X)"

legal(X) :- \+ illegal(X).

的评估如下：Prolog 尝试证明 illegal(X)。如果可以找到该目标的证明，则原始目标（即 \+ illegal(X)）失败。如果找不到证明，则原始目标成功。因此，\+/1 前缀运算符被称为“不可证明”运算符，因为查询 "?- \+ Goal" 在 Goal 不可证明时成功。如果其参数是接地，则这种否定是合理的。如果参数包含变量，则会失去合理性。特别是，查询 "?- legal(X)." 现在不能用于枚举所有合法的事物。

操作注意事项

在声明式阅读下，规则的顺序以及规则中目标的顺序无关紧要，因为逻辑析取和合取是可交换的。然而，在程序上，通常重要的是要考虑 Prolog 的执行策略，无论出于效率原因，还是由于非纯内置谓词的语义，其评估顺序很重要。

DCG 和解析

有一种称为确定性子句语法 (DCG) 的特殊表示法。通过 -->/2 而不是 :-/2 定义的规则由预处理器 (expand_term/2，一个类似于其他语言中的宏的功能) 根据一些简单的重写规则进行扩展，从而产生普通的 Prolog 子句。最值得注意的是，重写为谓词配备了两个额外的参数，这些参数可以用来隐式地将状态传递给周围，类似于其他语言中的单子。DCG 通常用于编写解析器或列表生成器，因为它们还提供了一个方便的接口来进行列表差异。

解析器示例

一个更大的示例将展示在解析中使用 Prolog 的潜力。

给定用 BNF 表达的句子

<sentence>    ::=  <stat_part>
<stat_part>   ::=  <statement> | <stat_part> <statement>
<statement>   ::=  <id> = <expression> ;
<expression>  ::=  <operand> | <expression> <operator> <operand>
<operand>     ::=  <id> | <digit>
<id>          ::=  a | b
<digit>       ::=  0..9
<operator>    ::=  + | - | *

这可以用 Prolog 中的 DCG 来编写，对应于具有一个标记前瞻的预测解析器

sentence(S)                --> statement(S0), sentence_r(S0, S).
sentence_r(S, S)           --> [].
sentence_r(S0, seq(S0, S)) --> statement(S1), sentence_r(S1, S).

statement(assign(Id,E)) --> id(Id), [=], expression(E), [;].

expression(E) --> term(T), expression_r(T, E).
expression_r(E, E)  --> [].
expression_r(E0, E) --> [+], term(T), expression_r(plus(E0,T), E).
expression_r(E0, E) --> [-], term(T), expression_r(minus(E0, T), E).

term(T)       --> factor(F), term_r(F, T).
term_r(T, T)  --> [].
term_r(T0, T) --> [*], factor(F), term_r(times(T0, F), T).

factor(id(ID))   --> id(ID).
factor(digit(D)) --> [D], { (number(D) ; var(D)), between(0, 9, D)}.

id(a) --> [a].
id(b) --> [b].

此代码定义了一个句子（以标记列表的形式给出）与其抽象语法树 (AST) 之间的关系。示例查询

?- phrase(sentence(AST), [a,=,1,+,3,*,b,;,b,=,0,;]).
AST = seq(assign(a, plus(digit(1), times(digit(3), id(b)))), assign(b, digit(0))) ;

AST 使用 Prolog 术语表示，可以用于应用优化、将这些表达式编译为机器代码，或者直接解释这些语句。正如谓词的关联性质所典型的那样，这些定义既可以用于解析和生成句子，也可以用于检查给定的树是否对应于给定的标记列表。使用迭代加深进行公平枚举，每个任意但固定的句子及其相应的 AST 最终都会被生成

?- length(Tokens, _), phrase(sentence(AST), Tokens).
 Tokens = [a, =, a, (;)], AST = assign(a, id(a)) ;
 Tokens = [a, =, b, (;)], AST = assign(a, id(b)) 
 etc.

高阶编程

由于可以在运行时构造和评估任意 Prolog 目标，因此很容易编写像 maplist/2 这样的高阶谓词，它将任意谓词应用于给定列表的每个成员，以及 sublist/3，它过滤满足给定谓词的元素，也允许柯里化。

为了将解从时间表示（回溯时的答案替换）转换为空间表示（术语），Prolog 具有各种所有解谓词，这些谓词将给定查询的所有答案替换收集到一个列表中。这可以用于列表推导。例如，完美数等于其真因子的总和

perfect(N) :-
    between(1, inf, N), U is N // 2,
    findall(D, (between(1,U,D), N mod D =:= 0), Ds),
    sumlist(Ds, N).

这可以用来枚举完美数，也可以用来检查一个数是否为完美数。

元解释器和反射

Prolog 是一种同像语言，并提供了许多用于反射的功能。它的隐式执行策略使编写简洁的元循环评估器（也称为元解释器）成为可能，用于纯 Prolog 代码。由于 Prolog 程序本身是 Prolog 术语的序列（:-/2 是一个中缀运算符），这些术语很容易使用内置机制（如 read/1）读取和检查，因此很容易编写自定义解释器，这些解释器为 Prolog 添加特定于域的功能。

实现技术

为了提高效率，Prolog 代码通常被编译为抽象机器代码，通常受基于寄存器的 Warren 抽象机 (WAM) 指令集的影响。一些实现采用抽象解释，在编译时推导出谓词的类型和模式信息，或者编译为真正的机器代码以获得高性能。为 Prolog 代码设计高效的实现技术是逻辑编程社区中一个活跃的研究领域，在一些实现中采用了各种其他执行技术。这些包括子句二元化和基于堆栈的虚拟机。

例子

下面是一些用 Prolog 编写的示例程序。

快速排序

快速排序排序算法，将一个列表与其排序后的版本相关联

partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :-
    (   X @< Pivot ->
        Smalls = [X|Rest],
        partition(Xs, Pivot, Rest, Bigs)
    ;   Bigs = [X|Rest],
        partition(Xs, Pivot, Smalls, Rest)
    ).

quicksort([])     --> [].
quicksort([X|Xs]) --> 
    { partition(Xs, X, Smaller, Bigger) },
    quicksort(Smaller), [X], quicksort(Bigger).

图灵机

可以通过使用 Prolog 模拟图灵机来证明 Prolog 的图灵完备性

turing(Tape0, Tape) :-
    perform(q0, [], Ls, Tape0, Rs),
    reverse(Ls, Ls1),
    append(Ls1, Rs, Tape).

perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    once(rule(Q0, Sym, Q1, NewSym, Action)),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).

symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).

action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).

left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).

一个简单的示例图灵机由以下事实指定

rule(q0, 1, q0, 1, right).
rule(q0, b, qf, 1, stay).

此机器执行以一元编码表示的数字加一：它循环遍历任何数量的“1”单元格，并在末尾附加一个额外的“1”。示例查询和结果

?- turing([1,1,1], Ts).
Ts = [1, 1, 1, 1] ;

此示例说明如何将任何计算声明性地表示为一系列状态转换，在 Prolog 中实现为感兴趣的连续状态之间的关系。作为另一个示例，具有三个优化步骤的优化编译器可以实现为初始程序与其优化形式之间的关系

program_optimized(Prog0, Prog) :-
    optimization_pass_1(Prog0, Prog1),
    optimization_pass_2(Prog1, Prog2),
    optimization_pass_3(Prog2, Prog).

或者等效地使用 DCG 表示法

program_optimized --> optimization_pass_1, optimization_pass_2, optimization_pass_3.

动态规划

以下 Prolog 程序使用动态规划以多项式时间找到两个列表的最长公共子序列。子句数据库用于记忆

:- dynamic stored/1.

memo(Goal) :- ( stored(Goal) -> true ; Goal, assertz(stored(Goal)) ).

lcs([], _, []) :- !.
lcs(_, [], []) :- !.
lcs([X|Xs], [X|Ys], [X|Ls]) :- !, memo(lcs(Xs, Ys, Ls)).
lcs([X|Xs], [Y|Ys], Ls) :-
    memo(lcs([X|Xs], Ys, Ls1)), memo(lcs(Xs, [Y|Ys], Ls2)),
    length(Ls1, L1), length(Ls2, L2),
    (   L1 >= L2 -> Ls = Ls1 ; Ls = Ls2 ).

示例查询

?- lcs([x,m,j,y,a,u,z], [m,z,j,a,w,x,u], Ls).
Ls = [m, j, a, u]

一些 Prolog 系统，如 BProlog 和 XSB，实现了一种称为表化的扩展，这使用户无需手动存储中间结果。

扩展

• 约束逻辑编程对于许多 Prolog 在工业环境中的应用至关重要，例如时间表和其他的调度任务。大多数 Prolog 系统至少附带一个有限域的约束求解器，通常还附带其他域的求解器，例如有理数。
• HiLog 和 λProlog 为 Prolog 扩展了高阶编程功能。
• F-logic 为 Prolog 扩展了用于知识表示的框架/对象。
• OW Prolog 是为了解决 Prolog 缺乏图形和界面而创建的。
• Logtalk 是一种开源面向对象扩展，用于 Prolog 编程语言。它将逻辑编程与面向对象和事件驱动编程相结合，与大多数 Prolog 编译器兼容。它支持原型和类。此外，它还通过基于类别的组合支持基于组件的编程。
• Prolog-MPI 是一个开源的 SWI-Prolog 扩展，用于通过消息传递接口进行分布式计算。

相关语言

• Visual Prolog，以前也称为PDC Prolog和Turbo Prolog。Visual Prolog 是 Prolog 的一种强类型面向对象方言，它与标准 Prolog 大不相同。作为 Turbo Prolog，它由 Borland 推出，但现在由最初开发它的丹麦公司 PDC（Prolog 开发中心）开发和销售。
• Datalog 实际上是 Prolog 的一个子集。它仅限于可以分层的语义关系，并且不允许复合项。与 Prolog 相反，Datalog 不是图灵完备的。
• 在某种程度上，Prolog 是 Planner 的一个子集，例如，参见 Kowalski 关于逻辑编程的早期历史。Planner 中的思想后来在科学社区隐喻中得到进一步发展。

也存在可以为 Prolog 和 Java 编程语言之间提供桥梁的框架

• InterProlog，一个在 Java 和 Prolog 之间的编程库桥梁，实现了两种语言之间双向谓词/方法调用。Java 对象可以映射到 Prolog 项，反之亦然。允许在 Java 中开发 GUI 和其他功能，同时将逻辑处理保留在 Prolog 层。支持 XSB、SWI-Prolog 和 YAP。
• Prova 提供与 Java 的原生语法集成、代理消息传递和反应规则。Prova 将自己定位为用于中间件的基于规则的脚本 (RBS) 系统。该语言在结合命令式编程和声明式编程方面开辟了新的领域。

参考资料

• Michael A. Covington，Donald Nute，Andre Vellino，《Prolog Programming in Depth》，1996 年，ISBN 0-13-138645-X。
• Michael A. Covington，《Natural Language Processing for Prolog Programmers》，1994 年，ISBN 0-13-629213-5。
• Leon Sterling 和 Ehud Shapiro，《The Art of Prolog: Advanced Programming Techniques》，1994 年，ISBN 0-262-19338-8。
• Ivan Bratko，《PROLOG Programming for Artificial Intelligence》，2000 年，ISBN 0-201-40375-7。
• Robert Kowalski，《The Early Years of Logic Programming》，CACM 1988 年 1 月。
• 《ISO/IEC 13211: Information technology — Programming languages — Prolog》。国际标准化组织，日内瓦。
• Alain Colmerauer 和 Philippe Roussel，《The birth of Prolog》，收录在《The second ACM SIGPLAN conference on History of programming languages》中，第 37-52 页，1992 年。
• Richard O'Keefe，《The Craft of Prolog》，ISBN 0-262-15039-5。
• Patrick Blackburn，Johan Bos，Kristina Striegnitz，《Learn Prolog Now!》，2006 年，ISBN 1-904987-17-6。

另请参见

• Prolog 中的 literate programming
• Prolog Tutorial 由 J.R.Fisher 撰写
• Visual Prolog 教程
• Visual Prolog Wiki
• 可运行的示例 由 Lloyd Allison 撰写
• Prolog Programming A First Course 由 Paul Brna 撰写
• Adventure in Prolog，由 Amzi! Inc. 撰写，在线书籍
• Prolog 编程在线指南 由 Roman Bartak 撰写
• Prolog 小册子，由 Faiz ul haque Zeya 撰写
• Learn Prolog Now! 由 Patrick Blackburn，Johan Bos 和 Kristina Striegnitz 撰写
• Prolog and Logic Programming 由 Peter Hancox 博士撰写
• Strawberry Prolog 帮助，在线帮助
• Building Expert Systems in Prolog，由 Amzi! Inc. 撰写，在线书籍
• comp.lang.prolog FAQ
• Prolog：ISO 标准
• Prolog 开发中心