Home / Docs / Language guide
Kinds and types
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.
- Distinct types.
I8toU64are distinct fromIntand from one another, with no implicit conversion. An operator takes operands of one type (U2001). - Literals take the fixed-width type their context expects: an annotated
let, a parameter, a field, a return, the other operand of an operator, or the field of a constructor checked against a known type, asSome(200)againstOption[U8]. A literal that does not fit is U2022. - Overflow of
+,-,*,/,modand unary-is a proof obligation of kindoverflow(§11), never a silent wrap. Clauses (where,requires,ensures) read every integer type as its mathematical value, sorequires a + b <= 255computes exactly. - Conversions are built-in methods:
x.to_i8()tox.to_u64()andx.to_int(). Widening, where every value fits, needs no proof. Narrowing carries anoverflowobligation that the value fits. - Wrapping and saturating arithmetic is written out:
a.wrapping_add(by: b),a.saturating_sub(by: b)and their siblings, never by default. Bit operations area.bit_and(mask: m),bit_or,bit_xor,bit_not(),a.shift_right(by: n)anda.wrapping_shift_left(by: n).
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()-- fails with U5001
module demo
pub add(a: U8, b: U8) -> U8 = a + b-- fails with U2022
module demo
pub too_big() -> U8 = 300-- fails with U2001
module demo
pub mixed(a: U8, b: U16) -> U16 = a + bThe 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).
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:
- Sum or alias. A right-hand side with
|at bracket depth zero is a sum; otherwise it is an alias or refinement. A single-variant sum needs a leading bar:kind PhoneError = | Malformed. - Records and sums are nominal. Two declarations with the same shape are different types.
- Aliases and refinements are structural over their base. A
Seatsvalue can be used wherever anIntis expected. Using anIntwhereSeatsis expected creates a proof obligation: the compiler must prove the value lies in0..5000. - Refinements stack. Refining a refined kind combines both predicates. Fixed-width types can be refined too:
kind Port = U16 where it > 0. - Range sugar:
T in a..bmeansT where a <= it and it <= b;T in a..<bexcludesb.
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.
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:
-- 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:
-- 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 |
- Written on functions only.
Kind[T: Eq]is U0101. Each type parameter takes at most one constraint, and an unknown name is U2027. - Operators need the constraint (U2026, with a repair that writes it). This includes
==on an unconstrained type parameter. Public functions write their constraints; private ones have the least constraint their body needs inferred. - Type arguments must satisfy it (U2025 at the call).
- No arithmetic on
T, constrained or not: convert withto_int()and compute onInt.
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)-- fails with U2026
module demo
pub same[T](a: T, b: T) -> Bool = a == b-- 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) |
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)- Opaque predicates never introduce axioms, so they cannot make the logic inconsistent. They carry validation that the solver cannot reason about (formats, checksums), and the fact travels in the type once established. Their bodies are code, with overflow obligations on fixed-width arithmetic.
reflectbodies compute exactly. The body of areflectpredicate is typed as code that runs, so its integer types do not mix (U2001), but its arithmetic is exact, as the verifier reads it and as every engine computes it: nooverflowobligation and no U2022. Solarge(4294967295)above holds.
3.6 Equality, ordering and conversions
==and!=are structural, for every type except functions.<,<=,>,>=work onInt, on the fixed-width types, onText(lexicographic), and on sums without payloads (declaration order).- There are no implicit conversions, not even between distinct kinds with the same shape, between
Intand a fixed-width type, or betweenIntandText. Integer conversions are the methods of §3.1.
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 |