Path: utzoo!attcan!uunet!husc6!mailrus!ames!decwrl!sun!quintus!ok From: ok@quintus (Richard A. O'Keefe) Newsgroups: comp.lang.prolog Subject: "Knowledge Systems in Prolog", more examples Message-ID: <151@quintus.UUCP> Date: 2 Jul 88 00:30:15 GMT Sender: news@quintus.UUCP Reply-To: ok@quintus (Richard A. O'Keefe) Organization: Quintus Computer Systems, Inc. Lines: 170 Well, I've read more of the Walker, McCord, Sowa, & Wilson book, and while I still say that there is some good advice in it, there are one or two things it would pay you *NOT* to imitate. (1) Wrappers. On pp 34-35, we are told that the Pascal declaration type person = record name : string; address : string; date_of_birth : array [1..3] of integer; sex : boolean; end {record}; -- which, by the way, is not a brilliant piece of Pascal -- introduces a type instances of which have as Prolog equivalents terms of the form person(name(N), address(A), date_of_birth(D.M.Y), sex(S)) Again, on page 51 we are shown /* Prolog structure */ { Pascal record } type loc = loc( record farmer(F), farmer : string; wolf(W), wolf : string; goat(G), goat : string; cabbage(C) cabbage : string; ) end {record}; -- which, in context, is an amazingly bad piece of Pascal -- DON'T *DO* THIS! Supposing F, W, G, and C to be constants, the representation they recommand would cost 13 words in Quintus Prolog (18 words in another Prolog I know of), whereas the sum-of-products approach yields the *real* equivalent of the Pascal record as loc(Farmer, Wolf, Goat, Cabbage) at a cost of 5 words in Quintus Prolog (6 in another Prolog). That's a substantial waste of space and time, and worse still, it confuses the reader, because when you see patterns like loc(farmer(F),_,_,_) and loc(_,wolf(W),_,_) floating around, your natural assumption is that patterns like loc(wolf(W),_,_,_) and loc(_,farmer(_),_,_) may be possible, for why else would anyone have unary wrappers if not to distinguish such cases? (2) Over-use of "." At least in chapter 2, the book has an excessive fondness for ".". Consider the birth_date(Day.Month.Year) example above. This would be better as date(Year,Month,Day) --when, amongst other advantages, it will sort properly-- at a space cost of 4 cells, which is admittedly the same as the cost of Day.Month.Year. The big advantage here is that all things made out of dots look alike, so it is very hard for a human reader to tell D.M.Y from any other X.Y.X, but date(Y,M,D) proclaims its nature to the world. On page 55, this book actually _recommends_ X.Y, X.Y.Z and the like, so this was not an accidental slip but a matter of policy. The authors have finally cured me of my lingering fondness for infix dot. I am now thoroughly convinced that bracket notation is to be preferred. Perhaps if I had been reading Lee Naish's code I might have been swayed the other way, but I fear that he may not be typical. (3) Factorial On page 36 they present the following code: factorial(0,1). factorial(N,X) <- lt(N,0) & write('Negative input to factorial'). factorial(N,X) <- (M := N - 1) & factorial(M,Y) & (X := N * Y). {Note: * in VM/Prolog is usually an anonymous variable, but not here.} What's wrong with this? Well, according to this, factorial(-1, 472) is true. {For the benefit of those fortunate enough not to have VM/Prolog, try factorial(0, 1). factorial(N, X) :- N < 0, write('Negative input to factorial.'), nl. factorial(N, X) :- M is N-1, factorial(M, Y), X is N*Y. } For real fun, try factorial(1, 2). If you are going to print an error message like this, you should at least have the decency to fail. So the second clause would have been better as factorial(N, *) <- lt(N,0) & write('Negative input to factorial') & / & fail. (4) (falsely so-called) "quick" sort Section 2.4.1 (p89) starts out admirably, saying that "The choice of algorithm is the most important factor in determining performance". But the example they consider is sorting, and they say "Three different algorithms might be considered: - a permutation sort that tries all possible permutations of a list in order to find one that is sorted - a bubble sort that interchanges pairs of elements until the result is sorted - a version of Quicksort ..." I am really getting thoroughly sick of "quick" sort. Remember, if you check the fine print in Knuth, Sedgewick, Melhorn, or any good book on the subject, you will find that the average case of "quick" sort does about 1.4 times as many comparisons as the WORST case of merge sort. If people are going to presume to give advice about sorting, they might at least check the standard literature. (Not that sorting is a major topic in Walker et al, but it wasn't a major topic in Clocksin&Mellish either, and that didn't stop people mistaking the difference-list example for advice about how to sort.) (5) Breadth-first search. On pp 82-83 we find breadth_first(Goal, Histories, Answer) <- member(Goal.Past, Histories) & reverse(Goal.Past, Answer). breadth_first(Goal, Histories, Answer) <- Histories=(*,*) & set_of(Next.Current.Past, member(Current.Past, Histories) & move(Current,Next) & \member(Next,Past), New_history_list) & remove_duplicate_head(New_history_list, Clean_list) & breadth_first(Goal, Clean_list, Answer). remove_duplicate_head(F.S.Tail, Clean) <- ((F=(Head.*) & S=(Head.*)) -> remove_duplicate_head(F.Tail,Clean); (remove_duplicate_head(S.Tail,L) & Clean=(F.L))). remove_duplicate_head(F.nil, F.nil). remove_duplicate_head(nil, nil). Let's start with remove_duplicate_head. The input is a list of lists, which is sorted, and subsequences ...,[A|T1],...,[A|Tn],... with the same head (A) are to be replaced by the first member of the subsequence (here [A|T1]). Can we do this more cleanly? remove_duplicate_heads([], []). remove_duplicate_heads([[Tag|Info]|Given], [[Tag|Info]|Clean]) :- skip_duplicate_heads(Given, Tag, Clean). skip_duplicate_heads([[Tag|_]|Given], Tag, Clean) :- !, skip_duplicate_heads(Given, Tag, Clean). skip_duplicate_heads(Given, _, Clean) :- remove_duplicate_heads(Given, Clean). In Quintus Prolog, the cleaner version is about three times faster. I think the test \member(Next, Past) might perhaps be better as \member(Next, Current.Past), in case the problem graph has self-loops. If you are given a generation function which yields all of the children of a node at once instead of a move/2 which enumerates them, you can write breadth first search without appealing to set_of/3 at all. {The predicate called set_of/3 in this book corresponds to the predicate called set_of_all/3 in the Quintus library, not to the predicate called set_of/3, except that set_of_all/3 checks that it is being called soundly, and set_of/3 in this book doesn't.} Reminder: In this note I've concentrated on some of the infelicities in the book. I repeat that there is a lot of good stuff in it, and on the whole I do not regret its purchase.