Constraint Handling Rules

Compilation, Execution, and Analysis

Thom Frühwirth, Frank Raiser (editors)
Textbook, ISBN 978-3-83-911591-6, March 2011.

Buy worldwide, e.g. at

eBook-Edition available in Germany, for Kindle at, at iTunes, as epub at e.g.

" of the most powerful multiset rewriting languages."
Professor Kazunori Ueda, Waseda University, Japan, and Norio Kato in 'Programming Logical Links'
"...a powerful, highly optimized, lazy rule engine [...] consistently outperforms Rete-based systems."
Peter Van Weert, K.U. Leuven, Belgium, in 'Efficient Lazy Evaluation of Rule-Based Programs'
"has the potential to become a lingua franca, a hub which collects and dispenses research efforts from and to the various related fields."
Jon Sneyers, K.U. Leuven, Belgium, in 'Optimizing Compilation and Complexity of CHR'
"perfectly suitable for high level design of constraint systems"
Marco Alberti and Evelina Lamma, Universita degli Studi di Ferrara, Italy, in 'Merging Views into CSPs: an Application for Computer Vision'

Constraint Handling Rules (CHR) is both a versatile theoretical formalism based on logic and an efficient practical high-level programming language based on rules and constraints.

Procedural knowledge is often expressed by if-then rules, events and actions are related by reaction rules, change is expressed by update rules. Algorithms are often specified using inference rules, rewrite rules, transition rules, sequents, proof rules, or logical axioms. All these kinds of rules can be almost directly written in CHR.

The clean logical semantics of CHR facilitates non-trivial program analysis and transformation. About a dozen implementations of CHR exist in Prolog, Haskell, Java, and C. CHR is also available as WebCHR for online experimentation with more than 40 example programs. More than 100 academic and industrial projects worldwide use CHR, and more than 200 books and 1000 research papers reference it.

Visit for more information.

Book Contents


This book presents recent research in implementation, extensions, and novel analyses of CHR.

In order to be self-contained, it starts with an introduction to CHR, which in the spirit of this book, is held concise and research-oriented. After that, carefully selected chapters from recent PhD theses provide detailed information on the topics compilation and optimization, execution strategies, and formal analysis of CHR. These chapters can be read individually based on the reader's interest.

The chapters have been edited by Thom Frühwirth and Frank Raiser to better suit the book's general theme. Additionally, the book has been reviewed by the individual authors of the chapters, the editors, and Florian Geiselhart and Johannes Langbein. The involved PhD theses range from 2005 up to the latest theses available at the time of writing, resulting in the following list of authors:
  • Gregory J. Duck
  • Leslie De Koninck
  • Edmund S. L. Lam
  • Frank Raiser
  • Tom Schrijvers
  • Jon Sneyers

Foreword (pdf)
Part I. Introduction to CHR
1. Constraint Handling Rules
Part II. Implementation and Optimization of CHR
2. Basic Compilation
3. The K.U. Leuven CHR System
Part III. Execution Strategies
4. Rule Priorities
5. Concurrent CHR
Part IV. Formal Analysis of CHR
6. Computational Complexity
7. Complexity Analysis of CHRrp Programs
8. A Complete and Terminating Operational Semantics
9. Abstract Interpretation
Appendix, Index (pdf)
Complete table of contents (pdf)
Thom Frühwirth, Frank Raiser, updated October 31, 2011