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