Type Checking: Static Typing, Inference, and Type Systems

Compilers Compilers 8 min read 1541 words Beginner ExcellentWiki Editorial Team

Type checking is the phase of compilation that verifies whether the program respects the language’s type system. A type system assigns a type to every expression and enforces rules about how values of different types can be combined. Type checking catches a wide range of programming errors at compile time — passing a string where an integer is expected, calling a method that does not exist on an object, or adding incompatible units — preventing these errors from reaching production. This article covers the fundamental concepts of type systems, the algorithms for type checking and type inference, and how languages implement generics, subtyping, and type soundness.

Type Systems: Basic Concepts

A type is a set of values and the operations that can be performed on them. A type system is a set of rules that assign types to program expressions and ensure type safety — that no operation receives a value of an unexpected type.

Static vs. Dynamic Typing

In a statically typed language, type checking occurs at compile time. Every expression has a type that is known before execution. C, Java, Rust, and TypeScript are statically typed.

In a dynamically typed language, type checking occurs at runtime. Variables can hold values of any type, and type errors manifest as runtime exceptions. Python, JavaScript, and Ruby are dynamically typed.

The tradeoff is safety vs. flexibility: static typing catches errors earlier but requires more annotation (or sophisticated inference); dynamic typing offers more flexibility but shifts error detection to testing and production.

Strong vs. Weak Typing

“Strong typing” means the language strictly enforces type rules — implicit conversions are rare or non-existent. “Weak typing” allows many implicit conversions. These terms are less precisely defined than static/dynamic. Rust and Haskell are strongly typed; C is weakly typed (automatic conversion between int, float, pointer).

Type Safety

A type-safe language prevents operations that violate type rules. For example, C is not memory-safe — you can cast an arbitrary integer to a function pointer and call it, or read memory beyond an array bound. Java is type-safe in the core language (though unsafe APIs break safety). Rust is type-safe with the borrow checker enforcing memory safety.

Type Checking Algorithms

Structural Type Checking

The simplest form of type checking is structural: the type checker walks the AST, assigns a type to each subexpression based on type rules, and verifies that the types of operands match operator expectations.

For the expression a + b in a language where + is defined for integers, the checker:

Determines the type of a (look it up in the symbol table)
Determines the type of b
Checks that both are integer types
Concludes that the result type is integer

Type rules are typically expressed as inference rules:

Γ ⊢ e1 : int    Γ ⊢ e2 : int
--------------------------
   Γ ⊢ e1 + e2 : int

Read as: “If in context Γ, e1 has type int and e2 has type int, then e1 + e2 has type int.”

Hindley-Milner Type Inference

Languages like ML, Haskell, and Rust use Hindley-Milner (HM) type inference, which infers types without requiring explicit annotations. The algorithm, independently discovered by Hindley and Milner in the 1970s, works in two phases:

Constraint generation — walk the AST and generate type constraints. For f(x), the constraint is “the type of f must be a function type whose parameter type matches the type of x, and the result type is the type of the application.”
Unification — solve the constraint system. Unification finds the most general type assignment that satisfies all constraints.

Unification

Unification is the process of making two types equal by finding a substitution. The basic cases:

A type variable (unknown) can be unified with any type — the variable is bound to that type
Two base types (int, bool) unify only if they are identical
Two function types A -> B and C -> D unify if A unifies with C and B unifies with D
A type error occurs when incompatible types are forced to unify (e.g., int with bool)

The standard unification algorithm (Martelli-Montanari) works in near-linear time using union-find (disjoint set) data structures to track type variable bindings.

Subtyping

Subtyping allows a value of one type to be used where a different type is expected. If S is a subtype of T, then any value of type S can be used in a context expecting type T.

Nominal Subtyping

