Skip to content

Proving

Contracts describe what is true if a function returns. requires is a caller obligation; ensures binds the return value as result, shadowing a same-named parameter within that clause. Opaque types may declare invariant. Ordinary checked validators serve runtime checks and specifications together. Callable contracts and inferred callback summaries compose through collections. gale verify (or mix gale.verify) discharges these claims. Compilation does not. Proofs do not mean a process is alive or a message was delivered.

Contracts state properties beyond a return type, such as a capacity limit or a relationship between inputs and outputs. The verifier checks these properties against the function body and reports any assumptions or unproved obligations.

pub fn increment(x: Integer) -> Integer
requires { x >= 0 }
ensures { result == x + 1 }
{
x + 1
}

requires is the caller’s obligation. ensures is yours: on every normal return, result (the return value, in the declared return type) must satisfy the formula. Errors returned as values are normal returns too.

Compilation does not prove contracts. The compiler checks that contract formulas are well-typed, so a false contract can still compile. gale verify (Why3 1.8.2 + Z3 4.16.0) discharges the actual obligations, and mix gale.check typechecks them without solvers.

Terminal window
mix gale.check # typecheck annotations without solvers
mix gale.verify # prove them with Why3 and Z3
mix test # execute Gale and native integration tests

A condition used in runtime validation and a specification can share one function. Here within_capacity checks construction, updates and the invariant:

pub pure fn within_capacity(reserved: Integer, capacity: Integer) -> Boolean
ensures { result == (reserved >= 0 and reserved <= capacity) }
{
reserved >= 0 and reserved <= capacity
}
pub opaque type State = %{reserved: Integer, capacity: Integer}
invariant(state) {
within_capacity(state.reserved, state.capacity)
}
pub fn new(capacity: Integer) -> Result<State, :invalid> {
if within_capacity(0, capacity) {
Ok(State(%{reserved: 0, capacity: capacity}))
} else {
Error(:invalid)
}
}
pub fn reserve(State(state): State, amount: Integer) -> Result<State, :invalid> {
candidate = %{state | reserved: state.reserved + amount}
if amount >= 0 and within_capacity(candidate.reserved, candidate.capacity) {
Ok(State(candidate))
} else {
Error(:invalid)
}
}
pub fn available(State(state): State) -> Integer
ensures { result >= 0 }
{
state.capacity - state.reserved
}

State(raw) constructs the opaque value inside the defining module. Other modules cannot call this constructor. The verifier proves the invariant at every construction, even for values that are discarded. Raw intermediates may violate the invariant while being repaired; typed State values carry it everywhere, including inside records, tuples and constructors.

pure requires determinism, no observable effects, and termination on valid inputs for use in specifications. Gale checks effects through called source; Why3 discharges the termination obligations. An ordinary helper used in specs can establish the same facts; extern pure trusts them for native code. None of this says anything about scheduler work or process survival, and ordinary executable functions may still diverge. There is no public total.

For a capacity of three, new(3) creates a state with three places available. reserve(state, 3) fills it; a negative reservation or one above the remaining capacity returns Error(:invalid). The runtime checks decide which result to return. The proof establishes that every constructed State satisfies the invariant, so available cannot return a negative number.

This is the same shape the GenServer chapter uses for its quota server: prove the pure transitions, keep the callbacks thin.

The list library is ordinary Gale source, so a pipeline over small lambdas needs no authored callback contracts. The verifier checks the source implementations and infers the summaries:

alias gale_std.list
pub fn pipeline() -> Integer
ensures { result == 10 }
{
selected = list.filter([1, 2, 3], fn(value) -> value >= 2)
assert { selected == [2, 3] }
doubled = list.map(selected, fn(value) -> value * 2)
assert { doubled == [4, 6] }
list.reduce(doubled, 0, fn(value, sum) -> value + sum)
}

