HindleyMilnerTypensystem

The Hindley–Milner type system, often abbreviated HM, is a classical type system for the simply typed lambda calculus extended with let-bindings that supports automatic type inference and parametric polymorphism. It was developed independently by J. Roger Hindley (1969) and Robin Milner (1978), and it became the formal foundation for type systems in ML-family languages such as Standard ML and OCaml. HM explains how programs can be assigned most general types without requiring explicit type annotations.

Core ideas of the Hindley–Milner system include the notion of principal types, where every typable expression has a most general type from which all other types can be instantiated. The system relies on unification to solve type equations and to infer a consistent assignment of types to expressions. A key mechanism is let-generalization: in a let-binding, the type of the bound expression can be generalized over type variables that are not free in the typing environment, yielding a polymorphic type scheme. Instantiation then replaces those generalized variables with fresh type variables when the bound value is used in a particular context. Algorithm W implements practical HM type inference, producing the most general type for expressions in a language with let-polymorphism.

HM supports parametric polymorphism but generally does not include subtyping or higher-rank polymorphism by default. Extensions and variations add features such as type classes (as in Haskell), module systems, or constrained polymorphism, while preserving the core HM inference approach. The Hindley–Milner type system remains influential in the design and implementation of many contemporary functional languages.