Constraint Handling Rules

CHR - The Ultra-High-Level Programming Language and Logical Formalism

Thom Frühwirth
Textbook, Cambridge University Press, ISBN 9780521877763, 2009.

"The reference on Constraint Handling Rules, covering both theory and practice."
Professor Pascal Van Hentenryck, Brown University, Rhode Island, USA

"This is a great book illustrating both the simplicity and power of Constraint Handling Rules, the purest form of rule based programming I know."
Professor Peter J. Stuckey, University of Melbourne, and National ICT Australia

The standard reference authored by the designer of CHR
- Provides a CHR tutorial for easy introduction -
An essential source for researchers, lecturers, graduate students and professional programmers

Available everywhere, e.g. at Cambridge University Press,,,,,

Also available as eBook!

Book Review by Eric Monfroy in TPLP Journal.

The follow-up book is "Constraint Handling Rules: Compilation, Execution, and Analysis" Thom Frühwirth, Frank Raiser (editors), 2018.

What are Constraint Handling Rules (CHR)?

" 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'

"... [Concurrent CHR in Haskell] exhibits significant speed up in most problems when executed on multi-core systems."
Members of the National University of Singapore at the Concurrent Constraint Handling Rules Home Page

"Since CHR seems to subsume most of the other formalisms that have been related to it, it 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'

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 conveniently 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, Javascript, Python and C. Some of them are so fast that they apply millions of rules per second. CHR is also available online for experimentation with many example programs. More than 250 academic and industrial projects worldwide use CHR, and about 2500 research papers reference it.

- Slides of CHR Keynote Talk, Thom Frühwirth at RuleML 2015.
- Constraint Handling Rules - What Else?, Thom Frühwirth, Survey, 2015.
- Online Interactive Constraint Handling Rules CHR WWW Demo Tool.
- Constraint Handling Rules (CHR) bibliography and news blog.
- Recent Research of Thom Fruehwirth on Constraint Handling Rules (CHR).
- Talk in German about Applications of CHR on Youtube (Slides in English): Computer knacken harte Nüsse: Von Sudoku über den Aktienhandel zum Robotersegeln.

The CHR Logo
CHR Logo - the Chinese Symbol "CHR"

Book Contents

This book, written by the creator of Constraint Handling Rules (CHR), describes the theory of CHR and how to use it in practice. After a basic tutorial, the author describes in detail the CHR language and discusses guaranteed properties of CHR programs. The author then compares CHR with other formalisms and languages and illustrates how it can capture their essential features. Finally, larger programs are introduced and analyzed in detail. These include constraint solvers and implementations of classical algorithms. The book is ideal for graduate students and lecturers, and for more experienced programmers and researchers, who can use it for self-study. Exercises with selected solutions, and bibliographic remarks are included at the ends of chapters. The book is the definitive reference on CHR.

Part I. CHR Tutorial:
1. Getting started
2. My first CHR programs
Part II. The CHR Language:
3. Syntax and semantics
4. Properties of CHR
5. Program analysis
6. Rule-based and graph-based formalisms in CHR
Part III. CHR Programs and Applications:
7. My first CHR programs, revisited for analysis
8. Finite domain constraint solvers
9. Infinite domain constraint solvers
10. Union-find algorithm
List of figures
List of illustrations

Contents and Preface (preliminary version).
Book excerpt: First Steps in CHR.

Some Industrial Users of Constraint Handling Rules

Stock Broking - Mike Elston, Director of Systems Development, SecuritEase, Wellington, New Zealand.

Automatic Test Data Generation - Ralf Gerlich, BSSE, Immenstaad, Germany.

Injection Mold Design - Alan Baljeu, President, Cornerstone Intelligent Software Corp, Windsor, Canada.

Smart Database with Constraints - Molham Aref, Logic Blox Inc, Atlanta, USA.

Cognitive Brain for Service Robotics - Teresa Escrig, CEO, Cognitive Robots, Castellon, Spain and Seattle, USA.

Optical Network Routing - Jonathan Weston-Dawkes, Mitre Corp, Bedford, USA.

