The Real Complexity of Bidirectional Type Checking

Introduction

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.

Try It

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.

<!-- Interactive bidirectional type checking demo -->
<div class="toolbar">
  <span class="label">Expression tree — click annotable nodes to toggle annotations</span>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="tree-container"></div>
<div id="legend" class="legend">
  <span class="badge check">&#x21D0; Check mode</span>
  <span class="badge synth">&#x21D2; Synthesis mode</span>
  <span class="badge error">&#x26A0; Error</span>
</div>
<div id="status" class="status"></div>
<p class="hint">Click the top node to toggle its annotation. When the annotation is on, the whole tree is in check mode. When it is off, lambdas without a known argument type become errors.</p>

/* Bidirectional type demo styles */
* { 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; }
/* Tree layout */
.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; }

// Bidirectional type checking demo — two modes:
// check (<=): verify expression e against known type A
// synth (=>): compute type A from the structure of e
// Rules: Var=>synth, Lam<=check, App=>synth, Ann:check then synth
// Nodes with annotations always switch to check mode for their body.

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Expression tree: let result: Int = add 3 4
// let-binding node wrapping a function application
const EXPR = {
  id: 'let',
  kind: 'let',
  label: 'let result =',
  annot: 'Int',
  annotable: true,
  children: [
    {
      id: 'app',
      kind: 'app',
      label: 'add 3 4',
      annotable: false,
      children: [
        { id: 'fn_add', kind: 'var', label: 'add', annotable: false, children: [] },
        { id: 'arg1', kind: 'lit', label: '3', annotable: false, children: [] },
        { id: 'arg2', kind: 'lit', label: '4', annotable: false, children: [] }
      ]
    }
  ]
};

// annotation toggle state: true = annotation present
const annotOn = { let: true };

// Type environment: known function and variable types
const ENV = { fn_add: 'Int -> Int -> Int', result: 'Int', let: 'Int' };

// infer(node, expected): synthesize or check based on mode
// synthDirect: compute type without re-entering the Ann rule
function synthDirect(node) {
  if (node.kind === 'lit') return { type: 'Int', ok: true };
  if (node.kind === 'var' || node.kind === 'let') {
    const t = ENV[node.id] || null;
    return t ? { type: t, ok: true } : { type: '?', ok: false };
  }
  if (node.kind === 'app') {
    const fn = synthDirect(node.children[0] || {});
    if (!fn.ok || !fn.type.includes('->')) return { type: '?', ok: false };
    const retType = fn.type.split(' -> ').slice(1).join(' -> ');
    return { type: retType, ok: true };
  }
  return { type: '?', ok: false };
}

function infer(node, expected) {
  const hasAnnot = annotOn[node.id] && node.annotable && node.annot;
  if (hasAnnot) {
    // Ann rule: annotated node checks body against its declared type
    return check(node, node.annot);
  }
  if (node.kind === 'lit') {
    // Lit rule: integer literals synthesize Int
    return { mode: 'synth', type: 'Int', ok: true };
  }
  if (node.kind === 'var' || node.kind === 'let') {
    const t = ENV[node.id] || null;
    return t ? { mode: 'synth', type: t, ok: true }
             : { mode: 'synth', type: '?', ok: false };
  }
  if (node.kind === 'app') {
    // App rule: synthesize function type, check argument
    const fnResult = infer(node.children[0] || {}, null);
    if (!fnResult.ok || !fnResult.type.includes('->')) {
      return { mode: 'synth', type: '?', ok: false };
    }
    const parts = fnResult.type.split(' -> ');
    const argType = parts[0];
    const retType = parts.slice(1).join(' -> ');
    (node.children || []).forEach((ch, i) => {
      if (i > 0) infer(ch, argType);
    });
    return { mode: 'synth', type: retType, ok: true };
  }
  if (node.kind === 'lam') {
    // Lam<=check rule: check lambda body against expected return type
    if (expected && expected.includes('->')) {
      const parts = expected.split(' -> ');
      const retType = parts.slice(1).join(' -> ');
      infer(node.children[0] || {}, retType);
      return { mode: 'check', type: expected, ok: true };
    }
    // Lam without expected type: error — cannot synthesize argument type
    return { mode: 'error', type: '?', ok: false };
  }
  return { mode: 'synth', type: '?', ok: false };
}

