2

I read in Mellish, Clocksin book about Prolog and got to this:

is_integer(0).

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

with the query ?- is_integer(X). the zero output is easy but how does it get 1, 2, 3, 4...

I know it is not easy to explain writing only but I will appreciate any attempt.

After the 1-st result X=0 I hit ; then the query becomes is_integer(0) or is still is_integer(X)?

It's long time I search for a good explanation to this issue. Thanks in advance.

lurker
  • 56,987
  • 9
  • 69
  • 103
vincent
  • 101
  • 1
  • 9
  • Prolog uses "backtracking". After it gives you the solution `X=0` and you hit `;`, it will move on to `is_integer(X)` because it's already done `is_integer(0)`. When it calls `is_integer(X)` as a clause, then the recursive call to `is_integer(Y)` will go back to `is_integer(0)` sine it's a new call. You can turn on `trace.` in your prolog interpreter and watch what happens. :) – lurker Dec 12 '13 at 02:24
  • Yes I did watch it with the trace but it doesn't arrive to me. Look how I see it: 1) The query gets matched with the fact and X = 0. – vincent Dec 12 '13 at 02:45
  • When you hit the second `;`, backtracking takes you to the last choice point, which would be the last call to `is_integer(Y)` which had first instantiated `Y=0`. The next time it will instantiate `Y=1` for the same reason your first `;` instantiated `X=1`. The calls nest deeper and deeper to give you `2`, `3`, etc... – lurker Dec 12 '13 at 02:48
  • how does Y get = to 1? From my view is_integer(Y) gets always matched to is_integer(0) and Y always = 0. Sorry for being stupid. – vincent Dec 12 '13 at 03:23
  • backtracking to the last choice point. See Daniel Lyons' detailed explanation. – lurker Dec 12 '13 at 09:48
  • Have you realized that this example is a bit flawed, in the sense that when called with an instantiated argument, you get a true, and upon backtracking end up in an endless loop? –  Dec 12 '13 at 13:43
  • 1
    Please look at this response: http://stackoverflow.com/questions/14115722/backtracking-in-recursive-predicates/14116016#14116016 – false Dec 12 '13 at 14:17

3 Answers3

4

This strikes to the heart of what makes Prolog so interesting and difficult. You're definitely not stupid, it's just extremely different.

There are two rules here. The existence of alternatives causes choice points to be created. You can think of the choice point as a moment when Prolog saw an alternate way of proceeding with the computation. Prolog always tries rules in the order they appear in the database, which will correspond to the order they appear in the source file. So when you issue the query is_integer(X), the first rule matches and unifies X with 0. This is your first result.

When you press ';' you are telling Prolog to fail, that this answer is not acceptable, which triggers backtracking. The only thing for Prolog to do is try entering the other rule, which begins is_integer(Y). Y is a new variable; it may or may not wind up instantiated to the same value as X, so far you haven't seen any reason why that wouldn't be the case.

This call, is_integer(Y) essentially duplicates the computation that's been attempted so far. It will enter the first rule, is_integer(0) and try that. This rule will succeed, Y will be unified with 0 and then X will be unified with Y+1, and the rule will exit having unified X with 1.

When you press ';' again, Prolog will back up to the nearest choice point. This time, the nearest choice point is the call is_integer(Y) within the second rule for is_integer/1. So the depth of the call stack is greater, but we haven't left the second rule. Indeed, each subsequent result will be had by backtracking from the first to the second rule at this location in the previous location's activation of the second rule. I doubt very seriously a verbal explanation like the preceeding is going to help, so please look at this trashy ASCII art of how the call tree is evolving like this:

1     2       2
     /         \
    1           2
               /
              1

^     ^        ^
|     |        |
0     |        |
     1+0       |
             1+(1+0)

where the numbers are indicating which rule is activated and the level is indicating the depth of the call stack. The next several steps will evolve like this:

2            2
 \            \
  2            2
   \            \
    2            2
   /              \
  1                2
                  /
                 1

   ^             ^
   |             |
1+(1+(1+0))      |
 = 3          1+(1+(1+(1+0)))
                = 4

Notice that we always produce a value by increasing the stack depth by 1 and reaching the first rule.

Daniel Lyons
  • 22,421
  • 2
  • 50
  • 77
  • Daniel reading it again after some time I realize your answer is superlative. But I am still stocked at this problem. Why would the depth of the call increase at each backtrack? I mean why backtracking would turn the rule in one like new? And what makes the connection betwin the different leveles? – vincent Feb 10 '14 at 22:23
  • @vincent Please email me, and I'll continue the explanation. It won't fit in a comment. :) fusion@storytotell.org – Daniel Lyons Feb 11 '14 at 00:09
3

The answer of Daniel is very good, I just want to offer another way to look at it.

Take this trivial Prolog definition of natural numbers based on TNT (so 0 is 0, 1 is s(0), 2 is s(s(0)) etc):

n(0).            % (1)
n(s(N)) :- n(N). % (2)

The declarative meaning is very clear. (1) says that 0 is a number. (2) says that s(N) is a number if N is a number. When called with a free variable:

?- n(X).

it gives you the expected X = 0 (from (1)), then looks at (2), and goes into a "new" invocation of n/1. In this new invocation, (1) succeeds, the recursive call to n/1 succeeds, and (2) succeeds with X = s(0). Then it looks at (2) of the new invocation, and so on, and so on.

This works by unification in the head of the second clause. Nothing stops you, however, from saying:

n_(0).
n_(S) :- n_(N), S = s(N).

This simply delays the unification of S with s(N) until after n_(N) is evaluated. As nothing happens between evaluating n_(N) and the unification, the result, when called with a free variable, is identical.

Do you see how this is isomorphic to your is_integer/1 predicate?

A word of warning. As pointed out in the comments, this query:

?- n_(0).

as well as the corresponding

?- is_integer(0).

have the annoying property of not terminating (you can call them with any natural number, not only 0). This is because after the first clause has been reached recursively, and the call succeeds, the second clause still gets evaluated. At that point you are "past" the end-of-recursion of the first clause.

n/1 defined above does not suffer from this, as Prolog can recognize by looking at the two clause heads that only one of them can succeed (in other words, the two clauses are mutually exclusive).

  • 1
    `n_/1` now does never terminate, whereas `n/1` does when there are finitely many solutions – false Dec 12 '13 at 13:33
  • @false You are of course correct, but the demonstrated `is_integer/1` has the exact same problem.... Unfortunately I don't have the book to see the context of the example. Do you know why it is presented like this? –  Dec 12 '13 at 13:40
  • 2
    It only shows once again, that beginners should not use `(is)/2`. Instead, `library(clpfd)` should be used. – false Dec 12 '13 at 13:43
  • Thanks. I think I got it seeing your part Boris. The Y goal gets instantiated with the head of the rule and gets the previous value of X and in the second goal of the rule increments the X by 1. I am very close to being sure. Maybe I didn't realize that backtracking is made from buttom to top? Any way all of you are very kind to help me. – vincent Dec 12 '13 at 14:06
  • @vincent Backtracking goes to the last choice point created, and predicate clauses are evaluated top to bottom, so yes. –  Dec 12 '13 at 14:11
  • +1, very good, declarative answer. And I second *false*'s suggestion that beginners should use `library(clpfd)` instead, where `X in inf..sup` states that `X` is an integer. – mat Dec 12 '13 at 14:43
0

enter image description here

I attempted to put into a graphic @daniel's great answer. I found his answer enlightening and could not have figured out what was going on here without his help. I hope that this image helps someone the way that @daniel's answer helped me!

Will Hawkins
  • 111
  • 1
  • 4