Transitive relation results in error : Out of local stack

Hello.
I've tried implementing a transitive relation "inherits_from". But my code
causes an error: Out of local stack.

--- The code: ---

instance_of(X,Z) :- instance_of(X,Y), inherits_from(Y,Z).
instance_of(ob1,cl1).

inherits_from(X,Z) :- inherits_from(X,Y), inherits_from(Y,Z). /* indicates
that inherits_from is a transitional relation */
inherits_from(X,Z) :- inherits_directly_from(X,Z). /* indicates that
inherits_from is a transitional relation */
inherits_directly_from(cl1, cl2).
inherits_directly_from(cl2, cl3).
inherits_directly_from(cl3, cl4).

?- inherits_from(cl1,cl4).
?- instance_of(ob1,cl4).

--- end code ---

My question is: what is the "proper way" to use transitive relations in
Prolog? How to avoid the "stack overflow" and the endless "loop" ?
I've googled a bit but didn't find answer. Some search results were
promising but the links turned out to be broken.

TIA
/KDP

> instance_of(X,Z) :- instance_of(X,Y), inherits_from(Y,Z).
> instance_of(ob1,cl1).

You should put the termination predicates first (before the recursive
ones, otherwise you enter in infinite loops. For example the first
relation becomes:
instance_of(ob1,cl1).
instance_of(X,Z) :- instance_of(X,Y), inherits_from(Y,Z).
You should do the same for the other relation.
Paul Fodor.

On Sep 6, 6:30 pm, raven <qs-ra...@wp.remove.this.please.pl> wrote:
> Hello.
> I've tried implementing a transitive relation "inherits_from". But my code
> causes an error: Out of local stack.
>
> --- The code: ---
>
> instance_of(X,Z) :- instance_of(X,Y), inherits_from(Y,Z).
> instance_of(ob1,cl1).
>
> inherits_from(X,Z) :- inherits_from(X,Y), inherits_from(Y,Z). /* indicates
> that inherits_from is a transitional relation */
> inherits_from(X,Z) :- inherits_directly_from(X,Z). /* indicates that
> inherits_from is a transitional relation */
> inherits_directly_from(cl1, cl2).
> inherits_directly_from(cl2, cl3).
> inherits_directly_from(cl3, cl4).
>
> ?- inherits_from(cl1,cl4).
> ?- instance_of(ob1,cl4).
>
> --- end code ---
>
> My question is: what is the "proper way" to use transitive relations in
> Prolog? How to avoid the "stack overflow" and the endless "loop" ?
> I've googled a bit but didn't find answer. Some search results were
> promising but the links turned out to be broken.
>
> TIA
> /KDP

On Sep 6, 7:33 pm, "fodor.p...@gmail.com" <fodor.p...@gmail.com>
wrote: 
>
> You should put the termination predicates first (before the recursive
> ones, otherwise you enter in infinite loops. For example the first
> relation becomes:
> instance_of(ob1,cl1).
> instance_of(X,Z) :- instance_of(X,Y), inherits_from(Y,Z).
> You should do the same for the other relation.
> Paul Fodor.
>
> On Sep 6, 6:30 pm, raven <qs-ra...@wp.remove.this.please.pl> wrote:
> 
> 
> 
> 
> 
> 
> 
> 

Paul's suggestion is a good one (termination criteria first),
and with a bit of tweaking it can suffice for the immediate
application.  However in general the problem of finding the
transitive closure (or finding connected components of graphs)
requires additional machinery to avoid looping.

Here if we assume the hierarchy of (object?) inheritance is
a finite strict partial order, the following will always give
an answer, success or failure:

inherits_from(X,Z) :- inherits_directly_from(X,Z), !.

inherits_from(X,Z) :- inherits_directly_from(X,Y),
inherits_from(Y,Z).

/* sample immediate inheritance data */

inherits_directly_from(cl1, cl2).
inherits_directly_from(cl2, cl3).
inherits_directly_from(cl3, cl4).

Note that raven's original rule:

inherits_from(X,Z) :- inherits_from(X,Y),
inherits_from(Y,Z).

is hydra-like, in that the "head" divides into two
more invocations of itself, the first of which has
its second argument free.  Even if the order of the
clauses were switched as Paul suggests, this would
still cause infinite recursion/stack overflow.

When the underlying graph contains loops, we need
to impose more structure in order guarantee the
computation will finish.  One way to do this is
to keep track of the minimal "steps" needed to
reach one node from another and avoid revisiting
nodes that one has already reached.

Let me know if you need more info about the "proper"
way to code for transitive closure in the more
general setting.

regards, chip