function check(node, expected) {
  if (node.kind === 'lam') {
    if (expected && expected.includes('->')) {
      const parts = expected.split(' -> ');
      const retType = parts.slice(1).join(' -> ');
      infer(node.children[0] || {}, retType);
      return { mode: 'check', type: expected, ok: true };
    }
    return { mode: 'error', type: '?', ok: false };
  }
  // check fallback: synthesize then verify the type matches
  const r = synthDirect(node);
  if (!r.ok) return { mode: 'error', type: '?', ok: false };
  const match = !expected || r.type === expected || r.type === '?';
  return { mode: 'check', type: expected || r.type, ok: match };
}

// walk the tree, threading expected types downward
const nodeResults = {};
function walk(node, expected) {
  const r = infer(node, expected);
  nodeResults[node.id] = r;
  (node.children || []).forEach(ch => walk(ch, r.mode === 'check' ? r.type : null));
}

function runAlgorithm() {
  Object.keys(nodeResults).forEach(k => delete nodeResults[k]);
  walk(EXPR, null);
}

// Render the expression tree with mode badges
function renderTree(node, depth, isLast) {
  const container = document.getElementById('tree-container');
  if (depth === 0) container.innerHTML = '<div class="tree"></div>';
  const tree = container.querySelector('.tree');

  const r = nodeResults[node.id] || { mode: 'synth', type: '?', ok: true };
  const modeClass = r.ok ? r.mode : 'error';

  const row = document.createElement('div');
  row.className = 'node-row';

  for (let i = 0; i < depth; i++) {
    const ind = document.createElement('span');
    ind.className = 'indent';
    row.appendChild(ind);
  }
  if (depth > 0) {
    const conn = document.createElement('span');
    conn.className = 'connector';
    conn.textContent = isLast ? '└─' : '├─';
    row.appendChild(conn);
  }

  const nd = document.createElement('div');
  nd.className = 'node ' + modeClass;
  nd.title = (r.mode === 'check' ? '⇐ ' : r.mode === 'error' ? '⚠ ' : '⇒ ') + (r.type || '?');

  const kindSpan = document.createElement('span');
  kindSpan.className = 'kind';
  kindSpan.textContent = node.kind;
  nd.appendChild(kindSpan);

  const lbl = document.createElement('span');
  lbl.textContent = ' ' + node.label;
  nd.appendChild(lbl);

  if (node.annotable && annotOn[node.id]) {
    const a = document.createElement('span');
    a.className = 'annot';
    a.textContent = ': ' + node.annot;
    nd.appendChild(a);
  }

  if (node.annotable) {
    nd.addEventListener('click', () => {
      annotOn[node.id] = !annotOn[node.id];
      runAlgorithm();
      rerenderAll();
      updateStatus();
    });
  }

  row.appendChild(nd);
  tree.appendChild(row);

  (node.children || []).forEach((ch, i) => {
    const last = i === node.children.length - 1;
    renderNode(ch, depth + 1, last, tree);
  });
}

