How to express a transitive relationship

Question

I want to express a transitive relationship. If A references B and B references C then A references C. I have this:

proj(A).
proj(B).
proj(C).
ref(A,B).
ref(B,C).

When I query using proj(A) I obtain:

[46] ?-proj(A).
A = _639

What does "_639" mean? I expected a yes or no and got that strangeness. I need to add a rule to say:

ref(A,C). and get YES. Ideally, if possible, I would like to show how this relationship came about: (A => B => C).

`_639` is an uninstantiated, anonymous variable. Your "facts" have variables rather than atoms. You probably wanted lower case (atoms), so `proj(a)` and `proj(b)`, etc. Otherwise, if you query, `proj(X)`, you'll get `X = `. The simplest way in Prolog to express `if p1 and p2 then p3` in this case is, `p3 :- p1, p2`, or more specifically, the rule `ref(A, C) :- ref(A, B), ref(B, A).`. You'll just need to watch for circular references depending upon your context. Then if you have `ref(a,b).` and `ref(b,c)`, querying `ref(a,c)` will be true because the rule says so. :) — lurker, Feb 19 '15 at 19:28
@lurker Thanks that is very helpful! This looks right. Can you explain why "ref(a,d)." is giving me success though? — P.Brian.Mackey, Feb 19 '15 at 19:36
Because your facts use variables. `ref(A,B)` says `ref(A,B)` is true for any values of `A` and `B`. You need to use atoms. So `ref(a,b).` and `ref(b,c).` which use specific values. Get rid of `ref(A,B)` and `ref(B,C)`. Then `ref(a,d)`. should fail. — lurker, Feb 19 '15 at 19:39
@IsmaelAbreu - I edited the question to show that I changed my variables to atoms. I'm still having an issue. — P.Brian.Mackey, Feb 19 '15 at 19:44
The question no longer makes sense. If you have all of the facts stated as shown (and no others), then the query `proj(A).` should not result in `A = _639`. If you want to show how a rule performed, you can either add another argument to the rule which collects information along the way, or do `write(...)` along the way in the rule. — lurker, Feb 19 '15 at 19:47
@lurker - You are right. I'm going to undo the edit. If you post the first comment you made as the answer I will choose it cause you really did get me to the next step. I'm probably doing some newbie dumb thing that I just haven't figured out yet. — P.Brian.Mackey, Feb 19 '15 at 19:49
Sounds like a deal. :) You're finding your way through some common first-timer issues. I recommend a good book (like, *The Art of Prolog* by Sterling & Shapiro, or *Programming In Prolog* by Clocksin & Mellish, which is not as "deep"). — lurker, Feb 19 '15 at 19:51
Btw the textbook example of this is usually reachability in graphs (which is the transitive closure on the edge relation). Another variant is decendants in a genealogy tree - there you (should) have no cycles, so the problem is a bit easier. — lambda.xy.x, Feb 20 '15 at 15:38

lurker · Accepted Answer · 2015-02-20T16:16:01.970

11

The _639 is an uninstantiated, anonymous variable. Your "facts" have variables rather than atoms. For example:

proj(A).   % This has a variable A and means "any A is a project"

So if I query:

:- proj(X).
X = _blah    % anonymous variable: anything is a project!

You need atoms:

proj(a).
proj(b).

Which results in the query:

:- proj(X).
X = a ;
X = b

If you have:

ref(a,b).
ref(b,c).

