Prolog/約束邏輯程式設計
我們已經看到，在 Prolog 中，一個變數可以是繫結的（具有一個值，可能是另一個變數）或自由的（沒有值）。約束邏輯程式設計 (CLP) 擴充套件了邏輯變數的概念，允許變數具有域而不是特定值。變數也可以被約束，這意味著它們的值必須遵守程式設計師指定的某些規則。約束邏輯程式設計使得用最少的程式碼量解決複雜的組合問題成為可能。
通常，Prolog 程式設計圍繞著對變數值的約束，體現在統一的概念中。例如，目標 X = f(1) 可以說約束變數 X 來獲取值 f(1)。統一當然比這更通用，因為 X = Y 約束兩個變數來獲取相同的值，而 X = f(_) 則以第三種方式約束 X：它可以獲取包括 f([]) 和 f(hamburger) 在內的無限個值集中的任何一個值，但它獲取的值必須與“模板” f(_) 相匹配。
然而，標準統一是有限制的，因為它只能對變數施加“正”約束。如果我們想說明 X 可以繫結到除那些與 f(_) 匹配的值以外的任何值，那麼我們可以將統一與否定一起使用，但我們必須非常小心。正如我們之前在一章中所見，我們有時可以使用失敗否定來表達不等式，但這並不總是可靠的。
?- X = 1, \+ X == 1.
false.
?- \+ X == 1, X = 1.
true
\+ 的這種非單調屬性迫使我們重新排序目標，以便在恰當的時間繫結變數，這使得程式碼更難閱讀、編寫和理解。
- 練習。編寫一個謂詞，當其輸入是僅包含唯一值的列表時成功。例如，
unique([1,2])應該成功，但unique([foo,foo,1])應該失敗，因為foo出現了兩次。你的謂詞如何處理unique([X,X])？unique([A,B,C,D])呢？
輸入 dif 謂詞。這個謂詞可以在 SWI 和 SICStus 中使用（但不是嚴格的標準 Prolog），它允許我們約束兩個變數不同。下面的 SWI-Prolog 會話顯示了它的操作。
?- dif(X,Y).
dif(X,Y).
?- dif(X, Y), member(X, [foo, bar]), member(Y, [foo, bar]).
X = foo,
Y = bar ;
X = bar,
Y = foo ;
false.
將這與其他不等謂詞 \= 和 \== 的結果進行對比。
- 練習。再次實現
unique/1謂詞，但這次使用dif/2。Prolog 對查詢unique([A,B,C,D,E])的響應是什麼？它報告了多少個約束？
- 練習。編寫一個謂詞
not_f1/1，它約束其引數不為f(_)形式，即不為具有函子f的一個引數項。提示：使用=..(“univ”) 運算子。
現在，我們轉向一個功能更強大的約束處理系統：有限域上的約束邏輯程式設計，也稱為 CLP(fd)。要使用它，我們必須載入一個庫。在 SWI-Prolog 中，就是
?- use_module(library(clpfd)).
你還記得 Prolog 中的算術如何在與未充分例項化的變數一起使用時會失敗嗎？試試這個作為開始
?- X > Y, member(X,[1,2,3]), Y=2.
即使這個查詢在邏輯上只有一個可能的答案（X=3），Prolog 無法推斷出來。我們可以透過重新排列查詢的連詞來得到正確的答案
?- member(X,[1,2,3]), Y=2, X > Y.
當涉及算術時，CLP(fd) 比 Prolog 聰明得多。試試這個（注意：ECLiPSe 使用者應該用替換為::):
?- X #> Y, X in 1..3, Y=2.
這個成功地得到了唯一的正確答案，X=3. 謂詞#>/2在給出兩個變數時，釋出約束，即它的左引數應該大於它的右引數。CLP(fd) 將此約束儲存在其約束儲存中，直到它對變數的可能值有了足夠的瞭解才能從其中推斷出更多資訊。當Y獲取值 2 時，CLP(fd) 推斷出X只能取值為 3。
當我們繫結Y到 1 時會發生什麼？
?- X #> Y, X in 1..3, Y=1.
Y = 1,
X in 2..3.
而不是開始回溯X的可能值，CLP(fd) 將X約束到更小的域並停止。要讓 CLP(fd) 搜尋變數的可能賦值，我們必須明確告訴它這樣做。最簡單的方法是使用謂詞label/1:
?- X #> Y, X in 1..3, Y=1, label([X]).
X = 2,
Y = 1 ;
X = 3,
Y = 1.
到目前為止，我們所看到的並不那麼有趣，因為只有一個約束變數。讓我們看看一個有八個變數的問題。
send more money 謎題是約束問題的典型例子。它相當於將 0 到 9 之間的不同數字分配給變數[S,E,N,D,M,O,R,Y]以便求解該和
SEND + MORE = MONEY
；S和M都應該大於零。我們不是在 Prolog 提示符中輸入，而是建立一個合適的 Prolog 模組。
:- use_module(library(clpfd)).
sendmoremoney(Vars) :-
Vars = [S,E,N,D,M,O,R,Y],
Vars ins 0..9,
S #\= 0,
M #\= 0,
all_different(Vars),
1000*S + 100*E + 10*N + D
+ 1000*M + 100*O + 10*R + E
#= 10000*M + 1000*O + 100*N + 10*E + Y.
ins/2與in/2相同，除了它同時設定多個變數的域。（ECLiPSe：使用::, SICStus：使用domain(Vars,0,9)). all_different（在一些實現中可能被稱為all_distinct）在邏輯上等效於在#\=Vars中的所有變數對上釋出不等式約束（），但更短，可能更高效。請注意，我們可以將求和表示為對所有八個變數的單個約束。讓我們試一試
?- sendmoremoney([S,E,N,D,M,O,R,Y]).
S = 9,
M = 1,
O = 0,
E in 4..7,
all_different([E, N, D, R, Y, 0, 1, 9]),
1000*9+91*E+ -90*N+D+ -9000*1+ -900*0+10*R+ -1*Y#=0,
N in 5..8,
D in 2..8,
R in 2..8,
Y in 2..8.
即使沒有對變數進行標記，CLP(fd) 也推斷出三個變數的值，簡化了求和，並對剩餘的五個變數施加了更嚴格的邊界。當然，我們希望得到所有變數的值
?- Vars=[S,E,N,D,M,O,R,Y], sendmoremoney(Vars), label(Vars).
Vars = [9, 5, 6, 7, 1, 0, 8, 2],
S = 9,
E = 5,
N = 6,
D = 7,
M = 1,
O = 0,
R = 8,
Y = 2
這應該會立即執行。練習：在 Prolog 中實現這個謎題，但不要使用 CLP(fd)，並注意執行需要多長時間。