The Hindley–Milner type system (HM) is a type system for programming languages that combines static typing, parametric polymorphism, and automatic type inference. In its standard form, it assigns types to a lambda calculus extended with let bindings, allowing many programs to be checked without explicit type annotations. Its defining property is the existence of principal types: whenever an expression is typable, it has a most general type from which all its other valid types can be obtained by substitution. HM forms an important theoretical foundation for type inference in functional programming languages, particularly the ML family.
Historical development
HM brings together several developments in the theory and implementation of programming languages.
In 1969, J. Roger Hindley established a principal-type result for combinatory logic, a formalism closely related to lambda calculus. Robin Milner developed a polymorphic typing discipline for ML and described an inference procedure, Algorithm W, in his 1978 paper A Theory of Type Polymorphism in Programming. Luis Damas and Milner subsequently established the principal-type-scheme result for the relevant functional language in their 1982 paper Principal Type-Schemes for Functional Programs.
These contributions explain the alternative names Damas–Milner and Damas–Hindley–Milner. The terminology is sometimes used broadly for related inference systems, but the core formal system is narrower than the complete type systems of modern ML-derived languages.
Core language and types
A minimal HM expression language contains variables, function abstraction, function application, and local definitions:
Constants, tuples, lists, conditional expressions, and algebraic data constructors can be added with suitable typing rules.
HM distinguishes monotypes from type schemes. A representative grammar is:
Here:
- is a type variable.
- is a base type, such as
IntorBool. - is a function type.
- is a type constructor, such as
List. - is a type scheme whose listed variables are universally quantified.
Function arrows associate to the right, so means .
A type variable represents an unknown or arbitrary type, not a dynamically typed value. The scheme
describes a function that can be instantiated at any type while preserving the relationship between its input and output types.
Quantifiers occur only at the outermost level of a scheme, not inside function argument types. This restriction is central to HM’s tractable inference discipline.
Let-polymorphism
The characteristic feature of HM is let-polymorphism: a type inferred for a let-bound expression can be generalized, and separate uses of the bound name can instantiate that generalized type independently.
For example:
let id = fun x -> x in
(id 3, id true)
The identity function receives the scheme
Its first use instantiates as Int, and its second use instantiates it as Bool. The entire expression therefore has type
By contrast, an ordinary lambda-bound parameter has one monotype within its scope. The expression
fun f -> (f 3, f true)
is not typable in basic HM when Int and Bool are distinct types: the two calls require incompatible argument types for the same monomorphic parameter.
This difference is intentional. HM does not provide unrestricted polymorphic function arguments.
Generalization and instantiation
A typing environment maps program variables to type schemes. Let denote the free type variables of a type or environment. Generalization is defined by
Only type variables not free in the surrounding environment may be generalized. Variables already constrained by the environment must retain those constraints.
For example:
fun x ->
let f = fun y -> x in
...
If x has type , then f can receive the scheme
but not . Its result is the particular captured value x, whose type cannot change independently at each call.
Instantiation replaces a scheme’s quantified variables with fresh type variables. Variables that are free rather than quantified remain shared with the environment.
Typing rules
The judgment
means that expression has monotype under environment .
A compact presentation uses four central rules.
Variable. A variable may be used at any monotype obtained by instantiating its scheme:
Abstraction. A function parameter is assigned a monotype while checking the body:
Application. A function’s input type must agree with the argument’s type:
Let binding. The inferred type of the bound expression is generalized relative to the environment:
These rules specify which expressions are well typed. An inference algorithm supplies an effective procedure for finding the types and substitutions needed to construct such derivations.
Type inference and Algorithm W
Algorithm W is the standard syntax-directed inference algorithm associated with HM. It traverses an expression and returns both a type and a substitution recording the constraints discovered during inference.
The central operation is unification: solving equations between type expressions. For example,
has a most general solution
A most general unifier makes only the identifications required by the equations; any other solution can be obtained by applying a further substitution.
Algorithm W handles the expression forms as follows:
- Variable: look up its scheme and instantiate its quantified variables with fresh type variables.
- Abstraction: give the parameter a fresh monotype, infer the body, and construct a function type.
- Application: infer the function and argument, then unify the function’s type with an arrow from the argument type to a fresh result variable.
- Let binding: infer the bound expression, apply the resulting substitution to the environment, generalize against that updated environment, and infer the body.
Updating the environment before generalization is essential: constraints discovered while checking the bound expression can restrict variables inherited from its context.
The occurs check
Unification includes an occurs check, which prevents a type variable from being equated with a type expression containing itself. The equation
has no solution among finite HM types.
Consequently, self-application,
fun x -> x x
is rejected. The parameter would have to be both an argument type and a function taking that same type as input.
Simply dropping the occurs check does not yield ordinary HM. Supporting recursive types requires a different account of types and their equality.
Principal types and soundness
A principal type scheme captures every valid typing of an expression through instantiation, without unnecessarily fixing its type variables. For example,
fun f -> fun x -> f x
has principal scheme
A type such as
is a valid instance, but is less general.
For the standard HM calculus, Algorithm W is sound and complete with respect to the typing rules: successful inference produces a valid typing, and a typable expression has a principal result recoverable by the algorithm. Principality is understood relative to the environment; constraints already present there remain in force.
Type safety is a related but distinct property. For a suitable operational semantics, well-typed programs do not encounter the kinds of type mismatch excluded by the typing rules—for example, applying a Boolean as though it were a function. This does not imply termination, the absence of all exceptions, or correctness with respect to an external specification. Such stronger properties belong to broader forms of formal verification.
Use in programming languages
HM is closely associated with ML and strongly influenced Standard ML, OCaml, and Haskell. These languages extend or modify the core system rather than implementing only the minimal calculus.
Common additions include:
- Algebraic data types and pattern matching, which work naturally with polymorphic constructors.
- Recursive definitions, usually checked using monomorphic assumptions within a recursive group before the completed bindings are generalized.
- Modules and abstract types, which add separate mechanisms for organizing and hiding type information.
- Qualified types, notably Haskell’s type-class constraints, which go beyond ordinary HM schemes.
- Mutable state, which requires restrictions on generalization.
In compiler implementations, HM-style inference supports concise source programs while retaining static checks. Implementations often use mutable representations of type variables and efficient graph-based unification rather than directly reproducing Algorithm W’s substitution-based presentation.
Restrictions and extensions
Higher-rank polymorphism
In basic HM, a function parameter cannot itself be assigned an independently instantiable polymorphic scheme. A type such as
contains a quantifier inside a function argument and is outside the HM grammar.
Higher-rank polymorphism supports such arguments. Languages offering it commonly require explicit annotations in places where ordinary HM would infer types automatically.
System F provides a more expressive formal treatment of universal polymorphism, including explicit type abstraction and application. General reconstruction of omitted type information for unrestricted System F does not retain HM’s decidable inference problem.
Polymorphic recursion
Under ordinary HM-style treatment of recursive definitions, a recursively defined name is monomorphic within its own definition. Polymorphic recursion, in which recursive calls use distinct type instances, is not inferred by standard Algorithm W.
Unrestricted inference with polymorphic recursion is undecidable. Some languages permit particular polymorphically recursive definitions when an explicit type signature supplies the necessary information.
Mutable state and the value restriction
Unrestricted generalization becomes unsound when combined naively with mutable references. A reference to an initially empty list must not be generalized so that one use can store integers while another reads the same contents as Booleans.
ML-family languages therefore restrict generalization. A common approach, the value restriction, broadly permits generalization for syntactic values while limiting it for expressions that may perform computation with effects. Exact rules vary by language; some use relaxed forms that recover additional safe generalization.
Features outside the basic system
Subtyping, overloaded operators, generalized algebraic data types, dependent types, and other advanced features require additional rules or different inference techniques. Some extensions preserve principal types under stated conditions; others introduce ambiguity, require annotations, or abandon global principal-type inference.
An implementation using HM-style unification therefore need not have all the metatheoretic properties of pure HM.
Complexity and practical limitations
HM inference is decidable, but decidability does not imply uniformly inexpensive inference. Despite good practical performance on many programs, inference for the general system has exponential worst-case behavior. Nested polymorphic definitions can generate very large types or force large implicit expansions during inference.
Efficient representations can share repeated type structure and avoid needless copying, but they do not eliminate the underlying worst-case complexity. This distinction matters when assessing the computational complexity of an inference algorithm versus the size of a fully expanded inferred type.
Error reporting is another practical limitation. Unification may detect a contradiction far from the expression that introduced the programmer’s mistake. A compiler can therefore identify a valid type conflict while presenting an unhelpful location or explanation. Modern implementations supplement inference with source-location tracking, constraint provenance, annotations, and specialized diagnostics.
Finally, a rejected program is not necessarily one that would fail during execution. Some expressions lie outside HM’s typing discipline because they need more expressive polymorphism, recursive types, or other extensions. HM deliberately balances expressiveness against automatic inference and strong, general typing guarantees.