2

我正在阅读解决代数的程序的源代码。它的一部分是一个尝试从 0 到 9 的每个数字的过程。这是它的源代码：

digit(0, 0) :- !.
digit(X, X).
digit(D, N) :-
  N2 is N - 1 ,
  digit(D, N2) .

当我运行它并询问我得到：

?- digit(X, 9).
X = 9 ;
X = 8 ;
X = 7 ;
X = 6 ;
X = 5 ;
X = 4 ;
X = 3 ;
X = 2 ;
X = 1 ;
X = 0.

我似乎不太明白为什么程序数字会这样做。有人可以向我解释一下吗？

谢谢您的回答！

4

1 回答 1

3

首先，一些术语。digit在 Prolog 中被称为“谓词”，而不是“过程”或“函数”。重要的是，“谓词”并不完全像函数或过程那样做。谓词是对逻辑关系的描述，调用谓词会尝试满足由该关系定义的逻辑目标，为此可能有零个、一个或多个解决方案。为了满足这个目标，它可以实例化任何未实例化的变量或术语（那些还没有被赋值的）。

要了解 的行为digit，您需要通过了解谓词的作用来“阅读”它。在此上下文中的含义digit(X, N)是“X 是 0 到 N 范围内的数字”。如果是 0，那么根据该定义N，我们只期望一个答案 (0) 。X如果N > 0那时我们期望有多个答案是digit(X, N)正确的。为此编写的规则（谓词）是：

digit(0, 0) :- !.
digit(X, X).
digit(X, N) :- N2 is N - 1, digit(X, N2).

这里的顺序很重要，因为 Prolog 将尝试按照给定的顺序匹配这些规则，如下所述。

第一个宣布的事实是：

digit(0, 0) :- !.

这表示 0 是 0 和 0 之间的唯一数字。我之所以这么说只是因为剪切会告诉 Prolog 在满足此目标后不要再寻找任何答案。这digit(0, 0)将是真实的，目标digit(X, 0).将产生X = 0并完成。

接下来是：

digit(X, X).

这表明它X是从 0 到 的有效数字X。没有削减，因此在满足该规则后可能会寻求后续解决方案。诸如digit(X, 9)将匹配此规则的目标和 yield X = 9。请注意，当您输入 时digit(X, 9)，第一个找到的结果是X = 9因为这是遇到的第一个满足请求目标的规则digit(X, 9)。

最后，还有：

digit(X, N) :- N2 is N - 1, digit(X, N2).

这表示这X是一个从 0 到的数字，N如果X是从0到的数字N - 1（N2用于实例化值N-1）。所以如果我输入一个目标digit(X, 9)，它首先满足digit(X, X)如上所述。然后，由于该规则没有削减，当 Prolog 回溯以寻求更多解决方案时，它已经满足digit(X, X)，因此将继续满足digit(X, 9)，并在此过程中尝试满足. 由于这是一个新目标（不是原始目标），它从顶部开始，按照相同的逻辑，将首先遇到并满足。因此，显示的第二个解决方案将是（记住给出的第一个解决方案是）。digit(X, 8)digit(X, N)digit(X, 9)digit(X, X)X = 8X = 8X = 9

该逻辑按顺序继续，满足digit(X, 7),digit(X, 6)等，相应地显示 , 等的解X = 7，X = 6直到最终到达digit(X, 0)。如上所述，digit(X, 0)将最终满足digit(0, 0)，产生解决方案X = 0，然后由于切割而完成。至此，它已经用尽了所有的解决方案并完成了。

所以，结果是X = 9, X = 8, ..., X = 0。

关键是Prolog继续（迭代/回溯）为您的既定目标寻找解决方案，找到所有可能的解决方案，直到找到所有可能性（由书面规则确定为谓词），或者直到这些可能性被截断使用削减。

于 2013-06-23T17:27:19.533 回答