Page 42 - 《软件学报》2024年第6期

2618 软件学报 2024 年第 35 卷第 6 期

异: 首先是类型定义语法上的轻微差异, 例如 Soufflé 中的“.type”与 DDlog 中的“typedef”; 其次则是类型系统上的
差异, 例如 Soufflé 中的“symbol”表示所有的字符串类型而 DDlog 中对应的类型名为“Tsymbol” (“IString”的别名).
这些差异都可以通过在 AST 的结构上进行对应的转换来简单地解决. 同样的处理方案也适用于变量命名风格、
内置函数命名、输入规则是否不变等方面的差异.

1 .type node = symbol 1 import fp
2 .decl node_ord(a:node,b:number) 2 import intern
3 .output node_ord 3 import souffle_lib
4 .comp Graph{ 4 import souffle_types
5 .decl edge(a:node,b:node) 5 typedef node = Tsymbol
6 .input edge 6 relation graph_edge(a:node, b:node)
7 } 7 input relation graph_edge_shadow(a:node, b:node)
8 .init graph = Graph 8 graph_edge(a, b) : - graph_edge_shadow(a, b).
node_ord(?a, ?a_ord) :- ?a_ord = ord(?a), graph.edge(?a, _).
9 9 output relation node_ord(a:node, b:Tnumber)
10 node_ord(?a, ?a_ord) : - 10 node_ord(a, a_ord) : -
11 (?a_ord = ord(?a), graph.edge(?a, _)); 11 var a_ord = ord(a), graph_edge(_, a).
12 (?a_ord = ord(?a), graph.edge(_, ?a)). 12 node_ord(a, a_ord) : -
13 .plan 1:(2,1), 2:(1,2) 13 var a_ord = ord(a), graph_edge(a, _).
(a) Soufflé 参考代码 (b) DDlog 参考代码
图 6 Soufflé 和 DDlog 语义等价的 Datalog 代码示例

“忽略”策略主要用于处理作为编译辅助内容的语法结构, 这些元素在 DDlog 中并没有对应的表示. 例如, 图 6
中 Soufflé 参考代码第 13 行的. plan 语句就是一种指导规则子句重排策略的语法结构. 在“忽略”策略下, 这类与
Soufflé 特定的语句将被我们的重写器直接忽略.

2.2.3 规则拓展重写
相比 DDlog 引擎, Soufflé 引擎在规则的拓展层面拥有更加强大的支持. 例如, 它可以支持 Datalog 语言不支持
的析取操作; 它也可以支持否定规则子句的无条件前置; 此外, 它还拥有一个优秀的规则子句重排器, 不仅可以推
断出对应规则可能的最优半朴素评估顺序, 还可以自动消除评估中的不确定规则.
对于这些与语义密切相关的差异, 不能通过单纯的 AST 结构重写来解决. 不过幸运的是, Datalog 规则的表现
力保证了这些 Soufflé 引擎的拓展在 DDlog 中存在一种语义等价的语法形式.
第一, 针对析取. 虽然 DDlog 中没有直接表示析取的语法结构, 但是通过并列两条规则的方式, DDlog 可以表
示这个语义. 以下是一个 Soufflé 中简单的例子.
node_ord(?a, ?a_ord):-
(?a_ord = ord(a), graph.edge(?a, _));
(?a_ord = ord(a), graph.edge(_, ?a)).
这个规则表示 node_ord 关系中的内容需要增加来自于两个推导的结果的并集, 中间通过表示析取的“;”连接.
遵循 Datalog 规则, 我们也可以将它重写为不包含“;”的等价形式如下.

node_ord(?a, ?a_ord) :- ?a_ord = ord(?a), graph.edge(_, ?a).
在图 5 的例子中, 这条规则出现在 Soufflé 参考代码中第 10–12 行, 和转换后 DDlog 参考代码中第 10–13 行
的两条规则相比, 我们还可以看到规则子句的重排, 有关于这部分的重写, 我们稍后就会谈到它.
第二, 针对函数类或带否定规则子句的重排. 在处理此类规则子句时, Soufflé 和 DDlog 对子句顺序的限制有