diff options
Diffstat (limited to 'doc/sphinx/proof-engine')
| -rw-r--r-- | doc/sphinx/proof-engine/detailed-tactic-examples.rst | 17 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/ltac.rst | 1310 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/proof-handling.rst | 595 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/ssreflect-proof-language.rst | 372 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/tactics.rst | 1636 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/vernacular-commands.rst | 1242 |
6 files changed, 4195 insertions, 977 deletions
diff --git a/doc/sphinx/proof-engine/detailed-tactic-examples.rst b/doc/sphinx/proof-engine/detailed-tactic-examples.rst index 932f967881..84810ddba5 100644 --- a/doc/sphinx/proof-engine/detailed-tactic-examples.rst +++ b/doc/sphinx/proof-engine/detailed-tactic-examples.rst @@ -6,6 +6,8 @@ Detailed examples of tactics This chapter presents detailed examples of certain tactics, to illustrate their behavior. +.. _dependent-induction: + dependent induction ------------------- @@ -316,7 +318,7 @@ explicit proof terms: This concludes our example. -See also: The ``induction`` :ref:`TODO-9-induction`, ``case`` :ref:`TODO-9-induction` and ``inversion`` :ref:`TODO-8.14-inversion` tactics. +See also: The :tacn:`induction`, :tacn:`case`, and :tacn:`inversion` tactics. autorewrite @@ -403,6 +405,8 @@ Example 2: Mac Carthy function autorewrite with base1 using reflexivity || simpl. +.. _quote: + quote ----- @@ -544,8 +548,7 @@ Combining variables and constants ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ One can have both variables and constants in abstracts terms; for -example, this is the case for the ``ring`` tactic -:ref:`TODO-25-ringandfieldtacticfamilies`. Then one must provide to +example, this is the case for the :tacn:`ring` tactic. Then one must provide to ``quote`` a list of *constructors of constants*. For example, if the list is ``[O S]`` then closed natural numbers will be considered as constants and other terms as variables. @@ -606,7 +609,7 @@ don’t expect miracles from it! See also: comments of source file ``plugins/quote/quote.ml`` -See also: the ``ring`` tactic :ref:`TODO-25-ringandfieldtacticfamilies` +See also: the :tacn:`ring` tactic. Using the tactical language @@ -733,7 +736,7 @@ and this length is decremented for each rotation down to, but not including, 1 because for a list of length ``n``, we can make exactly ``n−1`` rotations to generate at most ``n`` distinct lists. Here, it must be noticed that we use the natural numbers of Coq for the -rotation counter. On Figure :ref:`TODO-9.1-tactic-language`, we can +rotation counter. In :ref:`ltac-syntax`, we can see that it is possible to use usual natural numbers but they are only used as arguments for primitive tactics and they cannot be handled, in particular, we cannot make computations with them. So, a natural @@ -830,7 +833,7 @@ The pattern matching on goals allows a complete and so a powerful backtracking when returning tactic values. An interesting application is the problem of deciding intuitionistic propositional logic. Considering the contraction-free sequent calculi LJT* of Roy Dyckhoff -:ref:`TODO-56-biblio`, it is quite natural to code such a tactic +:cite:`Dyc92`, it is quite natural to code such a tactic using the tactic language as shown on figures: :ref:`Deciding intuitionistic propositions (1) <decidingintuitionistic1>` and :ref:`Deciding intuitionistic propositions (2) @@ -868,7 +871,7 @@ Deciding type isomorphisms A more tricky problem is to decide equalities between types and modulo isomorphisms. Here, we choose to use the isomorphisms of the simply typed λ-calculus with Cartesian product and unit type (see, for -example, [:ref:`TODO-45`]). The axioms of this λ-calculus are given below. +example, :cite:`RC95`). The axioms of this λ-calculus are given below. .. coqtop:: in reset diff --git a/doc/sphinx/proof-engine/ltac.rst b/doc/sphinx/proof-engine/ltac.rst new file mode 100644 index 0000000000..88c1e225fd --- /dev/null +++ b/doc/sphinx/proof-engine/ltac.rst @@ -0,0 +1,1310 @@ +.. include:: ../preamble.rst +.. include:: ../replaces.rst + +.. _ltac: + +The tactic language +=================== + +This chapter gives a compact documentation of |Ltac|, the tactic language +available in |Coq|. We start by giving the syntax, and next, we present the +informal semantics. If you want to know more regarding this language and +especially about its foundations, you can refer to :cite:`Del00`. Chapter +:ref:`detailedexamplesoftactics` is devoted to giving examples of use of this +language on small but also with non-trivial problems. + +.. _ltac-syntax: + +Syntax +------ + +The syntax of the tactic language is given below. See Chapter +:ref:`gallinaspecificationlanguage` for a description of the BNF metasyntax used +in these grammar rules. Various already defined entries will be used in this +chapter: entries :token:`natural`, :token:`integer`, :token:`ident`, +:token:`qualid`, :token:`term`, :token:`cpattern` and :token:`atomic_tactic` +represent respectively the natural and integer numbers, the authorized +identificators and qualified names, Coq terms and patterns and all the atomic +tactics described in Chapter :ref:`tactics`. The syntax of :token:`cpattern` is +the same as that of terms, but it is extended with pattern matching +metavariables. In :token:`cpattern`, a pattern-matching metavariable is +represented with the syntax :g:`?id` where :g:`id` is an :token:`ident`. The +notation :g:`_` can also be used to denote metavariable whose instance is +irrelevant. In the notation :g:`?id`, the identifier allows us to keep +instantiations and to make constraints whereas :g:`_` shows that we are not +interested in what will be matched. On the right hand side of pattern-matching +clauses, the named metavariable are used without the question mark prefix. There +is also a special notation for second-order pattern-matching problems: in an +applicative pattern of the form :g:`@?id id1 … idn`, the variable id matches any +complex expression with (possible) dependencies in the variables :g:`id1 … idn` +and returns a functional term of the form :g:`fun id1 … idn => term`. + +The main entry of the grammar is :n:`@expr`. This language is used in proof +mode but it can also be used in toplevel definitions as shown below. + +.. note:: + + - The infix tacticals “… \|\| …”, “… + …”, and “… ; …” are associative. + + - In :token:`tacarg`, there is an overlap between qualid as a direct tactic + argument and :token:`qualid` as a particular case of term. The resolution is + done by first looking for a reference of the tactic language and if + it fails, for a reference to a term. To force the resolution as a + reference of the tactic language, use the form :g:`ltac:(@qualid)`. To + force the resolution as a reference to a term, use the syntax + :g:`(@qualid)`. + + - As shown by the figure, tactical ``\|\|`` binds more than the prefix + tacticals try, repeat, do and abstract which themselves bind more + than the postfix tactical “… ;[ … ]” which binds more than “… ; …”. + + For instance + + .. coqtop:: in + + try repeat tac1 || tac2; tac3; [tac31 | ... | tac3n]; tac4. + + is understood as + + .. coqtop:: in + + try (repeat (tac1 || tac2)); + ((tac3; [tac31 | ... | tac3n]); tac4). + +.. productionlist:: coq + expr : `expr` ; `expr` + : | [> `expr` | ... | `expr` ] + : | `expr` ; [ `expr` | ... | `expr` ] + : | `tacexpr3` + tacexpr3 : do (`natural` | `ident`) tacexpr3 + : | progress `tacexpr3` + : | repeat `tacexpr3` + : | try `tacexpr3` + : | once `tacexpr3` + : | exactly_once `tacexpr3` + : | timeout (`natural` | `ident`) `tacexpr3` + : | time [`string`] `tacexpr3` + : | only `selector`: `tacexpr3` + : | `tacexpr2` + tacexpr2 : `tacexpr1` || `tacexpr3` + : | `tacexpr1` + `tacexpr3` + : | tryif `tacexpr1` then `tacexpr1` else `tacexpr1` + : | `tacexpr1` + tacexpr1 : fun `name` ... `name` => `atom` + : | let [rec] `let_clause` with ... with `let_clause` in `atom` + : | match goal with `context_rule` | ... | `context_rule` end + : | match reverse goal with `context_rule` | ... | `context_rule` end + : | match `expr` with `match_rule` | ... | `match_rule` end + : | lazymatch goal with `context_rule` | ... | `context_rule` end + : | lazymatch reverse goal with `context_rule` | ... | `context_rule` end + : | lazymatch `expr` with `match_rule` | ... | `match_rule` end + : | multimatch goal with `context_rule` | ... | `context_rule` end + : | multimatch reverse goal with `context_rule` | ... | `context_rule` end + : | multimatch `expr` with `match_rule` | ... | `match_rule` end + : | abstract `atom` + : | abstract `atom` using `ident` + : | first [ `expr` | ... | `expr` ] + : | solve [ `expr` | ... | `expr` ] + : | idtac [ `message_token` ... `message_token`] + : | fail [`natural`] [`message_token` ... `message_token`] + : | fresh | fresh `string` | fresh `qualid` + : | context `ident` [`term`] + : | eval `redexpr` in `term` + : | type of `term` + : | constr : `term` + : | uconstr : `term` + : | type_term `term` + : | numgoals + : | guard `test` + : | assert_fails `tacexpr3` + : | assert_suceeds `tacexpr3` + : | `atomic_tactic` + : | `qualid` `tacarg` ... `tacarg` + : | `atom` + atom : `qualid` + : | () + : | `integer` + : | ( `expr` ) + message_token : `string` | `ident` | `integer` + tacarg : `qualid` + : | () + : | ltac : `atom` + : | `term` + let_clause : `ident` [`name` ... `name`] := `expr` + context_rule : `context_hyp`, ..., `context_hyp` |- `cpattern` => `expr` + : | `cpattern` => `expr` + : | |- `cpattern` => `expr` + : | _ => `expr` + context_hyp : `name` : `cpattern` + : | `name` := `cpattern` [: `cpattern`] + match_rule : `cpattern` => `expr` + : | context [ident] [ `cpattern` ] => `expr` + : | _ => `expr` + test : `integer` = `integer` + : | `integer` (< | <= | > | >=) `integer` + selector : [`ident`] + : | `integer` + : (`integer` | `integer` - `integer`), ..., (`integer` | `integer` - `integer`) + toplevel_selector : `selector` + : | `all` + : | `par` + +.. productionlist:: coq + top : [Local] Ltac `ltac_def` with ... with `ltac_def` + ltac_def : `ident` [`ident` ... `ident`] := `expr` + : | `qualid` [`ident` ... `ident`] ::= `expr` + +.. _ltac-semantics: + +Semantics +--------- + +Tactic expressions can only be applied in the context of a proof. The +evaluation yields either a term, an integer or a tactic. Intermediary +results can be terms or integers but the final result must be a tactic +which is then applied to the focused goals. + +There is a special case for ``match goal`` expressions of which the clauses +evaluate to tactics. Such expressions can only be used as end result of +a tactic expression (never as argument of a non recursive local +definition or of an application). + +The rest of this section explains the semantics of every construction of +|Ltac|. + +Sequence +~~~~~~~~ + +A sequence is an expression of the following form: + +.. tacn:: @expr ; @expr + :name: ltac-seq + + The expression :n:`@expr__1` is evaluated to :n:`v__1`, which must be + a tactic value. The tactic :n:`v__1` is applied to the current goal, + possibly producing more goals. Then :n:`@expr__2` is evaluated to + produce :n:`v__2`, which must be a tactic value. The tactic + :n:`v__2` is applied to all the goals produced by the prior + application. Sequence is associative. + +Local application of tactics +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Different tactics can be applied to the different goals using the +following form: + +.. tacn:: [> {*| @expr }] + :name: [> ... | ... | ... ] (dispatch) + + The expressions :n:`@expr__i` are evaluated to :n:`v__i`, for + i=0,...,n and all have to be tactics. The :n:`v__i` is applied to the + i-th goal, for =1,...,n. It fails if the number of focused goals is not + exactly n. + + .. note:: + + If no tactic is given for the i-th goal, it behaves as if the tactic idtac + were given. For instance, ``[> | auto]`` is a shortcut for ``[> idtac | auto + ]``. + + .. tacv:: [> {*| @expr} | @expr .. | {*| @expr}] + + In this variant, token:`expr` is used for each goal coming after those + covered by the first list of :n:`@expr` but before those coevered by the + last list of :n:`@expr`. + + .. tacv:: [> {*| @expr} | .. | {*| @expr}] + + In this variant, idtac is used for the goals not covered by the two lists of + :n:`@expr`. + + .. tacv:: [> @expr .. ] + + In this variant, the tactic :n:`@expr` is applied independently to each of + the goals, rather than globally. In particular, if there are no goal, the + tactic is not run at all. A tactic which expects multiple goals, such as + ``swap``, would act as if a single goal is focused. + + .. tacv:: expr ; [{*| @expr}] + + This variant of local tactic application is paired with a sequence. In this + variant, there must be as many :n:`@expr` in the list as goals generated + by the application of the first :n:`@expr` to each of the individual goals + independently. All the above variants work in this form too. + Formally, :n:`@expr ; [ ... ]` is equivalent to :n:`[> @expr ; [> ... ] .. ]`. + +.. _goal-selectors: + +Goal selectors +~~~~~~~~~~~~~~ + +We can restrict the application of a tactic to a subset of the currently +focused goals with: + +.. tacn:: @toplevel_selector : @expr + :name: ... : ... (goal selector) + + We can also use selectors as a tactical, which allows to use them nested + in a tactic expression, by using the keyword ``only``: + + .. tacv:: only selector : expr + :name: only ... : ... + + When selecting several goals, the tactic expr is applied globally to all + selected goals. + + .. tacv:: [@ident] : @expr + + In this variant, :n:`@expr` is applied locally to a goal previously named + by the user (see :ref:`existential-variables`). + + .. tacv:: @num : @expr + + In this variant, :n:`@expr` is applied locally to the :token:`num`-th goal. + + .. tacv:: {+, @num-@num} : @expr + + In this variant, :n:`@expr` is applied globally to the subset of goals + described by the given ranges. You can write a single ``n`` as a shortcut + for ``n-n`` when specifying multiple ranges. + + .. tacv:: all: @expr + :name: all: ... + + In this variant, :n:`@expr` is applied to all focused goals. ``all:`` can only + be used at the toplevel of a tactic expression. + + .. tacv:: !: @expr + + In this variant, if exactly one goal is focused :n:`expr` is + applied to it. Otherwise the tactical fails. ``!:`` can only be + used at the toplevel of a tactic expression. + + .. tacv:: par: @expr + :name: par: ... + + In this variant, :n:`@expr` is applied to all focused goals in parallel. + The number of workers can be controlled via the command line option + ``-async-proofs-tac-j`` taking as argument the desired number of workers. + Limitations: ``par:`` only works on goals containing no existential + variables and :n:`@expr` must either solve the goal completely or do + nothing (i.e. it cannot make some progress). ``par:`` can only be used at + the toplevel of a tactic expression. + + .. exn:: No such goal. + :name: No such goal. (Goal selector) + + .. TODO change error message index entry + +For loop +~~~~~~~~ + +There is a for loop that repeats a tactic :token:`num` times: + +.. tacn:: do @num @expr + :name: do + + :n:`@expr` is evaluated to ``v`` which must be a tactic value. This tactic + value ``v`` is applied :token:`num` times. Supposing :token:`num` > 1, after the + first application of ``v``, ``v`` is applied, at least once, to the generated + subgoals and so on. It fails if the application of ``v`` fails before the num + applications have been completed. + +Repeat loop +~~~~~~~~~~~ + +We have a repeat loop with: + +.. tacn:: repeat @expr + :name: repeat + + :n:`@expr` is evaluated to ``v``. If ``v`` denotes a tactic, this tactic is + applied to each focused goal independently. If the application succeeds, the + tactic is applied recursively to all the generated subgoals until it eventually + fails. The recursion stops in a subgoal when the tactic has failed *to make + progress*. The tactic :n:`repeat @expr` itself never fails. + +Error catching +~~~~~~~~~~~~~~ + +We can catch the tactic errors with: + +.. tacn:: try @expr + :name: try + + :n:`@expr` is evaluated to ``v`` which must be a tactic value. The tactic + value ``v`` is applied to each focused goal independently. If the application of + ``v`` fails in a goal, it catches the error and leaves the goal unchanged. If the + level of the exception is positive, then the exception is re-raised with its + level decremented. + +Detecting progress +~~~~~~~~~~~~~~~~~~ + +We can check if a tactic made progress with: + +.. tacn:: progress expr + :name: progress + + :n:`@expr` is evaluated to v which must be a tactic value. The tactic value ``v`` + is applied to each focued subgoal independently. If the application of ``v`` + to one of the focused subgoal produced subgoals equal to the initial + goals (up to syntactical equality), then an error of level 0 is raised. + + .. exn:: Failed to progress. + +Backtracking branching +~~~~~~~~~~~~~~~~~~~~~~ + +We can branch with the following structure: + +.. tacn:: @expr__1 + @expr__2 + :name: + (backtracking branching) + + :n:`@expr__1` and :n:`@expr__2` are evaluated respectively to :n:`v__1` and + :n:`v__2` which must be tactic values. The tactic value :n:`v__1` is applied to + each focused goal independently and if it fails or a later tactic fails, then + the proof backtracks to the current goal and :n:`v__2` is applied. + + Tactics can be seen as having several successes. When a tactic fails it + asks for more successes of the prior tactics. + :n:`@expr__1 + @expr__2` has all the successes of :n:`v__1` followed by all the + successes of :n:`v__2`. Algebraically, + :n:`(@expr__1 + @expr__2); @expr__3 = (@expr__1; @expr__3) + (@expr__2; @expr__3)`. + + Branching is left-associative. + +First tactic to work +~~~~~~~~~~~~~~~~~~~~ + +Backtracking branching may be too expensive. In this case we may +restrict to a local, left biased, branching and consider the first +tactic to work (i.e. which does not fail) among a panel of tactics: + +.. tacn:: first [{*| @expr}] + :name: first + + The :n:`@expr__i` are evaluated to :n:`v__i` and :n:`v__i` must be + tactic values, for i=1,...,n. Supposing n>1, it applies, in each focused + goal independently, :n:`v__1`, if it works, it stops otherwise it + tries to apply :n:`v__2` and so on. It fails when there is no + applicable tactic. In other words, + :n:`first [:@expr__1 | ... | @expr__n]` behaves, in each goal, as the the first + :n:`v__i` to have *at least* one success. + + .. exn:: No applicable tactic. + + .. tacv:: first @expr + + This is an |Ltac| alias that gives a primitive access to the first + tactical as a |Ltac| definition without going through a parsing rule. It + expects to be given a list of tactics through a ``Tactic Notation``, + allowing to write notations of the following form: + + .. example:: + + .. coqtop:: in + + Tactic Notation "foo" tactic_list(tacs) := first tacs. + +Left-biased branching +~~~~~~~~~~~~~~~~~~~~~ + +Yet another way of branching without backtracking is the following +structure: + +.. tacn:: @expr__1 || @expr__2 + :name: || (left-biased branching) + + :n:`@expr__1` and :n:`@expr__2` are evaluated respectively to :n:`v__1` and + :n:`v__2` which must be tactic values. The tactic value :n:`v__1` is + applied in each subgoal independently and if it fails *to progress* then + :n:`v__2` is applied. :n:`@expr__1 || @expr__2` is + equivalent to :n:`first [ progress @expr__1 | @expr__2 ]` (except that + if it fails, it fails like :n:`v__2`). Branching is left-associative. + +Generalized biased branching +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +The tactic + +.. tacn:: tryif @expr__1 then @expr__2 else @expr__3 + :name: tryif + + is a generalization of the biased-branching tactics above. The + expression :n:`@expr__1` is evaluated to :n:`v__1`, which is then + applied to each subgoal independently. For each goal where :n:`v__1` + succeeds at least once, :n:`@expr__2` is evaluated to :n:`v__2` which + is then applied collectively to the generated subgoals. The :n:`v__2` + tactic can trigger backtracking points in :n:`v__1`: where :n:`v__1` + succeeds at least once, + :n:`tryif @expr__1 then @expr__2 else @expr__3` is equivalent to + :n:`v__1; v__2`. In each of the goals where :n:`v__1` does not succeed at least + once, :n:`@expr__3` is evaluated in :n:`v__3` which is is then applied to the + goal. + +Soft cut +~~~~~~~~ + +Another way of restricting backtracking is to restrict a tactic to a +single success *a posteriori*: + +.. tacn:: once @expr + :name: once + + :n:`@expr` is evaluated to ``v`` which must be a tactic value. The tactic value + ``v`` is applied but only its first success is used. If ``v`` fails, + :n:`once @expr` fails like ``v``. If ``v`` has a least one success, + :n:`once @expr` succeeds once, but cannot produce more successes. + +Checking the successes +~~~~~~~~~~~~~~~~~~~~~~ + +Coq provides an experimental way to check that a tactic has *exactly +one* success: + +.. tacn:: exactly_once @expr + :name: exactly_once + + :n:`@expr` is evaluated to ``v`` which must be a tactic value. The tactic value + ``v`` is applied if it has at most one success. If ``v`` fails, + :n:`exactly_once @expr` fails like ``v``. If ``v`` has a exactly one success, + :n:`exactly_once @expr` succeeds like ``v``. If ``v`` has two or more + successes, exactly_once expr fails. + + .. warning:: + + The experimental status of this tactic pertains to the fact if ``v`` + performs side effects, they may occur in a unpredictable way. Indeed, + normally ``v`` would only be executed up to the first success until + backtracking is needed, however exactly_once needs to look ahead to see + whether a second success exists, and may run further effects + immediately. + + .. exn:: This tactic has more than one success. + +Checking the failure +~~~~~~~~~~~~~~~~~~~~ + +Coq provides a derived tactic to check that a tactic *fails*: + +.. tacn:: assert_fails @expr + :name: assert_fails + + This behaves like :n:`tryif @expr then fail 0 tac "succeeds" else idtac`. + +Checking the success +~~~~~~~~~~~~~~~~~~~~ + +Coq provides a derived tactic to check that a tactic has *at least one* +success: + +.. tacn:: assert_succeeds @expr + :name: assert_suceeds + + This behaves like + :n:`tryif (assert_fails tac) then fail 0 tac "fails" else idtac`. + +Solving +~~~~~~~ + +We may consider the first to solve (i.e. which generates no subgoal) +among a panel of tactics: + +.. tacn:: solve [{*| @expr}] + :name: solve + + The :n:`@expr__i` are evaluated to :n:`v__i` and :n:`v__i` must be + tactic values, for i=1,...,n. Supposing n>1, it applies :n:`v__1` to + each goal independently, if it doesn’t solve the goal then it tries to + apply :n:`v__2` and so on. It fails if there is no solving tactic. + + .. exn:: Cannot solve the goal. + + .. tacv:: solve @expr + + This is an |Ltac| alias that gives a primitive access to the :n:`solve:` + tactical. See the :n:`first` tactical for more information. + +Identity +~~~~~~~~ + +The constant :n:`idtac` is the identity tactic: it leaves any goal unchanged but +it appears in the proof script. + +.. tacn:: idtac {* message_token} + :name: idtac + + This prints the given tokens. Strings and integers are printed + literally. If a (term) variable is given, its contents are printed. + +Failing +~~~~~~~ + +.. tacn:: fail + :name: fail + + This is the always-failing tactic: it does not solve any + goal. It is useful for defining other tacticals since it can be caught by + :tacn:`try`, :tacn:`repeat`, :tacn:`match goal`, or the branching tacticals. The + :tacn:`fail` tactic will, however, succeed if all the goals have already been + solved. + + .. tacv:: fail @num + + The number is the failure level. If no level is specified, it defaults to 0. + The level is used by :tacn:`try`, :tacn:`repeat`, :tacn:`match goal` and the branching + tacticals. If 0, it makes :tacn:`match goal` considering the next clause + (backtracking). If non zero, the current :tacn:`match goal` block, :tacn:`try`, + :tacn:`repeat`, or branching command is aborted and the level is decremented. In + the case of :n:`+`, a non-zero level skips the first backtrack point, even if + the call to :n:`fail @num` is not enclosed in a :n:`+` command, + respecting the algebraic identity. + + .. tacv:: fail {* message_token} + + The given tokens are used for printing the failure message. + + .. tacv:: fail @num {* message_token} + + This is a combination of the previous variants. + + .. tacv:: gfail + :name: gfail + + This variant fails even if there are no goals left. + + .. tacv:: gfail {* message_token} + + .. tacv:: gfail @num {* message_token} + + These variants fail with an error message or an error level even if + there are no goals left. Be careful however if Coq terms have to be + printed as part of the failure: term construction always forces the + tactic into the goals, meaning that if there are no goals when it is + evaluated, a tactic call like :n:`let x:=H in fail 0 x` will succeed. + + .. exn:: Tactic Failure message (level @num). + +Timeout +~~~~~~~ + +We can force a tactic to stop if it has not finished after a certain +amount of time: + +.. tacn:: timeout @num @expr + :name: timeout + + :n:`@expr` is evaluated to ``v`` which must be a tactic value. The tactic value + ``v`` is applied normally, except that it is interrupted after :n:`@num` seconds + if it is still running. In this case the outcome is a failure. + + .. warning:: + + For the moment, timeout is based on elapsed time in seconds, + which is very machine-dependent: a script that works on a quick machine + may fail on a slow one. The converse is even possible if you combine a + timeout with some other tacticals. This tactical is hence proposed only + for convenience during debug or other development phases, we strongly + advise you to not leave any timeout in final scripts. Note also that + this tactical isn’t available on the native Windows port of Coq. + +Timing a tactic +~~~~~~~~~~~~~~~ + +A tactic execution can be timed: + +.. tacn:: time @string @expr + :name: time + + evaluates :n:`@expr` and displays the time the tactic expression ran, whether it + fails or successes. In case of several successes, the time for each successive + runs is displayed. Time is in seconds and is machine-dependent. The :n:`@string` + argument is optional. When provided, it is used to identify this particular + occurrence of time. + +Timing a tactic that evaluates to a term +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Tactic expressions that produce terms can be timed with the experimental +tactic + +.. tacn:: time_constr expr + :name: time_constr + + which evaluates :n:`@expr ()` and displays the time the tactic expression + evaluated, assuming successful evaluation. Time is in seconds and is + machine-dependent. + + This tactic currently does not support nesting, and will report times + based on the innermost execution. This is due to the fact that it is + implemented using the tactics + + .. tacn:: restart_timer @string + :name: restart_timer + + and + + .. tacn:: finish_timing {? @string} @string + :name: finish_timing + + which (re)set and display an optionally named timer, respectively. The + parenthesized string argument to :n:`finish_timing` is also optional, and + determines the label associated with the timer for printing. + + By copying the definition of :n:`time_constr` from the standard library, + users can achive support for a fixed pattern of nesting by passing + different :n:`@string` parameters to :n:`restart_timer` and :n:`finish_timing` + at each level of nesting. + + .. example:: + + .. coqtop:: all + + Ltac time_constr1 tac := + let eval_early := match goal with _ => restart_timer "(depth 1)" end in + let ret := tac () in + let eval_early := match goal with _ => finish_timing ( "Tactic evaluation" ) "(depth 1)" end in + ret. + + Goal True. + let v := time_constr + ltac:(fun _ => + let x := time_constr1 ltac:(fun _ => constr:(10 * 10)) in + let y := time_constr1 ltac:(fun _ => eval compute in x) in + y) in + pose v. + Abort. + +Local definitions +~~~~~~~~~~~~~~~~~ + +Local definitions can be done as follows: + +.. tacn:: let @ident__1 := @expr__1 {* with @ident__i := @expr__i} in @expr + + each :n:`@expr__i` is evaluated to :n:`v__i`, then, :n:`@expr` is evaluated + by substituting :n:`v__i` to each occurrence of :n:`@ident__i`, for + i=1,...,n. There is no dependencies between the :n:`@expr__i` and the + :n:`@ident__i`. + + Local definitions can be recursive by using :n:`let rec` instead of :n:`let`. + In this latter case, the definitions are evaluated lazily so that the rec + keyword can be used also in non recursive cases so as to avoid the eager + evaluation of local definitions. + + .. but rec changes the binding!! + +Application +~~~~~~~~~~~ + +An application is an expression of the following form: + +.. tacn:: @qualid {+ @tacarg} + + The reference :n:`@qualid` must be bound to some defined tactic definition + expecting at least as many arguments as the provided :n:`tacarg`. The + expressions :n:`@expr__i` are evaluated to :n:`v__i`, for i=1,...,n. + + .. what expressions ?? + +Function construction +~~~~~~~~~~~~~~~~~~~~~ + +A parameterized tactic can be built anonymously (without resorting to +local definitions) with: + +.. tacn:: fun {+ @ident} => @expr + + Indeed, local definitions of functions are a syntactic sugar for binding + a :n:`fun` tactic to an identifier. + +Pattern matching on terms +~~~~~~~~~~~~~~~~~~~~~~~~~ + +We can carry out pattern matching on terms with: + +.. tacn:: match @expr with {+| @cpattern__i => @expr__i} end + + The expression :n:`@expr` is evaluated and should yield a term which is + matched against :n:`cpattern__1`. The matching is non-linear: if a + metavariable occurs more than once, it should match the same expression + every time. It is first-order except on the variables of the form :n:`@?id` + that occur in head position of an application. For these variables, the + matching is second-order and returns a functional term. + + Alternatively, when a metavariable of the form :n:`?id` occurs under binders, + say :n:`x__1, …, x__n` and the expression matches, the + metavariable is instantiated by a term which can then be used in any + context which also binds the variables :n:`x__1, …, x__n` with + same types. This provides with a primitive form of matching under + context which does not require manipulating a functional term. + + If the matching with :n:`@cpattern__1` succeeds, then :n:`@expr__1` is + evaluated into some value by substituting the pattern matching + instantiations to the metavariables. If :n:`@expr__1` evaluates to a + tactic and the match expression is in position to be applied to a goal + (e.g. it is not bound to a variable by a :n:`let in`), then this tactic is + applied. If the tactic succeeds, the list of resulting subgoals is the + result of the match expression. If :n:`@expr__1` does not evaluate to a + tactic or if the match expression is not in position to be applied to a + goal, then the result of the evaluation of :n:`@expr__1` is the result + of the match expression. + + If the matching with :n:`@cpattern__1` fails, or if it succeeds but the + evaluation of :n:`@expr__1` fails, or if the evaluation of + :n:`@expr__1` succeeds but returns a tactic in execution position whose + execution fails, then :n:`cpattern__2` is used and so on. The pattern + :n:`_` matches any term and shunts all remaining patterns if any. If all + clauses fail (in particular, there is no pattern :n:`_`) then a + no-matching-clause error is raised. + + Failures in subsequent tactics do not cause backtracking to select new + branches or inside the right-hand side of the selected branch even if it + has backtracking points. + + .. exn:: No matching clauses for match. + + No pattern can be used and, in particular, there is no :n:`_` pattern. + + .. exn:: Argument of match does not evaluate to a term. + + This happens when :n:`@expr` does not denote a term. + + .. tacv:: multimatch @expr with {+| @cpattern__i => @expr__i} end + + Using multimatch instead of match will allow subsequent tactics to + backtrack into a right-hand side tactic which has backtracking points + left and trigger the selection of a new matching branch when all the + backtracking points of the right-hand side have been consumed. + + The syntax :n:`match …` is, in fact, a shorthand for :n:`once multimatch …`. + + .. tacv:: lazymatch @expr with {+| @cpattern__i => @expr__i} end + + Using lazymatch instead of match will perform the same pattern + matching procedure but will commit to the first matching branch + rather than trying a new matching if the right-hand side fails. If + the right-hand side of the selected branch is a tactic with + backtracking points, then subsequent failures cause this tactic to + backtrack. + + .. tacv:: context @ident [@cpattern] + + This special form of patterns matches any term with a subterm matching + cpattern. If there is a match, the optional :n:`@ident` is assigned the "matched + context", i.e. the initial term where the matched subterm is replaced by a + hole. The example below will show how to use such term contexts. + + If the evaluation of the right-hand-side of a valid match fails, the next + matching subterm is tried. If no further subterm matches, the next clause + is tried. Matching subterms are considered top-bottom and from left to + right (with respect to the raw printing obtained by setting option + :opt:`Printing All`). + + .. example:: + + .. coqtop:: all + + Ltac f x := + match x with + context f [S ?X] => + idtac X; (* To display the evaluation order *) + assert (p := eq_refl 1 : X=1); (* To filter the case X=1 *) + let x:= context f[O] in assert (x=O) (* To observe the context *) + end. + Goal True. + f (3+4). + +.. _ltac-match-goal: + +Pattern matching on goals +~~~~~~~~~~~~~~~~~~~~~~~~~ + +We can make pattern matching on goals using the following expression: + +.. we should provide the full grammar here + +.. tacn:: match goal with {+| {+ hyp} |- @cpattern => @expr } | _ => @expr end + :name: match goal + + If each hypothesis pattern :n:`hyp`\ :sub:`1,i`, with i=1,...,m\ :sub:`1` is + matched (non-linear first-order unification) by an hypothesis of the + goal and if :n:`cpattern_1` is matched by the conclusion of the goal, + then :n:`@expr__1` is evaluated to :n:`v__1` by substituting the + pattern matching to the metavariables and the real hypothesis names + bound to the possible hypothesis names occurring in the hypothesis + patterns. If :n:`v__1` is a tactic value, then it is applied to the + goal. If this application fails, then another combination of hypotheses + is tried with the same proof context pattern. If there is no other + combination of hypotheses then the second proof context pattern is tried + and so on. If the next to last proof context pattern fails then + the last :n:`@expr` is evaluated to :n:`v` and :n:`v` is + applied. Note also that matching against subterms (using the :n:`context + @ident [ @cpattern ]`) is available and is also subject to yielding several + matchings. + + Failures in subsequent tactics do not cause backtracking to select new + branches or combinations of hypotheses, or inside the right-hand side of + the selected branch even if it has backtracking points. + + .. exn:: No matching clauses for match goal. + + No clause succeeds, i.e. all matching patterns, if any, fail at the + application of the right-hand-side. + + .. note:: + + It is important to know that each hypothesis of the goal can be matched + by at most one hypothesis pattern. The order of matching is the + following: hypothesis patterns are examined from the right to the left + (i.e. hyp\ :sub:`i,m`\ :sub:`i`` before hyp\ :sub:`i,1`). For each + hypothesis pattern, the goal hypothesis are matched in order (fresher + hypothesis first), but it possible to reverse this order (older first) + with the :n:`match reverse goal with` variant. + + .. tacv:: multimatch goal with {+| {+ hyp} |- @cpattern => @expr } | _ => @expr end + + Using :n:`multimatch` instead of :n:`match` will allow subsequent tactics + to backtrack into a right-hand side tactic which has backtracking points + left and trigger the selection of a new matching branch or combination of + hypotheses when all the backtracking points of the right-hand side have + been consumed. + + The syntax :n:`match [reverse] goal …` is, in fact, a shorthand for + :n:`once multimatch [reverse] goal …`. + + .. tacv:: lazymatch goal with {+| {+ hyp} |- @cpattern => @expr } | _ => @expr end + + Using lazymatch instead of match will perform the same pattern matching + procedure but will commit to the first matching branch with the first + matching combination of hypotheses rather than trying a new matching if + the right-hand side fails. If the right-hand side of the selected branch + is a tactic with backtracking points, then subsequent failures cause + this tactic to backtrack. + +Filling a term context +~~~~~~~~~~~~~~~~~~~~~~ + +The following expression is not a tactic in the sense that it does not +produce subgoals but generates a term to be used in tactic expressions: + +.. tacn:: context @ident [@expr] + + :n:`@ident` must denote a context variable bound by a context pattern of a + match expression. This expression evaluates replaces the hole of the + value of :n:`@ident` by the value of :n:`@expr`. + + .. exn:: Not a context variable. + +Generating fresh hypothesis names +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Tactics sometimes have to generate new names for hypothesis. Letting the +system decide a name with the intro tactic is not so good since it is +very awkward to retrieve the name the system gave. The following +expression returns an identifier: + +.. tacn:: fresh {* component} + + It evaluates to an identifier unbound in the goal. This fresh identifier + is obtained by concatenating the value of the :n:`@component`s (each of them + is, either a :n:`@qualid` which has to refer to a (unqualified) name, or + directly a name denoted by a :n:`@string`). + + .. I don't understand this component thing. Couldn't we give the grammar? + + If the resulting name is already used, it is padded with a number so that it + becomes fresh. If no component is given, the name is a fresh derivative of + the name ``H``. + +Computing in a constr +~~~~~~~~~~~~~~~~~~~~~ + +Evaluation of a term can be performed with: + +.. tacn:: eval @redexpr in @term + + where :n:`@redexpr` is a reduction tactic among :tacn:`red`, :tacn:`hnf`, + :tacn:`compute`, :tacn:`simpl`, :tacn:`cbv`, :tacn:`lazy`, :tacn:`unfold`, + :tacn:`fold`, :tacn:`pattern`. + +Recovering the type of a term +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +The following returns the type of term: + +.. tacn:: type of @term + +Manipulating untyped terms +~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. tacn:: uconstr : @term + + The terms built in |Ltac| are well-typed by default. It may not be + appropriate for building large terms using a recursive |Ltac| function: the + term has to be entirely type checked at each step, resulting in potentially + very slow behavior. It is possible to build untyped terms using |Ltac| with + the :n:`uconstr : @term` syntax. + +.. tacn:: type_term @term + + An untyped term, in |Ltac|, can contain references to hypotheses or to + |Ltac| variables containing typed or untyped terms. An untyped term can be + type-checked using the function type_term whose argument is parsed as an + untyped term and returns a well-typed term which can be used in tactics. + +Untyped terms built using :n:`uconstr :` can also be used as arguments to the +:tacn:`refine` tactic. In that case the untyped term is type +checked against the conclusion of the goal, and the holes which are not solved +by the typing procedure are turned into new subgoals. + +Counting the goals +~~~~~~~~~~~~~~~~~~ + +.. tacn:: numgoals + + The number of goals under focus can be recovered using the :n:`numgoals` + function. Combined with the guard command below, it can be used to + branch over the number of goals produced by previous tactics. + + .. example:: + + .. coqtop:: in + + Ltac pr_numgoals := let n := numgoals in idtac "There are" n "goals". + + Goal True /\ True /\ True. + split;[|split]. + + .. coqtop:: all + + all:pr_numgoals. + +Testing boolean expressions +~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. tacn:: guard @test + :name: guard + + The :tacn:`guard` tactic tests a boolean expression, and fails if the expression + evaluates to false. If the expression evaluates to true, it succeeds + without affecting the proof. + + The accepted tests are simple integer comparisons. + + .. example:: + + .. coqtop:: in + + Goal True /\ True /\ True. + split;[|split]. + + .. coqtop:: all + + all:let n:= numgoals in guard n<4. + Fail all:let n:= numgoals in guard n=2. + + .. exn:: Condition not satisfied. + +Proving a subgoal as a separate lemma +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. tacn:: abstract @expr + :name: abstract + + From the outside, :n:`abstract @expr` is the same as :n:`solve @expr`. + Internally it saves an auxiliary lemma called ``ident_subproofn`` where + ``ident`` is the name of the current goal and ``n`` is chosen so that this is + a fresh name. Such an auxiliary lemma is inlined in the final proof term. + + This tactical is useful with tactics such as :tacn:`omega` or + :tacn:`discriminate` that generate huge proof terms. With that tool the user + can avoid the explosion at time of the Save command without having to cut + manually the proof in smaller lemmas. + + It may be useful to generate lemmas minimal w.r.t. the assumptions they + depend on. This can be obtained thanks to the option below. + + .. tacv:: abstract @expr using @ident + + Give explicitly the name of the auxiliary lemma. + + .. warning:: + + Use this feature at your own risk; explicitly named and reused subterms + don’t play well with asynchronous proofs. + + .. tacv:: transparent_abstract @expr + :name: transparent_abstract + + Save the subproof in a transparent lemma rather than an opaque one. + + .. warning:: + + Use this feature at your own risk; building computationally relevant + terms with tactics is fragile. + + .. tacv:: transparent_abstract @expr using @ident + + Give explicitly the name of the auxiliary transparent lemma. + + .. warning:: + + Use this feature at your own risk; building computationally relevant terms + with tactics is fragile, and explicitly named and reused subterms + don’t play well with asynchronous proofs. + + .. exn:: Proof is not complete. + :name: Proof is not complete. (abstract) + +Tactic toplevel definitions +--------------------------- + +Defining |Ltac| functions +~~~~~~~~~~~~~~~~~~~~~~~~~ + +Basically, |Ltac| toplevel definitions are made as follows: + +.. cmd:: Ltac @ident {* @ident} := @expr + + This defines a new |Ltac| function that can be used in any tactic + script or new |Ltac| toplevel definition. + + .. note:: + + The preceding definition can equivalently be written: + + :n:`Ltac @ident := fun {+ @ident} => @expr` + + Recursive and mutual recursive function definitions are also possible + with the syntax: + + .. cmdv:: Ltac @ident {* @ident} {* with @ident {* @ident}} := @expr + + It is also possible to *redefine* an existing user-defined tactic using the syntax: + + .. cmdv:: Ltac @qualid {* @ident} ::= @expr + + A previous definition of qualid must exist in the environment. The new + definition will always be used instead of the old one and it goes across + module boundaries. + + If preceded by the keyword Local the tactic definition will not be + exported outside the current module. + +Printing |Ltac| tactics +~~~~~~~~~~~~~~~~~~~~~~~ + +.. cmd:: Print Ltac @qualid + + Defined |Ltac| functions can be displayed using this command. + +.. cmd:: Print Ltac Signatures + + This command displays a list of all user-defined tactics, with their arguments. + +Debugging |Ltac| tactics +------------------------ + +Info trace +~~~~~~~~~~ + +.. cmd:: Info @num @expr + :name: Info + + This command can be used to print the trace of the path eventually taken by an + |Ltac| script. That is, the list of executed tactics, discarding + all the branches which have failed. To that end the :cmd:`Info` command can be + used with the following syntax. + + + The number :n:`@num` is the unfolding level of tactics in the trace. At level + 0, the trace contains a sequence of tactics in the actual script, at level 1, + the trace will be the concatenation of the traces of these tactics, etc… + + .. example:: + + .. coqtop:: in reset + + Ltac t x := exists x; reflexivity. + Goal exists n, n=0. + + .. coqtop:: all + + Info 0 t 1||t 0. + + .. coqtop:: in + + Undo. + + .. coqtop:: all + + Info 1 t 1||t 0. + + The trace produced by :cmd:`Info` tries its best to be a reparsable + |Ltac| script, but this goal is not achievable in all generality. + So some of the output traces will contain oddities. + + As an additional help for debugging, the trace produced by :cmd:`Info` contains + (in comments) the messages produced by the :tacn:`idtac` tactical at the right + position in the script. In particular, the calls to idtac in branches which failed are + not printed. + + .. opt:: Info Level @num + + This option is an alternative to the :cmd:`Info` command. + + This will automatically print the same trace as :n:`Info @num` at each + tactic call. The unfolding level can be overridden by a call to the + :cmd:`Info` command. + +Interactive debugger +~~~~~~~~~~~~~~~~~~~~ + +.. opt:: Ltac Debug + + This option governs the step-by-step debugger that comes with the |Ltac| interpreter + +When the debugger is activated, it stops at every step of the evaluation of +the current |Ltac| expression and it prints information on what it is doing. +The debugger stops, prompting for a command which can be one of the +following: + ++-----------------+-----------------------------------------------+ +| simple newline: | go to the next step | ++-----------------+-----------------------------------------------+ +| h: | get help | ++-----------------+-----------------------------------------------+ +| x: | exit current evaluation | ++-----------------+-----------------------------------------------+ +| s: | continue current evaluation without stopping | ++-----------------+-----------------------------------------------+ +| r n: | advance n steps further | ++-----------------+-----------------------------------------------+ +| r string: | advance up to the next call to “idtac string” | ++-----------------+-----------------------------------------------+ + +A non-interactive mode for the debugger is available via the option: + +.. opt:: Ltac Batch Debug + + This option has the effect of presenting a newline at every prompt, when + the debugger is on. The debug log thus created, which does not require + user input to generate when this option is set, can then be run through + external tools such as diff. + +Profiling |Ltac| tactics +~~~~~~~~~~~~~~~~~~~~~~~~ + +It is possible to measure the time spent in invocations of primitive +tactics as well as tactics defined in |Ltac| and their inner +invocations. The primary use is the development of complex tactics, +which can sometimes be so slow as to impede interactive usage. The +reasons for the performence degradation can be intricate, like a slowly +performing |Ltac| match or a sub-tactic whose performance only +degrades in certain situations. The profiler generates a call tree and +indicates the time spent in a tactic depending its calling context. Thus +it allows to locate the part of a tactic definition that contains the +performance bug. + +.. opt:: Ltac Profiling + + This option enables and disables the profiler. + +.. cmd:: Show Ltac Profile + + Prints the profile + + .. cmdv:: Show Ltac Profile @string + + Prints a profile for all tactics that start with :n:`@string`. Append a period + (.) to the string if you only want exactly that name. + +.. cmd:: Reset Ltac Profile + + Resets the profile, that is, deletes all accumulated information. + + .. warning:: + + Backtracking across a :cmd:`Reset Ltac Profile` will not restore the information. + +.. coqtop:: reset in + + Require Import Coq.omega.Omega. + + Ltac mytauto := tauto. + Ltac tac := intros; repeat split; omega || mytauto. + + Notation max x y := (x + (y - x)) (only parsing). + + Goal forall x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z, + max x (max y z) = max (max x y) z /\ max x (max y z) = max (max x y) z + /\ (A /\ B /\ C /\ D /\ E /\ F /\ G /\ H /\ I /\ J /\ K /\ L /\ M /\ N /\ O /\ P /\ Q /\ R /\ S /\ T /\ U /\ V /\ W /\ X /\ Y /\ Z + -> Z /\ Y /\ X /\ W /\ V /\ U /\ T /\ S /\ R /\ Q /\ P /\ O /\ N /\ M /\ L /\ K /\ J /\ I /\ H /\ G /\ F /\ E /\ D /\ C /\ B /\ A). + Proof. + +.. coqtop:: all + + Set Ltac Profiling. + tac. + Show Ltac Profile. + Show Ltac Profile "omega". + +.. coqtop:: in + + Abort. + Unset Ltac Profiling. + +.. tacn:: start ltac profiling + :name: start ltac profiling + + This tactic behaves like :tacn:`idtac` but enables the profiler. + +.. tacn:: stop ltac profiling + :name: stop ltac profiling + + Similarly to :tacn:`start ltac profiling`, this tactic behaves like + :tacn:`idtac`. Together, they allow you to exclude parts of a proof script + from profiling. + +.. tacn:: reset ltac profile + :name: reset ltac profile + + This tactic behaves like the corresponding vernacular command + and allow displaying and resetting the profile from tactic scripts for + benchmarking purposes. + +.. tacn:: show ltac profile + :name: show ltac profile + + This tactic behaves like the corresponding vernacular command + and allow displaying and resetting the profile from tactic scripts for + benchmarking purposes. + +.. tacn:: show ltac profile @string + :name: show ltac profile + + This tactic behaves like the corresponding vernacular command + and allow displaying and resetting the profile from tactic scripts for + benchmarking purposes. + +You can also pass the ``-profile-ltac`` command line option to ``coqc``, which +turns the :opt:`Ltac Profiling` option on at the beginning of each document, +and performs a :cmd:`Show Ltac Profile` at the end. + +.. warning:: + + Note that the profiler currently does not handle backtracking into + multi-success tactics, and issues a warning to this effect in many cases + when such backtracking occurs. + +Run-time optimization tactic +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. tacn:: optimize_heap + :name: optimize_heap + +This tactic behaves like :n:`idtac`, except that running it compacts the +heap in the OCaml run-time system. It is analogous to the Vernacular +command :cmd:`Optimize Heap`. diff --git a/doc/sphinx/proof-engine/proof-handling.rst b/doc/sphinx/proof-engine/proof-handling.rst new file mode 100644 index 0000000000..eba0db3ff5 --- /dev/null +++ b/doc/sphinx/proof-engine/proof-handling.rst @@ -0,0 +1,595 @@ +.. include:: ../replaces.rst +.. _proofhandling: + +------------------- + Proof handling +------------------- + +In |Coq|’s proof editing mode all top-level commands documented in +Chapter :ref:`vernacularcommands` remain available and the user has access to specialized +commands dealing with proof development pragmas documented in this +section. They can also use some other specialized commands called +*tactics*. They are the very tools allowing the user to deal with +logical reasoning. They are documented in Chapter :ref:`tactics`. + +Coq user interfaces usually have a way of marking whether the user has +switched to proof editing mode. For instance, in coqtop the prompt ``Coq <`` is changed into +:n:`@ident <` where :token:`ident` is the declared name of the theorem currently edited. + +At each stage of a proof development, one has a list of goals to +prove. Initially, the list consists only in the theorem itself. After +having applied some tactics, the list of goals contains the subgoals +generated by the tactics. + +To each subgoal is associated a number of hypotheses called the *local context* +of the goal. Initially, the local context contains the local variables and +hypotheses of the current section (see Section :ref:`gallina-assumptions`) and +the local variables and hypotheses of the theorem statement. It is enriched by +the use of certain tactics (see e.g. :tacn:`intro`). + +When a proof is completed, the message ``Proof completed`` is displayed. +One can then register this proof as a defined constant in the +environment. Because there exists a correspondence between proofs and +terms of λ-calculus, known as the *Curry-Howard isomorphism* +:cite:`How80,Bar81,Gir89,Hue88`, |Coq| stores proofs as terms of |Cic|. Those +terms are called *proof terms*. + + +.. exn:: No focused proof. + + Coq raises this error message when one attempts to use a proof editing command + out of the proof editing mode. + +.. _proof-editing-mode: + +Switching on/off the proof editing mode +------------------------------------------- + +The proof editing mode is entered by asserting a statement, which typically is +the assertion of a theorem using an assertion command like :cmd:`Theorem`. The +list of assertion commands is given in :ref:`Assertions`. The command +:cmd:`Goal` can also be used. + +.. cmd:: Goal @form + + This is intended for quick assertion of statements, without knowing in + advance which name to give to the assertion, typically for quick + testing of the provability of a statement. If the proof of the + statement is eventually completed and validated, the statement is then + bound to the name ``Unnamed_thm`` (or a variant of this name not already + used for another statement). + +.. cmd:: Qed + + This command is available in interactive editing proof mode when the + proof is completed. Then :cmd:`Qed` extracts a proof term from the proof + script, switches back to Coq top-level and attaches the extracted + proof term to the declared name of the original goal. This name is + added to the environment as an opaque constant. + + .. exn:: Attempt to save an incomplete proof. + + .. note:: + + Sometimes an error occurs when building the proof term, because + tactics do not enforce completely the term construction + constraints. + + The user should also be aware of the fact that since the + proof term is completely rechecked at this point, one may have to wait + a while when the proof is large. In some exceptional cases one may + even incur a memory overflow. + + .. cmdv:: Defined + :name: Defined + + Same as :cmd:`Qed` but the proof is then declared transparent, which means + that its content can be explicitly used for type-checking and that it can be + unfolded in conversion tactics (see :ref:`performingcomputations`, + :cmd:`Opaque`, :cmd:`Transparent`). + + .. cmdv:: Save @ident + :name: Save + + Forces the name of the original goal to be :token:`ident`. This + command (and the following ones) can only be used if the original goal + has been opened using the :cmd:`Goal` command. + +.. cmd:: Admitted + + This command is available in interactive editing mode to give up + the current proof and declare the initial goal as an axiom. + +.. cmd:: Abort + + This command cancels the current proof development, switching back to + the previous proof development, or to the |Coq| toplevel if no other + proof was edited. + + .. exn:: No focused proof (No proof-editing in progress). + + .. cmdv:: Abort @ident + + Aborts the editing of the proof named :token:`ident` (in case you have + nested proofs). + + .. seealso:: :opt:`Nested Proofs Allowed` + + .. cmdv:: Abort All + + Aborts all current goals. + +.. cmd:: Proof @term + :name: Proof `term` + + This command applies in proof editing mode. It is equivalent to + :n:`exact @term. Qed.` + That is, you have to give the full proof in one gulp, as a + proof term (see Section :ref:`applyingtheorems`). + +.. cmd:: Proof + + Is a no-op which is useful to delimit the sequence of tactic commands + which start a proof, after a :cmd:`Theorem` command. It is a good practice to + use :cmd:`Proof` as an opening parenthesis, closed in the script with a + closing :cmd:`Qed`. + + .. seealso:: :cmd:`Proof with` + +.. cmd:: Proof using {+ @ident } + + This command applies in proof editing mode. It declares the set of + section variables (see :ref:`gallina-assumptions`) used by the proof. + At :cmd:`Qed` time, the + system will assert that the set of section variables actually used in + the proof is a subset of the declared one. + + The set of declared variables is closed under type dependency. For + example if ``T`` is variable and a is a variable of type ``T``, the commands + ``Proof using a`` and ``Proof using T a`` are actually equivalent. + + .. cmdv:: Proof using {+ @ident } with @tactic + + Combines in a single line :cmd:`Proof with` and :cmd:`Proof using`. + + .. seealso:: :ref:`tactics-implicit-automation` + + .. cmdv:: Proof using All + + Use all section variables. + + .. cmdv:: Proof using {? Type } + + Use only section variables occurring in the statement. + + .. cmdv:: Proof using Type* + + The ``*`` operator computes the forward transitive closure. E.g. if the + variable ``H`` has type ``p < 5`` then ``H`` is in ``p*`` since ``p`` occurs in the type + of ``H``. ``Type*`` is the forward transitive closure of the entire set of + section variables occurring in the statement. + + .. cmdv:: Proof using -({+ @ident }) + + Use all section variables except the list of :token:`ident`. + + .. cmdv:: Proof using @collection1 + @collection2 + + Use section variables from the union of both collections. + See :ref:`nameaset` to know how to form a named collection. + + .. cmdv:: Proof using @collection1 - @collection2 + + Use section variables which are in the first collection but not in the + second one. + + .. cmdv:: Proof using @collection - ({+ @ident }) + + Use section variables which are in the first collection but not in the + list of :token:`ident`. + + .. cmdv:: Proof using @collection * + + Use section variables in the forward transitive closure of the collection. + The ``*`` operator binds stronger than ``+`` and ``-``. + + +Proof using options +``````````````````` + +The following options modify the behavior of ``Proof using``. + + +.. opt:: Default Proof Using "@expression" + + Use :n:`@expression` as the default ``Proof using`` value. E.g. ``Set Default + Proof Using "a b"`` will complete all ``Proof`` commands not followed by a + ``using`` part with ``using a b``. + + +.. opt:: Suggest Proof Using + + When :cmd:`Qed` is performed, suggest a ``using`` annotation if the user did not + provide one. + +.. _`nameaset`: + +Name a set of section hypotheses for ``Proof using`` +```````````````````````````````````````````````````` + +.. cmd:: Collection @ident := @expression + + This can be used to name a set of section + hypotheses, with the purpose of making ``Proof using`` annotations more + compact. + + .. example:: + + Define the collection named ``Some`` containing ``x``, ``y`` and ``z``:: + + Collection Some := x y z. + + Define the collection named ``Fewer`` containing only ``x`` and ``y``:: + + Collection Fewer := Some - z + + Define the collection named ``Many`` containing the set union or set + difference of ``Fewer`` and ``Some``:: + + Collection Many := Fewer + Some + Collection Many := Fewer - Some + + Define the collection named ``Many`` containing the set difference of + ``Fewer`` and the unnamed collection ``x y``:: + + Collection Many := Fewer - (x y) + + + +.. cmd:: Existential @num := @term + + This command instantiates an existential variable. :token:`num` is an index in + the list of uninstantiated existential variables displayed by :cmd:`Show Existentials`. + + This command is intended to be used to instantiate existential + variables when the proof is completed but some uninstantiated + existential variables remain. To instantiate existential variables + during proof edition, you should use the tactic :tacn:`instantiate`. + +.. cmd:: Grab Existential Variables + + This command can be run when a proof has no more goal to be solved but + has remaining uninstantiated existential variables. It takes every + uninstantiated existential variable and turns it into a goal. + + +Navigation in the proof tree +-------------------------------- + +.. cmd:: Undo + + This command cancels the effect of the last command. Thus, it + backtracks one step. + +.. cmdv:: Undo @num + + Repeats Undo :token:`num` times. + +.. cmdv:: Restart + :name: Restart + + This command restores the proof editing process to the original goal. + + .. exn:: No focused proof to restart. + +.. cmd:: Focus + + This focuses the attention on the first subgoal to prove and the + printing of the other subgoals is suspended until the focused subgoal + is solved or unfocused. This is useful when there are many current + subgoals which clutter your screen. + + .. deprecated:: 8.8 + + Prefer the use of bullets or focusing brackets (see below). + +.. cmdv:: Focus @num + + This focuses the attention on the :token:`num` th subgoal to prove. + + .. deprecated:: 8.8 + + Prefer the use of focusing brackets with a goal selector (see below). + +.. cmd:: Unfocus + + This command restores to focus the goal that were suspended by the + last :cmd:`Focus` command. + + .. deprecated:: 8.8 + +.. cmd:: Unfocused + + Succeeds if the proof is fully unfocused, fails if there are some + goals out of focus. + +.. _curly-braces: + +.. cmd:: %{ %| %} + + The command ``{`` (without a terminating period) focuses on the first + goal, much like :cmd:`Focus` does, however, the subproof can only be + unfocused when it has been fully solved ( *i.e.* when there is no + focused goal left). Unfocusing is then handled by ``}`` (again, without a + terminating period). See also example in next section. + + Note that when a focused goal is proved a message is displayed + together with a suggestion about the right bullet or ``}`` to unfocus it + or focus the next one. + + .. cmdv:: @num: %{ + + This focuses on the :token:`num` th subgoal to prove. + + Error messages: + + .. exn:: This proof is focused, but cannot be unfocused this way. + + You are trying to use ``}`` but the current subproof has not been fully solved. + + .. exn:: No such goal. + :name: No such goal. (Focusing) + + .. exn:: Brackets only support the single numbered goal selector. + + See also error messages about bullets below. + +.. _bullets: + +Bullets +``````` + +Alternatively to ``{`` and ``}``, proofs can be structured with bullets. The +use of a bullet ``b`` for the first time focuses on the first goal ``g``, the +same bullet cannot be used again until the proof of ``g`` is completed, +then it is mandatory to focus the next goal with ``b``. The consequence is +that ``g`` and all goals present when ``g`` was focused are focused with the +same bullet ``b``. See the example below. + +Different bullets can be used to nest levels. The scope of bullet does +not go beyond enclosing ``{`` and ``}``, so bullets can be reused as further +nesting levels provided they are delimited by these. Available bullets +are ``-``, ``+``, ``*``, ``--``, ``++``, ``**``, ``---``, ``+++``, ``***``, ... (without a terminating period). + +Note again that when a focused goal is proved a message is displayed +together with a suggestion about the right bullet or ``}`` to unfocus it +or focus the next one. + +.. note:: + + In Proof General (``Emacs`` interface to |Coq|), you must use + bullets with the priority ordering shown above to have a correct + indentation. For example ``-`` must be the outer bullet and ``**`` the inner + one in the example below. + +The following example script illustrates all these features: + +.. example:: + .. coqtop:: all + + Goal (((True /\ True) /\ True) /\ True) /\ True. + Proof. + split. + - split. + + split. + ** { split. + - trivial. + - trivial. + } + ** trivial. + + trivial. + - assert True. + { trivial. } + assumption. + + +.. exn:: Wrong bullet @bullet1: Current bullet @bullet2 is not finished. + + Before using bullet :n:`@bullet1` again, you should first finish proving the current focused goal. Note that :n:`@bullet1` and :n:`@bullet2` may be the same. + +.. exn:: Wrong bullet @bullet1: Bullet @bullet2 is mandatory here. + + You must put :n:`@bullet2` to focus next goal. No other bullet is allowed here. + +.. exn:: No such goal. Focus next goal with bullet @bullet. + + You tried to apply a tactic but no goal where under focus. Using :n:`@bullet` is mandatory here. + +.. exn:: No such goal. Try unfocusing with %{. + + You just finished a goal focused by ``{``, you must unfocus it with ``}``. + +Set Bullet Behavior +``````````````````` +.. opt:: Bullet Behavior %( "None" %| "Strict Subproofs" %) + + This option controls the bullet behavior and can take two possible values: + + - "None": this makes bullets inactive. + - "Strict Subproofs": this makes bullets active (this is the default behavior). + +.. _requestinginformation: + +Requesting information +---------------------- + + +.. cmd:: Show + + This command displays the current goals. + + .. exn:: No focused proof. + + .. cmdv:: Show @num + + Displays only the :token:`num` th subgoal. + + .. exn:: No such goal. + + + .. cmdv:: Show @ident + + Displays the named goal :token:`ident`. This is useful in + particular to display a shelved goal but only works if the + corresponding existential variable has been named by the user + (see :ref:`existential-variables`) as in the following example. + + .. example:: + + .. coqtop:: all + + Goal exists n, n = 0. + eexists ?[n]. + Show n. + + .. cmdv:: Show Script + :name: Show Script + + Displays the whole list of tactics applied from the + beginning of the current proof. This tactics script may contain some + holes (subgoals not yet proved). They are printed under the form + + ``<Your Tactic Text here>``. + + .. cmdv:: Show Proof + :name: Show Proof + + It displays the proof term generated by the tactics + that have been applied. If the proof is not completed, this term + contain holes, which correspond to the sub-terms which are still to be + constructed. These holes appear as a question mark indexed by an + integer, and applied to the list of variables in the context, since it + may depend on them. The types obtained by abstracting away the context + from the type of each hole-placer are also printed. + + .. cmdv:: Show Conjectures + :name: Show Conjectures + + It prints the list of the names of all the + theorems that are currently being proved. As it is possible to start + proving a previous lemma during the proof of a theorem, this list may + contain several names. + + .. cmdv:: Show Intro + :name: Show Intro + + If the current goal begins by at least one product, + this command prints the name of the first product, as it would be + generated by an anonymous :tacn:`intro`. The aim of this command is to ease + the writing of more robust scripts. For example, with an appropriate + Proof General macro, it is possible to transform any anonymous :tacn:`intro` + into a qualified one such as ``intro y13``. In the case of a non-product + goal, it prints nothing. + + .. cmdv:: Show Intros + :name: Show Intros + + This command is similar to the previous one, it + simulates the naming process of an :tacn:`intros`. + + .. cmdv:: Show Existentials + :name: Show Existentials + + It displays the set of all uninstantiated + existential variables in the current proof tree, along with the type + and the context of each variable. + + .. cmdv:: Show Match @ident + + This variant displays a template of the Gallina + ``match`` construct with a branch for each constructor of the type + :token:`ident` + + .. example:: + .. coqtop:: all + + Show Match nat. + + .. exn:: Unknown inductive type. + + .. cmdv:: Show Universes + :name: Show Universes + + It displays the set of all universe constraints and + its normalized form at the current stage of the proof, useful for + debugging universe inconsistencies. + + +.. cmd:: Guarded + + Some tactics (e.g. :tacn:`refine`) allow to build proofs using + fixpoint or co-fixpoint constructions. Due to the incremental nature + of interactive proof construction, the check of the termination (or + guardedness) of the recursive calls in the fixpoint or cofixpoint + constructions is postponed to the time of the completion of the proof. + + The command :cmd:`Guarded` allows checking if the guard condition for + fixpoint and cofixpoint is violated at some time of the construction + of the proof without having to wait the completion of the proof. + + +Controlling the effect of proof editing commands +------------------------------------------------ + + +.. opt:: Hyps Limit @num + + This option controls the maximum number of hypotheses displayed in goals + after the application of a tactic. All the hypotheses remain usable + in the proof development. + When unset, it goes back to the default mode which is to print all + available hypotheses. + + +.. opt:: Automatic Introduction + + This option controls the way binders are handled + in assertion commands such as :n:`Theorem @ident {? @binders} : @term`. When the + option is on, which is the default, binders are automatically put in + the local context of the goal to prove. + + When the option is off, binders are discharged on the statement to be + proved and a tactic such as :tacn:`intro` (see Section :ref:`managingthelocalcontext`) + has to be used to move the assumptions to the local context. + + +.. opt:: Nested Proofs Allowed + + When turned on (it is off by default), this option enables support for nested + proofs: a new assertion command can be inserted before the current proof is + finished, in which case Coq will temporarily switch to the proof of this + *nested lemma*. When the proof of the nested lemma is finished (with :cmd:`Qed` + or :cmd:`Defined`), its statement will be made available (as if it had been + proved before starting the previous proof) and Coq will switch back to the + proof of the previous assertion. + + +Controlling memory usage +------------------------ + +When experiencing high memory usage the following commands can be used +to force |Coq| to optimize some of its internal data structures. + + +.. cmd:: Optimize Proof + + This command forces |Coq| to shrink the data structure used to represent + the ongoing proof. + + +.. cmd:: Optimize Heap + + This command forces the |OCaml| runtime to perform a heap compaction. + This is in general an expensive operation. + See: `OCaml Gc <http://caml.inria.fr/pub/docs/manual-ocaml/libref/Gc.html#VALcompact>`_ + There is also an analogous tactic :tacn:`optimize_heap`. diff --git a/doc/sphinx/proof-engine/ssreflect-proof-language.rst b/doc/sphinx/proof-engine/ssreflect-proof-language.rst index 61dffa0243..3b2009657f 100644 --- a/doc/sphinx/proof-engine/ssreflect-proof-language.rst +++ b/doc/sphinx/proof-engine/ssreflect-proof-language.rst @@ -6,10 +6,7 @@ The |SSR| proof language ------------------------------ -:Source: https://coq.inria.fr/distrib/current/refman/ssreflect.html -:Converted by: Enrico Tassi - -Author: Georges Gonthier, Assia Mahboubi, Enrico Tassi +:Authors: Georges Gonthier, Assia Mahboubi, Enrico Tassi Introduction @@ -40,7 +37,7 @@ bookkeeping is performed on the conclusion of the goal, using for that purpose a couple of syntactic constructions behaving similar to tacticals (and often named as such in this chapter). The ``:`` tactical moves hypotheses from the context to the conclusion, while ``=>`` moves hypotheses from the -conclusion to the context, and in moves back and forth an hypothesis from the +conclusion to the context, and ``in`` moves back and forth an hypothesis from the context to the conclusion for the time of applying an action to it. While naming hypotheses is commonly done by means of an ``as`` clause in the @@ -50,20 +47,22 @@ often followed by ``=>`` to explicitly name them. While generalizing the goal is normally not explicitly needed in Chapter :ref:`tactics`, it is an explicit operation performed by ``:``. +.. seealso:: :ref:`bookkeeping_ssr` + Beside the difference of bookkeeping model, this chapter includes specific tactics which have no explicit counterpart in Chapter :ref:`tactics` -such as tactics to mix forward steps and generalizations as generally -have or without loss. +such as tactics to mix forward steps and generalizations as +:tacn:`generally have` or :tacn:`without loss`. |SSR| adopts the point of view that rewriting, definition expansion and partial evaluation participate all to a same concept of rewriting a goal in a larger sense. As such, all these functionalities -are provided by the rewrite tactic. +are provided by the :tacn:`rewrite <rewrite (ssreflect)>` tactic. |SSR| includes a little language of patterns to select subterms in tactics or tacticals where it matters. Its most notable application is -in the rewrite tactic, where patterns are used to specify where the -rewriting step has to take place. +in the :tacn:`rewrite <rewrite (ssreflect)>` tactic, where patterns are +used to specify where the rewriting step has to take place. Finally, |SSR| supports so-called reflection steps, typically allowing to switch back and forth between the computational view and @@ -90,20 +89,24 @@ Getting started ~~~~~~~~~~~~~~~ To be available, the tactics presented in this manual need the -following minimal set of libraries to loaded: ``ssreflect.v``, +following minimal set of libraries to be loaded: ``ssreflect.v``, ``ssrfun.v`` and ``ssrbool.v``. Moreover, these tactics come with a methodology specific to the authors of |SSR| and which requires a few options to be set in a different way than in their default way. All in all, this corresponds to working in the following context: -.. coqtop:: all +.. coqtop:: in From Coq Require Import ssreflect ssrfun ssrbool. Set Implicit Arguments. Unset Strict Implicit. Unset Printing Implicit Defensive. +.. seealso:: + :opt:`Implicit Arguments`, :opt:`Strict Implicit`, + :opt:`Printing Implicit Defensive` + .. _compatibility_issues_ssr: @@ -117,14 +120,14 @@ compatible with the rest of |Coq|, up to a few discrepancies: + New keywords (``is``) might clash with variable, constant, tactic or tactical names, or with quasi-keywords in tactic or vernacular notations. -+ New tactic(al)s names (``last``, ``done``, ``have``, ``suffices``, - ``suff``, ``without loss``, ``wlog``, ``congr``, ``unlock``) ++ New tactic(al)s names (:tacn:`last`, :tacn:`done`, :tacn:`have`, :tacn:`suffices`, + :tacn:`suff`, :tacn:`without loss`, :tacn:`wlog`, :tacn:`congr`, :tacn:`unlock`) might clash with user tactic names. + Identifiers with both leading and trailing ``_``, such as ``_x_``, are reserved by |SSR| and cannot appear in scripts. -+ The extensions to the rewrite tactic are partly incompatible with those ++ The extensions to the :tacn:`rewrite` tactic are partly incompatible with those available in current versions of |Coq|; in particular: ``rewrite .. in - (type of k)`` or ``rewrite .. in *`` or any other variant of ``rewrite`` + (type of k)`` or ``rewrite .. in *`` or any other variant of :tacn:`rewrite` will not work, and the |SSR| syntax and semantics for occurrence selection and rule chaining is different. Use an explicit rewrite direction (``rewrite <- …`` or ``rewrite -> …``) to access the |Coq| rewrite tactic. @@ -142,7 +145,7 @@ compatible with the rest of |Coq|, up to a few discrepancies: Note that the full syntax of |SSR|’s rewrite and reserved identifiers are enabled only if the ssreflect module has been required and if ``SsrSyntax`` has - been imported. Thus a file that requires (without importing) ssreflect + been imported. Thus a file that requires (without importing) ``ssreflect`` and imports ``SsrSyntax``, can be required and imported without automatically enabling |SSR|’s extended rewrite syntax and reserved identifiers. @@ -151,9 +154,10 @@ compatible with the rest of |Coq|, up to a few discrepancies: such as have, set and pose. + The generalization of if statements to non-Boolean conditions is turned off by |SSR|, because it is mostly subsumed by Coercion to ``bool`` of the - ``sumXXX`` types (declared in ``ssrfun.v``) and the ``if`` *term* ``is`` *pattern* ``then`` - *term* ``else`` *term* construct (see :ref:`pattern_conditional_ssr`). To use the - generalized form, turn off the |SSR| Boolean if notation using the command: + ``sumXXX`` types (declared in ``ssrfun.v``) and the + :n:`if @term is @pattern then @term else @term` construct + (see :ref:`pattern_conditional_ssr`). To use the + generalized form, turn off the |SSR| Boolean ``if`` notation using the command: ``Close Scope boolean_if_scope``. + The following two options can be unset to disable the incompatible rewrite syntax and allow reserved identifiers to appear in scripts. @@ -194,9 +198,9 @@ construct differs from the latter in that + The pattern can be nested (deep pattern matching), in particular, this allows expression of the form: -.. coqtop:: in +.. coqdoc:: - let: exist (x, y) p_xy := Hp in … . + let: exist (x, y) p_xy := Hp in … . + The destructured constructor is explicitly given in the pattern, and is used for type inference. @@ -225,11 +229,7 @@ construct differs from the latter in that The ``let:`` construct is just (more legible) notation for the primitive -|Gallina| expression - -.. coqtop:: in - - match term with pattern => term end. +|Gallina| expression :n:`match @term with @pattern => @term end`. The |SSR| destructuring assignment supports all the dependent match annotations; the full syntax is @@ -289,28 +289,17 @@ assignment with a refutable pattern, adapted to the pure functional setting of |Gallina|, which lacks a ``Match_Failure`` exception. Like ``let:`` above, the ``if…is`` construct is just (more legible) notation -for the primitive |Gallina| expression: - -.. coqtop:: in - - match term with pattern => term | _ => term end. +for the primitive |Gallina| expression +:n:`match @term with @pattern => @term | _ => @term end`. Similarly, it will always be displayed as the expansion of this form in terms of primitive match expressions (where the default expression may be replicated). Explicit pattern testing also largely subsumes the generalization of -the if construct to all binary data types; compare: - -.. coqtop:: in - - if term is inl _ then term else term. - -and: - -.. coqtop:: in - - if term then term else term. +the ``if`` construct to all binary data types; compare +:n:`if @term is inl _ then @term else @term` and +:n:`if @term then @term else @term`. The latter appears to be marginally shorter, but it is quite ambiguous, and indeed often requires an explicit annotation @@ -426,7 +415,7 @@ an improvement over ``all null s``. The syntax of the new declaration is -.. cmd:: Prenex Implicits {+ @ident}. +.. cmd:: Prenex Implicits {+ @ident} Let us denote :math:`c_1` … :math:`c_n` the list of identifiers given to a ``Prenex Implicits`` command. The command checks that each ci is the name of @@ -437,7 +426,7 @@ a functional constant, whose implicit arguments are prenex, i.e., the first As these prenex implicit arguments are ubiquitous and have often large display strings, it is strongly recommended to change the default display settings of |Coq| so that they are not printed (except after -a ``Set Printing All command``). All |SSR| library files thus start +a ``Set Printing All`` command). All |SSR| library files thus start with the incantation .. coqtop:: all undo @@ -451,7 +440,7 @@ Anonymous arguments ~~~~~~~~~~~~~~~~~~~ When in a definition, the type of a certain argument is mandatory, but -not its name, one usually use “arrow” abstractions for prenex +not its name, one usually uses “arrow” abstractions for prenex arguments, or the ``(_ : term)`` syntax for inner arguments. In |SSR|, the latter can be replaced by the open syntax ``of term`` or (equivalently) ``& term``, which are both syntactically equivalent to a @@ -496,19 +485,13 @@ inferred from the whole context of the goal (see for example section Definitions ~~~~~~~~~~~ -The pose tactic allows to add a defined constant to a proof context. -|SSR| generalizes this tactic in several ways. In particular, the -|SSR| pose tactic supports *open syntax*: the body of the -definition does not need surrounding parentheses. For instance: +.. tacn:: pose + :name: pose (ssreflect) -.. coqtop:: reset - - From Coq Require Import ssreflect. - Set Implicit Arguments. - Unset Strict Implicit. - Unset Printing Implicit Defensive. - Lemma test : True. - Proof. + This tactic allows to add a defined constant to a proof context. + |SSR| generalizes this tactic in several ways. In particular, the + |SSR| pose tactic supports *open syntax*: the body of the + definition does not need surrounding parentheses. For instance: .. coqtop:: in @@ -518,10 +501,18 @@ is a valid tactic expression. The pose tactic is also improved for the local definition of higher order terms. Local definitions of functions can use the same syntax as -global ones. For example the tactic ``pose`` supoprts parameters: +global ones. +For example, the tactic :tacn:`pose <pose (ssreflect)>` supoprts parameters: .. example:: + .. coqtop:: reset + + From Coq Require Import ssreflect. + Set Implicit Arguments. + Unset Strict Implicit. + Unset Printing Implicit Defensive. + .. coqtop:: all Lemma test : True. @@ -631,7 +622,7 @@ where: surrounding the second :token:`term` are mandatory. + In the occurrence switch :token:`occ_switch`, if the first element of the list is a natural, this element should be a number, and not an Ltac - variable. The empty list {} is not interpreted as a valid occurrence + variable. The empty list ``{}`` is not interpreted as a valid occurrence switch. The tactic: @@ -667,7 +658,7 @@ The tactic first tries to find a subterm of the goal matching the second :token:`term` (and its type), and stops at the first subterm it finds. Then the occurrences of this subterm selected by the optional :token:`occ_switch` -are replaced by :token:`ident` and a definition ``ident := term`` +are replaced by :token:`ident` and a definition :n:`@ident := @term` is added to the context. If no :token:`occ_switch` is present, then all the occurrences are abstracted. @@ -676,20 +667,20 @@ abstracted. Matching ```````` -The matching algorithm compares a pattern ``term`` with a subterm of the +The matching algorithm compares a pattern :token:`term` with a subterm of the goal by comparing their heads and then pairwise unifying their arguments (modulo conversion). Head symbols match under the following conditions: -+ If the head of ``term`` is a constant, then it should be syntactically ++ If the head of :token:`term` is a constant, then it should be syntactically equal to the head symbol of the subterm. + If this head is a projection of a canonical structure, then canonical structure equations are used for the matching. + If the head of term is *not* a constant, the subterm should have the same structure (λ abstraction,let…in structure …). -+ If the head of ``term`` is a hole, the subterm should have at least as - many arguments as ``term``. ++ If the head of :token:`term` is a hole, the subterm should have at least as + many arguments as :token:`term`. .. example:: @@ -1082,7 +1073,7 @@ constants to the goal. Because they are tacticals, ``:`` and ``=>`` can be combined, as in -.. coqtop: in +.. coqtop:: in move: m le_n_m => p le_n_p. @@ -1147,9 +1138,7 @@ induction on the top variable ``m`` with elim=> [|m IHm] n le_n. The general form of the localization tactical in is also best -explained in terms of the goal stack: - -.. coqtop:: in +explained in terms of the goal stack:: tactic in a H1 H2 *. @@ -1212,8 +1201,8 @@ product or a ``let…in``, and performs ``hnf`` otherwise. Of course this tactic is most often used in combination with the bookkeeping tacticals (see section :ref:`introduction_ssr` and :ref:`discharge_ssr`). These -combinations mostly subsume the ``intros``, ``generalize``, ``revert``, ``rename``, -``clear`` and ``pattern`` tactics. +combinations mostly subsume the :tacn:`intros`, :tacn:`generalize`, :tacn:`revert`, :tacn:`rename`, +:tacn:`clear` and :tacn:`pattern` tactics. The case tactic @@ -1229,15 +1218,11 @@ The |SSR| case tactic has a special behavior on equalities. If the top assumption of the goal is an equality, the case tactic “destructs” it as a set of equalities between the constructor arguments of its left and right hand sides, as per the tactic injection. For example, -``case`` changes the goal - -.. coqtop:: in +``case`` changes the goal:: (x, y) = (1, 2) -> G. -into - -.. coqtop:: in +into:: x = 1 -> y = 2 -> G. @@ -1289,13 +1274,11 @@ In fact the |SSR| tactic: .. tacn:: apply :name: apply (ssreflect) -is a synonym for: - -.. coqtop:: in +is a synonym for:: intro top; first [refine top | refine (top _) | refine (top _ _) | …]; clear top. -where ``top`` is fresh name, and the sequence of refine tactics tries to +where ``top`` is a fresh name, and the sequence of refine tactics tries to catch the appropriate number of wildcards to be inserted. Note that this use of the refine tactic implies that the tactic tries to match the goal up to expansion of constants and evaluation of subterms. @@ -1322,18 +1305,14 @@ existential metavariables of sort Prop. Note that the last ``_`` of the tactic ``apply: (ex_intro _ (exist _ y _))`` - represents a proof that ``y < 3``. Instead of generating the goal - - .. coqtop:: in + represents a proof that ``y < 3``. Instead of generating the goal:: 0 < proj1_sig (exist (fun n : nat => n < 3) y ?Goal). the system tries to prove ``y < 3`` calling the trivial tactic. If it succeeds, let’s say because the context contains ``H : y < 3``, then the - system generates the following goal: - - .. coqtop:: in + system generates the following goal:: 0 < proj1_sig (exist (fun n => n < 3) y H). @@ -1352,6 +1331,7 @@ Discharge The general syntax of the discharging tactical ``:`` is: .. tacn:: @tactic {? @ident } : {+ @d_item } {? @clear_switch } + :name: ... : ... (ssreflect) .. prodn:: d_item ::= {? @occ_switch %| @clear_switch } @term @@ -1503,9 +1483,11 @@ side of an equation. The abstract tactic ``````````````````` -The ``abstract`` tactic assigns an ``abstract`` constant previously -introduced with the ``[: name ]`` intro pattern -(see section :ref:`introduction_ssr`). +.. tacn:: abstract: {+ d_item} + :name abstract (ssreflect) + +This tactic assigns an abstract constant previously introduced with the ``[: +name ]`` intro pattern (see section :ref:`introduction_ssr`). In a goal like the following:: @@ -1573,10 +1555,10 @@ The :token:`i_pattern` s can be seen as a variant of *intro patterns* :ref:`tactics`: each performs an introduction operation, i.e., pops some variables or assumptions from the goal. -An :token:`s_item` can simplify the set of subgoals or the subgoal themselves: +An :token:`s_item` can simplify the set of subgoals or the subgoals themselves: + ``//`` removes all the “trivial” subgoals that can be resolved by the - |SSR| tactic ``done`` described in :ref:`terminators_ssr`, i.e., + |SSR| tactic :tacn:`done` described in :ref:`terminators_ssr`, i.e., it executes ``try done``. + ``/=`` simplifies the goal by performing partial evaluation, as per the tactic ``simpl`` [#5]_. @@ -1734,7 +1716,7 @@ new constant as an equation. The tactic: .. coqtop:: in - move En: (size l) => n. + move En: (size l) => n. where ``l`` is a list, replaces ``size l`` by ``n`` in the goal and adds the fact ``En : size l = n`` to the context. @@ -1742,7 +1724,7 @@ This is quite different from: .. coqtop:: in - pose n := (size l). + pose n := (size l). which generates a definition ``n := (size l)``. It is not possible to generalize or rewrite such a definition; on the other hand, it is @@ -1812,6 +1794,8 @@ of a :token:`d_item` immediately following this ``/`` switch, using the syntax: .. tacv:: case: {+ @d_item } / {+ @d_item } + :name: case (ssreflect) + .. tacv:: elim: {+ @d_item } / {+ @d_item } The :token:`d_item` on the right side of the ``/`` switch are discharged as @@ -1829,9 +1813,9 @@ compact syntax: .. coqtop:: in - case: {2}_ / eqP. + case: {2}_ / eqP. -were ``_`` is interpreted as ``(_ == _)`` since +where ``_`` is interpreted as ``(_ == _)`` since ``eqP T a b : reflect (a = b) (a == b)`` and reflect is a type family with one index. @@ -1994,19 +1978,9 @@ into a closing one (similar to now). Its general syntax is: .. tacn:: by @tactic :name: by -The Ltac expression: - -.. coqtop:: in - - by [@tactic | [@tactic | …]. - -is equivalent to: - -.. coqtop:: in - - [by @tactic | by @tactic | ...]. - -and this form should be preferred to the former. +The Ltac expression :n:`by [@tactic | [@tactic | …]` is equivalent to +:n:`[by @tactic | by @tactic | ...]` and this form should be preferred +to the former. In the script provided as example in section :ref:`indentation_ssr`, the paragraph corresponding to each sub-case ends with a tactic line prefixed @@ -2016,20 +1990,13 @@ with a ``by``, like in: by apply/eqP; rewrite -dvdn1. -The by tactical is implemented using the user-defined, and extensible -done tactic. This done tactic tries to solve the current goal by some -trivial means and fails if it doesn’t succeed. Indeed, the tactic -expression: - -.. coqtop:: in - - by tactic. +.. tacn:: done + :name: done -is equivalent to: - -.. coqtop:: in - - tactic; done. +The :tacn:`by` tactical is implemented using the user-defined, and extensible +:tacn:`done` tactic. This :tacn:`done` tactic tries to solve the current goal by some +trivial means and fails if it doesn’t succeed. Indeed, the tactic +expression :n:`by @tactic` is equivalent to :n:`@tactic; done`. Conversely, the tactic @@ -2074,7 +2041,7 @@ is equivalent to: do [done | by move=> top; apply top]. -where top is a fresh name affected to the top assumption of the goal. +where ``top`` is a fresh name assigned to the top assumption of the goal. This applied form is supported by the : discharge tactical, and the tactic: @@ -2090,7 +2057,7 @@ is equivalent to: (see section :ref:`discharge_ssr` for the documentation of the apply: combination). -Warning The list of tactics, possibly chained by semi-columns, that +Warning The list of tactics, possibly chained by semicolons, that follows a by keyword is considered as a parenthesized block applied to the current goal. Hence for example if the tactic: @@ -2123,7 +2090,7 @@ generated by the previous tactic. This covers the frequent cases where a tactic generates two subgoals one of which can be easily disposed of. -This is an other powerful way of linearization of scripts, since it +This is another powerful way of linearization of scripts, since it happens very often that a trivial subgoal can be solved in a less than one line tactic. For instance, the tactic: @@ -2131,14 +2098,14 @@ one line tactic. For instance, the tactic: :name: last tries to solve the last subgoal generated by the first -tactic using the given second tactic , and fails if it does not succeeds. -Its analogous +tactic using the given second tactic, and fails if it does not succeed. +Its analogue .. tacn:: @tactic ; first by @tactic - :name: first + :name: first (ssreflect) tries to solve the first subgoal generated by the first tactic using the -second given tactic, and fails if it does not succeeds. +second given tactic, and fails if it does not succeed. |SSR| also offers an extension of this facility, by supplying tactics to *permute* the subgoals generated by a tactic. The tactic: @@ -2152,10 +2119,10 @@ equivalent to: More generally, the tactic: -.. tacn:: @tactic; last @natural first +.. tacn:: @tactic; last @num first :name: last first -where :token:`natural` is a |Coq| numeral, or and Ltac variable +where :token:`num` is a |Coq| numeral, or an Ltac variable denoting a |Coq| numeral, having the value k. It rotates the n subgoals G1 , …, Gn generated by tactic. The first subgoal becomes Gn + 1 − k and the @@ -2163,7 +2130,7 @@ circular order of subgoals remains unchanged. Conversely, the tactic: -.. tacn:: @tactic; first @natural last +.. tacn:: @tactic; first @num last :name: first last rotates the n subgoals G1 , …, Gn generated by tactic in order that @@ -2215,7 +2182,7 @@ Iteration thanks to the do tactical, whose general syntax is: .. tacn:: do {? @mult } ( @tactic | [ {+| @tactic } ] ) - :name: do + :name: do (ssreflect) where :token:`mult` is a *multiplier*. @@ -2259,14 +2226,14 @@ For instance, the tactic: tactic; do 1? rewrite mult_comm. -rewrites at most one time the lemma ``mult_com`` in all the subgoals +rewrites at most one time the lemma ``mult_comm`` in all the subgoals generated by tactic , whereas the tactic: .. coqtop:: in tactic; do 2! rewrite mult_comm. -rewrites exactly two times the lemma ``mult_com`` in all the subgoals +rewrites exactly two times the lemma ``mult_comm`` in all the subgoals generated by tactic, and fails if this rewrite is not possible in some subgoal. @@ -2335,10 +2302,10 @@ to the following one: .. tacv:: @tactic in {+ @clear_switch | {? @ } @ident | ( @ident ) | ( {? @ } @ident := @c_pattern ) } {? * } In its simplest form the last option lets one rename hypotheses that -can’t be cleared (like section variables). For example ``(y := x)`` +can’t be cleared (like section variables). For example, ``(y := x)`` generalizes over ``x`` and reintroduces the generalized variable under the name ``y`` (and does not clear ``x``). -For a more precise description this form of localization refer +For a more precise description of this form of localization refer to :ref:`advanced_generalization_ssr`. @@ -2351,7 +2318,7 @@ Forward reasoning structures the script by explicitly specifying some assumptions to be added to the proof context. It is closely associated with the declarative style of proof, since an extensive use of these highlighted statements make the script closer to a (very detailed) -text book proof. +textbook proof. Forward chaining tactics allow to state an intermediate lemma and start a piece of script dedicated to the proof of this statement. The use of closing @@ -2492,7 +2459,7 @@ also supported (assuming x occurs in the goal only): have {x} -> : x = y. -An other frequent use of the intro patterns combined with ``have`` is the +Another frequent use of the intro patterns combined with ``have`` is the destruction of existential assumptions like in the tactic: .. example:: @@ -2730,7 +2697,7 @@ type classes inference. Full inference for ``ty``. The first subgoal demands a proof of such instantiated statement. -+ coqtop:: ++ .. coqdoc:: have foo : ty := . @@ -2752,12 +2719,9 @@ type classes inference. No inference for ``t``. Unresolved instances are quantified in the (inferred) type of ``t`` and abstracted in ``t``. +.. opt:: SsrHave NoTCResolution -The behavior of |SSR| 1.4 and below (never resolve type classes) -can be restored with the option - -.. cmd:: Set SsrHave NoTCResolution. - + This option restores the behavior of |SSR| 1.4 and below (never resolve type classes). Variants: the suff and wlog tactics ``````````````````````````````````` @@ -2815,21 +2779,23 @@ Another useful construct is reduction, showing that a particular case is in fact general enough to prove a general property. This kind of reasoning step usually starts with: “Without loss of generality, we can suppose that …”. Formally, this corresponds to the proof of a goal -G by introducing a cut wlog_statement -> G. Hence the user shall -provide a proof for both (wlog_statement -> G) -> G and -wlog_statement -> G. However, such cuts are usually rather +``G`` by introducing a cut ``wlog_statement -> G``. Hence the user shall +provide a proof for both ``(wlog_statement -> G) -> G`` and +``wlog_statement -> G``. However, such cuts are usually rather painful to perform by -hand, because the statement wlog_statement is tedious to write by hand, +hand, because the statement ``wlog_statement`` is tedious to write by hand, and sometimes even to read. -|SSR| implements this kind of reasoning step through the without -loss tactic, whose short name is ``wlog``. It offers support to describe +|SSR| implements this kind of reasoning step through the :tacn:`without loss` +tactic, whose short name is :tacn:`wlog`. It offers support to describe the shape of the cut statements, by providing the simplifying hypothesis and by pointing at the elements of the initial goals which should be generalized. The general syntax of without loss is: .. tacn:: wlog {? suff } {? @clear_switch } {? @i_item } : {* @ident } / @term :name: wlog +.. tacv:: without loss {? suff } {? @clear_switch } {? @i_item } : {* @ident } / @term + :name: without loss where each :token:`ident` is a constant in the context of the goal. Open syntax is supported for :token:`term`. @@ -2837,16 +2803,17 @@ of the goal. Open syntax is supported for :token:`term`. In its defective form: .. tacv:: wlog: / @term +.. tacv:: without loss: / @term on a goal G, it creates two subgoals: a first one to prove the formula (term -> G) -> G and a second one to prove the formula term -> G. -If the optional list of :token:`itent` is present +If the optional list of :token:`ident` is present on the left side of ``/``, these constants are generalized in the -premise (term -> G) of the first subgoal. By default the body of local -definitions is erased. This behavior can be inhibited prefixing the +premise (term -> G) of the first subgoal. By default bodies of local +definitions are erased. This behavior can be inhibited by prefixing the name of the local definition with the ``@`` character. In the second subgoal, the tactic: @@ -2856,9 +2823,9 @@ In the second subgoal, the tactic: move=> clear_switch i_item. is performed if at least one of these optional switches is present in -the ``wlog`` tactic. +the :tacn:`wlog` tactic. -The ``wlog`` tactic is specially useful when a symmetry argument +The :tacn:`wlog` tactic is specially useful when a symmetry argument simplifies a proof. Here is an example showing the beginning of the proof that quotient and reminder of natural number euclidean division are unique. @@ -2879,9 +2846,10 @@ are unique. wlog: q1 q2 r1 r2 / q1 <= q2. by case (le_gt_dec q1 q2)=> H; last symmetry; eauto with arith. -The ``wlog suff`` variant is simpler, since it cuts wlog_statement instead -of wlog_statement -> G. It thus opens the goals wlog_statement -> G -and wlog_statement. +The ``wlog suff`` variant is simpler, since it cuts ``wlog_statement`` instead +of ``wlog_statement -> G``. It thus opens the goals +``wlog_statement -> G`` +and ``wlog_statement``. In its simplest form the ``generally have : …`` tactic is equivalent to ``wlog suff : …`` followed by last first. When the ``have`` tactic is used @@ -2920,7 +2888,7 @@ Advanced generalization The complete syntax for the items on the left hand side of the ``/`` separator is the following one: -.. tacv wlog … : {? @clear_switch | {? @ } @ident | ( {? @ } @ident := @c_pattern) } / @term +.. tacv:: wlog … : {? @clear_switch | {? @ } @ident | ( {? @ } @ident := @c_pattern) } / @term Clear operations are intertwined with generalization operations. This helps in particular avoiding dependency issues while generalizing some @@ -2936,7 +2904,7 @@ renaming does not require the original variable to be cleared. The syntax ``(@x := y)`` generates a let-in abstraction but with the following caveat: ``x`` will not bind ``y``, but its body, whenever ``y`` can be -unfolded. This cover the case of both local and global definitions, as +unfolded. This covers the case of both local and global definitions, as illustrated in the following example. .. example:: @@ -3035,7 +3003,7 @@ operation should be performed: specifies if and how the rewrite operation should be repeated. + A rewrite operation matches the occurrences of a *rewrite pattern*, - and replaces these occurrences by an other term, according to the + and replaces these occurrences by another term, according to the given :token:`r_item`. The optional *redex switch* ``[r_pattern]``, which should always be surrounded by brackets, gives explicitly this rewrite @@ -3329,7 +3297,7 @@ The rewrite tactic can be provided a *tuple* of rewrite rules, or more generally a tree of such rules, since this tuple can feature arbitrary inner parentheses. We call *multirule* such a generalized rewrite rule. This feature is of special interest when it is combined with -multiplier switches, which makes the rewrite tactic iterates the +multiplier switches, which makes the rewrite tactic iterate the rewrite operations prescribed by the rules on the current goal. @@ -3473,7 +3441,7 @@ efficient ones, e.g. for the purpose of a correctness proof. Wildcards vs abstractions ````````````````````````` -The rewrite tactic supports :token:`r_items` containing holes. For example in +The rewrite tactic supports :token:`r_items` containing holes. For example, in the tactic ``rewrite (_ : _ * 0 = 0).`` the term ``_ * 0 = 0`` is interpreted as ``forall n : nat, n * 0 = 0.`` Anyway this tactic is *not* equivalent to @@ -3730,14 +3698,15 @@ We provide a special tactic unlock for unfolding such definitions while removing “locks”, e.g., the tactic: .. tacn:: unlock {? @occ_switch } @ident + :name: unlock replaces the occurrence(s) of :token:`ident` coded by the :token:`occ_switch` with the corresponding body. We found that it was usually preferable to prevent the expansion of some functions by the partial evaluation switch ``/=``, unless this -allowed the evaluation of a condition. This is possible thanks to an -other mechanism of term tagging, resting on the following *Notation*: +allowed the evaluation of a condition. This is possible thanks to another +mechanism of term tagging, resting on the following *Notation*: .. coqtop:: in @@ -3781,7 +3750,7 @@ arithmetic operations. We define for instance: The operation ``addn`` behaves exactly like ``plus``, except that ``(addn (S n) m)`` will not simplify spontaneously to -``(S (addn n m))`` (the two terms, however, are inter-convertible). +``(S (addn n m))`` (the two terms, however, are convertible). In addition, the unfolding step: ``rewrite /addn`` will replace ``addn`` directly with ``plus``, so the ``nosimpl`` form is essentially invisible. @@ -3792,7 +3761,7 @@ essentially invisible. Congruence ~~~~~~~~~~ -Because of the way matching interferes with type families parameters, +Because of the way matching interferes with parameters of type families, the tactic: .. coqtop:: in @@ -3912,8 +3881,8 @@ The simple form of patterns used so far, terms possibly containing wild cards, often require an additional :token:`occ_switch` to be specified. While this may work pretty fine for small goals, the use of polymorphic functions and dependent types may lead to an invisible -duplication of functions arguments. These copies usually end up in -types hidden by the implicit arguments machinery or by user defined +duplication of function arguments. These copies usually end up in +types hidden by the implicit arguments machinery or by user-defined notations. In these situations computing the right occurrence numbers is very tedious because they must be counted on the goal as printed after setting the Printing All flag. Moreover the resulting script is @@ -3981,7 +3950,7 @@ pattern for the redex looking at the rule used for rewriting. The first :token:`c_pattern` is the simplest form matching any context but selecting a specific redex and has been described in the previous sections. We have seen so far that the possibility of selecting a -redex using a term with holes is already a powerful mean of redex +redex using a term with holes is already a powerful means of redex selection. Similarly, any terms provided by the user in the more complex forms of :token:`c_patterns` presented in the tables above can contain @@ -4064,7 +4033,7 @@ Contextual pattern in set and the : tactical As already mentioned in section :ref:`abbreviations_ssr` the ``set`` tactic takes as an argument a term in open syntax. This term is interpreted as the -simplest for of :token:`c_pattern`. To void confusion in the grammar, open +simplest form of :token:`c_pattern`. To avoid confusion in the grammar, open syntax is supported only for the simplest form of patterns, while parentheses are required around more complex patterns. @@ -4086,17 +4055,17 @@ parentheses are required around more complex patterns. set t := (a + _ in X in _ = X). -Since the user may define an infix notation for ``in`` the former tactic -may result ambiguous. The disambiguation rule implemented is to prefer +Since the user may define an infix notation for ``in`` the result of the former +tactic may be ambiguous. The disambiguation rule implemented is to prefer patterns over simple terms, but to interpret a pattern with double -parentheses as a simple term. For example the following tactic would +parentheses as a simple term. For example, the following tactic would capture any occurrence of the term ``a in A``. .. coqtop:: in set t := ((a in A)). -Contextual pattern can also be used as arguments of the ``:`` tactical. +Contextual patterns can also be used as arguments of the ``:`` tactical. For example: .. coqtop:: in @@ -4139,7 +4108,7 @@ Contextual patterns in rewrite Note that the right hand side of ``addn0`` is undetermined, but the rewrite pattern specifies the redex explicitly. The right hand side - of ``addn0`` is unified with the term identified by ``X``, ``0`` here. + of ``addn0`` is unified with the term identified by ``X``, here ``0``. The following pattern does not specify a redex, since it identifies an @@ -4269,7 +4238,7 @@ generation (see section :ref:`generation_of_equations_ssr`). .. example:: - The following script illustrate a toy example of this feature. Let us + The following script illustrates a toy example of this feature. Let us define a function adding an element at the end of a list: .. coqtop:: reset @@ -4283,7 +4252,7 @@ generation (see section :ref:`generation_of_equations_ssr`). .. coqtop:: all Variable d : Type. - Fixpoint add_last(s : list d) (z : d) {struct s} : list d := + Fixpoint add_last (s : list d) (z : d) {struct s} : list d := if s is cons x s' then cons x (add_last s' z) else z :: nil. One can define an alternative, reversed, induction principle on @@ -4296,7 +4265,7 @@ generation (see section :ref:`generation_of_equations_ssr`). forall s : list d, P s. Then the combination of elimination views with equation names result - in a concise syntax for reasoning inductively using the user defined + in a concise syntax for reasoning inductively using the user-defined elimination scheme. .. coqtop:: all @@ -4305,8 +4274,8 @@ generation (see section :ref:`generation_of_equations_ssr`). elim/last_ind_list E : l=> [| u v]; last first. -User provided eliminators (potentially generated with the ``Function`` -|Coq|’s command) can be combined with the type family switches described +User-provided eliminators (potentially generated with |Coq|’s ``Function`` +command) can be combined with the type family switches described in section :ref:`type_families_ssr`. Consider an eliminator ``foo_ind`` of type: @@ -4341,7 +4310,7 @@ The ``elim/`` tactic distinguishes two cases: As explained in section :ref:`type_families_ssr`, the initial prefix of ``ei`` can be omitted. -Here an example of a regular, but non trivial, eliminator. +Here is an example of a regular, but nontrivial, eliminator. .. example:: @@ -4423,7 +4392,7 @@ Here an example of a regular, but non trivial, eliminator. ``P`` should be the same as the second argument of ``plus``, in the second argument of ``P``, but ``y`` and ``z`` do no unify. -Here an example of a truncated eliminator: +Here is an example of a truncated eliminator: .. example:: @@ -4481,7 +4450,7 @@ Interpreting assumptions ~~~~~~~~~~~~~~~~~~~~~~~~ Interpreting an assumption in the context of a proof consists in -applying it a lemma before generalizing, and/or decomposing this +applying to it a lemma before generalizing, and/or decomposing this assumption. For instance, with the extensive use of boolean reflection (see section :ref:`views_and_reflection_ssr`.4), it is quite frequent to need to decompose the logical interpretation of (the boolean @@ -4681,15 +4650,17 @@ Note that the goal interpretation view mechanism supports both ``apply`` and ``exact`` tactics. As expected, a goal interpretation view command exact/term should solve the current goal or it will fail. -*Warning* Goal interpretation view tactics are *not* compatible with -the bookkeeping tactical ``=>`` since this would be redundant with the -``apply: term => _`` construction. +.. warning:: + + Goal interpretation view tactics are *not* compatible with + the bookkeeping tactical ``=>`` since this would be redundant with the + ``apply: term => _`` construction. Boolean reflection ~~~~~~~~~~~~~~~~~~ -In the Calculus of Inductive Construction, there is an obvious +In the Calculus of Inductive Constructions, there is an obvious distinction between logical propositions and boolean values. On the one hand, logical propositions are objects of *sort* ``Prop`` which is the carrier of intuitionistic reasoning. Logical connectives in @@ -5002,7 +4973,7 @@ but they also allow complex transformation, involving negations. Note that views, being part of :token:`i_pattern`, can be used to interpret assertions too. For example the following script asserts ``a && b`` but -actually used its propositional interpretation. +actually uses its propositional interpretation. .. example:: @@ -5038,7 +5009,7 @@ applied to a goal ``top`` is interpreted in the following way: Like assumption interpretation view hints, goal interpretation ones -are user defined lemmas stored (see section :ref:`views_and_reflection_ssr`) in the ``Hint View`` +are user-defined lemmas stored (see section :ref:`views_and_reflection_ssr`) in the ``Hint View`` database bridging the possible gap between the type of ``term`` and the type of the goal. @@ -5132,7 +5103,7 @@ See the files ``ssreflect.v`` and ``ssrbool.v`` for examples. Multiple views ~~~~~~~~~~~~~~ -The hypotheses and the goal can be interpreted applying multiple views +The hypotheses and the goal can be interpreted by applying multiple views in sequence. Both move and apply can be followed by an arbitrary number of ``/term``. The main difference between the following two tactics @@ -5188,8 +5159,9 @@ equivalences are indeed taken into account, otherwise only single |SSR| proposes an extension of the Search command. Its syntax is: .. cmd:: Search {? @pattern } {* {? - } %( @string %| @pattern %) {? % @ident} } {? in {+ {? - } @qualid } } + :name: Search (ssreflect) -where :token:`qualid` is the name of an open module. This command search returns +where :token:`qualid` is the name of an open module. This command returns the list of lemmas: @@ -5214,7 +5186,7 @@ Note that: + As for regular terms, patterns can feature scope indications. For instance, the command: ``Search _ (_ + _)%N.`` lists all the lemmas whose - statement (conclusion or hypotheses) involve an application of the + statement (conclusion or hypotheses) involves an application of the binary operation denoted by the infix ``+`` symbol in the ``N`` scope (which is |SSR| scope for natural numbers). + Patterns with holes should be surrounded by parentheses. @@ -5318,11 +5290,11 @@ intro item see :ref:`introduction_ssr` multiplier see :ref:`iteration_ssr` -.. prodn:: occ_switch ::= { {? + %| - } {* @natural } } +.. prodn:: occ_switch ::= { {? + %| - } {* @num } } occur. switch see :ref:`occurrence_selection_ssr` -.. prodn:: mult ::= {? @natural } @mult_mark +.. prodn:: mult ::= {? @num } @mult_mark multiplier see :ref:`iteration_ssr` @@ -5386,6 +5358,8 @@ rewrite see :ref:`rewriting_ssr` .. tacn:: have suff {? @clear_switch } {? @i_pattern } {? : @term } := @term .. tacv:: have suff {? @clear_switch } {? @i_pattern } : @term {? by @tactic } .. tacv:: gen have {? @ident , } {? @i_pattern } : {+ @gen_item } / @term {? by @tactic } +.. tacv:: generally have {? @ident , } {? @i_pattern } : {+ @gen_item } / @term {? by @tactic } + :name: generally have forward chaining see :ref:`structure_ssr` @@ -5395,7 +5369,11 @@ forward chaining see :ref:`structure_ssr` specializing see :ref:`structure_ssr` .. tacn:: suff {* @i_item } {? @i_pattern } {+ @binder } : @term {? by @tactic } + :name: suff +.. tacv:: suffices {* @i_item } {? @i_pattern } {+ @binder } : @term {? by @tactic } + :name: suffices .. tacv:: suff {? have } {? @clear_switch } {? @i_pattern } : @term {? by @tactic } +.. tacv:: suffices {? have } {? @clear_switch } {? @i_pattern } : @term {? by @tactic } backchaining see :ref:`structure_ssr` @@ -5491,7 +5469,7 @@ prenex implicits declaration see :ref:`parametric_polymorphism_ssr` used for such generated names. .. [#7] More precisely, it should have a quantified inductive type with a assumptions and m − a constructors. -.. [#8] This is an implementation feature: there is not such obstruction +.. [#8] This is an implementation feature: there is no such obstruction in the metatheory .. [#9] The current state of the proof shall be displayed by the Show Proof command of |Coq| proof mode. diff --git a/doc/sphinx/proof-engine/tactics.rst b/doc/sphinx/proof-engine/tactics.rst index da34e3b55b..29c2f8b815 100644 --- a/doc/sphinx/proof-engine/tactics.rst +++ b/doc/sphinx/proof-engine/tactics.rst @@ -24,7 +24,7 @@ Each (sub)goal is denoted with a number. The current goal is numbered 1. By default, a tactic is applied to the current goal, but one can address a particular goal in the list by writing n:tactic which means “apply tactic tactic to goal number n”. We can show the list of -subgoals by typing Show (see Section :ref:`TODO-7.3.1-Show`). +subgoals by typing Show (see Section :ref:`requestinginformation`). Since not every rule applies to a given statement, every tactic cannot be used to reduce any goal. In other words, before applying a tactic @@ -34,15 +34,16 @@ satisfied. If it is not the case, the tactic raises an error message. Tactics are built from atomic tactics and tactic expressions (which extends the folklore notion of tactical) to combine those atomic tactics. This chapter is devoted to atomic tactics. The tactic -language will be described in Chapter :ref:`TODO-9-Thetacticlanguage`. +language will be described in Chapter :ref:`ltac`. + +.. _invocation-of-tactics: Invocation of tactics ------------------------- A tactic is applied as an ordinary command. It may be preceded by a -goal selector (see Section :ref:`TODO-9.2-Semantics`). If no selector is -specified, the default selector (see Section -:ref:`TODO-8.1.1-Setdefaultgoalselector`) is used. +goal selector (see Section :ref:`ltac-semantics`). If no selector is +specified, the default selector is used. .. _tactic_invocation_grammar: @@ -50,20 +51,22 @@ specified, the default selector (see Section tactic_invocation : toplevel_selector : tactic. : |tactic . -.. cmd:: Set Default Goal Selector @toplevel_selector. +.. opt:: Default Goal Selector @toplevel_selector + + This option controls the default selector, used when no selector is + specified when applying a tactic. The initial value is 1, hence the + tactics are, by default, applied to the first goal. -After using this command, the default selector – used when no selector -is specified when applying a tactic – is set to the chosen value. The -initial value is 1, hence the tactics are, by default, applied to the -first goal. Using Set Default Goal Selector ‘‘all’’ will make is so -that tactics are, by default, applied to every goal simultaneously. -Then, to apply a tactic tac to the first goal only, you can write -1:tac. Although more selectors are available, only ‘‘all’’ or a single -natural number are valid default goal selectors. + Using value ``all`` will make it so that tactics are, by default, + applied to every goal simultaneously. Then, to apply a tactic tac + to the first goal only, you can write ``1:tac``. -.. cmd:: Test Default Goal Selector. + Using value ``!`` enforces that all tactics are used either on a + single focused goal or with a local selector (’’strict focusing + mode’’). -This command displays the current default selector. + Although more selectors are available, only ``all``, ``!`` or a + single natural number are valid default goal selectors. .. _bindingslist: @@ -89,14 +92,14 @@ bindings_list`` where ``bindings_list`` may be of two different forms: the ``n``-th non dependent premise of the ``term``, as determined by the type of ``term``. - .. exn:: No such binder + .. exn:: No such binder. + A bindings list can also be a simple list of terms :n:`{* term}`. In that case the references to which these terms correspond are - determined by the tactic. In case of ``induction``, ``destruct``, ``elim`` - and ``case`` (see :ref:`TODO-9-Thetacticlanguage`) the terms have to + determined by the tactic. In case of :tacn:`induction`, :tacn:`destruct`, :tacn:`elim` + and :tacn:`case`, the terms have to provide instances for all the dependent products in the type of term while in - the case of ``apply``, or of ``constructor`` and its variants, only instances + the case of :tacn:`apply`, or of :tacn:`constructor` and its variants, only instances for the dependent products that are not bound in the conclusion of the type are required. @@ -122,14 +125,12 @@ following syntax: The role of an occurrence clause is to select a set of occurrences of a term in a goal. In the first case, the :n:`@ident {? at {* num}}` parts indicate that -occurrences have to be selected in the hypotheses named :n:`@ident`. If no numbers -are given for hypothesis :n:`@ident`, then all the occurrences of `term` in the -hypothesis are selected. If numbers are given, they refer to occurrences of -`term` when the term is printed using option ``Set Printing All`` (see -:ref:`TODO-2.9-Printingconstructionsinfull`), counting from left to right. In -particular, occurrences of `term` in implicit arguments (see -:ref:`TODO-2.7-Implicitarguments`) or coercions (see :ref:`TODO-2.8-Coercions`) -are counted. +occurrences have to be selected in the hypotheses named :n:`@ident`. If no +numbers are given for hypothesis :n:`@ident`, then all the occurrences of `term` +in the hypothesis are selected. If numbers are given, they refer to occurrences +of `term` when the term is printed using option :opt:`Printing All`, counting +from left to right. In particular, occurrences of `term` in implicit arguments +(see :ref:`ImplicitArguments`) or coercions (see :ref:`Coercions`) are counted. If a minus sign is given between at and the list of occurrences, it negates the condition so that the clause denotes all the occurrences @@ -150,14 +151,15 @@ no numbers are given, all occurrences of :n:`@term` in the goal are selected. Finally, the last notation is an abbreviation for ``* |- *``. Note also that ``|-`` is optional in the first case when no ``*`` is given. -Here are some tactics that understand occurrences clauses: ``set``, ``remember`` -, ``induction``, ``destruct``. +Here are some tactics that understand occurrences clauses: :tacn:`set`, :tacn:`remember` +, :tacn:`induction`, :tacn:`destruct`. -See also: :ref:`TODO-8.3.7-Managingthelocalcontext`, -:ref:`TODO-8.5.2-Caseanalysisandinduction`, -:ref:`TODO-2.9-Printingconstructionsinfull`. +See also: :ref:`Managingthelocalcontext`, +:ref:`caseanalysisandinduction`, +:ref:`printing_constructions_full`. +.. _applyingtheorems: Applying theorems --------------------- @@ -165,195 +167,203 @@ Applying theorems .. tacn:: exact @term :name: exact -This tactic applies to any goal. It gives directly the exact proof -term of the goal. Let ``T`` be our goal, let ``p`` be a term of type ``U`` then -``exact p`` succeeds iff ``T`` and ``U`` are convertible (see -:ref:`TODO-4.3-Conversionrules`). + This tactic applies to any goal. It gives directly the exact proof + term of the goal. Let ``T`` be our goal, let ``p`` be a term of type ``U`` then + ``exact p`` succeeds iff ``T`` and ``U`` are convertible (see + :ref:`Conversion-rules`). -.. exn:: Not an exact proof. + .. exn:: Not an exact proof. -.. tacv:: eexact @term. + .. tacv:: eexact @term. + :name: eexact -This tactic behaves like exact but is able to handle terms and goals with -meta-variables. + This tactic behaves like exact but is able to handle terms and goals with + meta-variables. .. tacn:: assumption :name: assumption -This tactic looks in the local context for an hypothesis which type is equal to -the goal. If it is the case, the subgoal is proved. Otherwise, it fails. + This tactic looks in the local context for an hypothesis which type is equal to + the goal. If it is the case, the subgoal is proved. Otherwise, it fails. -.. exn:: No such assumption. + .. exn:: No such assumption. -.. tacv:: eassumption + .. tacv:: eassumption + :name: eassumption -This tactic behaves like assumption but is able to handle goals with -meta-variables. + This tactic behaves like assumption but is able to handle goals with + meta-variables. .. tacn:: refine @term :name: refine -This tactic applies to any goal. It behaves like exact with a big -difference: the user can leave some holes (denoted by ``_`` or``(_:type)``) in -the term. refine will generate as many subgoals as there are holes in -the term. The type of holes must be either synthesized by the system -or declared by an explicit cast like ``(_:nat->Prop)``. Any subgoal that -occurs in other subgoals is automatically shelved, as if calling -shelve_unifiable (see Section 8.17.4). This low-level tactic can be -useful to advanced users. + This tactic applies to any goal. It behaves like :tacn:`exact` with a big + difference: the user can leave some holes (denoted by ``_`` or ``(_:type)``) in + the term. :tacn:`refine` will generate as many subgoals as there are holes in + the term. The type of holes must be either synthesized by the system + or declared by an explicit cast like ``(_:nat->Prop)``. Any subgoal that + occurs in other subgoals is automatically shelved, as if calling + :tacn:`shelve_unifiable`. This low-level tactic can be + useful to advanced users. -.. example:: - .. coqtop:: reset all + .. example:: + .. coqtop:: reset all - Inductive Option : Set := - | Fail : Option - | Ok : bool -> Option. + Inductive Option : Set := + | Fail : Option + | Ok : bool -> Option. - Definition get : forall x:Option, x <> Fail -> bool. + Definition get : forall x:Option, x <> Fail -> bool. - refine - (fun x:Option => - match x return x <> Fail -> bool with - | Fail => _ - | Ok b => fun _ => b - end). + refine + (fun x:Option => + match x return x <> Fail -> bool with + | Fail => _ + | Ok b => fun _ => b + end). - intros; absurd (Fail = Fail); trivial. + intros; absurd (Fail = Fail); trivial. - Defined. + Defined. -.. exn:: invalid argument + .. exn:: Invalid argument. - The tactic ``refine`` does not know what to do with the term you gave. + The tactic :tacn:`refine` does not know what to do with the term you gave. -.. exn:: Refine passed ill-formed term + .. exn:: Refine passed ill-formed term. - The term you gave is not a valid proof (not easy to debug in general). This - message may also occur in higher-level tactics that call ``refine`` - internally. + The term you gave is not a valid proof (not easy to debug in general). This + message may also occur in higher-level tactics that call :tacn:`refine` + internally. -.. exn:: Cannot infer a term for this placeholder + .. exn:: Cannot infer a term for this placeholder. + :name: Cannot infer a term for this placeholder. (refine) - There is a hole in the term you gave which type cannot be inferred. Put a - cast around it. + There is a hole in the term you gave whose type cannot be inferred. Put a + cast around it. -.. tacv:: simple refine @term + .. tacv:: simple refine @term + :name: simple refine - This tactic behaves like refine, but it does not shelve any subgoal. It does - not perform any beta-reduction either. + This tactic behaves like refine, but it does not shelve any subgoal. It does + not perform any beta-reduction either. -.. tacv:: notypeclasses refine @term + .. tacv:: notypeclasses refine @term + :name: notypeclasses refine - This tactic behaves like ``refine`` except it performs typechecking without - resolution of typeclasses. + This tactic behaves like :tacn:`refine` except it performs typechecking without + resolution of typeclasses. -.. tacv:: simple notypeclasses refine @term + .. tacv:: simple notypeclasses refine @term + :name: simple notypeclasses refine - This tactic behaves like ``simple refine`` except it performs typechecking - without resolution of typeclasses. + This tactic behaves like :tacn:`simple refine` except it performs typechecking + without resolution of typeclasses. -.. tacv:: apply @term +.. tacn:: apply @term :name: apply -This tactic applies to any goal. The argument term is a term well-formed in the -local context. The tactic apply tries to match the current goal against the -conclusion of the type of term. If it succeeds, then the tactic returns as many -subgoals as the number of non-dependent premises of the type of term. If the -conclusion of the type of term does not match the goal *and* the conclusion is -an inductive type isomorphic to a tuple type, then each component of the tuple -is recursively matched to the goal in the left-to-right order. + This tactic applies to any goal. The argument term is a term well-formed in the + local context. The tactic apply tries to match the current goal against the + conclusion of the type of term. If it succeeds, then the tactic returns as many + subgoals as the number of non-dependent premises of the type of term. If the + conclusion of the type of term does not match the goal *and* the conclusion is + an inductive type isomorphic to a tuple type, then each component of the tuple + is recursively matched to the goal in the left-to-right order. -The tactic ``apply`` relies on first-order unification with dependent types -unless the conclusion of the type of ``term`` is of the form :g:`P (t`:sub:`1` -:g:`...` :g:`t`:sub:`n` :g:`)` with `P` to be instantiated. In the latter case, the behavior -depends on the form of the goal. If the goal is of the form -:g:`(fun x => Q) u`:sub:`1` :g:`...` :g:`u`:sub:`n` and the :g:`t`:sub:`i` and -:g:`u`:sub:`i` unifies, then :g:`P` is taken to be :g:`(fun x => Q)`. Otherwise, -``apply`` tries to define :g:`P` by abstracting over :g:`t`:sub:`1` :g:`...` -:g:`t`:sub:`n` in the goal. See :tacn:`pattern` to transform the goal so that it -gets the form :g:`(fun x => Q) u`:sub:`1` :g:`...` :g:`u`:sub:`n`. + The tactic :tacn:`apply` relies on first-order unification with dependent types + unless the conclusion of the type of :token:`term` is of the form :g:`P (t`:sub:`1` + :g:`...` :g:`t`:sub:`n` :g:`)` with `P` to be instantiated. In the latter case, the behavior + depends on the form of the goal. If the goal is of the form + :g:`(fun x => Q) u`:sub:`1` :g:`...` :g:`u`:sub:`n` and the :g:`t`:sub:`i` and + :g:`u`:sub:`i` unifies, then :g:`P` is taken to be :g:`(fun x => Q)`. Otherwise, + :tacn:`apply` tries to define :g:`P` by abstracting over :g:`t`:sub:`1` :g:`...` + :g:`t`:sub:`n` in the goal. See :tacn:`pattern` to transform the goal so that it + gets the form :g:`(fun x => Q) u`:sub:`1` :g:`...` :g:`u`:sub:`n`. -.. exn:: Unable to unify ... with ... . + .. exn:: Unable to unify ... with ... . -The apply tactic failed to match the conclusion of term and the current goal. -You can help the apply tactic by transforming your goal with the -:ref:`change <change_term>` or :tacn:`pattern` tactics. + The apply tactic failed to match the conclusion of :token:`term` and the + current goal. You can help the apply tactic by transforming your goal with + the :tacn:`change` or :tacn:`pattern` tactics. -.. exn:: Unable to find an instance for the variables {+ @ident}. + .. exn:: Unable to find an instance for the variables {+ @ident}. -This occurs when some instantiations of the premises of term are not deducible -from the unification. This is the case, for instance, when you want to apply a -transitivity property. In this case, you have to use one of the variants below: + This occurs when some instantiations of the premises of :token:`term` are not deducible + from the unification. This is the case, for instance, when you want to apply a + transitivity property. In this case, you have to use one of the variants below: -.. cmd:: apply @term with {+ @term} + .. tacv:: apply @term with {+ @term} -Provides apply with explicit instantiations for all dependent premises of the -type of term that do not occur in the conclusion and consequently cannot be -found by unification. Notice that the collection :n:`{+ @term}` must be given -according to the order of these dependent premises of the type of term. + Provides apply with explicit instantiations for all dependent premises of the + type of term that do not occur in the conclusion and consequently cannot be + found by unification. Notice that the collection :n:`{+ @term}` must be given + according to the order of these dependent premises of the type of term. -.. exn:: Not the right number of missing arguments. + .. exn:: Not the right number of missing arguments. -.. tacv:: apply @term with @bindings_list + .. tacv:: apply @term with @bindings_list -This also provides apply with values for instantiating premises. Here, variables -are referred by names and non-dependent products by increasing numbers (see -:ref:`bindings list <bindingslist>`). + This also provides apply with values for instantiating premises. Here, variables + are referred by names and non-dependent products by increasing numbers (see + :ref:`bindings list <bindingslist>`). -.. tacv:: apply {+, @term} + .. tacv:: apply {+, @term} -This is a shortcut for ``apply term``:sub:`1` -``; [.. | ... ; [ .. | apply`` ``term``:sub:`n` ``] ... ]``, -i.e. for the successive applications of ``term``:sub:`i+1` on the last subgoal -generated by ``apply term``:sub:`i` , starting from the application of -``term``:sub:`1`. + This is a shortcut for :n:`apply @term`:sub:`1` + :n:`; [.. | ... ; [ .. | apply @term`:sub:`n` :n:`] ... ]`, + i.e. for the successive applications of :token:`term`:sub:`i+1` on the last subgoal + generated by :n:`apply @term`:sub:`i` , starting from the application of + :token:`term`:sub:`1`. -.. tacv:: eapply @term - :name: eapply + .. tacv:: eapply @term + :name: eapply -The tactic ``eapply`` behaves like ``apply`` but it does not fail when no -instantiations are deducible for some variables in the premises. Rather, it -turns these variables into existential variables which are variables still to -instantiate (see :ref:`TODO-2.11-ExistentialVariables`). The instantiation is -intended to be found later in the proof. + The tactic :tacn:`eapply` behaves like :tacn:`apply` but it does not fail when no + instantiations are deducible for some variables in the premises. Rather, it + turns these variables into existential variables which are variables still to + instantiate (see :ref:`Existential-Variables`). The instantiation is + intended to be found later in the proof. -.. tacv:: simple apply @term. + .. tacv:: simple apply @term. + :name: simple apply -This behaves like ``apply`` but it reasons modulo conversion only on subterms -that contain no variables to instantiate. For instance, the following example -does not succeed because it would require the conversion of ``id ?foo`` and -``O``. + This behaves like :tacn:`apply` but it reasons modulo conversion only on subterms + that contain no variables to instantiate. For instance, the following example + does not succeed because it would require the conversion of ``id ?foo`` and + :g:`O`. -.. example:: + .. example:: - .. coqtop:: all + .. coqtop:: all - Definition id (x : nat) := x. - Hypothesis H : forall y, id y = y. - Goal O = O. - Fail simple apply H. + Definition id (x : nat) := x. + Parameter H : forall y, id y = y. + Goal O = O. + Fail simple apply H. -Because it reasons modulo a limited amount of conversion, ``simple apply`` fails -quicker than ``apply`` and it is then well-suited for uses in user-defined -tactics that backtrack often. Moreover, it does not traverse tuples as ``apply`` -does. + Because it reasons modulo a limited amount of conversion, :tacn:`simple apply` fails + quicker than :tacn:`apply` and it is then well-suited for uses in user-defined + tactics that backtrack often. Moreover, it does not traverse tuples as :tacn:`apply` + does. -.. tacv:: {? simple} apply {+, @term {? with @bindings_list}} -.. tacv:: {? simple} eapply {+, @term {? with @bindings_list}} + .. tacv:: {? simple} apply {+, @term {? with @bindings_list}} + .. tacv:: {? simple} eapply {+, @term {? with @bindings_list}} + :name: simple eapply -This summarizes the different syntaxes for ``apply`` and ``eapply``. + This summarizes the different syntaxes for :tacn:`apply` and :tacn:`eapply`. -.. tacv:: lapply @term - :name: `lapply + .. tacv:: lapply @term + :name: lapply -This tactic applies to any goal, say :g:`G`. The argument term has to be -well-formed in the current context, its type being reducible to a non-dependent -product :g:`A -> B` with :g:`B` possibly containing products. Then it generates -two subgoals :g:`B->G` and :g:`A`. Applying ``lapply H`` (where :g:`H` has type -:g:`A->B` and :g:`B` does not start with a product) does the same as giving the -sequence ``cut B. 2:apply H.`` where ``cut`` is described below. + This tactic applies to any goal, say :g:`G`. The argument term has to be + well-formed in the current context, its type being reducible to a non-dependent + product :g:`A -> B` with :g:`B` possibly containing products. Then it generates + two subgoals :g:`B->G` and :g:`A`. Applying ``lapply H`` (where :g:`H` has type + :g:`A->B` and :g:`B` does not start with a product) does the same as giving the + sequence ``cut B. 2:apply H.`` where ``cut`` is described below. -.. warn:: When @term contains more than one non dependent product the tactic lapply only takes into account the first product. + .. warn:: When @term contains more than one non dependent product the tactic lapply only takes into account the first product. .. example:: Assume we have a transitive relation ``R`` on ``nat``: @@ -435,7 +445,7 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. ``forall A, ... -> A``. Excluding this kind of lemma can be avoided by setting the following option: -.. opt:: Set Universal Lemma Under Conjunction. +.. opt:: Universal Lemma Under Conjunction This option, which preserves compatibility with versions of Coq prior to 8.4 is also available for :n:`apply @term in @ident` (see :tacn:`apply ... in`). @@ -493,7 +503,7 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. .. tacv:: eapply {+, @term with @bindings_list} in @ident as @intro_pattern. - This works as :tacn:`apply ... in as` but using ``eapply``. + This works as :tacn:`apply ... in ... as` but using ``eapply``. .. tacv:: simple apply @term in @ident @@ -501,15 +511,15 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. on subterms that contain no variables to instantiate. For instance, if :g:`id := fun x:nat => x` and :g:`H: forall y, id y = y -> True` and :g:`H0 : O = O` then ``simple apply H in H0`` does not succeed because it - would require the conversion of :g:`id ?1234` and :g:`O` where :g:`?1234` is - a variable to instantiate. Tactic :n:`simple apply @term in @ident` does not + would require the conversion of :g:`id ?x` and :g:`O` where :g:`?x` is + an existential variable to instantiate. Tactic :n:`simple apply @term in @ident` does not either traverse tuples as :n:`apply @term in @ident` does. .. tacv:: {? simple} apply {+, @term {? with @bindings_list}} in @ident {? as @intro_pattern} .. tacv:: {? simple} eapply {+, @term {? with @bindings_list}} in @ident {? as @intro_pattern} - This summarizes the different syntactic variants of :n:`apply @term in - @ident` and :n:`eapply @term in @ident`. + This summarizes the different syntactic variants of :n:`apply @term in @ident` + and :n:`eapply @term in @ident`. .. tacn:: constructor @num :name: constructor @@ -539,14 +549,16 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. The terms in the @bindings_list are checked in the context where constructor is executed and not in the context where @apply is executed (the introductions are not taken into account). .. tacv:: split + :name: split This applies only if :g:`I` has a single constructor. It is then equivalent to :n:`constructor 1.`. It is typically used in the case of a conjunction :g:`A` :math:`\wedge` :g:`B`. -.. exn:: Not an inductive goal with 1 constructor. +.. exn:: Not an inductive goal with 1 constructor .. tacv:: exists @val + :name: exists This applies only if :g:`I` has a single constructor. It is then equivalent to :n:`intros; constructor 1 with @bindings_list.` It is typically used in @@ -559,7 +571,10 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. This iteratively applies :n:`exists @bindings_list`. .. tacv:: left + :name: left + .. tacv:: right + :name: right These tactics apply only if :g:`I` has two constructors, for instance in the case of a disjunction :g:`A` :math:`\vee` :g:`B`. @@ -577,15 +592,25 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. for the appropriate ``i``. .. tacv:: econstructor + :name: econstructor + .. tacv:: eexists + :name: eexists + .. tacv:: esplit + :name: esplit + .. tacv:: eleft + :name: eleft + .. tacv:: eright + :name: eright - These tactics and their variants behave like ``constructor``, ``exists``, - ``split``, ``left``, ``right`` and their variants but they introduce - existential variables instead of failing when the instantiation of a - variable cannot be found (cf. :tacn:`eapply` and :tacn:`apply`). + These tactics and their variants behave like :tacn:`constructor`, + :tacn:`exists`, :tacn:`split`, :tacn:`left`, :tacn:`right` and their variants + but they introduce existential variables instead of failing when the + instantiation of a variable cannot be found (cf. :tacn:`eapply` and + :tacn:`apply`). .. _managingthelocalcontext: @@ -598,48 +623,53 @@ Managing the local context This tactic applies to a goal that is either a product or starts with a let binder. If the goal is a product, the tactic implements the "Lam" rule given in -:ref:`TODO-4.2-Typing-rules` [1]_. If the goal starts with a let binder, then the +:ref:`Typing-rules` [1]_. If the goal starts with a let binder, then the tactic implements a mix of the "Let" and "Conv". -If the current goal is a dependent product :math:`\forall` :g:`x:T, U` (resp +If the current goal is a dependent product :g:`forall x:T, U` (resp :g:`let x:=t in U`) then ``intro`` puts :g:`x:T` (resp :g:`x:=t`) in the local context. The new subgoal is :g:`U`. If the goal is a non-dependent product :g:`T`:math:`\rightarrow`:g:`U`, then it puts in the local context either :g:`Hn:T` (if :g:`T` is of type :g:`Set` or -:g:`Prop`) or Xn:T (if the type of :g:`T` is :g:`Type`). The optional index +:g:`Prop`) or :g:`Xn:T` (if the type of :g:`T` is :g:`Type`). The optional index ``n`` is such that ``Hn`` or ``Xn`` is a fresh identifier. In both cases, the new subgoal is :g:`U`. -If the goal is neither a product nor starting with a let definition, +If the goal is an existential variable, ``intro`` forces the resolution of the +existential variable into a dependent product :math:`forall`:g:`x:?X, ?Y`, puts +:g:`x:?X` in the local context and leaves :g:`?Y` as a new subgoal allowed to +depend on :g:`x`. + the tactic ``intro`` applies the tactic ``hnf`` until the tactic ``intro`` can be applied or the goal is not head-reducible. .. exn:: No product even after head-reduction. -.. exn:: ident is already used. +.. exn:: @ident is already used. .. tacv:: intros + :name: intros This repeats ``intro`` until it meets the head-constant. It never reduces head-constants and it never fails. -.. tac:: intro @ident +.. tacn:: intro @ident This applies ``intro`` but forces :n:`@ident` to be the name of the introduced hypothesis. -.. exn:: name @ident is already used +.. exn:: Name @ident is already used. .. note:: If a name used by intro hides the base name of a global constant then the latter can still be referred to by a qualified name - (see :ref:`TODO-2.6.2-Qualified-names`). + (see :ref:`Qualified-names`). .. tacv:: intros {+ @ident}. This is equivalent to the composed tactic :n:`intro @ident; ... ; intro @ident`. More generally, the ``intros`` tactic takes a pattern as argument in order to introduce names for components of an inductive definition or to clear introduced hypotheses. This is - explained in :ref:`TODO-8.3.2`. + explained in :ref:`Managingthelocalcontext`. .. tacv:: intros until @ident @@ -647,7 +677,7 @@ be applied or the goal is not head-reducible. `(@ident:term)` and discharges the variable named `ident` of the current goal. -.. exn:: No such hypothesis in current goal +.. exn:: No such hypothesis in current goal. .. tacv:: intros until @num @@ -676,7 +706,7 @@ be applied or the goal is not head-reducible. too so as to respect the order of dependencies between hypotheses. Note that :n:`intro at bottom` is a synonym for :n:`intro` with no argument. -.. exn:: No such hypothesis : @ident. +.. exn:: No such hypothesis: @ident. .. tacv:: intro @ident after @ident .. tacv:: intro @ident before @ident @@ -685,7 +715,7 @@ be applied or the goal is not head-reducible. These tactics behave as previously but naming the introduced hypothesis :n:`@ident`. It is equivalent to :n:`intro @ident` followed by the - appropriate call to move (see :tacn:`move ... after`). + appropriate call to ``move`` (see :tacn:`move ... after ...`). .. tacn:: intros @intro_pattern_list :name: intros ... @@ -730,7 +760,7 @@ be applied or the goal is not head-reducible. Assuming a goal of type :g:`Q → P` (non-dependent product), or of type - :math:`\forall`:g:`x:T, P` (dependent product), the behavior of + :g:`forall x:T, P` (dependent product), the behavior of :n:`intros p` is defined inductively over the structure of the introduction pattern :n:`p`: @@ -827,15 +857,10 @@ quantification or an implication. so that all the arguments of the i-th constructors of the corresponding inductive type are introduced can be controlled with the following option: - .. cmd:: Set Bracketing Last Introduction Pattern. - - Force completion, if needed, when the last introduction pattern is a - disjunctive or conjunctive pattern (this is the default). + .. opt:: Bracketing Last Introduction Pattern - .. cmd:: Unset Bracketing Last Introduction Pattern. - - Deactivate completion when the last introduction pattern is a disjunctive or - conjunctive pattern. + Force completion, if needed, when the last introduction pattern is a + disjunctive or conjunctive pattern (on by default). .. tacn:: clear @ident :name: clear @@ -854,13 +879,6 @@ quantification or an implication. This is equivalent to :n:`clear @ident. ... clear @ident.` -.. tacv:: clearbody @ident - - This tactic expects :n:`@ident` to be a local definition then clears its - body. Otherwise said, this tactic turns a definition into an assumption. - -.. exn:: @ident is not a local definition - .. tacv:: clear - {+ @ident} This tactic clears all the hypotheses except the ones depending in the @@ -875,24 +893,33 @@ quantification or an implication. This clears the hypothesis :n:`@ident` and all the hypotheses that depend on it. +.. tacv:: clearbody {+ @ident} + :name: clearbody + + This tactic expects :n:`{+ @ident}` to be local definitions and clears their + respective bodies. + In other words, it turns the given definitions into assumptions. + +.. exn:: @ident is not a local definition. + .. tacn:: revert {+ @ident} - :name: revert ... + :name: revert -This applies to any goal with variables :n:`{+ @ident}`. It moves the hypotheses -(possibly defined) to the goal, if this respects dependencies. This tactic is -the inverse of :tacn:`intro`. + This applies to any goal with variables :n:`{+ @ident}`. It moves the hypotheses + (possibly defined) to the goal, if this respects dependencies. This tactic is + the inverse of :tacn:`intro`. .. exn:: No such hypothesis. .. exn:: @ident is used in the hypothesis @ident. -.. tac:: revert dependent @ident +.. tacn:: revert dependent @ident This moves to the goal the hypothesis :n:`@ident` and all the hypotheses that depend on it. .. tacn:: move @ident after @ident - :name: move .. after ... + :name: move ... after ... This moves the hypothesis named :n:`@ident` in the local context after the hypothesis named :n:`@ident`, where “after” is in reference to the @@ -926,9 +953,9 @@ the inverse of :tacn:`intro`. This moves ident at the bottom of the local context (at the end of the context). -.. exn:: No such hypothesis -.. exn:: Cannot move @ident after @ident : it occurs in the type of @ident -.. exn:: Cannot move @ident after @ident : it depends on @ident +.. exn:: No such hypothesis. +.. exn:: Cannot move @ident after @ident : it occurs in the type of @ident. +.. exn:: Cannot move @ident after @ident : it depends on @ident. .. example:: .. coqtop:: all @@ -944,7 +971,7 @@ the inverse of :tacn:`intro`. move H0 before H. .. tacn:: rename @ident into @ident - :name: rename ... into ... + :name: rename This renames hypothesis :n:`@ident` into :n:`@ident` in the current context. The name of the hypothesis in the proof-term, however, is left unchanged. @@ -955,8 +982,8 @@ The name of the hypothesis in the proof-term, however, is left unchanged. particular, the target identifiers may contain identifiers that exist in the source context, as long as the latter are also renamed by the same tactic. -.. exn:: No such hypothesis -.. exn:: @ident is already used +.. exn:: No such hypothesis. +.. exn:: @ident is already used. .. tacn:: set (@ident := @term) :name: set @@ -968,7 +995,7 @@ The name of the hypothesis in the proof-term, however, is left unchanged. first checks that all subterms matching the pattern are compatible before doing the replacement using the leftmost subterm matching the pattern. -.. exn:: The variable @ident is already defined +.. exn:: The variable @ident is already defined. .. tacv:: set (@ident := @term ) in @goal_occurrences @@ -992,6 +1019,7 @@ The name of the hypothesis in the proof-term, however, is left unchanged. .. tacv:: eset (@ident {+ @binder} := @term ) in @goal_occurrences .. tacv:: eset @term in @goal_occurrences + :name: eset While the different variants of :tacn:`set` expect that no existential variables are generated by the tactic, :n:`eset` removes this constraint. In @@ -999,6 +1027,7 @@ The name of the hypothesis in the proof-term, however, is left unchanged. :tacn:`epose`, i.e. when the :`@term` does not occur in the goal. .. tacv:: remember @term as @ident + :name: remember This behaves as :n:`set (@ident:= @term ) in *` and using a logical (Leibniz’s) equality instead of a local definition. @@ -1016,6 +1045,8 @@ The name of the hypothesis in the proof-term, however, is left unchanged. .. tacv:: eremember @term as @ident .. tacv:: eremember @term as @ident in @goal_occurrences .. tacv:: eremember @term as @ident eqn:@ident + :name: eremember + While the different variants of :n:`remember` expect that no existential variables are generated by the tactic, :n:`eremember` removes this constraint. @@ -1067,7 +1098,7 @@ The name of the hypothesis in the proof-term, however, is left unchanged. This decomposes record types (inductive types with one constructor, like "and" and "exists" and those defined with the Record macro, see - :ref:`TODO-2.1`). + :ref:`record-types`). .. _controllingtheproofflow: @@ -1082,24 +1113,25 @@ Controlling the proof flow :g:`U` [2]_. The subgoal :g:`U` comes first in the list of subgoals remaining to prove. -.. exn:: Not a proposition or a type +.. exn:: Not a proposition or a type. Arises when the argument form is neither of type :g:`Prop`, :g:`Set` nor :g:`Type`. .. tacv:: assert form - This behaves as :n:`assert (@ident : form ) but :n:`@ident` is generated by + This behaves as :n:`assert (@ident : form)` but :n:`@ident` is generated by Coq. -.. tacv:: assert form by tactic +.. tacv:: assert @form by @tactic This tactic behaves like :n:`assert` but applies tactic to solve the subgoals generated by assert. - .. exn:: Proof is not complete + .. exn:: Proof is not complete. + :name: Proof is not complete. (assert) -.. tacv:: assert form as intro_pattern +.. tacv:: assert @form as @intro_pattern If :n:`intro_pattern` is a naming introduction pattern (see :tacn:`intro`), the hypothesis is named after this introduction pattern (in particular, if @@ -1108,7 +1140,7 @@ Controlling the proof flow introduction pattern, the tactic behaves like :n:`assert form` followed by the action done by this introduction pattern. -.. tacv:: assert form as intro_pattern by tactic +.. tacv:: assert @form as @intro_pattern by @tactic This combines the two previous variants of :n:`assert`. @@ -1118,9 +1150,10 @@ Controlling the proof flow the type of :g:`term`. This is deprecated in favor of :n:`pose proof`. If the head of term is :n:`@ident`, the tactic behaves as :n:`specialize @term`. - .. exn:: Variable @ident is already declared + .. exn:: Variable @ident is already declared. .. tacv:: eassert form as intro_pattern by tactic + :name: eassert .. tacv:: assert (@ident := @term) @@ -1130,6 +1163,7 @@ Controlling the proof flow to prove it. .. tacv:: pose proof @term {? as intro_pattern} + :name: pose proof This tactic behaves like :n:`assert T {? as intro_pattern} by exact @term` where :g:`T` is the type of :g:`term`. In particular, @@ -1143,6 +1177,7 @@ Controlling the proof flow the tactic, :n:`epose proof` removes this constraint. .. tacv:: enough (@ident : form) + :name: enough This adds a new hypothesis of name :n:`@ident` asserting :n:`form` to the goal the tactic :n:`enough` is applied to. A new subgoal stating :n:`form` is @@ -1158,9 +1193,9 @@ Controlling the proof flow This behaves like :n:`enough form` using :n:`intro_pattern` to name or destruct the new hypothesis. -.. tacv:: enough (@ident : form) by tactic -.. tacv:: enough form by tactic -.. tacv:: enough form as intro_pattern by tactic +.. tacv:: enough (@ident : @form) by @tactic +.. tacv:: enough @form by @tactic +.. tacv:: enough @form as @intro_pattern by @tactic This behaves as above but with :n:`tactic` expected to solve the initial goal after the extra assumption :n:`form` is added and possibly destructed. If the @@ -1168,22 +1203,27 @@ Controlling the proof flow applied to all of them. .. tacv:: eenough (@ident : form) by tactic + :name: eenough + .. tacv:: eenough form by tactic + .. tacv:: eenough form as intro_pattern by tactic While the different variants of :n:`enough` expect that no existential variables are generated by the tactic, :n:`eenough` removes this constraint. -.. tacv:: cut form +.. tacv:: cut @form + :name: cut This tactic applies to any goal. It implements the non-dependent case of - the “App” rule given in :ref:`TODO-4.2`. (This is Modus Ponens inference + the “App” rule given in :ref:`typing-rules`. (This is Modus Ponens inference rule.) :n:`cut U` transforms the current goal :g:`T` into the two following subgoals: :g:`U -> T` and :g:`U`. The subgoal :g:`U -> T` comes first in the list of remaining subgoal to prove. .. tacv:: specialize (ident {* @term}) {? as intro_pattern} .. tacv:: specialize ident with @bindings_list {? as intro_pattern} + :name: specialize The tactic :n:`specialize` works on local hypothesis :n:`@ident`. The premises of this hypothesis (either universal quantifications or @@ -1202,8 +1242,8 @@ Controlling the proof flow the goal. The :n:`as` clause is especially useful in this case to immediately introduce the instantiated statement as a local hypothesis. - .. exn:: @ident is used in hypothesis @ident - .. exn:: @ident is used in conclusion + .. exn:: @ident is used in hypothesis @ident. + .. exn:: @ident is used in conclusion. .. tacn:: generalize @term :name: generalize @@ -1236,7 +1276,7 @@ name of the variable (here :g:`n`) is chosen based on :g:`T`. This is equivalent to :n:`generalize @term` but it generalizes only over the specified occurrences of :n:`@term` (counting from left to right on the - expression printed using option :g:`Set Printing All`). + expression printed using option :opt:`Printing All`). .. tacv:: generalize @term as @ident @@ -1268,7 +1308,7 @@ name of the variable (here :g:`n`) is chosen based on :g:`T`. :n:`refine @term` (preferred alternative). .. note:: To be able to refer to an existential variable by name, the user - must have given the name explicitly (see :ref:`TODO-2.11`). + must have given the name explicitly (see :ref:`Existential-Variables`). .. note:: When you are referring to hypotheses which you did not name explicitly, be aware that Coq may make a different decision on how to @@ -1327,7 +1367,7 @@ goals cannot be closed with :g:`Qed` but only with :g:`Admitted`. a singleton inductive type (e.g. :g:`True` or :g:`x=x`), or two contradictory hypotheses. -.. exn:: No such assumption +.. exn:: No such assumption. .. tacv:: contradiction @ident @@ -1353,11 +1393,13 @@ goals cannot be closed with :g:`Qed` but only with :g:`Admitted`. then required to prove that False is indeed provable in the current context. This tactic is a macro for :n:`elimtype False`. +.. _CaseAnalysisAndInduction: + Case analysis and induction ------------------------------- The tactics presented in this section implement induction or case -analysis on inductive or co-inductive objects (see :ref:`TODO-4.5`). +analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`). .. tacn:: destruct @term :name: destruct @@ -1423,6 +1465,7 @@ analysis on inductive or co-inductive objects (see :ref:`TODO-4.5`). dependent premises of the type of :n:`@term` (see :ref:`syntax of bindings <bindingslist>`). .. tacv:: edestruct @term + :name: edestruct This tactic behaves like :n:`destruct @term` except that it does not fail if the instance of a dependent premises of the type of :n:`@term` is not @@ -1449,6 +1492,7 @@ analysis on inductive or co-inductive objects (see :ref:`TODO-4.5`). the effects of the `with`, `as`, `eqn:`, `using`, and `in` clauses. .. tacv:: case term + :name: case The tactic :n:`case` is a more basic tactic to perform case analysis without recursion. It behaves as :n:`elim @term` but using a case-analysis @@ -1458,14 +1502,15 @@ analysis on inductive or co-inductive objects (see :ref:`TODO-4.5`). Analogous to :n:`elim @term with @bindings_list` above. -.. tacv:: ecase @term -.. tacv:: ecase @term with @bindings_list +.. tacv:: ecase @term {? with @bindings_list } + :name: ecase In case the type of :n:`@term` has dependent premises, or dependent premises whose values are not inferable from the :n:`with @bindings_list` clause, :n:`ecase` turns them into existential variables to be resolved later on. .. tacv:: simple destruct @ident + :name: simple destruct This tactic behaves as :n:`intros until @ident; case @ident` when :n:`@ident` is a quantified variable of the goal. @@ -1528,9 +1573,9 @@ analysis on inductive or co-inductive objects (see :ref:`TODO-4.5`). intros n H. induction n. -.. exn:: Not an inductive product +.. exn:: Not an inductive product. -.. exn:: Unable to find an instance for the variables @ident ... @ident +.. exn:: Unable to find an instance for the variables @ident ... @ident. Use in this case the variant :tacn:`elim ... with` below. @@ -1556,6 +1601,7 @@ analysis on inductive or co-inductive objects (see :ref:`TODO-4.5`). premises of the type of :n:`term` (see :ref:`bindings list <bindingslist>`). .. tacv:: einduction @term + :name: einduction This tactic behaves like :tacn:`induction` except that it does not fail if some dependent premise of the type of :n:`@term` is not inferable. Instead, @@ -1628,6 +1674,7 @@ analysis on inductive or co-inductive objects (see :ref:`TODO-4.5`). (see :ref:`bindings list <bindingslist>`). .. tacv:: eelim @term + :name: eelim In case the type of :n:`@term` has dependent premises, this turns them into existential variables to be resolved later on. @@ -1635,7 +1682,7 @@ analysis on inductive or co-inductive objects (see :ref:`TODO-4.5`). .. tacv:: elim @term using @term .. tacv:: elim @term using @term with @bindings_list - Allows the user to give explicitly an elimination predicate :n:`@term` that + Allows the user to give explicitly an induction principle :n:`@term` that is not the standard one for the underlying inductive type of :n:`@term`. The :n:`@bindings_list` clause allows instantiating premises of the type of :n:`@term`. @@ -1646,7 +1693,8 @@ analysis on inductive or co-inductive objects (see :ref:`TODO-4.5`). These are the most general forms of ``elim`` and ``eelim``. It combines the effects of the ``using`` clause and of the two uses of the ``with`` clause. -.. tacv:: elimtype form +.. tacv:: elimtype @form + :name: elimtype The argument :n:`form` must be inductively defined. :n:`elimtype I` is equivalent to :n:`cut I. intro Hn; elim Hn; clear Hn.` Therefore the @@ -1656,6 +1704,7 @@ analysis on inductive or co-inductive objects (see :ref:`TODO-4.5`). :n:`elimtype I; 2:exact t.` .. tacv:: simple induction @ident + :name: simple induction This tactic behaves as :n:`intros until @ident; elim @ident` when :n:`@ident` is a quantified variable of the goal. @@ -1740,13 +1789,14 @@ analysis on inductive or co-inductive objects (see :ref:`TODO-4.5`). other ones need not be further generalized. .. tacv:: dependent destruction @ident + :name: dependent destruction This performs the generalization of the instance :n:`@ident` but uses ``destruct`` instead of induction on the generalized hypothesis. This gives results equivalent to ``inversion`` or ``dependent inversion`` if the hypothesis is dependent. -See also :ref:`TODO-10.1-dependentinduction` for a larger example of ``dependent induction`` +See also the larger example of :tacn:`dependent induction` and an explanation of the underlying technique. .. tacn:: function induction (@qualid {+ @term}) @@ -1754,8 +1804,8 @@ and an explanation of the underlying technique. The tactic functional induction performs case analysis and induction following the definition of a function. It makes use of a principle - generated by ``Function`` (see :ref:`TODO-2.3-Advancedrecursivefunctions`) or - ``Functional Scheme`` (see :ref:`TODO-13.2-Generationofinductionschemeswithfunctionalscheme`). + generated by ``Function`` (see :ref:`advanced-recursive-functions`) or + ``Functional Scheme`` (see :ref:`functional-scheme`). Note that this tactic is only available after a .. example:: @@ -1781,26 +1831,26 @@ and an explanation of the underlying technique. :n:`functional induction (f x1 x2 x3)` is actually a wrapper for :n:`induction x1, x2, x3, (f x1 x2 x3) using @qualid` followed by a cleaning phase, where :n:`@qualid` is the induction principle registered for :g:`f` - (by the ``Function`` (see :ref:`TODO-2.3-Advancedrecursivefunctions`) or - ``Functional Scheme`` (see :ref:`TODO-13.2-Generationofinductionschemeswithfunctionalscheme`) + (by the ``Function`` (see :ref:`advanced-recursive-functions`) or + ``Functional Scheme`` (see :ref:`functional-scheme`) command) corresponding to the sort of the goal. Therefore ``functional induction`` may fail if the induction scheme :n:`@qualid` is not - defined. See also :ref:`TODO-2.3-Advancedrecursivefunctions` for the function + defined. See also :ref:`advanced-recursive-functions` for the function terms accepted by ``Function``. .. note:: There is a difference between obtaining an induction scheme - for a function by using :g:`Function` (see :ref:`TODO-2.3-Advancedrecursivefunctions`) + for a function by using :g:`Function` (see :ref:`advanced-recursive-functions`) and by using :g:`Functional Scheme` after a normal definition using - :g:`Fixpoint` or :g:`Definition`. See :ref:`TODO-2.3-Advancedrecursivefunctions` + :g:`Fixpoint` or :g:`Definition`. See :ref:`advanced-recursive-functions` for details. -See also: :ref:`TODO-2.3-Advancedrecursivefunctions` - :ref:`TODO-13.2-Generationofinductionschemeswithfunctionalscheme` +See also: :ref:`advanced-recursive-functions` + :ref:`functional-scheme` :tacn:`inversion` -.. exn:: Cannot find induction information on @qualid -.. exn:: Not the right number of induction arguments +.. exn:: Cannot find induction information on @qualid. +.. exn:: Not the right number of induction arguments. .. tacv:: functional induction (@qualid {+ @term}) as @disj_conj_intro_pattern using @term with @bindings_list @@ -1833,8 +1883,8 @@ See also: :ref:`TODO-2.3-Advancedrecursivefunctions` :n:`@ident` is first introduced in the local context using :n:`intros until @ident`. -.. exn:: No primitive equality found -.. exn:: Not a discriminable equality +.. exn:: No primitive equality found. +.. exn:: Not a discriminable equality. .. tacv:: discriminate @num @@ -1849,6 +1899,7 @@ See also: :ref:`TODO-2.3-Advancedrecursivefunctions` .. tacv:: ediscriminate @num .. tacv:: ediscriminate @term {? with @bindings_list} + :name: ediscriminate This works the same as ``discriminate`` but if the type of :n:`@term`, or the type of the hypothesis referred to by :n:`@num`, has uninstantiated @@ -1861,7 +1912,7 @@ See also: :ref:`TODO-2.3-Advancedrecursivefunctions` the form :n:`@term <> @term`, this behaves as :n:`intro @ident; discriminate @ident`. - .. exn:: No discriminable equalities + .. exn:: No discriminable equalities. .. tacn:: injection @term :name: injection @@ -1872,7 +1923,7 @@ See also: :ref:`TODO-2.3-Advancedrecursivefunctions` :g:`t`:sub:`1` and :g:`t`:sub:`2` are equal too. If :n:`@term` is a proof of a statement of conclusion :n:`@term = @term`, - then ``injection`` applies the injectivity of constructors as deep as + then :tacn:`injection` applies the injectivity of constructors as deep as possible to derive the equality of all the subterms of :n:`@term` and :n:`@term` at positions where the terms start to differ. For example, from :g:`(S p, S n) = (q, S (S m))` we may derive :g:`S p = q` and @@ -1882,90 +1933,96 @@ See also: :ref:`TODO-2.3-Advancedrecursivefunctions` equality of all the subterms at positions where they differ and adds them as antecedents to the conclusion of the current goal. -.. example:: + .. example:: - Consider the following goal: + Consider the following goal: - .. coqtop:: reset all + .. coqtop:: in - Inductive list : Set := - | nil : list - | cons : nat -> list -> list. - Variable P : list -> Prop. - Goal forall l n, P nil -> cons n l = cons 0 nil -> P l. - intros. - injection H0. + Inductive list : Set := + | nil : list + | cons : nat -> list -> list. + Parameter P : list -> Prop. + Goal forall l n, P nil -> cons n l = cons 0 nil -> P l. + .. coqtop:: all -Beware that injection yields an equality in a sigma type whenever the -injected object has a dependent type :g:`P` with its two instances in -different types :g:`(P t`:sub:`1` :g:`... t`:sub:`n` :g:`)` and -:g:`(P u`:sub:`1` :g:`... u`:sub:`n` :sub:`)`. If :g:`t`:sub:`1` and -:g:`u`:sub:`1` are the same and have for type an inductive type for which a decidable -equality has been declared using the command ``Scheme Equality`` (see :ref:`TODO-13.1-GenerationofinductionprincipleswithScheme`), -the use of a sigma type is avoided. + intros. + injection H0. -.. note:: - If some quantified hypothesis of the goal is named :n:`@ident`, - then :n:`injection @ident` first introduces the hypothesis in the local - context using :n:`intros until @ident`. + Beware that injection yields an equality in a sigma type whenever the + injected object has a dependent type :g:`P` with its two instances in + different types :g:`(P t`:sub:`1` :g:`... t`:sub:`n` :g:`)` and + :g:`(P u`:sub:`1` :g:`... u`:sub:`n` :sub:`)`. If :g:`t`:sub:`1` and + :g:`u`:sub:`1` are the same and have for type an inductive type for which a decidable + equality has been declared using the command :cmd:`Scheme Equality` + (see :ref:`proofschemes-induction-principles`), + the use of a sigma type is avoided. -.. exn:: Not a projectable equality but a discriminable one -.. exn:: Nothing to do, it is an equality between convertible @terms -.. exn:: Not a primitive equality -.. exn:: Nothing to inject + .. note:: + If some quantified hypothesis of the goal is named :n:`@ident`, + then :n:`injection @ident` first introduces the hypothesis in the local + context using :n:`intros until @ident`. -.. tacv:: injection @num + .. exn:: Not a projectable equality but a discriminable one. + .. exn:: Nothing to do, it is an equality between convertible @terms. + .. exn:: Not a primitive equality. + .. exn:: Nothing to inject. - This does the same thing as :n:`intros until @num` followed by - :n:`injection @ident` where :n:`@ident` is the identifier for the last - introduced hypothesis. + .. tacv:: injection @num -.. tacv:: injection @term with @bindings_list + This does the same thing as :n:`intros until @num` followed by + :n:`injection @ident` where :n:`@ident` is the identifier for the last + introduced hypothesis. - This does the same as :n:`injection @term` but using the given bindings to - instantiate parameters or hypotheses of :n:`@term`. + .. tacv:: injection @term with @bindings_list -.. tacv:: einjection @num -.. tacv:: einjection @term {? with @bindings_list} + This does the same as :n:`injection @term` but using the given bindings to + instantiate parameters or hypotheses of :n:`@term`. - This works the same as :n:`injection` but if the type of :n:`@term`, or the - type of the hypothesis referred to by :n:`@num`, has uninstantiated - parameters, these parameters are left as existential variables. + .. tacv:: einjection @num + :name: einjection + .. tacv:: einjection @term {? with @bindings_list} + + This works the same as :n:`injection` but if the type of :n:`@term`, or the + type of the hypothesis referred to by :n:`@num`, has uninstantiated + parameters, these parameters are left as existential variables. -.. tacv:: injection + .. tacv:: injection - If the current goal is of the form :n:`@term <> @term` , this behaves as - :n:`intro @ident; injection @ident`. + If the current goal is of the form :n:`@term <> @term` , this behaves as + :n:`intro @ident; injection @ident`. - .. exn:: goal does not satisfy the expected preconditions + .. exn:: goal does not satisfy the expected preconditions. -.. tacv:: injection @term {? with @bindings_list} as {+ @intro_pattern} -.. tacv:: injection @num as {+ intro_pattern} -.. tacv:: injection as {+ intro_pattern} -.. tacv:: einjection @term {? with @bindings_list} as {+ intro_pattern} -.. tacv:: einjection @num as {+ intro_pattern} -.. tacv:: einjection as {+ intro_pattern} + .. tacv:: injection @term {? with @bindings_list} as {+ @intro_pattern} + .. tacv:: injection @num as {+ intro_pattern} + .. tacv:: injection as {+ intro_pattern} + .. tacv:: einjection @term {? with @bindings_list} as {+ intro_pattern} + .. tacv:: einjection @num as {+ intro_pattern} + .. tacv:: einjection as {+ intro_pattern} These variants apply :n:`intros {+ @intro_pattern}` after the call to - ``injection`` or ``einjection`` so that all equalities generated are moved in + :tacn:`injection` or :tacn:`einjection` so that all equalities generated are moved in the context of hypotheses. The number of :n:`@intro_pattern` must not exceed the number of equalities newly generated. If it is smaller, fresh names are automatically generated to adjust the list of :n:`@intro_pattern` to the number of new equalities. The original equality is erased if it corresponds to an hypothesis. -It is possible to ensure that :n:`injection @term` erases the original -hypothesis and leaves the generated equalities in the context rather -than putting them as antecedents of the current goal, as if giving -:n:`injection @term as` (with an empty list of names). To obtain this -behavior, the option ``Set Structural Injection`` must be activated. This -option is off by default. + .. opt:: Structural Injection -By default, ``injection`` only creates new equalities between :n:`@terms` whose -type is in sort :g:`Type` or :g:`Set`, thus implementing a special behavior for -objects that are proofs of a statement in :g:`Prop`. This behavior can be -turned off by setting the option ``Set Keep Proof Equalities``. + This option ensure that :n:`injection @term` erases the original hypothesis + and leaves the generated equalities in the context rather than putting them + as antecedents of the current goal, as if giving :n:`injection @term as` + (with an empty list of names). This option is off by default. + + .. opt:: Keep Proof Equalities + + By default, :tacn:`injection` only creates new equalities between :n:`@terms` + whose type is in sort :g:`Type` or :g:`Set`, thus implementing a special + behavior for objects that are proofs of a statement in :g:`Prop`. This option + controls this behavior. .. tacn:: inversion @ident :name: inversion @@ -1984,15 +2041,15 @@ turned off by setting the option ``Set Keep Proof Equalities``. .. note:: As ``inversion`` proofs may be large in size, we recommend the user to stock the lemmas whenever the same instance needs to be - inverted several times. See :ref:`TODO-13.3-Generationofinversionprincipleswithderiveinversion`. + inverted several times. See :ref:`derive-inversion`. .. note:: Part of the behavior of the ``inversion`` tactic is to generate equalities between expressions that appeared in the hypothesis that is being processed. By default, no equalities are generated if they relate two proofs (i.e. equalities between :n:`@terms` whose type is in sort - :g:`Prop`). This behavior can be turned off by using the option ``Set Keep - Proof Equalities``. + :g:`Prop`). This behavior can be turned off by using the option + :opt`Keep Proof Equalities`. .. tacv:: inversion @num @@ -2093,13 +2150,13 @@ turned off by setting the option ``Set Keep Proof Equalities``. :n:`dependent inversion_clear @ident`. .. tacv:: dependent inversion @ident with @term - :name: dependent inversion ... + :name: dependent inversion ... with ... This variant allows you to specify the generalization of the goal. It is useful when the system fails to generalize the goal automatically. If - :n:`@ident` has type :g:`(I t)` and :g:`I` has type :math:`\forall` - :g:`(x:T), s`, then :n:`@term` must be of type :g:`I:`:math:`\forall` - :g:`(x:T), I x -> s'` where :g:`s'` is the type of the goal. + :n:`@ident` has type :g:`(I t)` and :g:`I` has type :g:`forall (x:T), s`, + then :n:`@term` must be of type :g:`I:forall (x:T), I x -> s'` where + :g:`s'` is the type of the goal. .. tacv:: dependent inversion @ident as @intro_pattern with @term @@ -2108,7 +2165,7 @@ turned off by setting the option ``Set Keep Proof Equalities``. .. tacv:: dependent inversion_clear @ident with @term - Like :tacn:`dependent inversion ...` with but clears :n:`@ident` from the + Like :tacn:`dependent inversion ... with ...` with but clears :n:`@ident` from the local context. .. tacv:: dependent inversion_clear @ident as @intro_pattern with @term @@ -2117,6 +2174,7 @@ turned off by setting the option ``Set Keep Proof Equalities``. :n:`dependent inversion_clear @ident with @term`. .. tacv:: simple inversion @ident + :name: simple inversion It is a very primitive inversion tactic that derives all the necessary equalities but it does not simplify the constraints as ``inversion`` does. @@ -2300,7 +2358,7 @@ turned off by setting the option ``Set Keep Proof Equalities``. arguments are correct is done only at the time of registering the lemma in the environment. To know if the use of induction hypotheses is correct at some time of the interactive development of a proof, use - the command ``Guarded`` (see :ref:`TODO-7.3.2-Guarded`). + the command ``Guarded`` (see Section :ref:`requestinginformation`). .. tacv:: fix @ident @num with {+ (ident {+ @binder} [{struct @ident}] : @type)} @@ -2321,7 +2379,7 @@ turned off by setting the option ``Set Keep Proof Equalities``. done only at the time of registering the lemma in the environment. To know if the use of coinduction hypotheses is correct at some time of the interactive development of a proof, use the command ``Guarded`` - (see :ref:`TODO-7.3.2-Guarded`). + (see Section :ref:`requestinginformation`). .. tacv:: cofix @ident with {+ (@ident {+ @binder} : @type)} @@ -2335,41 +2393,41 @@ Rewriting expressions --------------------- These tactics use the equality :g:`eq:forall A:Type, A->A->Prop` defined in -file ``Logic.v`` (see :ref:`TODO-3.1.2-Logic`). The notation for :g:`eq T t u` is +file ``Logic.v`` (see :ref:`coq-library-logic`). The notation for :g:`eq T t u` is simply :g:`t=u` dropping the implicit type of :g:`t` and :g:`u`. .. tacn:: rewrite @term :name: rewrite -This tactic applies to any goal. The type of :n:`@term` must have the form + This tactic applies to any goal. The type of :token:`term` must have the form -``forall (x``:sub:`1` ``:A``:sub:`1` ``) ... (x``:sub:`n` ``:A``:sub:`n` ``). eq term``:sub:`1` ``term``:sub:`2` ``.`` + ``forall (x``:sub:`1` ``:A``:sub:`1` ``) ... (x``:sub:`n` ``:A``:sub:`n` ``). eq term``:sub:`1` ``term``:sub:`2` ``.`` -where :g:`eq` is the Leibniz equality or a registered setoid equality. + where :g:`eq` is the Leibniz equality or a registered setoid equality. -Then :n:`rewrite @term` finds the first subterm matching `term`\ :sub:`1` in the goal, -resulting in instances `term`:sub:`1`' and `term`:sub:`2`' and then -replaces every occurrence of `term`:subscript:`1`' by `term`:subscript:`2`'. -Hence, some of the variables :g:`x`\ :sub:`i` are solved by unification, -and some of the types :g:`A`\ :sub:`1`:g:`, ..., A`\ :sub:`n` become new -subgoals. + Then :n:`rewrite @term` finds the first subterm matching `term`\ :sub:`1` in the goal, + resulting in instances `term`:sub:`1`' and `term`:sub:`2`' and then + replaces every occurrence of `term`:subscript:`1`' by `term`:subscript:`2`'. + Hence, some of the variables :g:`x`\ :sub:`i` are solved by unification, + and some of the types :g:`A`\ :sub:`1`:g:`, ..., A`\ :sub:`n` become new + subgoals. -.. exn:: The @term provided does not end with an equation + .. exn:: The @term provided does not end with an equation. -.. exn:: Tactic generated a subgoal identical to the original goal. This happens if @term does not occur in the goal. + .. exn:: Tactic generated a subgoal identical to the original goal. This happens if @term does not occur in the goal. -.. tacv:: rewrite -> @term + .. tacv:: rewrite -> @term - Is equivalent to :n:`rewrite @term` + Is equivalent to :n:`rewrite @term` -.. tacv:: rewrite <- @term + .. tacv:: rewrite <- @term - Uses the equality :n:`@term`:sub:`1` :n:`= @term` :sub:`2` from right to left + Uses the equality :n:`@term`:sub:`1` :n:`= @term` :sub:`2` from right to left -.. tacv:: rewrite @term in clause + .. tacv:: rewrite @term in clause - Analogous to :n:`rewrite @term` but rewriting is done following clause - (similarly to :ref:`performing computations <performingcomputations>`). For instance: + Analogous to :n:`rewrite @term` but rewriting is done following clause + (similarly to :ref:`performing computations <performingcomputations>`). For instance: + :n:`rewrite H in H`:sub:`1` will rewrite `H` in the hypothesis `H`:sub:`1` instead of the current goal. @@ -2378,218 +2436,215 @@ subgoals. In particular a failure will happen if any of these three simpler tactics fails. + :n:`rewrite H in * |-` will do :n:`rewrite H in H`:sub:`i` for all hypotheses - :g:`H`:sub:`i` :g:`<> H`. A success will happen as soon as at least one of these - simpler tactics succeeds. + :g:`H`:sub:`i` different from :g:`H`. + A success will happen as soon as at least one of these simpler tactics succeeds. + :n:`rewrite H in *` is a combination of :n:`rewrite H` and :n:`rewrite H in * |-` that succeeds if at least one of these two tactics succeeds. - Orientation :g:`->` or :g:`<-` can be inserted before the :n:`@term` to rewrite. + Orientation :g:`->` or :g:`<-` can be inserted before the :token:`term` to rewrite. -.. tacv:: rewrite @term at occurrences + .. tacv:: rewrite @term at occurrences - Rewrite only the given occurrences of :n:`@term`. Occurrences are - specified from left to right as for pattern (:tacn:`pattern`). The rewrite is - always performed using setoid rewriting, even for Leibniz’s equality, so one - has to ``Import Setoid`` to use this variant. + Rewrite only the given occurrences of :token:`term`. Occurrences are + specified from left to right as for pattern (:tacn:`pattern`). The rewrite is + always performed using setoid rewriting, even for Leibniz’s equality, so one + has to ``Import Setoid`` to use this variant. -.. tacv:: rewrite @term by tactic + .. tacv:: rewrite @term by tactic - Use tactic to completely solve the side-conditions arising from the - :tacn:`rewrite`. + Use tactic to completely solve the side-conditions arising from the + :tacn:`rewrite`. -.. tacv:: rewrite {+ @term} + .. tacv:: rewrite {+, @term} - Is equivalent to the `n` successive tactics :n:`{+ rewrite @term}`, each one - working on the first subgoal generated by the previous one. Orientation - :g:`->` or :g:`<-` can be inserted before each :n:`@term` to rewrite. One - unique clause can be added at the end after the keyword in; it will then - affect all rewrite operations. + Is equivalent to the `n` successive tactics :n:`{+; rewrite @term}`, each one + working on the first subgoal generated by the previous one. Orientation + :g:`->` or :g:`<-` can be inserted before each :token:`term` to rewrite. One + unique clause can be added at the end after the keyword in; it will then + affect all rewrite operations. - In all forms of rewrite described above, a :n:`@term` to rewrite can be - immediately prefixed by one of the following modifiers: + In all forms of rewrite described above, a :token:`term` to rewrite can be + immediately prefixed by one of the following modifiers: - + `?` : the tactic rewrite :n:`?@term` performs the rewrite of :n:`@term` as many - times as possible (perhaps zero time). This form never fails. - + `n?` : works similarly, except that it will do at most `n` rewrites. - + `!` : works as ?, except that at least one rewrite should succeed, otherwise - the tactic fails. - + `n!` (or simply `n`) : precisely `n` rewrites of :n:`@term` will be done, - leading to failure if these n rewrites are not possible. + + `?` : the tactic :n:`rewrite ?@term` performs the rewrite of :token:`term` as many + times as possible (perhaps zero time). This form never fails. + + :n:`@num?` : works similarly, except that it will do at most :token:`num` rewrites. + + `!` : works as `?`, except that at least one rewrite should succeed, otherwise + the tactic fails. + + :n:`@num!` (or simply :n:`@num`) : precisely :token:`num` rewrites of :token:`term` will be done, + leading to failure if these :token:`num` rewrites are not possible. -.. tacv:: erewrite @term + .. tacv:: erewrite @term + :name: erewrite - This tactic works as :n:`rewrite @term` but turning - unresolved bindings into existential variables, if any, instead of - failing. It has the same variants as :tacn:`rewrite` has. + This tactic works as :n:`rewrite @term` but turning + unresolved bindings into existential variables, if any, instead of + failing. It has the same variants as :tacn:`rewrite` has. -.. tacn:: replace @term with @term +.. tacn:: replace @term with @term’ :name: replace This tactic applies to any goal. It replaces all free occurrences of :n:`@term` - in the current goal with :n:`@term` and generates the equality :n:`@term = - @term` as a subgoal. This equality is automatically solved if it occurs among - the assumption, or if its symmetric form occurs. It is equivalent to - :n:`cut @term = @term; [intro H`:sub:`n` :n:`; rewrite <- H`:sub:`n` :n:`; clear H`:sub:`n`:n:`|| assumption || symmetry; try assumption]`. + in the current goal with :n:`@term’` and generates an equality :n:`@term = @term’` + as a subgoal. This equality is automatically solved if it occurs among + the assumptions, or if its symmetric form occurs. It is equivalent to + :n:`cut @term = @term’; [intro H`:sub:`n` :n:`; rewrite <- H`:sub:`n` :n:`; clear H`:sub:`n`:n:`|| assumption || symmetry; try assumption]`. -.. exn:: @terms do not have convertible types + .. exn:: Terms do not have convertible types. -.. tacv:: replace @term with @term by tactic + .. tacv:: replace @term with @term’ by @tactic - This acts as :n:`replace @term` with :n:`@term` but applies tactic to solve the generated - subgoal :n:`@term = @term`. + This acts as :n:`replace @term with @term’` but applies :token:`tactic` to solve the generated + subgoal :n:`@term = @term’`. -.. tacv:: replace @term + .. tacv:: replace @term - Replaces :n:`@term` with :n:`@term’` using the first assumption whose type has - the form :n:`@term = @term’` or :n:`@term’ = @term`. + Replaces :n:`@term` with :n:`@term’` using the first assumption whose type has + the form :n:`@term = @term’` or :n:`@term’ = @term`. -.. tacv:: replace -> @term + .. tacv:: replace -> @term - Replaces :n:`@term` with :n:`@term’` using the first assumption whose type has - the form :n:`@term = @term’` + Replaces :n:`@term` with :n:`@term’` using the first assumption whose type has + the form :n:`@term = @term’` -.. tacv:: replace <- @term + .. tacv:: replace <- @term - Replaces :n:`@term` with :n:`@term’` using the first assumption whose type has - the form :n:`@term’ = @term` + Replaces :n:`@term` with :n:`@term’` using the first assumption whose type has + the form :n:`@term’ = @term` -.. tacv:: replace @term with @term in clause -.. tacv:: replace @term with @term in clause by tactic -.. tacv:: replace @term in clause replace -> @term in clause -.. tacv:: replace <- @term in clause + .. tacv:: replace @term {? with @term} in clause {? by @tactic} + .. tacv:: replace -> @term in clause + .. tacv:: replace <- @term in clause - Acts as before but the replacements take place inclause (see - :ref:`performingcomputations`) and not only in the conclusion of the goal. The - clause argument must not contain any type of nor value of. + Acts as before but the replacements take place in the specified clause (see + :ref:`performingcomputations`) and not only in the conclusion of the goal. The + clause argument must not contain any ``type of`` nor ``value of``. -.. tacv:: cutrewrite <- (@term = @term) + .. tacv:: cutrewrite <- (@term = @term’) + :name: cutrewrite - This tactic is deprecated. It acts like :n:`replace @term with @term`, or, - equivalently as :n:`enough (@term = @term) as <-`. + This tactic is deprecated. It can be replaced by :n:`enough (@term = @term’) as <-`. -.. tacv:: cutrewrite -> (@term = @term) + .. tacv:: cutrewrite -> (@term = @term’) - This tactic is deprecated. It can be replaced by enough :n:`(@term = @term) as ->`. + This tactic is deprecated. It can be replaced by :n:`enough (@term = @term’) as ->`. .. tacn:: subst @ident :name: subst + This tactic applies to a goal that has :n:`@ident` in its context and (at + least) one hypothesis, say :g:`H`, of type :n:`@ident = t` or :n:`t = @ident` + with :n:`@ident` not occurring in :g:`t`. Then it replaces :n:`@ident` by + :g:`t` everywhere in the goal (in the hypotheses and in the conclusion) and + clears :n:`@ident` and :g:`H` from the context. -This tactic applies to a goal that has :n:`@ident` in its context and (at -least) one hypothesis, say :g:`H`, of type :n:`@ident = t` or :n:`t = @ident` -with :n:`@ident` not occurring in :g:`t`. Then it replaces :n:`@ident` by -:g:`t` everywhere in the goal (in the hypotheses and in the conclusion) and -clears :n:`@ident` and :g:`H` from the context. - -If :n:`@ident` is a local definition of the form :n:`@ident := t`, it is also -unfolded and cleared. + If :n:`@ident` is a local definition of the form :n:`@ident := t`, it is also + unfolded and cleared. + .. note:: + + When several hypotheses have the form :n:`@ident = t` or :n:`t = @ident`, the + first one is used. -.. note:: - When several hypotheses have the form :n:`@ident = t` or :n:`t = @ident`, the - first one is used. + + If :g:`H` is itself dependent in the goal, it is replaced by the proof of + reflexivity of equality. + .. tacv:: subst {+ @ident} -.. note:: - If `H` is itself dependent in the goal, it is replaced by the proof of - reflexivity of equality. + This is equivalent to :n:`subst @ident`:sub:`1`:n:`; ...; subst @ident`:sub:`n`. + .. tacv:: subst -.. tacv:: subst {+ @ident} + This applies subst repeatedly from top to bottom to all identifiers of the + context for which an equality of the form :n:`@ident = t` or :n:`t = @ident` + or :n:`@ident := t` exists, with :n:`@ident` not occurring in ``t``. - This is equivalent to :n:`subst @ident`:sub:`1`:n:`; ...; subst @ident`:sub:`n`. + .. opt:: Regular Subst Tactic -.. tacv:: subst + This option controls the behavior of :tacn:`subst`. When it is + activated (it is by default), :tacn:`subst` also deals with the following corner cases: - This applies subst repeatedly from top to bottom to all identifiers of the - context for which an equality of the form :n:`@ident = t` or :n:`t = @ident` - or :n:`@ident := t` exists, with :n:`@ident` not occurring in `t`. + + A context with ordered hypotheses :n:`@ident`:sub:`1` :n:`= @ident`:sub:`2` + and :n:`@ident`:sub:`1` :n:`= t`, or :n:`t′ = @ident`:sub:`1`` with `t′` not + a variable, and no other hypotheses of the form :n:`@ident`:sub:`2` :n:`= u` + or :n:`u = @ident`:sub:`2`; without the option, a second call to + subst would be necessary to replace :n:`@ident`:sub:`2` by `t` or + `t′` respectively. + + The presence of a recursive equation which without the option would + be a cause of failure of :tacn:`subst`. + + A context with cyclic dependencies as with hypotheses :n:`@ident`:sub:`1` :n:`= f @ident`:sub:`2` + and :n:`@ident`:sub:`2` :n:`= g @ident`:sub:`1` which without the + option would be a cause of failure of :tacn:`subst`. - .. note:: + Additionally, it prevents a local definition such as :n:`@ident := t` to be + unfolded which otherwise it would exceptionally unfold in configurations + containing hypotheses of the form :n:`@ident = u`, or :n:`u′ = @ident` + with `u′` not a variable. Finally, it preserves the initial order of + hypotheses, which without the option it may break. + default. - The behavior of subst can be controlled using option ``Set Regular Subst - Tactic.`` When this option is activated, subst also deals with the - following corner cases: - + A context with ordered hypotheses :n:`@ident`:sub:`1` :n:`= @ident`:sub:`2` - and :n:`@ident`:sub:`1` :n:`= t`, or :n:`t′ = @ident`:sub:`1`` with `t′` not - a variable, and no other hypotheses of the form :n:`@ident`:sub:`2` :n:`= u` - or :n:`u = @ident`:sub:`2`; without the option, a second call to - subst would be necessary to replace :n:`@ident`:sub:`2` by `t` or - `t′` respectively. - + The presence of a recursive equation which without the option would - be a cause of failure of :tacn:`subst`. - + A context with cyclic dependencies as with hypotheses :n:`@ident`:sub:`1` :n:`= f @ident`:sub:`2` - and :n:`@ident`:sub:`2` :n:`= g @ident`:sub:`1` which without the - option would be a cause of failure of :tacn:`subst`. +.. tacn:: stepl @term + :name: stepl - Additionally, it prevents a local definition such as :n:`@ident := t` to be - unfolded which otherwise it would exceptionally unfold in configurations - containing hypotheses of the form :n:`@ident = u`, or :n:`u′ = @ident` - with `u′` not a variable. Finally, it preserves the initial order of - hypotheses, which without the option it may break. The option is on by - default. + This tactic is for chaining rewriting steps. It assumes a goal of the + form :n:`R @term @term` where ``R`` is a binary relation and relies on a + database of lemmas of the form :g:`forall x y z, R x y -> eq x z -> R z y` + where `eq` is typically a setoid equality. The application of :n:`stepl @term` + then replaces the goal by :n:`R @term @term` and adds a new goal stating + :n:`eq @term @term`. + .. cmd:: Declare Left Step @term -.. tacn:: stepl @term - :name: stepl + Adds :n:`@term` to the database used by :tacn:`stepl`. + The tactic is especially useful for parametric setoids which are not accepted + as regular setoids for :tacn:`rewrite` and :tacn:`setoid_replace` (see + :ref:`Generalizedrewriting`). -This tactic is for chaining rewriting steps. It assumes a goal of the -form :n:`R @term @term` where `R` is a binary relation and relies on a -database of lemmas of the form :g:`forall x y z, R x y -> eq x z -> R z y` -where `eq` is typically a setoid equality. The application of :n:`stepl @term` -then replaces the goal by :n:`R @term @term` and adds a new goal stating -:n:`eq @term @term`. + .. tacv:: stepl @term by @tactic -Lemmas are added to the database using the command ``Declare Left Step @term.`` -The tactic is especially useful for parametric setoids which are not accepted -as regular setoids for :tacn:`rewrite` and :tacn:`setoid_replace` (see -:ref:`TODO-27-Generalizedrewriting`). + This applies :n:`stepl @term` then applies :token:`tactic` to the second goal. -.. tacv:: stepl @term by tactic + .. tacv:: stepr @term stepr @term by tactic + :name: stepr - This applies :n:`stepl @term` then applies tactic to the second goal. + This behaves as :tacn:`stepl` but on the right-hand-side of the binary + relation. Lemmas are expected to be of the form + :g:`forall x y z, R x y -> eq y z -> R x z`. -.. tacv:: stepr @term stepr @term by tactic + .. cmd:: Declare Right Step @term - This behaves as :tacn:`stepl` but on the right-hand-side of the binary - relation. Lemmas are expected to be of the form :g:`forall x y z, R x y -> eq - y z -> R x z` and are registered using the command ``Declare Right Step - @term.`` + Adds :n:`@term` to the database used by :tacn:`stepr`. .. tacn:: change @term :name: change - This tactic applies to any goal. It implements the rule ``Conv`` given in - :ref:`TODO-4.4-Subtypingrules`. :g:`change U` replaces the current goal `T` - with `U` providing that `U` is well-formed and that `T` and `U` are - convertible. - -.. exn:: Not convertible + This tactic applies to any goal. It implements the rule ``Conv`` given in + :ref:`subtyping-rules`. :g:`change U` replaces the current goal `T` + with `U` providing that `U` is well-formed and that `T` and `U` are + convertible. + .. exn:: Not convertible. -.. tacv:: change @term with @term + .. tacv:: change @term with @term’ - This replaces the occurrences of :n:`@term` by :n:`@term` in the current goal. - The term :n:`@term` and :n:`@term` must be convertible. + This replaces the occurrences of :n:`@term` by :n:`@term’` in the current goal. + The term :n:`@term` and :n:`@term’` must be convertible. -.. tacv:: change @term at {+ @num} with @term + .. tacv:: change @term at {+ @num} with @term’ - This replaces the occurrences numbered :n:`{+ @num}` of :n:`@term by @term` - in the current goal. The terms :n:`@term` and :n:`@term` must be convertible. + This replaces the occurrences numbered :n:`{+ @num}` of :n:`@term` by :n:`@term’` + in the current goal. The terms :n:`@term` and :n:`@term’` must be convertible. -.. exn:: Too few occurrences + .. exn:: Too few occurrences. -.. tacv:: change @term in @ident -.. tacv:: change @term with @term in @ident -.. tacv:: change @term at {+ @num} with @term in @ident + .. tacv:: change @term {? {? at {+ @num}} with @term} in @ident - This applies the change tactic not to the goal but to the hypothesis :n:`@ident`. + This applies the :tacn:`change` tactic not to the goal but to the hypothesis :n:`@ident`. -See also: :ref:`Performing computations <performingcomputations>` + .. seealso:: :ref:`Performing computations <performingcomputations>` .. _performingcomputations: @@ -2637,7 +2692,7 @@ the conversion in hypotheses :n:`{+ @ident}`. the normalization of the goal according to the specified flags. In correspondence with the kinds of reduction considered in Coq namely :math:`\beta` (reduction of functional application), :math:`\delta` - (unfolding of transparent constants, see :ref:`TODO-6.10.2-Transparent`), + (unfolding of transparent constants, see :ref:`vernac-controlling-the-reduction-strategies`), :math:`\iota` (reduction of pattern-matching over a constructed term, and unfolding of :g:`fix` and :g:`cofix` expressions) and :math:`\zeta` (contraction of local definitions), the @@ -2649,7 +2704,7 @@ the conversion in hypotheses :n:`{+ @ident}`. second case the constant to unfold to all but the ones explicitly mentioned. Notice that the ``delta`` flag does not apply to variables bound by a let-in construction inside the :n:`@term` itself (use here the ``zeta`` flag). In - any cases, opaque constants are not unfolded (see :ref:`TODO-6.10.1-Opaque`). + any cases, opaque constants are not unfolded (see :ref:`vernac-controlling-the-reduction-strategies`). Normalization according to the flags is done by first evaluating the head of the expression into a *weak-head* normal form, i.e. until the @@ -2704,6 +2759,7 @@ the conversion in hypotheses :n:`{+ @ident}`. and :n:`lazy beta delta -{+ @qualid} iota zeta`. .. tacv:: vm_compute + :name: vm_compute This tactic evaluates the goal using the optimized call-by-value evaluation bytecode-based virtual machine described in :cite:`CompiledStrongReduction`. @@ -2713,6 +2769,7 @@ the conversion in hypotheses :n:`{+ @ident}`. reflection-based tactics. .. tacv:: native_compute + :name: native_compute This tactic evaluates the goal by compilation to Objective Caml as described in :cite:`FullReduction`. If Coq is running in native code, it can be @@ -2754,7 +2811,7 @@ the conversion in hypotheses :n:`{+ @ident}`. definition (say :g:`t`) and then reduces :g:`(t t`:sub:`1` :g:`... t`:sub:`n` :g:`)` according to :math:`\beta`:math:`\iota`:math:`\zeta`-reduction rules. -.. exn:: Not reducible +.. exn:: Not reducible. .. tacn:: hnf :name: hnf @@ -2768,7 +2825,7 @@ the conversion in hypotheses :n:`{+ @ident}`. :n:`hnf`. .. note:: - The :math:`\delta` rule only applies to transparent constants (see :ref:`TODO-6.10.1-Opaque` + The :math:`\delta` rule only applies to transparent constants (see :ref:`vernac-controlling-the-reduction-strategies` on transparency and opacity). .. tacn:: cbn @@ -2811,8 +2868,8 @@ the conversion in hypotheses :n:`{+ @ident}`. .. coqtop:: all Definition fcomp A B C f (g : A -> B) (x : A) : C := f (g x). - Notation "f \o g" := (fcomp f g) (at level 50). Arguments fcomp {A B C} f g x /. + Notation "f \o g" := (fcomp f g) (at level 50). After that command the expression :g:`(f \o g)` is left untouched by ``simpl`` while :g:`((f \o g) t)` is reduced to :g:`(f (g t))`. @@ -2881,7 +2938,7 @@ the conversion in hypotheses :n:`{+ @ident}`. This applies ``simpl`` only to the :n:`{+ @num}` occurrences of the subterms matching :n:`@pattern` in the current goal. - .. exn:: Too few occurrences + .. exn:: Too few occurrences. .. tacv:: simpl @qualid .. tacv:: simpl @string @@ -2906,12 +2963,12 @@ the conversion in hypotheses :n:`{+ @ident}`. This tactic applies to any goal. The argument qualid must denote a defined transparent constant or local definition (see - :ref:`TODO-1.3.2-Definitions` and :ref:`TODO-6.10.2-Transparent`). The tactic + :ref:`gallina-definitions` and :ref:`vernac-controlling-the-reduction-strategies`). The tactic ``unfold`` applies the :math:`\delta` rule to each occurrence of the constant to which :n:`@qualid` refers in the current goal and then replaces it with its :math:`\beta`:math:`\iota`-normal form. -.. exn:: @qualid does not denote an evaluable constant +.. exn:: @qualid does not denote an evaluable constant. .. tacv:: unfold @qualid in @ident @@ -2928,9 +2985,9 @@ the conversion in hypotheses :n:`{+ @ident}`. The lists :n:`{+, @num}` specify the occurrences of :n:`@qualid` to be unfolded. Occurrences are located from left to right. - .. exn:: bad occurrence number of @qualid + .. exn:: Bad occurrence number of @qualid. - .. exn:: @qualid does not occur + .. exn:: @qualid does not occur. .. tacv:: unfold @string @@ -2942,7 +2999,7 @@ the conversion in hypotheses :n:`{+ @ident}`. This is variant of :n:`unfold @string` where :n:`@string` gets its interpretation from the scope bound to the delimiting key :n:`key` - instead of its default interpretation (see :ref:`TODO-12.2.2-Localinterpretationrulesfornotations`). + instead of its default interpretation (see :ref:`Localinterpretationrulesfornotations`). .. tacv:: unfold {+, qualid_or_string at {+, @num}} This is the most general form, where :n:`qualid_or_string` is either a @@ -3020,7 +3077,7 @@ Conversion tactics applied to hypotheses Example: :n:`unfold not in (Type of H1) (Type of H3)`. -.. exn:: No such hypothesis : ident. +.. exn:: No such hypothesis: @ident. .. _automation: @@ -3071,6 +3128,7 @@ hints of the database named core. to know what lemmas/assumptions were used. .. tacv:: debug auto + :name: debug auto Behaves like :tacn:`auto` but shows the tactics it tries to solve the goal, including failing paths. @@ -3090,7 +3148,9 @@ hints of the database named core. .. tacv:: trivial with * .. tacv:: trivial using {+ @lemma} .. tacv:: debug trivial + :name: debug trivial .. tacv:: info_trivial + :name: info_trivial .. tacv:: {? info_}trivial {? using {+ @lemma}} {? with {+ @ident}} .. note:: @@ -3103,7 +3163,7 @@ the :tacn:`auto` and :tacn:`trivial` tactics: .. opt:: Info Auto .. opt:: Debug Auto .. opt:: Info Trivial -.. opt:: Info Trivial +.. opt:: Debug Trivial See also: :ref:`The Hints Databases for auto and eauto <thehintsdatabasesforautoandeauto>` @@ -3123,7 +3183,7 @@ can solve such a goal: Goal forall P:nat -> Prop, P 0 -> exists n, P n. eauto. -Note that :tacn:`ex_intro` should be declared as a hint. +Note that ``ex_intro`` should be declared as a hint. .. tacv:: {? info_}eauto {? @num} {? using {+ @lemma}} {? with {+ @ident}} @@ -3169,7 +3229,9 @@ the processing of the rewriting rules. The rewriting rule bases are built with the ``Hint Rewrite vernacular`` command. -.. warn:: This tactic may loop if you build non terminating rewriting systems. +.. warning:: + + This tactic may loop if you build non terminating rewriting systems. .. tacv:: autorewrite with {+ @ident} using @tactic @@ -3200,7 +3262,8 @@ See also: :tacn:`autorewrite` for examples showing the use of this tactic. This tactic tries to solve the current goal by a number of standard closing steps. In particular, it tries to close the current goal using the closing tactics - :tacn:`trivial`, reflexivity, symmetry, contradiction and inversion of hypothesis. + :tacn:`trivial`, :tacn:`reflexivity`, :tacn:`symmetry`, :tacn:`contradiction` + and :tacn:`inversion` of hypothesis. If this fails, it tries introducing variables and splitting and-hypotheses, using the closing tactics afterwards, and splitting the goal using :tacn:`split` and recursing. @@ -3211,7 +3274,7 @@ See also: :tacn:`autorewrite` for examples showing the use of this tactic. .. tacv:: now @tactic :name: now - Run :n:`@tac` followed by ``easy``. This is a notation for :n:`@tactic; easy`. + Run :n:`@tactic` followed by :tacn:`easy`. This is a notation for :n:`@tactic; easy`. Controlling automation -------------------------- @@ -3221,225 +3284,245 @@ Controlling automation The hints databases for auto and eauto ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -The hints for ``auto`` and ``eauto`` are stored in databases. Each database -maps head symbols to a list of hints. One can use the command +The hints for :tacn:`auto` and :tacn:`eauto` are stored in databases. Each database +maps head symbols to a list of hints. .. cmd:: Print Hint @ident -to display the hints associated to the head symbol :n:`@ident` -(see :ref:`Print Hint <printhint>`). Each hint has a cost that is a nonnegative -integer, and an optional pattern. The hints with lower cost are tried first. A -hint is tried by ``auto`` when the conclusion of the current goal matches its -pattern or when it has no pattern. + Use this command + to display the hints associated to the head symbol :n:`@ident` + (see :ref:`Print Hint <printhint>`). Each hint has a cost that is a nonnegative + integer, and an optional pattern. The hints with lower cost are tried first. A + hint is tried by :tacn:`auto` when the conclusion of the current goal matches its + pattern or when it has no pattern. Creating Hint databases ``````````````````````` -One can optionally declare a hint database using the command ``Create -HintDb``. If a hint is added to an unknown database, it will be +One can optionally declare a hint database using the command +:cmd:`Create HintDb`. If a hint is added to an unknown database, it will be automatically created. -.. cmd:: Create HintDb @ident {? discriminated}. - -This command creates a new database named :n:`@ident`. The database is -implemented by a Discrimination Tree (DT) that serves as an index of -all the lemmas. The DT can use transparency information to decide if a -constant should be indexed or not (c.f. :ref:`The hints databases for auto and eauto <thehintsdatabasesforautoandeauto>`), -making the retrieval more efficient. The legacy implementation (the default one -for new databases) uses the DT only on goals without existentials (i.e., ``auto`` -goals), for non-Immediate hints and do not make use of transparency -hints, putting more work on the unification that is run after -retrieval (it keeps a list of the lemmas in case the DT is not used). -The new implementation enabled by the discriminated option makes use -of DTs in all cases and takes transparency information into account. -However, the order in which hints are retrieved from the DT may differ -from the order in which they were inserted, making this implementation -observationally different from the legacy one. +.. cmd:: Create HintDb @ident {? discriminated} + + This command creates a new database named :n:`@ident`. The database is + implemented by a Discrimination Tree (DT) that serves as an index of + all the lemmas. The DT can use transparency information to decide if a + constant should be indexed or not + (c.f. :ref:`The hints databases for auto and eauto <thehintsdatabasesforautoandeauto>`), + making the retrieval more efficient. The legacy implementation (the default one + for new databases) uses the DT only on goals without existentials (i.e., :tacn:`auto` + goals), for non-Immediate hints and do not make use of transparency + hints, putting more work on the unification that is run after + retrieval (it keeps a list of the lemmas in case the DT is not used). + The new implementation enabled by the discriminated option makes use + of DTs in all cases and takes transparency information into account. + However, the order in which hints are retrieved from the DT may differ + from the order in which they were inserted, making this implementation + observationally different from the legacy one. The general command to add a hint to some databases :n:`{+ @ident}` is -.. cmd:: Hint hint_definition : {+ @ident} +.. cmd:: Hint @hint_definition : {+ @ident} -**Variants:** + .. cmdv:: Hint @hint_definition + + No database name is given: the hint is registered in the core database. + + .. cmdv:: Local Hint @hint_definition : {+ @ident} + + This is used to declare hints that must not be exported to the other modules + that require and import the current module. Inside a section, the option + Local is useless since hints do not survive anyway to the closure of + sections. + + .. cmdv:: Local Hint @hint_definition -.. cmd:: Hint hint_definition + Idem for the core database. - No database name is given: the hint is registered in the core database. + .. cmdv:: Hint Resolve @term {? | {? @num} {? @pattern}} + :name: Hint Resolve -.. cmd:: Local Hint hint_definition : {+ @ident} + This command adds :n:`simple apply @term` to the hint list with the head + symbol of the type of :n:`@term`. The cost of that hint is the number of + subgoals generated by :n:`simple apply @term` or :n:`@num` if specified. The + associated :n:`@pattern` is inferred from the conclusion of the type of + :n:`@term` or the given :n:`@pattern` if specified. In case the inferred type + of :n:`@term` does not start with a product the tactic added in the hint list + is :n:`exact @term`. In case this type can however be reduced to a type + starting with a product, the tactic :n:`simple apply @term` is also stored in + the hints list. If the inferred type of :n:`@term` contains a dependent + quantification on a variable which occurs only in the premisses of the type + and not in its conclusion, no instance could be inferred for the variable by + unification with the goal. In this case, the hint is added to the hint list + of :tacn:`eauto` instead of the hint list of auto and a warning is printed. A + typical example of a hint that is used only by :tacn:`eauto` is a transitivity + lemma. - This is used to declare hints that must not be exported to the other modules - that require and import the current module. Inside a section, the option - Local is useless since hints do not survive anyway to the closure of - sections. + .. exn:: @term cannot be used as a hint -.. cmd:: Local Hint hint_definition + The head symbol of the type of :n:`@term` is a bound variable such that + this tactic cannot be associated to a constant. - Idem for the core database. + .. cmdv:: Hint Resolve {+ @term} -The ``hint_definition`` is one of the following expressions: + Adds each :n:`Hint Resolve @term`. -+ :n:`Resolve @term {? | {? @num} {? @pattern}}` - This command adds :n:`simple apply @term` to the hint list with the head symbol of the type of - :n:`@term`. The cost of that hint is the number of subgoals generated by - :n:`simple apply @term` or :n:`@num` if specified. The associated :n:`@pattern` - is inferred from the conclusion of the type of :n:`@term` or the given - :n:`@pattern` if specified. In case the inferred type of :n:`@term` does not - start with a product the tactic added in the hint list is :n:`exact @term`. - In case this type can however be reduced to a type starting with a product, - the tactic :n:`simple apply @term` is also stored in the hints list. If the - inferred type of :n:`@term` contains a dependent quantification on a variable - which occurs only in the premisses of the type and not in its conclusion, no - instance could be inferred for the variable by unification with the goal. In - this case, the hint is added to the hint list of :tacn:`eauto` instead of the - hint list of auto and a warning is printed. A typical example of a hint that - is used only by ``eauto`` is a transitivity lemma. + .. cmdv:: Hint Resolve -> @term - .. exn:: @term cannot be used as a hint + Adds the left-to-right implication of an equivalence as a hint (informally + the hint will be used as :n:`apply <- @term`, although as mentionned + before, the tactic actually used is a restricted version of + :tacn:`apply`). - The head symbol of the type of :n:`@term` is a bound variable such that - this tactic cannot be associated to a constant. + .. cmdv:: Resolve <- @term - **Variants:** + Adds the right-to-left implication of an equivalence as a hint. - + :n:`Resolve {+ @term}` - Adds each :n:`Resolve @term`. + .. cmdv:: Hint Immediate @term + :name: Hint Immediate - + :n:`Resolve -> @term` - Adds the left-to-right implication of an equivalence as a hint (informally - the hint will be used as :n:`apply <- @term`, although as mentionned - before, the tactic actually used is a restricted version of ``apply``). + This command adds :n:`simple apply @term; trivial` to the hint list associated + with the head symbol of the type of :n:`@ident` in the given database. This + tactic will fail if all the subgoals generated by :n:`simple apply @term` are + not solved immediately by the :tacn:`trivial` tactic (which only tries tactics + with cost 0).This command is useful for theorems such as the symmetry of + equality or :g:`n+1=m+1 -> n=m` that we may like to introduce with a limited + use in order to avoid useless proof-search. The cost of this tactic (which + never generates subgoals) is always 1, so that it is not used by :tacn:`trivial` + itself. - + :n:`Resolve <- @term` - Adds the right-to-left implication of an equivalence as a hint. + .. exn:: @term cannot be used as a hint -+ :n:`Immediate @term` - This command adds :n:`simple apply @term; trivial` to the hint list associated - with the head symbol of the type of :n:`@ident` in the given database. This - tactic will fail if all the subgoals generated by :n:`simple apply @term` are - not solved immediately by the ``trivial`` tactic (which only tries tactics - with cost 0).This command is useful for theorems such as the symmetry of - equality or :g:`n+1=m+1 -> n=m` that we may like to introduce with a limited - use in order to avoid useless proof-search.The cost of this tactic (which - never generates subgoals) is always 1, so that it is not used by ``trivial`` - itself. + .. cmdv:: Immediate {+ @term} - .. exn:: @term cannot be used as a hint + Adds each :n:`Hint Immediate @term`. - **Variants:** + .. cmdv:: Hint Constructors @ident + :name: Hint Constructors - + :n:`Immediate {+ @term}` - Adds each :n:`Immediate @term`. + If :n:`@ident` is an inductive type, this command adds all its constructors as + hints of type ``Resolve``. Then, when the conclusion of current goal has the form + :n:`(@ident ...)`, :tacn:`auto` will try to apply each constructor. -+ :n:`Constructors @ident` - If :n:`@ident` is an inductive type, this command adds all its constructors as - hints of type Resolve. Then, when the conclusion of current goal has the form - :n:`(@ident ...)`, ``auto`` will try to apply each constructor. + .. exn:: @ident is not an inductive type - .. exn:: @ident is not an inductive type + .. cmdv:: Hint Constructors {+ @ident} - **Variants:** + Adds each :n:`Hint Constructors @ident`. - + :n:`Constructors {+ @ident}` - Adds each :n:`Constructors @ident`. + .. cmdv:: Hint Unfold @qualid + :name: Hint Unfold -+ :n:`Unfold @qualid` - This adds the tactic :n:`unfold @qualid` to the hint list that will only be - used when the head constant of the goal is :n:`@ident`. - Its cost is 4. + This adds the tactic :n:`unfold @qualid` to the hint list that will only be + used when the head constant of the goal is :n:`@ident`. + Its cost is 4. - **Variants:** + .. cmdv:: Hint Unfold {+ @ident} - + :n:`Unfold {+ @ident}` - Adds each :n:`Unfold @ident`. + Adds each :n:`Hint Unfold @ident`. -+ :n:`Transparent`, :n:`Opaque @qualid` - This adds a transparency hint to the database, making :n:`@qualid` a - transparent or opaque constant during resolution. This information is used - during unification of the goal with any lemma in the database and inside the - discrimination network to relax or constrain it in the case of discriminated - databases. + .. cmdv:: Hint %( Transparent %| Opaque %) @qualid + :name: Hint ( Transparent | Opaque ) - **Variants:** + This adds a transparency hint to the database, making :n:`@qualid` a + transparent or opaque constant during resolution. This information is used + during unification of the goal with any lemma in the database and inside the + discrimination network to relax or constrain it in the case of discriminated + databases. + + .. cmdv:: Hint %( Transparent %| Opaque %) {+ @ident} - + :n:`Transparent`, :n:`Opaque {+ @ident}` Declares each :n:`@ident` as a transparent or opaque constant. -+ :n:`Extern @num {? @pattern} => tactic` - This hint type is to extend ``auto`` with tactics other than ``apply`` and - ``unfold``. For that, we must specify a cost, an optional :n:`@pattern` and a - :n:`tactic` to execute. Here is an example:: - - Hint Extern 4 (~(_ = _)) => discriminate. - - Now, when the head of the goal is a disequality, ``auto`` will try - discriminate if it does not manage to solve the goal with hints with a - cost less than 4. One can even use some sub-patterns of the pattern in - the tactic script. A sub-pattern is a question mark followed by an - identifier, like ``?X1`` or ``?X2``. Here is an example: - - .. example:: - .. coqtop:: reset all - - Require Import List. - Hint Extern 5 ({?X1 = ?X2} + {?X1 <> ?X2}) => generalize X1, X2; decide equality : eqdec. - Goal forall a b:list (nat * nat), {a = b} + {a <> b}. - Info 1 auto with eqdec. - -+ :n:`Cut @regexp` - - .. warning:: these hints currently only apply to typeclass - proof search and the ``typeclasses eauto`` tactic (:ref:`TODO-20.6.5-typeclasseseauto`). - - This command can be used to cut the proof-search tree according to a regular - expression matching paths to be cut. The grammar for regular expressions is - the following. Beware, there is no operator precedence during parsing, one can - check with ``Print HintDb`` to verify the current cut expression: - - .. productionlist:: `regexp` - e : ident hint or instance identifier - :|_ any hint - :| e\|e′ disjunction - :| e e′ sequence - :| e * Kleene star - :| emp empty - :| eps epsilon - :| ( e ) - - The `emp` regexp does not match any search path while `eps` - matches the empty path. During proof search, the path of - successive successful hints on a search branch is recorded, as a - list of identifiers for the hints (note Hint Extern’s do not have - an associated identifier). - Before applying any hint :n:`@ident` the current path `p` extended with - :n:`@ident` is matched against the current cut expression `c` associated to - the hint database. If matching succeeds, the hint is *not* applied. The - semantics of ``Hint Cut e`` is to set the cut expression to ``c | e``, the - initial cut expression being `emp`. - -+ :n:`Mode @qualid {* (+ | ! | -)}` - This sets an optional mode of use of the identifier :n:`@qualid`. When - proof-search faces a goal that ends in an application of :n:`@qualid` to - arguments :n:`@term ... @term`, the mode tells if the hints associated to - :n:`@qualid` can be applied or not. A mode specification is a list of n ``+``, - ``!`` or ``-`` items that specify if an argument of the identifier is to be - treated as an input (``+``), if its head only is an input (``!``) or an output - (``-``) of the identifier. For a mode to match a list of arguments, input - terms and input heads *must not* contain existential variables or be - existential variables respectively, while outputs can be any term. Multiple - modes can be declared for a single identifier, in that case only one mode - needs to match the arguments for the hints to be applied.The head of a term - is understood here as the applicative head, or the match or projection - scrutinee’s head, recursively, casts being ignored. ``Hint Mode`` is - especially useful for typeclasses, when one does not want to support default - instances and avoid ambiguity in general. Setting a parameter of a class as an - input forces proof-search to be driven by that index of the class, with ``!`` - giving more flexibility by allowing existentials to still appear deeper in the - index but not at its head. + .. cmdv:: Hint Extern @num {? @pattern} => @tactic + :name: Hint Extern -.. note:: - One can use an ``Extern`` hint with no pattern to do pattern-matching on - hypotheses using ``match goal`` with inside the tactic. + This hint type is to extend :tacn:`auto` with tactics other than :tacn:`apply` and + :tacn:`unfold`. For that, we must specify a cost, an optional :n:`@pattern` and a + :n:`@tactic` to execute. + + .. example:: + + .. coqtop:: in + + Hint Extern 4 (~(_ = _)) => discriminate. + + Now, when the head of the goal is a disequality, ``auto`` will try + discriminate if it does not manage to solve the goal with hints with a + cost less than 4. + + One can even use some sub-patterns of the pattern in + the tactic script. A sub-pattern is a question mark followed by an + identifier, like ``?X1`` or ``?X2``. Here is an example: + + .. example:: + + .. coqtop:: reset all + + Require Import List. + Hint Extern 5 ({?X1 = ?X2} + {?X1 <> ?X2}) => generalize X1, X2; decide equality : eqdec. + Goal forall a b:list (nat * nat), {a = b} + {a <> b}. + Info 1 auto with eqdec. + + .. cmdv:: Hint Cut @regexp + + .. warning:: + + These hints currently only apply to typeclass proof search and the + :tacn:`typeclasses eauto` tactic. + + This command can be used to cut the proof-search tree according to a regular + expression matching paths to be cut. The grammar for regular expressions is + the following. Beware, there is no operator precedence during parsing, one can + check with :cmd:`Print HintDb` to verify the current cut expression: + + .. productionlist:: `regexp` + e : ident hint or instance identifier + :| _ any hint + :| e\|e′ disjunction + :| e e′ sequence + :| e * Kleene star + :| emp empty + :| eps epsilon + :| ( e ) + + The `emp` regexp does not match any search path while `eps` + matches the empty path. During proof search, the path of + successive successful hints on a search branch is recorded, as a + list of identifiers for the hints (note Hint Extern’s do not have + an associated identifier). + Before applying any hint :n:`@ident` the current path `p` extended with + :n:`@ident` is matched against the current cut expression `c` associated to + the hint database. If matching succeeds, the hint is *not* applied. The + semantics of ``Hint Cut e`` is to set the cut expression to ``c | e``, the + initial cut expression being `emp`. + + .. cmdv:: Hint Mode @qualid {* (+ | ! | -)} + + This sets an optional mode of use of the identifier :n:`@qualid`. When + proof-search faces a goal that ends in an application of :n:`@qualid` to + arguments :n:`@term ... @term`, the mode tells if the hints associated to + :n:`@qualid` can be applied or not. A mode specification is a list of n ``+``, + ``!`` or ``-`` items that specify if an argument of the identifier is to be + treated as an input (``+``), if its head only is an input (``!``) or an output + (``-``) of the identifier. For a mode to match a list of arguments, input + terms and input heads *must not* contain existential variables or be + existential variables respectively, while outputs can be any term. Multiple + modes can be declared for a single identifier, in that case only one mode + needs to match the arguments for the hints to be applied.The head of a term + is understood here as the applicative head, or the match or projection + scrutinee’s head, recursively, casts being ignored. ``Hint Mode`` is + especially useful for typeclasses, when one does not want to support default + instances and avoid ambiguity in general. Setting a parameter of a class as an + input forces proof-search to be driven by that index of the class, with ``!`` + giving more flexibility by allowing existentials to still appear deeper in the + index but not at its head. + + .. note:: + + One can use an ``Extern`` hint with no pattern to do pattern-matching on + hypotheses using ``match goal`` with inside the tactic. Hint databases defined in the Coq standard library @@ -3521,7 +3604,7 @@ at every moment. (left to right). Notice that the rewriting bases are distinct from the ``auto`` hint bases and thatauto does not take them into account. - This command is synchronous with the section mechanism (see :ref:`TODO-2.4-Sectionmechanism`): + This command is synchronous with the section mechanism (see :ref:`section-mechanism`): when closing a section, all aliases created by ``Hint Rewrite`` in that section are lost. Conversely, when loading a module, all ``Hint Rewrite`` declarations at the global level of that module are loaded. @@ -3561,7 +3644,7 @@ described above: either they disappear at the end of a section scope, or they remain global forever. This causes a scalability issue, because hints coming from an unrelated part of the code may badly influence another development. It can be mitigated to some extent -thanks to the ``Remove Hints`` command (see :ref:`Remove Hints <removehints>`), +thanks to the :cmd:`Remove Hints` command, but this is a mere workaround and has some limitations (for instance, external hints cannot be removed). @@ -3569,73 +3652,75 @@ A proper way to fix this issue is to bind the hints to their module scope, as for most of the other objects Coq uses. Hints should only made available when the module they are defined in is imported, not just required. It is very difficult to change the historical behavior, as it would break a lot of scripts. -We propose a smooth transitional path by providing the ``Loose Hint Behavior`` +We propose a smooth transitional path by providing the :opt:`Loose Hint Behavior` option which accepts three flags allowing for a fine-grained handling of non-imported hints. -**Variants:** - -.. cmd:: Set Loose Hint Behavior "Lax" +.. opt:: Loose Hint Behavior %( "Lax" %| "Warn" %| "Strict" %) + :name: Loose Hint Behavior - This is the default, and corresponds to the historical behavior, that - is, hints defined outside of a section have a global scope. + This option accepts three values, which control the behavior of hints w.r.t. + :cmd:`Import`: -.. cmd:: Set Loose Hint Behavior "Warn" + - "Lax": this is the default, and corresponds to the historical behavior, + that is, hints defined outside of a section have a global scope. - When set, it outputs a warning when a non-imported hint is used. Note that - this is an over-approximation, because a hint may be triggered by a run that - will eventually fail and backtrack, resulting in the hint not being actually - useful for the proof. + - "Warn": outputs a warning when a non-imported hint is used. Note that this + is an over-approximation, because a hint may be triggered by a run that + will eventually fail and backtrack, resulting in the hint not being + actually useful for the proof. -.. cmd:: Set Loose Hint Behavior "Strict" + - "Strict": changes the behavior of an unloaded hint to a immediate fail + tactic, allowing to emulate an import-scoped hint mechanism. - When set, it changes the behavior of an unloaded hint to a immediate fail - tactic, allowing to emulate an import-scoped hint mechanism. +.. _tactics-implicit-automation: Setting implicit automation tactics ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -.. cmd:: Proof with tactic +.. cmd:: Proof with @tactic This command may be used to start a proof. It defines a default tactic to be used each time a tactic command ``tactic``:sub:`1` is ended by ``...``. In this case the tactic command typed by the user is equivalent to ``tactic``:sub:`1` ``;tactic``. -See also: Proof. in :ref:`TODO-7.1.4-Proofterm`. + See also: ``Proof.`` in :ref:`proof-editing-mode`. -**Variants:** -.. cmd:: Proof with tactic using {+ @ident} + .. cmdv:: Proof with tactic using {+ @ident} - Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`TODO-7.1.5-Proofusing` + Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`proof-editing-mode` -.. cmd:: Proof using {+ @ident} with tactic + .. cmdv:: Proof using {+ @ident} with @tactic - Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`TODO-7.1.5-Proofusing` + Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`proof-editing-mode` -.. cmd:: Declare Implicit Tactic tactic + .. cmd:: Declare Implicit Tactic @tactic - This command declares a tactic to be used to solve implicit arguments - that Coq does not know how to solve by unification. It is used every - time the term argument of a tactic has one of its holes not fully - resolved. + This command declares a tactic to be used to solve implicit arguments + that Coq does not know how to solve by unification. It is used every + time the term argument of a tactic has one of its holes not fully + resolved. -Here is an example: + .. deprecated:: 8.9 -.. example:: + This command is deprecated. Use :ref:`typeclasses <typeclasses>` or + :ref:`tactics-in-terms <tactics-in-terms>` instead. - .. coqtop:: all + .. example:: - Parameter quo : nat -> forall n:nat, n<>0 -> nat. - Notation "x // y" := (quo x y _) (at level 40). - Declare Implicit Tactic assumption. - Goal forall n m, m<>0 -> { q:nat & { r | q * m + r = n } }. - intros. - exists (n // m). + .. coqtop:: all - The tactic ``exists (n // m)`` did not fail. The hole was solved - by ``assumption`` so that it behaved as ``exists (quo n m H)``. + Parameter quo : nat -> forall n:nat, n<>0 -> nat. + Notation "x // y" := (quo x y _) (at level 40). + Declare Implicit Tactic assumption. + Goal forall n m, m<>0 -> { q:nat & { r | q * m + r = n } }. + intros. + exists (n // m). + + The tactic ``exists (n // m)`` did not fail. The hole was solved + by ``assumption`` so that it behaved as ``exists (quo n m H)``. .. _decisionprocedures: @@ -3680,11 +3765,12 @@ Therefore, the use of :tacn:`intros` in the previous proof is unnecessary. an instantiation of `x` is necessary. .. tacv:: dtauto + :name: dtauto - While :tacn:`tauto` recognizes inductively defined connectives isomorphic to - the standard connective ``and, prod, or, sum, False, Empty_set, unit, True``, - :tacn:`dtauto` recognizes also all inductive types with one constructors and - no indices, i.e. record-style connectives. + While :tacn:`tauto` recognizes inductively defined connectives isomorphic to + the standard connective ``and, prod, or, sum, False, Empty_set, unit, True``, + :tacn:`dtauto` recognizes also all inductive types with one constructors and + no indices, i.e. record-style connectives. .. tacn:: intuition @tactic :name: intuition @@ -3713,7 +3799,7 @@ and then uses :tacn:`auto` which completes the proof. Originally due to César Muñoz, these tactics (:tacn:`tauto` and :tacn:`intuition`) have been completely re-engineered by David Delahaye using -mainly the tactic language (see :ref:`TODO-9-thetacticlanguage`). The code is +mainly the tactic language (see :ref:`ltac`). The code is now much shorter and a significant increase in performance has been noticed. The general behavior with respect to dependent types, unfolding and introductions has slightly changed to get clearer semantics. This may lead to @@ -3721,26 +3807,20 @@ some incompatibilities. .. tacv:: intuition - Is equivalent to :g:`intuition auto with *`. + Is equivalent to :g:`intuition auto with *`. .. tacv:: dintuition + :name: dintuition - While :tacn:`intuition` recognizes inductively defined connectives - isomorphic to the standard connective ``and, prod, or, sum, False, - Empty_set, unit, True``, :tacn:`dintuition` recognizes also all inductive - types with one constructors and no indices, i.e. record-style connectives. - -Some aspects of the tactic :tacn:`intuition` can be controlled using options. -To avoid that inner negations which do not need to be unfolded are -unfolded, use: - -.. cmd:: Unset Intuition Negation Unfolding + While :tacn:`intuition` recognizes inductively defined connectives + isomorphic to the standard connective ``and``, ``prod``, ``or``, ``sum``, ``False``, + ``Empty_set``, ``unit``, ``True``, :tacn:`dintuition` recognizes also all inductive + types with one constructors and no indices, i.e. record-style connectives. +.. opt:: Intuition Negation Unfolding -To do that all negations of the goal are unfolded even inner ones -(this is the default), use: - -.. cmd:: Set Intuition Negation Unfolding + Controls whether :tacn:`intuition` unfolds inner negations which do not need + to be unfolded. This option is on by default. .. tacn:: rtauto :name: rtauto @@ -3764,14 +3844,18 @@ first- order reasoning, written by Pierre Corbineau. It is not restricted to usual logical connectives but instead may reason about any first-order class inductive definition. -The default tactic used by :tacn:`firstorder` when no rule applies is :g:`auto -with \*`, it can be reset locally or globally using the ``Set Firstorder -Solver`` tactic vernacular command and printed using ``Print Firstorder -Solver``. +.. opt:: Firstorder Solver @tactic + + The default tactic used by :tacn:`firstorder` when no rule applies is + :g:`auto with *`, it can be reset locally or globally using this option. + + .. cmd:: Print Firstorder Solver + + Prints the default tactic used by :tacn:`firstorder` when no rule applies. .. tacv:: firstorder @tactic - Tries to solve the goal with :n:`@tactic` when no logical rule may apply. + Tries to solve the goal with :n:`@tactic` when no logical rule may apply. .. tacv:: firstorder using {+ @qualid} @@ -3788,8 +3872,9 @@ Solver``. This combines the effects of the different variants of :tacn:`firstorder`. -Proof-search is bounded by a depth parameter which can be set by -typing the ``Set Firstorder Depth n`` vernacular command. +.. opt:: Firstorder Depth @num + + This option controls the proof-search depth bound. .. tacn:: congruence :name: congruence @@ -3830,11 +3915,12 @@ match against it. hypotheses using assert in order for :tacn:`congruence` to use them. .. tacv:: congruence with {+ @term} + :name: congruence with - Adds :n:`{+ @term}` to the pool of terms used by :tacn:`congruence`. This helps - in case you have partially applied constructors in your goal. + Adds :n:`{+ @term}` to the pool of terms used by :tacn:`congruence`. This helps + in case you have partially applied constructors in your goal. -.. exn:: I don’t know how to handle dependent equality +.. exn:: I don’t know how to handle dependent equality. The decision procedure managed to find a proof of the goal or of a discriminable equality but this proof could not be built in Coq because of @@ -3846,7 +3932,7 @@ match against it. arguments are supplied for some partially applied constructors. Any term of an appropriate type will allow the tactic to successfully solve the goal. Those additional arguments can be given to congruence by filling in the holes in the - terms given in the error message, using the with variant described above. + terms given in the error message, using the :tacn:`congruence with` variant described above. .. opt:: Congruence Verbose @@ -3865,7 +3951,7 @@ succeeds, and results in an error otherwise. This tactic checks whether its arguments are equal modulo alpha conversion and casts. -.. exn:: Not equal +.. exn:: Not equal. .. tacn:: unify @term @term :name: unify @@ -3873,12 +3959,12 @@ succeeds, and results in an error otherwise. This tactic checks whether its arguments are unifiable, potentially instantiating existential variables. -.. exn:: Not unifiable +.. exn:: Not unifiable. .. tacv:: unify @term @term with @ident Unification takes the transparency information defined in the hint database - :n:`@ident` into account (see :ref:`the hints databases for auto and eauto <the-hints-databases-for-auto-and-eauto>`). + :n:`@ident` into account (see :ref:`the hints databases for auto and eauto <thehintsdatabasesforautoandeauto>`). .. tacn:: is_evar @term :name: is_evar @@ -3887,7 +3973,7 @@ succeeds, and results in an error otherwise. variable. Existential variables are uninstantiated variables generated by :tacn:`eapply` and some other tactics. -.. exn:: Not an evar +.. exn:: Not an evar. .. tacn:: has_evar @term :name: has_evar @@ -3896,7 +3982,7 @@ succeeds, and results in an error otherwise. a subterm. Unlike context patterns combined with ``is_evar``, this tactic scans all subterms, including those under binders. -.. exn:: No evars +.. exn:: No evars. .. tacn:: is_var @term :name: is_var @@ -3904,7 +3990,7 @@ succeeds, and results in an error otherwise. This tactic checks whether its argument is a variable or hypothesis in the current goal context or in the opened sections. -.. exn:: Not a variable or hypothesis +.. exn:: Not a variable or hypothesis. .. _equality: @@ -3928,10 +4014,10 @@ solved by :tacn:`f_equal`. :name: reflexivity This tactic applies to a goal that has the form :g:`t=u`. It checks that `t` -and `u` are convertible and then solves the goal. It is equivalent to apply -:tacn:`refl_equal`. +and `u` are convertible and then solves the goal. It is equivalent to +``apply refl_equal``. -.. exn:: The conclusion is not a substitutive equation +.. exn:: The conclusion is not a substitutive equation. .. exn:: Unable to unify ... with ... @@ -4009,6 +4095,7 @@ symbol :g:`=`. .. tacv:: esimplify_eq @num .. tacv:: esimplify_eq @term {? with @bindings_list} + :name: esimplify_eq This works the same as ``simplify_eq`` but if the type of :n:`@term`, or the type of the hypothesis referred to by :n:`@num`, has uninstantiated @@ -4031,6 +4118,7 @@ symbol :g:`=`. :tacn:`injection` and :tacn:`inversion` tactics. .. tacv:: dependent rewrite <- @ident + :name: dependent rewrite <- Analogous to :tacn:`dependent rewrite ->` but uses the equality from right to left. @@ -4044,12 +4132,12 @@ Inversion :tacn:`functional inversion` is a tactic that performs inversion on hypothesis :n:`@ident` of the form :n:`@qualid {+ @term} = @term` or :n:`@term = @qualid {+ @term}` where :n:`@qualid` must have been defined using Function (see -:ref:`TODO-2.3-advancedrecursivefunctions`). Note that this tactic is only +:ref:`advanced-recursive-functions`). Note that this tactic is only available after a ``Require Import FunInd``. -.. exn:: Hypothesis @ident must contain at least one Function -.. exn:: Cannot find inversion information for hypothesis @ident +.. exn:: Hypothesis @ident must contain at least one Function. +.. exn:: Cannot find inversion information for hypothesis @ident. This error may be raised when some inversion lemma failed to be generated by Function. @@ -4077,10 +4165,10 @@ This kind of inversion has nothing to do with the tactic :tacn:`inversion` above. This tactic does :g:`change (@ident t)`, where `t` is a term built in order to ensure the convertibility. In other words, it does inversion of the function :n:`@ident`. This function must be a fixpoint on a simple recursive -datatype: see :ref:`TODO-10.3-quote` for the full details. +datatype: see :ref:`quote` for the full details. -.. exn:: quote: not a simple fixpoint +.. exn:: quote: not a simple fixpoint. Happens when quote is not able to perform inversion properly. @@ -4109,6 +4197,8 @@ using the ``Require Import`` command. Use ``classical_right`` to prove the right part of the disjunction with the assumption that the negation of left part holds. +.. _tactics-automatizing: + Automatizing ------------ @@ -4148,7 +4238,7 @@ formulas built with `~`, `\/`, `/\`, `->` on top of equalities, inequalities and disequalities on both the type :g:`nat` of natural numbers and :g:`Z` of binary integers. This tactic must be loaded by the command ``Require Import Omega``. See the additional documentation about omega -(see Chapter :ref:`TODO-21-omega`). +(see Chapter :ref:`omega`). .. tacn:: ring @@ -4168,7 +4258,7 @@ given in the conclusion of the goal by their normal forms. If no term is given, then the conclusion should be an equation and both hand sides are normalized. -See :ref:`TODO-Chapter-25-Theringandfieldtacticfamilies` for more information on +See :ref:`Theringandfieldtacticfamilies` for more information on the tactic and how to declare new ring structures. All declared field structures can be printed with the ``Print Rings`` command. @@ -4194,7 +4284,7 @@ denominators. So it produces an equation without division nor inverse. All of these 3 tactics may generate a subgoal in order to prove that denominators are different from zero. -See :ref:`TODO-Chapter-25-Theringandfieldtacticfamilies` for more information on the tactic and how to +See :ref:`Theringandfieldtacticfamilies` for more information on the tactic and how to declare new field structures. All declared field structures can be printed with the Print Fields command. @@ -4286,24 +4376,24 @@ This tactics reverses the list of the focused goals. This tactic moves all goals under focus to a shelf. While on the shelf, goals will not be focused on. They can be solved by unification, or they can be called back into focus with the command - :tacn:`Unshelve`. + :cmd:`Unshelve`. -.. tacv:: shelve_unifiable + .. tacv:: shelve_unifiable + :name: shelve_unifiable - Shelves only the goals under focus that are mentioned in other goals. - Goals that appear in the type of other goals can be solved by unification. + Shelves only the goals under focus that are mentioned in other goals. + Goals that appear in the type of other goals can be solved by unification. -.. example:: + .. example:: - .. coqtop:: all reset + .. coqtop:: all reset - Goal exists n, n=0. - refine (ex_intro _ _ _). - all:shelve_unifiable. - reflexivity. + Goal exists n, n=0. + refine (ex_intro _ _ _). + all: shelve_unifiable. + reflexivity. -.. tacn:: Unshelve - :name: Unshelve +.. cmd:: Unshelve This command moves all the goals on the shelf (see :tacn:`shelve`) from the shelf into focus, by appending them to the end of the current @@ -4334,11 +4424,11 @@ A simple example has more value than a long explanation: The tactics macros are synchronous with the Coq section mechanism: a tactic definition is deleted from the current environment when you -close the section (see also :ref:`TODO-2.4Sectionmechanism`) where it was +close the section (see also :ref:`section-mechanism`) where it was defined. If you want that a tactic macro defined in a module is usable in the modules that require it, you should put it outside of any section. -:ref:`TODO-9-Thetacticlanguage` gives examples of more complex +:ref:`ltac` gives examples of more complex user-defined tactics. .. [1] Actually, only the second subgoal will be generated since the diff --git a/doc/sphinx/proof-engine/vernacular-commands.rst b/doc/sphinx/proof-engine/vernacular-commands.rst new file mode 100644 index 0000000000..c37233734b --- /dev/null +++ b/doc/sphinx/proof-engine/vernacular-commands.rst @@ -0,0 +1,1242 @@ +.. include:: ../preamble.rst +.. include:: ../replaces.rst + +.. _vernacularcommands: + +Vernacular commands +============================= + +.. _displaying: + +Displaying +-------------- + + +.. _Print: + +.. cmd:: Print @qualid + :name: Print + + This command displays on the screen information about the declared or + defined object referred by :n:`@qualid`. + + Error messages: + + .. exn:: @qualid not a defined object. + + .. exn:: Universe instance should have length @num. + + .. exn:: This object does not support universe names. + + + .. cmdv:: Print Term @qualid + :name: Print Term + + This is a synonym of :cmd:`Print` :n:`@qualid` when :n:`@qualid` + denotes a global constant. + + .. cmdv:: Print {? Term } @qualid\@@name + + This locally renames the polymorphic universes of :n:`@qualid`. + An underscore means the raw universe is printed. + + +.. cmd:: About @qualid + :name: About + + This displays various information about the object + denoted by :n:`@qualid`: its kind (module, constant, assumption, inductive, + constructor, abbreviation, …), long name, type, implicit arguments and + argument scopes. It does not print the body of definitions or proofs. + + .. cmdv:: About @qualid\@@name + + This locally renames the polymorphic universes of :n:`@qualid`. + An underscore means the raw universe is printed. + + +.. cmd:: Print All + + This command displays information about the current state of the + environment, including sections and modules. + + .. cmdv:: Inspect @num + :name: Inspect + + This command displays the :n:`@num` last objects of the + current environment, including sections and modules. + + .. cmdv:: Print Section @ident + + The name :n:`@ident` should correspond to a currently open section, + this command displays the objects defined since the beginning of this + section. + + +.. _flags-options-tables: + +Flags, Options and Tables +----------------------------- + +|Coq| configurability is based on flags (e.g. :opt:`Printing All`), options +(e.g. :opt:`Printing Width`), or tables (e.g. :cmd:`Add Printing Record`). The +names of flags, options and tables are made of non-empty sequences of +identifiers (conventionally with capital initial letter). The general commands +handling flags, options and tables are given below. + +.. TODO : flag is not a syntax entry + +.. cmd:: Set @flag + + This command switches :n:`@flag` on. The original state of :n:`@flag` + is restored when the current module ends. + + .. cmdv:: Local Set @flag + + This command switches :n:`@flag` on. The original state + of :n:`@flag` is restored when the current *section* ends. + + .. cmdv:: Global Set @flag + + This command switches :n:`@flag` on. The original state + of :n:`@flag` is *not* restored at the end of the module. Additionally, if + set in a file, :n:`@flag` is switched on when the file is `Require`-d. + + .. cmdv:: Export Set @flag + + This command switches :n:`@flag` on. The original state + of :n:`@flag` is restored at the end of the current module, but :n:`@flag` + is switched on when this module is imported. + + +.. cmd:: Unset @flag + + This command switches :n:`@flag` off. The original state of + :n:`@flag` is restored when the current module ends. + + .. cmdv:: Local Unset @flag + + This command switches :n:`@flag` off. The original + state of :n:`@flag` is restored when the current *section* ends. + + .. cmdv:: Global Unset @flag + + This command switches :n:`@flag` off. The original + state of :n:`@flag` is *not* restored at the end of the module. Additionally, + if set in a file, :n:`@flag` is switched off when the file is `Require`-d. + + .. cmdv:: Export Unset @flag + + This command switches :n:`@flag` off. The original state + of :n:`@flag` is restored at the end of the current module, but :n:`@flag` + is switched off when this module is imported. + + +.. cmd:: Test @flag + + This command prints whether :n:`@flag` is on or off. + + +.. cmd:: Set @option @value + + This command sets :n:`@option` to :n:`@value`. The original value of ` option` is + restored when the current module ends. + + .. TODO : option and value are not syntax entries + + .. cmdv:: Local Set @option @value + + This command sets :n:`@option` to :n:`@value`. The + original value of :n:`@option` is restored at the end of the module. + + .. cmdv:: Global Set @option @value + + This command sets :n:`@option` to :n:`@value`. The + original value of :n:`@option` is *not* restored at the end of the module. + Additionally, if set in a file, :n:`@option` is set to value when the file + is `Require`-d. + + .. cmdv:: Export Set @option + + This command set :n:`@option` to :n:`@value`. The original state + of :n:`@option` is restored at the end of the current module, but :n:`@option` + is set to :n:`@value` when this module is imported. + + +.. cmd:: Unset @option + + This command turns off :n:`@option`. + + .. cmdv:: Local Unset @option + + This command turns off :n:`@option`. The original state of :n:`@option` + is restored when the current *section* ends. + + .. cmdv:: Global Unset @option + + This command turns off :n:`@option`. The original state of :n:`@option` + is *not* restored at the end of the module. Additionally, if unset in a file, + :n:`@option` is reset to its default value when the file is `Require`-d. + + .. cmdv:: Export Unset @option + + This command turns off :n:`@option`. The original state of :n:`@option` + is restored at the end of the current module, but :n:`@option` is set to + its default value when this module is imported. + + +.. cmd:: Test @option + + This command prints the current value of :n:`@option`. + + +.. TODO : table is not a syntax entry + +.. cmd:: Add @table @value + :name: Add `table` `value` + +.. cmd:: Remove @table @value + :name: Remove `table` `value` + +.. cmd:: Test @table @value + :name: Test `table` `value` + +.. cmd:: Test @table for @value + :name: Test `table` for `value` + +.. cmd:: Print Table @table + +These are general commands for tables. + + +.. cmd:: Print Options + + This command lists all available flags, options and tables. + + .. cmdv:: Print Tables + + This is a synonymous of :cmd:`Print Options`. + + +.. _requests-to-the-environment: + +Requests to the environment +------------------------------- + +.. cmd:: Check @term + + This command displays the type of :n:`@term`. When called in proof mode, the + term is checked in the local context of the current subgoal. + + + .. TODO : selector is not a syntax entry + + .. cmdv:: @selector: Check @term + + This variant specifies on which subgoal to perform typing + (see Section :ref:`invocation-of-tactics`). + + +.. TODO : convtactic is not a syntax entry + +.. cmd:: Eval @convtactic in @term + + This command performs the specified reduction on :n:`@term`, and displays + the resulting term with its type. The term to be reduced may depend on + hypothesis introduced in the first subgoal (if a proof is in + progress). + + See also: Section :ref:`performingcomputations`. + + +.. cmd:: Compute @term + + This command performs a call-by-value evaluation of term by using the + bytecode-based virtual machine. It is a shortcut for ``Eval vm_compute in`` + :n:`@term`. + + See also: Section :ref:`performingcomputations`. + + +.. cmd:: Print Assumptions @qualid + + This commands display all the assumptions (axioms, parameters and + variables) a theorem or definition depends on. Especially, it informs + on the assumptions with respect to which the validity of a theorem + relies. + + .. cmdv:: Print Opaque Dependencies @qualid + :name: Print Opaque Dependencies + + Displays the set of opaque constants :n:`@qualid` relies on in addition to + the assumptions. + + .. cmdv:: Print Transparent Dependencies @qualid + :name: Print Transparent Dependencies + + Displays the set of transparent constants :n:`@qualid` relies on + in addition to the assumptions. + + .. cmdv:: Print All Dependencies @qualid + :name: Print All Dependencies + + Displays all assumptions and constants :n:`@qualid` relies on. + + +.. cmd:: Search @qualid + + This command displays the name and type of all objects (hypothesis of + the current goal, theorems, axioms, etc) of the current context whose + statement contains :n:`@qualid`. This command is useful to remind the user + of the name of library lemmas. + + .. exn:: The reference @qualid was not found in the current environment. + + There is no constant in the environment named qualid. + + .. cmdv:: Search @string + + If :n:`@string` is a valid identifier, this command + displays the name and type of all objects (theorems, axioms, etc) of + the current context whose name contains string. If string is a + notation’s string denoting some reference :n:`@qualid` (referred to by its + main symbol as in `"+"` or by its notation’s string as in `"_ + _"` or + `"_ 'U' _"`, see Section :ref:`notations`), the command works like ``Search`` :n:`@qualid`. + + .. cmdv:: Search @string%@key + + The string string must be a notation or the main + symbol of a notation which is then interpreted in the scope bound to + the delimiting key :n:`@key` (see Section :ref:`LocalInterpretationRulesForNotations`). + + .. cmdv:: Search @term_pattern + + This searches for all statements or types of + definition that contains a subterm that matches the pattern + `term_pattern` (holes of the pattern are either denoted by `_` or by + `?ident` when non linear patterns are expected). + + .. cmdv:: Search { + [-]@term_pattern_string } + + where + :n:`@term_pattern_string` is a term_pattern, a string, or a string followed + by a scope delimiting key `%key`. This generalization of ``Search`` searches + for all objects whose statement or type contains a subterm matching + :n:`@term_pattern` (or :n:`@qualid` if :n:`@string` is the notation for a reference + qualid) and whose name contains all string of the request that + correspond to valid identifiers. If a term_pattern or a string is + prefixed by `-`, the search excludes the objects that mention that + term_pattern or that string. + + .. cmdv:: Search @term_pattern_string … @term_pattern_string inside {+ @qualid } + + This restricts the search to constructions defined in the modules + named by the given :n:`qualid` sequence. + + .. cmdv:: Search @term_pattern_string … @term_pattern_string outside {+ @qualid } + + This restricts the search to constructions not defined in the modules + named by the given :n:`qualid` sequence. + + .. cmdv:: @selector: Search [-]@term_pattern_string … [-]@term_pattern_string + + This specifies the goal on which to search hypothesis (see + Section :ref:`invocation-of-tactics`). + By default the 1st goal is searched. This variant can + be combined with other variants presented here. + + .. example:: + + .. coqtop:: in + + Require Import ZArith. + + .. coqtop:: all + + Search Z.mul Z.add "distr". + + Search "+"%Z "*"%Z "distr" -positive -Prop. + + Search (?x * _ + ?x * _)%Z outside OmegaLemmas. + + .. cmdv:: SearchAbout + :name: SearchAbout + + .. deprecated:: 8.5 + + Up to |Coq| version 8.4, :cmd:`Search` had the behavior of current + :cmd:`SearchHead` and the behavior of current :cmd:`Search` was obtained with + command :cmd:`SearchAbout`. For compatibility, the deprecated name + :cmd:`SearchAbout` can still be used as a synonym of :cmd:`Search`. For + compatibility, the list of objects to search when using :cmd:`SearchAbout` + may also be enclosed by optional ``[ ]`` delimiters. + + +.. cmd:: SearchHead @term + + This command displays the name and type of all hypothesis of the + current goal (if any) and theorems of the current context whose + statement’s conclusion has the form `(term t1 .. tn)`. This command is + useful to remind the user of the name of library lemmas. + + .. example:: + + .. coqtop:: reset all + + SearchHead le. + + SearchHead (@eq bool). + + .. cmdv:: SearchHead @term inside {+ @qualid } + + This restricts the search to constructions defined in the modules named + by the given :n:`qualid` sequence. + + .. cmdv:: SearchHead term outside {+ @qualid } + + This restricts the search to constructions not defined in the modules + named by the given :n:`qualid` sequence. + + .. exn:: Module/section @qualid not found. + + No module :n:`@qualid` has been required (see Section :ref:`compiled-files`). + + .. cmdv:: @selector: SearchHead @term + + This specifies the goal on which to + search hypothesis (see Section :ref:`invocation-of-tactics`). + By default the 1st goal is searched. This variant can be combined + with other variants presented here. + + .. note:: Up to |Coq| version 8.4, ``SearchHead`` was named ``Search``. + + +.. cmd:: SearchPattern @term + + This command displays the name and type of all hypothesis of the + current goal (if any) and theorems of the current context whose + statement’s conclusion or last hypothesis and conclusion matches the + expressionterm where holes in the latter are denoted by `_`. + It is a variant of :n:`Search @term_pattern` that does not look for subterms + but searches for statements whose conclusion has exactly the expected + form, or whose statement finishes by the given series of + hypothesis/conclusion. + + .. example:: + + .. coqtop:: in + + Require Import Arith. + + .. coqtop:: all + + SearchPattern (_ + _ = _ + _). + + SearchPattern (nat -> bool). + + SearchPattern (forall l : list _, _ l l). + + Patterns need not be linear: you can express that the same expression + must occur in two places by using pattern variables `?ident`. + + + .. example:: + + .. coqtop:: all + + SearchPattern (?X1 + _ = _ + ?X1). + + .. cmdv:: SearchPattern @term inside {+ @qualid } + + This restricts the search to constructions defined in the modules + named by the given :n:`qualid` sequence. + + .. cmdv:: SearchPattern @term outside {+ @qualid } + + This restricts the search to constructions not defined in the modules + named by the given :n:`qualid` sequence. + + .. cmdv:: @selector: SearchPattern @term + + This specifies the goal on which to + search hypothesis (see Section :ref:`invocation-of-tactics`). + By default the 1st goal is + searched. This variant can be combined with other variants presented + here. + + +.. cmd:: SearchRewrite @term + + This command displays the name and type of all hypothesis of the + current goal (if any) and theorems of the current context whose + statement’s conclusion is an equality of which one side matches the + expression term. Holes in term are denoted by “_”. + + .. example:: + + .. coqtop:: in + + Require Import Arith. + + .. coqtop:: all + + SearchRewrite (_ + _ + _). + + .. cmdv:: SearchRewrite term inside {+ @qualid } + + This restricts the search to constructions defined in the modules + named by the given :n:`qualid` sequence. + + .. cmdv:: SearchRewrite @term outside {+ @qualid } + + This restricts the search to constructions not defined in the modules + named by the given :n:`qualid` sequence. + + .. cmdv:: @selector: SearchRewrite @term + + This specifies the goal on which to + search hypothesis (see Section :ref:`invocation-of-tactics`). + By default the 1st goal is + searched. This variant can be combined with other variants presented + here. + +.. note:: + + .. cmd:: Add Search Blacklist @string + + For the ``Search``, ``SearchHead``, ``SearchPattern`` and ``SearchRewrite`` + queries, it is possible to globally filter the search results using this + command. A lemma whose fully-qualified name + contains any of the declared strings will be removed from the + search results. The default blacklisted substrings are ``_subproof`` and + ``Private_``. + + .. cmd:: Remove Search Blacklist @string + + This command allows expunging this blacklist. + + +.. cmd:: Locate @qualid + + This command displays the full name of objects whose name is a prefix + of the qualified identifier :n:`@qualid`, and consequently the |Coq| module in + which they are defined. It searches for objects from the different + qualified name spaces of |Coq|: terms, modules, Ltac, etc. + + .. example:: + + .. coqtop:: all + + Locate nat. + + Locate Datatypes.O. + + Locate Init.Datatypes.O. + + Locate Coq.Init.Datatypes.O. + + Locate I.Dont.Exist. + + .. cmdv:: Locate Term @qualid + + As Locate but restricted to terms. + + .. cmdv:: Locate Module @qualid + + As Locate but restricted to modules. + + .. cmdv:: Locate Ltac @qualid + + As Locate but restricted to tactics. + +See also: Section :ref:`locating-notations` + + +.. _loading-files: + +Loading files +----------------- + +|Coq| offers the possibility of loading different parts of a whole +development stored in separate files. Their contents will be loaded as +if they were entered from the keyboard. This means that the loaded +files are ASCII files containing sequences of commands for |Coq|’s +toplevel. This kind of file is called a *script* for |Coq|. The standard +(and default) extension of |Coq|’s script files is .v. + + +.. cmd:: Load @ident + + This command loads the file named :n:`ident`.v, searching successively in + each of the directories specified in the *loadpath*. (see Section + :ref:`libraries-and-filesystem`) + + Files loaded this way cannot leave proofs open, and the ``Load`` + command cannot be used inside a proof either. + + .. cmdv:: Load @string + + Loads the file denoted by the string :n:`@string`, where + string is any complete filename. Then the `~` and .. abbreviations are + allowed as well as shell variables. If no extension is specified, |Coq| + will use the default extension ``.v``. + + .. cmdv:: Load Verbose @ident + + .. cmdv:: Load Verbose @string + + Display, while loading, + the answers of |Coq| to each command (including tactics) contained in + the loaded file See also: Section :ref:`controlling-display`. + + .. exn:: Can’t find file @ident on loadpath. + + .. exn:: Load is not supported inside proofs. + + .. exn:: Files processed by Load cannot leave open proofs. + +.. _compiled-files: + +Compiled files +------------------ + +This section describes the commands used to load compiled files (see +Chapter :ref:`thecoqcommands` for documentation on how to compile a file). A compiled +file is a particular case of module called *library file*. + + +.. cmd:: Require @qualid + + This command looks in the loadpath for a file containing module :n:`@qualid` + and adds the corresponding module to the environment of |Coq|. As + library files have dependencies in other library files, the command + :cmd:`Require` :n:`@qualid` recursively requires all library files the module + qualid depends on and adds the corresponding modules to the + environment of |Coq| too. |Coq| assumes that the compiled files have been + produced by a valid |Coq| compiler and their contents are then not + replayed nor rechecked. + + To locate the file in the file system, :n:`@qualid` is decomposed under the + form `dirpath.ident` and the file `ident.vo` is searched in the physical + directory of the file system that is mapped in |Coq| loadpath to the + logical path dirpath (see Section :ref:`libraries-and-filesystem`). The mapping between + physical directories and logical names at the time of requiring the + file must be consistent with the mapping used to compile the file. If + several files match, one of them is picked in an unspecified fashion. + + + .. cmdv:: Require Import @qualid + :name: Require Import + + This loads and declares the module :n:`@qualid` + and its dependencies then imports the contents of :n:`@qualid` as described + :ref:`here <import_qualid>`. It does not import the modules on which + qualid depends unless these modules were themselves required in module + :n:`@qualid` + using :cmd:`Require Export`, as described below, or recursively required + through a sequence of :cmd:`Require Export`. If the module required has + already been loaded, :cmd:`Require Import` :n:`@qualid` simply imports it, as + :cmd:`Import` :n:`@qualid` would. + + .. cmdv:: Require Export @qualid + :name: Require Export + + This command acts as :cmd:`Require Import` :n:`@qualid`, + but if a further module, say `A`, contains a command :cmd:`Require Export` `B`, + then the command :cmd:`Require Import` `A` also imports the module `B.` + + .. cmdv:: Require [Import | Export] {+ @qualid } + + This loads the + modules named by the :n:`qualid` sequence and their recursive + dependencies. If + ``Import`` or ``Export`` is given, it also imports these modules and + all the recursive dependencies that were marked or transitively marked + as ``Export``. + + .. cmdv:: From @dirpath Require @qualid + + This command acts as :cmd:`Require`, but picks + any library whose absolute name is of the form dirpath.dirpath’.qualid + for some `dirpath’`. This is useful to ensure that the :n:`@qualid` library + comes from a given package by making explicit its absolute root. + + .. exn:: Cannot load qualid: no physical path bound to dirpath. + + .. exn:: Cannot find library foo in loadpath. + + The command did not find the + file foo.vo. Either foo.v exists but is not compiled or foo.vo is in a + directory which is not in your LoadPath (see Section :ref:`libraries-and-filesystem`). + + .. exn:: Compiled library @ident.vo makes inconsistent assumptions over library qualid. + + The command tried to load library file :n:`@ident`.vo that + depends on some specific version of library :n:`@qualid` which is not the + one already loaded in the current |Coq| session. Probably `ident.v` was + not properly recompiled with the last version of the file containing + module :n:`@qualid`. + + .. exn:: Bad magic number. + + The file `ident.vo` was found but either it is not a + |Coq| compiled module, or it was compiled with an incompatible + version of |Coq|. + + .. exn:: The file `ident.vo` contains library dirpath and not library dirpath’. + + The library file `dirpath’` is indirectly required by the + ``Require`` command but it is bound in the current loadpath to the + file `ident.vo` which was bound to a different library name `dirpath` at + the time it was compiled. + + + .. exn:: Require is not allowed inside a module or a module type. + + This command + is not allowed inside a module or a module type being defined. It is + meant to describe a dependency between compilation units. Note however + that the commands ``Import`` and ``Export`` alone can be used inside modules + (see Section :ref:`Import <import_qualid>`). + + + +See also: Chapter :ref:`thecoqcommands` + + +.. cmd:: Print Libraries + + This command displays the list of library files loaded in the + current |Coq| session. For each of these libraries, it also tells if it + is imported. + + +.. cmd:: Declare ML Module {+ @string } + + This commands loads the OCaml compiled files + with names given by the :n:`@string` sequence + (dynamic link). It is mainly used to load tactics dynamically. The + files are searched into the current OCaml loadpath (see the + command ``Add ML Path`` in Section :ref:`libraries-and-filesystem`). + Loading of OCaml files is only possible under the bytecode version of + ``coqtop`` (i.e. ``coqtop`` called with option ``-byte``, see chapter + :ref:`thecoqcommands`), or when |Coq| has been compiled with a + version of OCaml that supports native Dynlink (≥ 3.11). + + .. cmdv:: Local Declare ML Module {+ @string } + + This variant is not exported to the modules that import the module + where they occur, even if outside a section. + + .. exn:: File not found on loadpath: @string. + + .. exn:: Loading of ML object file forbidden in a native Coq. + + +.. cmd:: Print ML Modules + + This prints the name of all OCaml modules loaded with ``Declare + ML Module``. To know from where these module were loaded, the user + should use the command ``Locate File`` (see :ref:`here <locate-file>`) + + +.. _loadpath: + +Loadpath +------------ + +Loadpaths are preferably managed using |Coq| command line options (see +Section `libraries-and-filesystem`) but there remain vernacular commands to manage them +for practical purposes. Such commands are only meant to be issued in +the toplevel, and using them in source files is discouraged. + + +.. cmd:: Pwd + + This command displays the current working directory. + + +.. cmd:: Cd @string + + This command changes the current directory according to :n:`@string` which + can be any valid path. + + .. cmdv:: Cd + + Is equivalent to Pwd. + + +.. cmd:: Add LoadPath @string as @dirpath + + This command is equivalent to the command line option + ``-Q`` :n:`@string` :n:`@dirpath`. It adds the physical directory string to the current + |Coq| loadpath and maps it to the logical directory dirpath. + + .. cmdv:: Add LoadPath @string + + Performs as Add LoadPath :n:`@string` as :n:`@dirpath` but + for the empty directory path. + + +.. cmd:: Add Rec LoadPath @string as @dirpath + + This command is equivalent to the command line option + ``-R`` :n:`@string` :n:`@dirpath`. It adds the physical directory string and all its + subdirectories to the current |Coq| loadpath. + + .. cmdv:: Add Rec LoadPath @string + + Works as :cmd:`Add Rec LoadPath` :n:`@string` as :n:`@dirpath` but for the empty + logical directory path. + + +.. cmd:: Remove LoadPath @string + + This command removes the path :n:`@string` from the current |Coq| loadpath. + + +.. cmd:: Print LoadPath + + This command displays the current |Coq| loadpath. + + .. cmdv:: Print LoadPath @dirpath + + Works as :cmd:`Print LoadPath` but displays only + the paths that extend the :n:`@dirpath` prefix. + + +.. cmd:: Add ML Path @string + + This command adds the path :n:`@string` to the current OCaml + loadpath (see the command `Declare ML Module`` in Section :ref:`compiled-files`). + + +.. cmd:: Add Rec ML Path @string + + This command adds the directory :n:`@string` and all its subdirectories to + the current OCaml loadpath (see the command :cmd:`Declare ML Module`). + + +.. cmd:: Print ML Path @string + + This command displays the current OCaml loadpath. This + command makes sense only under the bytecode version of ``coqtop``, i.e. + using option ``-byte`` + (see the command Declare ML Module in Section :ref:`compiled-files`). + +.. _locate-file: + +.. cmd:: Locate File @string + + This command displays the location of file string in the current + loadpath. Typically, string is a .cmo or .vo or .v file. + + +.. cmd:: Locate Library @dirpath + + This command gives the status of the |Coq| module dirpath. It tells if + the module is loaded and if not searches in the load path for a module + of logical name :n:`@dirpath`. + + +.. _backtracking: + +Backtracking +---------------- + +The backtracking commands described in this section can only be used +interactively, they cannot be part of a vernacular file loaded via +``Load`` or compiled by ``coqc``. + + +.. cmd:: Reset @ident + + This command removes all the objects in the environment since :n:`@ident` + was introduced, including :n:`@ident`. :n:`@ident` may be the name of a defined or + declared object as well as the name of a section. One cannot reset + over the name of a module or of an object inside a module. + + .. exn:: @ident: no such entry. + + .. cmdv:: Reset Initial + + Goes back to the initial state, just after the start + of the interactive session. + + +.. cmd:: Back + + This command undoes all the effects of the last vernacular command. + Commands read from a vernacular file via a :cmd:`Load` are considered as a + single command. Proof management commands are also handled by this + command (see Chapter :ref:`proofhandling`). For that, Back may have to undo more than + one command in order to reach a state where the proof management + information is available. For instance, when the last command is a + :cmd:`Qed`, the management information about the closed proof has been + discarded. In this case, :cmd:`Back` will then undo all the proof steps up to + the statement of this proof. + + .. cmdv:: Back @num + + Undo :n:`@num` vernacular commands. As for Back, some extra + commands may be undone in order to reach an adequate state. For + instance Back :n:`@num` will not re-enter a closed proof, but rather go just + before that proof. + + .. exn:: Invalid backtrack. + + The user wants to undo more commands than available in the history. + +.. cmd:: BackTo @num + + This command brings back the system to the state labeled :n:`@num`, + forgetting the effect of all commands executed after this state. The + state label is an integer which grows after each successful command. + It is displayed in the prompt when in -emacs mode. Just as :cmd:`Back` (see + above), the :cmd:`BackTo` command now handles proof states. For that, it may + have to undo some extra commands and end on a state `num′ ≤ num` if + necessary. + + .. cmdv:: Backtrack @num @num @num + :name: Backtrack + + .. deprecated:: 8.4 + + :cmd:`Backtrack` is a *deprecated* form of + :cmd:`BackTo` which allows explicitly manipulating the proof environment. The + three numbers represent the following: + + + *first number* : State label to reach, as for :cmd:`BackTo`. + + *second number* : *Proof state number* to unbury once aborts have been done. + |Coq| will compute the number of :cmd:`Undo` to perform (see Chapter :ref:`proofhandling`). + + *third number* : Number of :cmd:`Abort` to perform, i.e. the number of currently + opened nested proofs that must be canceled (see Chapter :ref:`proofhandling`). + + .. exn:: Invalid backtrack. + + The destination state label is unknown. + + +.. _quitting-and-debugging: + +Quitting and debugging +-------------------------- + + +.. cmd:: Quit + + This command permits to quit |Coq|. + + +.. cmd:: Drop + + This is used mostly as a debug facility by |Coq|’s implementors and does + not concern the casual user. This command permits to leave |Coq| + temporarily and enter the OCaml toplevel. The OCaml + command: + + :: + + #use "include";; + + adds the right loadpaths and loads some toplevel printers for all + abstract types of |Coq|- section_path, identifiers, terms, judgments, …. + You can also use the file base_include instead, that loads only the + pretty-printers for section_paths and identifiers. You can return back + to |Coq| with the command: + + :: + + go();; + + .. warning:: + + #. It only works with the bytecode version of |Coq| (i.e. `coqtop.byte`, + see Section `interactive-use`). + #. You must have compiled |Coq| from the source package and set the + environment variable COQTOP to the root of your copy of the sources + (see Section `customization-by-environment-variables`). + + +.. TODO : command is not a syntax entry + +.. cmd:: Time @command + + This command executes the vernacular command :n:`@command` and displays the + time needed to execute it. + + +.. cmd:: Redirect @string @command + + This command executes the vernacular command :n:`@command`, redirecting its + output to ":n:`@string`.out". + + +.. cmd:: Timeout @num @command + + This command executes the vernacular command :n:`@command`. If the command + has not terminated after the time specified by the :n:`@num` (time + expressed in seconds), then it is interrupted and an error message is + displayed. + + .. opt:: Default Timeout @num + + This option controls a default timeout for subsequent commands, as if they + were passed to a :cmd:`Timeout` command. Commands already starting by a + :cmd:`Timeout` are unaffected. + + +.. cmd:: Fail @command + + For debugging scripts, sometimes it is desirable to know + whether a command or a tactic fails. If the given :n:`@command` + fails, the ``Fail`` statement succeeds, without changing the proof + state, and in interactive mode, the system + prints a message confirming the failure. + If the given :n:`@command` succeeds, the statement is an error, and + it prints a message indicating that the failure did not occur. + + .. exn:: The command has not failed! + + +.. _controlling-display: + +Controlling display +----------------------- + +.. opt:: Silent + + This option controls the normal displaying. + +.. opt:: Warnings "{+, {? %( - %| + %) } @ident }" + + This option configures the display of warnings. It is experimental, and + expects, between quotes, a comma-separated list of warning names or + categories. Adding - in front of a warning or category disables it, adding + + makes it an error. It is possible to use the special categories all and + default, the latter containing the warnings enabled by default. The flags are + interpreted from left to right, so in case of an overlap, the flags on the + right have higher priority, meaning that `A,-A` is equivalent to `-A`. + +.. opt:: Search Output Name Only + + This option restricts the output of search commands to identifier names; + turning it on causes invocations of :cmd:`Search`, :cmd:`SearchHead`, + :cmd:`SearchPattern`, :cmd:`SearchRewrite` etc. to omit types from their + output, printing only identifiers. + +.. opt:: Printing Width @num + :name: Printing Width + + This command sets which left-aligned part of the width of the screen is used + for display. At the time of writing this documentation, the default value + is 78. + +.. opt:: Printing Depth @num + :name: Printing Depth + + This option controls the nesting depth of the formatter used for pretty- + printing. Beyond this depth, display of subterms is replaced by dots. At the + time of writing this documentation, the default value is 50. + +.. opt:: Printing Compact Contexts + + This option controls the compact display mode for goals contexts. When on, + the printer tries to reduce the vertical size of goals contexts by putting + several variables (even if of different types) on the same line provided it + does not exceed the printing width (see :opt:`Printing Width`). At the time + of writing this documentation, it is off by default. + +.. opt:: Printing Unfocused + + This option controls whether unfocused goals are displayed. Such goals are + created by focusing other goals with bullets (see :ref:`bullets` or + :ref:`curly braces <curly-braces>`). It is off by default. + +.. opt:: Printing Dependent Evars Line + + This option controls the printing of the “(dependent evars: …)” line when + ``-emacs`` is passed. + + +.. _vernac-controlling-the-reduction-strategies: + +Controlling the reduction strategies and the conversion algorithm +---------------------------------------------------------------------- + + +|Coq| provides reduction strategies that the tactics can invoke and two +different algorithms to check the convertibility of types. The first +conversion algorithm lazily compares applicative terms while the other +is a brute-force but efficient algorithm that first normalizes the +terms before comparing them. The second algorithm is based on a +bytecode representation of terms similar to the bytecode +representation used in the ZINC virtual machine :cite:`Leroy90`. It is +especially useful for intensive computation of algebraic values, such +as numbers, and for reflection-based tactics. The commands to fine- +tune the reduction strategies and the lazy conversion algorithm are +described first. + +.. cmd:: Opaque {+ @qualid } + + This command has an effect on unfoldable constants, i.e. on constants + defined by :cmd:`Definition` or :cmd:`Let` (with an explicit body), or by a command + assimilated to a definition such as :cmd:`Fixpoint`, :cmd:`Program Definition`, etc, + or by a proof ended by :cmd:`Defined`. The command tells not to unfold the + constants in the :n:`@qualid` sequence in tactics using δ-conversion (unfolding + a constant is replacing it by its definition). + + :cmd:`Opaque` has also an effect on the conversion algorithm of |Coq|, telling + it to delay the unfolding of a constant as much as possible when |Coq| + has to check the conversion (see Section :ref:`conversion-rules`) of two distinct + applied constants. + + .. cmdv:: Global Opaque {+ @qualid } + :name: Global Opaque + + The scope of :cmd:`Opaque` is limited to the current section, or current + file, unless the variant :cmd:`Global Opaque` is used. + + See also: sections :ref:`performingcomputations`, :ref:`tactics-automatizing`, + :ref:`proof-editing-mode` + + .. exn:: The reference @qualid was not found in the current environment. + + There is no constant referred by :n:`@qualid` in the environment. + Nevertheless, if you asked :cmd:`Opaque` `foo` `bar` and if `bar` does + not exist, `foo` is set opaque. + +.. cmd:: Transparent {+ @qualid } + + This command is the converse of :cmd:`Opaque` and it applies on unfoldable + constants to restore their unfoldability after an Opaque command. + + Note in particular that constants defined by a proof ended by Qed are + not unfoldable and Transparent has no effect on them. This is to keep + with the usual mathematical practice of *proof irrelevance*: what + matters in a mathematical development is the sequence of lemma + statements, not their actual proofs. This distinguishes lemmas from + the usual defined constants, whose actual values are of course + relevant in general. + + .. cmdv:: Global Transparent {+ @qualid } + :name: Global Transparent + + The scope of Transparent is limited to the current section, or current + file, unless the variant :cmd:`Global Transparent` is + used. + + .. exn:: The reference @qualid was not found in the current environment. + + There is no constant referred by :n:`@qualid` in the environment. + + See also: sections :ref:`performingcomputations`, + :ref:`tactics-automatizing`, :ref:`proof-editing-mode` + +.. _vernac-strategy: + +.. cmd:: Strategy @level [ {+ @qualid } ] + + This command generalizes the behavior of Opaque and Transparent + commands. It is used to fine-tune the strategy for unfolding + constants, both at the tactic level and at the kernel level. This + command associates a level to the qualified names in the :n:`@qualid` + sequence. Whenever two + expressions with two distinct head constants are compared (for + instance, this comparison can be triggered by a type cast), the one + with lower level is expanded first. In case of a tie, the second one + (appearing in the cast type) is expanded. + + Levels can be one of the following (higher to lower): + + + ``opaque`` : level of opaque constants. They cannot be expanded by + tactics (behaves like +∞, see next item). + + :n:`@num` : levels indexed by an integer. Level 0 corresponds to the + default behavior, which corresponds to transparent constants. This + level can also be referred to as transparent. Negative levels + correspond to constants to be expanded before normal transparent + constants, while positive levels correspond to constants to be + expanded after normal transparent constants. + + ``expand`` : level of constants that should be expanded first (behaves + like −∞) + + .. cmdv:: Local Strategy @level [ {+ @qualid } ] + + These directives survive section and module closure, unless the + command is prefixed by ``Local``. In the latter case, the behavior + regarding sections and modules is the same as for the :cmd:`Transparent` and + :cmd:`Opaque` commands. + + +.. cmd:: Print Strategy @qualid + + This command prints the strategy currently associated to :n:`@qualid`. It + fails if :n:`@qualid` is not an unfoldable reference, that is, neither a + variable nor a constant. + + .. exn:: The reference is not unfoldable. + + .. cmdv:: Print Strategies + + Print all the currently non-transparent strategies. + + +.. cmd:: Declare Reduction @ident := @convtactic + + This command allows giving a short name to a reduction expression, for + instance lazy beta delta [foo bar]. This short name can then be used + in ``Eval`` :n:`@ident` ``in`` ... or ``eval`` directives. This command + accepts the + Local modifier, for discarding this reduction name at the end of the + file or module. For the moment the name cannot be qualified. In + particular declaring the same name in several modules or in several + functor applications will be refused if these declarations are not + local. The name :n:`@ident` cannot be used directly as an Ltac tactic, but + nothing prevents the user to also perform a + ``Ltac`` `ident` ``:=`` `convtactic`. + + See also: sections :ref:`performingcomputations` + + +.. _controlling-locality-of-commands: + +Controlling the locality of commands +----------------------------------------- + + +.. cmd:: Local @command +.. cmd:: Global @command + +Some commands support a Local or Global prefix modifier to control the +scope of their effect. There are four kinds of commands: + + ++ Commands whose default is to extend their effect both outside the + section and the module or library file they occur in. For these + commands, the Local modifier limits the effect of the command to the + current section or module it occurs in. As an example, the :cmd:`Coercion` + and :cmd:`Strategy` commands belong to this category. ++ Commands whose default behavior is to stop their effect at the end + of the section they occur in but to extent their effect outside the module or + library file they occur in. For these commands, the Local modifier limits the + effect of the command to the current module if the command does not occur in a + section and the Global modifier extends the effect outside the current + sections and current module if the command occurs in a section. As an example, + the :cmd:`Arguments`, :cmd:`Ltac` or :cmd:`Notation` commands belong + to this category. Notice that a subclass of these commands do not support + extension of their scope outside sections at all and the Global is not + applicable to them. ++ Commands whose default behavior is to stop their effect at the end + of the section or module they occur in. For these commands, the ``Global`` + modifier extends their effect outside the sections and modules they + occurs in. The :cmd:`Transparent` and :cmd:`Opaque` + (see Section :ref:`vernac-controlling-the-reduction-strategies`) commands + belong to this category. ++ Commands whose default behavior is to extend their effect outside + sections but not outside modules when they occur in a section and to + extend their effect outside the module or library file they occur in + when no section contains them.For these commands, the Local modifier + limits the effect to the current section or module while the Global + modifier extends the effect outside the module even when the command + occurs in a section. The :cmd:`Set` and :cmd:`Unset` commands belong to this + category. |