On Mon, Jul 19, 2010 at 01:51:52PM -0300, José Romildo Malaquias wrote:
data Exp = IntExp Integer | VarExp Symbol | AssignExp Symbol Exp | IfExp Exp Exp (Maybe Exp) | CallExp Symbol [Exp] | LetExp [Dec] Exp
data Dec = TypeDec Symbol Ty | FunctionDec Symbol [(Symbol,Symbol)] (Mybe Symbol) Exp | VarDec Symbol (Maybe Symbol) Exp
Expressions can have type annotations, but declarations can not.
Hi, my favorite solution to this is using two level types. They don't only allow annotating the AST with information, but also allow things like generic unification over terms or hash consing for trivial CSE. As an example, you would translate. your thing to
data Exp e = IntExp Integer | VarExp Symbol | AssignExp Symbol e | IfExp Exp Exp (Maybe e) | CallExp Symbol [e] | LetExp [Dec e] e
data Dec e = TypeDec Symbol Ty | FunctionDec Symbol [(Symbol,Symbol)] (Maybe Symbol) e | VarDec Symbol (Maybe Symbol) e
we simply replace the recursive argument 'Exp' with a type parameter. Now, to create an unannotated version of the AST
newtype Fix e = F (e (Fix e)) type SExp = Fix Exp
now if you want to annotate each node with something,
data FixAnnotated a e = FA a (e (FixAnnotated a e)) type ExpTy = TypeAnnotated Ty Exp
but you can do much more interesting things, imagine you want to do common subexpression elimination on your whole program, using a hash table of subterms to identify when the same thing is calculated more than once. You could do something like
newtype FixHash e = FixHash (e Int)
notice our recursive parameter is just an 'Int' this will be the index into the table of the given subexpresion. You can write a wholely geneic CSE pass that does not even know about the structure of your terms! for more advanced things like a fully generic unification, see the following paper. In addition to the two-level types trick, the paper talks about parameterized classes, though I wouldn't recommend them so much, a useful trick sure, but not really essential for this task. the two level type stuff is golden though. unify: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.8205 I have attached a utility module I use for two level types, feel free to modify it for your needs. John -- John Meacham - ⑆repetae.net⑆john⑈ - http://notanumber.net/