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.
 -

parent(grandad, dad).
parent(dad, son).
child(mom, grandad).

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?

Thanks in advance,
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.
> parent(grandad, dad).
> parent(dad, son).
> child(mom, grandad).

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
        ?- descendant(adam, Who)
the first clause will look for
        ?- parent(Who, adam)
and find nobody, so the second clause will be tried:
        ?- descendant(adam, X), parent(Who, X)
           ^^^^^^^^^^^^^^^^^^^
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  
 
 [ 2 post ] 

 Relevant Pages 

1. help with locator I'm a cw5 novice user

2. Help, very novice users!

3. Help - I am a novice tcl/tk user...

4. Novice needs HELP for two PROLOG questions

5. Novice LabView user query - LONG

6. novice scheme user

7. Novice PHP User: Very basic problem with IIS

8. Novice user ot LISP

9. Novice Tk user on SCO

10. novice question on programming with prolog.

11. novice question on prolog

12. Novice writing a Prolog interpreter

 

 
Powered by phpBB® Forum Software