Proceedings of the fifth Workshop on Constraint Handling Rules pages:3-17
Workshop on Constraint Handling Rules edition:5 location:Hagenberg, Austria date:14 July 2008
Multi-headed rules are essential for the expressiveness of Constraint
Handling Rules (CHR), but incur considerable performance overhead. Current
indexing techniques are often unable to address this problem---they require
matchings to have particular form, or offer good run-time complexity rather
than good absolute figures.
We introduce two lightweight program transformations, based on term
flattening, which improve the effectiveness of existing CHR indexing
techniques, in terms of both complexity and constant factors. We also
describe a set of complementary post-processing program transformations,
which considerably reduce the flattening overhead.
We compare our techniques with the current state of the art in CHR
compilation, and measure their efficacy in K.U.Leuven CHR and CHRd.