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.

Answer 2

What you're really asking is how to create a choice point. You get a solution whenever you have a successful unification. That's what happens in @seanmcl's first predicate:

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

To get a choice point, you need to have alternatives. There are only two ways to get an alternative in Prolog: with an explicit "or": ;, or by supplying another rule. @seanmcl's code gives another rule, which is idiomatic for this situation.

To give another example, member/2 generates a solution for every item in the list, but there's no magic C function needed, just two rules:

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

Let's look at what happens here with member(X, [1,2]). First, the first rule is used and [X|_] is unified with [1,2], producing X=1, _=[2]. This is a successful unification, so a solution is generated. If this fails (such as by you pressing ; at the console), backtracking is initiated. The next choice point is between the two rules, so the next rule is entered. [_|Xs] unifies with [1,2], producing the binding Xs=[2] and then member(X, [2]) is called. Upon re-entry, the same decisions are available to be made again, so the first rule member(X, [X|_]) is applied and the X=2 binding is produced. This is a solution. If you backtrack again, you'll get a harmless failure because neither of the rules unify with [].

I hope this helps make sense of the situation a little bit.