anjo@swi.psy.uva.nl (Anjo Anjewierden) (02/05/91)
Below is a review of "The Craft of Prolog" I wrote for AI Communications
(the European AI Magazine). Enjoy.
:- Anjo, !.
%--------------------------------------------------------------------------
% Anjo Anjewierden NET: anjo@swi.psy.uva.nl
%
% Department of Social Science Informatics
% University of Amsterdam, Roeterstraat 15 TEL: +31 20 525 6786
% 1018 WB Amsterdam, The Netherlands FAX: +31 20 525 6896
%---------------------------------------------------------------------------
The Craft of Prolog
Richard A. O'Keefe
MIT Press, 1990
Reviewed by
Anjo Anjewierden
University of Amsterdam
Few Prolog texts address the problem of designing Prolog programs that
achieve good performance. Prolog is considered a rapid prototyping
language and used to demonstrate ideas. "The Craft of Prolog" tries to
show that Prolog programs can be made efficient and aims at uncovering
general principles that may be applied in practice.
The problem with Prolog is that there is no obvious model of what a
Prolog compiler does given a program. For languages such as C such a
model readily exists in the von Neuman hardware architecture. Over
the past two decades Prolog compiler technology has not only improved
to the point where Prolog has become a serious language, but all Prolog
compilers use similar techniques.
Whether the contents of "The Craft of Prolog" will appeal to you may
be determined by looking at the following four predicates. They all
implement a predicate that returns the highest of two numbers.
/* 1 */ max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.
/* 2 */ max(X, Y, X) :- X >= Y, !.
max(X, Y, Y) :- X < Y.
/* 3 */ max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).
/* 4 */ max(X, Y, Z) :- X >= Y, !, Z = X.
max(X, Y, Y).
If your preference is with the first program (called the pure version
because it is a straightforward implementation of the problem
specification) there is no need to read the book. I would be very
surprised if anyone selected number two. Program number three is
incorrect, and you should definitely read the book to find out why.
The final version is preferred by O'Keefe. The general principles
involved are: "Place a cut precisely as soon as you know that this is
the right clause to use, not later, and not sooner", and "Postpone
output unifications until after the cut."
The book assumes a working knowledge of Prolog syntax and semantics
(topics not covered) and is therefore only suitable for relatively
experienced programmers who want to learn how to improve programming
style, and how to design more efficient programs.
The book contains material that seems indispensable for efficient
Prolog programming and material that is difficult to place.
Indispensable material deals with schemata experienced programmers
use (chapter 1). In this chapter O'Keefe lists predicates that
follow some general form (passing context arguments, difference lists
and the relative ordering of predicate arguments for example).
Chapter 3 describes how Prolog compilers work, and in particular how
memory space is managed. The section on the use of cuts is the best
I have ever seen. Finally, chapter 5 is about the design of data
structures in Prolog.
The remaining chapters make the book highly personal. The
template O'Keefe uses is as follows:
* Specification of a problem
Usually a terse specification in English is given first, immediately
followed by the most "logical" Prolog equivalent. An example is:
"We are given a proper list of items, each of which is either
red, white, or blue. The task is to construct a new list
which contains the elements of the first list, first the red
ones, then the white ones, and finally the blue ones." (p.
113)
This example actually starts the chapter entitled "Methods of
Programming".
* Realisation that the program may not be efficient
Next O'Keefe realises that the obvious specification translated
into Prolog may not be efficient ("Prolog is an efficient
programming language because it is a very stupid theorem prover").
Often a complexity analysis follows.
* Progressively better versions of the program are developed
Here O'Keefe really seems to be enjoying himself. Many improved
Prolog programs are subsequently listed and their merits are
described. The techniques used to measure progress (i.e. faster
and/or better programs) are: observing running time and analytical
methods (complexity has been decreased). Sometimes O'Keefe
realises he has gone very far and reflects:
"These improvements reduce the time from 0.90 seconds to 0.53
seconds [...]. It is possible to improve this still further,
but if we push it far enough we end up with
answer([3,8,1,6,5,4,7,2,9]).
which doesn't illustrate many general points." (p. 130-1).
One of the programs is an ingenious Prolog implementation of the
N-Queens problem.
* Description of general principle applied
Having developed a satisfactory program for the original
specification, O'Keefe states the general principles applied.
It is without doubt that most of the material presented in the above
fashion would receive standing ovations at the annual "Hacker's
conference". Some of the chapters are very much in Dijkstra's
letters to myself (because no one understands it anyway) style.
"The Craft of Prolog" documents O'Keefe's knowledge about Prolog
programming and can almost be regarded as an autobiography. All of
the material illustrates his enormously deep understanding of what a
Prolog compiler does to a Prolog program. It is next to impossible
to find a serious mistake in any of the programs in the book.
Applying the principles in chapters 1 through 5 can do miracles to
your Prolog code. Definitely read the book if you think you are a
good Prolog programmer already. You'll be surprised.lhe@sics.se (Lars-Henrik Eriksson) (02/05/91)
In article <5771@swi.swi.psy.uva.nl>, anjo@swi (Anjo Anjewierden) writes: > >/* 1 */ max(X, Y, X) :- X >= Y. > max(X, Y, Y) :- X < Y. > >/* 2 */ max(X, Y, X) :- X >= Y, !. > max(X, Y, Y) :- X < Y. > >/* 3 */ max(X, Y, X) :- X >= Y, !. > max(X, Y, Y). > >/* 4 */ max(X, Y, Z) :- X >= Y, !, Z = X. > max(X, Y, Y). > >If your preference is with the first program (called the pure version >because it is a straightforward implementation of the problem >specification) there is no need to read the book. I would be very >surprised if anyone selected number two. Actually, I often use version number two. Why? I really prefer the pure version, but inserting as cut rids me of a useless choice point. At the same time the cut is semantically redundant (I believe O'Keefe calls this a "green" cut). -- Lars-Henrik Eriksson Internet: lhe@sics.se Swedish Institute of Computer Science Phone (intn'l): +46 8 752 15 09 Box 1263 Telefon (nat'l): 08 - 752 15 09 S-164 28 KISTA, SWEDEN
dave@quintus.UUCP (David Bowen) (02/06/91)
It should be noted that in Quintus Prolog the definition:
max(X, Y, Max) :-
( X < Y -> Max is Y ; Max is X ).
is substantially more efficient in Quintus Prolog than those which
Anjo quotes from Richard's book. The reason is that this is compiled
as a test and jump, so no choicepoint is created.felkl@aste16.Berkeley.EDU (Feliks Kluzniak) (02/08/91)
In article <4710@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: |> In article <5771@swi.swi.psy.uva.nl>, anjo@swi.psy.uva.nl (Anjo Anjewierden) writes: |> > Some of the chapters are very much in Dijkstra's |> > letters to myself (because no one understands it anyway) style. |> |> Perceptive! Dijkstra's writings have influenced me a lot. To this I would like to add the following quotation ("The Craft of Prolog", p.333): "Given that we usually have to put in a lot of time stepping through a program when we are debugging it...." Sapienti sat. -- F. K.
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (02/11/91)
In article <1991Feb7.183637.2783@ida.liu.se>, felkl@aste16.Berkeley.EDU (Feliks Kluzniak) writes: [I wrote] > |> Perceptive! Dijkstra's writings have influenced me a lot. > > To this I would like to add the following quotation ("The Craft of > Prolog", p.333): > > "Given that we usually have to put in a lot of time stepping through a > program when we are debugging it...." Curses. This is where the derivation of much of the book from a collection of "addenda to C&M" -- as I originally thought of them -- shows through. The *context* of the sentence does reveal my debt to Dijkstra, because it is a plea for "separation of concerns" (first make it right, then make it fast). The sentence should not be taken as implying that it is normal for Prolog code to require a lot of debugging; it should be read as "if&when". -- Professional programming is paranoid programming