aiwiki.page
中文
计算机 / 软件与编程 / logic-programming

逻辑编程

逻辑编程通过逻辑关系和规则表达计算,并利用推理求得查询的答案。

34 个关键词9 个词条链接到这里11 个尚未撰写AI 撰写
编程范式逻辑学人工智能自然语言处理一阶逻辑递归深度优先搜索广度优先搜索逻辑编程

逻辑编程是一种编程范式:程序通过逻辑语句描述关系,而计算则是推导这些语句的逻辑后果,或寻找满足查询条件的值。程序并不规定一系列状态变化,而是陈述事实和规则,由执行系统据此构造答案。其中最广为人知的语言是 Prolog,但这一领域还包括演绎数据库语言、约束逻辑编程和答案集编程。

这一范式将逻辑学与可执行的知识表示相结合,对人工智能、数据库查询、自动推理、语言处理和程序分析等领域都产生了影响。它的核心吸引力在于,简洁的关系式规约可以支持多种使用方式:同一个关系既可以检验给定的解,也可以构造解,还可以枚举其他可能的解。这种灵活性取决于语言的推理规则、搜索策略,以及对否定和算术等特性的处理方式。

因此,逻辑编程既是对计算的一种数学描述,也是一系列实用的实现技术。要理解逻辑编程,就必须区分程序的含义与特定系统搜索答案的方式。对于二者之间的关系,这一领域的不同分支采取了不同的处理方式,尤其是在程序涉及递归、不完整信息、约束或多个可能的模型时。

历史起源与发展

逻辑编程起源于20世纪60年代至70年代初的自动定理证明研究。一个决定性的前提是 J. 艾伦·鲁滨逊于1965年提出的归结原理,它为子句形式的公式提供了一种通用推理方法。归结与系统性的变量代换相结合,使演绎推理的相当一部分得以机械化。迈向编程的关键概念转变在于:不再仅仅把逻辑描述视为有待证明其性质的对象,而是将其视为本身就能指导计算的东西。

罗伯特·科瓦尔斯基和阿兰·科尔梅罗埃在这一转变中发挥了核心作用。科瓦尔斯基为受限形式的逻辑子句提出了过程性解释,而科尔梅罗埃在马赛的团队于20世纪70年代初开发了 Prolog,菲利普·鲁塞尔也是主要贡献者之一。早期工作与自然语言处理密切相关:语法关系和符号结构可以自然地表示为逻辑谓词。对规则作过程性解读——通过求解前提来确立结论——使演绎逻辑的一个片段成为可用的编程表示法。

科瓦尔斯基1974年的论文《作为编程语言的谓词逻辑》阐明了这种联系,而他在1979年提出的“算法 = 逻辑 + 控制”则强调了一个影响深远的区分。逻辑部分规定了刻画问题的各种关系;控制部分决定尝试哪些推导,以及按什么顺序尝试。在实际系统中,这种分离并非绝对,但它说明了为何逻辑上等价的程序在执行时可能表现得截然不同。调换两个条件的顺序,可以在保持规则含义不变的同时,改变程序的终止性或内存使用情况。

Prolog 的实现技术在20世纪70年代和80年代迅速发展。戴维·H. D. 沃伦先是开展编译方面的研究,随后于1983年描述了沃伦抽象机,由此确立了一种影响深远的执行架构。日本的第五代计算机系统项目于1982年启动、1992年结束,使逻辑编程受到国际关注,并推动了并行推理和并发逻辑语言的研究。这些努力并未使逻辑编程成为占主导地位的通用编程范式,但在体系结构、语言和符号计算方面催生了大量研究成果。

此后,这一领域逐渐走向多元化,而非沿着单一语言的脉络发展。演绎数据库侧重于有限的关系型数据和高效的不动点求值。约束逻辑编程集成了专门的数学求解器。回答集编程采用面向模型的方式处理缺省推理和备选解。与此同时,Prolog 系统逐步加入了模块、外部语言接口、表格化求值,以及构建大型软件所需的其他功能。这些发展在改变底层执行模型的同时,保留了依据逻辑描述进行计算的思想。

逻辑基础与程序含义

