First-class Refinement Types
in Scala

Matt Bovel, Viktor Kunčak and Martin Odersky
EPFL (Swiss Federal Institute of Technology in Lausanne, Switzerland)

October 6, 2026

Introduction

A refinement type is a type refined with a predicate.

For example,

\{ x: \text{Int} \mid x > 0 \}

denotes the type of integers x such that x > 0.

This talk presents:

  1. A prototype implementation of refinement types in Scala 3 as first-class types (§2, §4).
  1. A core calculus proven sound in Rocq for a pure subset of Scala; System F_{<:>} with refinements, dependent functions and positive equi-recursive types, under a partial correctness semantics (§3).

Part 1
Implementation

Syntax (§2.1)

Long form, mirroring the set-builder notation:

type NonEmpty[A] =
  {l: List[A] with l.nonEmpty}

Short form, reusing a name already in scope:

val x: (Int with x % 2 == 0) = 42
// desugars to:
val x: {v: Int with v % 2 == 0} = 42

Surveyed and implemented by Quentin Bernet for his Master thesis.

def zip[A, B](
  xs: List[A],
  ys: List[B] with ys.size == xs.size
): {zs: List[(A, B)] with zs.size == xs.size}
def concat[T](
  xs: List[T],
  ys: List[T]
): {zs: List[T] with zs.size ==
                       xs.size + ys.size}
val xs: List[Int] = …; val ys: List[Int] = …
zip(concat(xs, ys), concat(ys, xs))

Why first-class? (§1)

  1. It’s easier for us.
  2. It’s probably easier for users. See Usability Barriers for Liquid Types (Gamboa et al., PLDI 2025)
  3. It’s more expressive: refinement tyes are ordinary Scala types, participating in inference, overload resolution (1), subtyping (2), etc.
// Example 1: Overload resolution
def min(l: List[Int] with l.isSorted) =
  l.head // O(1)

def min(l: List[Int]) =
  l.min // O(n)

def ex1(l: List[Int] with l.isSorted) =
  min(l) // calls the first overload

Inspired by Abstract Refinement Types (Vazou et al., ESOP 2013).

// Example 2: Bounded polymorphism
given Ord[Int] = ...

type Even = {v: Int with v % 2 == 0}

def ex2: Even =
  maximum(List(2, 4, 6))
def maximum[T: Ord, U <: T](xs: List[U]): U =
  xs.reduce(max)

Mixed-precision type inference (§2.4)

Refinement types are not inferred from terms by default; the wider type is:

val x = 42 // Int, not {v: Int with v == 42}

Why not always infer the precise type?

  1. Backward compatibility: implicit and overload resolution depend on inferred types; a more precise type changes which instances are found.
  2. Performance: bigger types, slower comparisons.
  3. Usability: inferring most precise types everywhere would be unreadable.

Instead, precision is recovered on demand, by a standard mechanism called selfification, triggered by the bidirectional type-inference algorithm:

val x: (Int with x == 42) = 42 // selfified

Solver (§4.3)

How does the compiler check {x: T with p(x)} <: {x: T with q(x)}?

Need to check that p(x) implies q(x) for all x: T.

Existing implementations lower to SMT.

Due to packaging and performance concerns, we instead implemented our own lightweight e-graph-based solver.

{v: Int with v == a && a == b}
  <: {v: Int with v == b}
{v: Int with a == b}
  <: {v: Int with f(a) == f(b)}

And domain-specific normalizations such as:

{v: Int with v == x + 3 * y}
  <: {v: Int with v == 2 * y + (x + y)}

Also beta-reduction, ADT selections reductions and limited reasoning on LIA inequalities.

Run-time checks (§2.5)

Pattern matching branches on whether the predicate holds at run time:

type ID = {s: String with s.matches(idRegex)}

"a2e7-e89b" match
  case id: ID => ... // holds, id has type ID
  case _      => ... // does not hold

Evaluation (§4.4)

Compilation overhead, against each system’s own unchecked baseline:

System Overhead
First-class (ours) 0–13%
Schmid and Kunčak 20–41%
Stainless ≥ 53%

When the feature is unused, the full Dotty CI passes unchanged: the compiler itself (≈200 000 LoC),
≈10 000 tests, a 50-project community build.

≤ 4% slowdown on the official benchmark suite.

Part 2
Metatheory

Language (§3.1)

Essentially System F_{<:>} with refinements, dependent functions and pairs, sums, unions, intersections and equi-recursive types:

\begin{aligned} A, B ::=\ & X \mid \texttt{Unit} \mid \texttt{True} \mid \texttt{False} \mid \texttt{Int32} \mid \top \mid \bot \\ &\mid \Pi x{:}A.\, B \mid \forall (X {:>} L {<:} U).\, A \mid \Sigma x{:}A.\, B \\ &\mid A + B \mid \lbrace x : A \mid p \rbrace \mid A \lor B \mid A \land B \\ &\mid \mu X.\, A \end{aligned}

