Abstract

Constraint Handling Rules (CHR) is a multi-set rewriting language created in the early nineties. While originally designed for writing constraint solvers, the expressivity of its multi-headed rewrite rules has been appreciated in a wide range of applications: planning, type checking, business rules, ...

CHR implementation is an active topic of research. A stack-based compilation scheme allows for efficient compilation to conventional programming languages. Thanks to program analysis and appropriate indexing data structures for multi-headed matching, any algorithm can be implemented with optimal time and space complexity. As far as we know, this result has not been obtained in the pure fragment of other declarative language implementations.

This talk gives an overview of the CHR language, applications and interesting implementation results.

Tom Schrijvers is a post-doctoral researcher at the Department of Computer Science at the Catholic University of Leuven. He obtained his Ph.D. on “Analyses, Optimizations and Extensions of Constraint Handling Rules” in 2005 and is the lead developer of the K.U.Leuven CHR system, which is distributed with major Prolog systems.