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)，并注意运行需要多长时间。