Peter Van Weert is defending his PhD thesis on "Extension and Optimising Compilation of Constraint Handling Rules". The public defence takes places on May 26 2010 at 14:00 in Caste Arenberg in Heverlee. The presentation will be in Dutch. Afterwards, there will be a free reception in the salons of the castle.
More information and directions to the castle can be found on http://people.cs.kuleuven.be/~peter.vanweert/phd/
Abstract
Constraint Handling Rules (CHR) is a high-level declarative programming language based on multi-headed multiset rewrite rules, combined with aspects of logic and constraint programming. Originally designed for extending a host language with user-defined constraint solvers, CHR has evolved into a powerful, elegant general-purpose language with a wide spectrum of application domains.
The goal of this dissertation is to further improve the practical usability of the CHR programming language. As a first step, we therefore redesign the language's syntax, language features, and operational semantics to allow a more high-level, declarative programming style. Our streamlined CHR2 syntax allows for more natural, readable, and concise rule definitions. The operational semantics of CHR2 programs is designed to be as non-deterministic as possible, while still facilitating the effective execution control required for practical programming. In line with the ‘what, not how’ and ‘algorithm = logic + control’ maxims of declarative programming, the CHR2 system by default fully determines the execution strategy. When needed though, the programmer may control the order in which rules and conjunctions are executed using two orthogonal, familiar execution control constructs: rule priorities and sequential conjunction. Priorities are specified using symbolic priority constraints, which are more flexible than earlier proposals, and offer a better separation of logic and control.
We furthermore extended CHR with expressive language abstractions called aggregates. Aggregates are powerful, concise rule applicability conditions that collect information from larger parts of the constraint store. Well-known examples include min, sum, count, and findall. Our proposed framework supports nested aggregate expressions, efficient incremental aggregate computation and application-tailored user-defined aggregates. Aggregates eliminate the need for low-level encodings of aggregate computations commonly found in CHR programs. The extended CHR language thus fully regains its high-level, declarative nature.
A next crucial aspect of the practical usability of any programming language is the performance of its implementations. Because CHR2 rules are written at a very high level of abstraction, uncovering the optimal low-level execution steps required to evaluate them is very challenging. In the final part of the dissertation, we therefore introduce, evaluate and refine many new and existing analyses and optimisation techniques for CHR programs. Two instances are discussed in more detail: We revise CHR's compilation scheme to optimise the space consumption of recursive programs, and develop novel techniques for optimal—both in space and in time—reapplication prevention of CHR propagation rules.
Lastly, for CHR to be really useful for practical applications, CHR must be embedded in a mainstream host language. We therefore developed K.U.Leuven JCHR, a state-of-the-art CHR system for Java. The thesis addresses both the language design issues of integrating CHR with imperative host languages, and the technical challenges faced when compiling CHR to imperative languages. JCHR is currently one of the most complete and efficient CHR implementations available, typically outperforming other rule-based systems by several orders of magnitude. The next-generation JCHR2 system moreover is a first reference implementation of the improved CHR2 language, extended with negation as absence.