implementing type inference

I found the following resources helpful for understanding type inference, in order of increasing difficulty:

1. Chapter 30 (Type Inference) of the freely available book PLAI, Programming Languages: Application and Interpretation, sketches unification-based type inference.
2. The summer course Interpreting types as abstract values presents elegant evaluators, type checkers, type reconstructors and inferencers using Haskell as a metalanguage.
3. Chapter 7 (Types) of the book EOPL, Essentials of Programming Languages.
4. Chapter 22 (Type Reconstruction) of the book TAPL, Types and Programming Languages, and the corresponding OCaml implementations recon and fullrecon.
5. Chapter 13 (Type Reconstruction) of the new book DCPL, Design Concepts in Programming Languages.
6. Selection of academic papers.
7. Closure compiler’s TypeInference is an example of the data-flow analysis approach to type inference, which is better suited to dynamic languages that the Hindler Milner approach.

However, since the best way to learn is to do, I strongly suggest implementing type inference for a toy functional language by working through a homework assignment of a programming languages course.

I recommend these two accessible homeworks in ML, which you can both complete in less than a day:

1. PCF Interpreter (a solution) to warm up.
2. PCF Type Inference (a solution) to implement algorithm W for Hindley-Milner type inference.

These assignments are from a more advanced course:

1. Implementing MiniML

2. Polymorphic, Existential, Recursive Types (PDF)

3. Bi-Directional Typechecking (PDF)

4. Subtyping and Objects (PDF)