When writing an interpreter, how should the type inference algorithm change the parsed AST? Should it? Or parsing and inference are done necessarily simultaneously?

I have implemented a strongly typed functional language interpreter, in which each function can be declared only one time (i.e., with no signature variants). As soon as the non-typed implementation parser was concluded and working, I have written the type inference algorithm, feeded by the parser's resulting AST.

Hindley-Damas-Milner is working like a charm, but the program use it and if the type checking passes, it just forgets about the matter and pass the AST to the interpreter. To the moment, the "target language" (i.e., the one in which the interpreter is written) have satisfied the interpreter type needs, but I am wondering if this approach is usual: to discard all the type inference fruits after an "ok" result.

Also, would writing a compiler instead of an interpreter make any difference is this sense?

  • ps. I chose the term "type inference" because despite being, at the moment, a "type checking task" the user don't need to, actually, cannot declare types explicitly.
    – dawid
    Commented Jun 19, 2013 at 6:02
  • It's common to rewrite an AST in two steps, e.g., replace each expression node with a pair expression = tag * oldexpression, generate and solve your type equations against all the tags, and rewrite an AST again into expression = type * oldexpression.
    – SK-logic
    Commented Jun 19, 2013 at 7:18
  • What is the functional way to rewrite (or even just copy) an AST?
    – dawid
    Commented Jun 19, 2013 at 13:46
  • I have found something: a map with ids.
    – dawid
    Commented Jun 19, 2013 at 13:58
  • 1
    just rebuild an AST with each transform, it's cheap and purely functional.
    – SK-logic
    Commented Jun 19, 2013 at 14:48

1 Answer 1


No, it is definitely not the usual to throw away good analysis results. For a stark difference you may want to check out the Scala compiler. It is based on execution phases and you can add plugins which will be executed after certain phases. It is particularly interesting to place your plugin after the typing phase, because that gives you all of the inferred types in a very handy way.

The AST, however, is not so much changed as it is annotated. The basic structure of your statements, expressions, function definitions, etc. that are held in your AST do remain unchanged of course. What you really do during type inference is to annotate the tree nodes with their respective types.

For example, before typing inference ran you would have an AST with a function node for the function f, that is located somewhere within the AST and has some child nodes, which resemble arguments and statements/expressions. During type inference you determine the types of these child nodes, i.e. of the statements/expressions, and from them you determine the type of the function f. Now you could be satisfied detecting, that f is returning an int and it is only ever used in places, where int is used, but there is no reason to lose this information.

As for interpreter vs compiler, there are huge benefits from having types annotated to your AST, which go far beyond that. Consider for example IDEs.. plugin authors are very thankful for having a type-annotated AST available. It is so much more efficient to simply know that f returns an int, when you want to implement code completion, instead of having to run type inference yet again.

You may want to extend your language at one point. If the extension is anywhere past the type inference, you typically need to rely on its results. For example, consider adding type-safe macros, or some kind of semantic checks.

In summary: Type information in a strongly typed lanugage is so important, that it resembles blasphemy if you perform type inference only to throw away its results. You rob yourself and others of information that is both, extremely powerful when available, and rather costly to generate.

  • Great explanation! The IDE and extension parts can be important in the future. Maybe my problem is that I had based my parser and my inferencer from two different sources and end up with an AST for each one. With immutability all over my Scala code, I don't think it would be easy to add type annotation and avoid creating a second AST. Oh, it is not a total blasphemy, as you know, types are at least checked and nice messages given to the user, refusing going to go runtime..
    – dawid
    Commented Jun 19, 2013 at 6:19
  • To clarify: one AST is made of expressions (Expr, List etc.). The other is made of types (much of the statements like assignments become EmptyType after analysed). My HDMilner gets the first and converts to the second, but focusing in return types. Second AST is the first AST overly simplified only to typing needs.
    – dawid
    Commented Jun 19, 2013 at 6:23
  • As the ASTs should match in their syntactic structure, it should be straightforward to create an immutable typed-AST that simply references them both (immutable structure sharing and all that)
    – Frank
    Commented Jun 19, 2013 at 6:32
  • Ok, I can stop converting the parsed AST to AST-type like in: case NumE(n) => NumberT and in case CharE(s) => CharT and apply HDMilner directly to an annotable AST.
    – dawid
    Commented Jun 19, 2013 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.