function renderNode(node, depth, isLast, tree) {
  const r = nodeResults[node.id] || { mode: 'synth', type: '?', ok: true };
  const modeClass = r.ok ? r.mode : 'error';

  const row = document.createElement('div');
  row.className = 'node-row';

  for (let i = 0; i < depth; i++) {
    const ind = document.createElement('span');
    ind.className = 'indent';
    row.appendChild(ind);
  }
  if (depth > 0) {
    const conn = document.createElement('span');
    conn.className = 'connector';
    conn.textContent = isLast ? '└─' : '├─';
    row.appendChild(conn);
  }

  const nd = document.createElement('div');
  nd.className = 'node ' + modeClass;
  nd.title = (r.mode === 'check' ? '⇐ ' : r.mode === 'error' ? '⚠ ' : '⇒ ') + (r.type || '?');

  const kindSpan = document.createElement('span');
  kindSpan.className = 'kind';
  kindSpan.textContent = node.kind;
  nd.appendChild(kindSpan);

  const lbl = document.createElement('span');
  lbl.textContent = ' ' + node.label;
  nd.appendChild(lbl);

  if (node.annotable && annotOn[node.id]) {
    const a = document.createElement('span');
    a.className = 'annot';
    a.textContent = ': ' + node.annot;
    nd.appendChild(a);
  }

  if (node.annotable) {
    nd.addEventListener('click', () => {
      annotOn[node.id] = !annotOn[node.id];
      runAlgorithm();
      rerenderAll();
      updateStatus();
    });
  }

  row.appendChild(nd);
  tree.appendChild(row);

  (node.children || []).forEach((ch, i) => {
    const last = i === node.children.length - 1;
    renderNode(ch, depth + 1, last, tree);
  });
}

function rerenderAll() {
  const container = document.getElementById('tree-container');
  container.innerHTML = '<div class="tree"></div>';
  const tree = container.querySelector('.tree');
  renderNode(EXPR, 0, true, tree);
  (EXPR.children || []).forEach((ch, i) => {
    const last = i === EXPR.children.length - 1;
    renderNode(ch, 1, last, tree);
  });
}

function countErrors() {
  return Object.values(nodeResults).filter(r => !r.ok).length;
}

function updateStatus() {
  const s = document.getElementById('status');
  const errs = countErrors();
  if (errs === 0) {
    s.textContent = '✓ All nodes typed correctly.';
    s.className = 'status ok';
  } else {
    s.textContent = i18nFmt('✗ %n% node(s) need an annotation or have a type error.', { n: errs });
    s.className = 'status err';
  }
}

function fullRender() {
  runAlgorithm();
  const container = document.getElementById('tree-container');
  container.innerHTML = '<div class="tree"></div>';
  const tree = container.querySelector('.tree');

  function rec(node, depth, isLast) {
    const r = nodeResults[node.id] || { mode: 'synth', type: '?', ok: true };
    const modeClass = r.ok ? r.mode : 'error';

    const row = document.createElement('div');
    row.className = 'node-row';

    for (let i = 0; i < depth; i++) {
      const ind = document.createElement('span');
      ind.className = 'indent';
      row.appendChild(ind);
    }
    if (depth > 0) {
      const conn = document.createElement('span');
      conn.className = 'connector';
      conn.textContent = isLast ? '└─' : '├─';
      row.appendChild(conn);
    }

    const nd = document.createElement('div');
    nd.className = 'node ' + modeClass;
    nd.title = (r.mode === 'check' ? '⇐ ' : r.mode === 'error' ? '⚠ ' : '⇒ ') + (r.type || '?');

    const kindSpan = document.createElement('span');
    kindSpan.className = 'kind';
    kindSpan.textContent = node.kind;
    nd.appendChild(kindSpan);

    const lbl = document.createElement('span');
    lbl.textContent = ' ' + node.label;
    nd.appendChild(lbl);

    if (node.annotable && annotOn[node.id]) {
      const a = document.createElement('span');
      a.className = 'annot';
      a.textContent = ': ' + node.annot;
      nd.appendChild(a);
    }

    if (node.annotable) {
      nd.addEventListener('click', () => {
        annotOn[node.id] = !annotOn[node.id];
        runAlgorithm();
        fullRender();
        updateStatus();
      });
    }

    row.appendChild(nd);
    tree.appendChild(row);
    (node.children || []).forEach((ch, i) => rec(ch, depth + 1, i === node.children.length - 1));
  }

  rec(EXPR, 0, true);
  updateStatus();
}

document.getElementById('btn-reset').addEventListener('click', () => {
  Object.keys(annotOn).forEach(k => delete annotOn[k]);
  annotOn['let'] = true;
  fullRender();
});

fullRender();

