Implement Type Inference for a Simple Expression Language

Inferring Types Without Annotations

ML, Haskell, Rust, and TypeScript infer types where annotations are omitted. Hindley-Milner unification assigns types to every subexpression; Rust's solver handles traits. Even a simple constraint-based inferencer for arithmetic expressions teaches the core idea.

Unification on Expressions

Literals get concrete types: 42 is int, 3.14 is float. For a + b, unify a and b to the same numeric type; result matches. For if c then e1 else e2, unify e1 and e2; c must be bool.

cCopy
Loading…

• Generate type variables for unknown identifiers
• Constraints: add : int -> int -> int or polymorphic
• Solve by unification or fixed-point iteration
• Report ambiguous or unsolvable constraints as errors

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will implement type inference for a small expression language without explicit type annotations. This exercise requires generating constraints from the AST and solving them to assign types to every subexpression.