程式語言導論/統一成本模型
< 程式語言導論
我們從一個激勵性的問題開始這一節。以下用 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生成的樹大得多；因此，構建起來也需要更長的時間。討論的底線是：即使謂詞中項的順序不應該對其正確性有任何影響，但這個順序對於效率原因仍然很重要。更嚴格的謂詞應該放在前面，因為它們更有效地修剪在統一過程中探索的搜尋樹。
