help novice prolog users
Author Message
help novice prolog users

I've revcently been woriking with sbprolog and the Turbo Prolog manuals
for reference so I'm running into some problems.  The manuals are borowed
and I have much more access to the system with sbprolog than an IBM PC.
I can sayu fairly confidently that I know the language but don't know how
to use it.

Here are the problems -

I have a database that looks like the following.
-

child(X, Y) :- parent(Y, X).

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

-

1. If I use a statement like "descend(son, grandad)" it works fine, but
if I want to list all of the descendants found in a database like in
"descend(X,grandad)", it never terminates.  I can put a cut in the line
"descend(X, Y) :- parent(Y, X), !." and have it terminate but it will
terminate after the first match.  Is there a way for me to write this so
I can get a compete list of all of the descendants of a particular person
and still have it terminate?

2. I also want to add the line
parent(X,Y) :- child(Y,X).

but I have
child(X, Y) :- parent(Y, X).

this would cause infinite recursion.  Is there a correct way for me to
do this?

=============

second problem
-
hanoi(N) :- move(N, left, middle, right).

move(1, A, _, C) :- inform(A, C), !.
move(N, A, B, C) :-
N1 = N - 1, move(N1, A, C, B), inform(A, C), move(N1, B, A, C).

inform(Loc1, Loc2) :-
write(Loc1), tab(5), write(Loc2), nl.
-

This comes directly out of the Turbo Prolog manual.  I assume it works
with Turbo Prolog, but I haven't had the opportunity to try it.  It will
solve hanoi(1), but anything greater than that just puts a nice big core
in my directory.  What can I do to make this work in sbprolog?

Larry
--

Mon, 03 Aug 1992 03:57:03 GMT
help novice prolog users

Quote:

> I've revcently been woriking with SB Prolog and the Turbo Prolog manuals
> for reference so I'm running into some problems.

I'm sure you are:  SB Prolog and Turbo Prolog are very different.
(Well, that's not fair.  *Turbo* Prolog is very different.)

Quote:
> I have a database that looks like the following.

I do hope not!  That would mean that 'son' was a product of brother-sister
{*filter*}...

Quote:
> child(X, Y) :- parent(Y, X).
> descend(X, Y) :- parent(Y, X).
> descend(X, Y) :-  descend(X, Z), parent(Y, Z).

A general point of style:  it is a good idea to reserve verb phrases
for naming commands; for a pure predicate like this you should use a
noun phrase, such as "descendant".

What you have here is an example of "left recursion", which is bad
news for top-down left-to-right processors of any kind.  Any good
book on compilers or parsing should have an index entry for "left
recursion" and what to do about it.

Allow me the luxury of renaming the predicate:
descendant(X, Y) :- parent(Y, X).
descendant(X, Y) :- descendant(X, Z), parent(Y, Z).
Suppose you call
the first clause will look for
and find nobody, so the second clause will be tried:
^^^^^^^^^^^^^^^^^^^
but this is right back where we started.  The significant point is
that (apart from variable names) it is exactly the SAME goal.

The standard technique here is to turn LEFT recursion into RIGHT
recursion.  If you think of the rules for descendant and parent
as talking about boolean matrices, you see that
descendant = parent + descendant.parent
which has minimal solution
+
descendant = parent               +
Now we can factor the transitive closure m  of a matrix as either
+                                +
m + m .m (left recursion)  or  m + m.m  (right recursion)
So we can express descendant/2 as

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

or even as
descendant(X, Y) :-     % X is a descendant of Y
parent(Z, X),
( Z = Y ; descendant(Z, Y) ).

which is a straightforward depth-first search starting from X and
looking for Y.

What happens if we know Y and want to find X?  Will that cause any
problem?  Well, let's consider
?- descendant(Who, abraham)
this turns into
?- parent(Z, Who), (Z = abraham ; descendant(Z, abraham))
and solving the parent/2 subgoal might give us Z=tom, Who=sally
leaving the goal
?- (tom = abraham ; descendant(tom, abraham)
which reduces to
?- descendant(tom, abraham)
This _is_ a recusion, but it isn't the deadly kind;
descendant(tom, abraham) is not the same as descendant(Who, abraham).

So you should be able to use this (right-recursive) version of
descendant/2 in any data base where the parent/2 relation is finite
and not cyclic.

Quote:
> 2. I also want to add the line
>    parent(X,Y) :- child(Y,X).
>    but I have
>    child(X, Y) :- parent(Y, X).
>    this would cause infinite recursion.  Is there a correct way for me to
> do this?

Yes.  DON'T.  Define one of the two relations (say parent/2) without
reference to the other.  That's not hard, because anywhere that your
rules for parent/2 _would_ have contained the goal child(P,Q) you
know from your own intention that the two predicates should be
equivalent that you can replace child(P,Q) by parent(Q,P).  Having
defined parent/2 without reference to child/2, then just add your
rule
child(X, Y) :- parent(Y, X).

Quote:
> hanoi(N) :- move(N, left, middle, right).
> move(1, A, _, C) :- inform(A, C), !.
> move(N, A, B, C) :-
>    N1 = N - 1, move(N1, A, C, B), inform(A, C), move(N1, B, A, C).
> inform(Loc1, Loc2) :-
>    write(Loc1), tab(5), write(Loc2), nl.

Your problem here is that Stony Brook Prolog is pretty close to the
de facto standard (so you could, and *should*, read "Programming in
Prolog" by Clocksin & Mellish and "The Art of Prolog" by Sterling &
Shapiro, and expect that what you read there WILL apply to SB Prolog)
but that Turbo Prolog has far more differences than are justifiable.
In particular, Turbo Prolog uses '=' to cause arithmetic evaluation,
while other Prologs use 'is' for that and keep '=' for syntactic
unification.  Thus
N1 = N-1
means "subtract 1 from the value of N and bind N1 to the result"
in Turbo Prolog, while in every other Prolog it means "make the
unevaluated TREE -(N,1) and unify N1 with that".  So if you start
out calling hanoi(2) in SB Prolog, the sequence of calls to move/4
will look like
move(2, ...)
move(-(2,1), ...)
move(-(-(2,1),1), ...)
move(-(-(-(2,1),1),1), ...)
...

In Stony Brook Prolog it suffices to write

move(N, A, B, C) :- N =:= 1,
inform(A, C).
move(N, A, B, C) :- N  >  1,
M is N-1,
move(M, A, C, B),
inform(A, C),
move(M, B, A, C).

because the Stony Brook compiler is smart enough to realise that the
second clause is irrelevant if the N =:= 1 test succeeds without you
having to put a cut there to tell it.  In other Prologs, you should
write
move(1, A, _, C) :- !,
inform(A, C).
move(N, A, B, C) :-
M is N-1,
move(M, A, C, B),
inform(A, C),
move(M, B, A, C).
which would work in SB Prolog as well.  It would be a mistake to put
the cut *after* the call to inform/2, even in Turbo Prolog.

Basically, you have to make up your mind whether you are interested
in using Prolog or Turbo Prolog.  If you are interested in using Prolog,
there are several Prologs for the PC.  Applied Logic Systems have a PC
Prolog which is not very expensive, sticks close to the de facto standard,
and is supposed to be rather fast.  There are also Arity/Prolog and LPA
Prolog Professional, and something called A.D.A. Prolog which I haven't
tried.

[This is going in the "Ask Dr Strabismus" file.]

Mon, 03 Aug 1992 12:10:16 GMT

 Page 1 of 1 [ 2 post ]

Relevant Pages