Review of "The Art of Prolog"

by Leon Sterling and Ehud Shapiro

reviewed by Dale Miller, University of Pennsylvania

March 1987

This book is a very comprehensive introduction to the Prolog programming language and its uses. It makes quite clear what contributions logic programming and Prolog have made to the craft of programming.

This book is broken into four parts of several chapters each. We first describe each part separately.

Part I is an introduction to the general principles behind logic programming. The authors stress its declarative nature by defining the meaning of a program as those goals provable using a simple, non-deterministic Horn clause interpreter. They make it clear how this programming paradigm is very different from other more procedural programming paradigms. They address these differences head-on and, through numerous examples and good analysis, help the reader understand how conventional programming tasks could be re-thought and specified as logic programs. They gradually develop a problem solving approach to building logic programs which is used throughout the rest of the book.

Part II presents the Prolog language with all its inabilities to live up to the wonderful view of declarative programming described in Part I. Here the authors are determined to describe Prolog as it has been used for the past decade and more. Hence, they do not justify Prolog's reliance on such features as negation-by-failure, cut, freeze/melt, univ, and setof for any logically intrinsic reasons. Rather these are justified by referring to the language's historical development and by presenting numerous examples which show how they solve problems not addressed by ``pure Prolog''. As each feature is introduced, they are explained and illustrated. By the end of Part II, the full Prolog language with all its non-logical and meta-logical system predicates is introduced. In presenting both syntax and special predicates, the authors stay very close to the Prolog-10/Edinburgh Prolog/C-Prolog implementations of the language.

Part III describes advanced Prolog programming techniques. This part is extensive. It provides many well motivated examples of how to implement useful kinds of programming tasks: search, parsing, meta-interpreters, and generate-and-test to name a few.

Part IV discusses the development of larger, application-like programs. This part is intended to remove many people's doubt that Prolog is only good for small, toy applications. They show how larger programs can be built in a top-down and largely declarative style. Several game-playing programs, an expert system, an equation solver, and a compiler for a subset of Pascal are presented.

The author's presentation of all this material is well thought out. There are always enough examples, and most sections end with a collection of problems, some of which introduce new material. Most chapters end with a ``Background'' section which describes some of the historical developments of the ideas in that chapter as well as includes additional references for the interested reader. Although the bibliography is not complete, it is substantial (117 entries) and contains most of the fundamental papers in the field.

The authors do a very good job of presenting Prolog as a compromise between pretty but impractical declarative programming and the unfortunate realities of real world programming. Whenever they need to deviate from the declarative style and use the various non-logical or control-oriented primitives, they try to find a rational way to isolate the use of such features. Furthermore, the authors are often careful in their analysis of program correctness, complexity, and termination properties. In other texts, these topics are generally left to students to learn through experience. Here, the reader is provided with several tools for understanding these aspects of programs.

This book can easily be recommended to anyone who wishes to learn to program in Prolog. To the reader who has a knowledge of symbolic computing already, the book is self-contained and easily read. For a class in which symbolic computing is being taught for the first time, this book could be recommended as the sole text. Although it contains numerous AI programs, it could not be recommended as the sole text for an AI course. It would make, however, a very good companion text to a more standard AI text. Since this text is such a complete treatment of Prolog and its rationale, it should be very useful for those interested in Prolog for its applications in database programming and compiler writing.

There are at least two broad areas, however, which this book does not cover. First, it does not discuss how to implements a Prolog interpreter or compiler. There are occasional references to tail recursion removal, garbage collections, stack frames, and logical variables-as-pointers, but these topics are not developed. Second, this book does not cover the basic nature of logic and its role in logic programming. Questions such as ``How is negation-by-failure different from logical negation?'' and ``What happens if Horn clauses were to be extended in this or that way?'' are not addressed. The logic background necessary to address such questions is outside the scope of this text.