Prolog中的图语法、表处理及约束规则聚合技术

### Prolog 中的图语法、表处理及约束规则聚合技术 #### 一、图语法在 Prolog 中的表示与执行 结构化图表（如 ER 图）由有限类型的符号按照明确规则相互连接而成。图语法是用于指定结构化图表语法的一种形式化方法，不同的图语法形式主要区别在于其图重写机制。目前，图语法在代数框架下已得到较好的理解，但将其与逻辑编程相结合的研究相对较少。 为了解决这个问题，有人提出了一种名为 Prolog 图语法（Graph Grammar in Prolog，GGP）的形式化方法。GGP 可以像 DCG 将上下文无关字符串语法嵌入 Prolog 一样嵌入到 Prolog 中，并且使用 Prolog 为 GGP 形式化方法提供可执行的语义。 1. **基本概念** - **边终端**：是形如 `edge(vertex(U,A), vertex(V,B))` 的 Prolog 项，表示两个具有 ID 分别为 U、V，标签分别为 A、B 的顶点之间存在有向边。顶点 ID 或标签可以是 Prolog 变量或常量。 - **非终端（N - 项）**：是形如 `name(L)` 的 Prolog 项，其中 `name` 是原子，`L` 是 Prolog 列表，通常只包含 Prolog 变量。 - **GGP 产生式**：形式为 `Head ==> Body`，其中 `Head` 是 N - 项，`Body` 是终端和 N - 项的序列（也可以包含常用的 Prolog 谓词）。 2. **示例：星型图的 GGP 产生式** 以下是定义星型图语法的 GGP 产生式，星型图的中心顶点标签为 `a`，其他顶点标签为 `b`，只使用了一个非终端 `star`。 ```prolog star([S0]) ==> edge(vertex(S0,a),vertex(S1,b)). star([S0]) ==> edge(vertex(S0,a),vertex(S1,b)), star([S0]). ``` 对这些 GGP 产生式的声明性解读如下： - 第一个产生式表示由两个顶点 `S0` 和 `S1`（分别标记为 `a` 和 `b`）以及从 `S0` 到 `S1` 的单条有向边组成的图是星型图。 - 第二个产生式表示如果一个图包含顶点 `S0` 和 `S1`（分别标记为 `a` 和 `b`）以及从 `S0` 到 `S1` 的有向边，并且删除这条边（不删除顶点）后得到的图仍然是星型图，那么该图是以 `S0` 为中心顶点且标记为 `a` 的星型图。 3. **GGP 解析过程** GGP 用于解析给定的图（表示为顶点和边的无序集合），并报告该集合是否符合 GGP 产生式指定的语法。在 GGP 推导的每一步，都会从给定的边集合中移除一条边，当所有边都被移除时，推导终止。在推导过程中，N - 项中的 Prolog 变量会被实例化。 上述 GGP 产生式会被翻译成以下 Prolog 代码： ```prolog star(A,B,[C],D,E) :- check_edge(A,B,vertex(C,a),vertex(F,b),D,E). star(A,B,[C],D,E) :- check_edge(A,B,vertex(C,a),vertex(F,b),G,H), star(G,H,[C],D,E). ``` 可以使用 Prolog 解释器来检查上述（翻译后的）GGP 是否能解析一个有向 5 顶点星型图，其中中心顶点 ID 为 1，标签为 `a`，其他顶点 ID 为 2、3、4、5，标签为 `b`。实际的顶点 ID 以及顶点和边在列表中的顺序并不重要。 ```prolog ?- star([v(1,a),v(2,b),v(3,b),v(4,b),v(5,b)], [e(1,2),e(1,3),e(1,4),e(1,5)], X,_,[]). X = [1] ``` 4. **简单图语法（SGG）** 还开发了一种名为简单图语法（Simple Graph Grammar，SGG）的形式化方法，它既可以看作是一种字符串语法（具有字符串重写机制），也可以看作是一种图语法（具有图重写机制）。GGP 是 SGG 在 Prolog 中的嵌入，可以使用 GGP 来定义各种结构化图表（如 ER 图、消息序列图和状态图）的语法，并且正在研究将 GGP 用作图转换和图数据库查询机制。 #### 二、在 Prolog 中应用程序转换实现基于挂起的表处理 表处理是一种解决传统 Prolog 系统在处理冗余子计算和递归时局限性的技术。表处理机制主要分为两类：基于挂起的表处理机制和线性表处理机制。 1. **两种表处理机制对比** - **基于挂起的表处理机制**：需要保存挂起的表式子目标的状态，以确保正确计算所有答案。表式评估可以看作是一系列子计算，这些子计算会挂起并在后续恢复。 - **线性表处理机制**：使用表式子目标的迭代计算来计算不动点，其主要思想是维护一个单一的执行树，表式子目标总是扩展当前计算，不需要子计算的挂起和恢复。 2. **实现方法** 常见的将表处理支持集成到现有 Prolog 系统的方法是修改和扩展底层引擎，但这种方法虽然运行时效率高，但不易移植到其他 Prolog 系统。另一种方法是对表式程序应用源级转换，转换后的程序使用外部表处理原语来实现表式评估。 有人提出了一种基于程序转换的基于挂起的表处理机制，使用大多数 Prolog 系统都可用的 C 语言接口来实现表处理原语。具体来说，使用 Yap Prolog 系统的 C 接口构建外部 Prolog 模块来支持表式评估，实现中可以区分两个主要模块： - **实现特定控制原语的模块** - **实现表空间数据结构的模块** 表空间使用字典树（tries）实现，为了实现该机制（命名为带延续调用的表式评估），采用了局部调度策略。挂起通过在对应于被挂起的变体调用的表项中留下当前计算的延续调用来实现。在这个过程中，当找到新的答案时，它们会被存储在各自的表中，并通过调用之前存储的延续调用返回给所有变体调用。为了实现程序转换步骤，扩展了 Ramesh 和 Chen 最初的程序转换模块，以包含该方法的表处理原语。 3. **性能评估** 将该机制与最先进的 YapTab 系统进行了比较，YapTab 在底层引擎实现了表处理支持，也采用了基于挂起的机制，使用字典树实现表空间，并且基于 Yap 实现。实验结果表明，YapTab 在所有测试程序中都优于该机制，平均而言，YapTab 比延续调用机制快约 7.50 倍。对于左递归表式谓词且递归子句在前的情况，性能最佳，平均开销在 2 到 3 之间。结果还表明，执行时间的成本与评估过程中执行的冗余答案、变体调用和延续调用的数量成正比，其中延续调用的数量似乎是导致成本的最相关因素，因为延续调用未被编译，而是在运行时使用 C 语言接口构造和调用。 尽管如此，考虑到 Yap 和 YapTab 分别是目前最快的 Prolog 和表处理引擎之一，该方法仍然是将表处理集成到任何 Prolog 系统的一个不错的选择，它不需要对表处理的实现细节有高级知识，也不需要对底层引擎进行耗时或复杂的修改，并且源级转换和表处理原语可以很容易地移植到具有 C 语言接口的其他 Prolog 系统。目前，已经在与 Ciao 团队合作，将该实现作为 Ciao