<!-- Interactive bidirectional type checking demo -->
<div class="toolbar">
  <span class="label">Expression tree — click annotable nodes to toggle annotations</span>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div id="tree-container"></div>
<div id="legend" class="legend">
  <span class="badge check">&#x21D0; Check mode</span>
  <span class="badge synth">&#x21D2; Synthesis mode</span>
  <span class="badge error">&#x26A0; Error</span>
</div>
<div id="status" class="status"></div>
<p class="hint">Click the top node to toggle its annotation. When the annotation is on, the whole tree is in check mode. When it is off, lambdas without a known argument type become errors.</p>

/* Bidirectional type demo styles */
* { 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; }
/* Tree layout */
.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; }

// Bidirectional type checking demo — two modes:
// check (<=): verify expression e against known type A
// synth (=>): compute type A from the structure of e
// Rules: Var=>synth, Lam<=check, App=>synth, Ann:check then synth
// Nodes with annotations always switch to check mode for their body.

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Expression tree: let result: Int = add 3 4
// let-binding node wrapping a function application
const EXPR = {
  id: 'let',
  kind: 'let',
  label: 'let result =',
  annot: 'Int',
  annotable: true,
  children: [
    {
      id: 'app',
      kind: 'app',
      label: 'add 3 4',
      annotable: false,
      children: [
        { id: 'fn_add', kind: 'var', label: 'add', annotable: false, children: [] },
        { id: 'arg1', kind: 'lit', label: '3', annotable: false, children: [] },
        { id: 'arg2', kind: 'lit', label: '4', annotable: false, children: [] }
      ]
    }
  ]
};

// annotation toggle state: true = annotation present
const annotOn = { let: true };

// Type environment: known function and variable types
const ENV = { fn_add: 'Int -> Int -> Int', result: 'Int', let: 'Int' };

// infer(node, expected): synthesize or check based on mode
// synthDirect: compute type without re-entering the Ann rule
function synthDirect(node) {
  if (node.kind === 'lit') return { type: 'Int', ok: true };
  if (node.kind === 'var' || node.kind === 'let') {
    const t = ENV[node.id] || null;
    return t ? { type: t, ok: true } : { type: '?', ok: false };
  }
  if (node.kind === 'app') {
    const fn = synthDirect(node.children[0] || {});
    if (!fn.ok || !fn.type.includes('->')) return { type: '?', ok: false };
    const retType = fn.type.split(' -> ').slice(1).join(' -> ');
    return { type: retType, ok: true };
  }
  return { type: '?', ok: false };
}

function infer(node, expected) {
  const hasAnnot = annotOn[node.id] && node.annotable && node.annot;
  if (hasAnnot) {
    // Ann rule: annotated node checks body against its declared type
    return check(node, node.annot);
  }
  if (node.kind === 'lit') {
    // Lit rule: integer literals synthesize Int
    return { mode: 'synth', type: 'Int', ok: true };
  }
  if (node.kind === 'var' || node.kind === 'let') {
    const t = ENV[node.id] || null;
    return t ? { mode: 'synth', type: t, ok: true }
             : { mode: 'synth', type: '?', ok: false };
  }
  if (node.kind === 'app') {
    // App rule: synthesize function type, check argument
    const fnResult = infer(node.children[0] || {}, null);
    if (!fnResult.ok || !fnResult.type.includes('->')) {
      return { mode: 'synth', type: '?', ok: false };
    }
    const parts = fnResult.type.split(' -> ');
    const argType = parts[0];
    const retType = parts.slice(1).join(' -> ');
    (node.children || []).forEach((ch, i) => {
      if (i > 0) infer(ch, argType);
    });
    return { mode: 'synth', type: retType, ok: true };
  }
  if (node.kind === 'lam') {
    // Lam<=check rule: check lambda body against expected return type
    if (expected && expected.includes('->')) {
      const parts = expected.split(' -> ');
      const retType = parts.slice(1).join(' -> ');
      infer(node.children[0] || {}, retType);
      return { mode: 'check', type: expected, ok: true };
    }
    // Lam without expected type: error — cannot synthesize argument type
    return { mode: 'error', type: '?', ok: false };
  }
  return { mode: 'synth', type: '?', ok: false };
}

