Prolog - Tracing with out using trace?

Author

Tracing with out using trace?

Bruce Horrocks

2006-09-02, 6:59 pm

Background:
A friend wanted something that would help him graphically illustrate
relationships between people - your typical "friend of a friend's wife's
mother" type thing.

I suggested using Prolog to store and analyse the relationships and
GraphViz [1] to draw them. I dredged my memory, having studied Prolog
briefly at college decades ago, and produced an example program to give
him an idea of the kind of thing that is possible.[2]

An extract from the program is:

parent( homer, bart).
parent( gramps, homer).
married( homer, marge).
grandparent(X, Y) :-
parent(X, _someone),
parent(_someone, Y).

Problem:
If I ask the program to draw the grandparent relationship then I get a
direct link gramps-->bart, which is great but it doesn't show how the
relationship was arrived at. It should be possible to illustrate this by
highlighting gramps-->homer-->bart.

I don't want to do this by editing the definition of grandparent, if I
can help it, because I want my friend to be able to specify his own
rules without having to worry about my drawing bit.

So, another way might be to trace the execution of grandparent and
output drawing statements for each of the component relationships as
they are resolved. I have a vague memory of having written something
like a "trace program in prolog" at college but cannot now remember how.
So...

The question:
How do I write a trace program in Prolog that would allow me to "get at"
each part of the clause body?

Thanks in advance.

Oh, and suggestions for all-singing, all-dancing graphical relationship
analysis packages, preferably free, that can be passed onto my friend
are also welcome!

[1] http://www.graphviz.org
[2] http://www.horrocks.plus.com/downlo...lationships.pdf
--
Bruce Horrocks
Surrey
England
<firstname>@<surname>.plus.com -- fix the obvious for email

Markus Triska

2006-09-02, 6:59 pm

Bruce Horrocks <news@horrocks.plus.com> writes:

> I want my friend to be able to specify his own rules without having
> to worry about my drawing bit.

What about :

grandparent([Grandparent,Parent,Child]) :-
parent(Grandparent, Parent),
parent(Parent, Child).

Yielding:

?- grandparent(Ls).

Ls = [gramps, homer, bart] ;

and generalising the drawing bit to handle such extended relations
represented as lists? You can keep the old rule as well and use it to
draw the corresponding binary relation.

All the best,
-- Markus Triska

Bruce Horrocks

2006-09-03, 7:58 am

Markus Triska wrote:

> What about :
>
> grandparent([Grandparent,Parent,Child]) :-
> parent(Grandparent, Parent),
> parent(Parent, Child).
>
> Yielding:
>
> ?- grandparent(Ls).
>
> Ls = [gramps, homer, bart] ;
>
> and generalising the drawing bit to handle such extended relations
> represented as lists? You can keep the old rule as well and use it to
> draw the corresponding binary relation.

That would work for a specific degree of relationship. Suppose though
that I wished to define a rule "is_related_to". Distant cousins of
varying degrees will have a variable number of names in the result list
which could not necessarily be tied back to the right relationship.

Or friend-of-friend where there could be any number of connections
before getting to a final person?

Regards,

--
Bruce Horrocks
Surrey
England
<firstname>@<surname>.plus.com -- fix the obvious for email

Markus Triska

2006-09-03, 7:58 am

Bruce Horrocks <news@horrocks.plus.com> writes:

> Or friend-of-friend where there could be any number of connections
> before getting to a final person?

What about it? A list can hold any number of connections. Example
fact base and rules for (transitive) friend-of-friend:

friend(mary, harry).
friend(harry, sally).
friend(sally, garry).
friend(harry, mary).
friend(garry, sally).

friend_of_a_friend([A,B|Rest]) :-
friend(A, B),
friend_of_a_friend(B, Rest, [A,B]).

friend_of_a_friend(A, [B], Visited) :-
friend(A, B),
\+ memberchk(B, Visited).
friend_of_a_friend(A, [B|Rest], Visited) :-
friend(A, B),
\+ memberchk(B, Visited),
friend_of_a_friend(B, Rest, [B|Visited]).

Yielding:

?- friend_of_a_friend(Fs).

Fs = [mary, harry, sally] ;

Fs = [mary, harry, sally, garry] ;

Fs = [harry, sally, garry] ;

It's easy to derive the corresponding binary relation.

