backtracking - Can you write between/3 in pure prolog?

Question

I've been trying to understand how to produce a series of values from a Prolog predicate on backtracking. The builtin predicate between/3 will generate all the integers in a range one at a time on backtracking, so an example of how that is written may help me with my task.

I looked for an implementation in an existing Prolog system, but the implementation of between/3 for GNU Prolog is a C function, and the trick there is that it calls another C function "Pl_Create_Choice_Point" which allows it to produce additional values on backtracking.

Answer 1

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

In action:

$ 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.

If you use a cut, you can prevent the final search failure, and recover the exact builtin between/3 behavior:

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).

In action:

?- [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.