Prolog: Error out of global stack with what looks like ONE level of recursion to me

Question

I am quite rusty in prolog, but I am not sure why things like this fail:

frack(3).

frack(X) :- frack(X-1).

So, if I evaluate frack(4). from the interactive prompt with the above facts defined, I expect that it should not have to endlessly recurse, since 4-1 = 3. But I get this error in SWI-Prolog:

ERROR: Out of global stack

Answer 1

Try it:

?- 4-1 = 3.
false.

Why? Because 4-1 = -(4, 1), which clearly is not a number but a compound term.

To reason about integers in Prolog, use clpfd constraints, for example (using GNU Prolog or B-Prolog):

| ?- 4-1 #= X.

X = 3

In SWI-Prolog, the graphical tracer may be useful for you to see what happens:

?- gtrace, frack(4).

For more complex debugging, I recommend failure-slice as shown in false's answer.

Answer 2

Here is the reason for this non-termination. Your query does not terminate, because there is a failure-slice of your program that does not terminate:

?- frack(4).

frack(3) :- false.
frack(X) :-
   frack(X-1), false.

You can fix this only by modifying something in the visible part. Three SO-answers suggest to use (is)/2. But this will not remove non-termination! In fact, using (is)/2 leads to essentially the same fragment:

?- frack(4).

frack(3) :- false.
frack(X) :-
   Y is X - 1,
   frack(Y), false.

At least, frack(4) now succeeds, but it will loop on backtracking. You have to change something in the visible part, like some test for X, in order to avoid non-termination. See failure-slice for more.

Answer 3

frack(X) :- frack(X-1).

should be

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

The way you wrote it, X-1 expression of the first level unifies with X variable at the next level, never going for the frack(3) fact.

Answer 4

Prolog doesn't do arithmetic unless you use the is operator:

frack(X) :- X1 is X-1, frack(X1).