How do purely functional compilers annotate the AST with type info?

Question

In the syntax analysis phase, an imperative compiler can build an AST out of nodes that already contain a type field that is set to null during construction, and then later, in the semantic analysis phase, fill in the types by assigning the declared/inferred types into the type fields.

How do purely functional languages handle this, where you do not have the luxury of assignment? Is the type-less AST mapped to a different kind of type-enriched AST? Does that mean I need to define two types per AST node, one for the syntax phase, and one for the semantic phase?

Are there purely functional programming tricks that help the compiler writer with this problem?

Answer 1

I usually rewrite a source (or an already several steps lowered) AST into a new form, replacing each expression node with a pair (tag, expression).

Tags are unique numbers or symbols which are then used by the next pass which derives type equations from the AST. E.g., a + b will yield something like { numeric(Tag_a). numeric(Tag_b). equals(Tag_a, Tag_b). equals(Tag_e, Tag_a).}.

Then types equations are solved (e.g., by simply running them as a Prolog program), and, if successful, all the tags (which are variables in this program) are now bound to concrete types, and if not, they're left as type parameters.

In a next step, our previous AST is rewritten again, this time replacing tags with all the inferred type information.

The whole process is a sequence of pure rewrites, no need to replace anything in your AST destructively. A typical compilation pipeline may take a couple of dozens of rewrites, some of them changing the AST datatype.

Answer 2

There are several options to model this. You may use the same kind of nullable data fields as in your imperative case:

data Exp = Var Name (Maybe Type) | ...
parse :: String -> Maybe Exp     -- types are Nothings here
typeCheck :: Exp -> Maybe Exp    -- turns Nothings into Justs

or even, using a more precise type

data Exp ty = Var Name ty | ...
parse :: String -> Maybe (Exp ())
typeCheck :: Exp () -> Maybe (Exp Type)