Prolog

定义

Prolog 是一种声明式程序设计语言，其名称来自「Programming in Logic」（逻辑中的编程）。程序由事实与规则两类子句组成，用关系的形式描述对象及其性质，而不是逐步给出计算步骤。^[4] 使用者只需声明已知条件并提出问题，求解过程由系统承担，因此它常被归入描述型或面向目标的语言。^[5] 它的理论基础是 一阶谓词逻辑，语法成分在逻辑上对应 Horn 子句，目标、规则与事实分别对应子句的不同部分。^[1]

原理

Prolog 程序的知识库是一组子句。事实是不带条件成立的原子公式，规则形如 $H \leftarrow B_1 \land B_2 \land \cdots \land B_n$，读作「若各 $B_i$ 均成立，则 $H$ 成立」；不含变量的原子公式构成最简单的查询。^[1] 运行时，使用者提交一个目标作为查询，系统尝试对该目标的否定做消解反驳，所用方法是 SLD 消解；若反驳成功，则说明查询在程序中有逻辑推论，并把相应的变量绑定报告给使用者。^[6]

程序求解的起点是建立事实与规则，然后把待解问题交给推理机制；子目标激活规则，规则体又产生新的子目标，如此逐层展开，直到子目标与事实匹配或推理失败。^[1]

Prolog 的执行策略可以理解成函数调用的推广：同一目标可能匹配多条子句的首部，系统为此建立选择点，先试第一个分支，若后续目标失败就撤销选择点之后的变量绑定、改试下一个分支，这种策略称为按时间顺序的回溯。^[6] 其操作上的核心机制包括匹配、递归定义、自动回溯与控制回溯。^[5] 由于程序本身不含 if、for 这类流程语句，运行顺序由推理机制而非编写者决定；需要控制搜索时，语言也提供与常规语言差别较大的流程控制手段。^[1]

graph TD

A[提交查询目标] --> B{与事实或规则首部匹配}

B -- 匹配成功 --> C[产生变量绑定]

B -- 失败 --> D[回溯到最近选择点]

C --> E{规则体是否全部证实}

E -- 是 --> F[输出答案]

E -- 否 --> D

D --> B

发展历程

Prolog 起源于 20 世纪 70 年代初法国马赛的一项自然语言处理项目，其目标并非设计通用编程语言，而是让机器对法语文本进行推演。1971 年前后，团队与爱丁堡的 罗伯特·科瓦尔斯基 接触，引入了 SLD 消解方法，为语言的实现奠定了理论与实用基础。^[7] 1972 年夏，阿兰·科尔默劳尔 及其团队在 马赛 开发并实现了该语言的第一个版本，菲利普·鲁塞尔(Philippe Roussel)参与了设计与实现。^[2][4]

此后，大卫·沃伦(David H. Warren)于 1977 年在爱丁堡大学完成了该语言的首个编译器，即 DEC-10 Prolog 系统；1983 年他又提出了影响深远的抽象机模型 WAM，成为多数实现参照的执行模型。 1979 年，日本在第五代计算机研究计划中把 Prolog 列为核心语言，推动了该语言在西欧与日本的应用推广。^[1] 1986 年，美国 Prolog 开发中心推出 Turbo Prolog，由 Borland 公司发行，主要面向 IBM PC 系列及兼容微机。^[5]

国际标准化组织与国际电工委员会于 1995 年 6 月发布 ISO/IEC 13211-1，规定 Prolog 文本表示、语法约束、语义规则与输入输出表示，目的是提高程序在不同系统间的可移植性；2000 年又发布了关于模块的第 2 部分。^[3] 2022 年前后，相关学术团体组织了纪念 Prolog 诞生 50 周年的活动，并出版了回顾其发展与应用的文集。^[8]

应用

Prolog 适合表达人类的思维与推理规则，一出现就引起人工智能研究与开发者的关注，在西欧和日本被用于关系数据库、数理逻辑、抽象问题求解、自然语言理解与专家系统等领域。^[1] 在 IBM 的相关研究中，Prolog 也被视为一种基于逻辑的应用开发技术，用于构建应用程序。^[9]

作为通用语言，Prolog 还提供输入输出、图形使用与操作系统通信等内建谓词，这些谓词不具备关系意义，价值在于其对系统产生的副作用。^[6] 多个实现扩展出约束逻辑编程能力，可求解有限域、布尔与实数约束问题。^[10] 在语义网方向，Prolog 被用于教学与语义网应用，并可借助库处理 RDF、RDFS 等数据格式。^[10]

局限

Prolog 的实用实现包含若干非纯逻辑成分，例如缺乏 occurs 检查、否定不安全、cut 与 assert、retract 的随意使用，这使得不少实用程序难以给出清晰的说明性语义，验证、变换、优化与调试都受到限制。^[11] 其程序的可声明性也不如想象中强，谓词和子句的排列顺序对结果影响很大，编写者必须熟悉求值策略才能得到结果并保证效率。^[12]

回溯与非确定性作为默认行为带来实际代价：许多现实问题在大部分环节是确定性的，用 Prolog 高效表达往往要借助 cut 等非纯特性，而这些特性会破坏可逆性，并与约束求解配合不佳。^[12] 此外，算术等内建功能不具备关系性，无法「反向」运行，容易因参数未充分实例化而报错；搜索策略僵硬也使程序发散较为常见。^[13] 由于目标和规则左部被限定为原子公式的合取，加上推理控制机制本身较简单，该语言被认为难以适用于复杂应用领域。^[1]

参见

• 逻辑编程 —— Prolog 所属的编程范式，以逻辑语句描述问题并由系统求解。

• SLD 消解 —— Prolog 求解查询所依据的消解方法。

• Horn 子句 —— Prolog 程序事实与规则在逻辑上的基本形式。

• SWI-Prolog —— 1987 年起持续开发的开源 Prolog 实现，常用于教学。

• 第五代计算机 —— 日本将该语言列为核心语言的研究计划。

• 一阶谓词逻辑 —— Prolog 的理论基础。