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
"...one 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.
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.
Preface 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 Bibliography
List of figures
List of illustrations
Index.
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
