lm03_cif@uhura.cc.rochester.edu (Larry Moss) (02/15/90)
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 -- lm03_cif@uhura.cc.rochester.edu / CLARKE'S THIRD LAW: lmo3_ss@db1.cc.rochester.edu / Any sufficiently advanced technology is lmo3_ss@uordbv.bitnet / indistinguishable from magic.
ok@goanna.oz.au (Richard O'keefe) (02/15/90)
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.]