Home » forums » LtU Forum

Monadic Constraint Programming

Monadic Constraint Programming by Tom Schrijvers, Peter Stuckey and Philip Wadler.
A constraint programming system combines two essential components: a constraint solver and a search engine. The constraint solver reasons about satisfiability of conjunctions of constraints, and the search engine controls the search for solutions by iteratively exploring a disjunctive search tree defined by the constraint program. In this paper we give a monadic definition of constraint programming where the solver is defined as a monad threaded through the monadic search tree. We are then able to define search and search strategies as first class objects that can themselves be built or extended by composable search transformers. Search transformers give a powerful and unifying approach to viewing search in constraint programming, and the resulting constraint programming system is first class and extremely flexible.
By Greg Buchholz at 2009-06-03 22:27 | LtU Forum | previous forum topic | next forum topic | other blogs | 7117 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Great stuff

Wow, this is great stuff. A mature version of this, with the extension to CHR discussed in section 10, would be extremely useful for compiler development.

(Seems like good front page material?)

By Douglas McClean at Wed, 2009-06-03 23:24 | login or register to post comments

Monadic Constraint Programming

This is a very good paper, and the field of logic programming has much to offer to future mainstream programming languages - certainly to their compilers, and perhaps even to runtimes.

For example, the advanced typeclass extensions in Haskell effectively give you a compile-time Prolog interpretter, minus non-logical features like cuts. Every time you instantiate a typeclass, you initiate a backtracking search for a solution.

Of course, Haskell typeclasses are designed so they're always instantiated statically. But if you extended the language further, to allow more dynamic type-casting functionality, you would need to carry out that backtracking search at runtime. And if you did that, you could also support first-class joins, a la McAllester's Ontic language.

A while ago, learning Haskell greatly helped me (a C++ programmer) to distinguish between aspects of programming which are fundamentally hard, and aspects which are only hard because of C++'s limitations. But learning logic programming -- at the implementation level as much as the language level -- makes me realize that even Haskell has shortcomings in expressiveness.

Also, read up on Concurrent Constraint Logic Programming for more advancements in the field. But ignore the Wikipedia article, which misconstrues it.

By Tim Sweeney at Thu, 2009-06-04 03:15 | login or register to post comments