function check(node, expected) {
  if (node.kind === 'lam') {
    if (expected && expected.includes('->')) {
      const parts = expected.split(' -> ');
      const retType = parts.slice(1).join(' -> ');
      infer(node.children[0] || {}, retType);
      return { mode: 'check', type: expected, ok: true };
    }
    return { mode: 'error', type: '?', ok: false };
  }
  // check fallback: synthesize then verify the type matches
  const r = synthDirect(node);
  if (!r.ok) return { mode: 'error', type: '?', ok: false };
  const match = !expected || r.type === expected || r.type === '?';
  return { mode: 'check', type: expected || r.type, ok: match };
}

// walk the tree, threading expected types downward
const nodeResults = {};
function walk(node, expected) {
  const r = infer(node, expected);
  nodeResults[node.id] = r;
  (node.children || []).forEach(ch => walk(ch, r.mode === 'check' ? r.type : null));
}

function runAlgorithm() {
  Object.keys(nodeResults).forEach(k => delete nodeResults[k]);
  walk(EXPR, null);
}

// Render the expression tree with mode badges
function renderTree(node, depth, isLast) {
  const container = document.getElementById('tree-container');
  if (depth === 0) container.innerHTML = '<div class="tree"></div>';
  const tree = container.querySelector('.tree');

  const r = nodeResults[node.id] || { mode: 'synth', type: '?', ok: true };
  const modeClass = r.ok ? r.mode : 'error';

  const row = document.createElement('div');
  row.className = 'node-row';

  for (let i = 0; i < depth; i++) {
    const ind = document.createElement('span');
    ind.className = 'indent';
    row.appendChild(ind);
  }
  if (depth > 0) {
    const conn = document.createElement('span');
    conn.className = 'connector';
    conn.textContent = isLast ? '└─' : '├─';
    row.appendChild(conn);
  }

  const nd = document.createElement('div');
  nd.className = 'node ' + modeClass;
  nd.title = (r.mode === 'check' ? '⇐ ' : r.mode === 'error' ? '⚠ ' : '⇒ ') + (r.type || '?');

  const kindSpan = document.createElement('span');
  kindSpan.className = 'kind';
  kindSpan.textContent = node.kind;
  nd.appendChild(kindSpan);

  const lbl = document.createElement('span');
  lbl.textContent = ' ' + node.label;
  nd.appendChild(lbl);

  if (node.annotable && annotOn[node.id]) {
    const a = document.createElement('span');
    a.className = 'annot';
    a.textContent = ': ' + node.annot;
    nd.appendChild(a);
  }

  if (node.annotable) {
    nd.addEventListener('click', () => {
      annotOn[node.id] = !annotOn[node.id];
      runAlgorithm();
      rerenderAll();
      updateStatus();
    });
  }

  row.appendChild(nd);
  tree.appendChild(row);

  (node.children || []).forEach((ch, i) => {
    const last = i === node.children.length - 1;
    renderNode(ch, depth + 1, last, tree);
  });
}

function renderNode(node, depth, isLast, tree) {
  const r = nodeResults[node.id] || { mode: 'synth', type: '?', ok: true };
  const modeClass = r.ok ? r.mode : 'error';

  const row = document.createElement('div');
  row.className = 'node-row';

  for (let i = 0; i < depth; i++) {
    const ind = document.createElement('span');
    ind.className = 'indent';
    row.appendChild(ind);
  }
  if (depth > 0) {
    const conn = document.createElement('span');
    conn.className = 'connector';
    conn.textContent = isLast ? '└─' : '├─';
    row.appendChild(conn);
  }

  const nd = document.createElement('div');
  nd.className = 'node ' + modeClass;
  nd.title = (r.mode === 'check' ? '⇐ ' : r.mode === 'error' ? '⚠ ' : '⇒ ') + (r.type || '?');

  const kindSpan = document.createElement('span');
  kindSpan.className = 'kind';
  kindSpan.textContent = node.kind;
  nd.appendChild(kindSpan);

  const lbl = document.createElement('span');
  lbl.textContent = ' ' + node.label;
  nd.appendChild(lbl);

  if (node.annotable && annotOn[node.id]) {
    const a = document.createElement('span');
    a.className = 'annot';
    a.textContent = ': ' + node.annot;
    nd.appendChild(a);
  }

  if (node.annotable) {
    nd.addEventListener('click', () => {
      annotOn[node.id] = !annotOn[node.id];
      runAlgorithm();
      rerenderAll();
      updateStatus();
    });
  }

  row.appendChild(nd);
  tree.appendChild(row);

  (node.children || []).forEach((ch, i) => {
    const last = i === node.children.length - 1;
    renderNode(ch, depth + 1, last, tree);
  });
}

