12. Technical Informations

12.1. Structure of Session Files

The proof session state is stored in an XML file named dir/why3session.xml, where dir is the directory of the project. The XML file follows the DTD given in share/why3session.dtd and reproduced below.

<!ELEMENT why3session (prover*, file*)>
<!ATTLIST why3session shape_version CDATA #IMPLIED>

<!ELEMENT prover EMPTY>
<!ATTLIST prover id CDATA #REQUIRED>
<!ATTLIST prover name CDATA #REQUIRED>
<!ATTLIST prover version CDATA #REQUIRED>
<!ATTLIST prover alternative CDATA #IMPLIED>
<!ATTLIST prover timelimit CDATA #IMPLIED>
<!ATTLIST prover memlimit CDATA #IMPLIED>
<!ATTLIST prover steplimit CDATA #IMPLIED>

<!ELEMENT file (path*, theory*)>
<!ATTLIST file format CDATA #IMPLIED>
<!ATTLIST file name CDATA #IMPLIED>
<!ATTLIST file verified CDATA #IMPLIED>
<!ATTLIST file proved CDATA #IMPLIED>

<!ELEMENT path EMPTY>
<!ATTLIST path name CDATA #REQUIRED>

<!ELEMENT theory (label*,goal*)>
<!ATTLIST theory name CDATA #REQUIRED>
<!ATTLIST theory verified CDATA #IMPLIED>
<!ATTLIST theory proved CDATA #IMPLIED>

<!ELEMENT goal (label*, proof*, transf*)>
<!ATTLIST goal name CDATA #REQUIRED>
<!ATTLIST goal expl CDATA #IMPLIED>
<!ATTLIST goal sum CDATA #IMPLIED>
<!ATTLIST goal shape CDATA #IMPLIED>
<!ATTLIST goal proved CDATA #IMPLIED>

<!ELEMENT proof (path*, (result|undone|internalfailure|unedited))>
<!ATTLIST proof prover CDATA #REQUIRED>
<!ATTLIST proof timelimit CDATA #IMPLIED>
<!ATTLIST proof memlimit CDATA #IMPLIED>
<!ATTLIST proof steplimit CDATA #IMPLIED>
<!ATTLIST proof edited CDATA #IMPLIED>
<!ATTLIST proof obsolete CDATA #IMPLIED>

<!ELEMENT result EMPTY>
<!ATTLIST result status (valid|invalid|unknown|timeout|outofmemory|steplimitexceeded|failure|highfailure) #REQUIRED>
<!ATTLIST result time CDATA #IMPLIED>
<!ATTLIST result steps CDATA #IMPLIED>

<!ELEMENT undone EMPTY>
<!ELEMENT unedited EMPTY>

<!ELEMENT internalfailure EMPTY>
<!ATTLIST internalfailure reason CDATA #REQUIRED>

<!ELEMENT transf (goal*)>
<!ATTLIST transf name CDATA #REQUIRED>
<!ATTLIST transf proved CDATA #IMPLIED>
<!ATTLIST transf arg1 CDATA #IMPLIED>
<!ATTLIST transf arg2 CDATA #IMPLIED>
<!ATTLIST transf arg3 CDATA #IMPLIED>
<!ATTLIST transf arg4 CDATA #IMPLIED>

<!ELEMENT label EMPTY>
<!ATTLIST label name CDATA #REQUIRED>

12.2. Prover Detection

The data configuration for the automatic detection of installed provers is stored in the file provers-detection-data.conf typically located in directory /usr/local/share/why3 after installation.

12.3. The why3.conf Configuration File

One can use a custom configuration file. The Why3 tools look for it in the following order:

  1. the file specified by the why3 --config option,

  2. the file specified by the environment variable WHY3CONFIG if set,

  3. the file $HOME/.why3.conf ($USERPROFILE/.why3.conf under Windows) or, in the case of local installation, why3.conf in the top directory of Why3 sources.

If none of these files exist, a built-in default configuration is used.

A section begins with a header inside square brackets and ends at the beginning of the next section. The header of a section can be a single identifier, e.g., [main], or it can be composed by a family name and a single family argument, e.g., [prover alt-ergo].

Sections contain associations key=value. A value is either an integer (e.g., -555), a boolean (true, false), or a string (e.g., "emacs"). Some specific keys can be attributed multiple values and are thus allowed to occur several times inside a given section. In that case, the relative order of these associations matters.

12.3.1. Extra Configuration Files

In addition to the main configuration file, Why3 commands accept the option why3 --extra-config to read one or more files containing additional configuration option. It allows the user to pass extra declarations in prover drivers, as illustrated in Section 12.5, including declarations for realizations, as illustrated in Section 11.2.

12.4. Drivers for External Provers

Drivers for external provers are readable files from directory drivers. They describe how Why3 should interact with external provers.

Files with .drv extension represent drivers that might be associated to a specific solver in the why3.conf configuration file (see Section 12.3 for more information); files with .gen extension are intended to be imported by other drivers; finally, files with .aux extension are automatically generated from the main Makefile.

