From Kybernetes, vol. 33, no. 1, 2004, pp. 147-150

Book Review

by Chitta Baral

University Press, Cambridge, 2003, hardback, xiv + 530 pp., ISBN 0-521-81802-8, £60.00

In recent decades there has been much interest in programming computers declaratively, rather than procedurally. In declarative or logic programming, the steps to be taken to reach the required result are not specified and instead the system is given a set of logical assertions and some sort of query. The first two paragraphs of the Preface to this book explain the point very clearly:

The kind of support structure visualised is of course useful as an advanced "search engine" when coupled to databases and other sources of information. It also has exploratory and planning capabilities that are often illustrated by reference to the kind of task that might be required of a personal assistant, whether human or electronic, in for example planning a trip to attend a conference. The system might be required to find suitable combinations of flights, hotel accommodation, car hire, etc., all with verification of availability, and chosen to satisfy as far as possible the known preferences of the enquirer, presumably with attention to budget and to the complications of such things as conference discounts and frequent-flyer benefits. Such a capability is obviously useful in robots and autonomous agents in general.

Another reason for interest is that such a system can allow rapid and probably error-free prototyping, since the requirements for a new system can usually be expressed declaratively more quickly and reliably than is posible for procedural programming.

The kind of problem-solving operation needed has been well explored in mathematical theorem-proving, and the programming language Prolog has been available for some time. The new book is a comprehensive treatment of a development referred to as AnsProlog (also called A-Prolog), or "logic programming with answer set semantics". The treatment involves a great deal of mathematical formalism and the difficulty of getting to grips with all of it is acknowledged where the use of the book as a teaching text is discussed. A large part of it could be covered in an undergraduate course, and the ideal is to top this up with a taught graduate course.

Even the meaning of "answer-set semantics", also referred to as "stable model semantics", can only be explained by invoking some mathematical theory. One of the ways in which AnsProlog differs from standard Prolog is in being truly declarative. In the latter it is necessary to consider the order in which the "literals" within a rule are listed, and therefore the order in which they will be processed. This means that programming in Prolog is partly procedural, whereas AnsProlog is free from this taint.

It is argued convincingly that AnsProlog should be the system of choice for practical applications and that efficient software has been developed, such that very large programs can readily be handled. A number of alternative formulations are described, differing in the allowing or disallowing of certain operators in the heads of rules. The unrestricted version is indicated by AnsProlog* (possibly causing confusion since it is not immediately obvious that the asterisk does not refer to a footnote!) Alternatives are indicated by replacing the asterisk with a superscripted listing of the allowed or disallowed operators, so that a superscripted "-not" shows that the operator "not" is disallowed. (The operator not is distinct from the negation operator "¬" because, unlike standard Prolog, the system allows for variables having the three possibilities of true, false and unknown.)

The use of the method is illustrated with some impressive examples, including its application to a combinatorial auction, where participants can bid for any subset of objects offered, and the task of the auctioneer, or the AnsProlog program, is to select the combination of bids that will maximise the total return subject to no object being sold more than once. Other standard combinatorial problems are used as illustrations, one of them being the deduction of the correct ownership of a pet (a zebra, in the example) found wandering, where the choice of its home, out of five possibilities, must be derived from a set of fourteen statements about the characterisitics of the five houses and their occupants.

Even more convincing of the the power of the method is a practical application to the planning of actions to be taken in a space shuttle when there is failure of components of the means of controlling the maneuvering jets. This refers to a real project carried out by a NASA contractor and groups in the University of Texas.

A great deal of relevant information appears on the website http://www.baral.us/bookone, including coding for the examples and a good deal of downloadable software in C++, and a set of slides in PowerPoint format that could be the basis of an introductory lecture. Probably even more helpful for a beginner is another set of slides with the title: "Answer Set Programming: What it is and how to play with it", due to Aarati Parbat, who is associated with the early pioneer John McCarthy. His involvement is noteworthy since he laid foundations for logic programming in an early paper (McCarthy, 1959).

The possibility of nonmonotonic reasoning is put forward as an important characteristic of a logic programming language. Reasoning is nonmonotonic if the state of knowledge is not necessarily increased as further information comes available. Many discussions refer to an initial assertion that something (usually given the name "Tweety") is a bird, from which it seems safe to assume that Tweety can fly, though this will be revoked if there is the further information that Tweety is a penguin (or an ostrich or an injured or dead bird, etc.) Approaches to nonmonotonic reasoning are collected in the book edited by Ginsberg (1987). AnsProlog is said to have a useful property of "restricted monotonicity" according to which it resists changes that would drastically overthrow its existing knowledge structure.

The need for nonmonotonic reasoning is not apparent from the examples in the book and it seems possible that its relevance is reduced if the "universe of discourse" is widened to include observers, in accordance with ideas of second-order cybernetics (von Foerster and Poerksen 2002). A reference to a bird, for instance as the perceiver of a "bird's eye view", can safely be assumed to refer to a flying bird, since the distinction is otherwise pointless. The reference to a bird is therefore not ambiguous provided the model that the hearer/observer has of the speaker is of someone trying to convey a serious message rather than being frivolous or provocative. This would seem to be an aspect deserving further attention, though not directly relevant to the present review.

It seems clear that AnsProlog represents the current state of the art in applicable logic programming and that this book should be accepted as the definitive guide to it.

Alex M. Andrew

Back to Reviews