Skip to content

Verification

Gale verifies contracts over the code and interfaces in a resolved project. Write ordinary functions, reuse runtime validators in specifications, and state the properties consumers need. You do not need to maintain a second WhyML implementation. The proving tour introduces the syntax; this reference defines what a successful verification establishes.

For a function f, let D_in(x) describe its input types and their invariants, P(x) its preconditions, D_out(r) its result type and invariants, and Q(x, r) its postconditions. Under the checked program model and reported assumptions, normal-return correctness means:

For every x and r:
D_in(x) and P(x) and returns(f, x, r)
imply D_out(r) and Q(x, r).

returns means a normal return in the modeled execution. Error(reason) is also a normal return. Exceptions, external process termination and resource exhaustion do not become successful returns. A normal-return proof alone does not establish that a call finishes.

Arguments are evaluated before checking the enclosing call’s preconditions. The proof can therefore use a nested call’s result type, invariants and declared postconditions when establishing the outer call’s admission. Each nested call still owes its own preconditions and implementation proof.

A Never result has no admitted values. Its branch may fit any result type, but verification must retain the impossible normal-return obligation. It cannot provide an arbitrary value on a reachable path.

Opaque native child specifications retain their value identity in proofs. ChildSpec<A> does not expose a service payload or imply startup, process survival or any field-level theorem; ChildSpec<Never> can still have values.

Logical calls and the optional pure capability require effect freedom and termination, checked separately and recursively through source calls. Known source helpers need no qualifier when eligibility can be established. These properties do not describe allocation, scheduling, available memory or process survival on the BEAM. Native pure declarations trust both guarantees on admitted inputs. There is no public total qualifier. Specification and default calls also check the actual callbacks passed to an ordinary higher-order helper. A checked lambda or pure callback interface can supply eligibility without changing the helper’s ordinary executable API. Passing an already pure callback through an ordinary callback parameter retains its logical application facts at that value, while still checking invocation contracts. An unrelated unknown ordinary callback gains no such guarantee. Selection predicates and ordering comparators require pure fn. Transformation, accumulation and action callbacks permit effects. Native reduce_while, zip_with and scan keep ordinary callback interfaces; native reject requires a pure predicate. Forward invocation order and structural bounds do not imply purity.

Collection calls use their exported contracts. For a longer composition, bind intermediate results and use assert { ... } to establish useful facts before the next call. For example, prove the filtered list, then the mapped list, then the final reduction. Each assertion is checked; it does not add an assumption.

For a pipeline that still times out, put a stage in a helper with an ensures clause describing its result. The helper proves that contract separately; the caller uses the contract without reopening the implementation. This can keep list transformation proofs separate from dictionary construction proofs. A failed helper proof leaves its callers conditional.

call_requires(callback, arguments...) and call_ensures(callback, arguments..., output) observe invocation contracts without calling the callback. Arguments appear individually in declared order; zero-argument callbacks use call_requires(callback) and call_ensures(callback, output). These Boolean formulas are available only in contracts, predicates, assertions and ghost code, never runtime code or guards. They require a statically known mailbox-free function interface and type-correct inputs/outputs. Actual calls publish their invocation postcondition. Generic native contracts can preserve that relation for effectful callbacks, without claiming determinism or termination. An observation does not establish that an invocation occurred. Captures remain immutable; external/process state is outside this input/output relation. There is no conditional pure when syntax. Lambdas in specifications use the same checked closure implementation and capture admission duties as executable closure construction.

Eligibility for logical calls does not expose every helper body globally. Checked contracts and bounded body equations are separate proof interfaces. An eligible contracted helper can be used logically through its checked contract, with its implementation verified separately. Ordinary executable calls can also use the implicit guarantees of parameter and result types, such as UTF-8 validity for String. Private helpers can retain bounded checked body summaries. Unrelated tasks can omit imported operation laws and recursive helper equations; the defining helpers still have mandatory proof obligations. A brief attempt on each original Why3 goal precedes solving its split children, so splitting a goal cannot force repeated solver work when the original already proves. Concrete numerical recursive calls can also use bounded instances of their checked equations. Preconditions remain required, and every defining source implementation and termination obligation must still prove.

Known pure callback arguments do not reopen an eligible contracted helper’s implementation. Callers use its callback/result contract, while its implementation and callback conformance remain independently required. Adding unrelated functions or editing a contracted helper’s body should not change the caller’s WhyML input.

Libraries can expose small semantic relations and checked instantiation lemmas. For example, gale_schema.preserves_codecs(before, updated) states equality of validation, decoding and encoding results at every admitted input, excluding description metadata. Metadata combinators promise this relation, and the preserved_codec_results lemma instantiates it for particular inputs inside ghost. The relation does not assert codec inverse laws or justify a custom description.