digraph G_cc {
	graph [nodesep=0.4,
		rankdir=RL,
		ranksep=0.6
	];
	node [margin=0.05,
		shape=box
	];
	"cvc4-realize.drv" -> "smt-libv2.gen";
	"cvc4-realize.drv" -> "smt-libv2-bv-realization.gen";
	"cvc4-realize.drv" -> "cvc4_bv.gen";
	"cvc4_17_strings.drv" -> "cvc4_17.drv";
	"cvc4_17_strings.drv" -> "smtlib-strings.gen";
	"cvc4_17.drv" -> "cvc4_16.gen";
	"alt_ergo_2_2_0.drv" -> "alt_ergo_common.drv";
	"alt_ergo_2_2_0.drv" -> "no-bv.gen";
	"cvc4_16_counterexample.drv" -> "cvc4_16.drv";
	"cvc4_16.drv" -> "cvc4_16.gen";
	"cvc4_17_strings_counterexample.drv" -> "cvc4_17_strings.drv";
	"vampire-smt.drv" -> "smt-libv2.gen";
	"cvc4_16.gen" -> "smt-libv2.gen";
	"cvc4_16.gen" -> "cvc4_bv.gen";
	"cvc4_16.gen" -> "smt-libv2-bv.gen";
	"cvc4_16.gen" -> "smt-libv2-floats.gen";
	"cvc4_14.drv" -> "smt-libv2.gen";
	"cvc4_14.drv" -> "cvc4_bv.gen";
	"cvc4_14.drv" -> "smt-libv2-bv.gen";
	"z3_471_nobv.drv" -> "smtlib-strings.gen";
	"z3_471_nobv.drv" -> "z3_432.drv";
	"z3_432.drv" -> "smt-libv2.gen";
	"z3_432.drv" -> "no-bv.gen";
	"cvc4_15_counterexample.drv" -> "cvc4_15.drv";
	"cvc4_15.drv" -> "smt-libv2.gen";
	"cvc4_15.drv" -> "cvc4_bv.gen";
	"cvc4_15.drv" -> "smt-libv2-bv.gen";
	"verit.drv" -> "smt-libv2.gen";
	"alt_ergo.drv" -> "alt_ergo_common.drv";
	"alt_ergo.drv" -> "no-bv.gen";
	"alt_ergo_fp.drv" -> "alt_ergo_common.drv";
	"alt_ergo_fp.drv" -> "no-bv.gen";
	"yices-smt2.drv" -> "smt-libv2.gen";
	"z3_440.drv" -> "smt-libv2.gen";
	"z3_440.drv" -> "smt-libv2-bv.gen";
	"z3_440.drv" -> "z3_bv.gen";
	"z3_440.drv" -> "smt-libv2-floats.gen";
	"cvc4_17_counterexample.drv" -> "cvc4_17.drv";
	"z3.drv" -> "smt-libv2.gen";
	"z3_471.drv" -> "smtlib-strings.gen";
	"z3_471.drv" -> "z3_440.drv";
	"alt_ergo_2_3.drv" -> "alt_ergo_common.drv";
	"alt_ergo_2_3.drv" -> "no-bv.gen";
	"cvc4.drv" -> "smt-libv2.gen";
	"cvc4.drv" -> "no-bv.gen";
	"alt_ergo_model.drv" -> "alt_ergo.drv";
	"z3_440_counterexample.drv" -> "z3_440.drv";
	"z3_471_counterexample.drv" -> "smtlib-strings.gen";
	"z3_471_counterexample.drv" -> "z3_471.drv";
}

Fig. 12.1 Driver dependencies for SMT solvers

digraph G_cc {
	graph [nodesep=0.4,
		rankdir=RL,
		ranksep=0.6
	];
	node [margin=0.05,
		shape=box
	];
	"vampire.drv" -> "tptp.gen";
	"spass.drv" -> "tptp.gen";
	"iprover.drv" -> "tptp.gen";
	"eprover.drv" -> "tptp.gen";
	"metis.drv" -> "tptp.gen";
	"safeprover.drv" -> "tptp.gen";
}

Fig. 12.2 Driver dependencies for TPTP solvers

digraph G_cc {
	graph [nodesep=0.4,
		rankdir=RL,
		ranksep=0.6
	];
	node [margin=0.05,
		shape=box
	];
	"coq.drv" -> "coq-common.gen";
	"coq-common.gen" -> "coq-realizations.aux";
	"coq-realize.drv" -> "coq-common.gen";
}

Fig. 12.3 Driver dependencies for Coq

digraph G_cc {
	graph [nodesep=0.4,
		rankdir=RL,
		ranksep=0.6
	];
	node [margin=0.05,
		shape=box
	];
	"isabelle2019-realize.drv" -> "isabelle-common.gen";
	"isabelle-common.gen" -> "isabelle-realizations.aux";
	"isabelle2018.drv" -> "isabelle-common.gen";
	"isabelle2019.drv" -> "isabelle-common.gen";
	"isabelle2018-realize.drv" -> "isabelle-common.gen";
}

Fig. 12.4 Driver dependencies for Isabelle/HOL

digraph G_cc {
	graph [nodesep=0.4,
		rankdir=RL,
		ranksep=0.6
	];
	node [margin=0.05,
		shape=box
	];
	"pvs-realize.drv" -> "pvs-common.gen";
	"pvs-common.gen" -> "pvs-realizations.aux";
	"pvs.drv" -> "pvs-common.gen";
}

