diff options
Diffstat (limited to 'doc/sphinx/user-extensions/proof-schemes.rst')
| -rw-r--r-- | doc/sphinx/user-extensions/proof-schemes.rst | 77 |
1 files changed, 46 insertions, 31 deletions
diff --git a/doc/sphinx/user-extensions/proof-schemes.rst b/doc/sphinx/user-extensions/proof-schemes.rst index 583b73e53..838926d65 100644 --- a/doc/sphinx/user-extensions/proof-schemes.rst +++ b/doc/sphinx/user-extensions/proof-schemes.rst @@ -3,6 +3,8 @@ Proof schemes =============== +.. _proofschemes-induction-principles: + Generation of induction principles with ``Scheme`` -------------------------------------------------------- @@ -10,7 +12,7 @@ The ``Scheme`` command is a high-level tool for generating automatically (possibly mutual) induction principles for given types and sorts. Its syntax follows the schema: -.. cmd:: Scheme ident := Induction for ident' Sort sort {* with ident := Induction for ident' Sort sort} +.. cmd:: Scheme @ident := Induction for @ident Sort sort {* with @ident := Induction for @ident Sort sort} where each `ident'ᵢ` is a different inductive type identifier belonging to the same package of mutual inductive definitions. This @@ -18,17 +20,18 @@ command generates the `identᵢ`s to be mutually recursive definitions. Each term `identᵢ` proves a general principle of mutual induction for objects in type `identᵢ`. -.. cmdv:: Scheme ident := Minimality for ident' Sort sort {* with ident := Minimality for ident' Sort sort} +.. cmdv:: Scheme @ident := Minimality for @ident Sort sort {* with @ident := Minimality for @ident' Sort sort} Same as before but defines a non-dependent elimination principle more natural in case of inductively defined relations. -.. cmdv:: Scheme Equality for ident +.. cmdv:: Scheme Equality for @ident + :name: Scheme Equality Tries to generate a Boolean equality and a proof of the decidability of the usual equality. If `ident` involves some other inductive types, their equality has to be defined first. -.. cmdv:: Scheme Induction for ident Sort sort {* with Induction for ident Sort sort} +.. cmdv:: Scheme Induction for @ident Sort sort {* with Induction for @ident Sort sort} If you do not provide the name of the schemes, they will be automatically computed from the sorts involved (works also with Minimality). @@ -101,26 +104,34 @@ induction for objects in type `identᵢ`. Automatic declaration of schemes ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -It is possible to deactivate the automatic declaration of the -induction principles when defining a new inductive type with the -``Unset Elimination Schemes`` command. It may be reactivated at any time with -``Set Elimination Schemes``. - -The types declared with the keywords ``Variant`` (see :ref:`TODO-1.3.3`) and ``Record`` -(see :ref:`Record Types <record-types>`) do not have an automatic declaration of the induction -principles. It can be activated with the command -``Set Nonrecursive Elimination Schemes``. It can be deactivated again with -``Unset Nonrecursive Elimination Schemes``. - -In addition, the ``Case Analysis Schemes`` flag governs the generation of -case analysis lemmas for inductive types, i.e. corresponding to the -pattern-matching term alone and without fixpoint. -You can also activate the automatic declaration of those Boolean -equalities (see the second variant of ``Scheme``) with respectively the -commands ``Set Boolean Equality Schemes`` and ``Set Decidable Equality -Schemes``. However you have to be careful with this option since Coq may -now reject well-defined inductive types because it cannot compute a -Boolean equality for them. +.. opt:: Elimination Schemes + + It is possible to deactivate the automatic declaration of the + induction principles when defining a new inductive type with the + ``Unset Elimination Schemes`` command. It may be reactivated at any time with + ``Set Elimination Schemes``. + +.. opt:: Nonrecursive Elimination Schemes + + This option controls whether types declared with the keywords :cmd:`Variant` and + :cmd:`Record` get an automatic declaration of the induction principles. + +.. opt:: Case Analysis Schemes + + This flag governs the generation of case analysis lemmas for inductive types, + i.e. corresponding to the pattern-matching term alone and without fixpoint. + +.. opt:: Boolean Equality Schemes + +.. opt:: Decidable Equality Schemes + + These flags control the automatic declaration of those Boolean equalities (see + the second variant of ``Scheme``). + +.. warning:: + + You have to be careful with this option since Coq may now reject well-defined + inductive types because it cannot compute a Boolean equality for them. .. opt:: Rewriting Schemes @@ -133,7 +144,7 @@ The ``Combined Scheme`` command is a tool for combining induction principles generated by the ``Scheme command``. Its syntax follows the schema : -.. cmd:: Combined Scheme ident from {+, ident} +.. cmd:: Combined Scheme @ident from {+, ident} where each identᵢ after the ``from`` is a different inductive principle that must belong to the same package of mutual inductive principle definitions. @@ -163,6 +174,8 @@ concluded by the conjunction of their conclusions. Check tree_forest_mutind. +.. _functional-scheme: + Generation of induction principles with ``Functional`` ``Scheme`` ----------------------------------------------------------------- @@ -172,7 +185,7 @@ generating automatically induction principles corresponding to available via ``Require Import FunInd``. Its syntax then follows the schema: -.. cmd:: Functional Scheme ident := Induction for ident' Sort sort {* with ident := Induction for ident' Sort sort} +.. cmd:: Functional Scheme @ident := Induction for ident' Sort sort {* with @ident := Induction for @ident Sort sort} where each `ident'ᵢ` is a different mutually defined function name (the names must be in the same order as when they were defined). This @@ -229,7 +242,7 @@ definition written by the user. simpl; auto with arith. Qed. - We can use directly the functional induction (:ref:`TODO-8.5.5`) tactic instead + We can use directly the functional induction (:tacn:`function induction`) tactic instead of the pattern/apply trick: .. coqtop:: all @@ -305,13 +318,15 @@ definition written by the user. .. coqtop:: all Check tree_size_ind2. + +.. _derive-inversion: Generation of inversion principles with ``Derive`` ``Inversion`` ----------------------------------------------------------------- The syntax of ``Derive`` ``Inversion`` follows the schema: -.. cmd:: Derive Inversion ident with forall (x : T), I t Sort sort +.. cmd:: Derive Inversion @ident with forall (x : T), I t Sort sort This command generates an inversion principle for the `inversion … using` tactic. Let `I` be an inductive predicate and `x` the variables occurring @@ -320,17 +335,17 @@ sort `sort` corresponding to the instance `∀ (x:T), I t` with the name `ident` in the global environment. When applied, it is equivalent to having inverted the instance with the tactic `inversion`. -.. cmdv:: Derive Inversion_clear ident with forall (x:T), I t Sort sort +.. cmdv:: Derive Inversion_clear @ident with forall (x:T), I t Sort sort When applied, it is equivalent to having inverted the instance with the tactic inversion replaced by the tactic `inversion_clear`. -.. cmdv:: Derive Dependent Inversion ident with forall (x:T), I t Sort sort +.. cmdv:: Derive Dependent Inversion @ident with forall (x:T), I t Sort sort When applied, it is equivalent to having inverted the instance with the tactic `dependent inversion`. -.. cmdv:: Derive Dependent Inversion_clear ident with forall(x:T), I t Sort sort +.. cmdv:: Derive Dependent Inversion_clear @ident with forall(x:T), I t Sort sort When applied, it is equivalent to having inverted the instance with the tactic `dependent inversion_clear`. |