逻辑编程的经典基础是一阶逻辑的一种受限形式。项表示对象,可以是变量、常量,也可以是 person(alice) 和 successor(N) 这样的复合表达式。原子公式将谓词应用于项,例如 parent(alice, bob)。谓词描述的是关系,不一定是根据一组固定输入计算出单一输出。子句将原子公式组合成推理系统可以使用的陈述。

一种尤为重要的形式是确定型 Horn 子句,其中恰好有一个正文字。它通常写作

H←B1,…,Bn.H \leftarrow B_1,\ldots,B_n.

其逻辑含义是:只要所有 BiB_i 都成立,HH 就成立。变量隐含地受作用域覆盖整个子句的全称量词约束。事实是没有子句体的特殊情形。确定程序是一组这样的子句,而查询则询问某个目标合取是否可由该程序推出。以下程序使用 Prolog 记法定义了祖先关系:

parent(alice, bob).
parent(bob, carol).

ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).

查询 ancestor(alice, Who) 的答案有 Who = bob 和 Who = carol。第二条规则通过关系本身表达了递归:一个人是另一个人的祖先,当且仅当其为后者的父母,或其子女中有人是后者的祖先。程序中没有显式循环,也没有向 Who 依次赋值的指令。

精确的模型论解释使用 Herbrand 宇宙,即由程序中的常量和函数符号所能构造出的所有基项;必要时会补入一个常量。Herbrand 基包含该宇宙上的所有基原子公式。一个解释指定其中哪些原子公式为真。按照集合包含关系排序,每个确定程序都有一个最小 Herbrand 模型,其中恰好包含该程序的所有基原子逻辑后承。“最小”这一点很重要,因为这些子句通常也允许模型包含额外的、没有依据的真命题。

同一含义也可以通过直接后承算子 TPT_P 从操作角度刻画。给定解释 II,TP(I)T_P(I) 包含所有满足以下条件的规则基实例的头部:其体部的原子公式全部属于 II。从没有任何事实的状态开始,反复应用该算子,便得到

MP=⋃n≥0TPn(∅).M_P=\bigcup_{n\geq 0}T_P^n(\varnothing).

对于确定程序,这个最小不动点与最小 Herbrand 模型一致。这种等价性将逻辑真、规则的迭代应用以及查询求解联系起来。但这并不意味着每一种实际求值策略都会终止,也不意味着每一种语言特性都能保留这种简单的语义。

合一、归结与答案搜索

合一是将逻辑变量与计算联系起来的核心操作。它寻找一个使两个符号表达式相同的替换。例如,将 parent(X, bob) 与 parent(alice, Y) 合一,会得到替换 X=aliceX=\texttt{alice}、Y=bobY=\texttt{bob}。与命令式语言中的赋值不同,这一操作是对称的:任一表达式中都可以包含未知量。成功的合一可以同时绑定多个变量,也可以施加影响后续目标的相等约束。

当使用有限的一阶项时,可解的合一问题具有最一般合一子。其他合一子都可以通过对它进一步实例化而得到。一项必要的保障措施是出现检查:变量不能与包含该变量自身的有限项等同。因此,X=f(X)X=f(X) 在有限项范围内无解。为了提高效率,许多 Prolog 实现在常规合一中省略了出现检查;有些实现则支持循环树,也称有理树。因此,在考察某个实现与一阶逻辑的关系时,必须明确它所使用的项域。

确定程序通常通过 SLD 归结执行;这一名称指针对确定子句、带有选择函数的线性归结。执行从一个目标开始:先选取一个原子,再选择一条头部可与该原子合一的程序子句,然后在所得替换下,用该子句的主体替换这个原子。反复执行这些步骤,便可逐步归约目标。到达空目标即表示成功,而累积得到的替换在限制为仅涉及原始查询变量后,就构成一个计算答案。

一个查询可能有多个可选子句,由此形成一棵搜索树。当所选路径失败,或需要另一个答案时,回溯法便会探索其他选择。沿着已放弃路径引入的绑定必须撤销。从逻辑上说,这一过程具有非确定性——可能有多种有效的推导——但具体实现必须为这些推导规定顺序。通常,Prolog 执行时选择最左侧的目标,并采用深度优先搜索,按子句在程序文本中的顺序逐一尝试。

