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 | 1300 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/proof-handling.rst | 600 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/ssreflect-proof-language.rst | 136 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/tactics.rst | 774 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/vernacular-commands.rst | 1357 |
6 files changed, 3754 insertions, 430 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..009758319b --- /dev/null +++ b/doc/sphinx/proof-engine/ltac.rst @@ -0,0 +1,1300 @@ +.. 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: ; + + 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 + + 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 + + In this variant, :n:`@expr` is applied to all focused goals. ``all:`` can only + be used at the toplevel of a tactic expression. + + .. tacv:: par: @expr + + 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:: Error message: 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 @natural + + 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 @natural` 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 @natural {* 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 @natural {* 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 @natural). + +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 + + 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 + + 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 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 ``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 ``Info`` contains + (in comments) the messages produced by the idtac + tacticals \ `4.2 <#ltac%3Aidtac>`__ at the right possition 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 ``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 + ``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 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 +performs a ``Set Ltac Profiling`` at the beginning of each document, and a +``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..86c94bab36 --- /dev/null +++ b/doc/sphinx/proof-engine/proof-handling.rst @@ -0,0 +1,600 @@ +.. 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. He 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`. +When switching in editing proof mode, the prompt ``Coq <`` is changed into +``ident <`` where ``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 Section :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 + :name: Qed (interactive proof) + +This command is available in interactive editing proof mode when the +proof is completed. Then ``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 (interactive proof) + +Defines the proved term as a transparent constant. + +.. cmdv:: Save @ident. + +Forces the name of the original goal to be :n:`@ident`. This +command (and the following ones) can only be used if the original goal +has been opened using the ``Goal`` command. + +.. cmd:: Admitted. + :name: Admitted (interactive proof) + +This command is available in interactive editing proof mode to give up +the current proof and declare the initial goal as an axiom. + +.. cmd:: Proof @term. + :name: Proof `term` + +This command applies in proof editing mode. It is equivalent to + +.. cmd:: exact @term. Qed. + +That is, you have to give the full proof in one gulp, as a +proof term (see Section :ref:`applyingtheorems`). + +.. cmdv:: Proof. + :name: Proof (interactive proof) + +Is a noop which is useful to delimit the sequence of tactic commands +which start a proof, after a ``Theorem`` command. It is a good practice to +use ``Proof``. as an opening parenthesis, closed in the script with a +closing ``Qed``. + + +See also: ``Proof with tactic.`` in Section +:ref:`tactics-implicit-automation`. + + +.. cmd:: Proof using @ident1 ... @identn. + +This command applies in proof editing mode. It declares the set of +section variables (see :ref:`gallina-assumptions`) used by the proof. At ``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 @ident1 ... @identn with @tactic. + +in Section :ref:`tactics-implicit-automation`. + +.. cmdv:: Proof using All. + +Use all section variables. + + +.. cmdv:: Proof using Type. + +.. cmdv:: Proof using. + +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 -(@ident1 ... @identn). + +Use all section variables except :n:`@ident1` ... :n:`@identn`. + + +.. cmdv:: Proof using @collection1 + @collection2 . + + +.. cmdv:: Proof using @collection1 - @collection2 . + + +.. cmdv:: Proof using @collection - ( @ident1 ... @identn ). + + +.. cmdv:: Proof using @collection * . + +Use section variables being, respectively, in the set union, set +difference, set complement, set forward transitive closure. See +Section :ref:`nameaset` to know how to form a named 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 ``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 := @section_subset_expr + +The command ``Collection`` can be used to name a set of section +hypotheses, with the purpose of making ``Proof using`` annotations more +compact. + + +.. cmdv:: Collection Some := x y z + +Define the collection named "Some" containing ``x``, ``y`` and ``z``. + + +.. cmdv:: Collection Fewer := Some - z + +Define the collection named "Fewer" containing only ``x`` and ``y``. + + +.. cmdv:: Collection Many := Fewer + Some +.. cmdv:: Collection Many := Fewer - Some + +Define the collection named "Many" containing the set union or set +difference of "Fewer" and "Some". + + +.. cmdv:: Collection Many := Fewer - (x y) + +Define the collection named "Many" containing the set difference of +"Fewer" and the unnamed collection ``x`` ``y`` + + +.. 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 :n:`@ident`. + +.. cmdv:: Abort All. + +Aborts all current goals, switching back to the |Coq| +toplevel. + + + +.. cmd:: Existential @num := @term. + +This command instantiates an existential variable. :n:`@num` is an index in +the list of uninstantiated existential variables displayed by ``Show +Existentials`` (described in Section :ref:`requestinginformation`). + +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`. + + +See also: ``instantiate (num:= term).`` in Section +:ref:`controllingtheproofflow`. +See also: ``Grab Existential Variables.`` below. + + +.. 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 :n:`@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. + + +.. cmdv:: Focus @num. + +This focuses the attention on the :n:`@num` th subgoal to +prove. + +*This command is deprecated since 8.8*: prefer the use of bullets or +focusing brackets instead, including :n:`@num : %{` + +.. cmd:: Unfocus. + +This command restores to focus the goal that were suspended by the +last ``Focus`` command. + +*This command is deprecated since 8.8.* + +.. cmd:: Unfocused. + +Succeeds if the proof is fully unfocused, fails is there are some +goals out of focus. + +.. _curly-braces: + +.. cmd:: %{ %| %} + +The command ``{`` (without a terminating period) focuses on the first +goal, much like ``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 :n:`@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 applied 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 +``````````````````` + +The bullet behavior can be controlled by the following commands. + +.. opt:: Bullet Behavior "None" + +This makes bullets inactive. + +.. opt:: Bullet Behavior "Strict Subproofs" + +This makes bullets active (this is the default behavior). + + +.. _requestinginformation: + +Requesting information +---------------------- + + +.. cmd:: Show. + +This command displays the current goals. + + +.. cmdv:: Show @num + +Displays only the :n:`@num`-th subgoal. + +.. exn:: No such goal +.. exn:: No focused proof + +.. cmdv:: Show @ident. + +Displays the named goal :n:`@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. + +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. + +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. + +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. + +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 ``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 ``intro`` +into a qualified one such as ``intro y13``. In the case of a non-product +goal, it prints nothing. + +.. cmdv:: Show Intros. + +This command is similar to the previous one, it +simulates the naming process of an intros. + +.. cmdv:: 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 +:n:`@ident` + +.. example:: + .. coqtop:: all + + Show Match nat. + +.. exn:: Unknown inductive type + +.. _ShowUniverses: + +.. cmdv:: 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` :ref:`applyingtheorems`) 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 ``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 ``Theorem ident [binders] : form``. When the +option is set, which is the default, binders are automatically put in +the local context of the goal to prove. + +The option can be unset by issuing ``Unset Automatic Introduction``. When +the option is unset, binders are discharged on the statement to be +proved and a tactic such as intro (see Section :ref:`managingthelocalcontext`) has to be +used to move the assumptions to the local context. + + +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 :tac:`optimize_heap`. diff --git a/doc/sphinx/proof-engine/ssreflect-proof-language.rst b/doc/sphinx/proof-engine/ssreflect-proof-language.rst index 61dffa0243..977a5b8fad 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 @@ -451,7 +448,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,7 +493,10 @@ 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. +.. tacn:: pose + :name: pose (ssreflect) + +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: @@ -518,7 +518,7 @@ 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 ``pose`` supoprts parameters: .. example:: @@ -1295,7 +1295,7 @@ 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. @@ -1352,6 +1352,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 +1504,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,7 +1576,7 @@ 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., @@ -1812,6 +1815,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 @@ -1831,7 +1836,7 @@ compact syntax: 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. @@ -2074,7 +2079,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 +2095,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 +2128,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 +2136,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: @@ -2215,7 +2220,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 +2264,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 +2340,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 +2356,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 +2497,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:: @@ -2752,12 +2757,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 ``````````````````````````````````` @@ -2845,8 +2847,8 @@ term -> G. If the optional list of :token:`itent` 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: @@ -2936,7 +2938,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 +3037,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 +3331,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 +3475,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 +3732,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 +3784,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 +3795,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 +3915,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 +3984,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 +4067,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 +4089,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 +4142,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 +4272,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 +4286,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 +4299,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 +4308,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 +4344,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 +4426,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 +4484,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 @@ -4689,7 +4692,7 @@ the bookkeeping tactical ``=>`` since this would be redundant with the 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 +5005,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 +5041,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 +5135,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 +5191,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 +5218,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. @@ -5491,7 +5495,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..7a45272f25 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,15 @@ specified, the default selector (see Section tactic_invocation : toplevel_selector : tactic. : |tactic . -.. cmd:: Set Default Goal Selector @toplevel_selector. - -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. - -.. cmd:: Test Default Goal Selector. +.. opt:: Default Goal Selector @toplevel_selector -This command displays the current default selector. + This option controls 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 value ``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. .. _bindingslist: @@ -94,7 +90,7 @@ bindings_list`` where ``bindings_list`` may be of two different forms: + 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 + and ``case`` (see :ref:`ltac`) 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 for the dependent products that are not bound in the conclusion of the type @@ -122,14 +118,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 @@ -154,10 +148,11 @@ Here are some tactics that understand occurrences clauses: ``set``, ``remember`` , ``induction``, ``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 --------------------- @@ -168,11 +163,12 @@ Applying theorems 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`). +:ref:`Conversion-rules`). .. exn:: Not an exact proof. .. tacv:: eexact @term. + :name: eexact This tactic behaves like exact but is able to handle terms and goals with meta-variables. @@ -186,6 +182,7 @@ the goal. If it is the case, the subgoal is proved. Otherwise, it fails. .. exn:: No such assumption. .. tacv:: eassumption + :name: eassumption This tactic behaves like assumption but is able to handle goals with meta-variables. @@ -238,6 +235,7 @@ useful to advanced users. cast around it. .. 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. @@ -248,6 +246,7 @@ useful to advanced users. resolution of typeclasses. .. tacv:: simple notypeclasses refine @term + :name: simple notypeclasses refine This tactic behaves like ``simple refine`` except it performs typechecking without resolution of typeclasses. @@ -277,7 +276,7 @@ gets the form :g:`(fun x => Q) u`:sub:`1` :g:`...` :g:`u`:sub:`n`. 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. +:tacn:`change` or :tacn:`pattern` tactics. .. exn:: Unable to find an instance for the variables {+ @ident}. @@ -285,7 +284,7 @@ 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: -.. 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 @@ -314,10 +313,11 @@ generated by ``apply term``:sub:`i` , starting from the application of 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 +instantiate (see :ref:`Existential-Variables`). The instantiation is intended to be found later in the proof. .. 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 @@ -340,11 +340,12 @@ does. .. 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``. .. tacv:: lapply @term - :name: `lapply + :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 @@ -435,7 +436,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`). @@ -520,8 +521,8 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. constructor of :g:`I`, then ``constructor i`` is equivalent to ``intros; apply c``:sub:`i`. -.. exn:: Not an inductive product. -.. exn:: Not enough constructors. +.. exn:: Not an inductive product +.. exn:: Not enough constructors .. tacv:: constructor @@ -539,34 +540,39 @@ 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 the case of an existential quantification :math:`\exists`:g:`x, P(x).` -.. exn:: Not an inductive goal with 1 constructor. +.. exn:: Not an inductive goal with 1 constructor .. tacv:: exists @bindings_list 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`. Then, they are respectively equivalent to ``constructor 1`` and ``constructor 2``. -.. exn:: Not an inductive goal with 2 constructors. +.. exn:: Not an inductive goal with 2 constructors .. tacv:: left with @bindings_list .. tacv:: right with @bindings_list @@ -577,15 +583,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,7 +614,7 @@ 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 @@ -616,7 +632,7 @@ 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 @@ -632,14 +648,14 @@ be applied or the goal is not head-reducible. .. 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 @@ -827,15 +843,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. + .. opt:: Bracketing Last Introduction Pattern - Force completion, if needed, when the last introduction pattern is a - disjunctive or conjunctive pattern (this is the default). - - .. 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 @@ -855,6 +866,7 @@ quantification or an implication. This is equivalent to :n:`clear @ident. ... clear @ident.` .. tacv:: clearbody @ident + :name: clearbody This tactic expects :n:`@ident` to be a local definition then clears its body. Otherwise said, this tactic turns a definition into an assumption. @@ -876,7 +888,7 @@ quantification or an implication. it. .. 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 @@ -992,6 +1004,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 +1012,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 +1030,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 +1083,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: @@ -1089,7 +1105,7 @@ Controlling the proof flow .. 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 @@ -1098,6 +1114,7 @@ Controlling the proof flow generated by assert. .. exn:: Proof is not complete + :name: Proof is not complete (assert) .. tacv:: assert form as intro_pattern @@ -1121,6 +1138,7 @@ Controlling the proof flow .. exn:: Variable @ident is already declared .. tacv:: eassert form as intro_pattern by tactic + :name: eassert .. tacv:: assert (@ident := @term) @@ -1130,6 +1148,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 +1162,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 @@ -1168,22 +1188,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 @@ -1236,7 +1261,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 +1293,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 @@ -1353,11 +1378,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 +1450,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 +1477,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 +1487,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. @@ -1556,6 +1586,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 +1659,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 +1667,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 +1678,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 +1689,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 +1774,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 +1789,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,22 +1816,22 @@ 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 @@ -1849,6 +1884,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 @@ -1902,7 +1938,7 @@ 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`), +equality has been declared using the command ``Scheme Equality`` (see :ref:`proofschemes-induction-principles`), the use of a sigma type is avoided. .. note:: @@ -1928,6 +1964,7 @@ the use of a sigma type is avoided. .. tacv:: einjection @num .. tacv:: einjection @term {? with @bindings_list} + :name: einjection 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 @@ -1955,17 +1992,19 @@ the use of a sigma type is avoided. 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 +2023,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 @@ -2117,6 +2156,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 +2340,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 +2361,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,7 +2375,7 @@ 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 @@ -2417,6 +2457,7 @@ subgoals. leading to failure if these n rewrites are not possible. .. tacv:: erewrite @term + :name: erewrite This tactic works as :n:`rewrite @term` but turning unresolved bindings into existential variables, if any, instead of @@ -2463,6 +2504,7 @@ subgoals. clause argument must not contain any type of nor value of. .. tacv:: cutrewrite <- (@term = @term) + :cutrewrite: This tactic is deprecated. It acts like :n:`replace @term with @term`, or, equivalently as :n:`enough (@term = @term) as <-`. @@ -2506,30 +2548,30 @@ unfolded and cleared. 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`. - .. note:: - 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: + .. opt:: Regular Subst Tactic + + This option controls the behavior of :tacn:`subst`. When it is + activated, :tacn:`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`. + + 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`. - 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. + 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. .. tacn:: stepl @term @@ -2543,30 +2585,37 @@ 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`. -Lemmas are added to the database using the command ``Declare Left Step @term.`` +.. cmd:: Declare Left Step @term + + 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:`TODO-27-Generalizedrewriting`). +:ref:`Generalizedrewriting`). .. tacv:: stepl @term by tactic - This applies :n:`stepl @term` then applies tactic to the second goal. + This applies :n:`stepl @term` then applies tactic to the second goal. .. tacv:: stepr @term stepr @term by tactic + :name: stepr + + 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`. - 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.`` + .. cmd:: 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. + 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 @@ -2637,7 +2686,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 +2698,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 +2753,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 +2763,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 @@ -2768,7 +2819,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 @@ -2906,7 +2957,7 @@ 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. @@ -2942,7 +2993,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 @@ -3103,7 +3154,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>` @@ -3258,188 +3309,203 @@ 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 -.. cmd:: Hint hint_definition + No database name is given: the hint is registered in the core database. - No database name is given: the hint is registered in the core database. + .. cmdv:: Local Hint @hint_definition : {+ @ident} -.. cmd:: 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. - 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:: Local Hint hint_definition + Idem for the core database. - Idem for the core database. + .. cmdv:: Hint Resolve @term {? | {? @num} {? @pattern}} + :name: Hint Resolve -The ``hint_definition`` is one of the following expressions: + 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. -+ :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. + .. exn:: @term cannot be used as a hint - .. exn:: @term cannot be used as a hint + The head symbol of the type of :n:`@term` is a bound variable such that + this tactic cannot be associated to a constant. - The head symbol of the type of :n:`@term` is a bound variable such that - this tactic cannot be associated to a constant. + .. cmdv:: Hint Resolve {+ @term} - **Variants:** + Adds each :n:`Hint Resolve @term`. - + :n:`Resolve {+ @term}` - Adds each :n:`Resolve @term`. + .. cmdv:: Hint Resolve -> @term - + :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``). + 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`). - + :n:`Resolve <- @term` - Adds the right-to-left implication of an equivalence as a hint. + .. cmdv:: Resolve <- @term -+ :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. + Adds the right-to-left implication of an equivalence as a hint. - .. exn:: @term cannot be used as a hint + .. cmdv:: Hint Immediate @term + :name: Hint Immediate - **Variants:** + 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 :tacn:`trivial` + itself. - + :n:`Immediate {+ @term}` - Adds each :n:`Immediate @term`. + .. exn:: @term cannot be used as a hint -+ :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. + .. cmdv:: Immediate {+ @term} - .. exn:: @ident is not an inductive type + Adds each :n:`Hint Immediate @term`. - **Variants:** + .. cmdv:: Hint Constructors @ident + :name: Hint Constructors - + :n:`Constructors {+ @ident}` - Adds each :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 ...)`, :tacn:`auto` will try to apply each constructor. -+ :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. + .. exn:: @ident is not an inductive type - **Variants:** + .. cmdv:: Hint Constructors {+ @ident} - + :n:`Unfold {+ @ident}` - Adds each :n:`Unfold @ident`. + Adds each :n:`Hint Constructors @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 Unfold @qualid + :name: Hint Unfold - **Variants:** + 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. - + :n:`Transparent`, :n:`Opaque {+ @ident}` - Declares each :n:`@ident` as a transparent or opaque constant. + .. cmdv:: Hint Unfold {+ @ident} -+ :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. + Adds each :n:`Hint Unfold @ident`. -.. note:: - One can use an ``Extern`` hint with no pattern to do pattern-matching on - hypotheses using ``match goal`` with inside the tactic. + .. cmdv:: Hint %( Transparent %| Opaque %) @qualid + :name: Hint ( Transparent | Opaque ) + + 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} + + Declares each :n:`@ident` as a transparent or opaque constant. + + .. cmdv:: Hint Extern @num {? @pattern} => 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 +3587,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. @@ -3573,69 +3639,65 @@ We propose a smooth transitional path by providing the ``Loose Hint Behavior`` option which accepts three flags allowing for a fine-grained handling of non-imported hints. -**Variants:** +.. opt:: Loose Hint Behavior %( "Lax" %| "Warn" %| "Strict" %) -.. cmd:: Set Loose Hint Behavior "Lax" + This option accepts three values, which control the behavior of hints w.r.t. + :cmd:`Import`: - This is the default, and corresponds to the historical behavior, that - is, hints defined outside of a section have a global scope. + - "Lax": this is the default, and corresponds to the historical behavior, + that is, hints defined outside of a section have a global scope. -.. cmd:: Set Loose Hint Behavior "Warn" + - "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. - 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. + - "Strict": changes the behavior of an unloaded hint to a immediate fail + tactic, allowing to emulate an import-scoped hint mechanism. -.. cmd:: Set Loose Hint Behavior "Strict" - - 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`. - -**Variants:** + See also: ``Proof.`` in :ref:`proof-editing-mode`. -.. cmd:: Proof with tactic using {+ @ident} - Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`TODO-7.1.5-Proofusing` + .. cmdv:: Proof with tactic using {+ @ident} -.. cmd:: Proof using {+ @ident} with tactic + Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`proof-editing-mode` - Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`TODO-7.1.5-Proofusing` + .. cmdv:: Proof using {+ @ident} with @tactic -.. cmd:: Declare Implicit Tactic tactic + Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`proof-editing-mode` - 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. + .. cmd:: Declare Implicit Tactic @tactic -Here is an example: + 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. -.. example:: + .. example:: - .. coqtop:: all + .. coqtop:: all - 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). + 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)``. + 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 +3742,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 +3776,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 @@ -3730,17 +3793,10 @@ some incompatibilities. 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 +.. 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 +3820,15 @@ 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 + + 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 and + printed using :cmd:`Print Firstorder Solver`. .. 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 +3845,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 @natural + + This option controls the proof-search depth bound. .. tacn:: congruence :name: congruence @@ -3878,7 +3936,7 @@ succeeds, and results in an error otherwise. .. 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 @@ -4009,6 +4067,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 @@ -4020,7 +4079,7 @@ symbol :g:`=`. :n:`intro @ident; simplify_eq @ident`. .. tacn:: dependent rewrite -> @ident - :name: dependent rewrite -> + :name: dependent rewrite This tactic applies to any goal. If :n:`@ident` has type :g:`(existT B a b)=(existT B a' b')` in the local context (i.e. each @@ -4044,7 +4103,7 @@ 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``. @@ -4077,7 +4136,7 @@ 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 @@ -4109,6 +4168,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 +4209,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 +4229,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 +4255,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,7 +4347,7 @@ 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 @@ -4302,8 +4363,7 @@ This tactics reverses the list of the focused goals. 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 +4394,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..692ff294a6 --- /dev/null +++ b/doc/sphinx/proof-engine/vernacular-commands.rst @@ -0,0 +1,1357 @@ +.. include:: ../preamble.rst +.. include:: ../replaces.rst + +.. _vernacularcommands: + +Vernacular commands +============================= + +.. _displaying: + +Displaying +-------------- + + +.. _Print: + +.. cmd:: Print @qualid. + +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 :n:`num`. + +.. exn:: This object does not support universe names. + + +Variants: + + +.. cmdv:: Print Term @qualid. + +This is a synonym to ``Print`` :n:`@qualid` when :n:`@qualid` +denotes a global constant. + +.. cmdv:: 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:: Print @qualid\@@name + +This locally renames the polymorphic universes of :n:`@qualid`. +An underscore means the raw universe is printed. +This form can be used with ``Print Term`` and ``About``. + +.. cmd:: Print All. + +This command displays information about the current state of the +environment, including sections and modules. + + +Variants: + + +.. 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. + +Variants: + +.. 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. + + +Variants: + +.. 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. + + +Variants: + +.. 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`. + + +Variants: + + +.. 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. + + +Variants: + + +.. cmdv:: Print Tables. + +This is a synonymous of ``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. + + +Variants: + +.. TODO : selector is not a syntax entry + +.. cmdv:: @selector: Check @term. + +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::Extraction @term. + +This command displays the extracted term from :n:`@term`. The extraction is +processed according to the distinction between :g:`Set` and :g:`Prop`; that is +to say, between logical and computational content (see Section :ref:`sorts`). +The extracted term is displayed in OCaml syntax, where global identifiers are +still displayed as in |Coq| terms. + + +Variants: + + +.. cmdv:: Recursive Extraction {+ @qualid }. + +Recursively extracts all +the material needed for the extraction of the qualified identifiers. + + +See also: Chapter :ref:`extraction`. + + +.. 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. + + +Variants: + + +.. cmdv:: Print Opaque Dependencies @qualid. + +Displays the set of opaque constants :n:`@qualid` relies on in addition to +the assumptions. + +.. cmdv:: Print Transparent Dependencies @qualid. + +Displays the set of +transparent constants :n:`@qualid` relies on in addition to the assumptions. + +.. cmdv:: Print All Dependencies @qualid. + +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. + + +Error messages: + + +.. exn:: The reference @qualid was not found in the current environment + +There is no constant in the environment named qualid. + +Variants: + +.. 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. + + +.. 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. + +.. note:: Up to |Coq| version 8.4, ``Search`` had the behavior of current + ``SearchHead`` and the behavior of current Search was obtained with + command ``SearchAbout``. For compatibility, the deprecated name + SearchAbout can still be used as a synonym of Search. For + compatibility, the list of objects to search when using ``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. + + + +.. coqtop:: reset all + + SearchHead le. + + SearchHead (@eq bool). + + +Variants: + +.. 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. + +Error messages: + +.. 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 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. + +.. 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`. + + +.. coqtop:: all + + SearchPattern (?X1 + _ = _ + ?X1). + +Variants: + + +.. 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. + + + +.. cmdv:: 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 “_”. + +.. coqtop:: in + + Require Import Arith. + +.. coqtop:: all + + SearchRewrite (_ + _ + _). + +Variants: + + +.. 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:: + + For the ``Search``, ``SearchHead``, ``SearchPattern`` and ``SearchRewrite`` + queries, it + is possible to globally filter the search results via the command + ``Add Search Blacklist`` :n:`@substring`. A lemma whose fully-qualified name + contains any of the declared substrings will be removed from the + search results. The default blacklisted substrings are ``_subproof`` + ``Private_``. The command ``Remove Search Blacklist ...`` 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. + +.. coqtop:: none + + Set Printing Depth 50. + +.. coqtop:: all + + Locate nat. + + Locate Datatypes.O. + + Locate Init.Datatypes.O. + + Locate Coq.Init.Datatypes.O. + + Locate I.Dont.Exist. + +Variants: + + +.. 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. + +Variants: + + +.. 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`. + +Error messages: + +.. 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 +``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. + + +Variants: + +.. cmdv:: Require Import @qualid. + +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 ``Require Export``, as described below, or recursively required +through a sequence of ``Require Export``. If the module required has +already been loaded, ``Require Import`` :n:`@qualid` simply imports it, as ``Import`` +:n:`@qualid` would. + +.. cmdv:: Require Export @qualid. + +This command acts as ``Require Import`` :n:`@qualid`, +but if a further module, say `A`, contains a command ``Require Export`` `B`, +then the command ``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 ``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. + + + +Error messages: + +.. 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). + + +Variants: + + +.. 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. + + + +Error messages: + +.. 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. + + +Variants: + + +.. 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. + +Variants: + + +.. 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. + +Variants: + + +.. cmdv:: Add Rec LoadPath @string. + +Works as ``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. + + +Variants: + + +.. cmdv:: Print LoadPath @dirpath. + +Works as ``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 ``Declare ML Module`` +in Section :ref:`compiled-files`). + + +.. 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. + + +Error messages: + +.. exn:: @ident: no such entry + +Variants: + +.. cmd:: Reset Initial. + +Goes back to the initial state, just after the start +of the interactive session. + + + +.. cmd:: Back. + +This commands undoes all the effects of the last vernacular command. +Commands read from a vernacular file via a ``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 +``Qed``, the management information about the closed proof has been +discarded. In this case, ``Back`` will then undo all the proof steps up to +the statement of this proof. + + +Variants: + + +.. cmdv:: Back @num. + +Undoes :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. + + + +Error messages: + + +.. 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 ``Back`` (see +above), the ``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. + + +Variants: + + +.. cmdv:: Backtrack @num @num @num. + +`Backtrack` is a *deprecated* form of +`BackTo` which allows explicitly manipulating the proof environment. The +three numbers represent the following: + + + *first number* : State label to reach, as for BackTo. + + *second number* : *Proof state number* to unbury once aborts have been done. + |Coq| will compute the number of Undo to perform (see Chapter :ref:`proofhandling`). + + *third number* : Number of Abort to perform, i.e. the number of currently + opened nested proofs that must be canceled (see Chapter :ref:`proofhandling`). + + + + +Error messages: + + +.. 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. + +Error messages: + +.. 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 @integer + + 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 @integer + + 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 ``Definition`` or ``Let`` (with an explicit body), or by a command +assimilated to a definition such as ``Fixpoint``, ``Program Definition``, etc, +or by a proof ended by ``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). + +``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. + +The scope of ``Opaque`` is limited to the current section, or current +file, unless the variant ``Global Opaque`` is used. + + +See also: sections :ref:`performingcomputations`, :ref:`tactics-automatizing`, :ref:`proof-editing-mode` + + +Error messages: + + +.. 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 ``Opaque`` `foo` `bar` and if `bar` does not exist, `foo` is set opaque. + +.. cmd:: Transparent {+ @qualid }. + +This command is the converse of `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. + +The scope of Transparent is limited to the current section, or current +file, unless the variant ``Global Transparent`` is +used. + + +Error messages: + + +.. 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 −∞) + + +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 ``Transparent`` and +``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. + + +Error messages: + + +.. exn:: The reference is not unfoldable. + + + +Variants: + + +.. 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 ``Coercion`` + (see Section :ref:`coercions`) and ``Strategy`` (see :ref:`here <vernac-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:`Implicit 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 ``Transparent`` and ``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 ``Set`` and ``Unset`` commands belong to this + category. |