Liquid Types

Core Idea

Liquid types refine dependent types with liquid type checking — a technique that restricts refinements to a decidable subset of predicates (typically quantifier-free linear arithmetic), enabling fully automatic type checking via SMT solving. Rather than requiring users to manually prove type constraints (as in full dependent type theory), a liquid type checker automatically discharges proof obligations using an SMT solver. A liquid type for a list might be `[Int]<{v:Int | v > 0}>` (a list of positive integers). The type checker enforces this by verifying that all list-construction operations produce values satisfying the refinement, using SMT calls internally. Liquid Haskell is the most mature implementation, embedding liquid types into Haskell for practical verification without sacrificing automation or ease of use.

Explainer

Dependent types (in languages like Coq or Agda) allow types to depend on values, enabling extremely expressive type systems that can express complex properties. A dependent type `Vec(n)` represents vectors of exactly length n; you can express "the result is a list of length equal to the input" as a type. But dependent types come at a cost: verifying that a function satisfies its dependent type requires manual proofs, and the proof process is interactive and labor-intensive.

Liquid types strike a pragmatic balance. They refine ordinary types with logical predicates (drawn from a decidable logic), enabling strong correctness guarantees without manual proofs. The refinement is expressed as a liquid type annotation — a predicate that values of that type must satisfy. A liquid type for a list of positive integers is `{xs : [Int] | all(xs, \x -> x > 0)}` (in Liquid Haskell: `[Int]<{v:Int | v > 0}>`). The type checker automatically verifies that list operations maintain this invariant using SMT solving.

The key innovation is the restriction to decidable logics, typically quantifier-free linear arithmetic (QF_LIA) over integers. This logic is expressive enough to reason about:

• Numeric bounds (x >= 0, x < 100)
• Arithmetic relationships (y = x + 1, n > sum)
• Logical combinations (x > 0 && y < 10)

But it excludes:

• Unrestricted quantification (∃x. P(x) for arbitrary P)
• Nonlinear arithmetic (x * y > 0, when x and y are variables)
• General recursion and induction

Restricting to this fragment makes the decision problem tractable: an SMT solver like Z3 can always determine whether a constraint is satisfiable in bounded time.

Liquid Haskell (developed at UC San Diego) is the most mature implementation. Users write Haskell code with liquid type annotations:

```haskell

-- A natural number (Int >= 0)

{-@ type Nat = {v:Int | v >= 0} @-}

-- A function that divides x by y, where y != 0

{-@ divide :: x:Int -> y:{Int | y != 0} -> Int @-}

divide x y = x `div` y

```

When this function is called with a non-zero divisor (e.g., `divide(10, 3)`), the type checker verifies the constraint is satisfied. If called with zero (e.g., `divide(10, 0)`), the checker rejects it at compile time — division by zero is a type error, not a runtime error. The user writes the type annotation once; the checker verifies it everywhere the function is called.

The checking process is fully automatic: the type checker generates SMT queries and delegates them to a solver (typically Z3). No user-written proofs, no interactive tactic languages, no expertise in formal logic required. This automation is the pragmatic breakthrough that makes liquid types practical for real code.

Applications include:

• NASA/JPL verification: Liquid Haskell has been applied to verify properties of spacecraft control software.
• Industry adoption: Used at companies like Google and others for code verification without the burden of interactive theorem proving.
• Specification libraries: Liquid Haskell includes libraries with refined types for standard data structures (lists, sets, maps) with properties like sortedness, disjointness, and size.

The limitations are inherent to the decidable logic restriction: you cannot express arbitrary mathematical properties or non-linear constraints. But for the common case of verifying safety and liveness properties (bounds, non-negativity, ordering, absence of errors), the automatic checking makes liquid types a practical and popular choice.

Current research extends liquid types to more expressive logics (nonlinear arithmetic with limited quantification, temporal properties) while maintaining decidability, and integrates them with other type system features (generics, polymorphism, modules) for real-world software verification.