Damas-Hindley-Milner type inference algorithm implementation

Question

I'm looking for information about the well-known Damas-Hindley-Milner algorithm to do type inference for functional languages, especially information about implementation.

I already know how to do the Algorithm W, but I heard about recent new algorithms based on constraint generator/solver rather than usual unification. However, I can't manage to find any discussions about the implementation of those new algorithm.

Any idea where I could find some partial information on ML inference ?

Answer 1

If you're comfortable with ML code, the best way to find these things is to simply look into the implementations in the wild. A good reference implementation is HaMLet, which is designed as more of a test platform rather than a production implementation.

Almost all serious recent discussion of these issues is going to be in scholarly venues. One paper that might be of interest is Generalising Hindley-Milner type inference algorithms.

Also, the implementations of various type systems (including let polymorphism) in Pierce's "Types and Programming Languages", as well as Appel's "Modern Compiler Implementation in ML" more closely match modern approaches to implementing this than the vanilla description of algorithm W.