In nominal subtyping (used by Java, C#, C++), subtyping is declared explicitly: class Dog extends Animal declares Dog as a subtype of Animal. The type checker follows the declared inheritance hierarchy.

Structural Subtyping

In structural subtyping (used by TypeScript, Go), subtyping is based on structure rather than declarations. If a type has all the members that another type requires, it is a subtype — even if no explicit inheritance is declared. TypeScript’s object types work this way: { name: string; age: number } is a subtype of { name: string } because it has at least the name field.

Variance

Variance describes how subtyping propagates through type constructors:

Covariant — List<Dog> is a subtype of List<Animal> if List is covariant. Read-only collections are typically covariant.
Contravariant — Consumer<Animal> is a subtype of Consumer<Dog> if Consumer is contravariant. Function parameters are contravariant: a function that can handle any Animal can also handle Dog.
Invariant — MutableCell<Dog> is not a subtype of MutableCell<Animal> (nor vice versa) for mutable containers. Mutability makes type relationships invariant.

Java arrays are covariant (which is unsound — String[] s = new String[1]; Object[] o = s; o[0] = 1; compiles but throws ArrayStoreException). Rust and C++ use invariance for generics by default.

Generics (Parametric Polymorphism)

Generics allow writing code that works with multiple types without duplication. A generic function fn id<T>(x: T) -> T { x } works for any type T.

Implementation Strategies

Type erasure — Java generics are erased at compile time. The compiler checks generic usage but generates bytecode with casts. This preserves backward compatibility but loses type information at runtime.

Monomorphization — Rust, C++, and Swift generate specialized copies of generic code for each concrete type. Vec<i32> and Vec<String> compile to completely separate code. This produces fast code (no boxing) but increases binary size.

Reification — .NET generics are reified: generic types exist at runtime, and the JIT compiler generates specialized code lazily. This combines the performance of monomorphization with the binary size benefits of erasure.

Type-Level Programming

Advanced type systems support computation at the type level. C++ templates are Turing-complete — template metaprogramming can compute prime numbers, sort tuples, and implement embedded domain-specific languages, all at compile time. The cost is long compilation times and error messages that can span thousands of lines.

Rust’s const generics allow types parameterized by constant values, like [u8; N] where N is a compile-time constant. Rust also supports generic-associated types (GATs) and type alias impl traits (TAIT), enabling higher-kinded type patterns.

Haskell’s type-level programming with DataKinds, TypeFamilies, and TypeInType allows encoding invariants like “this function returns a list whose length is the sum of the input list lengths” in the type system. The Glasgow Haskell Compiler (GHC) routinely performs type-level computation that would be considered advanced metaprogramming in other languages.

Type Soundness

A type system is sound if no well-typed program can produce a type error at runtime. Soundness is usually proved via two properties:

Progress — a well-typed program is not stuck; it can either take a step or is a value
Preservation — if a well-typed program takes a step, the resulting program is also well-typed

The classic proof technique uses operational semantics and is covered in Pierce’s “Types and Programming Languages” (TAPL).

Real languages rarely have perfectly sound type systems. C and C++ have unsound corners (union type punning, reinterpret_cast). Java’s covariant arrays are unsound. TypeScript has intentional unsoundness for pragmatism. Rust is unusually sound, with unsafe being the only escape hatch.

FAQ

What is the difference between type checking and type inference? Type checking verifies that a program’s types are consistent according to the type rules. Type inference deduces the types of expressions without explicit annotations. Hindley-Milner does both simultaneously — it infers types while checking consistency.

What does “type inference” fail on? Hindley-Milner inference is limited to the simply typed lambda calculus with parametric polymorphism (let-polymorphism). It cannot infer higher-rank types (where a polymorphic type appears as a function argument). Languages like Haskell and Rust require annotations for these cases.

How does Rust’s borrow checker relate to type checking? The borrow checker is separate from the type checker. The type system handles ownership and borrowing (tracking whether values are moved or borrowed), while the type checker handles type equality and inference.

Can a type system be too strict? Yes. A type system that rejects valid programs is too strict. The tension is between soundness (catching all type errors) and completeness (accepting all correct programs). Practical type systems err on the side of rejecting some valid programs to guarantee safety.