Introduction

Ordinary type systems can tell you a variable is an Int, but they cannot tell you whether that Int is ever negative when it shouldn't be. Refinement types close that gap: a type like {v:Int∣v>0}\{v : \text{Int} \mid v > 0\} says "an integer and it must be positive," and the compiler enforces the predicate automatically using an SMT solver (a constraint-reasoning engine).

The idea is deceptively simple. Instead of writing a defensive if (n <= 0) throw ... everywhere and hoping no branch was forgotten, you write the condition once, in the type. Every assignment to that variable becomes a proof obligation — the compiler asks the SMT solver "can this value possibly violate the predicate?" and rejects the program if the answer is yes.

This is not just tidier code. It is a fundamentally different relationship between types and logic: types become first-class specifications, and checking them is mechanical theorem-proving at the scale of a whole codebase.

Try It

Below are three variables, each carrying a refinement predicate. Pick a value for each one and press Check — the demo simulates what an SMT solver decides: does the value satisfy the predicate, or is the program rejected?

<!-- Refinement-type checker demo: each variable carries a logical predicate -->
<p class="intro">Each variable has a refinement predicate. Enter a value and press Check — the demo shows whether the value satisfies the predicate, just like an SMT solver would decide at compile time.</p>
<div id="variables-list"></div>
<div class="btns">
  <button id="check-btn" type="button">Check</button>
  <button id="reset-btn" type="button" class="ghost">Reset</button>
</div>
<div id="result" class="result" aria-live="polite"></div>