Fig. 12.5 Driver dependencies for PVS

The most important drivers dependencies are shown in the following figures: Fig. 12.1 shows the drivers files for SMT solvers, Fig. 12.2 for TPTP solvers, Fig. 12.3 for Coq, Fig. 12.4 for Isabelle/HOL, and Fig. 12.5 for PVS.

12.5. Adding extra drivers for user theories

It is possible for the users to augment the system drivers with extra information for their own declared theories. The processus is described by the following example.

First, we define a new theory in a file bvmisc.mlw, containing

theory T
use bv.BV8
use bv.BV16
function lsb BV16.t : BV8.t (** least significant bits *)
function msb BV16.t : BV8.t (** most significant bits *)
end

For such a theory, it is a good idea to declare specific translation rules for provers that have a built-in bit-vector support, such as Z3 and CVC4 in this example. To do so, we write a extension driver file, my.drv, containing

theory bvmisc.T
syntax function lsb "((_ extract 7 0) %1)"
syntax function msb "((_ extract 15 8) %1)"
end

Now to tell Why3 that we would like this driver extension when calling Z3 or CVC4, we write an extra configuration file, my.conf, containing

[prover_modifiers]
prover = "CVC4"
driver = "my.drv"

[prover_modifiers]
prover = "Z3"
driver = "my.drv"

Finally, to make the whole thing work, we have to call any Why3 command with the additional option why3 --extra-config, such as

why3 --extra-config=my.conf prove myfile.mlw

12.6. Transformations

This section documents the available transformations. Note that the set of available transformations in your own installation is given by why3 --list-transforms.

apply

Apply an hypothesis to the goal of the task using a modus ponens rule. The hypothesis should be an implication whose conclusion can be matched with the goal. The intuitive behavior of apply can be translated as follows. Given \(\Gamma, h: f_1 \rightarrow f_2 \vdash G: f_2\), apply h generates a new task \(\Gamma, h: f_1 \rightarrow f_2 \vdash G: f_1\).

In practice, the transformation also manages to instantiate some variables with the appropriate terms.

For example, applying the transformation apply zero_is_even on the following goal

predicate is_even int
predicate is_zero int
axiom zero_is_even: forall x: int. is_zero x -> is_even x
goal G: is_even 0

produces the following goal:

predicate is_even int
predicate is_zero int
axiom zero_is_even: forall x:int. is_zero x -> is_even x
goal G: is_zero 0

The transformation first matched the goal against the hypothesis and instantiated x with 0. It then applied the modus ponens rule to generate the new goal.

This transformation helps automated provers when they do not know which hypothesis to use in order to prove a goal.

apply with

Variant of apply intended to be used in contexts where the latter cannot infer what terms to use for variables given in the applied hypothesis.

For example, applying the transformation apply transitivity on the following goal

axiom ac: a = c
axiom cb: c = b
axiom transitivity : forall x y z:int. x = y -> y = z -> x = z
goal G1 : a = b

raises the following error:

apply: Unable to infer arguments (try using "with") for: y

It means that the tool is not able to infer the right term to instantiate symbol y. In our case, the user knows that the term c should work. So, it can be specified as follows: apply transitivity with c

This generates two goals which are easily provable with hypotheses ac and cb.

When multiple variables are needed, they should be provided as a list in the transformation. For the sake of the example, we complicate the transitivity hypothesis:

axiom t : forall x y z k:int. k = k -> x = y -> y = z -> x = z

A value can be provided for k as follows: apply t with c,0.

assert

Create an intermediate subgoal. This is comparable to assert written in WhyML code. Here, the intent is only to help provers by specifying one key argument of the reasoning they should use.

Example: From a goal of the form \(\Gamma \vdash G\), the transformation assert (n = 0) produces the following two tasks: \(\Gamma \vdash h: n = 0\) and \(\Gamma, h: n = 0 \vdash G\). This effectively adds h as an intermediate goal to prove.

assert as

Same as assert, except that a name can be given to the new hypothesis. Example: assert (x = 0) as x0.

case

Split a goal into two subgoal, using the excluded middle on a given formula. On the task \(\Gamma \vdash G\), the transformation case f produces two tasks: \(\Gamma, h: f \vdash G\) and \(\Gamma, h: \neg f \vdash G\).

For example, applying case (x = 0) on the following goals

constant x : int
constant y : int
goal G: if x = 0 then y = 2 else y = 3

produces the following goals:

constant x : int
constant y : int
axiom h : x = 0
goal G : if x = 0 then y = 2 else y = 3
constant x : int
constant y : int
axiom h : not x = 0
goal G : if x = 0 then y = 2 else y = 3

The intent is again to simplify the job of automated provers by giving them a key argument of the reasoning behind the proof of a subgoal.

case as

Same as case, except that a name can be given to the new hypothesis. Example: case (x = 0) as x0.

clear_but

Remove all the hypotheses except those specified in the arguments. This is useful when a prover fails to find relevant hypotheses in a very large context. Example: clear_but h23,h25.

compute_hyp

Apply the transformation compute_in_goal on the given hypothesis.

compute_hyp_specified

Apply the transformation compute_specified on the given hypothesis.

compute_in_goal

Aggressively apply all known computation/simplification rules.

