Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 61 ยท Semantic Analysis

Type Inference and Unification

Learn how compilers infer types without annotations: type variables, unification, the occurs check and let-polymorphism, with a runnable Python inferer.

In the previous lesson every variable and parameter had a type that the programmer wrote down. That is safe but wordy. In languages such as Haskell, OCaml, Rust and (in parts) TypeScript, Kotlin and C++ with auto, you often write nothing and the compiler works the types out for itself. This is type inference, and the classic algorithm behind it is surprisingly small.

The idea is to treat unknown types as unknowns in an equation system. Every unknown gets a name (a type variable), every use of a value produces an equation ("this must equal that"), and a procedure called unification solves the equations. If they can be solved, the program is well typed and the solution tells you every type. If not, you have found a type error. By the end of this lesson you will have an inference engine of about 100 lines that infers fun f -> fun x -> f (f x) as ('a -> 'a) -> 'a -> 'a by itself.

Type variables and constraints

Take the tiny function fun x -> x + 1. Nobody told the compiler what x is. The inferer proceeds like this:

  1. Give x a fresh type variable, say 'a.
  2. The operator + has the known type int -> int -> int. Applying it to x means the argument type must match: 'a must equal int.
  3. The result of x + 1 is int, so the function has type 'a -> int, which is int -> int once we substitute the solution.

Nothing in the source said int; it came from how x was used. Formally, inference walks the tree and emits constraints of the form T1 = T2. A substitution is the map from type variables to types that makes all constraints true.

flowchart LR
    A["Expression"] --> B["Assign fresh type<br/>variables to unknowns"]
    B --> C["Walk the tree,<br/>emit constraints"]
    C --> D["Unify:<br/>solve T1 = T2"]
    D --> E["Apply the substitution<br/>to get final types"]
    D --> F["Type error if two<br/>types cannot match"]

Inference is the same tree walk as type checking, except that unknown types are variables to be solved for.

Our mini-language has just six forms: literals (42, true), variables, lambdas (fun x -> body), application (f a), let name = value in body and if. Operators like + are ordinary names in a starting environment with types such as int -> int -> int. A function type a -> b is written as TFun(a, b), and a function of two arguments is a function that returns a function (int -> int -> int means int -> (int -> int)).

Unification

Unification takes two types and finds a substitution that makes them identical, or fails. Its rules are short:

  • Two identical types unify with nothing to do. (int and int.)
  • A type variable unifies with any type: record "variable = that type".
  • Two function types unify if their argument types unify and their result types unify.
  • Anything else (int against bool, or int against a function) is a type error.

There is one trap. Unifying 'a with 'a -> int would give 'a = 'a -> int, an infinitely nested type. The occurs check refuses to bind a variable to a type that contains that same variable. This is exactly what rejects fun x -> x x: the argument is applied to itself, which would need an infinite type.

Python Unification by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The substitution is a plain dictionary from variable numbers to types. The helper walk chases bindings (a variable may point at another variable that points at a type), and resolve applies the whole substitution to a type before it is shown to the user. In the first case, 'a -> int and bool -> 'b match by pairing arguments and results: 'a = bool and 'b = int.

Algorithm W: the inference walk

Now the full algorithm, usually called Hindley-Milner after the logicians who discovered it independently (and Algorithm W or J for the procedure). It is a recursive function infer(expr, env) that returns a type and adds bindings to the substitution as a side effect. The rule for each expression form follows directly from what the form means.

Expression What infer does
literal int or bool
variable x look up x in the environment and instantiate its type
fun x -> body give x a fresh variable 'a, infer the body, return 'a -> body_type
f arg infer both, make a fresh result variable 'r, unify f_type with arg_type -> 'r, return 'r
if c then a else b unify c with bool; unify the branch types; return that type
let x = v in body infer v, generalize it, bind x to the result, infer body

Application is the heart of it. We do not know what f returns, so we invent 'r and demand that f be a function from the argument's type to 'r. If f is already a known function, unification checks the argument and reveals 'r. If f is itself an unknown variable (a lambda parameter), unification decides that it must be a function.

Let-polymorphism: instantiate and generalize

Consider fun x -> x. Its type is 'a -> 'a, and it should work for numbers and for booleans alike. This is parametric polymorphism. But a lambda parameter must have one type for the whole body: inside fun id -> ..., id cannot be used on both true and 1.

The two operations that give let its power are:

  • Generalize: after inferring the value of a let, every type variable in its type that is not mentioned elsewhere in the environment becomes a universally quantified variable. We store this as a scheme like "for all a, a -> a".
  • Instantiate: every time that name is used, replace the quantified variables with brand-new ones, so each use can pick its own types.

