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.

REFERENCES

• 1: S. Abdennadher. Operational semantics and confluence of constraint propagation rules. In Proc. of CP'97, LNCS, pages 252--266. Springer-Verlag, 1997.
• 2: Common CHR implementations, http://www.cs.kuleuven.ac.be/~dtai/projects/CHR.
• 3: G. J. Duck, P. J. Stuckey, M. J. García de la Banda, and C. Holzbaur. The Refined Operational Semantics of Constraint Handling Rules. In Proc of ICLP'04, pages 90--104, 2004.
• 4: G. J. Duck, P. J. Stuckey, and M. Sulzmann. Observable confluence for constraint handling rules. Technical Report CW 452, Katholieke Universteit Leuven, 2006. Proc. of CHR 2006, Third Workshop on Constraint Handling Rules.
• 5: T. Frühwirth. Constraint handling rules. In Constraint Programming: Basics and Trends, LNCS. Springer-Verlag, 1995.
• 6: T. Frühwirth. Parallelizing union-find in Constraint Handling Rules using confluence analysis. In Proc. of ICLP '05, volume 3668 of LNCS, pages 113--127. Springer-Verlag, 2005.
• 7: Thom Frühwirth, Constraint handling rules: the story so far, Proceedings of the 8th ACM SIGPLAN symposium on Principles and practice of declarative programming, p.13-14, July 10-12, 2006, Venice, Italy [doi>10.1145/1140335.1140337]
• 8: Glasgow haskell compiler home page, http://www.haskell.org/ghc/.
• 9: Tim Harris , Simon Marlow , Simon Peyton-Jones , Maurice Herlihy, Composable memory transactions, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065952]
• 10: S. Peyton Jones, editor. Haskell 98 Language and Libraries: The Revised Report. Cambridge University Press, 2003.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Constraint and logic languages

General Terms:
Algorithms, Languages

Keywords:
parallel implementation of concurrent language