Programming in Prolog. Using the ISO Standard. by William F. Clocksin , Christopher S. Mellish, Springer-Verlag, 2003, ISBN 3-540-00678-8, xiii + 299 pages.
This is the fifth and most recent edition of a legendary book whose first edition dates from 1981. It was probably the first introductory Prolog book and it still is the most gentle introduction to Prolog for everyone, including non-computer scientists. The authors make indeed very little assumptions on the computer science knowledge of the reader and not even on her programming skills. Still, the book covers most of the Prolog language.
The first edition was based on the de facto Edinburgh Prolog standard. Obviously, with the appearance of the ISO Prolog Standard, a new edition of the book needed to adapt to ISO, and that is the reason for the subtitle Using the ISO Standard. Other changes were introduced as well and this review mentions some of the differences, but mainly concentrates on the current contents, independent of the history involved.
The Preface of the book sketches the rationale behind the book and the new edition. It also lists in a table differences between the new and the old editions related to switching from the de facto standard to ISO. These differences are related to syntax and built-in predicates. There are surprisingly few differences and they are small.
The book consists of eleven chapters
The first chapter in any book on Prolog is the most difficult one: how to introduce gradually a whole bunch of connected concepts (and terminology) without getting sidetracked or forgetting certain essentials. The authors do a very good job here: after general remarks about objects and relationships, and the nature of programming, (ground) Prolog facts are introduced as a means to model the knowledge contained in simple English sentences. This is followed immediately by showing how such facts can be queried. Newbie questions in comp.lang.prolog show that at this point, the book would benefit from an explicit statement that facts like likes(john,mary). are not in the Prolog database at startup (and refer to the relevant section in the book). This chapter next discusses variables, conjunctions (in queries), a first example where backtracking happens, and rules. At the end of this chapter, the reader is familiar with datalog. A set of exercises concludes this chapter.
Chapter 2 starts by taking a closer look at the syntax of terms and
clauses. There is a lot of fine-print in Prolog syntax, but most
programmers never need to know it, so the book justifiably does not go
into all the details. That it does not mention the ISO syntax for
character codes (like 0'a for the ASCII 97), seems however a more
serious oversight, especially in view of the footnote on page 229
which suggests that the notation "a" for [97] should be used in some
implementations: "a" is legal syntax but its meaning is not defined by
ISO. Equality of terms (unification or matching) and arithmetic are
also covered explicitly at this stage. Most importantly, chapter 2
introduces diagrams with boxes containing a goal and an arrow that
illustrates the flow of control: this visualization of the execution
of Prolog is extremely helpful and is later in the book used for
explaining other concepts like backtracking, the cut and debugging. In
the first edition, these diagrams looked like a wiggly snake in a
Prolog database: the current form is much better.
Chapter 3 introduces data structures which are drawn as trees of Prolog terms and lists. The first recursive predicate now follows naturally: member/2. The chapter goes on with recursive predicates and compound data structures. At the end, we find two new sections on accumulators and difference structures.
There are two negative points about chapter 3: on page 56, the original edition contained an explanation which (rather strangely) links left-recursive rules to the order of rules. In the current edition, two code snippets were switched without adapting the text and it now makes even less sense than before. On pages 59/60, there is an albeit nice example which would have been worth reconsidering in the section on cut. Or at least in the section on cut, the reader could have been asked to reconsider the code on pages 59/60.
Chapter 4 explains in detail backtracking and the cut. Understanding
backtracking is central to programming in Prolog and the explanation
of backtracking is repeated in the context of several concrete
programming examples later in the book as well. This is nice work: it
makes use of the diagrams introduced in chapter 2, this time with nested
boxes. The cut is also explained very well and with the same diagrams.
This is also the natural place to introduce the Prolog negation
\+/1. The authors devote some space to the common uses and the
pitfalls of the cut. In particular they show that a cut should be
placed before the output unification (an issue related to
steadfastness), but too many of the example predicates in the book are not
steadfast!
Another critique related
to cuts in the programs in the book, is that there are so many of them. The
book would have gained a lot if the Prolog if-then-else construct
would have been introduced in this very same chapter, and if
subsequently a series of quite ugly programs had been cleaned up.
One more negative point: on page 89, the text seems to argue that
placing a cut in the body of the first clause (the fact) of append/3,
will increase space and time efficiency. This is not true. It is
understandable that the authors have chosen not to talk about first
argument indexing, but that does not justify wrong statements. Another
one of that kind (related to the silence about indexing) can be found
on page 146 where it is strongly suggested that Prolog must do a
linear search in a database of ground facts, even if the first
argument is instantiated.
A chapter about input and output is unavoidable in an introductory textbook on any programming language: it is never exciting and the current book makes no exception, but the example programs are OK. This chapter is adapted to the ISO standard, albeit in a minimalistic way: the authors stick to the DEC-10 see/seeing style which changes the current streams using the ISO built-ins current_input/1 and set_input/1, warning for the pitfalls, but failing to point out the more safe I/O predicates that take the stream as their first argument. At the end of this chapter, there is a list of most important ISO Prolog operators: for some reason the quoting of the operators is inconsistent and backslashes in quoted atoms were not doubled. Also, the ISO style of op/3 with a list of atoms in the third argument should have been followed. Still related to operators: on page 178 it is written that we shall have to declare a ``^'' operator; however, ``^'' is already an ISO operator. The subsequent declaration in the book gives a non-ISO precedence and associativity for ``^'' ...
Chapter 6 goes into more detail about some built-in predicates some of
which were covered already earlier in the book. To name just some new
ones: var/1 (and friends), clause/2 (and friends), the
functor/arg/univ triple, a series of predicates to transform atomic
objects to a list of characters, term comparison ...
The section on dynamic predicates should have mentioned the logical
database update view adopted by ISO Prolog. Page 132 says that the
query ?- number_chars(23,X). could deliver the result
X = ['2','3','.','0']: that is not true in ISO Prolog. The section
named Constructing Compound Goals (which deals with conjunction,
disjunction, call/1 and \+/1) should have contained the Prolog
if-then-else. The section on arithmetic lists some arithmetic
operators and concludes on page 140 with the note: ``Particular
Prolog implementations may include more arithmetic operations such as
exponentiation and trigonometric functions''. This is misleading as ISO
Prolog defines both exponentiation and a whole lot of trigonometric
functions, so every ISO Prolog must have them.
Chapter 7 contains a selection of classic programs: a sorted tree, searching in a maze, the towers of Hanoi, dealing with graphs ... Both the problems and the solution programs are nicely laid out: this chapter can be digested by a novice and contains lots of interesting stuff. It is not clear why the authors choose to introduce (the implementation of) findall/3 as an example program, instead of as an extremely useful built-in predicate. Page 147 contains a figure that was adapted from the first version and it looks nicer now, but unfortunately, cut&paste has introduced errors, and made the figure inconsistent with the text. The programs are mostly OK, but cut is used too often and inconsistently. Examples of this are on pages 148 and 165. Many of these programs would benefit from a rewrite in an if-then-else style.
Chapter 8 is about debugging Prolog programs: ISO says nothing about
it, but actual implementations do not differ much in their simple
interface to the Byrd Box Model. This model is explained very nicely
and example traces show how to use it. It includes spy-points and
leashing. This chapter contains advice on program layout (which the
book regularly does not follow), a section on Common Errors (whose
first point is wrong: there is no need to have a return after the last
dot in a program - EOF is enough), and a section on Fixing Bugs. The
update of the latter section is already 10 years overdue: one cannot
seriously describe the use of ?- [user]. (and its pitfalls) as
the main method for fixing a program, given the current user interfaces.
Definite Clause Grammars are explained in chapter 9, starting from a simple English sentence analysis. It is a classic and satisfying explanation. The section about Translating Language to Logic is particularly nice, because through DCGs it shows the relation between natural language sentences and logic formulas: this is what logic programming is about!
Chapter 10 explains how Prolog relates to (pure) Logic. A reader who just wants to have a practical grasp on Prolog could skip this chapter, but nobody should be afraid of tackling it: the authors have done a very good job starting from an explanation of Predicate Calculus, going to Clausal Form, covering Resolution and Theorem Provers, finally arriving at Horn Clauses and ending with Prolog. This chapter should be reread regularly by old Prolog programmers.
Chapter 11 lists some small and medium-sized projects to be done by the interested reader: the selection shows some of the areas Prolog is good at.
Appendix A contains the answers to selected problems: Prolog code plus
explanation. Not bad, but it should be cleaned up: indentation,
layout and cuts are the main issues. Page 269 and 270 introduce some
extra typos compared to the first edition, and it is suggested that
the notation {X} is not ISO, while it is (page 290 states it
correctly though).
Appendix B contains the code for translating a logic formula into clausal form: it follows the explanation of chapter 10, but now we see the full Prolog code.
Appendix C is about Writing Portable Standard Prolog Programs. The only sensible advice would have been to eschew anything that is not defined by the standard, and in particular the issues that ISO has left implementation dependent or implementation defined. Instead, the authors warn the reader that non-conforming implementations might exhibit non-ISO behavior, which is like the empty statement. A section which describes more clearly the differences between (say) DEC-10 Prolog and ISO Prolog would have been more helpful. The programs given in this chapter mimic ISO built-ins using predicates that were popular in the de facto standard: it seems better for the individual programmer not to use these programs.
Appendix D contains the full code for DCG translation. It is not clear why the authors wanted it in the book. Moreover the code and its comments still try to make it work in a non-ISO system: it is one of the examples of the ambiguity of the book which has not resolutely chosen for ISO.
Overall, the book is as great as ever as an introductory text
for Prolog. When a newbie asks for an introduction to Prolog, the best
advice is still Clocksin&Mellish. Leaving the ISO issue
aside, the book would benefit from correcting (sometimes newly
introduced) errors, cleaning up some programs (especially the cuts in
them) and introducing (and using) if-then-else.
People attracted by the subtitle Using the ISO Standard could feel left in the cold by the actual ISO content of the book. There are many small errors related to ISO in the book. One more example: the footnote on page 182 suggests that an implementation that limits the applicability of clause/2 to dynamic predicates, is not ISO conforming. Since dynamic predicates are public, and since an implementation can limit public predicates to the dynamic ones, it follows that this is not true. There are too many such points in the book.
The book also often fails in Using the ISO Standard in some of
its programs. As an example: the preface mentions explicitly that the
arithmetic operators =:= and =\= are introduced (they
were not in the first edition), but the programs on page 175 and 268 do
not use these operators while that would have been the natural thing
to do.
On top of that, there are at least two major areas in ISO that the book does not even mention: the first one is the issue of modules. On page 189, the book advises to split a large program over several files, but the concept of modules, neither the fact that ISO Prolog has also a part that standardized modules is mentioned. The second issue is the one of the ISO error mechanism: ISO Prolog prescribes it in detail and beginning programmers are confronted with it from the start because badly called built-in predicates throw an exception. The book should have explained the mechanism: it is not prohibitively difficult. Moreover, on pages 8 and 119, the book mentions only failure, failure+warning or error message as the ISO possibilities for calling a non-existing predicate or calling arithmetic on non-numbers.
In conclusion: this is a great introduction to Prolog, but it is weak
on the ISO aspect.
BART DEMOEN
K.U.Leuven, Belgium