[Haskell-cafe] combinators for a simple grammar

[Stefan O'Rear]

On Mon, Aug 06, 2007 at 10:33:01PM -0400, Rahul Kapoor wrote:
> I am having problems coming up with nice combinators for a simple
> DSEL. The abstract syntax is simply given by the types:
> 
> data SearchCondition = SearchCondition BoolTerm | OpOr SearchCondition  BoolTerm
> 
> data BoolTerm = BoolTerm BoolFactor | OpAnd BoolTerm BoolFactor
> 
> data BoolFactor = Constant Bool
> 
> 
> My current combinators are
> 
> (.||.) :: SearchCondition -> BoolTerm -> SearchCondition
> (.||.) sc term = OpOr sc term
> 
> (.&&.) :: BoolTerm -> BoolFactor -> BoolTerm
> (.&&.) term fact = OpAnd term fact
> 
> which allow you to write expression of the form
> 
> factTrue = Constant True
> termTrue = BoolTerm factTrue
> scTrue = SearchCondition termTrue
> 
> sc = scTrue .||. termTrue .||. termTrue .&&. factTrue
> 
> I am wondering it it is possible to define combinators to hide the
> structure of the grammar from the user to some extent, so that the
> user can simply write things like
> 
> sc = True .||.True .||. True .&&. False
> 
> or
> 
> sc = const True .||. const True .||. const True .&&. const  False
> 
> That is the user does not have to worry about the distinction between
> terms and factors (which exists solely for precedence in this case).
> 
> Or is it a better idea to just remove the precedence rules from the
> types and move it the part of the code that evaluates the expressions?

I think it would be better still to remove it from both and rely on
Haskell's built-in precedence parser.

data SearchCondition = Constant Bool
                     | SearchCondition :||: SearchCondition
                     | SearchCondition :&&: SearchCondition

infixr 3 :&&:
infixr 2 :||:

true = Constant True
false = Constant False

sc = true :||: true :||: true :&&: false

eval (Constant k) = k
eval (l :||: r) = eval l || eval r
eval (l :&&: r) = eval l && eval r

You can still hide the constructors if you want, of course.

Another idea is to directly represent search conditions as functions:

type SearchCondition = Object -> Bool
-- could be just Bool to match your example, but I imagine you were
-- simplifying, and making the leap from Bool to Object -> Bool is
-- not always obvious

(.||.) sc1 sc2 x = sc1 x || sc2 x
(.&&.) sc1 sc2 x = sc1 x && sc2 x
true x = True
false x = False

infixr 3 .&&.
infixl 2 .||.

-- eval is not needed!  You can just apply a search condition to an
-- object.  The downside of this is that applying is *all* you can do,
-- you can't optimize or analyze like you can with the explicit
-- approach.

Stefan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20070806/43a8908e/attachment.bin