Bidirectional Type Checking

Every time you write code, your compiler quietly decides which types go where. In some languages you annotate everything; in others, type inference figures it out automatically. Bidirectional type checking lands squarely in the middle — and it does so deliberately.

The idea, formalized by Benjamin Pierce and David Turner in 2000, is to split every expression into one of two modes:

• Check mode ($\Gamma \vdash e \Leftarrow A$): the compiler already knows what type $A$ to expect, and it just checks that the expression $e$ agrees.
• Synthesis mode ($\Gamma \vdash e \Rightarrow A$): the compiler doesn't know the type yet, and it synthesizes (computes) it from the structure of $e$.

The key insight is that these two modes flow into each other. A function application can synthesize the return type once it knows the function's type. A lambda body can be checked against the expected return type once an outer annotation provides it. Information flows inward when checking and outward when synthesizing — hence bidirectional.

The practical payoff is minimal annotations. You only need to write a type where the algorithm cannot synthesize one — typically at the top of a definition or when introducing a polymorphic function. Everything below that anchor inherits context and checks itself. Languages like Haskell, Rust, Scala, and many proof assistants rely on bidirectional ideas at their core.

The demo below shows a small expression tree. Each node can be in check mode (the type flows in from outside) or synthesis mode (the type must be computed from inside). Click a node to toggle whether it has an annotation. The algorithm propagates types and highlights which nodes still need one.

<!-- {{c_html_comment}} -->
<div class="toolbar">
  <span class="label">{{lbl_expr}}</span>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="tree-container"></div>
<div id="legend" class="legend">
  <span class="badge check">&#x21D0; {{lbl_check}}</span>
  <span class="badge synth">&#x21D2; {{lbl_synth}}</span>
  <span class="badge error">&#x26A0; {{lbl_error}}</span>
</div>
<div id="status" class="status"></div>
<p class="hint">{{hint_click}}</p>

/* {{c_css_comment}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; padding: .6rem; color: #222; }
.toolbar { display: flex; align-items: center; gap: .5rem; margin-bottom: .6rem; }
.label { font-size: .85rem; color: #555; }
button { font: 600 13px system-ui; padding: .35rem .75rem; border-radius: 7px; cursor: pointer;
         border: 1px solid #1d3557; background: #1d3557; color: #fff; }
button.ghost { background: #fff; color: #1d3557; }
#tree-container { overflow-x: auto; padding-bottom: .4rem; }
/* {{c_css_tree}} */
.tree { display: flex; flex-direction: column; align-items: flex-start; gap: 0; }
.node-row { display: flex; align-items: center; gap: 0; }
.indent { display: inline-block; width: 18px; flex-shrink: 0; }
.connector { display: inline-block; width: 18px; color: #aaa; font-size: 13px;
             flex-shrink: 0; user-select: none; }
.node { display: inline-flex; align-items: center; gap: 5px; padding: .28rem .55rem;
        border-radius: 7px; border: 1.5px solid #ccc; font: 500 13px ui-monospace, monospace;
        cursor: pointer; user-select: none; transition: background .12s, border-color .12s;
        margin: 2px 0; }
