François Laburthe
Bouygues, France
Programming Constraint Services: High level Programming of Standard and New Constraint Services by Christian Schulte, published in 2002 by Springer in the series Lecture Notes in Articial Intelligence, vol. 2302, ISBN 3-540-43371-6, xii + 176 pages, paperback.
'Service' is a word of fashion, from web services to service-oriented software architectures. Schulte brings it to Constraint Programming, crafting a new name, "Constraint Services" for generic methods related to the implementation of search in CP systems. This book, published last year in the LNAI series reviews the theory and implementation of search in the Oz/Mozart concurrent programming language.
The book is intended for all CP practitioners, from newcomers wanting to learn how a search exploration is built to experts looking for ideas in designing, or improving their favourite CP system.
I enjoyed reading the book, found it enlightening and, at times, frustrating. Talk about concurrent feelings ?
It is definitely an enlightening reading.
To my knowledge, it is the first book that thoroughly goes into the implementation issues of a CP system. As such, it does fill an important hole in the shelves of our libraries. It is a pity that such topics have been neglected and I am grateful to Christian Schulte for having the talent and taking the time to explain how a constraint system is built, both from theoretical and practical points of view.
The book indeed provides a self-contained and very didactic presentation of the Oz/Mozart platform. The theory of the concurrent language is based on the introduction of computation spaces which are entities that model the context of computation, such as the state of domains. The computation spaces are explicit: they are available as "first class citizens" of the language, as stated by the author. As such, they can be programmed, by being passed as functional arguments. This framework supports, among other things, a very simple way of programming search by copy.
The book features 15 chapters. Chapters 1,2,3 provide introductions, including a self contained description of Oz-light, a narrowed down version of the Oz system. Chapters 4 to 7 present the theory of global search in a concurrent language environment, including the issue of copying vs. re-computation Chapters 8 and 9 present two applications of this theory, to interactive search (supported by the 'Oz explorer' tool) and to distributed search. Chapters 10 and 11 develop the full theoretical model of search combinators, which are the objects that handle the computation spaces to control the search. Chapters 12 and 13 focus on implementation issues while the chapters 14 and 15 list other approaches and conclude.
The theoretical apparatus developed by Christian Schulte is very elegant and the author goes into many subtleties of tree search. Among them, here are a few original topics discussed or defended by the author that particularly caught my interest:
In one sentence rather than a thousand words, the book provides an easy access to a versatile technology and a complete CP system. Congratulations for making things look simple and natural.
Now, on the frustrating side, the weakness of the book concerns the account for related work. Although a small chapter lists references to other systems, the core presentation is focused on the sole Oz/Mozart platform. The interested reader would like to understand, which of the techniques mandatorily require working within a concurrent programming language and which do not. Unfortunately, such insights are not provided by the author. This is a pity, in particular concerning the section devoted to search by re-computation.
An approach using search by re-computation has been proposed by Laurent Perron and marketed by Ilog in the "Parallel Solver" product, and it would be most useful for the reader to understand how the approaches differ and what common procedures they use. In my opinion, re-computation-based search strategies do not require a concurrent programming environment, as they can manipulate a data structure representing the tree of explored nodes in a standard object-oriented environment, without sacrifying either the elegance of the code nor the performance of the exploration. As a reader, I would be interested in either understanding that my intuition is wrong and why, or that it may be right under some conditions and that some of the services from the Oz system can be described as primitives in a non-concurrent environment, and related to mechanisms of Perron's architecture.
The presentation of "Constraint Services" may not yet be the review of the state of the art techniques on search for constraint programming. To date, such book still does not exist. But who knows, reading some of the future work directions, it could well be Christian's next grand oeuvre.