Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!hp4nl!swi.psy.uva.nl!anjo From: anjo@swi.psy.uva.nl (Anjo Anjewierden) Newsgroups: comp.lang.prolog Subject: Review of "The Craft of Prolog" Message-ID: <5771@swi.swi.psy.uva.nl> Date: 4 Feb 91 16:42:56 GMT Reply-To: anjo@swi.psy.uva.nl () Organization: SWI, UvA, Amsterdam Lines: 137 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.