[Haskell-cafe] Haskell-Cafe Digest, Vol 174, Issue 13

Doaitse Swierstra doaitse at swierstra.net
Tue Feb 13 21:14:50 UTC 2018

This pattern is quite common; even so common that over the years many systems have been constructed to support this way of programming. The original term was Attribute Grammars, a term invented by Donald Knuth.

The http://hackage.haskell.org/package/uuagc <http://hackage.haskell.org/package/uuagc> system supports programming in this way in Haskell; it allows you to compose the semantics of an AST in a compositional way. The Utrecht Haskell compiler was built with it.

If you do not want to use a separate system you may want to use the embedding of attribute grammars in Haskell; a bit more cumbersome, but interesting since the completeness of the attribute grammar is checked using the Haskell type system:

http://hackage.haskell.org/package/AspectAG <http://hackage.haskell.org/package/AspectAG>

The thesis of Marcos Viera describes the underlying system in great detail: https://dspace.library.uu.nl/handle/1874/269786


> Op 13 feb. 2018, om 1:38  heeft Mikhail Baykov <manpacket at gmail.com> het volgende geschreven:
> recursion-schemes package might do the trick. I wrote TH for it and
> somebody took care of getting it merged in. It should simplify some of
> this boilerplate.
>> I am looking for a solution to get rid of this silly boilerplate:
>> eval :: Ord var => Map var Bool -> Proposition var -> Bool
>> eval ctx prop = evalP $ fmap (ctx Map.!) prop
>>  where
>>    evalP = \case
>>        Var b -> b
>>        Not q -> not $ evalP q
>>        And p q -> evalP p && evalP q
>>        Or p q -> evalP p || evalP q
>>        If p q -> evalP p ==> evalP q
>>        Iff p q -> evalP p == evalP q
>> What I would like to do in essence is to replace the data constructors like so:
>> -- Not valid Haskell!! Can't pattern match on constructor only...
>> magic = \case
>>    Var -> id
>>    Not -> not
>>    And -> (&&)
>>    Or -> (||)
>>    If -> (==>)
>>    Iff -> (==)
>> compile = transformAST magic $ fmap (\case 'P' -> False; 'Q' -> True)
>>>>> compile (Iff (Not (And (Var 'P') (Var 'Q'))) (Or (Not (Var 'P')) (Not (Var 'Q'))))
>>            ((==) (not ((&&) (id True) (id False))) ((||) (not (id True)) (not (id False))))
>> Note how the compiled expression exactly mirrors the AST, so there should be some meta programming technique for this.
>> Does anyone have an idea how I can achieve this?
>> The full source code is here: https://gist.github.com/vimuel/7dcb8a9f1d2b7b72f020d66ec4157d7b
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20180213/98f31d5b/attachment.html>

More information about the Haskell-Cafe mailing list