Verification Commands
ImandraX provides five core commands for reasoning about your code. Each serves a distinct purpose in the verification workflow.
verify
The verify command checks whether a property holds for all inputs. If it doesn't, ImandraX synthesizes a concrete counterexample. Goals in ImandraX are boolean-valued functions, and with verify you simply pass an anonymous lambda or the name of a defined function:
(* Does this hold for all x? *)
verify (fun x -> x + 1 > x)
(* Proved *)(* Does this hold for all x? *)
verify (fun x -> x * x > 0)
(* Counterexample: x = 0 *)verify is a primary tool for checking conjectures. Use it to:
- Validate properties before committing to a theorem
- Find edge cases in your definitions
- Explore the behavior of functions
Like theorem and lemma, verify supports the [@@by tactic] annotation to guide the proof:
verify (fun x y -> (x @ y) @ [] = x @ y) [@@by auto]With hypotheses
Use ==> (implication) to add preconditions:
verify (fun x -> x > 0 ==> x * x > 0)
(* Proved *)With multiple variables
verify (fun x y -> List.length (x @ y) = List.length x + List.length y)
(* Proved *)Bounded verification with [@@upto n]
The [@@upto n] attribute (available only for verify) performs bounded verification up to unrolling depth n, producing an actual bounded theorem as its result. It uses a version of unrolling that is complete for counterexample finding in a precise sense: if a counterexample exists within the bound, it will be found:
verify (fun (xs : int list) ->
List.length xs = List.length (List.rev xs))
[@@upto 100]This is valuable when a property is true but requires induction to prove in general. Bounded verification with [@@upto] gives you strong evidence before investing in a full proof.
[@@upto] vs unroll tactic
The [@@upto n] attribute is distinct from the unroll n tactic (which can
be used with [@@by unroll n] on any verification goal). [@@upto] is
specific to verify and produces a proper bounded result with counterexample
completeness guarantees. The unroll tactic is a general-purpose tactic that
can be used as part of larger tactic compositions.
With type annotations
When ImandraX needs help inferring types:
verify (fun (xs : int list) -> List.rev (List.rev xs) = xs)instance
The instance command finds a concrete input that satisfies a property. It answers: "Give me an example where this is true."
instance (fun x -> x * x = 144)
(* Instance found: x = 12 *)instance (fun (xs : int list) ->
List.length xs = 3 && List.for_all (fun x -> x > 0) xs)
(* Instance found: xs = [1; 1; 1] *)instance is invaluable for:
- Generating test cases
- Finding inputs satisfying complex constraints
- Exploring the space of valid inputs for a function
Combining constraints
instance (fun x y ->
x > 0 && y > 0 && x + y = 10 && x * y > 20)
(* Instance found: x = 5, y = 5 *)theorem
The theorem command states and proves a named result. Once proved, a theorem is available for use in subsequent proofs.
theorem append_nil xs =
xs @ [] = xs
[@@by auto]Theorems differ from verify in that they:
- Have a name that can be referenced later
- Can be installed as rewrite rules, forward-chaining rules, etc.
With tactics
The [@@by ...] annotation specifies how to prove the theorem:
theorem rev_rev xs =
rev (rev xs) = xs
[@@by auto]As rewrite rules
Install a theorem as a rewrite rule with [@@rw]:
theorem append_nil xs =
xs @ [] = xs
[@@by auto] [@@rw]Now whenever the simplifier sees <expr> @ [], it will rewrite it to <expr>.
As forward-chaining rules
Install as a forward-chaining rule with [@@fc]:
theorem length_non_neg xs =
(List.length xs [@trigger]) >= 0
[@@by auto] [@@fc]The [@trigger] annotation tells the simplifier which term to match on.
lemma
The lemma command is syntactically identical to theorem. It's conventionally used for intermediate results, stepping stones toward a bigger theorem:
(* A helper lemma *)
lemma insert_preserves_sorted a xs =
is_sorted xs ==> is_sorted (insert a xs)
[@@by auto] [@@rw]
(* The main theorem, which uses the lemma *)
theorem insertion_sort_sorts xs =
is_sorted (insert_sort xs)
[@@by auto]The distinction between theorem and lemma is purely stylistic; they have identical behavior.
axiom
The axiom command asserts a property without proof. The assertion is accepted unconditionally and can be used in subsequent reasoning.
axiom hash_deterministic x =
hash x = hash x
axiom hash_range x =
hash x >= 0 && hash x < 1000000Use axioms with extreme caution
Axioms bypass ImandraX's conservative extension discipline. An inconsistent
axiom, one that contradicts established facts, makes the entire logic unsound,
allowing you to "prove" anything. Only use axioms when you are confident they
are consistent, and prefer [@@opaque] functions with theorems when possible.
When to use axioms
- Modelling external systems whose implementation you don't control
- Constraining
[@@opaque]functions with known properties - Temporarily assuming a property to focus on the rest of a proof
Summary
| Command | Purpose | Requires proof? | Named? |
|---|---|---|---|
verify | Check if a property holds for all inputs | Optional ([@@by ...]) | No |
instance | Find an input satisfying a property | N/A | No |
theorem | State and prove a named result | Yes | Yes |
lemma | State and prove a named result (conventional for helpers) | Yes | Yes |
axiom | Assert a property without proof | No | Yes |