The kinds of simplification are as follows.

  • Computations with built-in symbols, e.g., operations on integers, when applied to explicit constants, are evaluated. This includes evaluation of equality when a decision can be made (on integer constants, on constructors of algebraic data types), Boolean evaluation, simplification of pattern-matching/conditional expression, extraction of record fields, and beta-reduction. At best, these computations reduce the goal to true and the transformations thus does not produce any sub-goal. For example, a goal like 6*7=42 is solved by those transformations.

  • Unfolding of definitions, as done by inline_goal. Transformation compute_in_goal unfolds all definitions, including recursive ones. For compute_specified, the user can enable unfolding of a specific logic symbol by attaching the meta rewrite_def to the symbol.

    function sqr (x:int) : int = x * x
    meta "rewrite_def" function sqr
    
  • Rewriting using axioms or lemmas declared as rewrite rules. When an axiom (or a lemma) has one of the forms

    axiom a: forall ... t1 = t2
    

    or

    axiom a: forall ... f1 <-> f2
    

    then the user can declare

    meta "rewrite" prop a
    

    to turn this axiom into a rewrite rule. Rewriting is always done from left to right. Beware that there is no check for termination nor for confluence of the set of rewrite rules declared.

Instead of using a meta, it is possible to declare an axiom as a rewrite rule by adding the [@rewrite] attribute on the axiom name or on the axiom itself, e.g.,

axiom a [@rewrite]: forall ... t1 = t2
lemma b: [@rewrite] forall ... f1 <-> f2

The second form allows some form of local rewriting, e.g.,

lemma l: forall x y. ([@rewrite] x = y) -> f x = f y

can be proved by introduce_premises followed by compute_specified.

The computations performed by this transformation can take an arbitrarily large number of steps, or even not terminate. For this reason, the number of steps is bounded by a maximal value, which is set by default to 1000. This value can be increased by another meta, e.g.,

meta "compute_max_steps" 1_000_000

When this upper limit is reached, a warning is issued, and the partly-reduced goal is returned as the result of the transformation.

compute_specified

Same as compute_in_goal, but perform rewriting using only built-in operators and user-provided rules.

cut

Same as assert, but the order of generated subgoals is reversed.

destruct

Eliminate the head symbol of a hypothesis.

For example, applying destruct h on the following goal

constant p1 : bool
predicate p2 int
axiom h : p1 = True /\ (forall x:int. p2 x)
goal G : p2 0

removes the logical connective /\ and produces

constant p1 : bool
predicate p2 int
axiom h1 : p1 = True
axiom h : forall x:int. p2 x
goal G : p2 0

destruct can be applied on the following constructions:

  • false, true,

  • /\, \/, ->, not,

  • exists,

  • if ... then ... else ...,

  • match ... with ... end,

  • (in)equality on constructors of the same type.

destruct_rec

Recursively call destruct on the generated hypotheses. The recursion on implication and match stops after the first occurence of a different symbol.

For example, applying destruct_rec H on the following goal

predicate a
predicate b
predicate c
axiom H : (a -> b) /\ (b /\ c)
goal G : false

does not destruct the implication symbol because it occurs as a subterm of an already destructed symbol. This restriction applies only to implication and match Other symbols are destructed recursively. Thus, in the generated task, the second /\ is simplified:

predicate a
predicate b
predicate c
axiom H2 : a -> b
axiom H1 : b
axiom H: c
goal G : false
destruct_term

Destruct an expression according to the type of the expression. The transformation produces all possible outcomes of a destruction of the algebraic type.

For example, applying destruct_term a on the following goal

type t = A | B int
constant a : t
goal G : a = A

produces the following two goals:

type t = A | B int
constant a : t
constant x : int
axiom h : a = B x
goal G : a = A
type t = A | B int
constant a : t
axiom h : a = A
goal G : a = A

The term was destructed according to all the possible outcomes in the type. Note that, during destruction, a new constant x has been introduced for the argument of constructor B.

destruct_term using

Same as destruct_term, except that names can be given to the constants that were generated.

destruct_term_subst

Same as destruct_term, except that it also substitutes the created term.

eliminate_algebraic

Replace algebraic data types by first-order definitions [Pas09].

eliminate_builtin

Remove definitions of symbols that are declared as builtin in the driver, with a “syntax” rule.

eliminate_definition_func

Replace all function definitions with axioms.

eliminate_definition_pred

Replace all predicate definitions with axioms.

eliminate_definition

Apply both eliminate_definition_func and eliminate_definition_pred.

eliminate_if

Apply both eliminate_if_term and eliminate_if_fmla.

eliminate_if_fmla

Replace formulas of the form if f1 then f2 else f3 by an equivalent formula using implications and other connectives.

eliminate_if_term

Replace terms of the form if formula then t2 else t3 by lifting them at the level of formulas. This may introduce if then else in formulas.

eliminate_inductive

Replace inductive predicates by (incomplete) axiomatic definitions, construction axioms and an inversion axiom.

eliminate_let

Apply both eliminate_let_fmla and eliminate_let_term.

eliminate_let_fmla

Eliminate let by substitution, at the predicate level.

eliminate_let_term

Eliminate let by substitution, at the term level.

eliminate_literal
eliminate_mutual_recursion

