ok@quintus (Richard A. O'Keefe) (07/02/88)
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.