The Monadic Constraint Programming Framework

Overview

The aim of this project is to model the generic aspects of Constraint Programming in Haskell. Of particular interest is the solver-independent framework for composable search strategies. This project involves also Peter Stuckey and Phil Wadler.

In the second phase of the project, Pieter Wuille and I are developing a layer in the framework for Finite Domain constraint solvers. Of particular interest here is the Gecode C++ backend.

Downloads

• Get the Cabal package on Hackage.

Publications

• Monadic Constraint Programming with Gecode, Ph.D. project of Pieter Wuille
  • Expressive Models for Monadic Constraint Programming, P. Wuille, T. Schrijvers. Accepted at ModRef 2010. [draft]
  • Finite Domain modeling and solving in the Monadic Constraint Programming framework, P. Wuille, T. Schrijvers. Abstract at ORBEL24.
  • Parameterized Models for On-line and Off-line Use, P. Wuille, T. Schrijvers. Presented at WFLP 2010. [paper pdf]
  • Monadic Constraint Programming with Gecode, P. Wuille, T. Schrijvers. Presented at ModRef 2009. [paper pdf] [slides pdf] [Details] [Hide details]

    This paper presents FD-MCP, a finite domain modeling language on top of the Monadic Constraint Programming framework for Haskell. FD-MCP leverages Haskell's rich static type system and powerful abstraction mechanisms for implementing syntactic sugar, model transformations and compilation to solver backends. Two backends are provided: a basic Haskell solver and a Gecode code generator. Our benchmarks establish that FD-MCP models are much more concise than hand-coded Gecode programs, more so when using disjunction, without sacrificing performance..

• Monadic Constraint Programming, T. Schrijvers, P. Stuckey, P. Wadler. Published in the Journal of Functional Programming. [draft pdf]
  • Monadic Constraint Programming, T. Schrijvers, presented at WLP 2009, AngloHaskell 2009, Oxford University, Cambridge University and University of Kent. [slides]
  • First Class Constraint Programming in Haskell, T. Schrijvers, P. Stuckey, P. Wadler. Work in progress presented at SingHaskell, November 28, 2007. [slides] [Details] [Hide details]

    We report on our Constraint Logic Programing framework for Haskell. The core concept of the framework is the search tree, which is explored by primitive search strategies. A primitive search strategy is defined by a queue datatype and can be extended by a search transformer. Moreover, multiple search transformers can be composed to obtain quite complex behavior. Note that our framework is generic in the underlying constraint solver, and in particular works for both backtracking and copying-based solvers.