Lambda the Ultimate

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.

If you have a language with extensible records (like those of Gaster and Jones), and you view functions like a -> Maybe { r } for some row r as patterns, are there practical obstacles that prevent you from extending the environment of a case alternative with the row of the result type of its controlling pattern?

I would appreciate pointers to anywhere that this is discussed in the literature, or an explanation of why it is a bad idea. Google hasn't been especially helpful.

-- concrete syntax for records is entirely made-up

wildcard_pattern = const Just {}

-- without first class labels, the compiler would have to make a whole family
-- of declarations like this, one for each variable bound by a pattern
variable_pattern_x val = Just { x := val }

-- same comment applies
as_pattern_x pat val = case pat val of
                         Just rec -> { x := val, rec }
                         Nothing -> Nothing

-- I'm not 100% sure that this handles laziness correctly, but you get the idea
-- declarations like this would be automatically generated from the datatype declarations
cons_pattern pat_head pat_tail [] = Nothing
cons_pattern pat_head pat_tail (x:xs) = case pat_head x of
                                          Just rec_head -> case pat_tail xs of
                                                             Just rec_tail -> record_join rec_head rec_tail
                                                             Nothing -> Nothing
                                          Nothing -> Nothing

nil_pattern [] = Just {}
nil_pattern _ = Nothing