Then, the simplest way in Prolog to express a transitive property is by declaring a rule (or what's known as a predicate in Prolog):

ref(A,C) :- ref(A,B), ref(B,C).

This says that, ref(A,C) is true if ref(A,B) is true, AND ref(B,C) is true.. Running the query:

:- ref(a,c).
true ;
Out of stack

Or:

:- ref(a,X).
X = b ;
X = c ;
Out of stack

So it sounds logical but has an issue: you can get into a loop due to the self-reference. A simple way around that is to make the rule name different than the fact:

refx(A, B) :- ref(A, B).
refx(A, C) :- ref(A, B), refx(B, C).

Now if I query:

:- refx(a, b).
true ;
no

:- refx(a, c).
yes

:- refx(a, X).
X = b ;
X = c
yes

Etc.

There are still cases where this could have termination issues, however, if the facts contain reflexive or commutative relationships. For example:

ref(a,b).
ref(b,a).
ref(b,c).

In this case, a query to refx(a, b) yields:

| ?- refx(a, b).
true ? ;
true ? ;
true ? ;
...

As @lambda.xy.x points out, this could be resolved by tracking where we've been and avoiding repeat "visits":

refx(X, Y) :-
    refx(X, Y, []).

refx(X, Y, A) :-
    ref(X, Y),
    \+ memberchk((X, Y), A).   % Make sure we haven't visited this case
refx(X, Y, A) :-
    ref(X, Z),
    \+ memberchk((X, Z), A),   % Make sure we haven't visited this case
    refx(Z, Y, [(X,Z)|A]).

Now we terminate with refx(a,b) and succeed once:

| ?- refx(a,b).
true ? ;
no
| ?-

And refx(X, Y) produces all of the solutions (albeit, some repeats due to succeeding more than once):

| ?- refx(X, Y).

X = a
Y = b ? ;

X = b
Y = a ? ;

X = b
Y = c ? ;

X = a
Y = a ? ;

X = a
Y = c ? ;

X = b
Y = b ? ;

X = b
Y = c ? ;

(2 ms) no

edited Feb 20 '15 at 16:16

answered Feb 19 '15 at 19:56

lurker

56,987
9
69
103

1

It seems the second rule body is missing a refx. Otherwise, if you add a fact ref(c,d). then then query refx(a,d) will fail. I think it makes sense to mention that you only remove non-termination which comes from cycles of length 0. If you add the fact ref(b,a), the query refx(a,c) will still fail. The standard way to exclude arbitrary cycles is to have an additional parameter which accumulates all visited nodes in a list. An element of ref is then only added (and followed), if it is not present in the list. – lambda.xy.x Feb 20 '15 at 09:03
@lambda.xy.x yes indeed, good catch. Thanks. I did consider the extra "accumulated nodes" argument but was trying to keep it simple for this particular example. – lurker Feb 20 '15 at 10:11
@lambda.xy.x - Thank you!! Now everything works wonderfully. You too lurker, great answer and thank you for being so thorough. – P.Brian.Mackey Feb 20 '15 at 14:51
@P.Brian.Mackey I updated the transitive `refx/2` accordingly. – lurker Feb 20 '15 at 14:58
`refx(A, C) :- ref(A, B), refx(B, C).` gave me an overflow error. However, `refx(A, C) :- ref(A, B), ref(B, C).` worked for me. – P.Brian.Mackey Feb 20 '15 at 15:12
1

@P.Brian.Mackey When you use `refx(A, C) :- ref(A, B), refx(B, C)` the non-termination comes from a cycle in the ref relation. Then prolog derives transitivity chains `a - b - a - ...` of arbitrary length. This also depends on the order your facts are defined and on your query: – lambda.xy.x Feb 20 '15 at 15:26
1

@P.Brian.Mackey (sorry hit enter too soon) suppose the facts are `ref(a,b). ref(b,a). ref(a,c)` then the query `refx(a,c)` will not terminate, since the loop occurs before the first solution. putting `ref(b,a)` to the end will show you infinite derivations of the fact. The reason is the order in which the goals are processed (left-to-right, depth-first search). -- the `refx(A, C) :- ref(A, B), ref(B, C).` solution always terminates, but is incomplete. – lambda.xy.x Feb 20 '15 at 15:32
In my case I want the program to fail if we have a circular reference. So if I have two facts: `ref(a,b). ref(b,a).` kaboom is good :). I'm having some trouble keeping up with you guys! But, so far this simple way works. I'm sure this will change as I learn more. – P.Brian.Mackey Feb 20 '15 at 16:53
@P.Brian.Mackey well.... "kaboom" is never really good. ;) Perhaps a "fail" in this case would be more appropriate. :) – lurker Feb 20 '15 at 16:55

How to express a transitive relationship

1 Answers1

Linked