Replace mutually recursive definitions with axioms.

eliminate_recursion

Replace all recursive definitions with axioms.

encoding_smt

Encode polymorphic types into monomorphic types [BCCL08].

encoding_tptp

Encode theories into unsorted logic.

exists

Instantiate an existential quantification with a witness.

For example, applying exists 0 on the following goal

goal G : exists x:int. x = 0

instantiates the symbol x with 0. Thus, the goal becomes

goal G : 0 = 0
hide

Hide a given term, by creating a new constant equal to the term and then replacing all occurences of the term in the context by this constant.

For example, applying hide t (1 + 1) on the goal

constant y : int
axiom h : forall x:int. x = (1 + 1)
goal G : (y - (1 + 1)) = ((1 + 1) - (1 + 1))

replaces all the occurrences of (1 + 1) with t, which gives the following goal:

constant y : int
constant t : int
axiom H : t = (1 + 1)
axiom h : forall x:int. x = t
goal G : (y - t) = (t - t)
hide_and_clear

First apply hide and then remove the equality between the hidden term and the introduced constant. This means that the hidden term completely disappears and cannot be recovered.

induction

Perform a reasoning by induction for the current goal.

For example, applying induction n on the following goal

constant n : int
predicate p int
predicate p1 int
axiom h : p1 n
goal G : p n

performs an induction on n starting at 0. The goal for the base case is

constant n : int
predicate p int
predicate p1 int
axiom h : p1 n
axiom Init : n <= 0
goal G : p n

while the recursive case is

constant n : int
predicate p int
predicate p1 int
axiom h : p1 n
axiom Init : 0 < n
axiom Hrec : forall n1:int. n1 < n -> p1 n1 -> p n1
goal G : p n
induction from

Same as induction, but it starts the induction from a given integer instead of 0.

induction_arg_pr

Apply induction_pr on the given hypothesis/goal symbol.

induction_arg_ty_lex

Apply induction_ty_lex on the given symbol.

induction_pr
induction_ty_lex

Perform structural, lexicographic induction on goals involving universally quantified variables of algebraic data types, such as lists, trees, etc. For instance, it transforms the following goal

goal G: forall l: list 'a. length l >= 0

into this one:

goal G :
  forall l:list 'a.
     match l with
     | Nil -> length l >= 0
     | Cons a l1 -> length l1 >= 0 -> length l >= 0
     end

When induction can be applied to several variables, the transformation picks one heuristically. The [@induction] attribute can be used to force induction over one particular variable, with

goal G: forall l1 [@induction] l2 l3: list 'a.
        l1 ++ (l2 ++ l3) = (l1 ++ l2) ++ l3

induction will be applied on l1. If this attribute is attached to several variables, a lexicographic induction is performed on these variables, from left to right.

inline_trivial

Expand and remove definitions of the form

function  f x1 ... xn = g e1 ... ek
predicate p x1 ... xn = q e1 ... ek

when each ei is either a ground term or one of the xj, and each x1 ... xn occurs at most once in all the ei.

The attribute [@inline:trivial] can be used to tag functions, so that the transformation forcefully expands them (not using the conditions above). This can be used to ensure that some specific functions are inlined for automatic provers (inline_trivial is used in many drivers).

inline_goal

Expand all outermost symbols of the goal that have a non-recursive definition.

inline_all

Expand all non-recursive definitions.

instantiate

Generate a new hypothesis with quantified variables replaced by the given terms.

For example, applying instantiate h 0, 1 on the following goal

predicate p int
axiom h : forall x:int, y:int. x <= y -> p x /\ p y
goal G : p 0

generates a new hypothesis:

predicate p int
axiom h : forall x:int, y:int. x <= y -> p x /\ p y
axiom Hinst : 0 <= 1 -> p 0 /\ p 1
goal G : p 0

This is used to help automatic provers that are generally better at working on instantiated hypothesis.

inst_rem

Apply instantiate then remove the original instantiated hypothesis.

introduce_premises

Move antecedents of implications and universal quantifications of the goal into the premises of the task.

intros

Introduce universal quantifiers in the context.

For example, applying intros n, m on the following goal

predicate p int int int
goal G : forall x:int, y:int, z:int. p x y z

produces the following goal:

predicate p int int int
constant n : int
constant m : int
goal G : forall z:int. p n m z
intros_n

Same as intros, but stops after the nth quantified variable or premise.

For example, applying intros_n 2 on the following goal

predicate p int int int
goal G : forall x:int, y:int, z:int. p x y z

produces the following goal:

predicate p int int int
constant x : int
constant y : int
goal G : forall z:int. p x y z
inversion_arg_pr

Apply inversion_pr on the given hypothesis/goal symbol.

inversion_pr
left

Remove the right part of the head disjunction of the goal.

For example, applying left on the following goal

constant x : int
goal G : x = 0 \/ x = 1

produces the following goal:

constant x : int
goal G : x = 0
pose

Add a new constant equal to the given term.

For example, applying pose t (x + 2) to the following goal

constant x : int
goal G : true

produces the following goal:

constant x : int
constant t : int
axiom H : t = (x + 2)
goal G : true
remove

Remove a hypothesis from the context.

For example, applying remove h on the following goal

axiom h : true
goal G : true

