Prolog: Check if X is in range of 0 to K - 1

Question

I'm new to prolog and every single bit of code I write turns into an infinite loop.

I'm specifically trying to see if X is in the range from 0 to K - 1.

range(X,X).
range(X,K) :- K0 is K - 1, range(X,K0).

My idea behind the code is that I decrement K until K0 equals X, then the base case will kick in. I'm getting an infinite loop though, so something with the way I'm thinking is wrong.

Answer 1

Welcome to the wondrous world of Prolog! It seems you tried to leapfrog several steps when learning Prolog, and (not very surprisingly) failed.

Ideally, you take a book like Art of Prolog and start with family relations. Then extend towards natural numbers using successor-arithmetics, and only then go to (is)/2. Today, (that is, since about 1996) there is even a better way than using (is)/2 which is library(clpfd) as found in SICStus or SWI.

So let's see how your program would have been, using successor-arithmetics. Maybe less_than_or_equal/2 would be a better name:

less_than_or_equal(N,N).
less_than_or_equal(N,s(M)) :-
   less_than_or_equal(N,M).

?- less_than_or_equal(N,s(s(0))).
   N = s(s(0))
;  N = s(0)
;  N = 0.

It works right out of the box! No looping whatsoever. So what went wrong?

Successor arithmetics relies on the natural numbers. But you used integers which contain also these negative numbers. With negative numbers, numbers are no longer well ordered (well founded, or Noetherian), and you directly experienced that consequence. So stick with the natural numbers! They are all natural, and do not contain any artificial negative ingredients. Whoever said "God made the integers, all else is the work of man." must have been wrong.

But now back to your program. Why does it not terminate? After all, you found an answer, so it is not completely wrong. Is it not? You tried to reapply the notions of control flow you learned in command oriented languages to Prolog. Well, Prolog has two relatively independent control flows, and many more surprising things like real variables (TM) that appear at runtime that have no direct counterpart in Java or C#. So this mapping did not work. I got a little bit suspicious when you called the fact a "base case". You probably meant that it is a "termination condition". But it is not.

So how can we easily understand termination in Prolog? The best is to use a failure-slice. The idea is that we will try to make your program as small as possible by inserting false goals into your program. At any place. Certain of the resulting programs will still not terminate. And those are most interesting, since they are a reason for non-termination of the original program! They are immediately, causally connected to your problem. And they are much better for they are shorter. Which means less time to read. Here are some attempts, I will strike through the parts that are no longer relevant.

range(X,X).
range(X,K) :-
   K0 is K - 1, false,
   range(X,K0).

Nah, above doesn't loop, so it cannot tell us anything. Let's try again:

range(X,X) :- false.
range(X,K) :-
   K0 is K - 1,
   range(X,K0), false.

This one loops for range(X,1) already. In fact, it is the minimal failure slice. With a bit of experience you will learn to see those with no effort.

We have to change something in the visible part to make this terminate. For example, you might add K > 0 or do what @Shevliaskovic suggested.

Answer 2

I believe the simplest way to do this is:

range(X,X).
range(X,K) :- X>0, X<K-1.

and here are my results:

6 ?- range(4,4).
true .

7 ?-  range(5,8).
true.

8 ?- range(5,4).
false.

Answer 3

The simple way, as has been pointed out, if you just want to validate that X lies within a specified domain would be to just check the condition:

range(X,K) :- X >= 0 , X < K .

Otherwise, if you want your range/2 to be generative, would be to use the built-in between/3:

range(X,K) :- integer(K) , K1 is K-1 , between(0,K1,X).

If your prolog doesn't have a between/3, it's a pretty simple implementation:

%
% the classic `between/3` wants the inclusive lower and upper bounds
% to be bound. So we'll make the test once and use a helper predicate.
%
between(Lo,Hi,N) :-
  integer(Lo),
  integer(Hi),
  _between(Lo,Hi,N)
  .

_between(Lo,Hi,Lo) :- % unify the lower bound with the result
  Lo =< Hi            % - if we haven't yet exceeded the inclusive upper bound.
  .                   %
_between(Lo,Hi,N)  :- % otherwise...
  Lo < Hi ,           % - if the lower bound is less than the inclusive upper bound
  L1 is Lo+1 ,        % - increment the lower bound
  _between(L1,Hi,N)   % - and recurse down.
  .                   %