That is why let id = fun x -> x in ... can use id at two types, while the lambda-bound version cannot. Below is the whole system. Run it and compare the results with what you would work out on paper.

Python A Hindley-Milner inferer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read down the results. The identity function gets 'a -> 'a and fun x -> x + 1 gets int -> int, even though no annotations were written. Composition (fun f -> fun g -> fun x -> f (g x)) comes out as ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b: the compiler discovered that g's result type is f's argument type. The if examples fail because the condition or the two branches disagree, fun x -> x x fails the occurs check, and the last example is a plain unknown name.

The final pair is the point of the lesson. The let version type-checks (to int) because id is generalized to "for all a, a -> a" and instantiated freshly at each use. The lambda version fails with cannot unify bool with int, because the parameter id has one monomorphic type that must be both bool -> r and int -> r2.

Watching the constraints

It helps to see unification as it happens. Subclassing the inferer to print every call to unify reveals the equations generated by fun f -> fun x -> f (f x). (Add this to the end of the previous example and run it, or just read the output below.)

Python
class Tracing(Inferer):
    def __init__(self):
        super().__init__()
        self.names = {}
    def unify(self, a, b):
        print("  unify", show(self.resolve(a), self.names),
              "with", show(self.resolve(b), self.names))
        super().unify(a, b)

tracer = Tracing()
result = tracer.infer(examples["fun f -> fun x -> f (f x)"], PRELUDE)

It prints this sequence:

TEXT
  unify 'a with 'b -> 'c
  unify 'b -> 'c with 'c -> 'd
  unify 'b with 'c
  unify 'c with 'd

Here 'a is the type of f, 'b the type of x, and 'c the result of the inner call f x. The first line says "f must be a function from x's type to something". The second line applies f to its own result: f (now known to be 'b -> 'c) must accept 'c and return a new 'd. Pairing arguments and results forces 'b = 'c = 'd, so f : 'b -> 'b and the final answer ('a -> 'a) -> 'a -> 'a.

Limits and real-world inference

Hindley-Milner is elegant, but real languages need more, and you meet its limits quickly:

  • Overloading and subtyping break plain unification. x + 1 with + on both numbers and strings has no single type. Haskell solves this with type classes; TypeScript and Kotlin use subtyping with bidirectional inference, passing an expected type down the tree as well as inferring up.
  • Local inference (Java var, C++ auto, Rust let) infers only inside a function body and still asks for annotations on function signatures, which gives better error messages and faster compilation.
  • Error messages are the weak spot. When unification fails, the real mistake may be far from the place where two types finally clash. Production compilers track where each constraint came from to point at the right line.
  • Decidability and speed. Full inference with higher-rank types or dependent types is undecidable or needs annotations. Plain Hindley-Milner runs in near-linear time on typical programs.

Rust's let v = Vec::new(); is a nice real example: v starts with an unknown element type, and a later v.push(3u8) is the constraint that fixes it. If nothing ever constrains it, the compiler reports "type annotations needed".

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does unification do?

    Unification solves the equation T1 = T2 by assigning types to type variables. If no assignment can make them equal, the program has a type error.
  2. 2. Why is fun x -> x x rejected by Hindley-Milner inference?

    Applying x to itself requires its type to contain itself. The occurs check stops a variable from being bound to a type that mentions that variable.
  3. 3. Why can a let-bound identity function be used at both int and bool, but a lambda parameter cannot?

    Generalization turns the free type variables of the let-bound value into universally quantified ones, and each use instantiates them with new variables. A lambda parameter is a single unknown shared by all its uses.
  4. 4. For an application f arg, the inferer creates a fresh variable 'r and unifies the type of f with (type of arg) -> 'r. What is the role of 'r?

    We do not yet know what f returns, so 'r is a placeholder. If f is a known function type, unification fills in 'r; if f is itself unknown, unification decides that f is a function.

Summary

  • Type inference removes annotations by giving unknown types names (type variables) and solving the equations that the program's structure implies.
  • Unification matches two types, binding variables as needed; the occurs check prevents infinite types.
  • Algorithm W is a single recursive tree walk: lambdas introduce fresh variables, applications unify a function type with arg -> result, and if unifies the condition with bool and the branches with each other.
  • let generalizes types into schemes, and each use instantiates them with fresh variables, which gives parametric polymorphism.
  • Real languages combine inference with overloading, subtyping and annotations, and put much effort into error messages.

Next: Intermediate Representations