Course contentsShow
← Computer Science
Lesson 2011 of 2,87245. Type Systems and SemanticsFree lesson

Algorithm W

The classic type inference algorithm that traverses expressions to generate constraints.

Algorithm W

You'll learn the classic algorithm that automatically infers types by walking through your code and solving constraints.

What is Algorithm W?

Algorithm W is the workhorse implementation of the Hindley-Milner type system. While the previous lesson explained what unification does (matching type variables with concrete types), Algorithm W is the how—the actual procedure that visits each expression in your program, generates type constraints, and unifies them to discover the most general type.

Think of it like a detective solving a case: Algorithm W walks through the crime scene (your code), collecting clues (type constraints from each expression), then pieces them together (unification) until the full picture emerges.

How Algorithm W Works

The algorithm processes expressions recursively:

  1. Visit a literal (like 42): instantly know its type (Int)
  2. Visit a variable (x): look up its type in the environment
  3. Visit a function application (f arg):
    • Infer the type of f
    • Infer the type of arg
    • Unify f's type with arg_type -> fresh_result_type
    • Return result_type
  4. Visit a lambda (λx. body):
    • Create a fresh type variable for x
    • Infer the body's type with x in scope
    • Return x_type -> body_type

At each step, unification updates our knowledge, potentially substituting type variables with concrete types or more specific polymorphic types.

Why It Matters

Algorithm W proves that automatic type inference is decidable—you don't need to annotate every variable. The compiler can figure it out by following this systematic traversal-and-constraint-solving process.

Key Takeaway: Algorithm W is the recursive traversal procedure that infers types by visiting each expression, generating constraints, and unifying them to find the most general type automatically.