What's correct way to make natural number rule in prolog?

Question

I guess I have some bigger problem in understanding prolog, but since I can't quite formulate it, I focus on single problem

I want to create a rule natural(X) that is true if X is 1,2,3,4,...
More importantly, I want both: natural(5) to be true and natural(X) to output X=1; X=2; ...

So, I explain rule as follows (pseudologic):

natural(1) must be true
natural(X) is true if natural(X-1) is true

or, in terms of prolog:

natural(1).
natural(X) :- natural(X-1).

but I get a problem - if I try natural(5) I get infinite recursion
debugger says that program evaluates:

natural(5)
 natural(5-1)
  natural(5-1-1)
   natural(5-1-1-1)
    natural(5-1-1-1-1)
     natural(5-1-1-1-1-1)
      natural(5-1-1-1-1-1-1)
...

I guess the problem is in X-1 not being evaluated?
Let's try to fix that:

natural(1).
natural(X) :-
  Y is X-1,
  natural(Y).

now, natural(5) works as expected
but, if I use natural(X) I get X=1; Exception: Arguments not sufficiently instantiated (Y is X-1)

ok, I guess the problem is we try to evaluate stuff that can be without value yet
If I try to use Y = X-1 we return to first problem. Y == X-1 returns false

The only solution that I found to work was switching lines and definition order:

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

Changing last line to = gives "+1+1+1..." results. == just fails.

This solution works great in generating X=1; X=2; ..., but when I use it as check (natural(5)), it goes in "0,(0,1),(0,1,2),(0,1,2,3),..." order. Yes I get correct result, but the path there is long and not what I would've imagined.
I would've stopped here, if I haven't seen the faster way of checking for natural(5) in previous solution.

So, what is better way of creating this rule have I missed?

I guess one way would be separating "true/false" queries from generator queries... But is there a way to make it "evaluate if possible to evaluate", i.e. separate only-constants from has-variables? var(X-1) is false somehow...

Use successor-arithmetics first to define natural numbers. In it, it is all natural, with (is)/2 it is very hard and incomplete. Then, use library(clpfd), which is even more natural. Think of: X #>= 0. — false

Daniel Lyons Daniel Lyons · Accepted Answer · 2019-12-04T04:17:52

Dealing with naturals is usually improved considerably by using succ/2. is/2, as you have discovered, is required for Prolog to evaluate an arithmetic expression, but it has a single instantiation pattern: -Number is +Expr. Without constraints, it would be total insanity for that to have a completely open pattern such as ?Number is ?Expr.

succ/2, on the other hand, has two patterns: succ(+Pred, -Succ) and succ(-Pred, +Succ). To wit: succ(X, 3) unifies X = 2 and succ(2, X) unifies X = 3. Although succ(X, Y) still is an error. However, you can build a solution to natural/1 using succ/2, with a caveat:

natural(1).
natural(X) :- natural(X0), succ(X0, X).

Logically, this should be the same as succ(X0, X), natural(X0), but Prolog is not logic, it has an evaluation order. This trick basically forces your request for whether X is a natural to start at X-1, go immediately to X-2, and thence downward until it hits 1, whereupon it can back up and start succeeding. If you supply a negative number, it fails right away because succ/2 fails for negatives. This works in both of your required ways, but has a nasty problem:

?- natural(X).
X = 1 ;
X = 2 ;
X = 3 ;
....

?- natural(5).
true ;
^CAction (h for help) ? abort

Yes, we get an infinite loop if we ask for a second result after supplying the value. Prolog goes off trying to find out if 5 ever appears again after 5.

A simple solution that avoids the problem is to use between/3:

natural(X) :- between(1, inf, X).

?- natural(X).
X = 1 ;
X = 2 ;
X = 3 ;
...

?- natural(5).
true.

No loop. This would be my preferred solution.

In addition to var/1 and nonvar/1 there is also ground/1, which can distinguish between terms that have variables and terms that do not. You can use that to make a distinction between (on one side) 5, 3-1, etc. and X, X-1, on the other. In my experience, breaking apart cases like this usually leads to tears and trouble with backwards correctness, but in extreme cases it may be warranted.

At this point you may be feeling a little sour about Prolog's logic. The standard system's arithmetic is on the disappointing side. But clpfd is much more powerful and flexible, and many people recommend you learn that first because it is better at generating solutions (is/2 really can't generate, but labeling can with clpfd). In my experience, succ/2 is close enough to Peano arithmetic that integer messing around is often OK, but for anything serious you will want to use clpfd.

What's correct way to make natural number rule in prolog?

1 Answers