All the best,
-- Markus Triska

Bruce Horrocks

2006-09-03, 7:58 am

Markus Triska wrote:

> It's easy to derive the corresponding binary relation.

That wasn't a good example by me. Suppose the relationships are son_of
and daughter_of, e.g.

son_of(homer, bart).
daughter_of(homer, lisa).
daughter_of(homer, maggie).

Now suppose I try to identify siblings by rule:

sibling([P, X, Y]) :-
son_of(P, X),
son_of(P, Y),
X \== Y.

sibling([P, X, Y]) :-
daughter_of(P, X),
daughter_of(P, Y),
X \== Y.

sibling([P, X, Y]) :-
son_of(P, X),
daughter_of(P, Y).

sibling([P, X, Y]) :-
daughter_of(P, X),
son_of(P, Y).

Not very elegant, I realise, but the print procedure does not know
whether to label the P-->X line on the graph with "son_of" or
"daughter_of" as they could be in either order.

Again, I realise that this can be coded around but I was hoping to avoid
putting such restrictions on the user created rules by being able to
duplicate trace and so "know" which link is being followed.

Does this make it clearer?

Regards,
--
Bruce Horrocks
Surrey
England
<firstname>@<surname>.plus.com -- fix the obvious for email

Markus Triska

2006-09-03, 6:59 pm

Bruce Horrocks <news@horrocks.plus.com> writes:

> Not very elegant, I realise, but the print procedure does not know
> whether to label the P-->X line on the graph with "son_of" or
> "daughter_of" as they could be in either order.

As a way to tell the print procedure what label we want, we can make
the needed information explicit by a term

label([Node1,Node2,Node3,...],Caption)

Users could write the first two clauses of your example (by the way,
"parent_of" implies argument order "parent, followed by child" -- you
can rename to parent_child or child_parent for clarity):

sibling([label([P,X],son_of), label([P,Y],son_of), label([X,Y],sibling)]) :-
son_of(P, X),
son_of(P, Y),
X \== Y.

sibling([label([P,X],daughter_of), label([P,Y],daughter_of), label([X,Y],sibling)]) :-
daughter_of(P, X),
daughter_of(P, Y),
X \== Y.

Yielding:
?- sibling(Ss).

Ss = [label([homer, lisa], daughter_of), label([homer, maggie], daughter_of), label([lisa, maggie], sibling)] ;

Ss = [label([homer, maggie], daughter_of), label([homer, lisa], daughter_of), label([maggie, lisa], sibling)] ;

The backend would be generalised to handle such terms.

> avoid putting such restrictions on the user created rules by being
> able to duplicate trace and so "know" which link is being followed.

All we have done so far is offering *more features*, i.e., ways of
specifying relations to the backend. Deriving labels from predicate
names is *restricting* the user in names and structure of predicates
(what about auxiliary predicates that *shouldn't* be part of the
graph?), while potentially allowing for more concise rules. In the
version described above, users encode arc labels explicitly and are
free to name their predicates as they want; they also have the full
power of Prolog available to describe any relation they want, and
derived relations are independent from how they are found. You only
need to think about what kinds of terms the drawing routine should be
able to handle, and user-supplied rules should generate (only) these
terms. You can give users access to all features of GraphViz if you
design the interface well. If common patterns arise, you can introduce
special constructs (for example: transitive closures, relation
subsumptions, ...) that a meta-interpreter can handle specially.

Extending a meta-interpreter to keep track of inferences can only help
to make implicit what would otherwise have to be explicit in
user-supplied rules. It *won't* give users more power (in terms of
what kinds of relations they can describe) than they already have by
using plain Prolog as extension language in combination with a
well-defined interface to the backend..

All the best,
-- Markus Triska

Bruce Horrocks

2006-09-05, 7:00 pm

Markus Triska wrote:
[snip]

> Extending a meta-interpreter to keep track of inferences can only help
> to make implicit what would otherwise have to be explicit in
I think you've hit a nail on the head here as I was wanting to separate
the drawing aspects from the logic of identifying relationships. Being
explicit about how to draw new relationships as part of the logic that
finds the new relationship is probably better.

I'll give your suggestions a go and see how it turns out.

Thanks.

--
Bruce Horrocks
Surrey
England
<firstname>@<surname>.plus.com -- fix the obvious for email

Sponsored Links