Book review:
Constraint Handling Rules by Thom Frühwirth
Cambridge University Press, 2009, hard cover: ISBN 978-0-521-87776-3.
This book presents a rule-based constraint programming language called Constraint Handling Rules (CHR) and covers both the theory of CHR and its use in practice. The book is intended for graduate students and lecturers, but also for researchers and practitioners. The book offers exercises with their solutions and is complemented by a webpage containing an exhaustive bibliography about CHR, links to research papers, course materials (such as slides, exercises, and tutorials), and links to the various CHR implementations in Prolog, Java, C, and Haskell.
The book consists of 3 parts divided into 10 chapters, most of them completed with exercises and bibliographic remarks.
The first part can be seen as a tutorial which explains how to write CHR programs and shows what are the CHR rules and how they are executed. The examples are very small (some of them just one line) and simple, but elegant and expressive; they illustrate well how to program with CHR and how the programs behave. Moreover, the programs are commented in detail and their properties are informally discussed.
The second part is more formal and describes the syntax and semantics (both declarative and operational semantics) of CHR. Then, guaranteed properties of CHR are presented: anytime and online algorithm properties are shown, declarative concurrency is discussed, etc. . The next chapter describes termination, confluence, operational equivalence, and time complexity of CHR programs. Finally, a comparison of CHR with other formalisms is given: it is shown that the essential aspects of logic-based programming, concurrent constraints, business rules, Petri nets, and some other formalisms can be embedded in CHR.
The third part returns to the programs of the tutorial and analyzes them using the properties and methods given in the second part. Some larger examples are also presented and analyzed, such as finite and infinite domain constraint solvers (i.e., algorithms for reasoning in constraint systems), and the classical union find algorithm (for solving the problem of maintaining a collection of disjoint sets under union).
The book is really pedagogical and the approach is very practice-oriented. The elegance and the natural of the examples of the tutorial part make the reader feel like installing a CHR implementation on his/her computer and trying them immediately. Then, in the second part, one discovers that CHR is not a toy programming language but provides a formal framework for analyzing programs. Finally in the third part, one realizes that this formal framework can also be used to develop larger programs, making of CHR a powerful programming language based on rules.
Another advantage of this book is that it is accompanied by a website, rich with useful information. For those considering the book as a textbook for graduate students, the web page offers teaching material such as slides, tutorials, and further exercises that come very handy. The CHR site also provides numerous examples of programs and a large number of links to some applications and projects that can be of interest for practitioners. The website offers links to research papers and an exhaustive list of references about CHR that can satisfy the most eager researcher. Last but not least, the web page offers links to a dozen of free implementations of CHR available in Prolog systems, Haskell, and more conventional programming languages such as Java and C.
In 2003, together with Slim Abdennadher, Thom Frühwirth wrote a book titled Essentials of Constraint Programming. The focus of that book was more on constraint programming languages, and how to write constraint solvers; CHR was used to specify, design, and implement these solvers. In this new book, a wider range of CHR applications are shown and CHR is used not only for implementing solvers, but is also considered as a complete programming language with examples well illustrating its wide possibilities. Moreover, the approach of this book is more practical and geared towards programming with CHR.
I was expecting a chapter about a CHR programming methodology: given a problem, how to define the required constraints, rules, and their order, how to handle large programs, how to manage a project with CHR, etc. . On the other hand, these matters are rather well covered by numerous examples, various versions of some programs. Further, Chapter 6 explains a relationship of CHR with other rule-based formalisms and programming languages and thus helps one to relate it to own favorite programming paradigm.
The book is written by the creator of CHR, and one can significantly appreciate the experience of the author in teaching CHR and his desire to share his knowledge and expertise. I heartily recommend this valuable book to graduate students, practitioners, and researchers as well, who are concerned with rule-based programming languages.