[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