编程语言导论/统一成本模型
< 编程语言导论
我们从一个激励性的问题开始这一节。以下用 Prolog 写的谓词的复杂度是什么？
&=([], []).
&=([H|Tl], [H|Tr]) :- &=(Tl, Tr).
人们很容易被误导认为该谓词在线性于最小列表的参数数量上。但是，我们可以考虑像这样的调用
&=([[1, 2, 3, 4, 5], [a, b, c, d, e]], [[1, 2, 3, 4, 5], [a, b, c, d, e]]).
我们不能只用两个操作来解决对&=的这个调用。必须逐一比较构成较大列表的两个子列表。在这种情况下，&=的复杂度与列表的大小成正比，而不是列表元素的数量。基于统一的搜索算法必须扫描整个数据结构才能推断出它们的属性。并且这个扫描操作是穷举性的：在统一解析期间，将探索所有可能的有效子句组合。这带来了一个重要观点：出于效率原因，最好先解决最严格的子句，将更开放的子句留待以后。例如，考虑以下谓词
parent(d, a).
parent(f, e).
parent(a, b).
parent(e, b).
parent(e, c).
male(a).
male(d).
给定这些项，在这两个实现中，哪一个更好？
grandfather_1(X,Y) :- parent(X,Z), parent(Z,Y), male(X).
grandfather_2(X,Y) :- male(X), parent(X,Z), parent(Z,Y).
第二个谓词效率更高。要了解原因，请注意有两个子句与male(X)在我们谓词数据库中统一male(a)和male(b). 因此，grandfather_2的搜索树从两个节点开始。每个与parent(X, Y)统一的节点最多只能有两个节点，要么是parent(a, b)要么是parent(d, a), 因为 a 和 d 是唯一满足male(X).
如果我们使用grandfather_1, 情况就会不同。这次，我们的搜索树从五个节点开始，因为parent(X, Z)与五个子句统一。反过来，这些节点中的每一个都跨越了三个新节点。这棵搜索树比grandfather_1生成的树大得多；因此，构建起来也需要更长的时间。讨论的底线是：即使谓词中项的顺序不应该对其正确性有任何影响，但这个顺序对于效率原因仍然很重要。更严格的谓词应该放在前面，因为它们更有效地修剪在统一过程中探索的搜索树。