produces the following goal:

goal G : true
replace

Replace a term with another one in a hypothesis or in the goal. This generates a new goal which asks for the proof of the equality.

For example, applying replace (y + 1) (x + 2) in h on the following goal

constant x : int
constant y : int
axiom h : x >= (y + 1)
goal G : true

produces the following two goals:

constant x : int
constant y : int
axiom h : x >= (x + 2)
goal G : true
constant x : int
constant y : int
axiom h : x >= (y + 1)
goal G : (y + 1) = (x + 2)

It can be seen as the combination of assert and rewrite.

revert

Opposite of intros. It takes hypotheses/constants and quantifies them in the goal.

For example, applying revert x on the following goal

constant x : int
constant y : int
axiom h : x = y
goal G : true

produces the following goal:

constant y : int
goal G : forall x:int. x = y -> true
rewrite

Rewrite using the given equality hypothesis.

For example, applying rewrite eq on the following goal

function a int : bool
function b int : bool
constant y : int
axiom eq : forall x:int. not x = 0 -> a x = b x
goal G : a y = True

produces the following goal:

function a int : bool
function b int : bool
constant y : int
axiom eq : forall x:int. not x = 0 -> a x = b x
goal G : b y = True

It also produces a goal for the premise of the equality hypothesis (as would apply):

function a int : bool
function b int : bool
constant y : int
axiom eq : forall x:int. not x = 0 -> a x = b x
goal G : not y = 0
rewrite with

Variant of rewrite intended to be used in contexts where the latter cannot infer what terms to use for the variables of the given hypotheses (see also apply with).

For example, the transformation rewrite eq with 0 can be applied to the following goal:

function a int : bool
function b int : bool
constant y : int
axiom eq : forall x:int, z:int. z = 0 -> not x = 0 -> a x = b x
goal G : a y = True

Here, a value is provided for the symbol z. This leads to the following three goals. One is the rewritten one, while the other two are for the premises of the equality hypothesis.

function a int : bool
function b int : bool
constant y : int
axiom eq : forall x:int, z:int. z = 0 -> not x = 0 -> a x = b x
goal G : b y = True
function a int : bool
function b int : bool
constant y : int
axiom eq : forall x:int, z:int. z = 0 -> not x = 0 -> a x = b x
goal G : 0 = 0
function a int : bool
function b int : bool
constant y : int
axiom eq : forall x:int, z:int. z = 0 -> not x = 0 -> a x = b x
goal G : not y = 0
rewrite_list

Variant of rewrite that allows simultaneous rewriting in a list of hypothesis/goals.

right

Remove the left part of the head disjunction of the goal.

For example, applying right on the following goal

constant x : int
goal G : x = 0 \/ x = 1

produces the following goal:

constant x : int
goal G : x = 1
simplify_array

Automatically rewrite the task using the lemma Select_eq of theory map.Map.

simplify_formula

Reduce trivial equalities t=t to true and then simplify propositional structure: removes true, false, simplifies f /\ f to f, etc.

simplify_formula_and_task

Apply simplify_formula and remove the goal if it is equivalent to true.

simplify_recursive_definition

Reduce mutually recursive definitions if they are not really mutually recursive, e.g.,

function f : ... = ... g ...
with g : ... = e

becomes

function g : ... = e
function f : ... = ... g ...

if f does not occur in e.

simplify_trivial_quantification

Simplify quantifications of the form

forall x, x = t -> P(x)

into

P(t)

when x does not occur in t. More generally, this simplification is applied whenever x=t or t=x appears in negative position.

simplify_trivial_quantification_in_goal

Apply simplify_trivial_quantification, but only in the goal.

split_all

Perform both split_premise and split_goal.

split_all_full

Perform both split_premise and split_goal_full.

split_goal

Change conjunctive goals into the corresponding set of subgoals. In absence of case analysis attributes, the number of subgoals generated is linear in the size of the initial goal.

The transformation treats specially asymmetric and by/so connectives. Asymmetric conjunction A && B in goal position is handled as syntactic sugar for A /\ (A -> B). The conclusion of the first subgoal can then be used to prove the second one.

Asymmetric disjunction A || B in hypothesis position is handled as syntactic sugar for A \/ ((not A) /\ B). In particular, a case analysis on such hypothesis would give the negation of the first hypothesis in the second case.

The by connective is treated as a proof indication. In hypothesis position, A by B is treated as if it were syntactic sugar for its regular interpretation A. In goal position, it is treated as if B was an intermediate step for proving A. A by B is then replaced by B and the transformation also generates a side-condition subgoal B -> A representing the logical cut.

Although splitting stops at disjunctive points like symmetric disjunction and left-hand sides of implications, the occurrences of the by connective are not restricted. For instance:

  • Splitting

    goal G : (A by B) && C
    

    generates the subgoals

    goal G1 : B
    goal G2 : A -> C
    goal G3 : B -> A (* side-condition *)
    
  • Splitting

    goal G : (A by B) \/ (C by D)
    

    generates

    goal G1 : B \/ D
    goal G2 : B -> A (* side-condition *)
    goal G3 : D -> C (* side-condition *)
    
  • Splitting

    goal G : (A by B) || (C by D)
    

    generates

    goal G1 : B || D
    goal G2 : B -> A        (* side-condition *)
    goal G3 : B || (D -> C) (* side-condition *)
    

    Note that due to the asymmetric disjunction, the disjunction is kept in the second side-condition subgoal.

  • Splitting

    goal G : exists x. P x by x = 42
    

    generates

    goal G1 : exists x. x = 42
    goal G2 : forall x. x = 42 -> P x (* side-condition *)
    

    Note that in the side-condition subgoal, the context is universally closed.

