Refinement Types

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 : \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.

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?

<!-- {{c_html_intro}} -->
<p class="intro">{{intro_text}}</p>
<div id="variables-list"></div>
<div class="btns">
  <button id="check-btn" type="button">{{btn_check}}</button>
  <button id="reset-btn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="result" class="result" aria-live="polite"></div>

/* {{c_css_intro}} */
* { 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; }

// Code not found

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.

How hard is it to check refinement types?

• For concrete literals, checking $\{v : \text{Int} \mid v > 0\}$ against the value $5$ 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 : \text{List} \mid \text{sorted}(v)\}$ unless "sorted" is expressible in linear arithmetic, which it generally is not without ghost variables or auxiliary lemmas.

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.

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.