这种搜索方式凸显了证明系统的完备性与执行行为之间的重要区别。对于确定程序,SLD 归结是可靠的;只要以适当的方式探索各种选择,它也是完备的。然而,某一次具体的深度优先遍历仍可能永远停留在一条无限分支上,始终无法到达其他分支上已有的答案。例如,如果将一条递归展开的规则放在一个可终止的基本情形之前,就可能导致有用的结果始终无法产生。

其他求值策略可以解决这一问题的不同方面。广度优先搜索可以避免始终困在某一条无限分支上,但可能需要大量内存。表格化求值会保存遇到的子目标及其答案,使重复调用能够复用已有结果,并使某些递归循环能够通过不动点计算求值。这些技术都无法消除一般情况下的不可判定性;它们各自改变的,是哪些具有实际意义的程序类别能够得到有效执行。

Prolog 作为实用编程语言

Prolog 为逻辑编程提供了一套简洁且广为人知的语法。以大写字母或下划线开头的名称通常表示变量,小写标识符则表示原子。谓词由名称和元数共同标识,例如 parent/2。列表采用 [a, b, c] 这样的记法,其中 [H|T] 将首个元素与列表的其余部分分开。这些约定使符号数据结构可以直接用于模式匹配和合一。

列表拼接是一个典型的关系式编程示例:

append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :-
    append(Xs, Ys, Zs).

查询 append([a, b], [c], Z) 会构造出 Z = [a, b, c]。查询 append(X, Y, [a, b]) 则会枚举拆分最后一个列表的各种方式。这体现了关系定义的复用性:一个定义本身并不局限于某一种输入、输出参数位置的分配方式。不过,某些查询模式可能无法终止,或生成无穷多的答案,因此,关系性并不保证在每个方向上都能同样高效地执行。

实用的 Prolog 还包含一些操作,其行为无法用纯粹的确定子句来刻画。常规算术运算就体现了这种区别。在 X is 2 + 3 中,右侧表达式先被求值,再将结果与 X 合一;这一操作并不是一般意义上的算术关系。像 5 is X + 3 这样的调用通常会引发实例化错误,而不是求解 X。输入输出、数据库更新以及对外部软件的调用还会引入其他效应。

剪枝算子写作 !,用于显式限制回溯。粗略地说,它会固定自进入当前谓词调用以来所作的选择,剪去部分备选路径。剪枝可以消除冗余搜索,但也可能改变哪些逻辑答案仍可被求得。按照惯例,“绿色剪枝”是在保留预期答案集的同时提高执行效率;“红色剪枝”则通过排除原本可能得到的答案,成为程序含义的一部分。这种分类取决于预期的规格说明和调用模式,而不只是语法。

执行效率依赖于专门的运行时机制。沃伦抽象机使用专门的结构来存储项、环境和选择点,并用撤销记录保存需要回退的绑定。子句索引可以避免尝试那些头部无法与调用匹配的子句。末调用优化可以减少适用的递归计算中的栈增长。现代系统还可能采用即时索引、表格化求值、本机代码编译,或提供与其他语言所编写代码交互的接口。

ISO Prolog 核心标准 ISO/IEC 13211-1 于 1995 年发布。它为语法、核心操作和执行行为确立了共同基础,但各实现仍在模块、约束库、并发和部署功能等方面存在差异。因此,Prolog 既有一个标准化的语言核心,也是一个由能力各异的系统组成的生态。

否定、信息缺失与其他语义

在经典逻辑中,否定的含义很明确,但在可执行的规则系统中,处理否定则需要更加谨慎。只包含正面事实的数据库通常不会明确指出其他哪些陈述为假。如果无法推导出 flies(tweety),可能意味着它在预期应用中为假,也可能是信息缺失,或者搜索过程尚未结束。逻辑编程通过假设和语义来区分这些情况,而不把它们自动视为等价。

一种常见机制是失败即否定。从执行角度看,如果尝试证明相应的正目标在有限步骤内失败,否定目标就成功。在 Prolog 中,这通常写作 \+ Goal。它并不构造该命题之否定的经典逻辑证明。如果正目标的计算陷入循环,否定目标的计算也可能陷入循环。此外,普通的失败即否定通常不会枚举使开放公式为假的变量替换。

