7

假设以下程序：

nat(0).
nat(s(N)) :- nat(N).

/* 0+b=b */
plus(0,B,B) :- nat(B).
/* (a+1)+b = c iff a+(b+1)=c */
plus(s(A),B,C) :- plus(A,s(B),C).

它非常适合添加两个数字，但是当我尝试以下排序的查询时： 

plus(Z,Z,s(0)).

Z在很明显没有解决方案（即Z>s(0)）之后，它会继续搜索可能的值很长时间

我熟悉 cut( !) 运算符，我的直觉说解决方案与它有关，我只是不确定在这种情况下如何使用它。

4

3 回答 3

4

!/0始终不是解决此类问题的好方法。它通常会导致更一般查询的有效解决方案丢失。

相反，考虑使用有限域约束，在这种情况下效果很好：

?- use_module(library(clpfd)).
true.

?- Z + Z #= 0.
Z = 0.

?- Z + Z #= 0, Z #> 0.
false.

编辑：根据要求，没有 CLP(FD) 的可能解决方案：

plus(0, Y, Y).
plus(s(X), Y, s(Z)) :- plus(X, Y, Z).
于 2014-03-23T22:38:15.937 回答
3

因此，您在这里要做的是了解特定程序的精确终止属性。Prolog 在这里与其他编程语言完全不同，因为它具有相对复杂的执行机制。特别是回溯与“正常分辨率”非常交织，然后与统一相结合。

了解原始程序问题的最简单方法是考虑以下故障片段（请参阅链接以获取其他示例）：

plus(0,B,B) :- false , nat(B)。
加（s（A），B，C）：-加（A，s（B），C），假。

如果这个小程序不会终止，那么您的原始程序也不会终止。所以我们可以先考虑这个程序什么时候不会终止的问题。

考虑第三个论点：只是C传递了一个变量。没有人对它的价值感兴趣（在这个片段中）。所以第三个参数对终止没有任何影响！

更糟糕的是，第二个参数也只是B头部中的一个自由变量，因此，该参数永远不会影响该片段是否终止。

因此：如果您希望该片段终止，则必须知道第一个参数。否则程序会循环。您还可以使用终止推理器将此屈服视为终止条件：

plus(A,B,C)terminates_if b(A),b(B);b(A),b(C).

最好的方法似乎是重新制定您的程序。给你以下终止条件：

plus(A,B,C)terminates_if b(A),b(B);b(C).

在 Prolog 中，我们通常喜欢进一步泛化程序，也接受一些意想不到的解决方案，同时将其终止条件提高到更好的条件：

plus(A,B,C)terminates_if b(A);b(C).

但是，最后一个版本现在承认并非总是可以接受的解决方案。例如plus(0, nonnumber, nonnumnber)，现在成功了，而您可能希望它失败。

当然，你也可以用 cut 做一些实验，但要注意，使用 cut 非常容易出错。至少你应该将它与适当的测试结合起来，这些测试通常会抵消“效率增益”。

于 2014-03-23T23:39:11.833 回答
1

我意识到我以错误的方式接近它，我需要的不是一个 cut( !)，而是一组不同的规则，这些规则找到X并Y通过“分解”Z直到它达到 0，因为X并且只有在减少Y时才会增加Z，它们永远不会被赋予不可能的值：

plus(0,0,0).
plus(s(A),B,s(C)) :- plus(A,B,C).
plus(0,s(B),s(C)) :- plus(0,B,C).
于 2014-03-23T23:08:32.603 回答