Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!mips!apple!uokmax!munnari.oz.au!goanna!ok From: ok@goanna.oz.au (Richard O'keefe) Newsgroups: comp.lang.prolog Subject: Re: help novice prolog users Keywords: sbprolog, Turbo Prolog Message-ID: <2870@goanna.oz.au> Date: 15 Feb 90 04:10:16 GMT References: <5249@ur-cc.UUCP> Organization: Comp Sci, RMIT, Melbourne, Australia Lines: 162 In article <5249@ur-cc.UUCP>, lm03_cif@uhura.cc.rochester.edu (Larry Moss) writes: > 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.) > 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 incest... > 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. > 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). > 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.]