/* Layout for the refinement-type checker demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 15px; }
.intro { font-size: .9rem; color: #444; margin: 0 0 1rem; line-height: 1.45; }
.var-row { display: flex; flex-wrap: wrap; align-items: center; gap: .5rem;
           border: 1px solid #d0d7de; border-radius: 8px; padding: .6rem .8rem;
           margin-bottom: .6rem; background: #f6f8fa; }
.type-badge { font: 600 12px ui-monospace, monospace; background: #1d3557; color: #fff;
              border-radius: 5px; padding: 2px 7px; white-space: nowrap; }
.var-name { font: 700 14px ui-monospace, monospace; color: #333; min-width: 3ch; }
.colon { color: #666; }
.pred-badge { font: 600 11px ui-monospace, monospace; background: #e8eef3; color: #1d3557;
              border: 1px solid #cdd9e3; border-radius: 5px; padding: 2px 7px; white-space: nowrap; }
label.eq { font: 600 13px system-ui; color: #555; }
input[type=number] { width: 80px; padding: .3rem .45rem; border: 1px solid #adb1b8;
                     border-radius: 6px; font: 14px ui-monospace, monospace; text-align: center; }
input[type=number]:focus { outline: 2px solid #1d3557; border-color: #1d3557; }
.var-status { font: 600 12px system-ui; margin-left: auto; }
.var-status.ok { color: #0a7d33; }
.var-status.bad { color: #c92f3c; }
.var-status.idle { color: #aaa; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.result { font-size: 1rem; font-weight: 600; min-height: 1.4em; }
.result.ok { color: #0a7d33; }
.result.bad { color: #c92f3c; }
.result.idle { color: #888; }

// Refinement-type checker: three variables each annotated with a predicate.
// Checking a concrete literal is trivial arithmetic; for symbolic expressions
// an SMT solver decides satisfiability (decidable for linear arithmetic).

// Variable definitions: name, base type, display predicate, and check function.
const VARS = [
  { name: 'dividend', type: 'Int', pred: 'v != 0',    check: v => v !== 0 },
  { name: 'index',    type: 'Int', pred: '0 <= v < 8', check: v => v >= 0 && v < 8 },
  { name: 'percent',  type: 'Int', pred: '0 <= v <= 100', check: v => v >= 0 && v <= 100 }
];

const inputs = {};

function buildUI() {
  // Build one row per variable with a type badge, name, predicate, and input.
  const list = document.getElementById('variables-list');
  list.innerHTML = '';
  VARS.forEach(def => {
    const row = document.createElement('div');
    row.className = 'var-row';
    row.dataset.name = def.name;

    const badge = document.createElement('span');
    badge.className = 'type-badge';
    badge.textContent = def.type;

    const varName = document.createElement('span');
    varName.className = 'var-name';
    varName.textContent = def.name;

    const colon = document.createElement('span');
    colon.className = 'colon';
    colon.textContent = ' | ';

    const pred = document.createElement('span');
    pred.className = 'pred-badge';
    pred.textContent = def.pred;

    const eq = document.createElement('label');
    eq.className = 'eq';
    eq.textContent = ' = ';

    const inp = document.createElement('input');
    inp.type = 'number';
    inp.placeholder = '?';
    inp.title = 'Enter an integer value';
    inp.setAttribute('aria-label', def.name);
    inputs[def.name] = inp;

    const status = document.createElement('span');
    status.className = 'var-status idle';
    status.textContent = '—';
    status.id = 'status-' + def.name;

    row.appendChild(badge);
    row.appendChild(varName);
    row.appendChild(colon);
    row.appendChild(pred);
    row.appendChild(eq);
    row.appendChild(inp);
    row.appendChild(status);
    list.appendChild(row);
  });
}

function setVarStatus(name, ok, text) {
  // Update the per-variable status indicator.
  const el = document.getElementById('status-' + name);
  if (!el) return;
  el.className = 'var-status ' + (ok === null ? 'idle' : ok ? 'ok' : 'bad');
  el.textContent = text;
}

function checkAll() {
  // Validate every input against its predicate and show the overall result.
  let allOk = true;
  let anyBlank = false;

  VARS.forEach(def => {
    const raw = inputs[def.name].value.trim();
    if (raw === '') {
      setVarStatus(def.name, null, '—');
      anyBlank = true;
      return;
    }
    const v = parseInt(raw, 10);
    const ok = def.check(v);
    if (!ok) allOk = false;
    setVarStatus(def.name, ok, ok ? '✓ ok' : '✗ rejected');
  });

  const res = document.getElementById('result');
  if (anyBlank) {
    res.textContent = 'Enter a value for every variable first.';
    res.className = 'result idle';
  } else if (allOk) {
    res.textContent = '✓ All values satisfy their refinement predicates — program accepted!';
    res.className = 'result ok';
    // All refinement predicates satisfied.
    console.log('All refinement predicates satisfied.');
  } else {
    res.textContent = '✗ One or more values violate their predicates — program rejected at compile time.';
    res.className = 'result bad';
    // Refinement violation detected — program would be rejected.
    console.log('Refinement violation detected — program would be rejected.');
  }
}

function resetAll() {
  // Clear all inputs and reset status indicators.
  VARS.forEach(def => {
    inputs[def.name].value = '';
    setVarStatus(def.name, null, '—');
  });
  const res = document.getElementById('result');
  res.textContent = '';
  res.className = 'result idle';
}

document.getElementById('check-btn').addEventListener('click', checkAll);
document.getElementById('reset-btn').addEventListener('click', resetAll);
buildUI();
Result
Console

Notice the asymmetry. Writing {v:Int | v>0} costs nothing extra; checking it for a concrete literal is instant arithmetic. The hard work happens when the value comes from a complex expression — the solver must reason about all possible inputs, which is why, in general, refinement checking is undecidable for arbitrary predicates (it reduces to the halting problem). Practical systems restrict predicates to decidable theories — linear arithmetic, uninterpreted functions — so the solver always terminates.

The Real Complexity

How hard is it to check refinement types?

  • For concrete literals, checking {v:Int∣v>0}\{v : \text{Int} \mid v > 0\} against the value 55 is just arithmetic — trivially decidable.
  • For general programs, deciding whether every execution path satisfies every predicate reduces to checking the satisfiability of logical formulas over program states. For arbitrary first-order logic this is undecidable — equivalent to deciding the halting problem.
  • Practical systems restrict the predicate language. Liquid types (Rondon, Kawaguchi & Jhala, 2008) restrict predicates to quantifier-free linear arithmetic and uninterpreted functions — both within the decidable fragment handled by modern SMT solvers (Z3, CVC5). Under this restriction, every proof obligation is dischargeable in practice in polynomial time on average.
  • Inference is also decidable in the liquid-types setting: the system infers the strongest refinements for intermediate variables automatically using Hindley-Milner extended with a fixpoint computation over predicate templates.

The result is a sweet spot: expressive enough to catch real bugs (array out of bounds, division by zero, negative indices), yet the solver always gives a definite yes-or-no answer. The price is expressiveness — you cannot write {v:List∣sorted(v)}\{v : \text{List} \mid \text{sorted}(v)\} unless "sorted" is expressible in linear arithmetic, which it generally is not without ghost variables or auxiliary lemmas.

Where It Matters

Refinement types have moved from theory into real tools used by practitioners:

  • Array safety: a function typed (a: Array, i: {v:Int | 0 <= v && v < a.length}) -> T makes an out-of-bounds access a compile-time error, not a runtime crash. LiquidHaskell uses exactly this.
  • Financial arithmetic: currencies should never go negative; balances should sum correctly. Refinement types enforce these invariants statically across an entire banking codebase.
  • Cryptographic APIs: many cryptographic APIs require keys or nonces of exact sizes. F* (used in the verified HTTPS library HACL*) uses refinements to ensure buffer lengths are correct at the type level.
  • Compiler verification: Dafny, a programming language designed for verification, uses refinement-style specifications called postconditions and preconditions as types, and its SMT backend rejects any program that cannot be proved correct.
  • Teaching formal methods: refinement types are the gentlest on-ramp to program verification — the concept of "a type is a proposition" becomes concrete the first time the compiler rejects your negative divisor.

Wherever a program carries invariants that base types cannot express — positivity, ordering, length constraints — refinement types turn runtime disasters into compile-time diagnostics. They are closely related to program synthesis: a synthesizer can search for programs that satisfy a given refinement type as its specification.

Conclusion

Refinement types reveal something profound about the relationship between types and proofs: a type annotated with a predicate is a specification, and every assignment to it is a theorem the compiler must verify. Practical systems such as LiquidHaskell and F* restrict predicates to decidable fragments, letting an SMT solver discharge obligations automatically — catching array overflows, division by zero, and broken invariants at compile time with no runtime overhead.

The undecidability lurking beneath the surface is real, but the art of refinement types is in choosing predicate languages expressive enough to be useful yet restricted enough to stay decidable. In that careful middle ground, a compiler can silently prove thousands of safety properties about your program before it ever runs — and the bugs it cannot catch are the ones you at least know you have to argue about yourself.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/refinement-types/Content licensed under CC BY-NC 4.0.