Hindley Milner Type Inference
using the classical
algorithm or an extension thereof. Commonly used by
s like Haskell [
] or ML [
]. Languages with a Hindley-Milner type system have the important property that one can assign to every expression a unique "most general" type, the PrincipalType
It is frustratingly easy to extend a given type system in a way that makes type inference undecidable or ambiguous;
, by contrast, is provably decideable. It is guaranteed to complete its type inference proof in finite (and pragmatically fast) time, making it suitable for use in a practical language interpreter/compiler.
This algorithm is also known as the DamasMilner
proved the completeness of the algorithm and the fact that the algorithm does in fact compute PrincipalType
s. He was
's PhD student.) RogerHindley
himself attributes the algorithm to
Description of algorithm
(This link is broken, is there another?
Behavior on programs with type errors can be unpredicatable, and often announcing type errors only toward end of program unifying substitutions can find type errors earlier:
A paper on improving type error reporting
Locating the Source of Type Errors
On relaxing type constraints from equations X = Y to inclusions X Y
Constrained type inference is strictly more general than Hindley Milner type inferenc. "Subtyping Constrained Types"
2003 Interview with Robin Milner
archive.org mirrors of interview
discussion of interview on Lambda the Ultimate
short blog discussion thereof
slashdot article/discussion on interview; links to e.g. Coq,
In the category of seriously geeky entertainment, there's now an amusing T-Shirt:
"What part of [the HM type inferencing algorithm] don't you understand?"
Is there any reason why the Hindley-Milner type system is only used in functional languages? Can it not be applied to languages without
, the Hindley-Milner type system is not at all only used in functional languages.
Can you give examples of imperative languages that use H-M type inference? What about languages with runtime polymorphism?
View edit of
May 26, 2010
with title or text search