3

From Bratko's book, Prolog Programming for Artificial Intelligence (4th Edition) We have the following code which doesn't work - 

anc4(X,Z):-
    anc4(X,Y),
    parent(Y,Z).
anc4(X,Z):-
    parent(X,Z).

In the book, on page 55, figure 2.15, is shown that parent(Y,Z) is kept calling until stack is out of memory.

What I don't understand is that prolog does a recursiv call to anc4(X,Y), and not to parent (Y,Z) first. Why doesn't prolog goes over and over to the first line, anc4(X,Y), and rather goes to the second line?

Can you please elaborate why is the line parent(Y,Z) is kept being called?

Thank you.

false
  • 10,264
  • 13
  • 101
  • 209
Assaf
  • 1,112
  • 4
  • 14
  • 35
  • 1
    `anc4(X, Z) :- anc4(X, Y), ...` right there. Prolog will keep selecting the first clause until it fails or succeeds. It does neither. It just keeps calling `anc4/2` again. – lurker Sep 07 '18 at 16:08
  • 1
    See [tag:failure-slice] on how to diagnose such problems. – false Sep 08 '18 at 12:36
  • 2
    And see [this question](https://stackoverflow.com/q/30328433/772868) for a general way to define this. – false Sep 08 '18 at 12:37

2 Answers2

5

The origin of your 'problem' (i.e. goals order) is deeply rooted in the basic of the language.

Prolog is based on the simple and efficient strategy of chronological backtracking, to implement SLD resolution, and left recursive clauses, like anc4/2, cause an infinite recursion. Indeed, the comma operator (,)/2 stands for

evaluate the right expression only if the left expression holds

So, order of goals in a clause is actually an essential part of the program.

For your concrete case,

... , parent(Y,Z).

cannot be called if 

anc4(X,Y),

doesn't hold.

The counterpart to goals order is clauses order.

That is, the whole program has a different semantics after the clauses are exchanged:

anc4(X,Z):-
    parent(X,Z).
anc4(X,Z):-
    anc4(X,Y),
    parent(Y,Z).

To better understand the problem, I think it's worth to try this definition as well.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
CapelliC
  • 59,646
  • 5
  • 47
  • 90
1

Prolog cannot handle left recursion by default without a tabling mechanism. Only some Prolog systems support tabling and usually you need to explicitly declare which predicates are tabled.

If you're using e.g. XSB, YAP, or SWI-Prolog, try adding the following directive on top of your source file containing the definition for the anc4/2 predicate:

:- table(anc4/2).

and retry your queries. The tabling mechanism detects when a query is calling a variant (*) of itself and suspends execution of that branch until a query answer is found and tries an alternative branch (provided in your case by the second clause). If that happens, execution is resumed with that answer.

(*) Variant here means that two terms are equal upon variable renaming.

Paulo Moura
  • 18,373
  • 3
  • 23
  • 33
  • Hi, Thank you, I'm not sure I understand what is a "tabling mechanism", I just don't understand why the second term of parent is calling. – Assaf Sep 07 '18 at 09:27
  • Edited my answer with a brief/limited explanation of tabling. For a comprehensive description, see the manuals of a system supporting tabling. – Paulo Moura Sep 07 '18 at 09:56
  • @Alan, tabling is basically the implementation of memoization ( https://en.wikipedia.org/wiki/Memoization ) in Prolog systems for efficiency. – coder Sep 07 '18 at 13:41
  • 1
    @coder: actually, tabling isn't so easy as it sounds from your comment. While it has some convenience, implementing it required (I think) months to one of the top of the world SW engineer, with a deep understanding of what is going on. And using it requires a lot of experience, because - like constraints - it's basically a [leaky abstraction](https://en.wikipedia.org/wiki/Leaky_abstraction) – CapelliC Sep 07 '18 at 16:55
  • @CapelliC, I totally agree I didn't referred to the complexity of achieving memoization in Prolog, the implementation is indeed a very complex think, I just explained the basic idea (e.g what is tabling) never said anything about the implementation... – coder Sep 07 '18 at 19:28
  • @CapelliC: What is leaking in constraints? – false Sep 08 '18 at 12:39
  • @false: generally the control flow. Nothing warns a naive user about (mis)using standard Prolog constructs... Maybe it's such kind of lacking integration that led to development of Minizinc. A whole new language with limited scope on purpose of constraints modelling. – CapelliC Sep 08 '18 at 12:53