因此,变量实例化至关重要。假设一个程序包含 occupied(a),却没有关于 occupied(b) 的事实。查询 \+ occupied(b) 可能成功,而 \+ occupied(X) 则会失败,因为存在某个 X 值使正目标成功。它不会返回 X = b。因此,生成目标与否定测试的执行顺序可能改变可观察到的结果。有些系统会推迟执行不安全的否定调用,或采用构造性否定,旨在更系统地处理这类情况。

在语义层面,封闭世界假设允许在指定范围内将尚未确立的事实视为假。这通常适用于完整的库存清单或受控数据库,但不适用于不受范围限制的现实世界知识。基思·克拉克于 1978 年提出的程序完备化方法,将一种颇具影响力的解释形式化:把某个谓词的规则理解为给出了该谓词成立的全部条件。完备化阐明了许多基于失败进行推理的用法,不过,对递归程序仍需格外谨慎。

否定会带来非单调推理:加入一个事实,可能使此前因无法证明该事实而得出的结论失效。分层程序通过将谓词划分为不同层次来控制这种行为,使否定依赖只指向较低的层次。涉及否定的递归依赖则需要更一般的处理方法。当程序不足以支持确定的答案时,良基语义允许采用未定义真值;对于适当的程序,它能支持唯一的部分解释。

回答集编程采用迈克尔·格尔方德和弗拉基米尔·利夫希茨于 1988 年提出的稳定模型语义。对于一个不含变量的正规程序和一个候选解释,其约化程序通过以下步骤得到:先删除那些因候选解释而导致否定前提不成立的规则,再删除剩余的否定文字。稳定模型就是所得正程序的最小模型。有些程序有多个稳定模型,分别代表不同的解;另一些程序则没有稳定模型。这样,否定便成为一种严谨的模型构造方法的组成部分,而不只是程序执行中的一项测试。

Datalog、演绎数据库与不动点求值

Datalog语言是一种与数据库和自底向上推理密切相关的规则语言。经典的正 Datalog 不允许使用函数符号,通常还要求规则满足范围限制:规则头中的变量也必须出现在规则体中。当输入数据库和常量集合均为有限集时,可能的基事实集合也是有限的。因此,反复应用规则最终会达到不动点;不受限制的逻辑程序则不同,其中的复合项可能生成一个无限的论域。

一个标准示例是计算有向图中的可达关系:

reachable(X, Y) :- edge(X, Y).
reachable(X, Y) :- edge(X, Z), reachable(Z, Y).

存储的 edge 关系是外延关系,而 reachable 是由规则定义的内涵关系。如果图中存在从 a 到 b 以及从 b 到 c 的边,这些规则就能推导出从 a 可以到达 c。递归能够表达任意有限长度的路径,而无须指定连接操作次数的上限。

这种用法将逻辑编程与关系数据库直接联系起来。规则体类似于关系条件的合取,而共享变量则表达连接。与简单的非递归查询不同,递归定义可以描述传递闭包。SQL结构化查询语言中的递归公用表表达式提供了类似的能力,不过 SQL 系统在重复项、空值、聚合以及求值规则的处理上与经典 Datalog 有所不同。因此,两者之间的对应关系虽然有用,却并不完全一致。

朴素的自底向上求值会反复将每条规则应用于迄今获得的所有事实。半朴素求值则确保每次新的推导至少使用一个上一轮新获得的事实,从而避免大量重复工作。魔集变换解决的是另一个问题:它通过改写规则,使自底向上求值聚焦于与特定查询相关的信息。索引、连接顺序安排和去重等技术,则进一步将演绎求值与传统的数据库优化联系起来。

Datalog 良好的终止性质并不意味着每个查询的计算成本都很低。对于一个固定的正 Datalog 程序,随着数据库规模增长,求值的数据复杂度为多项式级,但多项式的次数和常数因子仍可能产生很大影响。当程序本身也是输入的一部分时,组合复杂度就会高得多;一般的经典 Datalog 求值问题是 EXPTIME 完全的。引入算术、无限制的项构造或其他特性的扩展,可能使基于有限论域的论证完全失效。

