prolog - 你能用纯序言写 between/3 吗？

Question

我一直在尝试了解如何从 Prolog 谓词中的回溯生成一系列值。内置谓词between/3将在回溯时一次生成一个范围内的所有整数，因此一个如何编写的示例可能会帮助我完成我的任务。

我在现有的 Prolog 系统中寻找了一个实现，但between/3GNU Prolog 的实现是一个 C 函数，其中的诀窍是它调用另一个 C 函数“Pl_Create_Choice_Point”，它允许它在回溯时产生附加值。

Answer 1

bet(N, M, K) :- N =< M, K = N.
bet(N, M, K) :- N < M, N1 is N+1, bet(N1, M, K).

在行动：

$ swipl
?- [bet].
% bet compiled 0.00 sec, 1,064 bytes
true.

?- bet(1,5, K).
K = 1 n
K = 2 n
K = 3 n
K = 4 n
K = 5 n
false.

如果使用 cut，则可以防止最终搜索失败，并恢复确切的内置 between/3 行为：

bet(N, M, K) :- N < M, K = N.
bet(N, M, K) :- N == M, !, K = N.
bet(N, M, K) :- N < M, N1 is N+1, bet(N1, M, K).

在行动：

?- [bet].
% bet compiled 0.00 sec, 416 bytes
true.

?- between(1,5,K).
K = 1 n
K = 2 n
K = 3 n
K = 4 n
K = 5.

?- [bet].
% bet compiled 0.00 sec, 240 bytes
true.

?- bet(1,5,K).
K = 1 n
K = 2 n
K = 3 n
K = 4 n
K = 5.

Answer 2

你真正要问的是如何创建一个选择点。只要你有一个成功的统一，你就会得到一个解决方案。这就是@seanmcl 的第一个谓词中发生的情况：

bet(N, M, K) :- N =< M, K = N.

要获得选择点，您需要有替代方案。在 Prolog 中只有两种方法可以获得替代方案：使用明确的 "or":;或提供另一个规则。@seanmcl 的代码给出了另一个规则，这是这种情况的惯用语。

再举一个例子，member/2为列表中的每个项目生成一个解决方案，但不需要神奇的 C 函数，只需两条规则：

member(X, [X|_]).
member(X, [_|Xs]) :- member(X, Xs).

让我们看看这里发生了什么member(X, [1,2])。首先，使用第一条规则并[X|_]与[1,2], 产生X=1,统一_=[2]。这是一个成功的统一，因此产生了一个解决方案。如果失败（例如您;在控制台上按），则会启动回溯。下一个选择点在两条规则之间，所以输入下一条规则。[_|Xs]与 [1,2] 结合，产生绑定Xs=[2]，然后member(X, [2])被调用。重新进入时，可以再次做出相同的决定，因此应用第一条规则member(X, [X|_])并X=2产生绑定。这是一个解决方案。如果你再次回溯，你会得到一个无害的失败，因为这两个规则都没有与[].

我希望这有助于稍微了解情况。