Prefer direct recursive traversal when a callback would call back into the same traversal. This keeps recursive descent visible and avoids requiring a separate totality proof for a recursively created callback. The schema JSON conversion traversals use this form while preserving error order and paths.

Inferred structural recursion can forward an unchanged list, tree or product through finitely many helpers before descending. The forwarding calls receive decreasing finite phases; every recursive cycle must contain structural descent. The verifier proves the combined size-and-phase measure. A cycle that only forwards the same value still fails termination verification.

Dynamic Term traversal supports cons-cell descent and the finite native Map.to_list view of Map<Term, Term>. The map contents size correspondence is a reported native assumption. Generated list/product measures and recursive decreases remain checked; unrelated native functions receive no such guarantee.

Private helpers can state useful postconditions to provide local checked interfaces. For example, tuple encoding workers promise the output array’s arity, and a discriminator reader promises that success returns the string in the requested field. Their callers use that guarantee; each worker still proves its own body and result domain. An authored postcondition is the abstraction boundary. Helpers without such contracts can use bounded body inference, which does not publish a stronger fact than the inferred summary.

Application proofs name the fact they need. A quota decoder can ensure that an accepted state has nonnegative availability without describing every rejected input. Dispatch proves an empty branch list and the first matching branch; a property of a later branch is a lemma. Document generation and uncontracted search combinators stay executable and tested; they are not proof roots until they grow a contract a caller can use.

Known Integer and Float values retain their native kind through Term; successful numeric projection recovers the original Integer value or Float identity. This describes boxing and type refinement, without numerical Float arithmetic or an assumption that an arbitrary Term has either kind.

Boundary Required proof
Call The arguments satisfy the callee’s preconditions and typed domains
Function body Every normal result satisfies the result domain and postconditions, assuming admitted inputs
Opaque construction The representation satisfies its invariant, even if the constructed value is discarded
Typed aggregate Contained values retain their typed domains and invariants
Callable creation or conversion Its implementation admits the interface’s inputs and establishes its promised outputs and requested termination
assert The formula follows from the facts available at that source point
Terminating recursion A structural or explicit lexicographic measure decreases, with the required lower bound
Callback conformance The implementation accepts the callback’s admitted inputs and establishes its promised results

Ordered function clauses share one type signature. Heads, guards and ordering select the applicable clause and contract. They are not independent overloads.

A false precondition admits no calls. Proving a body under requires { false } is therefore vacuous; it does not justify a call from Gale, Elixir or OTP. Native callers must respect the declared interface just as Gale callers must.

The proof world consists of the selected Gale sources, their resolved dependency sources and explicit foreign interfaces. By default, library sources are proof roots, including private and unused functions. Tests are typechecked; selecting a test module explicitly can make it a proof root. Explicit module selection narrows roots, while reached implementation and conformance obligations remain part of the verification closure.

A source dependency is checked against its contract. This includes Gale code in the standard library and in other packages. A failed dependency implementation blocks project success even when a caller’s cached proof remains valid. Merely calling a module’s ordinary function does not select all of its unrelated callbacks; passing its module capability selects the relevant conformance duties.

A direct implementation call may also use callback promises when its actual type arguments satisfy the callback’s closed choices and its value preconditions hold. Such a caller depends on that callback’s provider conformance proof and remains conditional if conformance fails. Calls outside the callback’s type domain use the implementation’s own contract.

Elixir code outside these interfaces, hot code replacement and arbitrary external messages are not silently added to the proof world. Their behavior must meet the reported boundary assumptions. Typechecking does not establish contracts or opaque invariants. Enabled runtime checks evaluate executable conditions on actual values and raise on established violations. Runtime proof checks are best effort: unsupported or inconclusive formulas are skipped without blocking compilation or raising at runtime. Independent supported clauses and conjuncts still run. A skipped check establishes no truth; only verification establishes the modeled claims for every admitted input. An inconclusive guard can leave a dependent branch unchecked. Optional branch evaluation does not probe unobserved callbacks or foreign bindings; actual operations and known-selected checks retain their normal errors. Quantified properties of callbacks used or returned by executable code monitor actual invocations, including finite input types. Pure callables used only as proof predicates can run on current concrete data; their input type alone does not supply hypothetical callback arguments. Runtime evaluation separates four cases:

Case Result
Executable conditions and complete finite-domain/support reductions Exact Booleans; ordinary logical composition is supported.
Universal checks over actual typed inputs or callback invocations Check current inputs. A falsifying input refutes the claim; passing observations leave universal truth unknown. Negations and premises preserve that distinction.
Validated witnesses and induction certificates Establish truth; a missing certificate is inconclusive and skips that check, never producing a guessed false result.
Unsupported compositions Skipped when they cannot be evaluated conclusively; independent supported checks remain active.

