generation of positive numbers in a special case

Question

Hi,

i am searching for a possibility to transform this code

zero(0).
positive(X) :- \+ zero(X).

so that calls like

?- positive(X).

will generate values for X.

Actually only calls with specific values for X are tested correctly but no values can be generated.

Thanks.

Answer 1

Your code as posted here won't test anything correctly, except negative numbers, and then only accidentally (even a stopped clock is right twice a day :-) ):

positive(X) :- \+ zero(0).

The \+/1 predicate succeeds if there is no way to satisfy its argument. In other words, it will yield true whenever zero(0) can't be satisfied. But zero(0) is always satisfied (it's a fact!). So positive(X) here will yield false for any X – including 0!

I assume you really meant:

positive(X) :- \+ zero(X).

which fails too, but in a more interesting way. Remember that \+/1 fails if there is any way to satisfy its argument. If you query:

?- positive(1).

it will bind X to 1, and see if it's possible to satisfy zero(X) with the constraint that X must be 1. It's not, so positive(1) will yield true.

However, if you query:

?- positive(X).

you're asking if it's possible to satisfy zero(X) with no constraints on X. It is possible to do this by binding X to 0, which means zero(X) can be satisfied for some X – which will cause \+ zero(X) to yield false.

A closer step is to try:

positive(X) :- X > 0.

which takes negative numbers into account as well. This will give the right answer for positive(1), positive(0), and positive(-1). However, it won't generate numbers. If you try this:

?- positive(X).

you'll get:

ERROR: >/2: Arguments are not sufficiently instantiated

because you haven't said enough about what X is for the >/2 predicate to take effect – arithmetic operators cannot be invoked on uninstantiated objects (aka free variables, aka what X is in this case). This in general is going to be a problem with your "generate some integers" approach.

You can, however, specify a particular numeric range that you want to take values from, and have Prolog proceed from there:

positive(X) :- X > 0.
genPositive(X) :- between(-100, 100, X), positive(X).

Answer 2

You could write virtually straightforward

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

and this indeed will work

?- positive(X).
X = 1 ;
X = 2 ;
X = 3 ;
X = 4 ;
etc

but have in mind, that being not tail-recursive this algorithm is exponentially complex. I mean:

 ?- time((positive(X),X>4000)).
% 8,010,001 inferences, 3.70 CPU in 3.73 seconds (99% CPU, 2163038 Lips)
X = 4001.

Note the time for generation of 4000 positives.

But if we right it like:

positive1(X) :- from(1,X).

from(From,From).
from(From,X):-From1 is From + 1, from(From1,X).

All works fast now:

 ?- time((positive1(X),X>4000)).
% 8,002 inferences, 0.00 CPU in 0.00 seconds (?% CPU, Infinite Lips)
X = 4001.