\begin{aligned} a, b, f, p ::=\ & c \mid x \mid \lambda x{:}A.\, b \mid f\; a \mid f\,[A] \\ &\mid \Lambda (X {:>} L {<:} U).\, b \mid \textsf{let}\; x{:}A = a \;\textsf{in}\; b \\ &\mid (a_1, a_2) \mid \textsf{inl}[A]\, a \mid \textsf{inr}[A]\, a \mid \textsf{match} \ldots \\ &\mid a \;\mathit{op}\; b \mid \textsf{if}\; a \;\textsf{then}\; b_1 \;\textsf{else}\; b_2 \mid \textsf{loop}(a)\; x.\, b \end{aligned}

\textsf{loop}(a)\; x.\, b suffices to model loops and tail recursion. The body returns \textsf{inl} to continue, \textsf{inr} to exit.

Values are a separate category:

\begin{aligned} v ::=\ & c \mid (v_1, v_2) \mid \textsf{inl}(v) \mid \textsf{inr}(v) \mid \langle \rho, \lambda x.\, b \rangle \mid \langle \rho, \Lambda X.\, b \rangle \end{aligned}

Definitional Interpreter (§3.2)

Operational semantic is defined using a fuel-bounded definitional interpreter:

Inspired by Type soundness proofs with definitional interpreters (Amin et al., POPL 2017).

Fixpoint eval (fuel: nat) (env: list Value) (t: Term) : option (option Value) :=
  match fuel with
  | 0 => None              (* timeout *)
  | S fuel' =>
    match t with
    | tabs _ b =>
        Some (Some (vabs env b))
    | tapp f a =>
        match eval fuel' env f with
        | Some (Some (vabs envf b)) =>
          … eval fuel' (va :: envf) b
        | None => None       (* timeout *)
        | _ => Some None     (* stuck *)
    …

Interpretation (§3.3)

The value interpretation \mathcal{V}\llbracket A \rrbracket_{\delta}^{\rho}(v) defines what it means for a value v to satisfy a type A, given a semantic type context \delta and a value environement \rho. See A Logical Approach to Type Soundness (Timany et al., JACM 2024).

\mathcal{V}\llbracket A \rrbracket_{\delta}^{\rho} is a semantic type (Value -> Prop).

The term interpretation \mathcal{E}\llbracket A \rrbracket_{\delta}^{\rho}(t) lifts it to terms:

\begin{aligned} \mathcal{E}\llbracket A \rrbracket_{\delta}^{\rho}(t) \triangleq\ & \forall n, r.\; \texttt{eval}\; n\; \rho\; t = \texttt{Some}\; r \implies \\ &\quad \exists v.\; r = \texttt{Some}\; v \land \mathcal{V}\llbracket A \rrbracket_{\delta}^{\rho}(v) \end{aligned}

“If evaluation terminates, it produces a value, and that value is in \mathcal{V}\llbracket A \rrbracket.” Vacuously true for diverging terms; this is partial correctness.

Value interpretation of refinement types:

\mathcal{V}\llbracket \lbrace x : A \mid p \rbrace \rrbracket_{\delta}^{\rho}(v) \triangleq \mathcal{V}\llbracket A \rrbracket_{\delta}^{\rho}(v) \land \mathcal{E}\llbracket \texttt{True} \rrbracket_{\delta}^{\rho[x \mapsto v]}(p)

Typing (§3.4)

Semantic typing is defined:

\Gamma \vDash a : A \triangleq \forall \delta, \rho.\; \mathrm{wf}(\delta, \Gamma, \rho) \implies \mathcal{E}\llbracket A \rrbracket_{\delta}^{\rho}(a)

The typing rules are not declared, they are lemmas.

A context \Gamma is made of:

  1. Term bindings: x : A
  2. Type variable bindings: X >: A <: B
  3. Equality facts: s \sim t

Rule for let-bindings:

\frac{\Gamma \vDash a : A \qquad \Gamma, x : A, x \sim a \vDash b : B}{\Gamma \vDash \textsf{let}\; x{:}A = a \;\textsf{in}\; b : \textsf{avoid}(B, x)}\;\text{(T-Let)}

Selfification rule:

\frac{\Gamma \vDash a : A \qquad \textsf{firstorder}(A)}{\Gamma \vDash a : \lbrace x : A \mid x \mathbin{\texttt{==}} a \rbrace}\;\text{(T-Self)}

Subtyping (§3.5)

Subtyping is semantic inclusion:

\Gamma \vDash A <: B \triangleq \forall \delta, \rho.\; \mathrm{wf}(\delta, \Gamma, \rho) \implies \mathcal{V}\llbracket A \rrbracket_{\delta}^{\rho} \subseteq \mathcal{V}\llbracket B \rrbracket_{\delta}^{\rho}

Every value satisfying A also satisfies B.

Recursive types are equi-recursive:

\frac{\textsf{spos}(X, A)}{\Gamma \vDash \mu X.\, A <: A[X \mapsto \mu X.\, A]}\;\text{(S-Mu-Unfold)}

\frac{\textsf{spos}(X, A)}{\Gamma \vDash A[X \mapsto \mu X.\, A] <: \mu X.\, A}\;\text{(S-Mu-Fold)}

