Extending arbitrary solvers with constraint handling rules

ABSTRACT

Constraint Handling Rules (CHRs) are a high-level committed choice programming language commonly used to write constraint solvers. While the semantic basis of CHRs allows them to extend arbitrary underlying constraint solvers, in practice, all current implementations only extend Herbrand equation solvers. In this paper we show how to define CHR programs that extend arbitrary solvers and fully interact with them. In the process, we examine how to compile such programs to perform as little recomputation as possible, and describe how to build index structures for CHR constraints that are modified automatically when variables in the underlying solver change. We report on the implementation of these techniques in the HAL compiler, and give empirical results illustrating their benefits.

REFERENCES

• 1: S. Abdennadher. Operational semantics and confluence of constraint propagation rules. In Gert Smolka, editor, Proceedings of the Third International Conference on Principles and Practice of Constraint Programming, pages 252--266, 1997.
• 2: Philippe Codognet , Daniel Diaz, Boolean constraint solving using CLP(FD), Proceedings of the 1993 international symposium on Logic programming, p.525-539, December 1993, Vancouver, British Columbia, Canada
• 3: María J. García de la Banda , Bart Demoen , Kim Marriott , Peter J. Stuckey, To the Gates of HAL: A HAL Tutorial, Proceedings of the 6th International Symposium on Functional and Logic Programming, p.47-66, September 15-17, 2002
• 4: Bart Demoen , Maria J. García de la Banda , Warwick Harvey , Kim Marriott , Peter J. Stuckey, An Overview of HAL, Proceedings of the 5th International Conference on Principles and Practice of Constraint Programming, p.174-188, October 11-14, 1999
• 5: T. Frühwirth. CHR home page. www.informatik.uni-muenchen.de/~fruehwir/chr/.
• 6: T. Frühwirth. Theory and practice of constraint handling rules. Journal of Logic Programming, 37(1--3):95--138, 1998.
• 7: Maria J. García de la Banda , David Jeffery , Kim Marriott , Nicholas Nethercote , Peter J. Stuckey , Christian Holzbaur, Building Constraint Solvers with HAL, Proceedings of the 17th International Conference on Logic Programming, p.90-104, November 26-December 01, 2001
• 8: Christian Holzbaur , Thom W. Frühwirth, Compiling Constraint Handling Rules into Prolog with Attributed Variables, Proceedings of the International Conference PPDP'99 on Principles and Practice of Declarative Programming, p.117-133, September 29-October 01, 1999
• 9: C. Holzbaur and T. Frühwirth. Constraint handling rules, special issue. Journal of Applied Artificial Intelligence, 14(4), 2000.
• 10: Christian Holzbaur , Maria J. García de la Banda , David Jeffery , Peter J. Stuckey, Optimizing Compilation of Constraint Handling Rules, Proceedings of the 17th International Conference on Logic Programming, p.74-89, November 26-December 01, 2001
• 11: JCK: Java constraint kit. http://www.pms.informatik.uni-muenchen.de/software/jack/index.html, 2002.
• 12: K. Marriott and P.J. Stuckey. Programming with Constraints: an Introduction. MIT Press, 1998.
• 13: M. Trick. mat.gsia.cmu.edu/COLOR/color.html.
• 14: Pascal Van Hentenryck, Constraint satisfaction in logic programming, MIT Press, Cambridge, MA, 1989

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Constraints
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Languages

Keywords:
compilation, constraint handling rules, constraint solvers