A concurrent constraint handling rules implementation in Haskell with software transactional memory

Abstract

Constraint Handling Rules (CHR) is a concurrent committed-choice constraint logic programming language to describe transformations (rewritings) among multi-sets of constraints (atomic formulae). CHR is widely used in a range of applications spanning from type system design to artificial intelligence. However, none of the existing CHR implementations we are aware of exploits concurrency or parallelism explicitly. We give a concurrent CHR implementation using GHC (Glasgow Haskell Compiler) with support for Software Transactional Memory. We achieve some significant performance improvements compared to a single-threaded CHR implementation. We obtain a further speed-up, in some cases nearly close to the optimum of 100%, when running programs under under a dual-core processor architecture. Our results show that CHR can be implemented efficiently on a multi-core architecture. Copyright 2007 ACM.