.node:hover { filter: brightness(.94); }
.node.check { background: #dbeafe; border-color: #3b82f6; }
.node.synth { background: #dcfce7; border-color: #22c55e; }
.node.error { background: #fee2e2; border-color: #ef4444; }
.node .kind { font-size: 10px; opacity: .7; }
.node .annot { font-size: 11px; background: #fff; border: 1px solid #999; border-radius: 4px;
               padding: 0 4px; margin-left: 3px; color: #444; }
.badge { font-size: .78rem; padding: .2rem .5rem; border-radius: 6px; }
.badge.check { background: #dbeafe; color: #1d4ed8; }
.badge.synth { background: #dcfce7; color: #15803d; }
.badge.error { background: #fee2e2; color: #dc2626; }
.legend { display: flex; gap: .6rem; flex-wrap: wrap; margin: .5rem 0; }
.status { font: 600 .9rem system-ui; min-height: 1.3em; margin: .3rem 0; }
.status.ok { color: #15803d; }
.status.err { color: #dc2626; }
.hint { font-size: .82rem; color: #666; margin: .4rem 0 0; line-height: 1.4; }

// Code not found

Notice the pattern: a top-level annotation unlocks check mode for the whole body. Inner sub-expressions inherit that context and check themselves without extra annotations. Remove the top annotation and the algorithm falls back to synthesis — but it can only do that where the structure is unambiguous (variables and constants). Lambdas without an annotation cannot synthesize their argument type and light up as errors.

Bidirectional type checking is a solved, decidable algorithm. Unlike full Hindley-Milner inference, which requires unification and can produce bewildering error messages about type variables you never wrote, bidirectional checking is deliberately restrained.

How hard is it?

• Each expression is visited once. The algorithm runs in a single recursive pass over the syntax tree — $O(n)$ in the size of the program.
• No backtracking. At every node the direction (check or synthesize) is determined by position, not by a global solver. Errors are local and precise.
• Annotation placement is predictable. Formal rules determine exactly where annotations are required (introduction forms without context, e.g. a lambda with unknown argument type) and where they are optional (elimination forms, e.g. function application).

The key rules (from Pierce & Turner 2000, and the later Dunfield & Krishnaswami 2021 survey):

• $(\Rightarrow\text{Var})$: a variable synthesizes the type recorded in the environment $\Gamma$.
• $(\Leftarrow\text{Lam})$: a lambda checks against an arrow type $A \to B$, binding the argument at type $A$.
• $(\Rightarrow\text{App})$: an application synthesizes by first synthesizing the function type, then checking the argument.
• $(\text{Ann})$: an annotated expression $e : A$ checks $e$ against $A$ and then synthesizes $A$.

The result is a type system that is easy to implement, gives good error messages, and composes cleanly with features like polymorphism and dependent types. Most modern languages and proof assistants — including Agda, Lean, and Idris — build on these ideas. You can also see the tension between checking and synthesis as a microcosm of the broader P vs NP story: verifying (checking) is easy; discovering (synthesizing) requires structure.

Bidirectional type checking is not an academic curiosity — it is the backbone of several mainstream languages and virtually all modern proof assistants:

• Rust: the borrow checker and lifetime inference use bidirectional ideas to avoid requiring users to annotate every pointer. The compiler checks most lifetimes from context; annotations are required only at function boundaries.
• Scala 3 (Dotty): replaces the old Hindley-Milner-style type inferencer with a bidirectional system that gives dramatically better error messages and handles complex dependent types.
• Agda, Lean 4, Idris 2: all three proof assistants use bidirectional elaboration as the core of their type checkers. The user provides high-level types; the system checks them against the expected sort.
• TypeScript: uses a form of contextual typing — passing expected types inward when checking object literals and arrow functions — that mirrors the check mode of bidirectional systems.

The unifying theme is predictability: programmers know where to put annotations because the rules are syntactically driven. Contrast this with Hindley-Milner, where a single missing annotation deep in a call chain can produce an error miles away.

Related ideas appear in gradual typing, where the unknown type ? flows through bidirectional rules to maintain soundness without full static knowledge.

Bidirectional type checking offers an elegant trade-off: give the compiler a type at the top, and it will do the rest. The two modes — check and synthesize — flow into each other along the structure of the program, requiring annotations only where the algorithm genuinely cannot proceed without them.

The design is deliberately modest. It gives up some inference power (you cannot always omit annotations on top-level polymorphic definitions) in exchange for predictability, good error messages, and easy extensibility. That bargain has proven valuable enough that it now underlies some of the most demanding type systems ever built.

Next time you add a type annotation to a function signature, you are not just helping yourself — you are giving the bidirectional algorithm an anchor, from which it will check the entire body without needing to ask for anything more. The annotation is the seed; the algorithm grows the rest.