Home / Docs / Language guide

Kinds and types

Release v0.4.0

3.1 Built-in types

Type Values Notes
Int mathematical integers unbounded
I8, I16, I32, I64 -2^(n-1) to 2^(n-1) - 1 edition 0.2; overflow is a proof obligation
U8, U16, U32, U64 0 to 2^n - 1 edition 0.2; overflow is a proof obligation
Nat Int where it >= 0 prelude alias
Bool true, false
Text Unicode strings t.len counts Unicode scalar values; in edition 0.2, split, join, find, contains_text, ends_with, replace, slice, chars, bytes, to_upper, to_lower, trim_start, trim_end and parse_int (spec/22)
Unit unit
List[T] or [T] [1, 2, 3] values; xs.len; changed through set and append (§5.6)
Map[K, V] empty_map().with(key: "a", value: 1) edition 0.2; keys satisfy Ord, in ascending order; m.len, has, get, keys, values, entries, with, without, and edit m.set and edit m.remove (spec/21)
Option[T] Some(value), None
Result[T, E] Ok(value), Err(failure) produced by attempt (§6.4)
Hashed opaque digests produced by the Keys capability; only == and !=
fn(A, B) -> C lambdas and named functions not comparable

Fixed-width integers (edition 0.2, spec/18). They exist where an exact width matters, such as bytes, protocols and hashing. Int stays where it was: list lengths, indices and Text.len are Int.

una
module demo

pub kind Port = U16 where it > 0

--- Literals take the fixed-width type their context expects.
pub defaults() -> List[U8] = [0, 127, 255]

pub maybe_byte(flag: Bool) -> Option[U8] = if flag then Some(200) else None

--- Overflow is an obligation: `a + b` must fit in `U8`. Clauses compute exactly, so `a + b <= 255` is the mathematical sum.
pub add_small(a: U8, b: U8) -> U8
  requires a + b <= 255
=
  a + b

--- Wrapping arithmetic is written out, never implied.
pub checksum(a: U8, b: U8) -> U8 = a.wrapping_add(by: b)

--- Widening needs no proof; narrowing does.
pub widen(x: U8) -> I32 = x.to_i32()

pub narrow(x: I32) -> U8
  requires x >= 0 and x <= 255
=
  x.to_u8()
una
-- fails with U5001
module demo

pub add(a: U8, b: U8) -> U8 = a + b
una
-- fails with U2022
module demo

pub too_big() -> U8 = 300
una
-- fails with U2001
module demo

pub mixed(a: U8, b: U16) -> U16 = a + b

The overflow diagnostic proposes, in order: a guard computed on Int, as if a.to_int() + b.to_int() in 0..255; a wider type through explicit conversions; or a wrapping or saturating method, when that is the arithmetic meant.

3.2 Declaring kinds

A kind declaration takes one of four forms: an alias, a refinement, a sum and a record. Any of them may take type parameters (§3.3).

una
module demo

pub kind Label = Text

pub kind Phone = Text where valid_phone(it)

pub kind Seats = Int in 0..5000

pub kind Availability = SoldOut | Few | Open

pub kind Registration
  name: Text
  phone: Phone

pub kind Lookup = Found(registration: Registration) | Missing

pub kind Event
  name: Text
  remaining: Seats

pub kind NonEmpty[T] = List[T] where it.len > 0

pub kind PhoneError = | Malformed

pub predicate opaque valid_phone(t: Text) -> Bool = t.len == 11 and is_digits(t)

Rules:

Recursive kinds (edition 0.2, ADR 0060). A kind may contain itself through any field, as long as it has a finite value: some variant (or, for a record, every field) needs no value of a kind without one. Inside a recursion, the kinds of the recursion take only type parameters as arguments.

una
module demo

--- `Lit` is a finite value, so `Expr` may contain itself through any field.
pub kind Expr = Lit(value: Int) | Add(left: Expr, right: Expr) | Neg(inner: Expr)

pub eval(e: Expr) -> Int
=
  when e
    is Lit(value) -> value
    is Add(left, right) -> eval(left) + eval(right)
    is Neg(inner) -> -eval(inner)

--- A generic recursive kind passes on only its own type parameter.
pub kind Tree[T] = Leaf | Node(left: Tree[T], item: T, right: Tree[T])

pub size[T](t: Tree[T]) -> Int
=
  when t
    is Leaf -> 0
    is Node(left, right) -> size(left) + 1 + size(right)

