The idea: types nobody wrote
In OCaml or Haskell you can write fun x -> x + 1 with no types at all, and the compiler still knows it is int -> int. This is type inference. The method most of these languages use is Hindley-Milner. It works in two phases. First it gives every node of the expression tree an unknown type, a type variable t1, t2, …, and writes down what each node's rule says about them as equations. Then it solves the equations by unification. The answer is a substitution S, a table "t4 is int, t1 is int -> int, …" (Demo 1).
The tree is what the parser builds (see LL(1) parsing). Inference is part of the semantic analysis phase in the compiler pipeline.
Phase 1: constraints from each node
Press Generate. The page walks the tree from the top. Each node gets the next fresh variable, and a fun also gives its parameter one. The parameter goes into the environment, the list of names in scope with their types. When a node's children are done, the node's rule flies to the constraint list:
| Node (its variable t) | Constraints |
|---|---|
literal 1 or true | t = int, or t = bool |
use of a parameter x of type tx | t = tx |
fun x -> e | t = tx -> te |
f a (apply) | tf = ta -> t |
e1 + e2 | t1 = int, t2 = int, t = int |
if c then a else b | tc = bool, ta = tb, t = ta |
The rule for apply is the key one. It does not look up a type for f. It says f must be some function from the argument's type to the result's type. For fun x -> x + 1 this gives 6 constraints over 5 variables.
Phase 2: unification
Press Unify. The page takes the open constraints from top to bottom. It first applies S to both sides, so variables that are already known get replaced. The line under the list shows the result. Then one of five cases applies:
When the page binds a variable, it also replaces that variable inside every entry already in S. So S never has a known variable on a right side, and reading a type off S takes one look. A split puts the two new constraints right under the old one. In Demo 2 (twice, fun f -> fun x -> f (f x)) the two uses of f give 7 constraints; one of them is arrow = arrow and splits into 2 more, so 9 in total and 8 entries in S.
A clash means two different type shapes must be equal. (fun x -> x + 1) true needs x to be int because of the +, and bool because of the argument. Unification stops at int = bool (Demo 4). Real compilers report this as "this expression has type bool but an expression was expected of type int".
The occurs check
In fun x -> x x, x is applied to itself. Its type t2 must be a function that takes t2: the page gets t2 = t2 -> t3 (Demo 5). Binding t2 to a type that contains t2 would make an infinite type, t2 = (t2 -> t3) -> t3 = … with no end. So before every bind, unification checks that the variable does not occur in the other side. Here it does, and the expression has no type.
The most general type
When unification finishes, apply S to the root's variable. Some variables may be left over, bound to nothing. Nothing in the program forces them, so they can be any type. The page renames them 'a, 'b, … as OCaml prints them. Demo 2 ends with ('a -> 'a) -> 'a -> 'a and Demo 3 (compose, fun f -> fun g -> fun x -> f (g x)) with ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b. Unification only binds what an equation demands, so this is the most general type (the principal type): every other correct type, like (int -> int) -> int -> int, is an instance of it. Functions of several arguments come out curried; see closures and currying.
let-polymorphism: generalize, then copy
In let id = fun x -> x in if id true then id 1 else 2, id is used at bool and at int. That works because let is treated in a special way (Demo 6):
- Infer the part after
=first and solve its 2 constraints right away. id has typet3 -> t3. - Generalize: t3 appears nowhere else in the environment, so it gets a "for all":
id : ∀t3. t3 -> t3. - Instantiate at every use: each use of id gets a fresh copy.
id truegetst8 -> t8andid 1getst12 -> t12. t8 becomes bool and t12 becomes int, with no conflict.
The whole run has 17 constraints (13 generated, 4 from 2 splits), S ends with 13 entries, and the type is int.
Now pass the same id as a fun parameter instead: (fun id -> if id true then id 1 else 2) (fun x -> x) (Demo 7). A parameter is never generalized, because the function could be called with any argument. Both uses share one variable t3. The first use makes t3 = bool -> t5, the second needs int -> t8, and the split gives the clash bool = int. This is the limit of Hindley-Milner: functions can be polymorphic, but a function cannot take a polymorphic argument.
Where this runs
| Language | What it infers |
|---|---|
| Standard ML, OCaml, F# | Hindley-Milner with let-polymorphism, as on this page; type annotations are optional |
| Haskell | Hindley-Milner plus type classes (Num a => a -> a) |
Rust, Swift, Kotlin, TypeScript, C++ auto | Local inference inside a function body; function signatures are written by hand |
The environment is the compile-time view of scope from static vs dynamic scoping: a name's type comes from the nearest enclosing binder in the source.
See also Three-Address Code, Basic Blocks and Local Optimizations for what the compiler does with a well-typed tree next.
What the page leaves out
The page has only int, bool and function types, and one ML-style expression at a time. It leaves out tuples, lists and user-defined data types, recursion (let rec), the value restriction on generalizing (for references), type classes, union-find with path compression (how real compilers store S quickly), Algorithm W and Algorithm J as the textbooks write them (they mix the two phases, as the page does only at let), error messages that point at the right source line, and type annotations checked against the inferred type.