Monads and constraint satisfaction problems (CSP)

All, All this talk about Mathematica and a reference to monadic treatments of backtracking reminded me that a year ago i was involved in work on a Mathematica-like widget. At the time i noticed that a good deal of the structure underlying LP, SAT and other solvers was terribly reminiscent of comprehension-style monadic structure. i think i asked Erik Meijer if he knew of any work done on this and posted to LtU, but nobody seemed to have understood what i was mumbling about. So, let me try here: does anybody know of references for a monadic treatment of constraint satisfaction? BTW, i think this could have a lot of bang-for-buck because the literature i read exhibited two basic features: - the "standard" treatments (even by CS-types) are decidedly not compositional - the people in the field who face industrial strength csp problems report that they have to take compositional approaches because the problems are just too large otherwise (both from a human engineering problem as well as a computational complexity problem) Best wishes, --greg -- L.G. Meredith Managing Partner Biosimilarity LLC 505 N 72nd St Seattle, WA 98103 +1 206.650.3740 http://biosimilarity.blogspot.com

On Thu, May 31, 2007 at 10:42:57AM -0700, Greg Meredith wrote:
All,
All this talk about Mathematica and a reference to monadic treatments of backtracking reminded me that a year ago i was involved in work on a Mathematica-like widget. At the time i noticed that a good deal of the structure underlying LP, SAT and other solvers was terribly reminiscent of comprehension-style monadic structure. i think i asked Erik Meijer if he knew of any work done on this and posted to LtU, but nobody seemed to have understood what i was mumbling about. So, let me try here: does anybody know of references for a monadic treatment of constraint satisfaction?
It's not particularly monadic, but you might check out "Modular Lazy Search for Constraint Satisfaction Problems" http://cse.ogi.edu/PacSoft/publications/.../modular_lazy_search.pdf

At Thu, 31 May 2007 10:42:57 -0700, Greg Meredith wrote:
BTW, i think this could have a lot of bang-for-buck because the literature i read exhibited two basic features:
- the "standard" treatments (even by CS-types) are decidedly not compositional - the people in the field who face industrial strength csp problems report that they have to take compositional approaches because the problems are just too large otherwise (both from a human engineering problem as well as a computational complexity problem)
This paper describes a non-monadic, compositional method for solving CSPs: http://www.cse.ogi.edu/PacSoft/publications/2001/modular_lazy_search_jfp.pdf There is also the LogicT monad transformer: http://okmij.org/ftp/Computation/monads.html j.

At Thu, 31 May 2007 11:36:55 -0700, Jeremy Shaw wrote:
This paper describes a non-monadic, compositional method for solving CSPs:
http://www.cse.ogi.edu/PacSoft/publications/2001/modular_lazy_search_jfp.pdf
btw, there are multiple versions of this paper. This version includes a section on dynamic variable ordering, as well as some improvements to the other sections. j.
participants (3)
-
Brandon Michael Moore
-
Greg Meredith
-
Jeremy Shaw