[Haskell-cafe] Tiger compiler in Haskell: annotating abstract syntax tree

[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

[Job Vranish]

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-position-information-to-a-datatype/

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

Post by 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.
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
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Job Vranish]

Ah, I found the attachment on your other email.

I would recommend using the Fix and Ann types, instead of the AnnFix type.

I modified your code a bit (and fixed the Show instances etc...) and put it
here:
http://hpaste.org/fastcgi/hpaste.fcgi/view?id=27823#a27823

Let me know if you have questions about it.

- Job
<http://hpaste.org/fastcgi/hpaste.fcgi/view?id=27823#a27823>

I didn't get any attachments from you, but haskell-cafe might filter them
out (I'm not sure).
But, the usual derived instances for Show should work fine for your
expression and annotation types.
instance (Show (f (Fix f))) => Show (Fix f) where
show (Fix a) = show "Fix " ++ show a
{-# LANGUAGE FlexibleContexts, UndecidableInstances #-}
- Job

Post by Job Vranish

Post by Job Vranish
Martijn van Steenbergen has a good blog post that describes the method I

http://martijn.van.steenbergen.nl/journal/2010/06/24/generically-adding-position-information-to-a-datatype/

Post by Job Vranish
In his example he annotates the expression tree with position

information,

Post by Job Vranish
but you can use the same method to add type annotations, or whatever you
want.

After a quick read at Martijn blog article I've written the attached
test program, which works.
But I am not succeeding in deriving Show for the data types. Any help?
Romildo

Post by Job Vranish

Post by 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

Post by Job Vranish

Post by José Romildo Malaquias
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

Post by Job Vranish

Post by José Romildo Malaquias
phases of compilation.
The type checker would annotate the abstract syntax tree (ast) with

type

Post by Job Vranish

Post by José Romildo Malaquias
annotations, that could be used later by the translater to

intermediate

Post by Job Vranish

Post by José Romildo Malaquias
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.
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?

[Malcolm Wallace]

I would be inclined to add type annotations as an extra constructor of
the expression representation type.

Post by José Romildo Malaquias
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

[a***@spamcop.net]

G'day all.

Post by 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

[José Pedro Magalhães]

Hi José,

Post by 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.
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

Post by José Romildo Malaquias
Regards,
Romildo
--
Computer Science Department
Universidade Federal de Ouro Preto, Brasil
_______________________________________________
Haskell-Cafe mailing list
http://www.haskell.org/mailman/listinfo/haskell-cafe

[José Romildo Malaquias]

Post by José Pedro Magalhães

Post by 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.

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

[José Pedro Magalhães]

Hi Romildo,

Post by José Romildo Malaquias

Post by José Pedro Magalhães

Post by 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.

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

Post by José Romildo Malaquias
Romildo

[o***@okmij.org]

Post by 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.

There is also a general way of annotating AST post factum, described in
http://okmij.org/ftp/Algorithms.html#tree-annot

The method lets one attach arbitrarily many annotations to an already
built AST, *without* the need to change the definition of the
datatype. One does not even have to anticipate annotations! The method
would work with your AST

Post by José Romildo Malaquias
data Exp
= IntExp Integer
| VarExp Symbol
| AssignExp Symbol Exp

as _it is_, without any modifications -- neither to the data type
definition, nor to the tree.

The method was demonstrated when writing a compiler of sorts:
annotating an AST with an inferred type for each node. If the type
inference fails, we can still print out the inferred types for the
good subexpressions.

[José Pedro Magalhães]

Hi Oleg,

[o***@okmij.org]

Jose Pedro Magalhaes wrote:

[José Pedro Magalhães]

Hi Oleg,

[S. Doaitse Swierstra]

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

Post by 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.
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
http://www.haskell.org/mailman/listinfo/haskell-cafe

[John Meacham]

Post by José Romildo Malaquias
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

Post by José Romildo Malaquias
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

Post by José Romildo Malaquias
newtype Fix e = F (e (Fix e))
type SExp = Fix Exp

now if you want to annotate each node with something,

Post by José Romildo Malaquias
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

Post by José Romildo Malaquias
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/