The so connective plays a similar role in hypothesis position, as it serves as a consequence indication. In goal position, A so B is treated as if it were syntactic sugar for its regular interpretation A. In hypothesis position, it is treated as if both A and B were true because B is a consequence of A. A so B is replaced by A /\ B and the transformation also generates a side-condition subgoal A -> B corresponding to the consequence relation between formula.

As with the by connective, occurrences of so are unrestricted. Examples:

  • Splitting

    goal G : (((A so B) \/ C) -> D) && E
    

    generates

    goal G1 : ((A /\ B) \/ C) -> D
    goal G2 : (A \/ C -> D) -> E
    goal G3 : A -> B               (* side-condition *)
    
  • Splitting

    goal G : A by exists x. P x so Q x so R x by T x
    (* reads: A by (exists x. P x so (Q x so (R x by T x))) *)
    

    generates

    goal G1 : exists x. P x
    goal G2 : forall x. P x -> Q x               (* side-condition *)
    goal G3 : forall x. P x -> Q x -> T x        (* side-condition *)
    goal G4 : forall x. P x -> Q x -> T x -> R x (* side-condition *)
    goal G5 : (exists x. P x /\ Q x /\ R x) -> A (* side-condition *)
    

    In natural language, this corresponds to the following proof scheme for A: There exists a x for which P holds. Then, for that witness Q and R also holds. The last one holds because T holds as well. And from those three conditions on x, we can deduce A.

The transformations in the “split” family can be controlled by using attributes on formulas.

The [@stop_split] attribute can be used to block the splitting of a formula. The attribute is removed after blocking, so applying the transformation a second time will split the formula. This is can be used to decompose the splitting process in several steps. Also, if a formula with this attribute is found in non-goal position, its by/so proof indication will be erased by the transformation. In a sense, formulas tagged by [@stop_split] are handled as if they were local lemmas.

The [@case_split] attribute can be used to force case analysis on hypotheses. For instance, applying split_goal on

goal G : ([@case_split] A \/ B) -> C

generates the subgoals

goal G1 : A -> C
goal G2 : B -> C

Without the attribute, the transformation does nothing because undesired case analysis may easily lead to an exponential blow-up.

Note that the precise behavior of splitting transformations in presence of the [@case_split] attribute is not yet specified and is likely to change in future versions.

split_goal_full

Behave similarly to split_goal, but also convert the goal to conjunctive normal form. The number of subgoals generated may be exponential in the size of the initial goal.

split_intro

Perform both split_goal and introduce_premises.

split_premise

Replace axioms in conjunctive form by an equivalent collection of axioms. In absence of case analysis attributes (see split_goal for details), the number of axiom generated per initial axiom is linear in the size of that initial axiom.

split_premise_full

Behave similarly to split_premise, but also convert the axioms to conjunctive normal form. The number of axioms generated per initial axiom may be exponential in the size of the initial axiom.

subst

Substitute a given constant using an equality found in the context. The constant is removed.

For example, when applying subst x on the following goal

constant x : int
constant y : int
constant z : int
axiom h : x = y + 1
axiom h1 : z = (x + y)
goal G : x = z

the transformation first finds the hypothesis h that can be used to rewrite x. Then, it replaces every occurrences of x with y + 1. Finally, it removes h and x. The resulting goal is as follows:

constant y : int
constant z : int
axiom h1 : z = ((y + 1) + y)
goal G : (y + 1) = z

This transformation is used to make the task more easily readable by a human during debugging. This transformation should not help automatic provers at all as they generally implement substitution rules in their logic.

unfold

Unfold the definition of a logical symbol in the given hypothesis.

For example, applying unfold p on the following goal

predicate p (x:int) = x <= 22
axiom h : forall x:int. p x -> p (x - 1)
goal G : p 21

produces the following goal:

predicate p (x:int) = x <= 22
axiom h : forall x:int. p x -> p (x - 1)
goal G : 21 <= 22

One can also unfold in the hypothesis, using unfold p in h, which gives the following goal:

predicate p (x:int) = x <= 22
axiom h : forall x:int. x <= 22 -> (x - 1) <= 22
goal G : 21 <= 22
use_th

Import a theory inside the current context. This is used, in some rare case, to reduced the size of the context in other goals, since importing a theory in the WhyML code would the theory available in all goals whereas the theory is only needed in one specific goal.

For example, applying use_th int.Int on the following goal

predicate p int
goal G : p 5

imports the Int theory. So, one is able to use the addition over integers, e.g., replace 5 (2 + 3).

Any lemma appearing in the imported theory can also be used.

Note that axioms are also imported. So, this transformation should be used with care. We recommend to use only theories that do not contain any axiom because this transformation could easily make the context inconsistent.

12.7. Proof Strategies

