Tiger compiler in Haskell: annotating abstract syntax tree
Hello. In his book "Modern Compilder Implementation in ML", Appel presents a compiler project for the Tiger programming language where type checking and intermediate code generation are intrinsically coupled. There is a function transExp :: Absyn.Exp -> (Tree.Exp,Types.Type) that do semantic analysis, translating an expression to the Tree intermediate representation language and also do type checking, calculating the type of the expression. Maybe the compiler can be made more didatic if these phases are separate phases of compilation. The type checker would annotate the abstract syntax tree (ast) with type annotations, that could be used later by the translater to intermediate representation. In an imperative language probably each relevant ast node would have a field for the type annotation, and the type checker would assign the type of the node to this field after computing it. I am writing here to ask suggestions on how to annotate an ast with types (or any other information that would be relevant in a compiler phase) in Haskell. As an example, consider the simplified ast types: 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. Comments? Regards, Romildo -- Computer Science Department Universidade Federal de Ouro Preto, Brasil
Martijn van Steenbergen has a good blog post that describes the method I
generally use:
http://martijn.van.steenbergen.nl/journal/2010/06/24/generically-adding-posi...
In his example he annotates the expression tree with position information,
but you can use the same method to add type annotations, or whatever you
want.
- Job
2010/7/19 José Romildo Malaquias
Hello.
In his book "Modern Compilder Implementation in ML", Appel presents a compiler project for the Tiger programming language where type checking and intermediate code generation are intrinsically coupled.
There is a function
transExp :: Absyn.Exp -> (Tree.Exp,Types.Type)
that do semantic analysis, translating an expression to the Tree intermediate representation language and also do type checking, calculating the type of the expression.
Maybe the compiler can be made more didatic if these phases are separate phases of compilation.
The type checker would annotate the abstract syntax tree (ast) with type annotations, that could be used later by the translater to intermediate representation.
In an imperative language probably each relevant ast node would have a field for the type annotation, and the type checker would assign the type of the node to this field after computing it.
I am writing here to ask suggestions on how to annotate an ast with types (or any other information that would be relevant in a compiler phase) in Haskell.
As an example, consider the simplified ast types:
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.
Comments?
Regards,
Romildo -- Computer Science Department Universidade Federal de Ouro Preto, Brasil _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
I would be inclined to add type annotations as an extra constructor of the expression representation type.
data Exp = IntExp Integer | VarExp Symbol | AssignExp Symbol Exp | IfExp Exp Exp (Maybe Exp) | CallExp Symbol [Exp] | LetExp [Dec] Exp
| Exp `HasType` Ty This is particularly useful if the source language allows arbitrary type annotations on expressions, because it can cover both the user- supplied annotations, and the compiler-inferred ones. Also, your type inference phase is free to add as many or as few annotations into the AST as it wishes - they are not required everywhere. Regards, Malcolm
G'day all.
Quoting José Romildo Malaquias
I am writing here to ask suggestions on how to annotate an ast with types (or any other information that would be relevant in a compiler phase) in Haskell.
This might help: http://www.haskell.org/haskellwiki/Indirect_composite Andrew Bromage
Hi José,
2010/7/19 José Romildo Malaquias
I am writing here to ask suggestions on how to annotate an ast with types (or any other information that would be relevant in a compiler phase) in Haskell.
As an example, consider the simplified ast types:
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.
Comments?
Indeed I would suggest the method described in our paper: Martijn van Steenbergen, José Pedro Magalhães, and Johan Jeuring. Generic selections of subexpressions. Paper link: http://dreixel.net/research/pdf/gss_draft.pdf Related hackage package: http://hackage.haskell.org/package/Annotations Something like what Malcolm proposed (adding one extra constructor) would also be possible generically, but it would be more similar to how we add meta-variables in our generic rewriting library (ask for more details if you're interested in this alternative). Cheers, Pedro
Regards,
Romildo -- Computer Science Department Universidade Federal de Ouro Preto, Brasil _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
On Tue, Jul 20, 2010 at 09:17:15AM +0200, José Pedro Magalhães wrote:
2010/7/19 José Romildo Malaquias
I am writing here to ask suggestions on how to annotate an ast with types (or any other information that would be relevant in a compiler phase) in Haskell.
Indeed I would suggest the method described in our paper:
Martijn van Steenbergen, José Pedro Magalhães, and Johan Jeuring. Generic selections of subexpressions. Paper link: http://dreixel.net/research/pdf/gss_draft.pdf Related hackage package: http://hackage.haskell.org/package/Annotations
Annotations-0.1 requires base ==4.1.* and parsec ==3.0.*, but I have base-4.2.0.2 and parsec-3.1.0 on my Gentoo Linux system. Would it work with these new versions of base and parsec? Romildo
Hi Romildo,
2010/7/23 José Romildo Malaquias
On Tue, Jul 20, 2010 at 09:17:15AM +0200, José Pedro Magalhães wrote:
2010/7/19 José Romildo Malaquias
I am writing here to ask suggestions on how to annotate an ast with types (or any other information that would be relevant in a compiler phase) in Haskell.
Indeed I would suggest the method described in our paper:
Martijn van Steenbergen, José Pedro Magalhães, and Johan Jeuring. Generic selections of subexpressions. Paper link: http://dreixel.net/research/pdf/gss_draft.pdf Related hackage package: http://hackage.haskell.org/package/Annotations
Annotations-0.1 requires base ==4.1.* and parsec ==3.0.*, but I have base-4.2.0.2 and parsec-3.1.0 on my Gentoo Linux system. Would it work with these new versions of base and parsec?
Yes, that version has a problem with the constraints. I think they are too restrictive; probably base >= 4 && base < 4.3 would do. As for parsec, I am not sure, but at least you can easily get parsec-3.0.*, whereas base is more complicated. We will upload a new version soon to fix this. Cheers, Pedro
Romildo
Despite the interesting discussing which has followed this question I think that in orde to approach this specific problem the use of a specific compiler-writers toolset such as the uuagc (http://hackage.haskell.org/package/uuagc-0.9.29)) system is to be preferred; it provides aneffiicent and modular way of constructing sch complicated compositions. The complete Utrecht haskell compiler is constructed in this way. Doaitse 1) If you are brave hearted you may try to use the http://hackage.haskell.org/package/AspectAG road ;-} 2) If you are interested in an (albeit old) Tiger compiler built using uuagc see: http://hackage.haskell.org/package/tiger On 19 jul 2010, at 18:51, José Romildo Malaquias wrote:
Hello.
In his book "Modern Compilder Implementation in ML", Appel presents a compiler project for the Tiger programming language where type checking and intermediate code generation are intrinsically coupled.
There is a function
transExp :: Absyn.Exp -> (Tree.Exp,Types.Type)
that do semantic analysis, translating an expression to the Tree intermediate representation language and also do type checking, calculating the type of the expression.
Maybe the compiler can be made more didatic if these phases are separate phases of compilation.
The type checker would annotate the abstract syntax tree (ast) with type annotations, that could be used later by the translater to intermediate representation.
In an imperative language probably each relevant ast node would have a field for the type annotation, and the type checker would assign the type of the node to this field after computing it.
I am writing here to ask suggestions on how to annotate an ast with types (or any other information that would be relevant in a compiler phase) in Haskell.
As an example, consider the simplified ast types:
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.
Comments?
Regards,
Romildo -- Computer Science Department Universidade Federal de Ouro Preto, Brasil _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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/
participants (7)
-
ajb＠spamcop.net -
Job Vranish -
John Meacham -
José Pedro Magalhães -
José Romildo Malaquias -
Malcolm Wallace -
S. Doaitse Swierstra