Programming with Constraints: An Introduction

Book review (a teacher's perspective)
Kim Marriott and Peter Stuckey

Pages: 467
Hardcover price: $49.50

Review by:
Francesca Rossi
University of Padova, Italy
frossi@math.unipd.it

The authors of this book say, in the first sentence of the introduction, that ``constraint programming is one of the most exciting developments in programming languages in the last decade''. In fact, constraint programming, and in particular constraint logic programming, has quickly evolved from a basic research idea to a powerful programming paradigm that is increasingly used to model and solve many hard real-life problems. Several companies have started up to exploit this technology, and the number of industrial applications is now growing very quickly: from scheduling to resource allocation, from timetabling to vehicle routing, from transport problems to personnel assignment, from option trading to molecular biology, from graphical interfaces to multimedia.

This book gives an introduction to most of the main concepts and techniques underlying the constraint logic programming paradigm, which can be briefly described as the combination of constraint solving techniques and logic programming. From the logic programming part, we get declarativeness and a search for solutions based on backtracking. From the constraint part, we get efficiency and wide applicability to several domains.

Because of the increasing use of constraint programming in practice, and of the fact that this is the first comprehensive collection of material on the subject, it is reasonable to expect a lot of interest in this book. In fact, one year after his publication, this book has been already heavily reviewed. (and I think also heavily read, at least I hope for the authors). I know of at least two reviews that have been recently published. One has been written by K. Apt for the em Logic Programming Newsletter, vol.12/1, 1999, and the other one by Y. Jianchao for Intelligence: New Vision of AI in Practice (previously the ACM SIGART Bulletin).

Thus one may think that an additional review is not really needed: what else can be said that has not been said already by the other two reviewers? Actually, I think there is one point of view that has not been considered by the other two reviews, which however were very informative and useful: the point of view of somebody who used the book not only to read it and get some insight into constraint logic programming, but also to teach a course on this subject. Maybe the other two reviewers have also used the book to teach, but no notion of that emerges from my reading of their reviews.

Using a book to teach gives a different perspective about how successful a book is in bringing a group of completely novices into the subject. Of course also the teaching skills of the professor are important, but the material chosen, the sequence in which it is presented, and the level of detail chosen by a book are all crucial in molding the final knowledge of the students about the subject. , knowledge that in my course had to be demonstrated both by answering some questions (written and oral) and also by developing a full project in a constraint programming language of choice. Therefore in this review I will try to combine my opinions on the book as a researcher and also as a teacher.

When I decided to give a course on constraint logic programming, I found a lot of material from several colleagues who were teaching similar courses and have been so kind to show me their lecture notes. However, some of these courses were very AI-oriented (that is, mostly devoted to solution and propagation algorithms, and variants of the backtracking search, without much on the programming side), and others were very rigorous and detailed, which I liked a lot, but I was worried about filling the mind of my students with all those details, and I thought they were more apt for graduate students (mine were undergraduate). So, when I saw this book, I thought it had the right balance of everything, and I decided for it. However, I have to say that here and there I took some material from these other courses.

Being constraint logic programming the combination of constraints and logic programming, the authors have decided to first give the notions and properties of constraints and then pass onto logic programming. They could have chosen to do the opposite (first logic programming and then constraints), but I think this is the right sequence, because constraint solving exists and has its value even without the logic programming shell around. Of course one could say the opposite as well (that logic programming exists even without constraints), but in my course I was not interested in forming logic programmers, but constraint programmers, so I thought it was better to see logic programming as one of the programming shells where constraints could be embedded.

Constraints are presented in the first three chapters. Chapter 1 introduces the notion of constraint, constraint satisfaction, and solution, and describes solution algorithms like Gauss-Jordan elimination and unification (here called ''tree constraint solver''). Everything is done by using many examples, that are very useful to get the idea that constraints are really everywhere and very useful as a modeling tool. I have to say that I also added some more examples to the ones in the book, taken from the notes of the other courses cited above. However, this chapter (and this applies to the whole book as well) is very keen on examples, which is a very positive thing in my view. I think also my students, who are third year undergraduate, either from a mathematic degree or a computer science degree, appreciated it a lot. Another aspect to notice in the first chapter, but that applies to the whole book, is the presence of many exercises at the end of the chapter. Moreover, there are two kinds of exercises: ``theoretical'' ones, that test the comprehension of the concepts and algorithms described in the chapter, and ask for their application to exercises that can be solved by hand, and ``practical'' ones, that involve the use of existing constraint programming languages, such as CLP(R), Sicstus Prolog, and Eclipse, to solve them. In this respect, it is also important to notice that, in the sections devoted to practical exercises, whenever a new language has to be used, a short introduction to the use of this language (how it can be obtained, what to do to start its execution, ...) is given, so that the student may have an initial help to the use of the languages. Last thing to notice in this first chapter is that, even though only constraint solving, and not constraint programming, is dealt with, there are already practical exercises involving constraint programming languages, so that one starts getting acquainted with them, and also realizes that these languages have an underlying constraint solver that can also be used without the logic programming constructs.

Chapter 2 describes some useful operations on constraints, such as projection (as a form of simplification) and optimization. Two projection algorithms are introduced: Fourier's algorithm for linear inequalities, and a tree constraint simplifier. For the optimization operation, the simplex method is defined and a reasonably long example is carefully described in all its steps. The notion of implication and equivalence of constraints are also given at the end of the chapter.

Chapter 3 deals with finite domain constraints, a very important constraint domain. Again, many examples are given (map coloring, n-queens, ...), and then search with chronological backtracking is introduced as a complete solution algorithm. After this, several incomplete algorithms, like node-consistency, arc-consistency, and bounds-consistency, are defined, as well as their integration within the backtracking search to obtain new complete solvers. One of two reviews cited above complained about the lack of a rigorous formulation for some of these algorithms. One could also add that not all existing propagation algorithms are present, and the description is not as general as it could be. However, I've seen that the level of formality chosen by the book is enough to make the students able to understand these algorithms, work with them, combine them, and later program with them. So, I think that the lack of a completely rigorous treatment, which could be a problem in other contexts, is not really important if the final goal is to produce students who know how to reason with constraints and develop fairly complex constraint programs.

Having learnt what constraints are and how one can solve and manipulate them in Chapter 1 to 3, in Chapters 4 to 10 the book turns to the logic programming part of the subject. In particular, Chapter 4 explains the concept of rules and user-defined constraints, and defines the goal rewriting mechanism given by derivations. It was the first time for my students that they saw logic programming, but in this simple initial chapter they seemed to have no problem at all. However, I felt like I had to integrate the programming exercises proposed at the end of the chapter with some other exercises on writing a logic program.

Chapter 5 goes deeper into the practical use of (constraint) logic programming, and shows how to use it for several problems, some of which are in my view too complex for the students to follow. For example, at the end I decided not to show them the option trading example which, although very useful to show that constraint programming can be used for very different purposes, it took me some time to understand (not the logic programming part, just the option trading part; maybe it's because I don't do much option trading). So I thought that it would have confused my students instead of helping them understand things better. Of this chapter I (and my students) particularly liked Section 5.3, where it is shown how from an imperative iterative program (describing the usual mortgage problem) one can pass, step by step, to an ''equivalent'' recursive constraint logic programming program. In fact, when my students take this course on constraint logic programming, they know already the main concepts and implementation techniques of most programming paradigms (imperative, object-oriented, ...), and they have heavily programmed in C, C++, and Java. But they know nothing about logic programming. So this section plays the role of a useful link from what they know to what they are learning, and I saw that this makes the new concepts, and the presence of much fewer constructs (just rules and only recursion) easier to relate to.

Chapter 6 goes even more into this line, showing the details of how to model the data structures they are used to work with (arrays, records, lists, trees, ...) in constraint logic programming, giving very instructive examples for each of these data structures.

Chapter 7 tries to define the concept of complexity for a constraint logic program, and gives guidelines and techniques (like rule reordering, literals reordering, and addition of redundant constraints) to improve the efficiency of a program. While the general motivations that lead to such techniques are given, and can be grasped by everybody, it all remains a bit ''hand-wavy'', maybe too much to learn how to make a program efficient. (in this I agree with one of the two reviews above). Moreover, the bridge example given in this chapter, although very interesting for an experienced researcher, is maybe too complex for novices who are still struggling to learn the basics of constraint logic programming. So I guess this is the chapter I liked the least, and where I had to add much (in terms of definitions and also examples) before having the idea that the students had understood the subject. I could guess why this chapter is so: the authors know the subject so well, having written several scientific papers on it, thought for other researchers, that they may have problems rephrasing it for novices.

Chapter 8 deals with finite domain constraint programming. I think that this chapter has many good points. First, the notions of domain and labeling, which are the core notions underlying the subject of this chapter, are explained very well. In particular, I liked Section 8.3, where alternative labeling techniques are shown and where it is also shown how to program them in the language. Then, it is also very good the way the authors have treated the issue of different models: an assignment problem is taken, and three different models, as well as a combination of two of them, are shown. Also the complex scheduling examples of Section 8.5 is very useful and, although rather long, it could be followed in all details by the students, who in fact used some of the solutions adopted here in their final project.

Chapter 9 shows some advanced techniques that can also be useful, like how to extend the constraint solver within the program (the example that shows how to program the Newton-Raphson iteration to handle non-linear arithmetic functions, which otherwise could not be treated in CLP(R), is very nice), how to combine symbolic and arithmetic reasoning, and how to program the branch-and-bound method. Moreover, it introduces some built-in higher-order predicates, like the {\tt once} predicate which collects only one solution, and the negation predicate {\tt not}, which however is explained a bit fast to fully grasp all the consequences of its use.

My teaching experience with this book ends here. I had only 60 hours (between lectures, exercises, and lab practices), and I went slower than I though when I realized that the students had problems. In fact, I had originally planned to cover also the remaining material: Chapter 10, which discusses implementation issues, Chapter 11, which describes the notion of constraint databases and relates them to relational databases, (that the students have seen in another course), and Chapter 12, which indicates other constraint programming languages, and thus shows that not only logic programming can benefit from the introduction of constraints.

Besides the text of the book, other very useful material, at least for the preparation of my lectures, are the slides that are available on-line in the MIT Press web site of the book (http://mitpress.mit.edu/book-home.tcl?isbn=0262133415), that cover each chapter of the book. I have to say that in many cases I found them a bit scarce, and I integrated them with other examples and informal statements, but they were a very good starting point to produce a personalized set of lecture slides.

During the course, the students had to pass two written exams consisting of a series of exercises, one on constraint solving and propagation (Chapter 1 to 3), and the other one on constraint logic programming (Chapter 4 to 9). Then, at the end of the course, groups of two/three students each were formed, and each group had to develop a constraint logic programming program to solve a university timetabling problem (based on assumptions and constraints that I provided them). The students could choose any of the constraint logic programming languages seen during the course (in my case they had seen CLP(R) and clp(fd)). The resulting projects were in the average reasonably satisfactory, with some very good ones where also efficiency issues were ingeniously considered.

By the way, one thing to notice about the programming languages is that, although the programming exercises of the books use CLP(R), Sicstus Prolog and Eclipse, it is reasonably easy and not traumatic for the students to use any other language with the same main features, because the book is written in a way that is almost independent from the language used. In my case, for example, I used CLP(R) to program with arithmetic constraints and Herbrand terms, and clp(fd) to program with finite domain constraints. Maybe next year I will pass to Eclipse, or maybe I will use CHIP. So prospective teachers should not be worried that this book, because of the origin of its authors, is mainly CLP(R)-oriented.

So I can say that, all considered, the course based on this book has been a good way to introduce the students to this new discipline, because it brought complete novices to a reasonably deep knowledge of the subject, both theoretically and practically, in just 60 hours and three months. If I have to point out a moment of difficulty, I would say in the middle of the course, where students tried to write their first logic programs. Maybe because my students are in a mathematics department, they had absolutely no problem in mastering the techniques for manipulating constraints, but when it came to learn how to program with logic programming they were a bit puzzled at first, and it needed some care and time to make them understand this completely new, for them, approach to programming. But I cannot say that this problem came from a fault of the book, it's just that students need time to assimilate such an original approach to programming as logic programming is.

Needless to say, another good point of the book is the fact that, for the first time, we have everything in one place, while until now we could find all this material scattered in several books, surveys, and papers. This is important not only for students but also for researchers who want to learn about this discipline or have a reference book where all the main notions about constraint logic programming are contained. In fact, as a researcher, I too found the book very instructive: although I have been working in this area for a long time, the impressive amount of examples and techniques described here provided me with some interesting new knowledge, and allowed me to get a more profound view of constraint programming.