[Haskell-cafe] Thoughts on program annotations.

[wren ng thornton]

On 3/4/11 1:32 AM, Jason Dusek wrote:
>    Hi List,
>
>    I am working on a Bash config generation system. I've decided
>    to factor out the Bash AST and pretty printer, here in a
>    pre-release state:
>
>      https://github.com/solidsnack/bash

Awesome!

>    Given that every statement has an annotation, it seemed better
>    to me to use mutually recursive datatypes, using one datatype
>    to capture "annotatedness", like this:
>
>      --  From https://github.com/solidsnack/bash/blob/c718de36d349efc9ac073a2c7082742c45606769/hs/Language/Bash/Syntax.hs
>
>      data Annotated t = Annotated t (Statement t)
>      data Statement t = SimpleCommand Expression [Expression]
>                       | ...
>                       | IfThen (Annotated t) (Annotated t)
>                       | ...
>
>    I wonder what folks think of this approach?

This is the same basic approach used by Tim Sheard:

     http://web.cecs.pdx.edu/~sheard/papers/JfpPearl.ps
     http://web.cecs.pdx.edu/~sheard/papers/generic.ps

and I think it works pretty well for this kind of problem. One change 
I'd make is to use something like this definition instead:

     data Annotated a
         = NewAnn   a (Statement a)
         | MergeAnn a (Statement a)

where the annotation of MergeAnn is merged with the previous annotation 
up the tree (via mappend), thus allowing for annotations to be inherited 
and modified incrementally based on the Monoid instance; whereas the 
NewAnn constructor uses the annotation directly, overriding any 
contextual annotations. This can be helpful to reduce the amount of 
duplication in the AST, though how helpful will depend on how you plan 
to use/generate the ASTs.

-- 
Live well,
~wren