Callback-contract observations preserve the declared permitted-output relation; observed outputs do not narrow a weak interface. Pure logical application still needs its deterministic result. Executable specification helpers also check input types, prerequisites, postconditions and explicit descent measures. Invocations inside a helper body validate their own contracts. References inside a contract may evaluate an active function’s mathematical body with domain/type/descent checks, avoiding recursive postcondition expansion through direct or mutual references. Nested checks reuse actual call results and temporary pure evaluation results; their cache is cleared on return or failure.

“Supported” means the verifier can generate the relevant obligations. It does not promise that an automatic solver can prove every true statement.

Feature Current proof support
Integers and Booleans Mathematical integer +, -, *, comparisons and Boolean logic; difficult nonlinear formulas may remain unproved
Branches, patterns and ordered clauses Path conditions, exhaustiveness, guards and selected-clause contracts
Tuples, records, ADTs, unions and opaque values Typed domains, construction, projection, matching and invariant preservation
Lists Element domains, structural descent, append laws and source-defined collection operations
Dictionaries and sets Finite contents, strict key identity, lookup/update/removal and modeled size or membership contracts
Strings and binaries Shared byte identity, literal content, concatenation and byte lengths; String additionally requires valid UTF-8
Structs Runtime maps including the module tag; native structs may carry additional fields
Generic source functions Instantiated source reasoning and preserved element domains; unknown F<A> applications remain opaque with independent admission predicates
Function values Checked callable contracts, captures, storage, later calls and eligible inferred summaries
Termination Checked structural list/ADT descent and explicit numeric or lexicographic measures
Specifications Checked effect-free, terminating helpers; predicates, lemmas, assertions and ghost code (erased when runtime checks are disabled)
Behaviours and OTP Selected callback contracts and conditional state/lifecycle obligations, within the restrictions below

Use a single pure fn for a condition needed in runtime validation and contracts. Small eligible helpers and callbacks can also infer the necessary facts. Source collection functions can reuse checked callback summaries, so ordinary filter/map/reduce pipelines can establish useful results without handwritten callable specifications at every step.

Reflected helpers retain call-admission checks at their expression sites. Recursive calls must establish their result contracts before a later call can use those results to satisfy its own preconditions.

Public proof interfaces follow the declaration kind: pub fn and pub pure fn expose their types and contracts, pub predicate exposes its formula, and pub lemma exposes its theorem. pure requests logical-call eligibility; it does not make a public implementation visible. Functions without explicit postconditions still keep their body private to implementation verification. Small eligible private helpers without postconditions retain bounded checked body inference, with or without pure. An authored postcondition closes the private interface. A private helper named by a public predicate remains part of the predicate’s definition.

Reflection is bounded to 128 expression nodes per helper, counting its body and contracts, and 16 nested helpers. Public functions use their contracts. Larger private executable functions use their contracts. A logical use that requires an unsupported reflected body receives a diagnostic. Prefer stable public contracts when consumers should not depend on implementation details. Contract-exposed predicates, invariants and helpers remain part of the public proof input.

Proof identity follows BEAM strict equality. Opaque wrappers and source unions introduce no extra runtime tags. Boolean values share identity with their corresponding atoms. Integer and Float keys remain distinct. String/Binary identity compares bytes and performs no Unicode normalization. byte_size counts bytes, not characters or graphemes.

Extern structs can contain hidden fields: equality of their declared fields alone does not establish whole-value equality. Native layouts and default values require an explicit correspondence assumption. Function equality is about runtime function identity; equal outputs do not imply equal functions.

The compact dictionary interface has a separate validation against a concrete finite-map model. Application proofs reuse that interface; they cannot validate axioms merely by assuming them. Runtime correspondence is also tested against BEAM operations. These model checks belong to the toolchain, not application specification files.

Some valid Gale programs cannot currently be verified. An unsupported model produces a diagnostic, commonly G2599; it is not an omitted obligation that counts as success.

Area Limit
Float Values, identity and stable comparison observations can be transported through branches. No numerical ordering, distinct-literal or arithmetic laws are assumed. Float arithmetic and rounding models are unsupported.
Checked integer division Audited native-target/signature models expose truncating quotient, signed remainder and modulo identities. Expected division errors remain Result values.
Raw mailboxes A receive proves a matching arm or a finite after result. It does not establish message arrival, elapsed time, or termination. Mailbox-capable callable proof interfaces remain unsupported.
Callback conformance Contracted callback implementations dispatch through their clauses like ordinary functions, with interface requires/ensures admitted per clause. The direct single-clause form requires plain named parameters.
Generic proof declarations Generic predicates and lemmas support admitted value models, with checked type substitution, definition bodies and call-admission duties.
Polymorphic recursion Recursive calls that change their generic instantiation are unsupported.
Recursive callable creation Cyclic construction of a proof-eligible callable is unsupported. Cyclic proof declarations also receive a diagnostic.
Native APIs without a model or useful contract A target name does not create semantic facts. A typed return alone does not establish an application property.
Solver automation Timeout, unknown and unproved outcomes may occur for supported code. They do not establish the contract or necessarily exhibit a counterexample.

