tactic ::= ... |vcgen`vcgen` will break down a Hoare triple proof goal like `⦃P⦄ prog ⦃Q⦄` into verification conditions, provided that all functions used in `prog` have specifications registered with `@[spec]`. `vcgen` is experimental and subject to change. `set_option experimental.vcgen true` acknowledges its experimental status and silences the warning that each call reports. ### Program types `vcgen` works on any program type `Prog` that carries a `Std.WP.WP` interpretation. A monad is one such program type. An inductive type of commands is another, once its weakest precondition is defined in terms of an operational semantics. ### Verification conditions and specifications A verification condition is an entailment `pre ⊑ post` in the assertion lattice of the goal. The original program `prog` no longer occurs in it. The assertion lattice is any `CompleteLattice`, and the entailment is its order, so a verification condition is an ordinary Lean goal that `grind` can attack. A `@[spec]` theorem declares a specification in one of two forms. A Hoare triple `foo_spec : ⦃P⦄ foo a b c ⦃Q⦄` states it directly. An equation `baz_eq : baz a b c = ...` states it by rewriting. ### Features When used like `vcgen [foo_spec, bar_def, baz_eq]`, `vcgen` will additionally * add a Hoare triple specification `foo_spec : ⦃P⦄ foo ... ⦃Q⦄` to the `spec` set for a function `foo` occurring in `prog`, * unfold a definition `def bar_def ... := ...` in `prog`, * rewrite with an equational specification `baz_eq : baz ... = ...` in `prog`. ### Config options See `Lean.Elab.Tactic.Do.VCGen.Config` for the options. Of particular note are `stepLimit = some 42`, which is useful for bisecting bugs and tracing execution, and `errorOnMissingSpec := false`, which leaves a goal whose head has no matching spec as a verification condition for you to discharge. ### Extended syntax Often, `vcgen` will be used like this: ``` vcgen [...] invariants · I1 · I2 with try finish ``` The `with` clause takes one step of `grind` mode, such as `finish`. That step shares the E-graph that `vcgen` builds, so it sees the hypotheses of every verification condition. A sequence of steps needs explicit grouping, as in `with (s₁; s₂)`. Invariants also take a labelled form, which is useful for naming inaccessibles: ``` vcgen [...] invariants | inv1 _ acc _ => I1 acc | _ => I2 ``` `vcgen` has three further clauses. ``` vcgen until f a _ c ``` stops VC generation at the first program that matches the pattern, and leaves that program in the goal. Holes are written `_`, as in `conv in`. ``` vcgen frames | f a _ c => F ``` supplies a frame for a call. Take `mkFreshNat : StateM (Nat × Nat) Nat`, which returns `s.1` and increments it. Its specification mentions `s.1` alone: ``` @[spec] theorem mkFreshNat_spec : ⦃fun s => ⌜s.1 = n⌝⦄ mkFreshNat ⦃fun r s => ⌜r = n ∧ s.1 = n + 1⌝⦄ ``` A caller that knows `s.2 = 7` loses that fact at the call, because the postcondition says nothing about `s.2`. Writing ``` vcgen frames | mkFreshNat => fun s => ⌜s.2 = 7⌝ ``` carries `s.2 = 7` past the call, and `vcgen` proves that `mkFreshNat` preserves it. The named binders are in scope in the frame, bound to the matched arguments. ``` vcgen simp [Nat.add_assoc, h] ``` adds theorems to the simp set of `vcgen`. `vcgen` rewrites the hypotheses it introduces, the state arguments of the program and the verification conditions with the theorems tagged `@[vcgen_simp]`, the theorems of the clause, and the evaluation of ground terms such as `41 + 1` and `"x" = "y"`. An argument is a theorem or definition name, a local hypothesis, a proof term, or `*` for every local hypothesis. A theorem with hypotheses, such as `wrap_of_lt (h : n < 2 ^ w) : wrap w n = n`, rewrites only if the same simplification proves each hypothesis. `vcgen -simp` turns this simplification off. ### Invariant suggestions `vcgen [...] invariants?` warns that invariant suggestions are not available in `vcgen` and that the keyword is slated for removal. Alternatives after `invariants?` elaborate like `invariants`.optConfig ([(Configuration options for tactics.simpStar |The simp lemma specification `*` means to rewrite with all hypothesessimpErase |An erasure specification `-thm` says to remove `thm` from the simp setsimpLemma),*])? (until term)? (A simp lemma specification is: * optional `↑` or `↓` to specify use before or after entering the subterm * optional `←` to use the lemma backward * `thm` for the theorem to rewrite withAfter `mvcgen [...]`, there can be an optional `invariants` followed by either * a bulleted list of invariants `· term; · term`. * a labelled list of invariants `| inv1 => term; inv2 a b c => term`, which is useful for naming inaccessibles. The tracing variant ` invariants? ` will suggest a skeleton for missing invariants; see the docstring for `mvcgen`.invariants (Either the contextual keyword ` invariants ` or its tracing form ` invariants? ` which suggests skeletons for missing invariants as a hint.invariantDotAlt |An invariant alternative of the form `· term`, one per invariant goal.invariantCaseAlt)*)? (simp [(An invariant alternative of the form `| inv<n> a b c => term`, one per invariant goal.simpStar |The simp lemma specification `*` means to rewrite with all hypothesessimpErase |An erasure specification `-thm` says to remove `thm` from the simp setsimpLemma),*])? (with vcgenDischarge)?A simp lemma specification is: * optional `↑` or `↓` to specify use before or after entering the subterm * optional `←` to use the lemma backward * `thm` for the theorem to rewrite with
Generates verification conditions for the current goal.
The Lean.Parser.Tactic.vcgen : tactic`vcgen` will break down a Hoare triple proof goal like `⦃P⦄ prog ⦃Q⦄` into verification conditions,
provided that all functions used in `prog` have specifications registered with `@[spec]`.
`vcgen` is experimental and subject to change. `set_option experimental.vcgen true` acknowledges
its experimental status and silences the warning that each call reports.
### Program types
`vcgen` works on any program type `Prog` that carries a `Std.WP.WP` interpretation. A monad
is one such program type. An inductive type of commands is another, once its weakest precondition is
defined in terms of an operational semantics.
### Verification conditions and specifications
A verification condition is an entailment `pre ⊑ post` in the assertion lattice of the goal. The
original program `prog` no longer occurs in it. The assertion lattice is any `CompleteLattice`, and
the entailment is its order, so a verification condition is an ordinary Lean goal that `grind` can
attack.
A `@[spec]` theorem declares a specification in one of two forms. A Hoare triple
`foo_spec : ⦃P⦄ foo a b c ⦃Q⦄` states it directly. An equation `baz_eq : baz a b c = ...` states it
by rewriting.
### Features
When used like `vcgen [foo_spec, bar_def, baz_eq]`, `vcgen` will additionally
* add a Hoare triple specification `foo_spec : ⦃P⦄ foo ... ⦃Q⦄` to the `spec` set for a function
`foo` occurring in `prog`,
* unfold a definition `def bar_def ... := ...` in `prog`,
* rewrite with an equational specification `baz_eq : baz ... = ...` in `prog`.
### Config options
See `Lean.Elab.Tactic.Do.VCGen.Config` for the options. Of particular note are `stepLimit = some 42`,
which is useful for bisecting bugs and tracing execution, and `errorOnMissingSpec := false`, which
leaves a goal whose head has no matching spec as a verification condition for you to discharge.
### Extended syntax
Often, `vcgen` will be used like this:
```
vcgen [...] invariants
· I1
· I2
with try finish
```
The `with` clause takes one step of `grind` mode, such as `finish`. That step shares the E-graph that
`vcgen` builds, so it sees the hypotheses of every verification condition. A sequence of steps needs
explicit grouping, as in `with (s₁; s₂)`.
Invariants also take a labelled form, which is useful for naming inaccessibles:
```
vcgen [...] invariants
| inv1 _ acc _ => I1 acc
| _ => I2
```
`vcgen` has three further clauses.
```
vcgen until f a _ c
```
stops VC generation at the first program that matches the pattern, and leaves that program in the
goal. Holes are written `_`, as in `conv in`.
```
vcgen frames
| f a _ c => F
```
supplies a frame for a call. Take `mkFreshNat : StateM (Nat × Nat) Nat`, which returns `s.1` and
increments it. Its specification mentions `s.1` alone:
```
@[spec] theorem mkFreshNat_spec :
⦃fun s => ⌜s.1 = n⌝⦄ mkFreshNat ⦃fun r s => ⌜r = n ∧ s.1 = n + 1⌝⦄
```
A caller that knows `s.2 = 7` loses that fact at the call, because the postcondition says nothing
about `s.2`. Writing
```
vcgen frames
| mkFreshNat => fun s => ⌜s.2 = 7⌝
```
carries `s.2 = 7` past the call, and `vcgen` proves that `mkFreshNat` preserves it. The named binders
are in scope in the frame, bound to the matched arguments.
```
vcgen simp [Nat.add_assoc, h]
```
adds theorems to the simp set of `vcgen`. `vcgen` rewrites the hypotheses it introduces, the state
arguments of the program and the verification conditions with the theorems tagged
`@[vcgen_simp]`, the theorems of the clause, and the evaluation of ground terms such as `41 + 1`
and `"x" = "y"`. An argument is a theorem or definition name, a local hypothesis, a proof term, or
`*` for every local hypothesis. A theorem with hypotheses, such as
`wrap_of_lt (h : n < 2 ^ w) : wrap w n = n`, rewrites only if the same simplification proves each
hypothesis.
`vcgen -simp` turns this simplification off.
### Invariant suggestions
`vcgen [...] invariants?` warns that invariant suggestions are not available in `vcgen` and that
the keyword is slated for removal. Alternatives after `invariants?` elaborate like `invariants`.until clause stops verification condition generation at the first goal that matches the provided pattern.
The Lean.Parser.Tactic.vcgen : tactic`vcgen` will break down a Hoare triple proof goal like `⦃P⦄ prog ⦃Q⦄` into verification conditions,
provided that all functions used in `prog` have specifications registered with `@[spec]`.
`vcgen` is experimental and subject to change. `set_option experimental.vcgen true` acknowledges
its experimental status and silences the warning that each call reports.
### Program types
`vcgen` works on any program type `Prog` that carries a `Std.WP.WP` interpretation. A monad
is one such program type. An inductive type of commands is another, once its weakest precondition is
defined in terms of an operational semantics.
### Verification conditions and specifications
A verification condition is an entailment `pre ⊑ post` in the assertion lattice of the goal. The
original program `prog` no longer occurs in it. The assertion lattice is any `CompleteLattice`, and
the entailment is its order, so a verification condition is an ordinary Lean goal that `grind` can
attack.
A `@[spec]` theorem declares a specification in one of two forms. A Hoare triple
`foo_spec : ⦃P⦄ foo a b c ⦃Q⦄` states it directly. An equation `baz_eq : baz a b c = ...` states it
by rewriting.
### Features
When used like `vcgen [foo_spec, bar_def, baz_eq]`, `vcgen` will additionally
* add a Hoare triple specification `foo_spec : ⦃P⦄ foo ... ⦃Q⦄` to the `spec` set for a function
`foo` occurring in `prog`,
* unfold a definition `def bar_def ... := ...` in `prog`,
* rewrite with an equational specification `baz_eq : baz ... = ...` in `prog`.
### Config options
See `Lean.Elab.Tactic.Do.VCGen.Config` for the options. Of particular note are `stepLimit = some 42`,
which is useful for bisecting bugs and tracing execution, and `errorOnMissingSpec := false`, which
leaves a goal whose head has no matching spec as a verification condition for you to discharge.
### Extended syntax
Often, `vcgen` will be used like this:
```
vcgen [...] invariants
· I1
· I2
with try finish
```
The `with` clause takes one step of `grind` mode, such as `finish`. That step shares the E-graph that
`vcgen` builds, so it sees the hypotheses of every verification condition. A sequence of steps needs
explicit grouping, as in `with (s₁; s₂)`.
Invariants also take a labelled form, which is useful for naming inaccessibles:
```
vcgen [...] invariants
| inv1 _ acc _ => I1 acc
| _ => I2
```
`vcgen` has three further clauses.
```
vcgen until f a _ c
```
stops VC generation at the first program that matches the pattern, and leaves that program in the
goal. Holes are written `_`, as in `conv in`.
```
vcgen frames
| f a _ c => F
```
supplies a frame for a call. Take `mkFreshNat : StateM (Nat × Nat) Nat`, which returns `s.1` and
increments it. Its specification mentions `s.1` alone:
```
@[spec] theorem mkFreshNat_spec :
⦃fun s => ⌜s.1 = n⌝⦄ mkFreshNat ⦃fun r s => ⌜r = n ∧ s.1 = n + 1⌝⦄
```
A caller that knows `s.2 = 7` loses that fact at the call, because the postcondition says nothing
about `s.2`. Writing
```
vcgen frames
| mkFreshNat => fun s => ⌜s.2 = 7⌝
```
carries `s.2 = 7` past the call, and `vcgen` proves that `mkFreshNat` preserves it. The named binders
are in scope in the frame, bound to the matched arguments.
```
vcgen simp [Nat.add_assoc, h]
```
adds theorems to the simp set of `vcgen`. `vcgen` rewrites the hypotheses it introduces, the state
arguments of the program and the verification conditions with the theorems tagged
`@[vcgen_simp]`, the theorems of the clause, and the evaluation of ground terms such as `41 + 1`
and `"x" = "y"`. An argument is a theorem or definition name, a local hypothesis, a proof term, or
`*` for every local hypothesis. A theorem with hypotheses, such as
`wrap_of_lt (h : n < 2 ^ w) : wrap w n = n`, rewrites only if the same simplification proves each
hypothesis.
`vcgen -simp` turns this simplification off.
### Invariant suggestions
`vcgen [...] invariants?` warns that invariant suggestions are not available in `vcgen` and that
the keyword is slated for removal. Alternatives after `invariants?` elaborate like `invariants`.invariants clause allows loop invariants to be specified.
These invariants are used during verification condition generation and can inform the simplification and automation passes.
By default, all the hypotheses that vcgen introduces, the program's intermediate states, and the resulting verification conditions are simplified according to the vcgen_simp set.
The Lean.Parser.Tactic.vcgen : tactic`vcgen` will break down a Hoare triple proof goal like `⦃P⦄ prog ⦃Q⦄` into verification conditions,
provided that all functions used in `prog` have specifications registered with `@[spec]`.
`vcgen` is experimental and subject to change. `set_option experimental.vcgen true` acknowledges
its experimental status and silences the warning that each call reports.
### Program types
`vcgen` works on any program type `Prog` that carries a `Std.WP.WP` interpretation. A monad
is one such program type. An inductive type of commands is another, once its weakest precondition is
defined in terms of an operational semantics.
### Verification conditions and specifications
A verification condition is an entailment `pre ⊑ post` in the assertion lattice of the goal. The
original program `prog` no longer occurs in it. The assertion lattice is any `CompleteLattice`, and
the entailment is its order, so a verification condition is an ordinary Lean goal that `grind` can
attack.
A `@[spec]` theorem declares a specification in one of two forms. A Hoare triple
`foo_spec : ⦃P⦄ foo a b c ⦃Q⦄` states it directly. An equation `baz_eq : baz a b c = ...` states it
by rewriting.
### Features
When used like `vcgen [foo_spec, bar_def, baz_eq]`, `vcgen` will additionally
* add a Hoare triple specification `foo_spec : ⦃P⦄ foo ... ⦃Q⦄` to the `spec` set for a function
`foo` occurring in `prog`,
* unfold a definition `def bar_def ... := ...` in `prog`,
* rewrite with an equational specification `baz_eq : baz ... = ...` in `prog`.
### Config options
See `Lean.Elab.Tactic.Do.VCGen.Config` for the options. Of particular note are `stepLimit = some 42`,
which is useful for bisecting bugs and tracing execution, and `errorOnMissingSpec := false`, which
leaves a goal whose head has no matching spec as a verification condition for you to discharge.
### Extended syntax
Often, `vcgen` will be used like this:
```
vcgen [...] invariants
· I1
· I2
with try finish
```
The `with` clause takes one step of `grind` mode, such as `finish`. That step shares the E-graph that
`vcgen` builds, so it sees the hypotheses of every verification condition. A sequence of steps needs
explicit grouping, as in `with (s₁; s₂)`.
Invariants also take a labelled form, which is useful for naming inaccessibles:
```
vcgen [...] invariants
| inv1 _ acc _ => I1 acc
| _ => I2
```
`vcgen` has three further clauses.
```
vcgen until f a _ c
```
stops VC generation at the first program that matches the pattern, and leaves that program in the
goal. Holes are written `_`, as in `conv in`.
```
vcgen frames
| f a _ c => F
```
supplies a frame for a call. Take `mkFreshNat : StateM (Nat × Nat) Nat`, which returns `s.1` and
increments it. Its specification mentions `s.1` alone:
```
@[spec] theorem mkFreshNat_spec :
⦃fun s => ⌜s.1 = n⌝⦄ mkFreshNat ⦃fun r s => ⌜r = n ∧ s.1 = n + 1⌝⦄
```
A caller that knows `s.2 = 7` loses that fact at the call, because the postcondition says nothing
about `s.2`. Writing
```
vcgen frames
| mkFreshNat => fun s => ⌜s.2 = 7⌝
```
carries `s.2 = 7` past the call, and `vcgen` proves that `mkFreshNat` preserves it. The named binders
are in scope in the frame, bound to the matched arguments.
```
vcgen simp [Nat.add_assoc, h]
```
adds theorems to the simp set of `vcgen`. `vcgen` rewrites the hypotheses it introduces, the state
arguments of the program and the verification conditions with the theorems tagged
`@[vcgen_simp]`, the theorems of the clause, and the evaluation of ground terms such as `41 + 1`
and `"x" = "y"`. An argument is a theorem or definition name, a local hypothesis, a proof term, or
`*` for every local hypothesis. A theorem with hypotheses, such as
`wrap_of_lt (h : n < 2 ^ w) : wrap w n = n`, rewrites only if the same simplification proves each
hypothesis.
`vcgen -simp` turns this simplification off.
### Invariant suggestions
`vcgen [...] invariants?` warns that invariant suggestions are not available in `vcgen` and that
the keyword is slated for removal. Alternatives after `invariants?` elaborate like `invariants`.simp clause adds further theorems.
Simplification can be switched off by setting the simp flag to false.
Because vcgen shares much of its implementation with grind, the Lean.Parser.Tactic.vcgen : tactic`vcgen` will break down a Hoare triple proof goal like `⦃P⦄ prog ⦃Q⦄` into verification conditions,
provided that all functions used in `prog` have specifications registered with `@[spec]`.
`vcgen` is experimental and subject to change. `set_option experimental.vcgen true` acknowledges
its experimental status and silences the warning that each call reports.
### Program types
`vcgen` works on any program type `Prog` that carries a `Std.WP.WP` interpretation. A monad
is one such program type. An inductive type of commands is another, once its weakest precondition is
defined in terms of an operational semantics.
### Verification conditions and specifications
A verification condition is an entailment `pre ⊑ post` in the assertion lattice of the goal. The
original program `prog` no longer occurs in it. The assertion lattice is any `CompleteLattice`, and
the entailment is its order, so a verification condition is an ordinary Lean goal that `grind` can
attack.
A `@[spec]` theorem declares a specification in one of two forms. A Hoare triple
`foo_spec : ⦃P⦄ foo a b c ⦃Q⦄` states it directly. An equation `baz_eq : baz a b c = ...` states it
by rewriting.
### Features
When used like `vcgen [foo_spec, bar_def, baz_eq]`, `vcgen` will additionally
* add a Hoare triple specification `foo_spec : ⦃P⦄ foo ... ⦃Q⦄` to the `spec` set for a function
`foo` occurring in `prog`,
* unfold a definition `def bar_def ... := ...` in `prog`,
* rewrite with an equational specification `baz_eq : baz ... = ...` in `prog`.
### Config options
See `Lean.Elab.Tactic.Do.VCGen.Config` for the options. Of particular note are `stepLimit = some 42`,
which is useful for bisecting bugs and tracing execution, and `errorOnMissingSpec := false`, which
leaves a goal whose head has no matching spec as a verification condition for you to discharge.
### Extended syntax
Often, `vcgen` will be used like this:
```
vcgen [...] invariants
· I1
· I2
with try finish
```
The `with` clause takes one step of `grind` mode, such as `finish`. That step shares the E-graph that
`vcgen` builds, so it sees the hypotheses of every verification condition. A sequence of steps needs
explicit grouping, as in `with (s₁; s₂)`.
Invariants also take a labelled form, which is useful for naming inaccessibles:
```
vcgen [...] invariants
| inv1 _ acc _ => I1 acc
| _ => I2
```
`vcgen` has three further clauses.
```
vcgen until f a _ c
```
stops VC generation at the first program that matches the pattern, and leaves that program in the
goal. Holes are written `_`, as in `conv in`.
```
vcgen frames
| f a _ c => F
```
supplies a frame for a call. Take `mkFreshNat : StateM (Nat × Nat) Nat`, which returns `s.1` and
increments it. Its specification mentions `s.1` alone:
```
@[spec] theorem mkFreshNat_spec :
⦃fun s => ⌜s.1 = n⌝⦄ mkFreshNat ⦃fun r s => ⌜r = n ∧ s.1 = n + 1⌝⦄
```
A caller that knows `s.2 = 7` loses that fact at the call, because the postcondition says nothing
about `s.2`. Writing
```
vcgen frames
| mkFreshNat => fun s => ⌜s.2 = 7⌝
```
carries `s.2 = 7` past the call, and `vcgen` proves that `mkFreshNat` preserves it. The named binders
are in scope in the frame, bound to the matched arguments.
```
vcgen simp [Nat.add_assoc, h]
```
adds theorems to the simp set of `vcgen`. `vcgen` rewrites the hypotheses it introduces, the state
arguments of the program and the verification conditions with the theorems tagged
`@[vcgen_simp]`, the theorems of the clause, and the evaluation of ground terms such as `41 + 1`
and `"x" = "y"`. An argument is a theorem or definition name, a local hypothesis, a proof term, or
`*` for every local hypothesis. A theorem with hypotheses, such as
`wrap_of_lt (h : n < 2 ^ w) : wrap w n = n`, rewrites only if the same simplification proves each
hypothesis.
`vcgen -simp` turns this simplification off.
### Invariant suggestions
`vcgen [...] invariants?` warns that invariant suggestions are not available in `vcgen` and that
the keyword is slated for removal. Alternatives after `invariants?` elaborate like `invariants`.with clause allows either an interactive grind tactic or an ordinary tactic to be applied in all generated verification conditions.