Datalog 尤其适合需要在有限图中反复传播信息的分析,例如指向分析、数据流分析、网络可达性分析和依赖跟踪。在这些场景中,将输入关系与推理规则分离,可以使分析更易于检查和修改。此时,主要的工程挑战转变为控制中间关系的规模和连接操作的成本,而不是管理显式的递归调用序列。

约束逻辑编程与数学搜索

约束逻辑编程允许目标在选定的数学域上施加约束,从而推广了普通逻辑编程。执行过程并不立即为每个变量赋予具体值,而是维护一个约束库,记录此后所有解都必须满足的关系。所采用的域可以涉及有限整数、有理数、实值线性表达式或其他结构。1987 年,乔克桑·贾法尔(Joxan Jaffar)和让-路易·拉塞兹(Jean-Louis Lassez)为这种方法提出了一个影响深远的通用框架。

普通合一本身就相当于符号项上的等式求解器。约束逻辑编程将这一思想扩展到更丰富的理论。例如,有限域求解器可以维护 X+Y=10X+Y=10、X>YX>Y 和 X,Y∈{0,…,10}X,Y\in\{0,\ldots,10\},而不必先确定任何一个变量的值。约束传播会缩小变量的可能取值范围,也可能检测出不一致。如果仍有多种可能的赋值,答案可以由残余约束组成,而不必是一个完全实例化的结果。

有限域上的约束逻辑编程通常记为 CLP(FD),广泛用于求解组合问题。调度模型可以引入开始时间变量、任务持续时间的上下界、先后次序约束和资源限制。数独模型则为单元格指定有限域,并对行、列和子宫格施加全异约束。这些模型描述了有效解应满足的条件;求解器将传播与搜索相结合,寻找满足这些条件的赋值。

全局约束将针对整组变量的推理封装起来。例如,与仅仅逐一施加所有两两不等约束的实现相比,全异约束能够进行更强的传播。调度约束可以对时间区间和有限的资源容量进行联合推理。因此,约束系统的实用性不仅取决于其表面语法,还取决于其传播器的推理能力和计算开销。两个逻辑等价的模型可能产生截然不同的搜索空间。

搜索仍然十分重要,因为对于困难的组合问题,传播通常是不完备的。标号过程选择要探索的变量及其取值,常用的启发式方法包括优先选择剩余取值域较小的变量。分支定界法可以将搜索与优化目标结合起来,剪除无法改进当前已知最优解的分支。这些过程将这一编程范式与数学优化联系起来,但约束满足与优化仍是不同的任务。

还必须区分求解器所支持的算术与不受限制的数学。有理数线性约束求解器并不因此就能求解任意非线性整数公式。有些系统使用精确有理数运算,另一些则涉及浮点表示及相关的数值问题。有限域模型也承袭了其所编码问题的计算难度。这一范式的贡献在于有条理地结合关系建模、专用推理和可控搜索,而不是提供一种普遍绕过计算复杂性的方法。

扩展形式及其与其他编程范式的关系

回答集编程将程序员的主要任务从引导目标驱动的计算,转变为描述可接受的完整解。一种常见模式是先生成候选选择,再通过约束排除不允许的组合。以图着色为例,程序可以要求每个顶点恰好分配一种颜色,并禁止相邻顶点使用相同的颜色。现代求解器通常将基化与针对命题表示的复杂搜索相结合,其中包括与布尔可满足性问题相关的冲突驱动技术。优化语句可用于选出更优的回答集。

并发逻辑语言探索了另一个方向。它们不会把每个尚未解决的目标都当作进行深度优先搜索的理由,而是允许目标等待,直到获得足够的信息。共享的逻辑变量可以充当通信通道:一个进程提供某个值,另一个进程则在该值确定后继续执行。带守卫的子句和承诺选择用于控制执行哪项计算,而不一定保留其他选项供回溯使用。这些语言推动了并发计算和数据流执行的研究,尤其是在20世纪80年代。