The intermediate assert clauses give the solver smaller claims to establish: filter to [2, 3], double to [4, 6], then sum to 10. These assertions are proof obligations, not assumptions. A timeout remains an unproved result. Unknown or effectful callbacks keep their executable contracts; they do not acquire inferred purity just because the surrounding helper supports proof. (A proof-only lambda can observe an effectful callback’s invocation contract without invoking it; such lambdas stay in predicates and ghost code.)

When a callable’s promise must survive storage and later calls, put the contract on its type:

pub fn incrementer() -> (pure fn(value: Integer) -> Integer ensures { result == value + 1 }) {
fn(value) -> value + 1
}
pub fn apply_increment(
value: Integer,
transform: pure fn(input: Integer) -> Integer ensures { result == input + 1 }
) -> Integer
ensures { result == value + 1 }
{
transform.(value)
}

The parentheses attach the contract to the returned arrow. Creating or assigning such a callable proves admission, postcondition and requested termination; invoking it proves the precondition and earns the postcondition. A bare fn(Integer) -> Integer promises only callability. Capturing a function with a requires into the bare type means proving that requires for every admitted input. Known small lambdas retain checked summaries; an unknown callable of the same bare type supplies none.

Structural recursion over list tails and ADT children infers a size measure, mutual recursion included. Numeric recursion says its measure explicitly:

pub fn zero(x: Integer) -> Integer
requires { x >= 0 }
ensures { result == 0 }
decreases { x }
{
if x == 0 {
0
} else {
zero(x - 1)
}
}

Rebuilt values, unchanged arguments and accumulator swaps are not structural descent. Server loops may run indefinitely; their contracts describe what holds if they return.

Most validation stays an ordinary function. When a theorem needs a name, predicate and lemma are erased declarations:

pub predicate nonnegative(value: Integer) {
value >= 0
}
pub lemma successor(value: Integer)
requires { nonnegative(value) }
ensures { nonnegative(value + 1) }
pub fn step(value: Integer) -> Integer
requires { nonnegative(value) }
ensures { nonnegative(result) }
{
ghost { successor(value) }
value + 1
}

A predicate is a nonrecursive Boolean formula. It cannot be called or captured as a runtime function and emits no code. A bodyless lemma is proved from its requires by the solver. ghost { } cites theorems and is erased before code runs; assert { condition } is also proved and erased. gale_std.test.assert(condition) checks a condition at runtime. Predicates and lemmas take ordinary generic parameters, with each use substituting its type arguments and the generic definition checked independently. Gale has no assume, admit or SMT trigger syntax. Computable helpers used in specifications are ordinary fns with ensures.

For quantified contracts, proof-only forall(value: Type) { formula } can state a property of every invocation of a returned function, such as a decoder. Nested calls must satisfy their preconditions on every reached path; guard a partial call with its domain.

  • Extern declarations are trusted (externs): callers prove the declared preconditions and assume the native types, effects and postconditions. Gale never proves Elixir or Erlang bodies. A spec call needs an explicit extern pure declaration.

  • Numbers: integer division/remainder follow the truncation-toward-zero model; integer.mod is divisor-signed; nonnegative powers use a checked bridge. These are reported as native-correspondence assumptions. Numerical Float proofs are outside v1: identity, transport and stable comparisons are available; arithmetic and ordering laws are not. Full Unicode, calendar, Decimal and external-world models are likewise excluded.

  • Verification outcomes: complete verification accounts for all required goals and dependencies. Unknown, timeout, unsupported, incomplete and no-goal outcomes are reported separately. A timeout is not a counterexample. Changed helpers reverify even when their unchanged contract permits caller reuse; body, model or toolchain changes invalidate dependent evidence.

  • Processes: proofs cover normal returns. Nothing here establishes message delivery, process survival, or a whole-loop termination claim. For infinite servers, verification covers initialization and transition invariants.

The verification reference gives the formal normal-return guarantee, the supported models and the current limits. In particular, a receive proof covers one matching arm or a finite timeout and does not establish message delivery or termination, and a proved domain function says nothing about the process orchestration around it.