Together they give \mu X.\, A <:> A[X \mapsto \mu X.\, A], provided X occurs only strictly positively in A.

Refinements Subtyping and Semantic Implication (§3.5)

Last but not the least, rules for refinement types:

\Gamma \vDash \lbrace x : A \mid p \rbrace <: A \;\text{(S-RefineBase)}

Subtyping between refinements is semantic implication, a.k.a. entailment:

\frac{\Gamma \vDash A <: B \qquad \Gamma, x : A \vDash p_1 \Rightarrow p_2}{\Gamma \vDash \lbrace x : A \mid p_1 \rbrace <: \lbrace x : B \mid p_2 \rbrace}\;\text{(S-Refine)}

A refinement \lbrace x : A \mid p \rbrace holds when p evaluates to true whenever it terminates. Implication reads both predicates that way:

\begin{aligned} \Gamma \vDash p_1 \Rightarrow p_2 \triangleq\ & \forall \delta, \rho.\; \mathrm{wf}(\delta, \Gamma, \rho) \implies \\ &\quad \mathcal{E}\llbracket \texttt{True} \rrbracket(p_1) \implies \mathcal{E}\llbracket \texttt{True} \rrbracket(p_2) \end{aligned}

Lemma:

\Gamma \vDash \lbrace x : A \mid \textsf{diverge} \rbrace \mathrel{<:>} \lbrace x : A \mid \texttt{true} \rbrace \mathrel{<:>} A

Wrap-up

Future work

Implementation:

  • Better Solver for what our lightweight solver cannot do.

  • A termination checker, needed only for the termination-sensitive entailment rules, never systematically for every function in a predicate.

  • Term-parameterized types, to modularize predicates:

    type Range(from: Int, to: Int) =
      {v: Int with v >= from && v < to}

Theory:

  • Rules for semantic implication. We leave implication purely semantic; the solver’s normalization rules are not yet verified against it.

  • Enforcing purity. Today a function called in a predicate is assumed pure. Capture and separation checking can ensure that predicates are pure.

  • Classes and objects, absent from the presented core calculus.

Conclusion

We showed:

  1. A prototype implementation of refinement types in Scala 3 as first-class types; normal Scala types that participate in subtyping, inference, overloads resolution and pattern matching.

  2. A core calculus proven sound in Rocq by semantic typing. It includes refinements, dependent functions and pairs, sums, unions, intersections and equi-recursive positive types, and allows predicates to diverge.

Un type raffiné,
by Marina Granados Castro

Bonus slides

Backup: LH Usability Barriers

From “Usability Barriers for Liquid Types” [1]:

  • 4.2 Unclear Divide between Haskell and LiquidHaskell:
    • “comments are usually seen as just optional information in the code and not something that is directly used by the compiler”
    • “It’s sort of like you’re doing two things at once because you’re implementing in Haskell. But you’re also talking to GHC, but you’re also talking to LiquidHaskell.”
  • 4.7 Unhelpful Error Messages
    • “[…] error messages produced from typing errors inside the predicates, seemed indistinguishable from those produced by verification errors.”
  • 4.8 Limited IDE Support
    • “[user] tried to use the function length, but since it was not imported, it was impossible to use in this case.”

[1] Catarina Gamboa, Abigail Reese, Alcides Fonseca, and Jonathan Aldrich. 2025. Usability Barriers for Liquid Types. Proc. ACM Program. Lang. 9, PLDI, Article 224 (June 2025), 26 pages. doi:10.1145/3729327

Backup: List.collect

Scala type parameters are erased at runtime, so we cannot match on a List[T].

However, we can use .collect to filter and convert a list:

type Pos = { v: Int with v >= 0 }

val xs = List(-1,2,-2,1)
xs.collect { case x: Pos => x } : List[Pos]

Backup: Value interpretation (more)

Value interpretation of function types:

\begin{aligned} \mathcal{V}\llbracket \Pi x{:}A.\, B \rrbracket_{\delta}^{\rho}(v) \triangleq\ & \exists \rho_f, b.\; v = \langle \rho_f, \lambda x.\, b \rangle\ \land \\ & \forall v_a.\; \mathcal{V}\llbracket A \rrbracket_{\delta}^{\rho}(v_a) \implies \mathcal{E}\llbracket B \rrbracket_{\delta}^{\rho_f[x \mapsto v_a]}(b) \end{aligned}

Value interpretation of recursive types?

\textcolor{red}{\mathcal{V}\llbracket \mu X.\, A \rrbracket_{\delta}^{\rho}(v) \triangleq \mathcal{V}\llbracket A \rrbracket_{\delta[X \mapsto \mathcal{V}\llbracket \mu X.\, A \rrbracket_{\delta}^{\rho}]}^{\rho}(v)}

\mathcal{V}\llbracket \mu X.\, A \rrbracket_{\delta}^{\rho}(v) \triangleq \forall n.\; F^n(v)

F^0(v) = \top,\quad F^{n+1}(v) = \mathcal{V}\llbracket A \rrbracket_{\delta[X \mapsto F^n]}^{\rho}(v)