Predicate that generates integers and tests if integer

Question

I'm trying to make a Prolog predicate that will let me test if a given value is a integer bigger than 0, and also give me a valid integer given a variable. It now looks like this:

intgr(1).
intgr(X) :- intgr(Y), X is Y+1.

This will generate all integers, but when used as intgr(8), it will find that it's valid, and then loop forever. Any ideas of how to solve this?

Answer 1

For generating natural numbers, you can easily write a tail-recursive (and thus more space efficient) predicate. For example:

next_integer(I) :-
    next_integer(1, I).

next_integer(I, I).
next_integer(I, J) :-
    I2 is I + 1,
    next_integer(I2, J).

But note that several Prolog compilers already provided, either as a built-in predicate or as a library predicate, the de facto standard between/3 predicate, which allows you to enumerate integers in a given interval. For example:

?- between(1, 3, I).
I = 1 ;
I = 2 ;
I = 3.

Depending on the implementation, you may also be able to use this predicate to test if an integer belongs to a given interval without leaving spurious choice points. For example:

?- between(1, 3, 2).
true.

Back to your question, your predicate will loop on backtracking when testing as there's nothing in it that says that the argument you pass will not be found again by continuing to add one at each pass. One solution would be to test the argument using the standard built-in predicate var/1 and cut on the first solution when the argument is bound. For example:

next_integer(I) :-
    (   var(I) ->
        next_integer(1, I).
    ;   integer(I) ->
        next_integer(1, I),
        !
    ;   fail    % or error
    )

next_integer(I, I).
next_integer(I, J) :-
    I2 is I + 1,
    next_integer(I2, J).

Hope this helps.

Answer 2

Here is first the reason why your program does not terminate. To see this, I will add goals false into your program:

intgr(1) :- false.
intgr(X) :- intgr(Y), false, X is Y+1.

What is now interesting is the following property. Given any query for your program,

If this fragment (failure-slice) does not terminate, then also your original program does not terminate.

In this fragment it is probably easier to see: There is no way how this program can terminate. The variable X occurs only once in the head. In the visible part of the program there is no further reference and thus nobody cares about the concrete instantiation of X. That is: No matter what you put as argument to intgr/1, your definition will loop. Anything! intgr(-1) loops, intgr(stop) loops, intgr(X) loops, intgr(1) loops.

For more about failure-slices and how to use them see tag failure-slice.

To remove the problem something has to be changed in the visible part of your program. Don't look at the strike-through sections - they will not be able to improve termination.

I would use length(_, N) which includes 0. Here is another way using library(clpfd):

?- X #> 0.

And if you insist on enumerating the solutions:

nat(0).
nat(X0) :-
   X0 #> 0,
   X1 #= X0-1,
   nat(X1).