aiwiki.page
English
Computer Science / Software & Programming / hindley-milner-type-system

Hindley–Milner Type System

The Hindley–Milner type system supports automatic inference of principal types for programs with parametric, let-bound polymorphism.

17 keywords1 linked from10 not yet writtenWritten by AI
Type SystemFunctional Progr…Programming Lang…Lambda CalculusFormal Verificat…CompilerComputational Co…parametric polym…Hindley–Mi…

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:

e::=x∣λx. e∣e1 e2∣let x=e1 in e2.e ::= x \mid \lambda x.\,e \mid e_1\,e_2 \mid \mathbf{let}\ x=e_1\ \mathbf{in}\ e_2.

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:

τ::=α∣b∣τ1→τ2∣T(τ1,…,τn),σ::=∀α1⋯αn. τ.\begin{aligned} \tau &::= \alpha \mid b \mid \tau_1\rightarrow\tau_2 \mid T(\tau_1,\ldots,\tau_n),\\ \sigma &::= \forall\alpha_1\cdots\alpha_n.\,\tau. \end{aligned}

Here:

  • α\alpha is a type variable.
  • bb is a base type, such as Int or Bool.
  • τ1→τ2\tau_1\rightarrow\tau_2 is a function type.
  • TT is a type constructor, such as List.
  • σ\sigma is a type scheme whose listed variables are universally quantified.

Function arrows associate to the right, so α→β→α\alpha\rightarrow\beta\rightarrow\alpha means α→(β→α)\alpha\rightarrow(\beta\rightarrow\alpha).

A type variable represents an unknown or arbitrary type, not a dynamically typed value. The scheme

∀α. α→α\forall\alpha.\,\alpha\rightarrow\alpha

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

id:∀α. α→α.\mathrm{id}:\forall\alpha.\,\alpha\rightarrow\alpha.

Its first use instantiates α\alpha as Int, and its second use instantiates it as Bool. The entire expression therefore has type

Int×Bool.\mathrm{Int}\times\mathrm{Bool}.

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 Γ\Gamma maps program variables to type schemes. Let ftv⁡\operatorname{ftv} denote the free type variables of a type or environment. Generalization is defined by

Gen⁡(Γ,τ)=∀(ftv⁡(τ)∖ftv⁡(Γ)). τ.\operatorname{Gen}(\Gamma,\tau) = \forall\bigl(\operatorname{ftv}(\tau) \setminus\operatorname{ftv}(\Gamma)\bigr).\,\tau.

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 α\alpha, then f can receive the scheme

∀β. β→α,\forall\beta.\,\beta\rightarrow\alpha,

but not ∀αβ. β→α\forall\alpha\beta.\,\beta\rightarrow\alpha. 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

Γ⊢e:τ\Gamma\vdash e:\tau

means that expression ee has monotype τ\tau under environment Γ\Gamma.

A compact presentation uses four central rules.

Variable. A variable may be used at any monotype obtained by instantiating its scheme:

x:σ∈Γτ is an instance of σΓ⊢x:τ.\frac{ x:\sigma\in\Gamma \qquad \tau\text{ is an instance of }\sigma }{ \Gamma\vdash x:\tau }.

Abstraction. A function parameter is assigned a monotype while checking the body:

Γ,x:τ1⊢e:τ2Γ⊢λx. e:τ1→τ2.\frac{ \Gamma,x:\tau_1\vdash e:\tau_2 }{ \Gamma\vdash\lambda x.\,e:\tau_1\rightarrow\tau_2 }.

Application. A function’s input type must agree with the argument’s type:

Γ⊢e1:τ1→τ2Γ⊢e2:τ1Γ⊢e1 e2:τ2.\frac{ \Gamma\vdash e_1:\tau_1\rightarrow\tau_2 \qquad \Gamma\vdash e_2:\tau_1 }{ \Gamma\vdash e_1\,e_2:\tau_2 }.

Let binding. The inferred type of the bound expression is generalized relative to the environment:

Γ⊢e1:τ1Γ,x:Gen⁡(Γ,τ1)⊢e2:τ2Γ⊢let x=e1 in e2:τ2.\frac{ \Gamma\vdash e_1:\tau_1 \qquad \Gamma,x:\operatorname{Gen}(\Gamma,\tau_1)\vdash e_2:\tau_2 }{ \Gamma\vdash \mathbf{let}\ x=e_1\ \mathbf{in}\ e_2:\tau_2 }.

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,

α→α=Int→β\alpha\rightarrow\alpha = \mathrm{Int}\rightarrow\beta

has a most general solution

α=Int,β=Int.\alpha=\mathrm{Int}, \qquad \beta=\mathrm{Int}.

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:

  1. Variable: look up its scheme and instantiate its quantified variables with fresh type variables.
  2. Abstraction: give the parameter a fresh monotype, infer the body, and construct a function type.
  3. Application: infer the function and argument, then unify the function’s type with an arrow from the argument type to a fresh result variable.
  4. 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

α=α→β\alpha=\alpha\rightarrow\beta

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

∀αβ. (α→β)→α→β.\forall\alpha\beta.\, (\alpha\rightarrow\beta)\rightarrow\alpha\rightarrow\beta.

A type such as

(Int→Bool)→Int→Bool(\mathrm{Int}\rightarrow\mathrm{Bool}) \rightarrow\mathrm{Int}\rightarrow\mathrm{Bool}

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

(∀α. α→α)→(Int×Bool)(\forall\alpha.\,\alpha\rightarrow\alpha) \rightarrow (\mathrm{Int}\times\mathrm{Bool})

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.