A receive can be a proof root. The obligation is the result after one matching message or a finite timeout. This one holds for every delivered integer:

pub fn non_negative() receives Integer -> Integer
ensures { result >= 0 }
{
receive {
value when value >= 0 -> value
_ -> 0
}
}

A claim that every delivered integer is already nonnegative stays unproved. The proof still does not establish that a message arrives or that the function terminates. Use the processes tour for mailbox typing. Keep pure domain transformations separate from process orchestration when you want to verify them independently; a selected proof of those transformations does not prove the surrounding receive loop.

Extern types, representations, effects, totality and contracts describe a foreign boundary. Gale checks callers and Gale wrappers against those declarations; it does not prove the Elixir or Erlang body. A new binding can be declared in Gale without extending the compiler, but its postcondition remains an assumption unless established by checked Gale code or a supported semantic model. Review the verification report’s native and abstraction assumptions, and test foreign correspondence at runtime.

OTP lifecycle induction is conditional on the environment supplying admissible callback arguments, installing only the verified callback outcomes, and not replacing state administratively. It establishes the modeled invariant at those boundaries. It does not establish mailbox ordering, message delivery, fairness, absence of deadlock, external service correctness, crash rollback or process survival. A raw receive adds only the partial result of a matching arm or a finite timeout. Typed OTP interfaces and selected callback proofs remain available beside that limit.

The remaining trusted base includes the compiler’s translation, Why3 and the solver, plus the correspondence between the runtime model and the BEAM. A proof report is evidence about the selected program under this base, not a proof of the implementation of the entire toolchain.

Guidelines for application and library authors

Section titled “Guidelines for application and library authors”
  1. Model valid states. Use ADTs for alternatives and opaque invariants for relationships that should survive every update. Decode foreign input first.
  2. Share executable checks. Reuse a small checked validator in constructors and specifications. Keep optional lemmas for properties that need them.
  3. Specify public behavior. State the result consumers need. Avoid making callers depend on a large library body or internal data layout.
  4. Let ordinary callbacks infer facts. Use explicit callable contracts when a stored, returned or externally supplied callback needs a stable interface.
  5. Make recursion clear. Recurse on structural children, or state a numeric checked decreases measure when needed for logical use. pure may request the full logical-call guarantee explicitly.
  6. Keep native assumptions narrow. Use typed errors for expected failures, and test that foreign contracts match runtime behavior. Do not add an unjustified extern postcondition simply to make a proof pass.
  7. Check both kinds of evidence. Run verification and runtime tests. Inspect selected roots, dependencies, assumptions and every non-success outcome.

gale check and mix gale.check check types only. gale compile and mix compile additionally emit Elixir. gale verify and mix gale.verify invoke the proof toolchain. Use gale help for root selection, reporting and resource options; toolchain setup lists the required tools.

mix gale.verify requires a nonempty gale: [proofs: [...]] commitment list. Entries use canonical module names: gale_std.list/member? selects every arity of that function, while gale_std.map/has_key?:2 selects one. Predicates and lemmas use module/predicate:name and module/lemma:name. One gale verify process proves every listed subject, with the CLI defaults of 5 seconds per goal, 120 seconds of wall time for the whole run, and one worker. {"gale_std.list/map", goal: 30, wall: 90} raises that subject’s goal limit and gives it a separate proving wall. gale: [options: ["--jobs", "4"]] passes extra arguments to that one process.

Successful verification requires every selected obligation to succeed. A cache may reuse established evidence when its proof inputs are unchanged; it cannot turn a failed implementation into success. A setup error, unsupported lowering, resource limit, timeout or unproved condition needs resolution. Reducing the selected scope changes what is proved and must not be described as proving the excluded code.

Patterns [] and [head | tail] can inspect a Term in proofs. Head and tail remain dynamic, so improper lists are not silently treated as proper lists. The reported whyml.builtin.dynamic-cons-v1 model supplies native nil/cons observations and a nonnegative finite-tree size. Both parts of a cons cell have smaller size, allowing ordinary structural termination checks. Embedding a typed list preserves its empty/cons structure and elements. These are native semantic assumptions, not claims that arbitrary decoded inputs have a valid list type.

Passing is_binary, is_bitstring, is_float and is_map tests project a dynamic value into the corresponding model in the reached branch. Binary projections retain the byte-domain guarantee. These conservative projections supply typed values; they do not add float arithmetic laws or infer UTF-8 validity from is_binary. Map projections preserve the dynamic key/value domain. Recursive helpers that descend through Term use checked size-based definitions; the compiler does not emit unchecked mathematical recursion through abstract head/tail observers.