你能在纯Prolog中写出between/3吗？

Question

我一直在尝试理解如何通过Prolog谓词回溯生成一系列值。内置的谓词between/3会在回溯时逐个生成范围内的所有整数，因此一个实现该谓词的示例可能对我有所帮助。

我寻找了现有Prolog系统中的实现，但GNU Prolog的between/3实现是一个C函数，其中的技巧在于它调用另一个C函数"Pl_Create_Choice_Point"，从而允许它在回溯时生成附加值。

- postfuturist

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，可以防止最终搜索失败，并恢复 exact builtin 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.

- seanmcl

---

你的初始版本稍微好一些，因为它不会在末尾失败。 - user1812457

Answer 2

你实际上要问的是如何创建一个选择点。只有在成功的统一时才能得到解决方案。这就是 @seanmcl 的第一个谓词中发生的事情:

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

为了获得一个选择点，你需要有备选方案。在Prolog中，只有两种获得备选方案的方法：通过显式的“或”：;，或者提供另一条规则。@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 绑定。这是一个解决方案。如果再次回溯，将得到一个无害的失败，因为没有一个规则与 [] 统一。希望这能让情况更加清晰易懂一些。

- Daniel Lyons