A kind without a finite value is U2002, with a repair:

una
-- fails with U2002
module demo

pub kind Stream = | Cons(head: Int, tail: Stream)

In edition 0.1, a kind may contain itself only through List or Option fields:

una
-- fails with U2002
-- edition 0.1
module demo

pub kind Expr = Lit(value: Int) | Add(left: Expr, right: Expr)

3.3 Generics and constraints

Kinds and functions can take type parameters, and type arguments are inferred at call sites. Without a constraint, the only operations on a type parameter are those that function parameters provide.

In edition 0.2 (ADR 0066, spec/20), a function's type parameter can carry one built-in constraint:

Constraint Allows on values of T Satisfied by
Eq ==, != every type whose values hold no functions
Ord what Eq allows, and <, <=, >, >= Int, I8 to U64, Text, and sums whose variants have no payload
Integer what Ord allows, and x.to_int() Int, I8 to U64
una
module demo

--- Unconstrained: only what the function parameters provide.
pub first_or[T](xs: List[T], default: T) -> T = xs.first().or_else(default)

--- `Ord` allows comparisons; `max` is generic over `Ord` in edition 0.2.
pub largest[T: Ord](xs: List[T], floor: T) -> T = xs.fold(initial: floor, step: fn(best, x) -> max(best, b: x))

--- `Eq` allows `==` and `!=`.
pub same[T: Eq](a: T, b: T) -> Bool = a == b

pub has[T: Eq](xs: List[T], item: T) -> Bool = xs.contains(item)

--- `Integer` adds `to_int()`; arithmetic happens on `Int`.
pub total[T: Integer](xs: List[T]) -> Int = xs.map(each: fn(x) -> x.to_int()).sum()

pub ranked(names: List[Text]) -> List[Text] = sort(names)
una
-- fails with U2026
module demo

pub same[T](a: T, b: T) -> Bool = a == b
una
-- fails with U2025
module demo

pub kind Shape = Circle(radius: Int) | Square(side: Int)

pub biggest(shapes: List[Shape]) -> List[Shape] = sort(shapes)

In edition 0.1, type parameters are unconstrained, and equality on one is allowed with an inferred bound: the function cannot be instantiated with a type whose values hold functions (U2001).

3.4 The refinement language (RL)

where, requires and ensures accept only expressions the verifier can reason about:

Allowed Examples
Integer and boolean literals 0, true
it, parameters, result, old(x) of an edit parameter, and field access on them it.remaining, e.remaining, old(t).seen
Length of Text and List it.len, xs.len
Linear arithmetic a + b, a - b, -a, 3 * a; / and mod only by a nonzero literal
Comparisons and ranges ==, !=, <, <=, >, >=, x in 1..10
Variant tests, with is only result is SoldOut, not (result is Open); == or != against a variant, as in result != Open, is U2014
Boolean connectives and, or, not, implies
Predicate calls valid_phone(it), adult(age)

Anything else, such as calls to ordinary functions, methods such as x.to_int(), or a * b with two variables, is U2014, reported on the outermost offending sub-expression. Also outside RL: the ordering of Text, is with a literal, == or != against a variant, unit and interpolated text. For x == V the diagnostic carries an edit to x is V, and for x is 1 an edit to x == 1.

In clauses, every integer type reads as its mathematical Int: operators accept any mix of integer types and compute exactly, with no overflow obligation and no U2022. So ensures result <= 300 on a U8 result is valid.

3.5 Predicates

Predicates are named, pure, total boolean functions usable in RL. There are two forms:

Form Body Seen by the solver How a value gets the fact
predicate reflect must be in RL and not recursive yes, as a definition proven statically
predicate opaque any pure, non-failing expression no, only its name a runtime checked (§6.5) or a capability operation's ensures (§7.1)
una
module demo

predicate reflect adult(age: Int) -> Bool = age >= 18

--- Format check only.
pub predicate opaque valid_phone(t: Text) -> Bool = t.len == 11 and is_digits(t)

--- A reflect body computes exactly: no overflow obligation, even on `U32`.
predicate reflect large(x: U32) -> Bool = x * 4294967295 > 4294967295

pub kind Adult = Int where adult(it)

3.6 Equality, ordering and conversions

3.7 Subtyping, in one table

Flow Allowed when
refined value into refined position the compiler proves the target predicate (obligation)
labeled value into labeled position source label ⊑ target label (§8)
function into function position parameters contravariant, result covariant, and its uses and fails are included in the target's

Constructs