Home / Docs / Language guide / Kinds and types
where and refinements
What it does
A refinement narrows a type by a predicate: Text where valid_phone(it) is the texts for which valid_phone holds, and Int in 0..5000 the integers from 0 to 5000. The compiler proves, at every place a value enters the refined type, that the predicate holds. The proof happens at compile time, before the program runs, so a program that checks never holds a value outside its refinement, relative to the solver and to the ensures clauses of capability operations, which are assumed, not proven: a host implementation is trusted to satisfy them.
Learn more: Refined kinds and predicates.
module shop
pub kind Seats = Int in 0..5000
pub kind Event
name: Text
remaining: Seats
pub book(e: Event, count: Int) -> Seats
requires count >= 1
requires count <= e.remaining
=
e.remaining - countForms
In the grammar below, each rule gives a name, =, what the name stands for and ;, quoted words are written as shown, NEWLINE, INDENT and DEDENT stand for a line break and for one more or one less level of indentation, [ ] marks an optional part, { } a part that may repeat, | separates alternatives, ( ) groups them, and (* *) holds a comment.
alias_body = "=" type [ "where" line_expr ] NEWLINE ;
type = [ label ] type_core [ "in" range ] ;
range = signed_int ( ".." | "..<" ) signed_int ;T where p, wherepis written in the refinement language, the small set of expressions listed below that the verifier can decide, anditnames the value.- Range sugar:
T in a..bmeansT where a <= it and it <= b, andT in a..<bmeansT where a <= it and it < b.
The refinement language is what the verifier, the part of una check that proves what the program must keep, decides:
- integer, boolean and text literals;
it, parameters, and field access on them;.lenonTextandList;+,-, unary-,*with a literal operand, and/andmodby a nonzero literal;==,!=,<,<=,>,>=,in range,is Variant;and,or,not,implies;- calls of predicates. See
predicate.
Examples
In the body above, the preconditions give the facts that prove e.remaining - count lies in 0..5000. A caller that cannot show a value fits is refuted, with a counterexample:
-- fails with U5001
module shop
pub kind Seats = Int in 0..5000
pub to_seats(count: Int) -> Seats = countA guard is enough when it gives the facts. In the last else branch the verifier knows not (raw < 0) and not (raw > 5000), so raw lies in 0..5000, and in the then branches the literals fit:
module shop
pub kind Seats = Int in 0..5000
pub cap_seats(raw: Int) -> Seats = if raw < 0 then 0 else if raw > 5000 then 5000 else rawA predicate makes a refinement readable, and a reflect predicate's definition is visible to the solver, the program that decides each obligation:
module shop
pub predicate reflect adult(age: Int) -> Bool = age >= 18
pub kind Adult = Int where adult(it)
pub grow(a: Adult) -> Adult = a + 1Edge cases
Only the refinement language. An expression outside it is U2014, at the outermost offending part. Outside it are the ordering of Text, is with a literal, == against a variant, unit and interpolated text:
-- fails with U2014
module shop
pub kind Late = Text where it > "m"Refinements are top-level. In editions 0.1 and 0.2, a refined kind cannot be a type argument, so List[Quantity] is ill-formed. Refine the list itself, or check each element where it is used:
-- fails with U2002
module shop
pub kind Quantity = Int where it > 0
pub kind Order
quantities: List[Quantity]Further rules:
- Structural over the base. A refined value is a value of its base, with no conversion; only entering the refinement creates an obligation.
- Stacking. A refinement of a refined kind conjoins both predicates.
itis valid only inwhereclauses and in the predicate ofchecked(U2013). In edition0.3, where an operation's condition is also written withwhere, a kind'swherecounts, not the condition on an operation.- Unknown is not proven. An obligation, a fact the program must be shown to keep, that the solver cannot decide is an error, U5002, never a pass.
- Opaque facts. A refinement may name an opaque predicate, whose fact a value obtains only through
checked. Seechecked. - Function kinds.
kind F = fn(Int) -> Int where good(it)is ill-formed. Refine the parameters or the result (U2002).
Diagnostics
- U2002: a refined type argument in editions
0.1and0.2, or a refinement of a function type. - U2013:
itoutside awhereclause or the predicate ofchecked. - U2014: a predicate outside the refinement language.
- U5001: a value that may not satisfy the refinement it enters, with a counterexample.
- U5002: an obligation the solver cannot decide.
Edition
Refinements are the same in editions 0.1 and 0.2. In edition 0.2, a fixed-width integer type can be refined too, as kind Port = U16 where it > 0. Edition 0.3 accepts refined type arguments, as List[Quantity]: every value put into such a position must be proven to satisfy the refinement, and every value read from it carries it.
Normative source
- spec/03 §2: rules 2 and 3; spec/03 §3: the refinement language, range sugar, refined type arguments and function kinds.
- spec/02 §2: the grammar; spec/02 §8: where
itmay appear. - spec/12 §2: the decidable fragment; spec/12 §3: the
refinementobligation; spec/12 §6: statuses. - spec/03 §4: predicates, and opaque facts.
- spec/18 §1: refined fixed-width integers.
- Decision records: ADR 0040, for refined type arguments in editions
0.1and0.2; ADR 0103, for refined type arguments in edition0.3; ADR 0092, foritin edition0.3; ADR 0045, for refined function kinds.