4

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
false
  • 10,264
  • 13
  • 101
  • 209
Warren P
  • 65,725
  • 40
  • 181
  • 316

4 Answers4

5

Here is the reason for this non-termination. Your query does not terminate, because there is a 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 for more.

false
  • 10,264
  • 13
  • 101
  • 209
5

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 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 as shown in false's answer.

Community
  • 1
  • 1
mat
  • 40,498
  • 3
  • 51
  • 78
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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • Thanks for using the word Unifies. Now it makes sense again. I last did prolog in 1989. It's been a while. – Warren P Feb 10 '12 at 14:39
  • @WarrenP Wow, so you're an old-timer compared to me! I last did Prolog in 1996 :) – Sergey Kalinichenko Feb 10 '12 at 14:44
  • Your solution still does not terminate. – false Nov 15 '12 at 12:05
  • @false Why wouldn't it terminate if OP's `frack(3).` fact is still in place, and he's passing a `4`? – Sergey Kalinichenko Nov 15 '12 at 12:20
  • 1
    @dasblinkenlight: `frack(4)` does find a solution, but it does not terminate. Very old toplevels did not ask for "further solutions" if the goal was ground. So people thought that everything works. However, when they later used the code in another context, the loop came up at the most inappropriate moment. Think of `setof(X,(X=1,frack(4)),_)`. For this reason, newer toplevels (like in SWI, YAP, B, GNU) always ask for further answers, provided there is (internally) a choicepoint left. In this manner such hidden loops can be detected earlier (see [tag:failure-slice] for more). – false Nov 15 '12 at 12:27
  • @false Ah, interesting to know. My last Prolog runtime was Quintus back in 1996, I never touched Prolog since except to answer a few questions on SO. – Sergey Kalinichenko Nov 15 '12 at 12:31
  • @dasblinkenlight: Or take `frack(2)`. For many purposes the best toplevel currently is in SWI. – false Nov 15 '12 at 12:33
  • @false I'm curious if adding `frack(3) :- !.` would fix the non-termination for calls of `frack(X)` with `X` above `3`? – Sergey Kalinichenko Nov 15 '12 at 14:06
  • @dasblinkenlight: Above 3, yes. But not for `frack(2).` Usually you have some further arguments which makes understanding such cuts even more complicated. I personally prefer in any case [tag:clpfd] - [like this](http://stackoverflow.com/a/11704020/772868) – false Nov 15 '12 at 14:17
2

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

frack(X) :- X1 is X-1, frack(X1).
Scott Hunter
  • 48,888
  • 12
  • 60
  • 101