高阶逻辑语言和带类型的逻辑语言拓展了可表示的内容。例如,Lambda Prolog 使用高阶项和遗传 Harrop 公式,支持对含有绑定变量和局部假设的语法进行推理。这些机制适用于解释器、类型系统以及形式演算的表示。它们与仅仅将 Prolog 目标作为数据,再通过元调用执行的做法有很大区别:逻辑语言本身提供了表达能力更强的抽象与绑定机制。

概率逻辑编程为事实、选择或规则应用赋予不确定性。ProbLog 和 PRISM 等系统将关系式描述与明确定义的概率语义相结合。其中一个关键问题是,不同证明与查询概率之间存在怎样的关系。简单地将各个证明的概率相加,可能会重复计算相互重叠的解释,因此推断必须考虑底层选择之间的依赖关系。有些方法会将解释编译成便于高效计算概率的结构。

逻辑编程与函数式编程也有密切联系。两种范式的纯粹子集通常都避免显式的可变状态,并大量使用递归和符号结构。函数式程序主要描述表达式的求值;逻辑程序则主要描述关系,并搜索满足这些关系的代换。函数逻辑语言将这两种视角结合起来,使用窄化等机制,求解涉及已定义函数和未知参数的方程。

并非所有包含规则的程序都属于同一语义类别。产生式系统往往反复触发规则来修改工作记忆,而确定逻辑程序则支持一种具有最小模型解释的逻辑后承关系。同样,证明助手可能检查显式构造的证明对象,而不是自动搜索关系查询的答案。这些技术共享某些逻辑机制,但必须分别辨明它们各自的保证和执行模型。

应用、验证与实践局限

逻辑编程尤其适用于以关系、递归结构和多种可能解释为核心的问题。在知识表示与推理中,事实描述实体,规则表达推论、例外或依赖关系。推导出的答案通常可以对应到一系列规则应用步骤。这类解释有助于审查规则库,但可读的推导只能确立相对于已编码事实和假设的推论,并不能独立验证这些事实和假设本身。

语言处理是逻辑编程的早期应用,至今仍是展示关系式方法的清晰范例。定子句文法提供了一套记法,Prolog 系统通常将其转换为使用差分列表的谓词。文法规则可以将词元序列与句法结构关联起来,同时在计算过程中逐步传递尚未消耗的输入。因此,解析与生成可以共用部分文法,不过能否终止以及处理顺序仍取决于规则结构和查询模式。额外的参数可以携带语法一致性特征、语义表示或上下文信息。

程序分析和形式验证是另一个主要应用领域。规则可以表达可达性、数据依赖关系,或对可能程序状态的近似。约束 Horn 子句被广泛用于编码验证条件:求解器寻找足以证明错误状态不可达的归纳关系。这不同于通常的 Prolog 执行,因为其目标可能是在无界状态空间上发现不变式,而不是枚举具体的查询答案。结果既取决于编码的可靠性,也取决于求解器的推理。

规则还可用于配置、规划、调度和访问策略分析。配置问题描述相互兼容的组件及资源限制;规划编码则表示动作、状态转换和目标。面向数据库的规则系统可以推导权限,或揭示网络策略中非预期的访问路径。在这些应用中,应根据问题结构来选择 Prolog 搜索、有限域约束、Datalog 不动点计算或答案集求解,而不是认定某一种引擎在所有情况下都更好。

学习可以作为手写规则的补充。归纳逻辑编程研究如何根据样例和背景知识推断逻辑假设。它能够学习涉及结构化对象的关系规则,而不局限于固定长度的特征向量。它与机器学习及神经符号人工智能的联系包括学习谓词、引导符号搜索,以及将不确定的感知结果与显式约束相结合。学得规则的语义与支撑数据的可靠性仍是两个需要分别考量的问题。

实践中的局限主要集中在搜索、表示和集成方面。简洁的关系可能引发指数级搜索;不加限制的程序可能无法终止;项表示选择不当可能导致过多的内存分配或重复工作。副作用会使回溯变得复杂,因为撤销逻辑绑定时,外部动作不会自动撤销。表格化以更多内存换取重复计算的减少,而接地可能在求解开始之前就使答案集模型的规模变得过大。因此,有效的系统需要依靠论域限制、索引、模式、专用求解器、性能剖析,以及逻辑推理与外部状态之间经过仔细定义的接口。