function rerenderAll() {
  const container = document.getElementById('tree-container');
  container.innerHTML = '<div class="tree"></div>';
  const tree = container.querySelector('.tree');
  renderNode(EXPR, 0, true, tree);
  (EXPR.children || []).forEach((ch, i) => {
    const last = i === EXPR.children.length - 1;
    renderNode(ch, 1, last, tree);
  });
}

function countErrors() {
  return Object.values(nodeResults).filter(r => !r.ok).length;
}

function updateStatus() {
  const s = document.getElementById('status');
  const errs = countErrors();
  if (errs === 0) {
    s.textContent = '✓ All nodes typed correctly.';
    s.className = 'status ok';
  } else {
    s.textContent = i18nFmt('✗ %n% node(s) need an annotation or have a type error.', { n: errs });
    s.className = 'status err';
  }
}

function fullRender() {
  runAlgorithm();
  const container = document.getElementById('tree-container');
  container.innerHTML = '<div class="tree"></div>';
  const tree = container.querySelector('.tree');

  function rec(node, depth, isLast) {
    const r = nodeResults[node.id] || { mode: 'synth', type: '?', ok: true };
    const modeClass = r.ok ? r.mode : 'error';

    const row = document.createElement('div');
    row.className = 'node-row';

    for (let i = 0; i < depth; i++) {
      const ind = document.createElement('span');
      ind.className = 'indent';
      row.appendChild(ind);
    }
    if (depth > 0) {
      const conn = document.createElement('span');
      conn.className = 'connector';
      conn.textContent = isLast ? '└─' : '├─';
      row.appendChild(conn);
    }

    const nd = document.createElement('div');
    nd.className = 'node ' + modeClass;
    nd.title = (r.mode === 'check' ? '⇐ ' : r.mode === 'error' ? '⚠ ' : '⇒ ') + (r.type || '?');

    const kindSpan = document.createElement('span');
    kindSpan.className = 'kind';
    kindSpan.textContent = node.kind;
    nd.appendChild(kindSpan);

    const lbl = document.createElement('span');
    lbl.textContent = ' ' + node.label;
    nd.appendChild(lbl);

    if (node.annotable && annotOn[node.id]) {
      const a = document.createElement('span');
      a.className = 'annot';
      a.textContent = ': ' + node.annot;
      nd.appendChild(a);
    }

    if (node.annotable) {
      nd.addEventListener('click', () => {
        annotOn[node.id] = !annotOn[node.id];
        runAlgorithm();
        fullRender();
        updateStatus();
      });
    }

    row.appendChild(nd);
    tree.appendChild(row);
    (node.children || []).forEach((ch, i) => rec(ch, depth + 1, i === node.children.length - 1));
  }

  rec(EXPR, 0, true);
  updateStatus();
}

document.getElementById('btn-reset').addEventListener('click', () => {
  Object.keys(annotOn).forEach(k => delete annotOn[k]);
  annotOn['let'] = true;
  fullRender();
});

fullRender();

Result

Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

https://www.kipuhub.com/en/article/type-checking-bidirectional/Content licensed under CC BY-NC 4.0.

Cookies & privacy

Bidirectional Type Checking

When to tell the compiler and when to let it figure it out