Questions: Liquid Types

Question 1

A function is declared with liquid type `incr :: x:{Int | x >= 0} -> {y:Int | y > x}`. What does the type checker verify when this function is called with argument 5?

Model answer: The type checker verifies that: (1) the argument 5 satisfies the precondition {x:Int | x >= 0} (which it does: 5 >= 0), and (2) assuming the function is correctly implemented, the returned value satisfies the postcondition {y:Int | y > x} where x is bound to 5 (so the return value must be > 5). If the function actually returns an Int without additional constraints, the type checker would report an error unless the function is proven to satisfy the stronger output type. The SMT solver is used internally to check these logical constraints.

Liquid type checking turns type verification into SMT problems. Each function call generates constraints that the SMT solver discharges. For the call `incr(5)`, the solver checks: does 5 satisfy the precondition? (yes: 5 >= 0 is satisfiable). Does the function's implementation guarantee the postcondition? (type checker recursively checks the function body). The power is that the user writes types with logical refinements, and the checker automates the reasoning rather than requiring manual proofs.

Question 2

Liquid types restrict refinement predicates to a decidable fragment (typically quantifier-free linear arithmetic). Why not allow arbitrary logic like full first-order logic?

Model answer: Arbitrary first-order logic is undecidable — no algorithm can determine whether a formula is satisfiable. This would make type checking undecidable, requiring the user to provide manual proofs. By restricting to quantifier-free linear arithmetic (QF_LIA) or similar decidable theories, liquid type checking becomes a decision problem: the SMT solver always terminates with a yes/no answer. This enables fully automatic type checking without user-written proofs, though it limits the expressiveness of refinements to quantifier-free predicates.

The name 'liquid' captures the idea: types are 'liquid' (fluid, flexible) in their expressiveness — you can refine any type with any quantifier-free predicate. But they're not so expressive that checking becomes undecidable. This is a careful balance: dependent types (like Coq or Agda) have full expressiveness but require users to prove refinement properties; liquid types have restricted expressiveness but automatic checking. Research into more expressive logics (e.g., allowing some quantifiers in restricted forms) is ongoing.

Question 3

Liquid Haskell verifies a function `divide :: x:Nat -> y:{Nat | y != 0} -> Nat`. When type-checking a call `divide(10, 0)`, what happens?

• A. The function executes and raises a runtime error
• B. The type checker rejects the program at compile time because the argument 0 does not satisfy the liquid type {y:Nat | y != 0}
• C. The type checker warns but allows the code to compile
• D. The type checker asks the user to provide a proof that 0 != 0

Answer: (B)

Liquid type checking is compile-time verification. The SMT solver checks whether the argument 0 satisfies the constraint y != 0. Since 0 = 0 is true (the constraint is unsatisfiable), the solver reports UNSAT and the type checker rejects the program. No runtime error occurs because the error is caught statically. This is the power of refinement types: division-by-zero is no longer a runtime error but a compile-time type error, caught before the program executes.

Question 4

Consider a function `sum :: xs:[Int]<{v:Int | v > 0}> -> {n:Int | n > 0}` that sums a non-empty list of positive integers. How would a liquid type checker verify this?

Model answer: The type checker would verify: (1) the input is a list of integers, each greater than 0; (2) the output is an integer greater than 0. For the function body (likely a recursion or fold), the checker generates proof obligations for each expression: if you sum positive integers, the result is positive. The SMT solver checks this arithmetic property automatically. If the function is correctly implemented, all obligations are discharged (the solver returns SAT); if not, the solver finds a counterexample (an input that violates the postcondition).

This example shows liquid types in action: instead of manually proving 'sum of positive integers is positive,' you write the types with logical refinements and the checker verifies them. The SMT solver handles the arithmetic reasoning, making it practical for real code. This is the key advantage over full dependent types: you avoid writing explicit proofs while still getting strong correctness guarantees.