Tactic: seq
The seq tactic applies to program-logic goals by splitting the
program(s) under consideration into two consecutive parts.
Applying seq allows one to decompose such a goal into two separate
program-logic obligations by splitting the program(s) at a chosen point.
The first obligation establishes that the initial precondition ensures
some intermediate assertion after execution of the first part. The second
obligation then shows that, assuming this intermediate assertion, execution
of the second part entails the desired postcondition.
The seq tactic requires the intermediate assertion to be supplied by
the user, it is not inferred automatically.
Variant: Hoare logic
Syntax
seq {codepos} : ({formula})
The {codepos} specifies the position in the program where the split
should occur. The formula {formula} is the intermediate assertion that
must hold after execution of the first part of the program.
Applying this form of seq produces two Hoare-style proof obligations:
one for the first segment, from the original precondition to the supplied
intermediate assertion, and one for the remaining segment, from this
assertion to the original postcondition.
Variant: Probabilistic relation Hoare logic (two-sided)
Syntax
seq {codepos} {codepos} : {formula}
Here, the first {codepos} specifies where to split the left-hand
program, and the second {codepos} specifies where to split the right-hand
program. The formula {formula} is the intermediate relational assertion
that must hold between the two memories after execution of the first parts.
Applying this form of seq produces two relational proof obligations:
one for the initial segments of both programs, from the original precondition
to the supplied intermediate assertion, and one for the remaining segments,
from this assertion to the original postcondition.
Variant: Probabilistic relation Hoare logic (one-sided)
Syntax
seq {side} {codepos} : (_: {formula} ==> {formula})
Variant: Probabilistic Hoare logic
Syntax
seq {codepos} : {formula} {formula|_} {formula|_} {formula|_} {formula|_} {formula}?
Here:
{codepos}specifies where the program is split into a first and a second part.The first
{formula}is the probabilistic intermediate assertion, used to connect the probability reasoning between the two parts of the program.The four arguments
{formula|_}are the real probability bounds required by the probabilistic sequencing rule. Each may be given explicitly, or left as_to let EasyCrypt infer or simplify it.The last optional
{formula}is a non-probabilistic intermediate assertion that is required to hold after execution of the first part. When provided, it is added to the preconditions of the subgoals targeting the second part of the program.
The four real coefficients supplied to seq correspond to the two possible
outcomes of the intermediate probabilistic assertion:
The first coefficient bounds the probability that the intermediate assertion holds after executing the first part of the program.
The second coefficient bounds the probability of reaching the final postcondition after executing the second part, assuming the intermediate assertion holds.
The third coefficient bounds the probability that the intermediate assertion does not hold after the first part.
The fourth coefficient bounds the probability of reaching the final postcondition after the second part, assuming the intermediate assertion does not hold.
These coefficients are then combined in the final arithmetic goal to obtain the probability bound of the original judgement.
When seq is applied to a probabilistic Hoare-logic goal, EasyCrypt splits
the program into two parts and generates several proof obligations that
justify how the probability of the whole program is obtained from the two
fragments.
Concretely, the tactic produces the following kinds of goals:
A Hoare goal for the optional pure assertion. If a final (non-probabilistic) intermediate assertion is provided, the first goal is to prove that the first part of the program establishes this assertion from the current precondition. If no assertion is given, it is taken to be
true, and this goal is trivial.A probabilistic goal for the first part. A goal is generated to bound the probability that the first part of the program establishes the intermediate probabilistic assertion.
Probabilistic goals for the second part under the intermediate assertion. The second part of the program is then considered assuming that the intermediate probabilistic assertion holds (and also assuming the optional pure assertion, if one was provided). A goal is generated to bound the probability of reaching the final postcondition in this case.
Probabilistic goals for the second part under the negation of the intermediate assertion. A symmetric goal is generated for the case where the intermediate probabilistic assertion does not hold after the first part.
A final logical side-condition combining the bounds Finally, EasyCrypt generates a pure arithmetic obligation stating that the probability bounds supplied to
seqcorrectly combine to give the overall probability bound of the original goal.
[easycrypt failed]
Variant: Expectation Hoare logic
Syntax
seq {codepos} : {formula}