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

Bidirectional Type Checking

Combining inference and checking modes for more expressive type systems.

Bidirectional Type Checking

What you'll learn: How combining inference and checking modes creates more powerful and practical type systems.

The Core Idea

So far you've seen type inference (Algorithm W, unification) deduce types automatically, and type checking verify that terms match expected types. Bidirectional type checking combines both approaches strategically: some language constructs infer their types upward, while others check against types pushed downward from context.

Think of it like a conversation where sometimes you volunteer information ("I'm bringing dessert") and sometimes you respond to a request ("Can you bring a dessert? Yes, I can"). Inference volunteers type information; checking responds to contextual demands.

Why Combine Both Modes?

Pure inference (like Hindley-Milner) is elegant but has limits. Some features—like polymorphic lambdas without annotations—become undecidable. Pure checking requires annotations everywhere, which is tedious.

Bidirectional typing splits the difference:

  • Inference mode (↑): Expressions with clear structure (variables, function applications) synthesize their type and push it up.
  • Checking mode (↓): Expressions that need context (lambda abstractions, conditionals) check against an expected type pushed down.

For example, in let f = λx. x + 1, the lambda can check against an expected type Int → Int rather than requiring you to annotate x. Meanwhile, f(5) can infer its result type from f's known signature.

The Pattern

Bidirectional checking alternates modes:

  1. Annotated terms and applications infer types
  2. Lambdas and branches check against expected types
  3. Information flows both up (from leaves) and down (from context)

This hybrid approach handles polymorphism, subtyping, and complex features more gracefully than pure inference, while keeping most annotations optional.

Key Takeaway: Bidirectional type checking combines inference (bottom-up) and checking (top-down) modes to balance expressiveness, decidability, and annotation burden in practical type systems.