CHRjs Project - Matt Delaney, New Ocean Health Solutions, Conshohocken, USA.

Unit Testing Tool AgitarOne for Java - Agitar Software, Mountain View, USA.

Try and Download Constraint Handling Rules

Online Interactive Constraint Handling Rules CHR Demo Tool and Javascript JIT CHR Compiler
CHR Online. Test-Drive CHR. Run full-fledged CHR online now! Play with many example programs or write your own.

Some CHR implementations in Prolog

SWI Prolog (SWI Prolog Reference Manual 7.1),
Sicstus Prolog (Sicstus Prolog User's Manual),
Yap Prolog,
XSB Prolog,
Ciao Prolog,

Other CHR-Prolog systems:

ToyCHR: simple CHR interpreter in LogTalk
CHRrp: CHR extended with rule priorities
CHRat: CHR with ask and tell, a modular CHR system
HAL includes a CHR system
CHR in Curry: a functional logic language

Main CHR implementations in Java, JavaScript, C and Haskell

JCHR: CHR in Java
CHRJS: CHR in Javascript
CCHR: Efficient CHR in C
Parallel CHR in Haskell
STM-based Concurrent CHR in Haskell

More CHR Systems...

More software involving CHR

SMCHR: Satisfiability Modulo Constraint Handling Rules
From XML Schema to JSON Schema - Comparison and Translation with Constraint Handling Rules, (tool download).
CHORD (CHR with Search and Objects)
Actor Model in Haskell CHR
Join-Calculus and Join-Patterns in Haskell CHR
An extensible Eclipse platform for analysing graph transformation systems in CHR (pdf) (Eclipse Plug-in tar-file).

More CHR Software Downloads...

Course Materials Constraint Handling Rules

Courses by the author based on the book were held for example at the University of Ulm in 2009 (and every year thereafter), at the University of Venice in 2009, at the The CHR Working Week 2009, First CHR Summer School 2010 , Second CHR Summer School 2011, 3rd CHR Summer School 2013.

400+ Slides accompanying the book

CHR book Chapter 1
CHR book Chapter 2 (2015)
CHR book Chapter 3
CHR book Chapter 4
CHR book Chapter 5
CHR book Chapter 6 (extended version, 2021)
CHR book Chapter 7

Practical Lab Course

A CHR course should be combined with a practical lab course. The book contains 55 exercises, here are some of the book and some new ones:

CHR Cheat Sheet, 2012.
CHR Exercises, 2014.
CHR Exercises, 2013.
CHR Exercises, 2012.
CHR Exercises, 2009: Exercise 1, Exercise 2, Exercise 3, Exercise 4, Exercise 5.
CHR CP Exercises, 2009: Exercise 2, Exercise 3, Exercise 4 (, Exercise 5, Exercise 6 (, Exercise 7 (
CHR CP Exercises, 2006: Exercise 5, Exercise 6, Exercise 7, Exercise 8, Exercise 9, Exercise 10, Exercise 11, Exercise 12, Exercise 13.

CHR Example Programs

KU Leuven CHR
SWI-Prolog CHR
Javascript CHR

Constraint Handling Rules (CHR) Tutorials and Links

Wikipedia on CHR
CHR Summary (pdf, 2 pages) "The story so far"
CHR Tutorial Slides (pdf, Thom Fruehwirth)
CHR Tutorial Slides (pdf, Tom Schrijvers)
CHR Keynote Talk Slides (pdf, Thom Frühwirth)
More CHR Tutorials...
Javascript JIT CHR Compiler and Online CHR Demo Tool
Book excerpt: First Steps in CHR (pdf)
Welcome to Constraint Handling Rules (pdf)
Programming in Constraint Handling Rules (pdf)
CHR survey, Update to CHR survey
Constraint Handling Rules (CHR) bibliography and news blog
All you ever wanted to know about CHR (up to 2014)
SwishCHR. Test-Drive CHR. Run CHR online now! (replacing WebCHR)
Recent Research of Thom Fruehwirth on Constraint Handling Rules (CHR).

Thom Frühwirth, updated March 11, 2022