As seen in Section 6.3, the IDE provides a few buttons that trigger the run of simple proof strategies on the selected goals. Proof strategies can be defined using a basic assembly-style language, and put into the Why3 configuration file. The commands of this basic language are:

  • c p t m calls the prover p with a time limit t and memory limit m. On success, the strategy ends, it continues to next line otherwise.

  • t n lab applies the transformation n. On success, the strategy continues to label lab, and is applied to each generated sub-goals. It continues to next line otherwise.

  • g lab unconditionally jumps to label lab.

  • lab: declares the label lab. The default label exit stops the program.

To examplify this basic programming language, we give below the default strategies that are attached to the default buttons of the IDE, assuming that the provers Alt-Ergo 2.3.0, CVC4 1.7 and Z3 4.8.4 were detected by the why3 config command.

Split_VC

is bound to the 1-line strategy

t split_vc exit
Auto_level_0

is bound to

c Z3,4.8.4, 1 1000
c Alt-Ergo,2.3.0, 1 1000
c CVC4,1.7, 1 1000

The three provers are tried for a time limit of 1 second and memory limit of 1 Gb, each in turn. This is a perfect strategy for a first attempt to discharge a new goal.

Auto_level_1

is bound to

c Z3,4.8.4, 5 1000
c Alt-Ergo,2.3.0, 5 1000
c CVC4,1.7, 5 1000

Same as Auto_level_0 but with 5 seconds instead of 1.

Auto_level_2

is bound to

start:
c Z3,4.8.4, 1 1000
c Alt-Ergo,2.3.0, 1 1000
c CVC4,1.7, 1 1000
t split_vc start
c Z3,4.8.4, 10 4000
c Alt-Ergo,2.3.0, 10 4000
c CVC4,1.7, 10 4000

The three provers are first tried for a time limit of 1 second and memory limit of 1 Gb, each in turn. If none of them succeed, a split is attempted. If the split works then the same strategy is retried on each sub-goals. If the split does not succeed, the provers are tried again with larger limits.

Auto level 3

is bound to

start:
c Z3,4.8.4, 1 1000
c Eprover,2.0, 1 1000
c Spass,3.7, 1 1000
c Alt-Ergo,2.3.0, 1 1000
c CVC4,1.7, 1 1000
t split_vc start
c Z3,4.8.4, 5 2000
c Eprover,2.0, 5 2000
c Spass,3.7, 5 2000
c Alt-Ergo,2.3.0, 5 2000
c CVC4,1.7, 5 2000
t introduce_premises afterintro
afterintro:
t inline_goal afterinline
g trylongertime
afterinline:
t split_all_full start
trylongertime:
c Z3,4.8.4, 30 4000
c Eprover,2.0, 30 4000
c Spass,3.7, 30 4000
c Alt-Ergo,2.3.0, 30 4000
c CVC4,1.7, 30 4000

Notice that now 5 provers are used. The provers are first tried for a time limit of 1 second and memory limit of 1 Gb, each in turn. If none of them succeed, a split is attempted. If the split works then the same strategy is retried on each sub-goals. If the split does not succeed, the prover are tried again with limits of 5 s and 2 Gb. If all fail, we attempt the transformation of introduction of premises in the context, followed by an inlining of the definitions in the goals. We then attempt a split again, if the split succeeds, we restart from the beginning, if it fails then provers are tried again with 30s and 4 Gb.

12.8. WhyML Attributes

case_split
induction
infer
inline:trivial
model_trace
rewrite
stop_split
vc:annotation
vc:divergent
vc:keep_precondition
vc:sp
vc:wp
vc:white_box

12.9. Why3 Metas

compute_max_steps
keep:literal
realized_theory
rewrite
rewrite_def

12.10. Debug Flags

infer-loop
infer-print-ai-result
infer-print-cfg
print-inferred-invs
print-domains-loop
stack_trace

12.11. Updating Syntax Error Messages

Here is the developer’s recipe to update a syntax error message. We do it on the following illustrative example.

function let int : int

If such a file is passed to Why3, one obtains:

File "bench/parsing/bad/498_function.mlw", line 1, characters 9-12:
syntax error

The recipe given here provides a way to produce a more informative message. It is based on handcrafted error messages provided by the Menhir parser generator.

The first step is to call menhir with option --interpret-error while giving as input the erroneous input, under the form of a sequence of tokens as generated by src/parser/lexer.mll.

$ echo "decl_eof: FUNCTION LET" | menhir --base src/parser/parser --interpret-error src/parser/parser_common.mly src/parser/parser.mly
decl_eof: FUNCTION LET
##
## Ends in an error in state: 1113.
##
## pure_decl -> FUNCTION . function_decl list(with_logic_decl) [ VAL USE TYPE THEORY SCOPE PREDICATE MODULE META LET LEMMA INDUCTIVE IMPORT GOAL FUNCTION EXCEPTION EOF END CONSTANT COINDUCTIVE CLONE AXIOM ]
##
## The known suffix of the stack is as follows:
## FUNCTION
##

<YOUR SYNTAX ERROR MESSAGE HERE>

The text returned by that command should be appended to src/parser/handcrafted.messages, with of course an appropriate error message, such as this one:

expected function name must be a non-reserved uncapitalized identifier (token LIDENT_NQ), found "$0"