diff options
Diffstat (limited to 'doc/sphinx/proof-engine')
| -rw-r--r-- | doc/sphinx/proof-engine/detailed-tactic-examples.rst | 17 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/ltac.rst | 1310 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/proof-handling.rst | 596 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/ssreflect-proof-language.rst | 46 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/tactics.rst | 1364 | ||||
| -rw-r--r-- | doc/sphinx/proof-engine/vernacular-commands.rst | 1584 |
6 files changed, 3073 insertions, 1844 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..2b128b98fe --- /dev/null +++ b/doc/sphinx/proof-engine/ltac.rst @@ -0,0 +1,1310 @@ +.. include:: ../preamble.rst +.. include:: ../replaces.rst + +.. _ltac: + +The tactic language +=================== + +This chapter gives a compact documentation of |Ltac|, the tactic language +available in |Coq|. We start by giving the syntax, and next, we present the +informal semantics. If you want to know more regarding this language and +especially about its foundations, you can refer to :cite:`Del00`. Chapter +:ref:`detailedexamplesoftactics` is devoted to giving examples of use of this +language on small but also with non-trivial problems. + +.. _ltac-syntax: + +Syntax +------ + +The syntax of the tactic language is given below. See Chapter +:ref:`gallinaspecificationlanguage` for a description of the BNF metasyntax used +in these grammar rules. Various already defined entries will be used in this +chapter: entries :token:`natural`, :token:`integer`, :token:`ident`, +:token:`qualid`, :token:`term`, :token:`cpattern` and :token:`atomic_tactic` +represent respectively the natural and integer numbers, the authorized +identificators and qualified names, Coq terms and patterns and all the atomic +tactics described in Chapter :ref:`tactics`. The syntax of :token:`cpattern` is +the same as that of terms, but it is extended with pattern matching +metavariables. In :token:`cpattern`, a pattern-matching metavariable is +represented with the syntax :g:`?id` where :g:`id` is an :token:`ident`. The +notation :g:`_` can also be used to denote metavariable whose instance is +irrelevant. In the notation :g:`?id`, the identifier allows us to keep +instantiations and to make constraints whereas :g:`_` shows that we are not +interested in what will be matched. On the right hand side of pattern-matching +clauses, the named metavariable are used without the question mark prefix. There +is also a special notation for second-order pattern-matching problems: in an +applicative pattern of the form :g:`@?id id1 … idn`, the variable id matches any +complex expression with (possible) dependencies in the variables :g:`id1 … idn` +and returns a functional term of the form :g:`fun id1 … idn => term`. + +The main entry of the grammar is :n:`@expr`. This language is used in proof +mode but it can also be used in toplevel definitions as shown below. + +.. note:: + + - The infix tacticals “… \|\| …”, “… + …”, and “… ; …” are associative. + + - In :token:`tacarg`, there is an overlap between qualid as a direct tactic + argument and :token:`qualid` as a particular case of term. The resolution is + done by first looking for a reference of the tactic language and if + it fails, for a reference to a term. To force the resolution as a + reference of the tactic language, use the form :g:`ltac:(@qualid)`. To + force the resolution as a reference to a term, use the syntax + :g:`(@qualid)`. + + - As shown by the figure, tactical ``\|\|`` binds more than the prefix + tacticals try, repeat, do and abstract which themselves bind more + than the postfix tactical “… ;[ … ]” which binds more than “… ; …”. + + For instance + + .. coqtop:: in + + try repeat tac1 || tac2; tac3; [tac31 | ... | tac3n]; tac4. + + is understood as + + .. coqtop:: in + + try (repeat (tac1 || tac2)); + ((tac3; [tac31 | ... | tac3n]); tac4). + +.. productionlist:: coq + expr : `expr` ; `expr` + : | [> `expr` | ... | `expr` ] + : | `expr` ; [ `expr` | ... | `expr` ] + : | `tacexpr3` + tacexpr3 : do (`natural` | `ident`) tacexpr3 + : | progress `tacexpr3` + : | repeat `tacexpr3` + : | try `tacexpr3` + : | once `tacexpr3` + : | exactly_once `tacexpr3` + : | timeout (`natural` | `ident`) `tacexpr3` + : | time [`string`] `tacexpr3` + : | only `selector`: `tacexpr3` + : | `tacexpr2` + tacexpr2 : `tacexpr1` || `tacexpr3` + : | `tacexpr1` + `tacexpr3` + : | tryif `tacexpr1` then `tacexpr1` else `tacexpr1` + : | `tacexpr1` + tacexpr1 : fun `name` ... `name` => `atom` + : | let [rec] `let_clause` with ... with `let_clause` in `atom` + : | match goal with `context_rule` | ... | `context_rule` end + : | match reverse goal with `context_rule` | ... | `context_rule` end + : | match `expr` with `match_rule` | ... | `match_rule` end + : | lazymatch goal with `context_rule` | ... | `context_rule` end + : | lazymatch reverse goal with `context_rule` | ... | `context_rule` end + : | lazymatch `expr` with `match_rule` | ... | `match_rule` end + : | multimatch goal with `context_rule` | ... | `context_rule` end + : | multimatch reverse goal with `context_rule` | ... | `context_rule` end + : | multimatch `expr` with `match_rule` | ... | `match_rule` end + : | abstract `atom` + : | abstract `atom` using `ident` + : | first [ `expr` | ... | `expr` ] + : | solve [ `expr` | ... | `expr` ] + : | idtac [ `message_token` ... `message_token`] + : | fail [`natural`] [`message_token` ... `message_token`] + : | fresh | fresh `string` | fresh `qualid` + : | context `ident` [`term`] + : | eval `redexpr` in `term` + : | type of `term` + : | constr : `term` + : | uconstr : `term` + : | type_term `term` + : | numgoals + : | guard `test` + : | assert_fails `tacexpr3` + : | assert_suceeds `tacexpr3` + : | `atomic_tactic` + : | `qualid` `tacarg` ... `tacarg` + : | `atom` + atom : `qualid` + : | () + : | `integer` + : | ( `expr` ) + message_token : `string` | `ident` | `integer` + tacarg : `qualid` + : | () + : | ltac : `atom` + : | `term` + let_clause : `ident` [`name` ... `name`] := `expr` + context_rule : `context_hyp`, ..., `context_hyp` |- `cpattern` => `expr` + : | `cpattern` => `expr` + : | |- `cpattern` => `expr` + : | _ => `expr` + context_hyp : `name` : `cpattern` + : | `name` := `cpattern` [: `cpattern`] + match_rule : `cpattern` => `expr` + : | context [ident] [ `cpattern` ] => `expr` + : | _ => `expr` + test : `integer` = `integer` + : | `integer` (< | <= | > | >=) `integer` + selector : [`ident`] + : | `integer` + : (`integer` | `integer` - `integer`), ..., (`integer` | `integer` - `integer`) + toplevel_selector : `selector` + : | `all` + : | `par` + +.. productionlist:: coq + top : [Local] Ltac `ltac_def` with ... with `ltac_def` + ltac_def : `ident` [`ident` ... `ident`] := `expr` + : | `qualid` [`ident` ... `ident`] ::= `expr` + +.. _ltac-semantics: + +Semantics +--------- + +Tactic expressions can only be applied in the context of a proof. The +evaluation yields either a term, an integer or a tactic. Intermediary +results can be terms or integers but the final result must be a tactic +which is then applied to the focused goals. + +There is a special case for ``match goal`` expressions of which the clauses +evaluate to tactics. Such expressions can only be used as end result of +a tactic expression (never as argument of a non recursive local +definition or of an application). + +The rest of this section explains the semantics of every construction of +|Ltac|. + +Sequence +~~~~~~~~ + +A sequence is an expression of the following form: + +.. tacn:: @expr ; @expr + :name: ; + + The expression :n:`@expr__1` is evaluated to :n:`v__1`, which must be + a tactic value. The tactic :n:`v__1` is applied to the current goal, + possibly producing more goals. Then :n:`@expr__2` is evaluated to + produce :n:`v__2`, which must be a tactic value. The tactic + :n:`v__2` is applied to all the goals produced by the prior + application. Sequence is associative. + +Local application of tactics +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Different tactics can be applied to the different goals using the +following form: + +.. tacn:: [> {*| @expr }] + :name: [> ... | ... | ... ] (dispatch) + + The expressions :n:`@expr__i` are evaluated to :n:`v__i`, for + i=0,...,n and all have to be tactics. The :n:`v__i` is applied to the + i-th goal, for =1,...,n. It fails if the number of focused goals is not + exactly n. + + .. note:: + + If no tactic is given for the i-th goal, it behaves as if the tactic idtac + were given. For instance, ``[> | auto]`` is a shortcut for ``[> idtac | auto + ]``. + + .. tacv:: [> {*| @expr} | @expr .. | {*| @expr}] + + In this variant, token:`expr` is used for each goal coming after those + covered by the first list of :n:`@expr` but before those coevered by the + last list of :n:`@expr`. + + .. tacv:: [> {*| @expr} | .. | {*| @expr}] + + In this variant, idtac is used for the goals not covered by the two lists of + :n:`@expr`. + + .. tacv:: [> @expr .. ] + + In this variant, the tactic :n:`@expr` is applied independently to each of + the goals, rather than globally. In particular, if there are no goal, the + tactic is not run at all. A tactic which expects multiple goals, such as + ``swap``, would act as if a single goal is focused. + + .. tacv:: expr ; [{*| @expr}] + + This variant of local tactic application is paired with a sequence. In this + variant, there must be as many :n:`@expr` in the list as goals generated + by the application of the first :n:`@expr` to each of the individual goals + independently. All the above variants work in this form too. + Formally, :n:`@expr ; [ ... ]` is equivalent to :n:`[> @expr ; [> ... ] .. ]`. + +.. _goal-selectors: + +Goal selectors +~~~~~~~~~~~~~~ + +We can restrict the application of a tactic to a subset of the currently +focused goals with: + +.. tacn:: @toplevel_selector : @expr + :name: ... : ... (goal selector) + + We can also use selectors as a tactical, which allows to use them nested + in a tactic expression, by using the keyword ``only``: + + .. tacv:: only selector : expr + :name: only ... : ... + + When selecting several goals, the tactic expr is applied globally to all + selected goals. + + .. tacv:: [@ident] : @expr + + In this variant, :n:`@expr` is applied locally to a goal previously named + by the user (see :ref:`existential-variables`). + + .. tacv:: @num : @expr + + In this variant, :n:`@expr` is applied locally to the :token:`num`-th goal. + + .. tacv:: {+, @num-@num} : @expr + + In this variant, :n:`@expr` is applied globally to the subset of goals + described by the given ranges. You can write a single ``n`` as a shortcut + for ``n-n`` when specifying multiple ranges. + + .. tacv:: all: @expr + :name: all: ... + + In this variant, :n:`@expr` is applied to all focused goals. ``all:`` can only + be used at the toplevel of a tactic expression. + + .. tacv:: !: @expr + + In this variant, if exactly one goal is focused :n:`expr` is + applied to it. Otherwise the tactical fails. ``!:`` can only be + used at the toplevel of a tactic expression. + + .. tacv:: par: @expr + :name: par: ... + + In this variant, :n:`@expr` is applied to all focused goals in parallel. + The number of workers can be controlled via the command line option + ``-async-proofs-tac-j`` taking as argument the desired number of workers. + Limitations: ``par:`` only works on goals containing no existential + variables and :n:`@expr` must either solve the goal completely or do + nothing (i.e. it cannot make some progress). ``par:`` can only be used at + the toplevel of a tactic expression. + + .. exn:: No such goal. + :name: No such goal. (Goal selector) + + .. TODO change error message index entry + +For loop +~~~~~~~~ + +There is a for loop that repeats a tactic :token:`num` times: + +.. tacn:: do @num @expr + :name: do + + :n:`@expr` is evaluated to ``v`` which must be a tactic value. This tactic + value ``v`` is applied :token:`num` times. Supposing :token:`num` > 1, after the + first application of ``v``, ``v`` is applied, at least once, to the generated + subgoals and so on. It fails if the application of ``v`` fails before the num + applications have been completed. + +Repeat loop +~~~~~~~~~~~ + +We have a repeat loop with: + +.. tacn:: repeat @expr + :name: repeat + + :n:`@expr` is evaluated to ``v``. If ``v`` denotes a tactic, this tactic is + applied to each focused goal independently. If the application succeeds, the + tactic is applied recursively to all the generated subgoals until it eventually + fails. The recursion stops in a subgoal when the tactic has failed *to make + progress*. The tactic :n:`repeat @expr` itself never fails. + +Error catching +~~~~~~~~~~~~~~ + +We can catch the tactic errors with: + +.. tacn:: try @expr + :name: try + + :n:`@expr` is evaluated to ``v`` which must be a tactic value. The tactic + value ``v`` is applied to each focused goal independently. If the application of + ``v`` fails in a goal, it catches the error and leaves the goal unchanged. If the + level of the exception is positive, then the exception is re-raised with its + level decremented. + +Detecting progress +~~~~~~~~~~~~~~~~~~ + +We can check if a tactic made progress with: + +.. tacn:: progress expr + :name: progress + + :n:`@expr` is evaluated to v which must be a tactic value. The tactic value ``v`` + is applied to each focued subgoal independently. If the application of ``v`` + to one of the focused subgoal produced subgoals equal to the initial + goals (up to syntactical equality), then an error of level 0 is raised. + + .. exn:: Failed to progress. + +Backtracking branching +~~~~~~~~~~~~~~~~~~~~~~ + +We can branch with the following structure: + +.. tacn:: @expr__1 + @expr__2 + :name: + (backtracking branching) + + :n:`@expr__1` and :n:`@expr__2` are evaluated respectively to :n:`v__1` and + :n:`v__2` which must be tactic values. The tactic value :n:`v__1` is applied to + each focused goal independently and if it fails or a later tactic fails, then + the proof backtracks to the current goal and :n:`v__2` is applied. + + Tactics can be seen as having several successes. When a tactic fails it + asks for more successes of the prior tactics. + :n:`@expr__1 + @expr__2` has all the successes of :n:`v__1` followed by all the + successes of :n:`v__2`. Algebraically, + :n:`(@expr__1 + @expr__2); @expr__3 = (@expr__1; @expr__3) + (@expr__2; @expr__3)`. + + Branching is left-associative. + +First tactic to work +~~~~~~~~~~~~~~~~~~~~ + +Backtracking branching may be too expensive. In this case we may +restrict to a local, left biased, branching and consider the first +tactic to work (i.e. which does not fail) among a panel of tactics: + +.. tacn:: first [{*| @expr}] + :name: first + + The :n:`@expr__i` are evaluated to :n:`v__i` and :n:`v__i` must be + tactic values, for i=1,...,n. Supposing n>1, it applies, in each focused + goal independently, :n:`v__1`, if it works, it stops otherwise it + tries to apply :n:`v__2` and so on. It fails when there is no + applicable tactic. In other words, + :n:`first [:@expr__1 | ... | @expr__n]` behaves, in each goal, as the the first + :n:`v__i` to have *at least* one success. + + .. exn:: No applicable tactic. + + .. tacv:: first @expr + + This is an |Ltac| alias that gives a primitive access to the first + tactical as a |Ltac| definition without going through a parsing rule. It + expects to be given a list of tactics through a ``Tactic Notation``, + allowing to write notations of the following form: + + .. example:: + + .. coqtop:: in + + Tactic Notation "foo" tactic_list(tacs) := first tacs. + +Left-biased branching +~~~~~~~~~~~~~~~~~~~~~ + +Yet another way of branching without backtracking is the following +structure: + +.. tacn:: @expr__1 || @expr__2 + :name: || (left-biased branching) + + :n:`@expr__1` and :n:`@expr__2` are evaluated respectively to :n:`v__1` and + :n:`v__2` which must be tactic values. The tactic value :n:`v__1` is + applied in each subgoal independently and if it fails *to progress* then + :n:`v__2` is applied. :n:`@expr__1 || @expr__2` is + equivalent to :n:`first [ progress @expr__1 | @expr__2 ]` (except that + if it fails, it fails like :n:`v__2`). Branching is left-associative. + +Generalized biased branching +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +The tactic + +.. tacn:: tryif @expr__1 then @expr__2 else @expr__3 + :name: tryif + + is a generalization of the biased-branching tactics above. The + expression :n:`@expr__1` is evaluated to :n:`v__1`, which is then + applied to each subgoal independently. For each goal where :n:`v__1` + succeeds at least once, :n:`@expr__2` is evaluated to :n:`v__2` which + is then applied collectively to the generated subgoals. The :n:`v__2` + tactic can trigger backtracking points in :n:`v__1`: where :n:`v__1` + succeeds at least once, + :n:`tryif @expr__1 then @expr__2 else @expr__3` is equivalent to + :n:`v__1; v__2`. In each of the goals where :n:`v__1` does not succeed at least + once, :n:`@expr__3` is evaluated in :n:`v__3` which is is then applied to the + goal. + +Soft cut +~~~~~~~~ + +Another way of restricting backtracking is to restrict a tactic to a +single success *a posteriori*: + +.. tacn:: once @expr + :name: once + + :n:`@expr` is evaluated to ``v`` which must be a tactic value. The tactic value + ``v`` is applied but only its first success is used. If ``v`` fails, + :n:`once @expr` fails like ``v``. If ``v`` has a least one success, + :n:`once @expr` succeeds once, but cannot produce more successes. + +Checking the successes +~~~~~~~~~~~~~~~~~~~~~~ + +Coq provides an experimental way to check that a tactic has *exactly +one* success: + +.. tacn:: exactly_once @expr + :name: exactly_once + + :n:`@expr` is evaluated to ``v`` which must be a tactic value. The tactic value + ``v`` is applied if it has at most one success. If ``v`` fails, + :n:`exactly_once @expr` fails like ``v``. If ``v`` has a exactly one success, + :n:`exactly_once @expr` succeeds like ``v``. If ``v`` has two or more + successes, exactly_once expr fails. + + .. warning:: + + The experimental status of this tactic pertains to the fact if ``v`` + performs side effects, they may occur in a unpredictable way. Indeed, + normally ``v`` would only be executed up to the first success until + backtracking is needed, however exactly_once needs to look ahead to see + whether a second success exists, and may run further effects + immediately. + + .. exn:: This tactic has more than one success. + +Checking the failure +~~~~~~~~~~~~~~~~~~~~ + +Coq provides a derived tactic to check that a tactic *fails*: + +.. tacn:: assert_fails @expr + :name: assert_fails + + This behaves like :n:`tryif @expr then fail 0 tac "succeeds" else idtac`. + +Checking the success +~~~~~~~~~~~~~~~~~~~~ + +Coq provides a derived tactic to check that a tactic has *at least one* +success: + +.. tacn:: assert_succeeds @expr + :name: assert_suceeds + + This behaves like + :n:`tryif (assert_fails tac) then fail 0 tac "fails" else idtac`. + +Solving +~~~~~~~ + +We may consider the first to solve (i.e. which generates no subgoal) +among a panel of tactics: + +.. tacn:: solve [{*| @expr}] + :name: solve + + The :n:`@expr__i` are evaluated to :n:`v__i` and :n:`v__i` must be + tactic values, for i=1,...,n. Supposing n>1, it applies :n:`v__1` to + each goal independently, if it doesn’t solve the goal then it tries to + apply :n:`v__2` and so on. It fails if there is no solving tactic. + + .. exn:: Cannot solve the goal. + + .. tacv:: solve @expr + + This is an |Ltac| alias that gives a primitive access to the :n:`solve:` + tactical. See the :n:`first` tactical for more information. + +Identity +~~~~~~~~ + +The constant :n:`idtac` is the identity tactic: it leaves any goal unchanged but +it appears in the proof script. + +.. tacn:: idtac {* message_token} + :name: idtac + + This prints the given tokens. Strings and integers are printed + literally. If a (term) variable is given, its contents are printed. + +Failing +~~~~~~~ + +.. tacn:: fail + :name: fail + + This is the always-failing tactic: it does not solve any + goal. It is useful for defining other tacticals since it can be caught by + :tacn:`try`, :tacn:`repeat`, :tacn:`match goal`, or the branching tacticals. The + :tacn:`fail` tactic will, however, succeed if all the goals have already been + solved. + + .. tacv:: fail @num + + The number is the failure level. If no level is specified, it defaults to 0. + The level is used by :tacn:`try`, :tacn:`repeat`, :tacn:`match goal` and the branching + tacticals. If 0, it makes :tacn:`match goal` considering the next clause + (backtracking). If non zero, the current :tacn:`match goal` block, :tacn:`try`, + :tacn:`repeat`, or branching command is aborted and the level is decremented. In + the case of :n:`+`, a non-zero level skips the first backtrack point, even if + the call to :n:`fail @num` is not enclosed in a :n:`+` command, + respecting the algebraic identity. + + .. tacv:: fail {* message_token} + + The given tokens are used for printing the failure message. + + .. tacv:: fail @num {* message_token} + + This is a combination of the previous variants. + + .. tacv:: gfail + :name: gfail + + This variant fails even if there are no goals left. + + .. tacv:: gfail {* message_token} + + .. tacv:: gfail @num {* message_token} + + These variants fail with an error message or an error level even if + there are no goals left. Be careful however if Coq terms have to be + printed as part of the failure: term construction always forces the + tactic into the goals, meaning that if there are no goals when it is + evaluated, a tactic call like :n:`let x:=H in fail 0 x` will succeed. + + .. exn:: Tactic Failure message (level @num). + +Timeout +~~~~~~~ + +We can force a tactic to stop if it has not finished after a certain +amount of time: + +.. tacn:: timeout @num @expr + :name: timeout + + :n:`@expr` is evaluated to ``v`` which must be a tactic value. The tactic value + ``v`` is applied normally, except that it is interrupted after :n:`@num` seconds + if it is still running. In this case the outcome is a failure. + + .. warning:: + + For the moment, timeout is based on elapsed time in seconds, + which is very machine-dependent: a script that works on a quick machine + may fail on a slow one. The converse is even possible if you combine a + timeout with some other tacticals. This tactical is hence proposed only + for convenience during debug or other development phases, we strongly + advise you to not leave any timeout in final scripts. Note also that + this tactical isn’t available on the native Windows port of Coq. + +Timing a tactic +~~~~~~~~~~~~~~~ + +A tactic execution can be timed: + +.. tacn:: time @string @expr + :name: time + + evaluates :n:`@expr` and displays the time the tactic expression ran, whether it + fails or successes. In case of several successes, the time for each successive + runs is displayed. Time is in seconds and is machine-dependent. The :n:`@string` + argument is optional. When provided, it is used to identify this particular + occurrence of time. + +Timing a tactic that evaluates to a term +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Tactic expressions that produce terms can be timed with the experimental +tactic + +.. tacn:: time_constr expr + :name: time_constr + + which evaluates :n:`@expr ()` and displays the time the tactic expression + evaluated, assuming successful evaluation. Time is in seconds and is + machine-dependent. + + This tactic currently does not support nesting, and will report times + based on the innermost execution. This is due to the fact that it is + implemented using the tactics + + .. tacn:: restart_timer @string + :name: restart_timer + + and + + .. tacn:: finish_timing {? @string} @string + :name: finish_timing + + which (re)set and display an optionally named timer, respectively. The + parenthesized string argument to :n:`finish_timing` is also optional, and + determines the label associated with the timer for printing. + + By copying the definition of :n:`time_constr` from the standard library, + users can achive support for a fixed pattern of nesting by passing + different :n:`@string` parameters to :n:`restart_timer` and :n:`finish_timing` + at each level of nesting. + + .. example:: + + .. coqtop:: all + + Ltac time_constr1 tac := + let eval_early := match goal with _ => restart_timer "(depth 1)" end in + let ret := tac () in + let eval_early := match goal with _ => finish_timing ( "Tactic evaluation" ) "(depth 1)" end in + ret. + + Goal True. + let v := time_constr + ltac:(fun _ => + let x := time_constr1 ltac:(fun _ => constr:(10 * 10)) in + let y := time_constr1 ltac:(fun _ => eval compute in x) in + y) in + pose v. + Abort. + +Local definitions +~~~~~~~~~~~~~~~~~ + +Local definitions can be done as follows: + +.. tacn:: let @ident__1 := @expr__1 {* with @ident__i := @expr__i} in @expr + + each :n:`@expr__i` is evaluated to :n:`v__i`, then, :n:`@expr` is evaluated + by substituting :n:`v__i` to each occurrence of :n:`@ident__i`, for + i=1,...,n. There is no dependencies between the :n:`@expr__i` and the + :n:`@ident__i`. + + Local definitions can be recursive by using :n:`let rec` instead of :n:`let`. + In this latter case, the definitions are evaluated lazily so that the rec + keyword can be used also in non recursive cases so as to avoid the eager + evaluation of local definitions. + + .. but rec changes the binding!! + +Application +~~~~~~~~~~~ + +An application is an expression of the following form: + +.. tacn:: @qualid {+ @tacarg} + + The reference :n:`@qualid` must be bound to some defined tactic definition + expecting at least as many arguments as the provided :n:`tacarg`. The + expressions :n:`@expr__i` are evaluated to :n:`v__i`, for i=1,...,n. + + .. what expressions ?? + +Function construction +~~~~~~~~~~~~~~~~~~~~~ + +A parameterized tactic can be built anonymously (without resorting to +local definitions) with: + +.. tacn:: fun {+ @ident} => @expr + + Indeed, local definitions of functions are a syntactic sugar for binding + a :n:`fun` tactic to an identifier. + +Pattern matching on terms +~~~~~~~~~~~~~~~~~~~~~~~~~ + +We can carry out pattern matching on terms with: + +.. tacn:: match @expr with {+| @cpattern__i => @expr__i} end + + The expression :n:`@expr` is evaluated and should yield a term which is + matched against :n:`cpattern__1`. The matching is non-linear: if a + metavariable occurs more than once, it should match the same expression + every time. It is first-order except on the variables of the form :n:`@?id` + that occur in head position of an application. For these variables, the + matching is second-order and returns a functional term. + + Alternatively, when a metavariable of the form :n:`?id` occurs under binders, + say :n:`x__1, …, x__n` and the expression matches, the + metavariable is instantiated by a term which can then be used in any + context which also binds the variables :n:`x__1, …, x__n` with + same types. This provides with a primitive form of matching under + context which does not require manipulating a functional term. + + If the matching with :n:`@cpattern__1` succeeds, then :n:`@expr__1` is + evaluated into some value by substituting the pattern matching + instantiations to the metavariables. If :n:`@expr__1` evaluates to a + tactic and the match expression is in position to be applied to a goal + (e.g. it is not bound to a variable by a :n:`let in`), then this tactic is + applied. If the tactic succeeds, the list of resulting subgoals is the + result of the match expression. If :n:`@expr__1` does not evaluate to a + tactic or if the match expression is not in position to be applied to a + goal, then the result of the evaluation of :n:`@expr__1` is the result + of the match expression. + + If the matching with :n:`@cpattern__1` fails, or if it succeeds but the + evaluation of :n:`@expr__1` fails, or if the evaluation of + :n:`@expr__1` succeeds but returns a tactic in execution position whose + execution fails, then :n:`cpattern__2` is used and so on. The pattern + :n:`_` matches any term and shunts all remaining patterns if any. If all + clauses fail (in particular, there is no pattern :n:`_`) then a + no-matching-clause error is raised. + + Failures in subsequent tactics do not cause backtracking to select new + branches or inside the right-hand side of the selected branch even if it + has backtracking points. + + .. exn:: No matching clauses for match. + + No pattern can be used and, in particular, there is no :n:`_` pattern. + + .. exn:: Argument of match does not evaluate to a term. + + This happens when :n:`@expr` does not denote a term. + + .. tacv:: multimatch @expr with {+| @cpattern__i => @expr__i} end + + Using multimatch instead of match will allow subsequent tactics to + backtrack into a right-hand side tactic which has backtracking points + left and trigger the selection of a new matching branch when all the + backtracking points of the right-hand side have been consumed. + + The syntax :n:`match …` is, in fact, a shorthand for :n:`once multimatch …`. + + .. tacv:: lazymatch @expr with {+| @cpattern__i => @expr__i} end + + Using lazymatch instead of match will perform the same pattern + matching procedure but will commit to the first matching branch + rather than trying a new matching if the right-hand side fails. If + the right-hand side of the selected branch is a tactic with + backtracking points, then subsequent failures cause this tactic to + backtrack. + + .. tacv:: context @ident [@cpattern] + + This special form of patterns matches any term with a subterm matching + cpattern. If there is a match, the optional :n:`@ident` is assigned the "matched + context", i.e. the initial term where the matched subterm is replaced by a + hole. The example below will show how to use such term contexts. + + If the evaluation of the right-hand-side of a valid match fails, the next + matching subterm is tried. If no further subterm matches, the next clause + is tried. Matching subterms are considered top-bottom and from left to + right (with respect to the raw printing obtained by setting option + :opt:`Printing All`). + + .. example:: + + .. coqtop:: all + + Ltac f x := + match x with + context f [S ?X] => + idtac X; (* To display the evaluation order *) + assert (p := eq_refl 1 : X=1); (* To filter the case X=1 *) + let x:= context f[O] in assert (x=O) (* To observe the context *) + end. + Goal True. + f (3+4). + +.. _ltac-match-goal: + +Pattern matching on goals +~~~~~~~~~~~~~~~~~~~~~~~~~ + +We can make pattern matching on goals using the following expression: + +.. we should provide the full grammar here + +.. tacn:: match goal with {+| {+ hyp} |- @cpattern => @expr } | _ => @expr end + :name: match goal + + If each hypothesis pattern :n:`hyp`\ :sub:`1,i`, with i=1,...,m\ :sub:`1` is + matched (non-linear first-order unification) by an hypothesis of the + goal and if :n:`cpattern_1` is matched by the conclusion of the goal, + then :n:`@expr__1` is evaluated to :n:`v__1` by substituting the + pattern matching to the metavariables and the real hypothesis names + bound to the possible hypothesis names occurring in the hypothesis + patterns. If :n:`v__1` is a tactic value, then it is applied to the + goal. If this application fails, then another combination of hypotheses + is tried with the same proof context pattern. If there is no other + combination of hypotheses then the second proof context pattern is tried + and so on. If the next to last proof context pattern fails then + the last :n:`@expr` is evaluated to :n:`v` and :n:`v` is + applied. Note also that matching against subterms (using the :n:`context + @ident [ @cpattern ]`) is available and is also subject to yielding several + matchings. + + Failures in subsequent tactics do not cause backtracking to select new + branches or combinations of hypotheses, or inside the right-hand side of + the selected branch even if it has backtracking points. + + .. exn:: No matching clauses for match goal. + + No clause succeeds, i.e. all matching patterns, if any, fail at the + application of the right-hand-side. + + .. note:: + + It is important to know that each hypothesis of the goal can be matched + by at most one hypothesis pattern. The order of matching is the + following: hypothesis patterns are examined from the right to the left + (i.e. hyp\ :sub:`i,m`\ :sub:`i`` before hyp\ :sub:`i,1`). For each + hypothesis pattern, the goal hypothesis are matched in order (fresher + hypothesis first), but it possible to reverse this order (older first) + with the :n:`match reverse goal with` variant. + + .. tacv:: multimatch goal with {+| {+ hyp} |- @cpattern => @expr } | _ => @expr end + + Using :n:`multimatch` instead of :n:`match` will allow subsequent tactics + to backtrack into a right-hand side tactic which has backtracking points + left and trigger the selection of a new matching branch or combination of + hypotheses when all the backtracking points of the right-hand side have + been consumed. + + The syntax :n:`match [reverse] goal …` is, in fact, a shorthand for + :n:`once multimatch [reverse] goal …`. + + .. tacv:: lazymatch goal with {+| {+ hyp} |- @cpattern => @expr } | _ => @expr end + + Using lazymatch instead of match will perform the same pattern matching + procedure but will commit to the first matching branch with the first + matching combination of hypotheses rather than trying a new matching if + the right-hand side fails. If the right-hand side of the selected branch + is a tactic with backtracking points, then subsequent failures cause + this tactic to backtrack. + +Filling a term context +~~~~~~~~~~~~~~~~~~~~~~ + +The following expression is not a tactic in the sense that it does not +produce subgoals but generates a term to be used in tactic expressions: + +.. tacn:: context @ident [@expr] + + :n:`@ident` must denote a context variable bound by a context pattern of a + match expression. This expression evaluates replaces the hole of the + value of :n:`@ident` by the value of :n:`@expr`. + + .. exn:: Not a context variable. + +Generating fresh hypothesis names +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Tactics sometimes have to generate new names for hypothesis. Letting the +system decide a name with the intro tactic is not so good since it is +very awkward to retrieve the name the system gave. The following +expression returns an identifier: + +.. tacn:: fresh {* component} + + It evaluates to an identifier unbound in the goal. This fresh identifier + is obtained by concatenating the value of the :n:`@component`s (each of them + is, either a :n:`@qualid` which has to refer to a (unqualified) name, or + directly a name denoted by a :n:`@string`). + + .. I don't understand this component thing. Couldn't we give the grammar? + + If the resulting name is already used, it is padded with a number so that it + becomes fresh. If no component is given, the name is a fresh derivative of + the name ``H``. + +Computing in a constr +~~~~~~~~~~~~~~~~~~~~~ + +Evaluation of a term can be performed with: + +.. tacn:: eval @redexpr in @term + + where :n:`@redexpr` is a reduction tactic among :tacn:`red`, :tacn:`hnf`, + :tacn:`compute`, :tacn:`simpl`, :tacn:`cbv`, :tacn:`lazy`, :tacn:`unfold`, + :tacn:`fold`, :tacn:`pattern`. + +Recovering the type of a term +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +The following returns the type of term: + +.. tacn:: type of @term + +Manipulating untyped terms +~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. tacn:: uconstr : @term + + The terms built in |Ltac| are well-typed by default. It may not be + appropriate for building large terms using a recursive |Ltac| function: the + term has to be entirely type checked at each step, resulting in potentially + very slow behavior. It is possible to build untyped terms using |Ltac| with + the :n:`uconstr : @term` syntax. + +.. tacn:: type_term @term + + An untyped term, in |Ltac|, can contain references to hypotheses or to + |Ltac| variables containing typed or untyped terms. An untyped term can be + type-checked using the function type_term whose argument is parsed as an + untyped term and returns a well-typed term which can be used in tactics. + +Untyped terms built using :n:`uconstr :` can also be used as arguments to the +:tacn:`refine` tactic. In that case the untyped term is type +checked against the conclusion of the goal, and the holes which are not solved +by the typing procedure are turned into new subgoals. + +Counting the goals +~~~~~~~~~~~~~~~~~~ + +.. tacn:: numgoals + + The number of goals under focus can be recovered using the :n:`numgoals` + function. Combined with the guard command below, it can be used to + branch over the number of goals produced by previous tactics. + + .. example:: + + .. coqtop:: in + + Ltac pr_numgoals := let n := numgoals in idtac "There are" n "goals". + + Goal True /\ True /\ True. + split;[|split]. + + .. coqtop:: all + + all:pr_numgoals. + +Testing boolean expressions +~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. tacn:: guard @test + :name: guard + + The :tacn:`guard` tactic tests a boolean expression, and fails if the expression + evaluates to false. If the expression evaluates to true, it succeeds + without affecting the proof. + + The accepted tests are simple integer comparisons. + + .. example:: + + .. coqtop:: in + + Goal True /\ True /\ True. + split;[|split]. + + .. coqtop:: all + + all:let n:= numgoals in guard n<4. + Fail all:let n:= numgoals in guard n=2. + + .. exn:: Condition not satisfied. + +Proving a subgoal as a separate lemma +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. tacn:: abstract @expr + :name: abstract + + From the outside, :n:`abstract @expr` is the same as :n:`solve @expr`. + Internally it saves an auxiliary lemma called ``ident_subproofn`` where + ``ident`` is the name of the current goal and ``n`` is chosen so that this is + a fresh name. Such an auxiliary lemma is inlined in the final proof term. + + This tactical is useful with tactics such as :tacn:`omega` or + :tacn:`discriminate` that generate huge proof terms. With that tool the user + can avoid the explosion at time of the Save command without having to cut + manually the proof in smaller lemmas. + + It may be useful to generate lemmas minimal w.r.t. the assumptions they + depend on. This can be obtained thanks to the option below. + + .. tacv:: abstract @expr using @ident + + Give explicitly the name of the auxiliary lemma. + + .. warning:: + + Use this feature at your own risk; explicitly named and reused subterms + don’t play well with asynchronous proofs. + + .. tacv:: transparent_abstract @expr + :name: transparent_abstract + + Save the subproof in a transparent lemma rather than an opaque one. + + .. warning:: + + Use this feature at your own risk; building computationally relevant + terms with tactics is fragile. + + .. tacv:: transparent_abstract @expr using @ident + + Give explicitly the name of the auxiliary transparent lemma. + + .. warning:: + + Use this feature at your own risk; building computationally relevant terms + with tactics is fragile, and explicitly named and reused subterms + don’t play well with asynchronous proofs. + + .. exn:: Proof is not complete. + :name: Proof is not complete. (abstract) + +Tactic toplevel definitions +--------------------------- + +Defining |Ltac| functions +~~~~~~~~~~~~~~~~~~~~~~~~~ + +Basically, |Ltac| toplevel definitions are made as follows: + +.. cmd:: Ltac @ident {* @ident} := @expr + + This defines a new |Ltac| function that can be used in any tactic + script or new |Ltac| toplevel definition. + + .. note:: + + The preceding definition can equivalently be written: + + :n:`Ltac @ident := fun {+ @ident} => @expr` + + Recursive and mutual recursive function definitions are also possible + with the syntax: + + .. cmdv:: Ltac @ident {* @ident} {* with @ident {* @ident}} := @expr + + It is also possible to *redefine* an existing user-defined tactic using the syntax: + + .. cmdv:: Ltac @qualid {* @ident} ::= @expr + + A previous definition of qualid must exist in the environment. The new + definition will always be used instead of the old one and it goes across + module boundaries. + + If preceded by the keyword Local the tactic definition will not be + exported outside the current module. + +Printing |Ltac| tactics +~~~~~~~~~~~~~~~~~~~~~~~ + +.. cmd:: Print Ltac @qualid + + Defined |Ltac| functions can be displayed using this command. + +.. cmd:: Print Ltac Signatures + + This command displays a list of all user-defined tactics, with their arguments. + +Debugging |Ltac| tactics +------------------------ + +Info trace +~~~~~~~~~~ + +.. cmd:: Info @num @expr + :name: Info + + This command can be used to print the trace of the path eventually taken by an + |Ltac| script. That is, the list of executed tactics, discarding + all the branches which have failed. To that end the :cmd:`Info` command can be + used with the following syntax. + + + The number :n:`@num` is the unfolding level of tactics in the trace. At level + 0, the trace contains a sequence of tactics in the actual script, at level 1, + the trace will be the concatenation of the traces of these tactics, etc… + + .. example:: + + .. coqtop:: in reset + + Ltac t x := exists x; reflexivity. + Goal exists n, n=0. + + .. coqtop:: all + + Info 0 t 1||t 0. + + .. coqtop:: in + + Undo. + + .. coqtop:: all + + Info 1 t 1||t 0. + + The trace produced by :cmd:`Info` tries its best to be a reparsable + |Ltac| script, but this goal is not achievable in all generality. + So some of the output traces will contain oddities. + + As an additional help for debugging, the trace produced by :cmd:`Info` contains + (in comments) the messages produced by the :tacn:`idtac` tactical at the right + position in the script. In particular, the calls to idtac in branches which failed are + not printed. + + .. opt:: Info Level @num + + This option is an alternative to the :cmd:`Info` command. + + This will automatically print the same trace as :n:`Info @num` at each + tactic call. The unfolding level can be overridden by a call to the + :cmd:`Info` command. + +Interactive debugger +~~~~~~~~~~~~~~~~~~~~ + +.. opt:: Ltac Debug + + This option governs the step-by-step debugger that comes with the |Ltac| interpreter + +When the debugger is activated, it stops at every step of the evaluation of +the current |Ltac| expression and it prints information on what it is doing. +The debugger stops, prompting for a command which can be one of the +following: + ++-----------------+-----------------------------------------------+ +| simple newline: | go to the next step | ++-----------------+-----------------------------------------------+ +| h: | get help | ++-----------------+-----------------------------------------------+ +| x: | exit current evaluation | ++-----------------+-----------------------------------------------+ +| s: | continue current evaluation without stopping | ++-----------------+-----------------------------------------------+ +| r n: | advance n steps further | ++-----------------+-----------------------------------------------+ +| r string: | advance up to the next call to “idtac string” | ++-----------------+-----------------------------------------------+ + +A non-interactive mode for the debugger is available via the option: + +.. opt:: Ltac Batch Debug + + This option has the effect of presenting a newline at every prompt, when + the debugger is on. The debug log thus created, which does not require + user input to generate when this option is set, can then be run through + external tools such as diff. + +Profiling |Ltac| tactics +~~~~~~~~~~~~~~~~~~~~~~~~ + +It is possible to measure the time spent in invocations of primitive +tactics as well as tactics defined in |Ltac| and their inner +invocations. The primary use is the development of complex tactics, +which can sometimes be so slow as to impede interactive usage. The +reasons for the performence degradation can be intricate, like a slowly +performing |Ltac| match or a sub-tactic whose performance only +degrades in certain situations. The profiler generates a call tree and +indicates the time spent in a tactic depending its calling context. Thus +it allows to locate the part of a tactic definition that contains the +performance bug. + +.. opt:: Ltac Profiling + + This option enables and disables the profiler. + +.. cmd:: Show Ltac Profile + + Prints the profile + + .. cmdv:: Show Ltac Profile @string + + Prints a profile for all tactics that start with :n:`@string`. Append a period + (.) to the string if you only want exactly that name. + +.. cmd:: Reset Ltac Profile + + Resets the profile, that is, deletes all accumulated information. + + .. warning:: + + Backtracking across a :cmd:`Reset Ltac Profile` will not restore the information. + +.. coqtop:: reset in + + Require Import Coq.omega.Omega. + + Ltac mytauto := tauto. + Ltac tac := intros; repeat split; omega || mytauto. + + Notation max x y := (x + (y - x)) (only parsing). + + Goal forall x y z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z, + max x (max y z) = max (max x y) z /\ max x (max y z) = max (max x y) z + /\ (A /\ B /\ C /\ D /\ E /\ F /\ G /\ H /\ I /\ J /\ K /\ L /\ M /\ N /\ O /\ P /\ Q /\ R /\ S /\ T /\ U /\ V /\ W /\ X /\ Y /\ Z + -> Z /\ Y /\ X /\ W /\ V /\ U /\ T /\ S /\ R /\ Q /\ P /\ O /\ N /\ M /\ L /\ K /\ J /\ I /\ H /\ G /\ F /\ E /\ D /\ C /\ B /\ A). + Proof. + +.. coqtop:: all + + Set Ltac Profiling. + tac. + Show Ltac Profile. + Show Ltac Profile "omega". + +.. coqtop:: in + + Abort. + Unset Ltac Profiling. + +.. tacn:: start ltac profiling + :name: start ltac profiling + + This tactic behaves like :tacn:`idtac` but enables the profiler. + +.. tacn:: stop ltac profiling + :name: stop ltac profiling + + Similarly to :tacn:`start ltac profiling`, this tactic behaves like + :tacn:`idtac`. Together, they allow you to exclude parts of a proof script + from profiling. + +.. tacn:: reset ltac profile + :name: reset ltac profile + + This tactic behaves like the corresponding vernacular command + and allow displaying and resetting the profile from tactic scripts for + benchmarking purposes. + +.. tacn:: show ltac profile + :name: show ltac profile + + This tactic behaves like the corresponding vernacular command + and allow displaying and resetting the profile from tactic scripts for + benchmarking purposes. + +.. tacn:: show ltac profile @string + :name: show ltac profile + + This tactic behaves like the corresponding vernacular command + and allow displaying and resetting the profile from tactic scripts for + benchmarking purposes. + +You can also pass the ``-profile-ltac`` command line option to ``coqc``, which +turns the :opt:`Ltac Profiling` option on at the beginning of each document, +and performs a :cmd:`Show Ltac Profile` at the end. + +.. warning:: + + Note that the profiler currently does not handle backtracking into + multi-success tactics, and issues a warning to this effect in many cases + when such backtracking occurs. + +Run-time optimization tactic +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. tacn:: optimize_heap + :name: optimize_heap + +This tactic behaves like :n:`idtac`, except that running it compacts the +heap in the OCaml run-time system. It is analogous to the Vernacular +command :cmd:`Optimize Heap`. diff --git a/doc/sphinx/proof-engine/proof-handling.rst b/doc/sphinx/proof-engine/proof-handling.rst index 52cde52c69..069cf8a6dc 100644 --- a/doc/sphinx/proof-engine/proof-handling.rst +++ b/doc/sphinx/proof-engine/proof-handling.rst @@ -8,176 +8,188 @@ 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 +section. They can also use some other specialized commands called *tactics*. They are the very tools allowing the user to deal with logical reasoning. They are documented in Chapter :ref:`tactics`. -When switching in editing proof mode, the prompt ``Coq <`` is changed into -``ident <`` where ``ident`` is the declared name of the theorem currently -edited. + +Coq user interfaces usually have a way of marking whether the user has +switched to proof editing mode. For instance, in coqtop the prompt ``Coq <`` is changed into +:n:`@ident <` where :token:`ident` is the declared name of the theorem currently edited. At each stage of a proof development, one has a list of goals to prove. Initially, the list consists only in the theorem itself. After having applied some tactics, the list of goals contains the subgoals generated by the tactics. -To each subgoal is associated a number of hypotheses called the *local -context* of the goal. Initially, the local context contains the local -variables and hypotheses of the current section (see Section :ref:`TODO_gallina_assumptions`) -and the local variables and hypotheses of the theorem statement. It is -enriched by the use of certain tactics (see e.g. ``intro`` in Section -:ref:`managingthelocalcontext`). +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* [[How80]_, -[Bar81]_, [Gir89]_, [Hue88]_ ], |Coq| -stores proofs as terms of |Cic|. Those terms -are called *proof terms*. +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. -.. exn:: No focused proof + Coq raises this error message when one attempts to use a proof editing command + out of the proof editing mode. -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: - -.. cmd:: Theorem @ident [@binders] : @form. - -The list of assertion commands is given in Section :ref:TODO-assertions_and_proof`. The -command ``Goal`` can also be used. - -.. cmd:: Goal @form. - -This is intended for quick assertion of statements, without knowing in -advance which name to give to the assertion, typically for quick -testing of the provability of a statement. If the proof of the -statement is eventually completed and validated, the statement is then -bound to the name ``Unnamed_thm`` (or a variant of this name not already -used for another statement). - -.. cmd:: Qed. - -This command is available in interactive editing proof mode when the -proof is completed. Then ``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 +The proof editing mode is entered by asserting a statement, which typically is +the assertion of a theorem using an assertion command like :cmd:`Theorem`. The +list of assertion commands is given in :ref:`Assertions`. The command +:cmd:`Goal` can also be used. -.. note:: +.. cmd:: Goal @form - Sometimes an error occurs when building the proof term, because - tactics do not enforce completely the term construction - constraints. + 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). -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. +.. cmd:: Qed + :name: Qed (interactive proof) -.. cmdv:: Defined. + This command is available in interactive editing proof mode when the + proof is completed. Then :cmd:`Qed` extracts a proof term from the proof + script, switches back to Coq top-level and attaches the extracted + proof term to the declared name of the original goal. This name is + added to the environment as an opaque constant. -Defines the proved term as a transparent constant. + .. exn:: Attempt to save an incomplete proof. -.. cmdv:: Save @ident. + .. note:: -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. + 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. -.. cmd:: Admitted. + .. cmdv:: Defined + :name: Defined (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. + Defines the proved term as a transparent constant. + .. cmdv:: Save @ident + :name: Save -.. cmd:: Proof @term. + Forces the name of the original goal to be :token:`ident`. This + command (and the following ones) can only be used if the original goal + has been opened using the :cmd:`Goal` command. -This command applies in proof editing mode. It is equivalent to +.. cmd:: Admitted + :name: Admitted (interactive proof) -.. cmd:: exact @term. Qed. + This command is available in interactive editing mode to give up + the current proof and declare the initial goal as an axiom. -That is, you have to give the full proof in one gulp, as a -proof term (see Section :ref:`applyingtheorems`). +.. 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. -.. cmdv:: Proof. + .. exn:: No focused proof (No proof-editing in progress). -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``. + .. cmdv:: Abort @ident + Aborts the editing of the proof named :token:`ident` (in case you have + nested proofs). -See also: ``Proof with tactic.`` in Section -:ref:`setimpautotactics`. + .. cmdv:: Abort All + Aborts all current goals. -.. cmd:: Proof using @ident1 ... @identn. +.. cmd:: Proof @term + :name: Proof `term` -This command applies in proof editing mode. It declares the set of -section variables (see :ref:`TODO-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. + This command applies in proof editing mode. It is equivalent to + :n:`exact @term. Qed.` + That is, you have to give the full proof in one gulp, as a + proof term (see Section :ref:`applyingtheorems`). -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. +.. cmd:: Proof + :name: Proof (interactive proof) + Is a no-op which is useful to delimit the sequence of tactic commands + which start a proof, after a :cmd:`Theorem` command. It is a good practice to + use :cmd:`Proof` as an opening parenthesis, closed in the script with a + closing :cmd:`Qed`. -.. cmdv:: Proof using @ident1 ... @identn with @tactic. + .. seealso:: :cmd:`Proof with` -in Section :ref:`setimpautotactics`. +.. cmd:: Proof using {+ @ident } -.. cmdv:: Proof using All. + This command applies in proof editing mode. It declares the set of + section variables (see :ref:`gallina-assumptions`) used by the proof. + At :cmd:`Qed` time, the + system will assert that the set of section variables actually used in + the proof is a subset of the declared one. -Use all section variables. + The set of declared variables is closed under type dependency. For + example if ``T`` is variable and a is a variable of type ``T``, the commands + ``Proof using a`` and ``Proof using T a`` are actually equivalent. + .. cmdv:: Proof using {+ @ident } with @tactic -.. cmdv:: Proof using Type. + Combines in a single line :cmd:`Proof with` and :cmd:`Proof using`. -.. cmdv:: Proof using. + .. seealso:: :ref:`tactics-implicit-automation` -Use only section variables occurring in the statement. + .. cmdv:: Proof using All + Use all section variables. -.. cmdv:: Proof using Type*. + .. 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. + Use only section variables occurring in the statement. + .. cmdv:: Proof using Type* -.. cmdv:: Proof using -(@ident1 ... @identn). + 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. -Use all section variables except :n:`@ident1` ... :n:`@identn`. + .. cmdv:: Proof using -({+ @ident }) + Use all section variables except the list of :token:`ident`. -.. cmdv:: Proof using @collection1 + @collection2 . + .. cmdv:: Proof using @collection1 + @collection2 + Use section variables from the union of both collections. + See :ref:`nameaset` to know how to form a named collection. -.. cmdv:: Proof using @collection1 - @collection2 . + .. cmdv:: Proof using @collection1 - @collection2 + Use section variables which are in the first collection but not in the + second one. -.. cmdv:: Proof using @collection - ( @ident1 ... @identn ). + .. cmdv:: Proof using @collection - ({+ @ident }) + Use section variables which are in the first collection but not in the + list of :token:`ident`. -.. cmdv:: Proof using @collection * . + .. 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 ``-``. + Use section variables in the forward transitive closure of the collection. + The ``*`` operator binds stronger than ``+`` and ``-``. Proof using options @@ -186,176 +198,151 @@ Proof using options The following options modify the behavior of ``Proof using``. -.. cmdv:: Set Default Proof Using "@expression". +.. 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``. + 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``. -.. cmdv:: Set Suggest Proof Using. +.. opt:: Suggest Proof Using -When ``Qed`` is performed, suggest a using annotation if the user did not -provide one. + When :cmd:`Qed` is performed, suggest a ``using`` annotation if the user did not + provide one. .. _`nameaset`: Name a set of section hypotheses for ``Proof using`` ```````````````````````````````````````````````````` -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". +.. cmd:: Collection @ident := @expression + This can be used to name a set of section + hypotheses, with the purpose of making ``Proof using`` annotations more + compact. -.. cmdv:: Collection Many := Fewer - (x y). + .. example:: -Define the collection named "Many" containing the set difference of -"Fewer" and the unnamed collection ``x`` ``y``. + Define the collection named ``Some`` containing ``x``, ``y`` and ``z``:: + Collection Some := x y z. -.. cmd:: Abort. + Define the collection named ``Fewer`` containing only ``x`` and ``y``:: -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. + Collection Fewer := Some - z + Define the collection named ``Many`` containing the set union or set + difference of ``Fewer`` and ``Some``:: -.. exn:: No focused proof (No proof-editing in progress) + Collection Many := Fewer + Some + Collection Many := Fewer - Some + Define the collection named ``Many`` containing the set difference of + ``Fewer`` and the unnamed collection ``x y``:: + Collection Many := Fewer - (x y) -.. cmdv:: Abort @ident. -Aborts the editing of the proof named :n:`@ident`. -.. cmdv:: Abort All. +.. cmd:: Existential @num := @term -Aborts all current goals, switching back to the |Coq| -toplevel. + This command instantiates an existential variable. :token:`num` is an index in + the list of uninstantiated existential variables displayed by :cmd:`Show Existentials`. + This command is intended to be used to instantiate existential + variables when the proof is completed but some uninstantiated + existential variables remain. To instantiate existential variables + during proof edition, you should use the tactic :tacn:`instantiate`. +.. cmd:: Grab Existential Variables -.. 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 instantiate. - - -See also: ``instantiate (num:= term).`` in Section -:ref:`TODO-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. + 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 -.. cmd:: Undo. - -This command cancels the effect of the last command. Thus, it -backtracks one step. + This command cancels the effect of the last command. Thus, it + backtracks one step. +.. cmdv:: Undo @num -.. cmdv:: Undo @num. + Repeats Undo :token:`num` times. -Repeats Undo :n:`@num` times. +.. cmdv:: Restart + :name: Restart -.. cmdv:: Restart. + This command restores the proof editing process to the original goal. -This command restores the proof editing process to the original goal. + .. exn:: No focused proof to restart. +.. cmd:: Focus -.. exn:: No focused proof to restart + This focuses the attention on the first subgoal to prove and the + printing of the other subgoals is suspended until the focused subgoal + is solved or unfocused. This is useful when there are many current + subgoals which clutter your screen. + .. deprecated:: 8.8 -.. cmd:: Focus. + Prefer the use of bullets or focusing brackets (see below). -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 :token:`num` th subgoal to prove. -.. cmdv:: Focus @num. + .. deprecated:: 8.8 -This focuses the attention on the :n:`@num` th subgoal to -prove. + Prefer the use of focusing brackets with a goal selector (see below). -*This command is deprecated since 8.8*: prefer the use of bullets or -focusing brackets instead, including :n:`@num : %{` +.. cmd:: Unfocus -.. cmd:: Unfocus. + This command restores to focus the goal that were suspended by the + last :cmd:`Focus` command. -This command restores to focus the goal that were suspended by the -last ``Focus`` command. + .. deprecated:: 8.8 -*This command is deprecated since 8.8.* +.. cmd:: Unfocused -.. cmd:: Unfocused. - -Succeeds if the proof is fully unfocused, fails is there are some -goals out of focus. + Succeeds if the proof is fully unfocused, fails if there are some + goals out of focus. +.. _curly-braces: .. cmd:: %{ %| %} -The command ``{`` (without a terminating period) focuses on the first -goal, much like ``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. + The command ``{`` (without a terminating period) focuses on the first + goal, much like :cmd:`Focus` does, however, the subproof can only be + unfocused when it has been fully solved ( *i.e.* when there is no + focused goal left). Unfocusing is then handled by ``}`` (again, without a + terminating period). See also example in next section. -Note that when a focused goal is proved a message is displayed -together with a suggestion about the right bullet or ``}`` to unfocus it -or focus the next one. + 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: %{ + .. cmdv:: @num: %{ -This focuses on the :n:`@num` th subgoal to prove. + This focuses on the :token:`num` th subgoal to prove. -Error messages: + Error messages: -.. exn:: This proof is focused, but cannot be unfocused this way + .. 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. + You are trying to use ``}`` but the current subproof has not been fully solved. -.. exn:: No such goal + .. exn:: No such goal. + :name: No such goal. (Focusing) -.. exn:: Brackets only support the single numbered goal selector + .. exn:: Brackets only support the single numbered goal selector. + See also error messages about bullets below. -See also error messages about bullets below. +.. _bullets: Bullets ``````` @@ -404,152 +391,156 @@ The following example script illustrates all these features: assumption. -.. exn:: Wrong bullet @bullet1 : Current bullet @bullet2 is not finished. +.. 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. + 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. +.. exn:: Wrong bullet @bullet1: Bullet @bullet2 is mandatory here. -You must put :n:`@bullet2` to focus next goal. No other bullet is allowed 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. + You tried to apply a tactic but no goal where under focus. Using :n:`@bullet` is mandatory here. .. exn:: No such goal. Try unfocusing with %{. -You just finished a goal focused by ``{``, you must unfocus it with ``}``. + You just finished a goal focused by ``{``, you must unfocus it with ``}``. Set Bullet Behavior ``````````````````` +.. opt:: Bullet Behavior %( "None" %| "Strict Subproofs" %) -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). + This option controls the bullet behavior and can take two possible values: + - "None": this makes bullets inactive. + - "Strict Subproofs": this makes bullets active (this is the default behavior). +.. _requestinginformation: Requesting information ---------------------- -.. cmd:: Show. +.. cmd:: Show -This command displays the current goals. + This command displays the current goals. + .. exn:: No focused proof. -.. cmdv:: Show @num + .. cmdv:: Show @num -Displays only the :n:`@num`-th subgoal. + Displays only the :token:`num` th subgoal. -.. exn:: No such goal -.. exn:: No focused proof + .. exn:: No such goal. -.. 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:`exvariables`) as in the following example. + .. cmdv:: Show @ident -.. example:: + Displays the named goal :token:`ident`. This is useful in + particular to display a shelved goal but only works if the + corresponding existential variable has been named by the user + (see :ref:`existential-variables`) as in the following example. - .. coqtop:: all + .. example:: - Goal exists n, n = 0. - eexists ?[n]. - Show n. + .. coqtop:: all -.. cmdv:: Show Script. + Goal exists n, n = 0. + eexists ?[n]. + Show n. -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 + .. cmdv:: Show Script + :name: Show Script -``<Your Tactic Text here>``. + 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 -.. cmdv:: Show Proof. + ``<Your Tactic Text here>``. -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 Proof + :name: Show Proof -.. cmdv:: Show Conjectures. + 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. -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 Conjectures + :name: Show Conjectures -.. cmdv:: Show Intro. + 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. -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 Intro + :name: Show Intro -.. cmdv:: Show Intros. + If the current goal begins by at least one product, + this command prints the name of the first product, as it would be + generated by an anonymous :tacn:`intro`. The aim of this command is to ease + the writing of more robust scripts. For example, with an appropriate + Proof General macro, it is possible to transform any anonymous :tacn:`intro` + into a qualified one such as ``intro y13``. In the case of a non-product + goal, it prints nothing. -This command is similar to the previous one, it -simulates the naming process of an intros. + .. cmdv:: Show Intros + :name: Show Intros -.. cmdv:: Show Existentials. + This command is similar to the previous one, it + simulates the naming process of an :tacn:`intros`. -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 Existentials + :name: Show Existentials -.. cmdv:: Show Match @ident. + It displays the set of all uninstantiated + existential variables in the current proof tree, along with the type + and the context of each variable. -This variant displays a template of the Gallina -``match`` construct with a branch for each constructor of the type -:n:`@ident` + .. cmdv:: Show Match @ident -.. example:: - .. coqtop:: all + This variant displays a template of the Gallina + ``match`` construct with a branch for each constructor of the type + :token:`ident` + + .. example:: + .. coqtop:: all - Show Match nat. + Show Match nat. -.. exn:: Unknown inductive type + .. exn:: Unknown inductive type. -.. exn:: Show Universes. + .. cmdv:: Show Universes + :name: Show Universes -It displays the set of all universe constraints and -its normalized form at the current stage of the proof, useful for -debugging universe inconsistencies. + 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. +.. cmd:: Guarded -Some tactics (e.g. 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. + Some tactics (e.g. :tacn:`refine`) allow to build proofs using + fixpoint or co-fixpoint constructions. Due to the incremental nature + of interactive proof construction, the check of the termination (or + guardedness) of the recursive calls in the fixpoint or cofixpoint + constructions is postponed to the time of the completion of the proof. -The command ``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. + The command :cmd:`Guarded` allows checking if the guard condition for + fixpoint and cofixpoint is violated at some time of the construction + of the proof without having to wait the completion of the proof. Controlling the effect of proof editing commands ------------------------------------------------ -.. opt:: Hyps Limit @num. +.. 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 @@ -558,17 +549,16 @@ When unset, it goes back to the default mode which is to print all available hypotheses. -.. opt:: Automatic Introduction. +.. 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 +option is on, 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. +When the option is off, binders are discharged on the statement to be +proved and a tactic such as :tacn:`intro` (see Section :ref:`managingthelocalcontext`) +has to be used to move the assumptions to the local context. Controlling memory usage @@ -578,15 +568,15 @@ 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. +.. cmd:: Optimize Proof This command forces |Coq| to shrink the data structure used to represent the ongoing proof. -.. cmd:: Optimize Heap. +.. 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 ``optimize_heap`` (see~:ref:`tactic-optimizeheap`) +There is also an analogous tactic :tacn:`optimize_heap`. diff --git a/doc/sphinx/proof-engine/ssreflect-proof-language.rst b/doc/sphinx/proof-engine/ssreflect-proof-language.rst index bd71e5ed81..63cd0f3ead 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 @@ -426,7 +423,7 @@ an improvement over ``all null s``. The syntax of the new declaration is -.. cmd:: Prenex Implicits {+ @ident}. +.. cmd:: Prenex Implicits {+ @ident} Let us denote :math:`c_1` … :math:`c_n` the list of identifiers given to a ``Prenex Implicits`` command. The command checks that each ci is the name of @@ -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: @@ -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:: @@ -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 @@ -2135,7 +2140,7 @@ 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 succeed. @@ -2152,10 +2157,10 @@ equivalent to: More generally, the tactic: -.. tacn:: @tactic; last @natural first +.. tacn:: @tactic; last @num first :name: last first -where :token:`natural` is a |Coq| numeral, or and Ltac variable +where :token:`num` is a |Coq| numeral, or an Ltac variable denoting a |Coq| numeral, having the value k. It rotates the n subgoals G1 , …, Gn generated by tactic. The first subgoal becomes Gn + 1 − k and the @@ -2163,7 +2168,7 @@ circular order of subgoals remains unchanged. Conversely, the tactic: -.. tacn:: @tactic; first @natural last +.. tacn:: @tactic; first @num last :name: first last rotates the n subgoals G1 , …, Gn generated by tactic in order that @@ -2215,7 +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*. @@ -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 ``````````````````````````````````` @@ -3730,6 +3732,7 @@ 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. @@ -5188,6 +5191,7 @@ 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 returns the list of lemmas: @@ -5318,11 +5322,11 @@ intro item see :ref:`introduction_ssr` multiplier see :ref:`iteration_ssr` -.. prodn:: occ_switch ::= { {? + %| - } {* @natural } } +.. prodn:: occ_switch ::= { {? + %| - } {* @num } } occur. switch see :ref:`occurrence_selection_ssr` -.. prodn:: mult ::= {? @natural } @mult_mark +.. prodn:: mult ::= {? @num } @mult_mark multiplier see :ref:`iteration_ssr` diff --git a/doc/sphinx/proof-engine/tactics.rst b/doc/sphinx/proof-engine/tactics.rst index 2af73c28e5..0318bddde4 100644 --- a/doc/sphinx/proof-engine/tactics.rst +++ b/doc/sphinx/proof-engine/tactics.rst @@ -24,7 +24,7 @@ Each (sub)goal is denoted with a number. The current goal is numbered 1. By default, a tactic is applied to the current goal, but one can address a particular goal in the list by writing n:tactic which means “apply tactic tactic to goal number n”. We can show the list of -subgoals by typing Show (see Section :ref:`TODO-7.3.1-Show`). +subgoals by typing Show (see Section :ref:`requestinginformation`). Since not every rule applies to a given statement, every tactic cannot be used to reduce any goal. In other words, before applying a tactic @@ -34,15 +34,16 @@ satisfied. If it is not the case, the tactic raises an error message. Tactics are built from atomic tactics and tactic expressions (which extends the folklore notion of tactical) to combine those atomic tactics. This chapter is devoted to atomic tactics. The tactic -language will be described in Chapter :ref:`TODO-9-Thetacticlanguage`. +language will be described in Chapter :ref:`ltac`. + +.. _invocation-of-tactics: Invocation of tactics ------------------------- A tactic is applied as an ordinary command. It may be preceded by a -goal selector (see Section :ref:`TODO-9.2-Semantics`). If no selector is -specified, the default selector (see Section -:ref:`TODO-8.1.1-Setdefaultgoalselector`) is used. +goal selector (see Section :ref:`ltac-semantics`). If no selector is +specified, the default selector is used. .. _tactic_invocation_grammar: @@ -50,20 +51,22 @@ specified, the default selector (see Section tactic_invocation : toplevel_selector : tactic. : |tactic . -.. cmd:: Set Default Goal Selector @toplevel_selector. +.. opt:: Default Goal Selector @toplevel_selector + + This option controls the default selector, used when no selector is + specified when applying a tactic. The initial value is 1, hence the + tactics are, by default, applied to the first goal. -After using this command, the default selector – used when no selector -is specified when applying a tactic – is set to the chosen value. The -initial value is 1, hence the tactics are, by default, applied to the -first goal. Using Set Default Goal Selector ‘‘all’’ will make is so -that tactics are, by default, applied to every goal simultaneously. -Then, to apply a tactic tac to the first goal only, you can write -1:tac. Although more selectors are available, only ‘‘all’’ or a single -natural number are valid default goal selectors. + Using value ``all`` will make it so that tactics are, by default, + applied to every goal simultaneously. Then, to apply a tactic tac + to the first goal only, you can write ``1:tac``. -.. cmd:: Test Default Goal Selector. + Using value ``!`` enforces that all tactics are used either on a + single focused goal or with a local selector (’’strict focusing + mode’’). -This command displays the current default selector. + Although more selectors are available, only ``all``, ``!`` or a + single natural number are valid default goal selectors. .. _bindingslist: @@ -89,14 +92,14 @@ bindings_list`` where ``bindings_list`` may be of two different forms: the ``n``-th non dependent premise of the ``term``, as determined by the type of ``term``. - .. exn:: No such binder + .. exn:: No such binder. + A bindings list can also be a simple list of terms :n:`{* term}`. In that case the references to which these terms correspond are - determined by the tactic. In case of ``induction``, ``destruct``, ``elim`` - and ``case`` (see :ref:`TODO-9-Thetacticlanguage`) the terms have to + determined by the tactic. In case of :tacn:`induction`, :tacn:`destruct`, :tacn:`elim` + and :tacn:`case`, the terms have to provide instances for all the dependent products in the type of term while in - the case of ``apply``, or of ``constructor`` and its variants, only instances + the case of :tacn:`apply`, or of :tacn:`constructor` and its variants, only instances for the dependent products that are not bound in the conclusion of the type are required. @@ -122,14 +125,12 @@ following syntax: The role of an occurrence clause is to select a set of occurrences of a term in a goal. In the first case, the :n:`@ident {? at {* num}}` parts indicate that -occurrences have to be selected in the hypotheses named :n:`@ident`. If no numbers -are given for hypothesis :n:`@ident`, then all the occurrences of `term` in the -hypothesis are selected. If numbers are given, they refer to occurrences of -`term` when the term is printed using option ``Set Printing All`` (see -:ref:`TODO-2.9-Printingconstructionsinfull`), counting from left to right. In -particular, occurrences of `term` in implicit arguments (see -:ref:`TODO-2.7-Implicitarguments`) or coercions (see :ref:`TODO-2.8-Coercions`) -are counted. +occurrences have to be selected in the hypotheses named :n:`@ident`. If no +numbers are given for hypothesis :n:`@ident`, then all the occurrences of `term` +in the hypothesis are selected. If numbers are given, they refer to occurrences +of `term` when the term is printed using option :opt:`Printing All`, counting +from left to right. In particular, occurrences of `term` in implicit arguments +(see :ref:`ImplicitArguments`) or coercions (see :ref:`Coercions`) are counted. If a minus sign is given between at and the list of occurrences, it negates the condition so that the clause denotes all the occurrences @@ -150,14 +151,15 @@ no numbers are given, all occurrences of :n:`@term` in the goal are selected. Finally, the last notation is an abbreviation for ``* |- *``. Note also that ``|-`` is optional in the first case when no ``*`` is given. -Here are some tactics that understand occurrences clauses: ``set``, ``remember`` -, ``induction``, ``destruct``. +Here are some tactics that understand occurrences clauses: :tacn:`set`, :tacn:`remember` +, :tacn:`induction`, :tacn:`destruct`. -See also: :ref:`TODO-8.3.7-Managingthelocalcontext`, -:ref:`TODO-8.5.2-Caseanalysisandinduction`, -:ref:`TODO-2.9-Printingconstructionsinfull`. +See also: :ref:`Managingthelocalcontext`, +:ref:`caseanalysisandinduction`, +:ref:`printing_constructions_full`. +.. _applyingtheorems: Applying theorems --------------------- @@ -165,195 +167,203 @@ Applying theorems .. tacn:: exact @term :name: exact -This tactic applies to any goal. It gives directly the exact proof -term of the goal. Let ``T`` be our goal, let ``p`` be a term of type ``U`` then -``exact p`` succeeds iff ``T`` and ``U`` are convertible (see -:ref:`TODO-4.3-Conversionrules`). + This tactic applies to any goal. It gives directly the exact proof + term of the goal. Let ``T`` be our goal, let ``p`` be a term of type ``U`` then + ``exact p`` succeeds iff ``T`` and ``U`` are convertible (see + :ref:`Conversion-rules`). -.. exn:: Not an exact proof. + .. exn:: Not an exact proof. -.. tacv:: eexact @term. + .. tacv:: eexact @term. + :name: eexact -This tactic behaves like exact but is able to handle terms and goals with -meta-variables. + This tactic behaves like exact but is able to handle terms and goals with + meta-variables. .. tacn:: assumption :name: assumption -This tactic looks in the local context for an hypothesis which type is equal to -the goal. If it is the case, the subgoal is proved. Otherwise, it fails. + This tactic looks in the local context for an hypothesis which type is equal to + the goal. If it is the case, the subgoal is proved. Otherwise, it fails. -.. exn:: No such assumption. + .. exn:: No such assumption. -.. tacv:: eassumption + .. tacv:: eassumption + :name: eassumption -This tactic behaves like assumption but is able to handle goals with -meta-variables. + This tactic behaves like assumption but is able to handle goals with + meta-variables. .. tacn:: refine @term :name: refine -This tactic applies to any goal. It behaves like exact with a big -difference: the user can leave some holes (denoted by ``_`` or``(_:type)``) in -the term. refine will generate as many subgoals as there are holes in -the term. The type of holes must be either synthesized by the system -or declared by an explicit cast like ``(_:nat->Prop)``. Any subgoal that -occurs in other subgoals is automatically shelved, as if calling -shelve_unifiable (see Section 8.17.4). This low-level tactic can be -useful to advanced users. + This tactic applies to any goal. It behaves like :tacn:`exact` with a big + difference: the user can leave some holes (denoted by ``_`` or ``(_:type)``) in + the term. :tacn:`refine` will generate as many subgoals as there are holes in + the term. The type of holes must be either synthesized by the system + or declared by an explicit cast like ``(_:nat->Prop)``. Any subgoal that + occurs in other subgoals is automatically shelved, as if calling + :tacn:`shelve_unifiable`. This low-level tactic can be + useful to advanced users. -.. example:: - .. coqtop:: reset all + .. example:: + .. coqtop:: reset all - Inductive Option : Set := - | Fail : Option - | Ok : bool -> Option. + Inductive Option : Set := + | Fail : Option + | Ok : bool -> Option. - Definition get : forall x:Option, x <> Fail -> bool. + Definition get : forall x:Option, x <> Fail -> bool. - refine - (fun x:Option => - match x return x <> Fail -> bool with - | Fail => _ - | Ok b => fun _ => b - end). + refine + (fun x:Option => + match x return x <> Fail -> bool with + | Fail => _ + | Ok b => fun _ => b + end). - intros; absurd (Fail = Fail); trivial. + intros; absurd (Fail = Fail); trivial. - Defined. + Defined. -.. exn:: invalid argument + .. exn:: Invalid argument. - The tactic ``refine`` does not know what to do with the term you gave. + The tactic :tacn:`refine` does not know what to do with the term you gave. -.. exn:: Refine passed ill-formed term + .. exn:: Refine passed ill-formed term. - The term you gave is not a valid proof (not easy to debug in general). This - message may also occur in higher-level tactics that call ``refine`` - internally. + The term you gave is not a valid proof (not easy to debug in general). This + message may also occur in higher-level tactics that call :tacn:`refine` + internally. -.. exn:: Cannot infer a term for this placeholder + .. exn:: Cannot infer a term for this placeholder. + :name: Cannot infer a term for this placeholder. (refine) - There is a hole in the term you gave which type cannot be inferred. Put a - cast around it. + There is a hole in the term you gave whose type cannot be inferred. Put a + cast around it. -.. tacv:: simple refine @term + .. tacv:: simple refine @term + :name: simple refine - This tactic behaves like refine, but it does not shelve any subgoal. It does - not perform any beta-reduction either. + This tactic behaves like refine, but it does not shelve any subgoal. It does + not perform any beta-reduction either. -.. tacv:: notypeclasses refine @term + .. tacv:: notypeclasses refine @term + :name: notypeclasses refine - This tactic behaves like ``refine`` except it performs typechecking without - resolution of typeclasses. + This tactic behaves like :tacn:`refine` except it performs typechecking without + resolution of typeclasses. -.. tacv:: simple notypeclasses refine @term + .. tacv:: simple notypeclasses refine @term + :name: simple notypeclasses refine - This tactic behaves like ``simple refine`` except it performs typechecking - without resolution of typeclasses. + This tactic behaves like :tacn:`simple refine` except it performs typechecking + without resolution of typeclasses. -.. tacv:: apply @term +.. tacn:: apply @term :name: apply -This tactic applies to any goal. The argument term is a term well-formed in the -local context. The tactic apply tries to match the current goal against the -conclusion of the type of term. If it succeeds, then the tactic returns as many -subgoals as the number of non-dependent premises of the type of term. If the -conclusion of the type of term does not match the goal *and* the conclusion is -an inductive type isomorphic to a tuple type, then each component of the tuple -is recursively matched to the goal in the left-to-right order. + This tactic applies to any goal. The argument term is a term well-formed in the + local context. The tactic apply tries to match the current goal against the + conclusion of the type of term. If it succeeds, then the tactic returns as many + subgoals as the number of non-dependent premises of the type of term. If the + conclusion of the type of term does not match the goal *and* the conclusion is + an inductive type isomorphic to a tuple type, then each component of the tuple + is recursively matched to the goal in the left-to-right order. -The tactic ``apply`` relies on first-order unification with dependent types -unless the conclusion of the type of ``term`` is of the form :g:`P (t`:sub:`1` -:g:`...` :g:`t`:sub:`n` :g:`)` with `P` to be instantiated. In the latter case, the behavior -depends on the form of the goal. If the goal is of the form -:g:`(fun x => Q) u`:sub:`1` :g:`...` :g:`u`:sub:`n` and the :g:`t`:sub:`i` and -:g:`u`:sub:`i` unifies, then :g:`P` is taken to be :g:`(fun x => Q)`. Otherwise, -``apply`` tries to define :g:`P` by abstracting over :g:`t`:sub:`1` :g:`...` -:g:`t`:sub:`n` in the goal. See :tacn:`pattern` to transform the goal so that it -gets the form :g:`(fun x => Q) u`:sub:`1` :g:`...` :g:`u`:sub:`n`. + The tactic :tacn:`apply` relies on first-order unification with dependent types + unless the conclusion of the type of :token:`term` is of the form :g:`P (t`:sub:`1` + :g:`...` :g:`t`:sub:`n` :g:`)` with `P` to be instantiated. In the latter case, the behavior + depends on the form of the goal. If the goal is of the form + :g:`(fun x => Q) u`:sub:`1` :g:`...` :g:`u`:sub:`n` and the :g:`t`:sub:`i` and + :g:`u`:sub:`i` unifies, then :g:`P` is taken to be :g:`(fun x => Q)`. Otherwise, + :tacn:`apply` tries to define :g:`P` by abstracting over :g:`t`:sub:`1` :g:`...` + :g:`t`:sub:`n` in the goal. See :tacn:`pattern` to transform the goal so that it + gets the form :g:`(fun x => Q) u`:sub:`1` :g:`...` :g:`u`:sub:`n`. -.. exn:: Unable to unify ... with ... . + .. exn:: Unable to unify ... with ... . -The apply tactic failed to match the conclusion of term and the current goal. -You can help the apply tactic by transforming your goal with the -:ref:`change <change_term>` or :tacn:`pattern` tactics. + The apply tactic failed to match the conclusion of :token:`term` and the + current goal. You can help the apply tactic by transforming your goal with + the :tacn:`change` or :tacn:`pattern` tactics. -.. exn:: Unable to find an instance for the variables {+ @ident}. + .. exn:: Unable to find an instance for the variables {+ @ident}. -This occurs when some instantiations of the premises of term are not deducible -from the unification. This is the case, for instance, when you want to apply a -transitivity property. In this case, you have to use one of the variants below: + This occurs when some instantiations of the premises of :token:`term` are not deducible + from the unification. This is the case, for instance, when you want to apply a + transitivity property. In this case, you have to use one of the variants below: -.. cmd:: apply @term with {+ @term} + .. tacv:: apply @term with {+ @term} -Provides apply with explicit instantiations for all dependent premises of the -type of term that do not occur in the conclusion and consequently cannot be -found by unification. Notice that the collection :n:`{+ @term}` must be given -according to the order of these dependent premises of the type of term. + Provides apply with explicit instantiations for all dependent premises of the + type of term that do not occur in the conclusion and consequently cannot be + found by unification. Notice that the collection :n:`{+ @term}` must be given + according to the order of these dependent premises of the type of term. -.. exn:: Not the right number of missing arguments. + .. exn:: Not the right number of missing arguments. -.. tacv:: apply @term with @bindings_list + .. tacv:: apply @term with @bindings_list -This also provides apply with values for instantiating premises. Here, variables -are referred by names and non-dependent products by increasing numbers (see -:ref:`bindings list <bindingslist>`). + This also provides apply with values for instantiating premises. Here, variables + are referred by names and non-dependent products by increasing numbers (see + :ref:`bindings list <bindingslist>`). -.. tacv:: apply {+, @term} + .. tacv:: apply {+, @term} -This is a shortcut for ``apply term``:sub:`1` -``; [.. | ... ; [ .. | apply`` ``term``:sub:`n` ``] ... ]``, -i.e. for the successive applications of ``term``:sub:`i+1` on the last subgoal -generated by ``apply term``:sub:`i` , starting from the application of -``term``:sub:`1`. + This is a shortcut for :n:`apply @term`:sub:`1` + :n:`; [.. | ... ; [ .. | apply @term`:sub:`n` :n:`] ... ]`, + i.e. for the successive applications of :token:`term`:sub:`i+1` on the last subgoal + generated by :n:`apply @term`:sub:`i` , starting from the application of + :token:`term`:sub:`1`. -.. tacv:: eapply @term - :name: eapply + .. tacv:: eapply @term + :name: eapply -The tactic ``eapply`` behaves like ``apply`` but it does not fail when no -instantiations are deducible for some variables in the premises. Rather, it -turns these variables into existential variables which are variables still to -instantiate (see :ref:`TODO-2.11-ExistentialVariables`). The instantiation is -intended to be found later in the proof. + The tactic :tacn:`eapply` behaves like :tacn:`apply` but it does not fail when no + instantiations are deducible for some variables in the premises. Rather, it + turns these variables into existential variables which are variables still to + instantiate (see :ref:`Existential-Variables`). The instantiation is + intended to be found later in the proof. -.. tacv:: simple apply @term. + .. tacv:: simple apply @term. + :name: simple apply -This behaves like ``apply`` but it reasons modulo conversion only on subterms -that contain no variables to instantiate. For instance, the following example -does not succeed because it would require the conversion of ``id ?foo`` and -``O``. + This behaves like :tacn:`apply` but it reasons modulo conversion only on subterms + that contain no variables to instantiate. For instance, the following example + does not succeed because it would require the conversion of ``id ?foo`` and + :g:`O`. -.. example:: + .. example:: - .. coqtop:: all + .. coqtop:: all - Definition id (x : nat) := x. - Hypothesis H : forall y, id y = y. - Goal O = O. - Fail simple apply H. + Definition id (x : nat) := x. + Parameter H : forall y, id y = y. + Goal O = O. + Fail simple apply H. -Because it reasons modulo a limited amount of conversion, ``simple apply`` fails -quicker than ``apply`` and it is then well-suited for uses in user-defined -tactics that backtrack often. Moreover, it does not traverse tuples as ``apply`` -does. + Because it reasons modulo a limited amount of conversion, :tacn:`simple apply` fails + quicker than :tacn:`apply` and it is then well-suited for uses in user-defined + tactics that backtrack often. Moreover, it does not traverse tuples as :tacn:`apply` + does. -.. tacv:: {? simple} apply {+, @term {? with @bindings_list}} -.. tacv:: {? simple} eapply {+, @term {? with @bindings_list}} + .. tacv:: {? simple} apply {+, @term {? with @bindings_list}} + .. tacv:: {? simple} eapply {+, @term {? with @bindings_list}} + :name: simple eapply -This summarizes the different syntaxes for ``apply`` and ``eapply``. + This summarizes the different syntaxes for :tacn:`apply` and :tacn:`eapply`. -.. tacv:: lapply @term - :name: `lapply + .. tacv:: lapply @term + :name: lapply -This tactic applies to any goal, say :g:`G`. The argument term has to be -well-formed in the current context, its type being reducible to a non-dependent -product :g:`A -> B` with :g:`B` possibly containing products. Then it generates -two subgoals :g:`B->G` and :g:`A`. Applying ``lapply H`` (where :g:`H` has type -:g:`A->B` and :g:`B` does not start with a product) does the same as giving the -sequence ``cut B. 2:apply H.`` where ``cut`` is described below. + This tactic applies to any goal, say :g:`G`. The argument term has to be + well-formed in the current context, its type being reducible to a non-dependent + product :g:`A -> B` with :g:`B` possibly containing products. Then it generates + two subgoals :g:`B->G` and :g:`A`. Applying ``lapply H`` (where :g:`H` has type + :g:`A->B` and :g:`B` does not start with a product) does the same as giving the + sequence ``cut B. 2:apply H.`` where ``cut`` is described below. -.. warn:: When @term contains more than one non dependent product the tactic lapply only takes into account the first product. + .. warn:: When @term contains more than one non dependent product the tactic lapply only takes into account the first product. .. example:: Assume we have a transitive relation ``R`` on ``nat``: @@ -435,7 +445,7 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. ``forall A, ... -> A``. Excluding this kind of lemma can be avoided by setting the following option: -.. opt:: Set Universal Lemma Under Conjunction. +.. opt:: Universal Lemma Under Conjunction This option, which preserves compatibility with versions of Coq prior to 8.4 is also available for :n:`apply @term in @ident` (see :tacn:`apply ... in`). @@ -493,7 +503,7 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. .. tacv:: eapply {+, @term with @bindings_list} in @ident as @intro_pattern. - This works as :tacn:`apply ... in as` but using ``eapply``. + This works as :tacn:`apply ... in ... as` but using ``eapply``. .. tacv:: simple apply @term in @ident @@ -501,15 +511,15 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. on subterms that contain no variables to instantiate. For instance, if :g:`id := fun x:nat => x` and :g:`H: forall y, id y = y -> True` and :g:`H0 : O = O` then ``simple apply H in H0`` does not succeed because it - would require the conversion of :g:`id ?1234` and :g:`O` where :g:`?1234` is - a variable to instantiate. Tactic :n:`simple apply @term in @ident` does not + would require the conversion of :g:`id ?x` and :g:`O` where :g:`?x` is + an existential variable to instantiate. Tactic :n:`simple apply @term in @ident` does not either traverse tuples as :n:`apply @term in @ident` does. .. tacv:: {? simple} apply {+, @term {? with @bindings_list}} in @ident {? as @intro_pattern} .. tacv:: {? simple} eapply {+, @term {? with @bindings_list}} in @ident {? as @intro_pattern} - This summarizes the different syntactic variants of :n:`apply @term in - @ident` and :n:`eapply @term in @ident`. + This summarizes the different syntactic variants of :n:`apply @term in @ident` + and :n:`eapply @term in @ident`. .. tacn:: constructor @num :name: constructor @@ -539,14 +549,16 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. The terms in the @bindings_list are checked in the context where constructor is executed and not in the context where @apply is executed (the introductions are not taken into account). .. tacv:: split + :name: split This applies only if :g:`I` has a single constructor. It is then equivalent to :n:`constructor 1.`. It is typically used in the case of a conjunction :g:`A` :math:`\wedge` :g:`B`. -.. exn:: Not an inductive goal with 1 constructor. +.. exn:: Not an inductive goal with 1 constructor .. tacv:: exists @val + :name: exists This applies only if :g:`I` has a single constructor. It is then equivalent to :n:`intros; constructor 1 with @bindings_list.` It is typically used in @@ -559,7 +571,10 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. This iteratively applies :n:`exists @bindings_list`. .. tacv:: left + :name: left + .. tacv:: right + :name: right These tactics apply only if :g:`I` has two constructors, for instance in the case of a disjunction :g:`A` :math:`\vee` :g:`B`. @@ -577,15 +592,25 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. for the appropriate ``i``. .. tacv:: econstructor + :name: econstructor + .. tacv:: eexists + :name: eexists + .. tacv:: esplit + :name: esplit + .. tacv:: eleft + :name: eleft + .. tacv:: eright + :name: eright - These tactics and their variants behave like ``constructor``, ``exists``, - ``split``, ``left``, ``right`` and their variants but they introduce - existential variables instead of failing when the instantiation of a - variable cannot be found (cf. :tacn:`eapply` and :tacn:`apply`). + These tactics and their variants behave like :tacn:`constructor`, + :tacn:`exists`, :tacn:`split`, :tacn:`left`, :tacn:`right` and their variants + but they introduce existential variables instead of failing when the + instantiation of a variable cannot be found (cf. :tacn:`eapply` and + :tacn:`apply`). .. _managingthelocalcontext: @@ -598,27 +623,32 @@ Managing the local context This tactic applies to a goal that is either a product or starts with a let binder. If the goal is a product, the tactic implements the "Lam" rule given in -:ref:`TODO-4.2-Typing-rules` [1]_. If the goal starts with a let binder, then the +:ref:`Typing-rules` [1]_. If the goal starts with a let binder, then the tactic implements a mix of the "Let" and "Conv". -If the current goal is a dependent product :math:`\forall` :g:`x:T, U` (resp +If the current goal is a dependent product :g:`forall x:T, U` (resp :g:`let x:=t in U`) then ``intro`` puts :g:`x:T` (resp :g:`x:=t`) in the local context. The new subgoal is :g:`U`. If the goal is a non-dependent product :g:`T`:math:`\rightarrow`:g:`U`, then it puts in the local context either :g:`Hn:T` (if :g:`T` is of type :g:`Set` or -:g:`Prop`) or Xn:T (if the type of :g:`T` is :g:`Type`). The optional index +:g:`Prop`) or :g:`Xn:T` (if the type of :g:`T` is :g:`Type`). The optional index ``n`` is such that ``Hn`` or ``Xn`` is a fresh identifier. In both cases, the new subgoal is :g:`U`. -If the goal is neither a product nor starting with a let definition, +If the goal is an existential variable, ``intro`` forces the resolution of the +existential variable into a dependent product :math:`forall`:g:`x:?X, ?Y`, puts +:g:`x:?X` in the local context and leaves :g:`?Y` as a new subgoal allowed to +depend on :g:`x`. + the tactic ``intro`` applies the tactic ``hnf`` until the tactic ``intro`` can be applied or the goal is not head-reducible. .. exn:: No product even after head-reduction. -.. exn:: ident is already used. +.. exn:: @ident is already used. .. tacv:: intros + :name: intros This repeats ``intro`` until it meets the head-constant. It never reduces head-constants and it never fails. @@ -628,18 +658,18 @@ be applied or the goal is not head-reducible. This applies ``intro`` but forces :n:`@ident` to be the name of the introduced hypothesis. -.. exn:: name @ident is already used +.. exn:: Name @ident is already used. .. note:: If a name used by intro hides the base name of a global constant then the latter can still be referred to by a qualified name - (see :ref:`TODO-2.6.2-Qualified-names`). + (see :ref:`Qualified-names`). .. tacv:: intros {+ @ident}. This is equivalent to the composed tactic :n:`intro @ident; ... ; intro @ident`. More generally, the ``intros`` tactic takes a pattern as argument in order to introduce names for components of an inductive definition or to clear introduced hypotheses. This is - explained in :ref:`TODO-8.3.2`. + explained in :ref:`Managingthelocalcontext`. .. tacv:: intros until @ident @@ -647,7 +677,7 @@ be applied or the goal is not head-reducible. `(@ident:term)` and discharges the variable named `ident` of the current goal. -.. exn:: No such hypothesis in current goal +.. exn:: No such hypothesis in current goal. .. tacv:: intros until @num @@ -676,7 +706,7 @@ be applied or the goal is not head-reducible. too so as to respect the order of dependencies between hypotheses. Note that :n:`intro at bottom` is a synonym for :n:`intro` with no argument. -.. exn:: No such hypothesis : @ident. +.. exn:: No such hypothesis: @ident. .. tacv:: intro @ident after @ident .. tacv:: intro @ident before @ident @@ -685,7 +715,7 @@ be applied or the goal is not head-reducible. These tactics behave as previously but naming the introduced hypothesis :n:`@ident`. It is equivalent to :n:`intro @ident` followed by the - appropriate call to move (see :tacn:`move ... after`). + appropriate call to ``move`` (see :tacn:`move ... after ...`). .. tacn:: intros @intro_pattern_list :name: intros ... @@ -730,7 +760,7 @@ be applied or the goal is not head-reducible. Assuming a goal of type :g:`Q → P` (non-dependent product), or of type - :math:`\forall`:g:`x:T, P` (dependent product), the behavior of + :g:`forall x:T, P` (dependent product), the behavior of :n:`intros p` is defined inductively over the structure of the introduction pattern :n:`p`: @@ -827,15 +857,10 @@ quantification or an implication. so that all the arguments of the i-th constructors of the corresponding inductive type are introduced can be controlled with the following option: - .. cmd:: Set Bracketing Last Introduction Pattern. - - Force completion, if needed, when the last introduction pattern is a - disjunctive or conjunctive pattern (this is the default). - - .. cmd:: Unset Bracketing Last Introduction Pattern. + .. opt:: 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,11 +880,12 @@ 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. -.. exn:: @ident is not a local definition +.. exn:: @ident is not a local definition. .. tacv:: clear - {+ @ident} @@ -876,7 +902,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 @@ -892,7 +918,7 @@ the inverse of :tacn:`intro`. depend on it. .. tacn:: move @ident after @ident - :name: move .. after ... + :name: move ... after ... This moves the hypothesis named :n:`@ident` in the local context after the hypothesis named :n:`@ident`, where “after” is in reference to the @@ -926,9 +952,9 @@ the inverse of :tacn:`intro`. This moves ident at the bottom of the local context (at the end of the context). -.. exn:: No such hypothesis -.. exn:: Cannot move @ident after @ident : it occurs in the type of @ident -.. exn:: Cannot move @ident after @ident : it depends on @ident +.. exn:: No such hypothesis. +.. exn:: Cannot move @ident after @ident : it occurs in the type of @ident. +.. exn:: Cannot move @ident after @ident : it depends on @ident. .. example:: .. coqtop:: all @@ -955,8 +981,8 @@ The name of the hypothesis in the proof-term, however, is left unchanged. particular, the target identifiers may contain identifiers that exist in the source context, as long as the latter are also renamed by the same tactic. -.. exn:: No such hypothesis -.. exn:: @ident is already used +.. exn:: No such hypothesis. +.. exn:: @ident is already used. .. tacn:: set (@ident := @term) :name: set @@ -968,7 +994,7 @@ The name of the hypothesis in the proof-term, however, is left unchanged. first checks that all subterms matching the pattern are compatible before doing the replacement using the leftmost subterm matching the pattern. -.. exn:: The variable @ident is already defined +.. exn:: The variable @ident is already defined. .. tacv:: set (@ident := @term ) in @goal_occurrences @@ -992,6 +1018,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 +1026,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 +1044,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 +1097,7 @@ The name of the hypothesis in the proof-term, however, is left unchanged. This decomposes record types (inductive types with one constructor, like "and" and "exists" and those defined with the Record macro, see - :ref:`TODO-2.1`). + :ref:`record-types`). .. _controllingtheproofflow: @@ -1082,14 +1112,14 @@ Controlling the proof flow :g:`U` [2]_. The subgoal :g:`U` comes first in the list of subgoals remaining to prove. -.. exn:: Not a proposition or a type +.. exn:: Not a proposition or a type. Arises when the argument form is neither of type :g:`Prop`, :g:`Set` nor :g:`Type`. .. tacv:: assert form - This behaves as :n:`assert (@ident : form ) but :n:`@ident` is generated by + This behaves as :n:`assert (@ident : form)` but :n:`@ident` is generated by Coq. .. tacv:: assert form by tactic @@ -1097,7 +1127,8 @@ Controlling the proof flow This tactic behaves like :n:`assert` but applies tactic to solve the subgoals generated by assert. - .. exn:: Proof is not complete + .. exn:: Proof is not complete. + :name: Proof is not complete. (assert) .. tacv:: assert form as intro_pattern @@ -1118,9 +1149,10 @@ Controlling the proof flow the type of :g:`term`. This is deprecated in favor of :n:`pose proof`. If the head of term is :n:`@ident`, the tactic behaves as :n:`specialize @term`. - .. exn:: Variable @ident is already declared + .. exn:: Variable @ident is already declared. .. tacv:: eassert form as intro_pattern by tactic + :name: eassert .. tacv:: assert (@ident := @term) @@ -1130,6 +1162,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 +1176,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 +1202,27 @@ Controlling the proof flow applied to all of them. .. tacv:: eenough (@ident : form) by tactic + :name: eenough + .. tacv:: eenough form by tactic + .. tacv:: eenough form as intro_pattern by tactic While the different variants of :n:`enough` expect that no existential variables are generated by the tactic, :n:`eenough` removes this constraint. -.. tacv:: cut form +.. tacv:: cut @form + :name: cut This tactic applies to any goal. It implements the non-dependent case of - the “App” rule given in :ref:`TODO-4.2`. (This is Modus Ponens inference + the “App” rule given in :ref:`typing-rules`. (This is Modus Ponens inference rule.) :n:`cut U` transforms the current goal :g:`T` into the two following subgoals: :g:`U -> T` and :g:`U`. The subgoal :g:`U -> T` comes first in the list of remaining subgoal to prove. .. tacv:: specialize (ident {* @term}) {? as intro_pattern} .. tacv:: specialize ident with @bindings_list {? as intro_pattern} + :name: specialize The tactic :n:`specialize` works on local hypothesis :n:`@ident`. The premises of this hypothesis (either universal quantifications or @@ -1202,8 +1241,8 @@ Controlling the proof flow the goal. The :n:`as` clause is especially useful in this case to immediately introduce the instantiated statement as a local hypothesis. - .. exn:: @ident is used in hypothesis @ident - .. exn:: @ident is used in conclusion + .. exn:: @ident is used in hypothesis @ident. + .. exn:: @ident is used in conclusion. .. tacn:: generalize @term :name: generalize @@ -1236,7 +1275,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 +1307,7 @@ name of the variable (here :g:`n`) is chosen based on :g:`T`. :n:`refine @term` (preferred alternative). .. note:: To be able to refer to an existential variable by name, the user - must have given the name explicitly (see :ref:`TODO-2.11`). + must have given the name explicitly (see :ref:`Existential-Variables`). .. note:: When you are referring to hypotheses which you did not name explicitly, be aware that Coq may make a different decision on how to @@ -1327,7 +1366,7 @@ goals cannot be closed with :g:`Qed` but only with :g:`Admitted`. a singleton inductive type (e.g. :g:`True` or :g:`x=x`), or two contradictory hypotheses. -.. exn:: No such assumption +.. exn:: No such assumption. .. tacv:: contradiction @ident @@ -1353,11 +1392,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 +1464,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 +1491,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 +1501,15 @@ analysis on inductive or co-inductive objects (see :ref:`TODO-4.5`). Analogous to :n:`elim @term with @bindings_list` above. -.. tacv:: ecase @term -.. tacv:: ecase @term with @bindings_list +.. tacv:: ecase @term {? with @bindings_list } + :name: ecase In case the type of :n:`@term` has dependent premises, or dependent premises whose values are not inferable from the :n:`with @bindings_list` clause, :n:`ecase` turns them into existential variables to be resolved later on. .. tacv:: simple destruct @ident + :name: simple destruct This tactic behaves as :n:`intros until @ident; case @ident` when :n:`@ident` is a quantified variable of the goal. @@ -1528,9 +1572,9 @@ analysis on inductive or co-inductive objects (see :ref:`TODO-4.5`). intros n H. induction n. -.. exn:: Not an inductive product +.. exn:: Not an inductive product. -.. exn:: Unable to find an instance for the variables @ident ... @ident +.. exn:: Unable to find an instance for the variables @ident ... @ident. Use in this case the variant :tacn:`elim ... with` below. @@ -1556,6 +1600,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 +1673,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. @@ -1646,7 +1692,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 +1703,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 +1788,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 +1803,8 @@ and an explanation of the underlying technique. The tactic functional induction performs case analysis and induction following the definition of a function. It makes use of a principle - generated by ``Function`` (see :ref:`TODO-2.3-Advancedrecursivefunctions`) or - ``Functional Scheme`` (see :ref:`TODO-13.2-Generationofinductionschemeswithfunctionalscheme`). + generated by ``Function`` (see :ref:`advanced-recursive-functions`) or + ``Functional Scheme`` (see :ref:`functional-scheme`). Note that this tactic is only available after a .. example:: @@ -1781,26 +1830,26 @@ and an explanation of the underlying technique. :n:`functional induction (f x1 x2 x3)` is actually a wrapper for :n:`induction x1, x2, x3, (f x1 x2 x3) using @qualid` followed by a cleaning phase, where :n:`@qualid` is the induction principle registered for :g:`f` - (by the ``Function`` (see :ref:`TODO-2.3-Advancedrecursivefunctions`) or - ``Functional Scheme`` (see :ref:`TODO-13.2-Generationofinductionschemeswithfunctionalscheme`) + (by the ``Function`` (see :ref:`advanced-recursive-functions`) or + ``Functional Scheme`` (see :ref:`functional-scheme`) command) corresponding to the sort of the goal. Therefore ``functional induction`` may fail if the induction scheme :n:`@qualid` is not - defined. See also :ref:`TODO-2.3-Advancedrecursivefunctions` for the function + defined. See also :ref:`advanced-recursive-functions` for the function terms accepted by ``Function``. .. note:: There is a difference between obtaining an induction scheme - for a function by using :g:`Function` (see :ref:`TODO-2.3-Advancedrecursivefunctions`) + for a function by using :g:`Function` (see :ref:`advanced-recursive-functions`) and by using :g:`Functional Scheme` after a normal definition using - :g:`Fixpoint` or :g:`Definition`. See :ref:`TODO-2.3-Advancedrecursivefunctions` + :g:`Fixpoint` or :g:`Definition`. See :ref:`advanced-recursive-functions` for details. -See also: :ref:`TODO-2.3-Advancedrecursivefunctions` - :ref:`TODO-13.2-Generationofinductionschemeswithfunctionalscheme` +See also: :ref:`advanced-recursive-functions` + :ref:`functional-scheme` :tacn:`inversion` -.. exn:: Cannot find induction information on @qualid -.. exn:: Not the right number of induction arguments +.. exn:: Cannot find induction information on @qualid. +.. exn:: Not the right number of induction arguments. .. tacv:: functional induction (@qualid {+ @term}) as @disj_conj_intro_pattern using @term with @bindings_list @@ -1833,8 +1882,8 @@ See also: :ref:`TODO-2.3-Advancedrecursivefunctions` :n:`@ident` is first introduced in the local context using :n:`intros until @ident`. -.. exn:: No primitive equality found -.. exn:: Not a discriminable equality +.. exn:: No primitive equality found. +.. exn:: Not a discriminable equality. .. tacv:: discriminate @num @@ -1849,6 +1898,7 @@ See also: :ref:`TODO-2.3-Advancedrecursivefunctions` .. tacv:: ediscriminate @num .. tacv:: ediscriminate @term {? with @bindings_list} + :name: ediscriminate This works the same as ``discriminate`` but if the type of :n:`@term`, or the type of the hypothesis referred to by :n:`@num`, has uninstantiated @@ -1861,7 +1911,7 @@ See also: :ref:`TODO-2.3-Advancedrecursivefunctions` the form :n:`@term <> @term`, this behaves as :n:`intro @ident; discriminate @ident`. - .. exn:: No discriminable equalities + .. exn:: No discriminable equalities. .. tacn:: injection @term :name: injection @@ -1872,7 +1922,7 @@ See also: :ref:`TODO-2.3-Advancedrecursivefunctions` :g:`t`:sub:`1` and :g:`t`:sub:`2` are equal too. If :n:`@term` is a proof of a statement of conclusion :n:`@term = @term`, - then ``injection`` applies the injectivity of constructors as deep as + then :tacn:`injection` applies the injectivity of constructors as deep as possible to derive the equality of all the subterms of :n:`@term` and :n:`@term` at positions where the terms start to differ. For example, from :g:`(S p, S n) = (q, S (S m))` we may derive :g:`S p = q` and @@ -1882,90 +1932,96 @@ See also: :ref:`TODO-2.3-Advancedrecursivefunctions` equality of all the subterms at positions where they differ and adds them as antecedents to the conclusion of the current goal. -.. example:: + .. example:: - Consider the following goal: + Consider the following goal: - .. coqtop:: reset all + .. coqtop:: in - Inductive list : Set := - | nil : list - | cons : nat -> list -> list. - Variable P : list -> Prop. - Goal forall l n, P nil -> cons n l = cons 0 nil -> P l. - intros. - injection H0. + Inductive list : Set := + | nil : list + | cons : nat -> list -> list. + Parameter P : list -> Prop. + Goal forall l n, P nil -> cons n l = cons 0 nil -> P l. + .. coqtop:: all -Beware that injection yields an equality in a sigma type whenever the -injected object has a dependent type :g:`P` with its two instances in -different types :g:`(P t`:sub:`1` :g:`... t`:sub:`n` :g:`)` and -:g:`(P u`:sub:`1` :g:`... u`:sub:`n` :sub:`)`. If :g:`t`:sub:`1` and -:g:`u`:sub:`1` are the same and have for type an inductive type for which a decidable -equality has been declared using the command ``Scheme Equality`` (see :ref:`TODO-13.1-GenerationofinductionprincipleswithScheme`), -the use of a sigma type is avoided. + intros. + injection H0. -.. note:: - If some quantified hypothesis of the goal is named :n:`@ident`, - then :n:`injection @ident` first introduces the hypothesis in the local - context using :n:`intros until @ident`. + Beware that injection yields an equality in a sigma type whenever the + injected object has a dependent type :g:`P` with its two instances in + different types :g:`(P t`:sub:`1` :g:`... t`:sub:`n` :g:`)` and + :g:`(P u`:sub:`1` :g:`... u`:sub:`n` :sub:`)`. If :g:`t`:sub:`1` and + :g:`u`:sub:`1` are the same and have for type an inductive type for which a decidable + equality has been declared using the command :cmd:`Scheme Equality` + (see :ref:`proofschemes-induction-principles`), + the use of a sigma type is avoided. -.. exn:: Not a projectable equality but a discriminable one -.. exn:: Nothing to do, it is an equality between convertible @terms -.. exn:: Not a primitive equality -.. exn:: Nothing to inject + .. note:: + If some quantified hypothesis of the goal is named :n:`@ident`, + then :n:`injection @ident` first introduces the hypothesis in the local + context using :n:`intros until @ident`. -.. tacv:: injection @num + .. exn:: Not a projectable equality but a discriminable one. + .. exn:: Nothing to do, it is an equality between convertible @terms. + .. exn:: Not a primitive equality. + .. exn:: Nothing to inject. - This does the same thing as :n:`intros until @num` followed by - :n:`injection @ident` where :n:`@ident` is the identifier for the last - introduced hypothesis. + .. tacv:: injection @num -.. tacv:: injection @term with @bindings_list + This does the same thing as :n:`intros until @num` followed by + :n:`injection @ident` where :n:`@ident` is the identifier for the last + introduced hypothesis. - This does the same as :n:`injection @term` but using the given bindings to - instantiate parameters or hypotheses of :n:`@term`. + .. tacv:: injection @term with @bindings_list -.. tacv:: einjection @num -.. tacv:: einjection @term {? with @bindings_list} + This does the same as :n:`injection @term` but using the given bindings to + instantiate parameters or hypotheses of :n:`@term`. - This works the same as :n:`injection` but if the type of :n:`@term`, or the - type of the hypothesis referred to by :n:`@num`, has uninstantiated - parameters, these parameters are left as existential variables. + .. tacv:: einjection @num + :name: einjection + .. tacv:: einjection @term {? with @bindings_list} -.. tacv:: injection + This works the same as :n:`injection` but if the type of :n:`@term`, or the + type of the hypothesis referred to by :n:`@num`, has uninstantiated + parameters, these parameters are left as existential variables. - If the current goal is of the form :n:`@term <> @term` , this behaves as - :n:`intro @ident; injection @ident`. + .. tacv:: injection - .. exn:: goal does not satisfy the expected preconditions + If the current goal is of the form :n:`@term <> @term` , this behaves as + :n:`intro @ident; injection @ident`. -.. tacv:: injection @term {? with @bindings_list} as {+ @intro_pattern} -.. tacv:: injection @num as {+ intro_pattern} -.. tacv:: injection as {+ intro_pattern} -.. tacv:: einjection @term {? with @bindings_list} as {+ intro_pattern} -.. tacv:: einjection @num as {+ intro_pattern} -.. tacv:: einjection as {+ intro_pattern} + .. exn:: goal does not satisfy the expected preconditions. + + .. tacv:: injection @term {? with @bindings_list} as {+ @intro_pattern} + .. tacv:: injection @num as {+ intro_pattern} + .. tacv:: injection as {+ intro_pattern} + .. tacv:: einjection @term {? with @bindings_list} as {+ intro_pattern} + .. tacv:: einjection @num as {+ intro_pattern} + .. tacv:: einjection as {+ intro_pattern} These variants apply :n:`intros {+ @intro_pattern}` after the call to - ``injection`` or ``einjection`` so that all equalities generated are moved in + :tacn:`injection` or :tacn:`einjection` so that all equalities generated are moved in the context of hypotheses. The number of :n:`@intro_pattern` must not exceed the number of equalities newly generated. If it is smaller, fresh names are automatically generated to adjust the list of :n:`@intro_pattern` to the number of new equalities. The original equality is erased if it corresponds to an hypothesis. -It is possible to ensure that :n:`injection @term` erases the original -hypothesis and leaves the generated equalities in the context rather -than putting them as antecedents of the current goal, as if giving -:n:`injection @term as` (with an empty list of names). To obtain this -behavior, the option ``Set Structural Injection`` must be activated. This -option is off by default. + .. opt:: Structural Injection + + 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, ``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``. + 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 +2040,15 @@ turned off by setting the option ``Set Keep Proof Equalities``. .. note:: As ``inversion`` proofs may be large in size, we recommend the user to stock the lemmas whenever the same instance needs to be - inverted several times. See :ref:`TODO-13.3-Generationofinversionprincipleswithderiveinversion`. + inverted several times. See :ref:`derive-inversion`. .. note:: Part of the behavior of the ``inversion`` tactic is to generate equalities between expressions that appeared in the hypothesis that is being processed. By default, no equalities are generated if they relate two proofs (i.e. equalities between :n:`@terms` whose type is in sort - :g:`Prop`). This behavior can be turned off by using the option ``Set Keep - Proof Equalities``. + :g:`Prop`). This behavior can be turned off by using the option + :opt`Keep Proof Equalities`. .. tacv:: inversion @num @@ -2093,13 +2149,13 @@ turned off by setting the option ``Set Keep Proof Equalities``. :n:`dependent inversion_clear @ident`. .. tacv:: dependent inversion @ident with @term - :name: dependent inversion ... + :name: dependent inversion ... with ... This variant allows you to specify the generalization of the goal. It is useful when the system fails to generalize the goal automatically. If - :n:`@ident` has type :g:`(I t)` and :g:`I` has type :math:`\forall` - :g:`(x:T), s`, then :n:`@term` must be of type :g:`I:`:math:`\forall` - :g:`(x:T), I x -> s'` where :g:`s'` is the type of the goal. + :n:`@ident` has type :g:`(I t)` and :g:`I` has type :g:`forall (x:T), s`, + then :n:`@term` must be of type :g:`I:forall (x:T), I x -> s'` where + :g:`s'` is the type of the goal. .. tacv:: dependent inversion @ident as @intro_pattern with @term @@ -2108,7 +2164,7 @@ turned off by setting the option ``Set Keep Proof Equalities``. .. tacv:: dependent inversion_clear @ident with @term - Like :tacn:`dependent inversion ...` with but clears :n:`@ident` from the + Like :tacn:`dependent inversion ... with ...` with but clears :n:`@ident` from the local context. .. tacv:: dependent inversion_clear @ident as @intro_pattern with @term @@ -2117,6 +2173,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 +2357,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 +2378,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 +2392,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 @@ -2354,7 +2411,7 @@ Hence, some of the variables :g:`x`\ :sub:`i` are solved by unification, and some of the types :g:`A`\ :sub:`1`:g:`, ..., A`\ :sub:`n` become new subgoals. -.. exn:: The @term provided does not end with an equation +.. exn:: The @term provided does not end with an equation. .. exn:: Tactic generated a subgoal identical to the original goal. This happens if @term does not occur in the goal. @@ -2378,8 +2435,8 @@ subgoals. In particular a failure will happen if any of these three simpler tactics fails. + :n:`rewrite H in * |-` will do :n:`rewrite H in H`:sub:`i` for all hypotheses - :g:`H`:sub:`i` :g:`<> H`. A success will happen as soon as at least one of these - simpler tactics succeeds. + :g:`H`:sub:`i` different from :g:`H`. + A success will happen as soon as at least one of these simpler tactics succeeds. + :n:`rewrite H in *` is a combination of :n:`rewrite H` and :n:`rewrite H in * |-` that succeeds if at least one of these two tactics succeeds. @@ -2417,6 +2474,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 @@ -2431,7 +2489,7 @@ subgoals. the assumption, or if its symmetric form occurs. It is equivalent to :n:`cut @term = @term; [intro H`:sub:`n` :n:`; rewrite <- H`:sub:`n` :n:`; clear H`:sub:`n`:n:`|| assumption || symmetry; try assumption]`. -.. exn:: @terms do not have convertible types +.. exn:: @terms do not have convertible types. .. tacv:: replace @term with @term by tactic @@ -2463,6 +2521,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 +2565,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 - + 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`. + This option controls the behavior of :tacn:`subst`. When it is + activated, :tacn:`subst` also deals with the following corner cases: - 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. + + 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. .. tacn:: stepl @term @@ -2543,32 +2602,39 @@ 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`. + + .. cmd:: Declare Right Step @term - This behaves as :tacn:`stepl` but on the right-hand-side of the binary - relation. Lemmas are expected to be of the form :g:`forall x y z, R x y -> eq - y z -> R x z` and are registered using the command ``Declare Right Step - @term.`` + Adds :n:`@term` to the database used by :tacn:`stepr`. .. tacn:: change @term :name: change - This tactic applies to any goal. It implements the rule ``Conv`` given in - :ref:`TODO-4.4-Subtypingrules`. :g:`change U` replaces the current goal `T` - with `U` providing that `U` is well-formed and that `T` and `U` are - convertible. + 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 +.. exn:: Not convertible. .. tacv:: change @term with @term @@ -2581,7 +2647,7 @@ as regular setoids for :tacn:`rewrite` and :tacn:`setoid_replace` (see This replaces the occurrences numbered :n:`{+ @num}` of :n:`@term by @term` in the current goal. The terms :n:`@term` and :n:`@term` must be convertible. -.. exn:: Too few occurrences +.. exn:: Too few occurrences. .. tacv:: change @term in @ident .. tacv:: change @term with @term in @ident @@ -2637,7 +2703,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 +2715,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 +2770,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 +2780,7 @@ the conversion in hypotheses :n:`{+ @ident}`. reflection-based tactics. .. tacv:: native_compute + :name: native_compute This tactic evaluates the goal by compilation to Objective Caml as described in :cite:`FullReduction`. If Coq is running in native code, it can be @@ -2754,7 +2822,7 @@ the conversion in hypotheses :n:`{+ @ident}`. definition (say :g:`t`) and then reduces :g:`(t t`:sub:`1` :g:`... t`:sub:`n` :g:`)` according to :math:`\beta`:math:`\iota`:math:`\zeta`-reduction rules. -.. exn:: Not reducible +.. exn:: Not reducible. .. tacn:: hnf :name: hnf @@ -2768,7 +2836,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 @@ -2881,7 +2949,7 @@ the conversion in hypotheses :n:`{+ @ident}`. This applies ``simpl`` only to the :n:`{+ @num}` occurrences of the subterms matching :n:`@pattern` in the current goal. - .. exn:: Too few occurrences + .. exn:: Too few occurrences. .. tacv:: simpl @qualid .. tacv:: simpl @string @@ -2906,12 +2974,12 @@ the conversion in hypotheses :n:`{+ @ident}`. This tactic applies to any goal. The argument qualid must denote a defined transparent constant or local definition (see - :ref:`TODO-1.3.2-Definitions` and :ref:`TODO-6.10.2-Transparent`). The tactic + :ref:`gallina-definitions` and :ref:`vernac-controlling-the-reduction-strategies`). The tactic ``unfold`` applies the :math:`\delta` rule to each occurrence of the constant to which :n:`@qualid` refers in the current goal and then replaces it with its :math:`\beta`:math:`\iota`-normal form. -.. exn:: @qualid does not denote an evaluable constant +.. exn:: @qualid does not denote an evaluable constant. .. tacv:: unfold @qualid in @ident @@ -2928,9 +2996,9 @@ the conversion in hypotheses :n:`{+ @ident}`. The lists :n:`{+, @num}` specify the occurrences of :n:`@qualid` to be unfolded. Occurrences are located from left to right. - .. exn:: bad occurrence number of @qualid + .. exn:: Bad occurrence number of @qualid. - .. exn:: @qualid does not occur + .. exn:: @qualid does not occur. .. tacv:: unfold @string @@ -2942,7 +3010,7 @@ the conversion in hypotheses :n:`{+ @ident}`. This is variant of :n:`unfold @string` where :n:`@string` gets its interpretation from the scope bound to the delimiting key :n:`key` - instead of its default interpretation (see :ref:`TODO-12.2.2-Localinterpretationrulesfornotations`). + instead of its default interpretation (see :ref:`Localinterpretationrulesfornotations`). .. tacv:: unfold {+, qualid_or_string at {+, @num}} This is the most general form, where :n:`qualid_or_string` is either a @@ -3020,7 +3088,7 @@ Conversion tactics applied to hypotheses Example: :n:`unfold not in (Type of H1) (Type of H3)`. -.. exn:: No such hypothesis : ident. +.. exn:: No such hypothesis: @ident. .. _automation: @@ -3071,6 +3139,7 @@ hints of the database named core. to know what lemmas/assumptions were used. .. tacv:: debug auto + :name: debug auto Behaves like :tacn:`auto` but shows the tactics it tries to solve the goal, including failing paths. @@ -3090,7 +3159,9 @@ hints of the database named core. .. tacv:: trivial with * .. tacv:: trivial using {+ @lemma} .. tacv:: debug trivial + :name: debug trivial .. tacv:: info_trivial + :name: info_trivial .. tacv:: {? info_}trivial {? using {+ @lemma}} {? with {+ @ident}} .. note:: @@ -3103,7 +3174,7 @@ the :tacn:`auto` and :tacn:`trivial` tactics: .. opt:: Info Auto .. opt:: Debug Auto .. opt:: Info Trivial -.. opt:: Info Trivial +.. opt:: Debug Trivial See also: :ref:`The Hints Databases for auto and eauto <thehintsdatabasesforautoandeauto>` @@ -3123,7 +3194,7 @@ can solve such a goal: Goal forall P:nat -> Prop, P 0 -> exists n, P n. eauto. -Note that :tacn:`ex_intro` should be declared as a hint. +Note that ``ex_intro`` should be declared as a hint. .. tacv:: {? info_}eauto {? @num} {? using {+ @lemma}} {? with {+ @ident}} @@ -3200,7 +3271,8 @@ See also: :tacn:`autorewrite` for examples showing the use of this tactic. This tactic tries to solve the current goal by a number of standard closing steps. In particular, it tries to close the current goal using the closing tactics - :tacn:`trivial`, reflexivity, symmetry, contradiction and inversion of hypothesis. + :tacn:`trivial`, :tacn:`reflexivity`, :tacn:`symmetry`, :tacn:`contradiction` + and :tacn:`inversion` of hypothesis. If this fails, it tries introducing variables and splitting and-hypotheses, using the closing tactics afterwards, and splitting the goal using :tacn:`split` and recursing. @@ -3211,7 +3283,7 @@ See also: :tacn:`autorewrite` for examples showing the use of this tactic. .. tacv:: now @tactic :name: now - Run :n:`@tac` followed by ``easy``. This is a notation for :n:`@tactic; easy`. + Run :n:`@tactic` followed by :tacn:`easy`. This is a notation for :n:`@tactic; easy`. Controlling automation -------------------------- @@ -3221,225 +3293,245 @@ Controlling automation The hints databases for auto and eauto ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -The hints for ``auto`` and ``eauto`` are stored in databases. Each database -maps head symbols to a list of hints. One can use the command +The hints for :tacn:`auto` and :tacn:`eauto` are stored in databases. Each database +maps head symbols to a list of hints. .. cmd:: Print Hint @ident -to display the hints associated to the head symbol :n:`@ident` -(see :ref:`Print Hint <printhint>`). Each hint has a cost that is a nonnegative -integer, and an optional pattern. The hints with lower cost are tried first. A -hint is tried by ``auto`` when the conclusion of the current goal matches its -pattern or when it has no pattern. + Use this command + to display the hints associated to the head symbol :n:`@ident` + (see :ref:`Print Hint <printhint>`). Each hint has a cost that is a nonnegative + integer, and an optional pattern. The hints with lower cost are tried first. A + hint is tried by :tacn:`auto` when the conclusion of the current goal matches its + pattern or when it has no pattern. Creating Hint databases ``````````````````````` -One can optionally declare a hint database using the command ``Create -HintDb``. If a hint is added to an unknown database, it will be +One can optionally declare a hint database using the command +:cmd:`Create HintDb`. If a hint is added to an unknown database, it will be automatically created. -.. cmd:: Create HintDb @ident {? discriminated}. - -This command creates a new database named :n:`@ident`. The database is -implemented by a Discrimination Tree (DT) that serves as an index of -all the lemmas. The DT can use transparency information to decide if a -constant should be indexed or not (c.f. :ref:`The hints databases for auto and eauto <thehintsdatabasesforautoandeauto>`), -making the retrieval more efficient. The legacy implementation (the default one -for new databases) uses the DT only on goals without existentials (i.e., ``auto`` -goals), for non-Immediate hints and do not make use of transparency -hints, putting more work on the unification that is run after -retrieval (it keeps a list of the lemmas in case the DT is not used). -The new implementation enabled by the discriminated option makes use -of DTs in all cases and takes transparency information into account. -However, the order in which hints are retrieved from the DT may differ -from the order in which they were inserted, making this implementation -observationally different from the legacy one. +.. cmd:: Create HintDb @ident {? discriminated} + + This command creates a new database named :n:`@ident`. The database is + implemented by a Discrimination Tree (DT) that serves as an index of + all the lemmas. The DT can use transparency information to decide if a + constant should be indexed or not + (c.f. :ref:`The hints databases for auto and eauto <thehintsdatabasesforautoandeauto>`), + making the retrieval more efficient. The legacy implementation (the default one + for new databases) uses the DT only on goals without existentials (i.e., :tacn:`auto` + goals), for non-Immediate hints and do not make use of transparency + hints, putting more work on the unification that is run after + retrieval (it keeps a list of the lemmas in case the DT is not used). + The new implementation enabled by the discriminated option makes use + of DTs in all cases and takes transparency information into account. + However, the order in which hints are retrieved from the DT may differ + from the order in which they were inserted, making this implementation + observationally different from the legacy one. The general command to add a hint to some databases :n:`{+ @ident}` is -.. cmd:: Hint hint_definition : {+ @ident} +.. cmd:: Hint @hint_definition : {+ @ident} -**Variants:** + .. cmdv:: Hint @hint_definition + + No database name is given: the hint is registered in the core database. + + .. cmdv:: Local Hint @hint_definition : {+ @ident} + + This is used to declare hints that must not be exported to the other modules + that require and import the current module. Inside a section, the option + Local is useless since hints do not survive anyway to the closure of + sections. + + .. cmdv:: Local Hint @hint_definition -.. cmd:: Hint hint_definition + Idem for the core database. - No database name is given: the hint is registered in the core database. + .. cmdv:: Hint Resolve @term {? | {? @num} {? @pattern}} + :name: Hint Resolve -.. cmd:: Local Hint hint_definition : {+ @ident} + This command adds :n:`simple apply @term` to the hint list with the head + symbol of the type of :n:`@term`. The cost of that hint is the number of + subgoals generated by :n:`simple apply @term` or :n:`@num` if specified. The + associated :n:`@pattern` is inferred from the conclusion of the type of + :n:`@term` or the given :n:`@pattern` if specified. In case the inferred type + of :n:`@term` does not start with a product the tactic added in the hint list + is :n:`exact @term`. In case this type can however be reduced to a type + starting with a product, the tactic :n:`simple apply @term` is also stored in + the hints list. If the inferred type of :n:`@term` contains a dependent + quantification on a variable which occurs only in the premisses of the type + and not in its conclusion, no instance could be inferred for the variable by + unification with the goal. In this case, the hint is added to the hint list + of :tacn:`eauto` instead of the hint list of auto and a warning is printed. A + typical example of a hint that is used only by :tacn:`eauto` is a transitivity + lemma. - This is used to declare hints that must not be exported to the other modules - that require and import the current module. Inside a section, the option - Local is useless since hints do not survive anyway to the closure of - sections. + .. exn:: @term cannot be used as a hint -.. cmd:: Local Hint hint_definition + The head symbol of the type of :n:`@term` is a bound variable such that + this tactic cannot be associated to a constant. - Idem for the core database. + .. cmdv:: Hint Resolve {+ @term} -The ``hint_definition`` is one of the following expressions: + Adds each :n:`Hint Resolve @term`. -+ :n:`Resolve @term {? | {? @num} {? @pattern}}` - This command adds :n:`simple apply @term` to the hint list with the head symbol of the type of - :n:`@term`. The cost of that hint is the number of subgoals generated by - :n:`simple apply @term` or :n:`@num` if specified. The associated :n:`@pattern` - is inferred from the conclusion of the type of :n:`@term` or the given - :n:`@pattern` if specified. In case the inferred type of :n:`@term` does not - start with a product the tactic added in the hint list is :n:`exact @term`. - In case this type can however be reduced to a type starting with a product, - the tactic :n:`simple apply @term` is also stored in the hints list. If the - inferred type of :n:`@term` contains a dependent quantification on a variable - which occurs only in the premisses of the type and not in its conclusion, no - instance could be inferred for the variable by unification with the goal. In - this case, the hint is added to the hint list of :tacn:`eauto` instead of the - hint list of auto and a warning is printed. A typical example of a hint that - is used only by ``eauto`` is a transitivity lemma. + .. cmdv:: Hint Resolve -> @term - .. exn:: @term cannot be used as a hint + Adds the left-to-right implication of an equivalence as a hint (informally + the hint will be used as :n:`apply <- @term`, although as mentionned + before, the tactic actually used is a restricted version of + :tacn:`apply`). - The head symbol of the type of :n:`@term` is a bound variable such that - this tactic cannot be associated to a constant. + .. cmdv:: Resolve <- @term - **Variants:** + Adds the right-to-left implication of an equivalence as a hint. - + :n:`Resolve {+ @term}` - Adds each :n:`Resolve @term`. + .. cmdv:: Hint Immediate @term + :name: Hint Immediate - + :n:`Resolve -> @term` - Adds the left-to-right implication of an equivalence as a hint (informally - the hint will be used as :n:`apply <- @term`, although as mentionned - before, the tactic actually used is a restricted version of ``apply``). + This command adds :n:`simple apply @term; trivial` to the hint list associated + with the head symbol of the type of :n:`@ident` in the given database. This + tactic will fail if all the subgoals generated by :n:`simple apply @term` are + not solved immediately by the :tacn:`trivial` tactic (which only tries tactics + with cost 0).This command is useful for theorems such as the symmetry of + equality or :g:`n+1=m+1 -> n=m` that we may like to introduce with a limited + use in order to avoid useless proof-search. The cost of this tactic (which + never generates subgoals) is always 1, so that it is not used by :tacn:`trivial` + itself. - + :n:`Resolve <- @term` - Adds the right-to-left implication of an equivalence as a hint. + .. exn:: @term cannot be used as a hint -+ :n:`Immediate @term` - This command adds :n:`simple apply @term; trivial` to the hint list associated - with the head symbol of the type of :n:`@ident` in the given database. This - tactic will fail if all the subgoals generated by :n:`simple apply @term` are - not solved immediately by the ``trivial`` tactic (which only tries tactics - with cost 0).This command is useful for theorems such as the symmetry of - equality or :g:`n+1=m+1 -> n=m` that we may like to introduce with a limited - use in order to avoid useless proof-search.The cost of this tactic (which - never generates subgoals) is always 1, so that it is not used by ``trivial`` - itself. + .. cmdv:: Immediate {+ @term} - .. exn:: @term cannot be used as a hint + Adds each :n:`Hint Immediate @term`. - **Variants:** + .. cmdv:: Hint Constructors @ident + :name: Hint Constructors - + :n:`Immediate {+ @term}` - Adds each :n:`Immediate @term`. + If :n:`@ident` is an inductive type, this command adds all its constructors as + hints of type ``Resolve``. Then, when the conclusion of current goal has the form + :n:`(@ident ...)`, :tacn:`auto` will try to apply each constructor. -+ :n:`Constructors @ident` - If :n:`@ident` is an inductive type, this command adds all its constructors as - hints of type Resolve. Then, when the conclusion of current goal has the form - :n:`(@ident ...)`, ``auto`` will try to apply each constructor. + .. exn:: @ident is not an inductive type - .. exn:: @ident is not an inductive type + .. cmdv:: Hint Constructors {+ @ident} - **Variants:** + Adds each :n:`Hint Constructors @ident`. - + :n:`Constructors {+ @ident}` - Adds each :n:`Constructors @ident`. + .. cmdv:: Hint Unfold @qualid + :name: Hint Unfold -+ :n:`Unfold @qualid` - This adds the tactic :n:`unfold @qualid` to the hint list that will only be - used when the head constant of the goal is :n:`@ident`. - Its cost is 4. + This adds the tactic :n:`unfold @qualid` to the hint list that will only be + used when the head constant of the goal is :n:`@ident`. + Its cost is 4. - **Variants:** + .. cmdv:: Hint Unfold {+ @ident} - + :n:`Unfold {+ @ident}` - Adds each :n:`Unfold @ident`. + Adds each :n:`Hint Unfold @ident`. -+ :n:`Transparent`, :n:`Opaque @qualid` - This adds a transparency hint to the database, making :n:`@qualid` a - transparent or opaque constant during resolution. This information is used - during unification of the goal with any lemma in the database and inside the - discrimination network to relax or constrain it in the case of discriminated - databases. + .. cmdv:: Hint %( Transparent %| Opaque %) @qualid + :name: Hint %( Transparent %| Opaque %) - **Variants:** + This adds a transparency hint to the database, making :n:`@qualid` a + transparent or opaque constant during resolution. This information is used + during unification of the goal with any lemma in the database and inside the + discrimination network to relax or constrain it in the case of discriminated + databases. + + .. cmdv:: Hint %( Transparent %| Opaque %) {+ @ident} - + :n:`Transparent`, :n:`Opaque {+ @ident}` Declares each :n:`@ident` as a transparent or opaque constant. -+ :n:`Extern @num {? @pattern} => tactic` - This hint type is to extend ``auto`` with tactics other than ``apply`` and - ``unfold``. For that, we must specify a cost, an optional :n:`@pattern` and a - :n:`tactic` to execute. Here is an example:: - - Hint Extern 4 (~(_ = _)) => discriminate. - - Now, when the head of the goal is a disequality, ``auto`` will try - discriminate if it does not manage to solve the goal with hints with a - cost less than 4. One can even use some sub-patterns of the pattern in - the tactic script. A sub-pattern is a question mark followed by an - identifier, like ``?X1`` or ``?X2``. Here is an example: - - .. example:: - .. coqtop:: reset all - - Require Import List. - Hint Extern 5 ({?X1 = ?X2} + {?X1 <> ?X2}) => generalize X1, X2; decide equality : eqdec. - Goal forall a b:list (nat * nat), {a = b} + {a <> b}. - Info 1 auto with eqdec. - -+ :n:`Cut @regexp` - - .. warning:: these hints currently only apply to typeclass - proof search and the ``typeclasses eauto`` tactic (:ref:`TODO-20.6.5-typeclasseseauto`). - - This command can be used to cut the proof-search tree according to a regular - expression matching paths to be cut. The grammar for regular expressions is - the following. Beware, there is no operator precedence during parsing, one can - check with ``Print HintDb`` to verify the current cut expression: - - .. productionlist:: `regexp` - e : ident hint or instance identifier - :|_ any hint - :| e\|e′ disjunction - :| e e′ sequence - :| e * Kleene star - :| emp empty - :| eps epsilon - :| ( e ) - - The `emp` regexp does not match any search path while `eps` - matches the empty path. During proof search, the path of - successive successful hints on a search branch is recorded, as a - list of identifiers for the hints (note Hint Extern’s do not have - an associated identifier). - Before applying any hint :n:`@ident` the current path `p` extended with - :n:`@ident` is matched against the current cut expression `c` associated to - the hint database. If matching succeeds, the hint is *not* applied. The - semantics of ``Hint Cut e`` is to set the cut expression to ``c | e``, the - initial cut expression being `emp`. - -+ :n:`Mode @qualid {* (+ | ! | -)}` - This sets an optional mode of use of the identifier :n:`@qualid`. When - proof-search faces a goal that ends in an application of :n:`@qualid` to - arguments :n:`@term ... @term`, the mode tells if the hints associated to - :n:`@qualid` can be applied or not. A mode specification is a list of n ``+``, - ``!`` or ``-`` items that specify if an argument of the identifier is to be - treated as an input (``+``), if its head only is an input (``!``) or an output - (``-``) of the identifier. For a mode to match a list of arguments, input - terms and input heads *must not* contain existential variables or be - existential variables respectively, while outputs can be any term. Multiple - modes can be declared for a single identifier, in that case only one mode - needs to match the arguments for the hints to be applied.The head of a term - is understood here as the applicative head, or the match or projection - scrutinee’s head, recursively, casts being ignored. ``Hint Mode`` is - especially useful for typeclasses, when one does not want to support default - instances and avoid ambiguity in general. Setting a parameter of a class as an - input forces proof-search to be driven by that index of the class, with ``!`` - giving more flexibility by allowing existentials to still appear deeper in the - index but not at its head. + .. cmdv:: Hint Extern @num {? @pattern} => tactic + :name: Hint Extern -.. note:: - One can use an ``Extern`` hint with no pattern to do pattern-matching on - hypotheses using ``match goal`` with inside the tactic. + This hint type is to extend :tacn:`auto` with tactics other than :tacn:`apply` and + :tacn:`unfold`. For that, we must specify a cost, an optional :n:`@pattern` and a + :n:`@tactic` to execute. + + .. example:: + + .. coqtop:: in + + Hint Extern 4 (~(_ = _)) => discriminate. + + Now, when the head of the goal is a disequality, ``auto`` will try + discriminate if it does not manage to solve the goal with hints with a + cost less than 4. + + One can even use some sub-patterns of the pattern in + the tactic script. A sub-pattern is a question mark followed by an + identifier, like ``?X1`` or ``?X2``. Here is an example: + + .. example:: + + .. coqtop:: reset all + + Require Import List. + Hint Extern 5 ({?X1 = ?X2} + {?X1 <> ?X2}) => generalize X1, X2; decide equality : eqdec. + Goal forall a b:list (nat * nat), {a = b} + {a <> b}. + Info 1 auto with eqdec. + + .. cmdv:: Hint Cut @regexp + + .. warning:: + + These hints currently only apply to typeclass proof search and the + :tacn:`typeclasses eauto` tactic. + + This command can be used to cut the proof-search tree according to a regular + expression matching paths to be cut. The grammar for regular expressions is + the following. Beware, there is no operator precedence during parsing, one can + check with :cmd:`Print HintDb` to verify the current cut expression: + + .. productionlist:: `regexp` + e : ident hint or instance identifier + :| _ any hint + :| e\|e′ disjunction + :| e e′ sequence + :| e * Kleene star + :| emp empty + :| eps epsilon + :| ( e ) + + The `emp` regexp does not match any search path while `eps` + matches the empty path. During proof search, the path of + successive successful hints on a search branch is recorded, as a + list of identifiers for the hints (note Hint Extern’s do not have + an associated identifier). + Before applying any hint :n:`@ident` the current path `p` extended with + :n:`@ident` is matched against the current cut expression `c` associated to + the hint database. If matching succeeds, the hint is *not* applied. The + semantics of ``Hint Cut e`` is to set the cut expression to ``c | e``, the + initial cut expression being `emp`. + + .. cmdv:: Hint Mode @qualid {* (+ | ! | -)} + + This sets an optional mode of use of the identifier :n:`@qualid`. When + proof-search faces a goal that ends in an application of :n:`@qualid` to + arguments :n:`@term ... @term`, the mode tells if the hints associated to + :n:`@qualid` can be applied or not. A mode specification is a list of n ``+``, + ``!`` or ``-`` items that specify if an argument of the identifier is to be + treated as an input (``+``), if its head only is an input (``!``) or an output + (``-``) of the identifier. For a mode to match a list of arguments, input + terms and input heads *must not* contain existential variables or be + existential variables respectively, while outputs can be any term. Multiple + modes can be declared for a single identifier, in that case only one mode + needs to match the arguments for the hints to be applied.The head of a term + is understood here as the applicative head, or the match or projection + scrutinee’s head, recursively, casts being ignored. ``Hint Mode`` is + especially useful for typeclasses, when one does not want to support default + instances and avoid ambiguity in general. Setting a parameter of a class as an + input forces proof-search to be driven by that index of the class, with ``!`` + giving more flexibility by allowing existentials to still appear deeper in the + index but not at its head. + + .. note:: + + One can use an ``Extern`` hint with no pattern to do pattern-matching on + hypotheses using ``match goal`` with inside the tactic. Hint databases defined in the Coq standard library @@ -3521,7 +3613,7 @@ at every moment. (left to right). Notice that the rewriting bases are distinct from the ``auto`` hint bases and thatauto does not take them into account. - This command is synchronous with the section mechanism (see :ref:`TODO-2.4-Sectionmechanism`): + This command is synchronous with the section mechanism (see :ref:`section-mechanism`): when closing a section, all aliases created by ``Hint Rewrite`` in that section are lost. Conversely, when loading a module, all ``Hint Rewrite`` declarations at the global level of that module are loaded. @@ -3561,7 +3653,7 @@ described above: either they disappear at the end of a section scope, or they remain global forever. This causes a scalability issue, because hints coming from an unrelated part of the code may badly influence another development. It can be mitigated to some extent -thanks to the ``Remove Hints`` command (see :ref:`Remove Hints <removehints>`), +thanks to the :cmd:`Remove Hints` command, but this is a mere workaround and has some limitations (for instance, external hints cannot be removed). @@ -3569,73 +3661,70 @@ A proper way to fix this issue is to bind the hints to their module scope, as for most of the other objects Coq uses. Hints should only made available when the module they are defined in is imported, not just required. It is very difficult to change the historical behavior, as it would break a lot of scripts. -We propose a smooth transitional path by providing the ``Loose Hint Behavior`` +We propose a smooth transitional path by providing the :opt:`Loose Hint Behavior` option which accepts three flags allowing for a fine-grained handling of non-imported hints. -**Variants:** - -.. cmd:: Set Loose Hint Behavior "Lax" +.. opt:: Loose Hint Behavior %( "Lax" %| "Warn" %| "Strict" %) + :name: Loose Hint Behavior - This is the default, and corresponds to the historical behavior, that - is, hints defined outside of a section have a global scope. + This option accepts three values, which control the behavior of hints w.r.t. + :cmd:`Import`: -.. cmd:: Set Loose Hint Behavior "Warn" + - "Lax": this is the default, and corresponds to the historical behavior, + that is, hints defined outside of a section have a global scope. - When set, it outputs a warning when a non-imported hint is used. Note that - this is an over-approximation, because a hint may be triggered by a run that - will eventually fail and backtrack, resulting in the hint not being actually - useful for the proof. + - "Warn": outputs a warning when a non-imported hint is used. Note that this + is an over-approximation, because a hint may be triggered by a run that + will eventually fail and backtrack, resulting in the hint not being + actually useful for the proof. -.. cmd:: Set Loose Hint Behavior "Strict" + - "Strict": changes the behavior of an unloaded hint to a immediate fail + tactic, allowing to emulate an import-scoped hint mechanism. - When set, it changes the behavior of an unloaded hint to a immediate fail - tactic, allowing to emulate an import-scoped hint mechanism. +.. _tactics-implicit-automation: Setting implicit automation tactics ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -.. cmd:: Proof with tactic +.. cmd:: Proof with @tactic This command may be used to start a proof. It defines a default tactic to be used each time a tactic command ``tactic``:sub:`1` is ended by ``...``. In this case the tactic command typed by the user is equivalent to ``tactic``:sub:`1` ``;tactic``. -See also: Proof. in :ref:`TODO-7.1.4-Proofterm`. + See also: ``Proof.`` in :ref:`proof-editing-mode`. -**Variants:** -.. cmd:: Proof with tactic using {+ @ident} + .. cmdv:: Proof with tactic using {+ @ident} - Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`TODO-7.1.5-Proofusing` + Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`proof-editing-mode` -.. cmd:: Proof using {+ @ident} with tactic + .. cmdv:: Proof using {+ @ident} with @tactic - Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`TODO-7.1.5-Proofusing` + Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`proof-editing-mode` -.. cmd:: Declare Implicit Tactic tactic + .. cmd:: Declare Implicit Tactic @tactic - This command declares a tactic to be used to solve implicit arguments - that Coq does not know how to solve by unification. It is used every - time the term argument of a tactic has one of its holes not fully - resolved. + This command declares a tactic to be used to solve implicit arguments + that Coq does not know how to solve by unification. It is used every + time the term argument of a tactic has one of its holes not fully + resolved. -Here is an example: + .. 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 +3769,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 +3803,7 @@ and then uses :tacn:`auto` which completes the proof. Originally due to César Muñoz, these tactics (:tacn:`tauto` and :tacn:`intuition`) have been completely re-engineered by David Delahaye using -mainly the tactic language (see :ref:`TODO-9-thetacticlanguage`). The code is +mainly the tactic language (see :ref:`ltac`). The code is now much shorter and a significant increase in performance has been noticed. The general behavior with respect to dependent types, unfolding and introductions has slightly changed to get clearer semantics. This may lead to @@ -3721,26 +3811,20 @@ some incompatibilities. .. tacv:: intuition - Is equivalent to :g:`intuition auto with *`. + Is equivalent to :g:`intuition auto with *`. .. tacv:: dintuition + :name: dintuition - While :tacn:`intuition` recognizes inductively defined connectives - isomorphic to the standard connective ``and, prod, or, sum, False, - Empty_set, unit, True``, :tacn:`dintuition` recognizes also all inductive - types with one constructors and no indices, i.e. record-style connectives. + While :tacn:`intuition` recognizes inductively defined connectives + isomorphic to the standard connective ``and``, ``prod``, ``or``, ``sum``, ``False``, + ``Empty_set``, ``unit``, ``True``, :tacn:`dintuition` recognizes also all inductive + types with one constructors and no indices, i.e. record-style connectives. -Some aspects of the tactic :tacn:`intuition` can be controlled using options. -To avoid that inner negations which do not need to be unfolded are -unfolded, use: +.. opt:: Intuition Negation Unfolding -.. cmd:: Unset 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 +3848,18 @@ first- order reasoning, written by Pierre Corbineau. It is not restricted to usual logical connectives but instead may reason about any first-order class inductive definition. -The default tactic used by :tacn:`firstorder` when no rule applies is :g:`auto -with \*`, it can be reset locally or globally using the ``Set Firstorder -Solver`` tactic vernacular command and printed using ``Print Firstorder -Solver``. +.. opt:: Firstorder Solver @tactic + + The default tactic used by :tacn:`firstorder` when no rule applies is + :g:`auto with *`, it can be reset locally or globally using this option. + + .. cmd:: Print Firstorder Solver + + Prints the default tactic used by :tacn:`firstorder` when no rule applies. .. tacv:: firstorder @tactic - Tries to solve the goal with :n:`@tactic` when no logical rule may apply. + Tries to solve the goal with :n:`@tactic` when no logical rule may apply. .. tacv:: firstorder using {+ @qualid} @@ -3788,8 +3876,9 @@ Solver``. This combines the effects of the different variants of :tacn:`firstorder`. -Proof-search is bounded by a depth parameter which can be set by -typing the ``Set Firstorder Depth n`` vernacular command. +.. opt:: Firstorder Depth @num + + This option controls the proof-search depth bound. .. tacn:: congruence :name: congruence @@ -3830,11 +3919,12 @@ match against it. hypotheses using assert in order for :tacn:`congruence` to use them. .. tacv:: congruence with {+ @term} + :name: congruence with - Adds :n:`{+ @term}` to the pool of terms used by :tacn:`congruence`. This helps - in case you have partially applied constructors in your goal. + Adds :n:`{+ @term}` to the pool of terms used by :tacn:`congruence`. This helps + in case you have partially applied constructors in your goal. -.. exn:: I don’t know how to handle dependent equality +.. exn:: I don’t know how to handle dependent equality. The decision procedure managed to find a proof of the goal or of a discriminable equality but this proof could not be built in Coq because of @@ -3846,7 +3936,7 @@ match against it. arguments are supplied for some partially applied constructors. Any term of an appropriate type will allow the tactic to successfully solve the goal. Those additional arguments can be given to congruence by filling in the holes in the - terms given in the error message, using the with variant described above. + terms given in the error message, using the :tacn:`congruence with` variant described above. .. opt:: Congruence Verbose @@ -3865,7 +3955,7 @@ succeeds, and results in an error otherwise. This tactic checks whether its arguments are equal modulo alpha conversion and casts. -.. exn:: Not equal +.. exn:: Not equal. .. tacn:: unify @term @term :name: unify @@ -3873,12 +3963,12 @@ succeeds, and results in an error otherwise. This tactic checks whether its arguments are unifiable, potentially instantiating existential variables. -.. exn:: Not unifiable +.. exn:: Not unifiable. .. tacv:: unify @term @term with @ident Unification takes the transparency information defined in the hint database - :n:`@ident` into account (see :ref:`the hints databases for auto and eauto <the-hints-databases-for-auto-and-eauto>`). + :n:`@ident` into account (see :ref:`the hints databases for auto and eauto <thehintsdatabasesforautoandeauto>`). .. tacn:: is_evar @term :name: is_evar @@ -3887,7 +3977,7 @@ succeeds, and results in an error otherwise. variable. Existential variables are uninstantiated variables generated by :tacn:`eapply` and some other tactics. -.. exn:: Not an evar +.. exn:: Not an evar. .. tacn:: has_evar @term :name: has_evar @@ -3896,7 +3986,7 @@ succeeds, and results in an error otherwise. a subterm. Unlike context patterns combined with ``is_evar``, this tactic scans all subterms, including those under binders. -.. exn:: No evars +.. exn:: No evars. .. tacn:: is_var @term :name: is_var @@ -3904,7 +3994,7 @@ succeeds, and results in an error otherwise. This tactic checks whether its argument is a variable or hypothesis in the current goal context or in the opened sections. -.. exn:: Not a variable or hypothesis +.. exn:: Not a variable or hypothesis. .. _equality: @@ -3928,10 +4018,10 @@ solved by :tacn:`f_equal`. :name: reflexivity This tactic applies to a goal that has the form :g:`t=u`. It checks that `t` -and `u` are convertible and then solves the goal. It is equivalent to apply -:tacn:`refl_equal`. +and `u` are convertible and then solves the goal. It is equivalent to +``apply refl_equal``. -.. exn:: The conclusion is not a substitutive equation +.. exn:: The conclusion is not a substitutive equation. .. exn:: Unable to unify ... with ... @@ -4009,6 +4099,7 @@ symbol :g:`=`. .. tacv:: esimplify_eq @num .. tacv:: esimplify_eq @term {? with @bindings_list} + :name: esimplify_eq This works the same as ``simplify_eq`` but if the type of :n:`@term`, or the type of the hypothesis referred to by :n:`@num`, has uninstantiated @@ -4031,6 +4122,7 @@ symbol :g:`=`. :tacn:`injection` and :tacn:`inversion` tactics. .. tacv:: dependent rewrite <- @ident + :name: dependent rewrite <- Analogous to :tacn:`dependent rewrite ->` but uses the equality from right to left. @@ -4044,12 +4136,12 @@ Inversion :tacn:`functional inversion` is a tactic that performs inversion on hypothesis :n:`@ident` of the form :n:`@qualid {+ @term} = @term` or :n:`@term = @qualid {+ @term}` where :n:`@qualid` must have been defined using Function (see -:ref:`TODO-2.3-advancedrecursivefunctions`). Note that this tactic is only +:ref:`advanced-recursive-functions`). Note that this tactic is only available after a ``Require Import FunInd``. -.. exn:: Hypothesis @ident must contain at least one Function -.. exn:: Cannot find inversion information for hypothesis @ident +.. exn:: Hypothesis @ident must contain at least one Function. +.. exn:: Cannot find inversion information for hypothesis @ident. This error may be raised when some inversion lemma failed to be generated by Function. @@ -4077,10 +4169,10 @@ This kind of inversion has nothing to do with the tactic :tacn:`inversion` above. This tactic does :g:`change (@ident t)`, where `t` is a term built in order to ensure the convertibility. In other words, it does inversion of the function :n:`@ident`. This function must be a fixpoint on a simple recursive -datatype: see :ref:`TODO-10.3-quote` for the full details. +datatype: see :ref:`quote` for the full details. -.. exn:: quote: not a simple fixpoint +.. exn:: quote: not a simple fixpoint. Happens when quote is not able to perform inversion properly. @@ -4109,6 +4201,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 +4242,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 +4262,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 +4288,7 @@ denominators. So it produces an equation without division nor inverse. All of these 3 tactics may generate a subgoal in order to prove that denominators are different from zero. -See :ref:`TODO-Chapter-25-Theringandfieldtacticfamilies` for more information on the tactic and how to +See :ref:`Theringandfieldtacticfamilies` for more information on the tactic and how to declare new field structures. All declared field structures can be printed with the Print Fields command. @@ -4286,24 +4380,24 @@ This tactics reverses the list of the focused goals. This tactic moves all goals under focus to a shelf. While on the shelf, goals will not be focused on. They can be solved by unification, or they can be called back into focus with the command - :tacn:`Unshelve`. + :cmd:`Unshelve`. -.. tacv:: shelve_unifiable + .. tacv:: shelve_unifiable + :name: shelve_unifiable - Shelves only the goals under focus that are mentioned in other goals. - Goals that appear in the type of other goals can be solved by unification. + Shelves only the goals under focus that are mentioned in other goals. + Goals that appear in the type of other goals can be solved by unification. -.. example:: + .. example:: - .. coqtop:: all reset + .. coqtop:: all reset - Goal exists n, n=0. - refine (ex_intro _ _ _). - all:shelve_unifiable. - reflexivity. + Goal exists n, n=0. + refine (ex_intro _ _ _). + all: shelve_unifiable. + reflexivity. -.. tacn:: Unshelve - :name: Unshelve +.. cmd:: Unshelve This command moves all the goals on the shelf (see :tacn:`shelve`) from the shelf into focus, by appending them to the end of the current @@ -4334,11 +4428,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 index 0bb6eea233..c37233734b 100644 --- a/doc/sphinx/proof-engine/vernacular-commands.rst +++ b/doc/sphinx/proof-engine/vernacular-commands.rst @@ -14,62 +14,63 @@ Displaying .. _Print: -.. cmd:: Print @qualid. +.. cmd:: Print @qualid + :name: Print -This command displays on the screen information about the declared or -defined object referred by :n:`@qualid`. + This command displays on the screen information about the declared or + defined object referred by :n:`@qualid`. + Error messages: -Error messages: + .. exn:: @qualid not a defined object. + .. exn:: Universe instance should have length @num. -.. exn:: @qualid not a defined object + .. exn:: This object does not support universe names. -.. exn:: Universe instance should have length :n:`num`. -.. exn:: This object does not support universe names. + .. cmdv:: Print Term @qualid + :name: Print Term + This is a synonym of :cmd:`Print` :n:`@qualid` when :n:`@qualid` + denotes a global constant. -Variants: + .. cmdv:: Print {? Term } @qualid\@@name + This locally renames the polymorphic universes of :n:`@qualid`. + An underscore means the raw universe is printed. -.. cmdv:: Print Term @qualid. -This is a synonym to ``Print`` :n:`@qualid` when :n:`@qualid` -denotes a global constant. +.. cmd:: About @qualid + :name: About -.. cmdv:: About @qualid. + 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. -This displays various information about the object -denoted by :n:`@qualid`: its kind (module, constant, assumption, inductive, -constructor, abbreviation, …), long name, type, implicit arguments and -argument scopes. It does not print the body of definitions or proofs. + .. cmdv:: About @qualid\@@name -.. cmdv:: Print @qualid\@@name + This locally renames the polymorphic universes of :n:`@qualid`. + An underscore means the raw universe is printed. -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. +.. cmd:: Print All -This command displays information about the current state of the -environment, including sections and modules. + This command displays information about the current state of the + environment, including sections and modules. + .. cmdv:: Inspect @num + :name: Inspect -Variants: + This command displays the :n:`@num` last objects of the + current environment, including sections and modules. + .. cmdv:: Print Section @ident -.. cmdv:: Inspect @num. - -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. + 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: @@ -77,137 +78,144 @@ section. Flags, Options and Tables ----------------------------- -|Coq| configurability is based on flags (e.g. Set Printing All in -Section :ref:`TODO-2.9-printing-full`), options (e.g. ``Set Printing Widthinteger`` in Section -:ref:`TODO-6.9.6-set-printing-width`), or tables (e.g. ``Add Printing Record ident``, in Section -:ref:`TODO-2.2.4-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. +|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. - +.. cmd:: Set @flag -Variants: + This command switches :n:`@flag` on. The original state of :n:`@flag` + is restored when the current module ends. + .. cmdv:: Local Set @flag -.. cmdv:: Local Set @flag. + This command switches :n:`@flag` on. The original state + of :n:`@flag` is restored when the current *section* ends. -This command switches :n:`@flag` on. The original state -of :n:`@flag` is restored when the current *section* ends. + .. cmdv:: Global Set @flag -.. 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. -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. +.. cmd:: Unset @flag -This command switches :n:`@flag` off. The original state of :n:`@flag` is restored -when the current module ends. + This command switches :n:`@flag` off. The original state of + :n:`@flag` is restored when the current module ends. + .. cmdv:: Local Unset @flag -Variants: + This command switches :n:`@flag` off. The original + state of :n:`@flag` is restored when the current *section* ends. -.. cmdv:: Local Unset @flag. + .. cmdv:: Global Unset @flag -This command switches :n:`@flag` off. The original -state of :n:`@flag` is restored when the current *section* ends. + 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:: Global Unset @flag. + .. cmdv:: Export 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. + 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 -.. cmd:: Test @flag. + This command prints whether :n:`@flag` is on or off. -This command prints whether :n:`@flag` is on or off. +.. cmd:: Set @option @value -.. cmd:: Set @option @value. + This command sets :n:`@option` to :n:`@value`. The original value of ` option` is + restored when the current module ends. -This command sets :n:`@option` to :n:`@value`. The original value of ` option` is -restored when the current module ends. + .. TODO : option and value are not syntax entries + .. cmdv:: Local Set @option @value -Variants: + This command sets :n:`@option` to :n:`@value`. The + original value of :n:`@option` is restored at the end of the module. -.. TODO : option and value are not syntax entries + .. cmdv:: Global Set @option @value -.. cmdv:: Local 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. -This command sets :n:`@option` to :n:`@value`. The -original value of :n:`@option` is restored at the end of the module. + .. cmdv:: Export Set @option -.. cmdv:: Global Set @option @value. + 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. -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. +.. cmd:: Unset @option + This command turns off :n:`@option`. -.. cmd:: Unset @option. + .. cmdv:: Local Unset @option -This command resets option to its default value. + This command turns off :n:`@option`. The original state of :n:`@option` + is restored when the current *section* ends. + .. cmdv:: Global Unset @option -Variants: + 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 -.. cmdv:: Local 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. -This command resets :n:`@option` to its default -value. The original state of :n:`@option` is restored when the current -*section* ends. -.. cmdv:: Global Unset @option. +.. cmd:: Test @option -This command resets :n:`@option` to its default -value. 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. + This command prints the current value of :n:`@option`. +.. TODO : table is not a syntax entry -.. cmd:: Test @option. - -This command prints the current value of :n:`@option`. +.. cmd:: Add @table @value + :name: Add `table` `value` +.. cmd:: Remove @table @value + :name: Remove `table` `value` -.. TODO : table is not a syntax entry +.. cmd:: Test @table @value + :name: Test `table` `value` -.. cmd:: Add @table @value. -.. cmd:: Remove @table @value. -.. cmd:: Test @table @value. -.. cmd:: Test @table for @value. -.. cmd:: Print Table @table. +.. cmd:: Test @table for @value + :name: Test `table` for `value` -These are general commands for tables. +.. cmd:: Print Table @table -.. cmd:: Print Options. +These are general commands for tables. -This command lists all available flags, options and tables. +.. cmd:: Print Options -Variants: + This command lists all available flags, options and tables. + .. cmdv:: Print Tables -.. cmdv:: Print Tables. - -This is a synonymous of ``Print Options``. + This is a synonymous of :cmd:`Print Options`. .. _requests-to-the-environment: @@ -215,361 +223,333 @@ This is a synonymous of ``Print Options``. Requests to the environment ------------------------------- -.. cmd:: Check @term. +.. 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. + 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 -.. TODO : selector is not a syntax entry + .. cmdv:: @selector: Check @term -.. cmdv:: @selector: Check @term. + This variant specifies on which subgoal to perform typing + (see Section :ref:`invocation-of-tactics`). -specifies on which subgoal to perform typing -(see Section :ref:`TODO-8.1-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:`TODO-8.7-performing-computations`. - - -.. 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:`TODO-8.7-performing-computations`. - - -.. cmd::Extraction @term. +.. cmd:: Eval @convtactic in @term -This command displays the extracted term from :n:`@term`. The extraction is -processed according to the distinction between ``Set`` and ``Prop``; that is -to say, between logical and computational content (see Section -:ref:`TODO-4.1.1-sorts`). The extracted term is displayed in OCaml -syntax, -where global identifiers are still displayed as in |Coq| terms. + 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`. -Variants: +.. cmd:: Compute @term -.. cmdv:: Recursive Extraction {+ @qualid }. + 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`. -Recursively extracts all -the material needed for the extraction of the qualified identifiers. + See also: Section :ref:`performingcomputations`. -See also: Chapter ref:`TODO-23-chapter-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. -.. cmd:: Print Assumptions @qualid. + .. cmdv:: Print Opaque Dependencies @qualid + :name: Print Opaque Dependencies -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. + Displays the set of opaque constants :n:`@qualid` relies on in addition to + the assumptions. + .. cmdv:: Print Transparent Dependencies @qualid + :name: Print Transparent Dependencies -Variants: + Displays the set of transparent constants :n:`@qualid` relies on + in addition to the assumptions. + .. cmdv:: Print All Dependencies @qualid + :name: Print All Dependencies -.. cmdv:: Print Opaque Dependencies @qualid. + Displays all assumptions and constants :n:`@qualid` relies on. -Displays the set of opaque constants :n:`@qualid` relies on in addition to -the assumptions. -.. cmdv:: Print Transparent Dependencies @qualid. +.. cmd:: Search @qualid -Displays the set of -transparent constants :n:`@qualid` relies on in addition to the assumptions. + 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. -.. cmdv:: Print All Dependencies @qualid. + .. exn:: The reference @qualid was not found in the current environment. -Displays all assumptions and constants :n:`@qualid` relies on. + There is no constant in the environment named qualid. + .. cmdv:: Search @string + If :n:`@string` is a valid identifier, this command + displays the name and type of all objects (theorems, axioms, etc) of + the current context whose name contains string. If string is a + notation’s string denoting some reference :n:`@qualid` (referred to by its + main symbol as in `"+"` or by its notation’s string as in `"_ + _"` or + `"_ 'U' _"`, see Section :ref:`notations`), the command works like ``Search`` :n:`@qualid`. -.. cmd:: Search @qualid. + .. cmdv:: Search @string%@key -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. + 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 -Error messages: + 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 } -.. exn:: The reference @qualid was not found in the current environment + 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. -There is no constant in the environment named qualid. + .. cmdv:: Search @term_pattern_string … @term_pattern_string inside {+ @qualid } -Variants: + This restricts the search to constructions defined in the modules + named by the given :n:`qualid` sequence. -.. cmdv:: Search @string. + .. cmdv:: Search @term_pattern_string … @term_pattern_string outside {+ @qualid } -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:`TODO-12.1-notations`), the command works like ``Search`` :n:`@qualid`. + This restricts the search to constructions not defined in the modules + named by the given :n:`qualid` sequence. -.. cmdv:: Search @string%@key. + .. cmdv:: @selector: Search [-]@term_pattern_string … [-]@term_pattern_string -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:`TODO-12.2.2-local-interpretation-rules-for-notations`). + 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:: Search @term_pattern. + .. example:: -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). + .. coqtop:: in -.. cmdv:: Search { + [-]@term_pattern_string }. + Require Import ZArith. -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. + .. coqtop:: all -.. cmdv:: Search @term_pattern_string … @term_pattern_string inside {+ @qualid } . + Search Z.mul Z.add "distr". -This restricts the search to constructions defined in the modules named by the given :n:`qualid` sequence. + Search "+"%Z "*"%Z "distr" -positive -Prop. -.. cmdv:: Search @term_pattern_string … @term_pattern_string outside {+ @qualid }. + Search (?x * _ + ?x * _)%Z outside OmegaLemmas. -This restricts the search to constructions not defined in the modules named by the given :n:`qualid` sequence. + .. cmdv:: SearchAbout + :name: SearchAbout -.. cmdv:: @selector: Search [-]@term_pattern_string … [-]@term_pattern_string. + .. deprecated:: 8.5 -This specifies the goal on which to search hypothesis (see -Section :ref:`TODO-8.1-invocation-of-tactics`). -By default the 1st goal is searched. This variant can -be combined with other variants presented here. + Up to |Coq| version 8.4, :cmd:`Search` had the behavior of current + :cmd:`SearchHead` and the behavior of current :cmd:`Search` was obtained with + command :cmd:`SearchAbout`. For compatibility, the deprecated name + :cmd:`SearchAbout` can still be used as a synonym of :cmd:`Search`. For + compatibility, the list of objects to search when using :cmd:`SearchAbout` + may also be enclosed by optional ``[ ]`` delimiters. -.. coqtop:: in +.. cmd:: SearchHead @term - Require Import ZArith. + 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:: all + .. example:: - Search Z.mul Z.add "distr". + .. coqtop:: reset all - Search "+"%Z "*"%Z "distr" -positive -Prop. + SearchHead le. - Search (?x * _ + ?x * _)%Z outside OmegaLemmas. + SearchHead (@eq bool). -.. 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. + .. cmdv:: SearchHead @term inside {+ @qualid } + This restricts the search to constructions defined in the modules named + by the given :n:`qualid` sequence. -.. cmd:: SearchHead @term. + .. cmdv:: SearchHead term outside {+ @qualid } -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. + This restricts the search to constructions not defined in the modules + named by the given :n:`qualid` sequence. + .. exn:: Module/section @qualid not found. + No module :n:`@qualid` has been required (see Section :ref:`compiled-files`). -.. coqtop:: reset all + .. cmdv:: @selector: SearchHead @term - SearchHead le. + 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. - SearchHead (@eq bool). + .. note:: Up to |Coq| version 8.4, ``SearchHead`` was named ``Search``. -Variants: +.. cmd:: SearchPattern @term -.. cmdv:: SearchHead @term inside {+ @qualid }. + This command displays the name and type of all hypothesis of the + current goal (if any) and theorems of the current context whose + statement’s conclusion or last hypothesis and conclusion matches the + expressionterm where holes in the latter are denoted by `_`. + It is a variant of :n:`Search @term_pattern` that does not look for subterms + but searches for statements whose conclusion has exactly the expected + form, or whose statement finishes by the given series of + hypothesis/conclusion. -This restricts the search to constructions defined in the modules named by the given :n:`qualid` sequence. + .. example:: -.. cmdv:: SearchHead term outside {+ @qualid }. + .. coqtop:: in -This restricts the search to constructions not defined in the modules named by the given :n:`qualid` sequence. + Require Import Arith. -Error messages: + .. coqtop:: all -.. exn:: Module/section @qualid not found + SearchPattern (_ + _ = _ + _). -No module :n:`@qualid` has been required -(see Section :ref:`TODO-6.5.1-require`). + SearchPattern (nat -> bool). -.. cmdv:: @selector: SearchHead @term. + SearchPattern (forall l : list _, _ l l). -This specifies the goal on which to -search hypothesis (see Section :ref:`TODO-8.1-invocation-of-tactics`). -By default the 1st goal is -searched. This variant can be combined with other variants presented -here. + Patterns need not be linear: you can express that the same expression + must occur in two places by using pattern variables `?ident`. -.. note:: Up to |Coq| version 8.4, ``SearchHead`` was named ``Search``. + .. example:: -.. cmd:: SearchPattern @term. + .. coqtop:: all -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. + SearchPattern (?X1 + _ = _ + ?X1). -.. coqtop:: in + .. cmdv:: SearchPattern @term inside {+ @qualid } - Require Import Arith. + This restricts the search to constructions defined in the modules + named by the given :n:`qualid` sequence. -.. coqtop:: all + .. cmdv:: SearchPattern @term outside {+ @qualid } - SearchPattern (_ + _ = _ + _). + This restricts the search to constructions not defined in the modules + named by the given :n:`qualid` sequence. - SearchPattern (nat -> bool). + .. cmdv:: @selector: SearchPattern @term - SearchPattern (forall l : list _, _ l l). + 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. -Patterns need not be linear: you can express that the same expression -must occur in two places by using pattern variables `?ident`. +.. cmd:: SearchRewrite @term -.. coqtop:: all + 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 “_”. - SearchPattern (?X1 + _ = _ + ?X1). + .. example:: -Variants: + .. coqtop:: in + Require Import Arith. -.. cmdv:: SearchPattern @term inside {+ @qualid } . + .. coqtop:: all -This restricts the search to constructions defined in the modules named by the given :n:`qualid` sequence. + SearchRewrite (_ + _ + _). -.. cmdv:: SearchPattern @term outside {+ @qualid }. + .. cmdv:: SearchRewrite term inside {+ @qualid } -This restricts the search to constructions not defined in the modules named by the given :n:`qualid` sequence. + This restricts the search to constructions defined in the modules + named by the given :n:`qualid` sequence. -.. cmdv:: @selector: SearchPattern @term. + .. cmdv:: SearchRewrite @term outside {+ @qualid } -This specifies the goal on which to -search hypothesis (see Section :ref:`TODO-8.1-invocation-of-tactics`). By default the 1st goal is -searched. This variant can be combined with other variants presented -here. + This restricts the search to constructions not defined in the modules + named by the given :n:`qualid` sequence. + .. cmdv:: @selector: SearchRewrite @term - -.. 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:`TODO-8.1-invocation-of-tactics`). By default the 1st goal is -searched. This variant can be combined with other variants presented -here. + 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:: Add Search Blacklist @string + For the ``Search``, ``SearchHead``, ``SearchPattern`` and ``SearchRewrite`` + queries, it is possible to globally filter the search results using this + command. A lemma whose fully-qualified name + contains any of the declared strings will be removed from the + search results. The default blacklisted substrings are ``_subproof`` and + ``Private_``. -.. cmd:: Locate @qualid. + .. cmd:: Remove Search Blacklist @string -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. + This command allows expunging this blacklist. -.. coqtop:: none - Set Printing Depth 50. +.. cmd:: Locate @qualid -.. coqtop:: all + 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. - Locate nat. + .. example:: - Locate Datatypes.O. + .. coqtop:: all - Locate Init.Datatypes.O. + Locate nat. - Locate Coq.Init.Datatypes.O. + Locate Datatypes.O. - Locate I.Dont.Exist. + Locate Init.Datatypes.O. -Variants: + Locate Coq.Init.Datatypes.O. + Locate I.Dont.Exist. -.. cmdv:: Locate Term @qualid. + .. cmdv:: Locate Term @qualid -As Locate but restricted to terms. + As Locate but restricted to terms. -.. cmdv:: Locate Module @qualid. + .. cmdv:: Locate Module @qualid -As Locate but restricted to modules. + As Locate but restricted to modules. -.. cmdv:: Locate Ltac @qualid. + .. cmdv:: Locate Ltac @qualid -As Locate but restricted to tactics. + As Locate but restricted to tactics. - -See also: Section :ref:`TODO-12.1.10-LocateSymbol` +See also: Section :ref:`locating-notations` .. _loading-files: @@ -585,40 +565,35 @@ 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:`TODO-2.6.3-libraries-and-filesystem`) - -Files loaded this way cannot leave proofs open, and the ``Load`` -command cannot be used inside a proof either. - -Variants: +.. 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`) -.. cmdv:: Load @string. + Files loaded this way cannot leave proofs open, and the ``Load`` + command cannot be used inside a proof either. -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 @string -.. cmdv:: Load Verbose @ident. + 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 @string. + .. cmdv:: Load Verbose @ident -Display, while loading, -the answers of |Coq| to each command (including tactics) contained in -the loaded file See also: Section :ref:`TODO-6.9.1-silent`. + .. cmdv:: Load Verbose @string -Error messages: + Display, while loading, + the answers of |Coq| to each command (including tactics) contained in + the loaded file See also: Section :ref:`controlling-display`. -.. exn:: Can’t find file @ident on loadpath + .. exn:: Can’t find file @ident on loadpath. -.. exn:: Load is not supported inside proofs + .. exn:: Load is not supported inside proofs. -.. exn:: Files processed by Load cannot leave open proofs + .. exn:: Files processed by Load cannot leave open proofs. .. _compiled-files: @@ -626,155 +601,143 @@ Compiled files ------------------ This section describes the commands used to load compiled files (see -Chapter :ref:`TODO-14-coq-commands` for documentation on how to compile a file). A compiled +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. +.. 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. + This command looks in the loadpath for a file containing module :n:`@qualid` + and adds the corresponding module to the environment of |Coq|. As + library files have dependencies in other library files, the command + :cmd:`Require` :n:`@qualid` recursively requires all library files the module + qualid depends on and adds the corresponding modules to the + environment of |Coq| too. |Coq| assumes that the compiled files have been + produced by a valid |Coq| compiler and their contents are then not + replayed nor rechecked. -To locate the file in the file system, :n:`@qualid` is decomposed under the -form `dirpath.ident` and the file `ident.vo` is searched in the physical -directory of the file system that is mapped in |Coq| loadpath to the -logical path dirpath (see Section :ref:`TODO-2.6.3-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. + 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 + :name: Require Import -.. 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 :cmd:`Require Export`, as described below, or recursively required + through a sequence of :cmd:`Require Export`. If the module required has + already been loaded, :cmd:`Require Import` :n:`@qualid` simply imports it, as + :cmd:`Import` :n:`@qualid` would. -This loads and declares the module :n:`@qualid` -and its dependencies then imports the contents of :n:`@qualid` as described -in Section :ref:`TODO-2.5.8-import`.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 + :name: Require Export -.. cmdv:: Require Export @qualid. + This command acts as :cmd:`Require Import` :n:`@qualid`, + but if a further module, say `A`, contains a command :cmd:`Require Export` `B`, + then the command :cmd:`Require Import` `A` also imports the module `B.` -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 } -.. 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``. -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 -.. cmdv:: From @dirpath Require @qualid. + This command acts as :cmd:`Require`, but picks + any library whose absolute name is of the form dirpath.dirpath’.qualid + for some `dirpath’`. This is useful to ensure that the :n:`@qualid` library + comes from a given package by making explicit its absolute root. -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. + .. 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`). -Error messages: + .. exn:: Compiled library @ident.vo makes inconsistent assumptions over library qualid. -.. exn:: Cannot load qualid: no physical path bound to dirpath + 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:: Cannot find library foo in loadpath + .. exn:: Bad magic number. -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:`TODO-2.6.3-libraries-and-filesystem`). + 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:: Compiled library ident.vo makes inconsistent assumptions over library qualid + .. exn:: The file `ident.vo` contains library dirpath and not library dirpath’. -The command tried to load library file `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`. + 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:: 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:: Require is not allowed inside a module or a module type. -.. exn:: The file `ident.vo` contains library dirpath and not library dirpath’ + 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>`). -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 +See also: Chapter :ref:`thecoqcommands` -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:`TODO-2.5.8-import`). +.. 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. -See also: Chapter :ref:`TODO-14-coq-commands` +.. cmd:: Declare ML Module {+ @string } -.. cmd:: Print Libraries. + 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). -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. + .. 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. -.. cmd:: Declare ML Module {+ @string } . + .. exn:: File not found on loadpath: @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:`TODO-2.6.3-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:`TODO-14-coq-commands`), or when |Coq| has been compiled with a -version of OCaml that supports native Dynlink (≥ 3.11). + .. exn:: Loading of ML object file forbidden in a native Coq. -Variants: +.. cmd:: Print ML Modules - -.. 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 Section :ref:`TODO-6.6.10-locate-file`) + 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: @@ -783,114 +746,97 @@ Loadpath ------------ Loadpaths are preferably managed using |Coq| command line options (see -Section `2.6.3-libraries-and-filesystem`) but there remain vernacular commands to manage them +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. +.. cmd:: Pwd -Is equivalent to Pwd. + This command displays the current working directory. +.. cmd:: Cd @string -.. cmd:: Add LoadPath @string as @dirpath. + This command changes the current directory according to :n:`@string` which + can be any valid path. -This command is equivalent to the command line option -``-Q`` :n:`@string` :n:`@dirpath`. It adds the physical directory string to the current -|Coq| loadpath and maps it to the logical directory dirpath. + .. cmdv:: Cd -Variants: + Is equivalent to Pwd. -.. cmdv:: Add LoadPath @string. +.. cmd:: Add LoadPath @string as @dirpath -Performs as Add LoadPath :n:`@string` as :n:`@dirpath` but -for the empty directory path. + This command is equivalent to the command line option + ``-Q`` :n:`@string` :n:`@dirpath`. It adds the physical directory string to the current + |Coq| loadpath and maps it to the logical directory dirpath. + .. cmdv:: Add LoadPath @string + Performs as Add LoadPath :n:`@string` as :n:`@dirpath` but + for the empty directory path. -.. cmd:: Add Rec LoadPath @string as @dirpath. -This command is equivalent to the command line option -``-R`` :n:`@string` :n:`@dirpath`. It adds the physical directory string and all its -subdirectories to the current |Coq| loadpath. +.. cmd:: Add Rec LoadPath @string as @dirpath -Variants: + This command is equivalent to the command line option + ``-R`` :n:`@string` :n:`@dirpath`. It adds the physical directory string and all its + subdirectories to the current |Coq| loadpath. + .. cmdv:: Add Rec LoadPath @string -.. cmdv:: Add Rec LoadPath @string. + Works as :cmd:`Add Rec LoadPath` :n:`@string` as :n:`@dirpath` but for the empty + logical directory path. -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:: 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. -.. cmd:: Print LoadPath. + .. cmdv:: Print LoadPath @dirpath -This command displays the current |Coq| loadpath. + Works as :cmd:`Print LoadPath` but displays only + the paths that extend the :n:`@dirpath` prefix. -Variants: +.. 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`). -.. cmdv:: Print LoadPath @dirpath. -Works as ``Print LoadPath`` but displays only -the paths that extend the :n:`@dirpath` prefix. +.. cmd:: Add Rec ML Path @string + This command adds the directory :n:`@string` and all its subdirectories to + the current OCaml loadpath (see the command :cmd:`Declare ML Module`). -.. cmd:: 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:`TODO-6.5-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`). -.. cmd:: Add Rec ML Path @string. +.. _locate-file: -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:`TODO-6.5-compiled-files`). +.. 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:: 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:`TODO-6.5-compiled-files`). +.. cmd:: Locate Library @dirpath - -.. 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`. + 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: @@ -903,95 +849,72 @@ 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:`TODO-7-proof-handling`). 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: +.. 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. -.. cmdv:: Back @num. + .. exn:: @ident: no such entry. -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. + .. cmdv:: Reset Initial + Goes back to the initial state, just after the start + of the interactive session. -Error messages: +.. cmd:: Back + This command undoes all the effects of the last vernacular command. + Commands read from a vernacular file via a :cmd:`Load` are considered as a + single command. Proof management commands are also handled by this + command (see Chapter :ref:`proofhandling`). For that, Back may have to undo more than + one command in order to reach a state where the proof management + information is available. For instance, when the last command is a + :cmd:`Qed`, the management information about the closed proof has been + discarded. In this case, :cmd:`Back` will then undo all the proof steps up to + the statement of this proof. -.. exn:: Invalid backtrack + .. cmdv:: Back @num -The user wants to undo more commands than available in the history. + Undo :n:`@num` vernacular commands. As for Back, some extra + commands may be undone in order to reach an adequate state. For + instance Back :n:`@num` will not re-enter a closed proof, but rather go just + before that proof. -.. cmd:: BackTo @num. + .. exn:: Invalid backtrack. -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. + The user wants to undo more commands than available in the history. +.. cmd:: BackTo @num -Variants: + This command brings back the system to the state labeled :n:`@num`, + forgetting the effect of all commands executed after this state. The + state label is an integer which grows after each successful command. + It is displayed in the prompt when in -emacs mode. Just as :cmd:`Back` (see + above), the :cmd:`BackTo` command now handles proof states. For that, it may + have to undo some extra commands and end on a state `num′ ≤ num` if + necessary. + .. cmdv:: Backtrack @num @num @num + :name: Backtrack -.. cmdv:: Backtrack @num @num @num. + .. deprecated:: 8.4 -`Backtrack` is a *deprecated* form of -`BackTo` which allows explicitly manipulating the proof environment. The -three numbers represent the following: + :cmd:`Backtrack` is a *deprecated* form of + :cmd:`BackTo` which allows explicitly manipulating the proof environment. The + three numbers represent the following: - + *first number* : State label to reach, as for 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:`TODO-7-proof-handling`). - + *third number* : Number of Abort to perform, i.e. the number of currently - opened nested proofs that must be canceled (see Chapter :ref:`TODO-7-proof-handling`). + + *first number* : State label to reach, as for :cmd:`BackTo`. + + *second number* : *Proof state number* to unbury once aborts have been done. + |Coq| will compute the number of :cmd:`Undo` to perform (see Chapter :ref:`proofhandling`). + + *third number* : Number of :cmd:`Abort` to perform, i.e. the number of currently + opened nested proofs that must be canceled (see Chapter :ref:`proofhandling`). + .. exn:: Invalid backtrack. - - -Error messages: - - -.. exn:: Invalid backtrack - - -The destination state label is unknown. + The destination state label is unknown. .. _quitting-and-debugging: @@ -1000,227 +923,143 @@ 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: +.. cmd:: Quit + This command permits to quit |Coq|. -:: - #use "include";; +.. 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: -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: + :: + #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();; + :: + go();; + .. warning:: -Warnings: - - -#. It only works with the bytecode version of |Coq| (i.e. `coqtop.byte`, - see Section `TODO-14.1-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 `14.3.2-customization-by-envionment-variables`). - + #. 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:: Time @command -.. cmd:: Redirect @string @command. + This command executes the vernacular command :n:`@command` and displays the + time needed to execute it. -This command executes the vernacular command :n:`@command`, redirecting its -output to ":n:`@string`.out". +.. cmd:: Redirect @string @command -.. cmd:: Timeout @num @command. + This command executes the vernacular command :n:`@command`, redirecting its + output to ":n:`@string`.out". -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. +.. cmd:: Timeout @num @command -.. cmd:: Set Default Timeout @num. + 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. -After using this command, all subsequent commands behave as if they -were passed to a Timeout command. Commands already starting by a -`Timeout` are unaffected. + .. 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:: Unset Default Timeout. -This command turns off the use of a default timeout. +.. cmd:: Fail @command -.. cmd:: Test Default Timeout. + 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. -This command displays whether some default timeout has been set or not. + .. exn:: The command has not failed! -.. 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 -.. cmd:: Set Silent. - -This command turns off the normal displaying. - - -.. cmd:: Unset Silent. - -This command turns the normal display on. - -TODO : check that spaces are handled well - -.. cmd:: Set Warnings ‘‘(@ident {* , @ident } )’’. - -This command 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`. - - -.. cmd:: Set Search Output Name Only. - -This command restricts the output of search commands to identifier -names; turning it on causes invocations of ``Search``, ``SearchHead``, -``SearchPattern``, ``SearchRewrite`` etc. to omit types from their output, -printing only identifiers. - - -.. cmd:: Unset Search Output Name Only. - -This command turns type display in search results back on. - - -.. cmd:: Set Printing Width @integer. - -This command sets which left-aligned part of the width of the screen -is used for display. - - -.. cmd:: Unset Printing Width. - -This command resets the width of the screen used for display to its -default value (which is 78 at the time of writing this documentation). + This option controls the normal displaying. +.. opt:: Warnings "{+, {? %( - %| + %) } @ident }" -.. cmd:: Test Printing Width. + 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`. -This command displays the current screen width used for display. +.. 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. -.. cmd:: Set Printing Depth @integer. +.. opt:: Printing Width @num + :name: Printing Width -This command sets the nesting depth of the formatter used for pretty- -printing. Beyond this depth, display of subterms is replaced by dots. + This command sets which left-aligned part of the width of the screen is used + for display. At the time of writing this documentation, the default value + is 78. +.. opt:: Printing Depth @num + :name: Printing Depth -.. cmd:: Unset Printing Depth. + This option controls the nesting depth of the formatter used for pretty- + printing. Beyond this depth, display of subterms is replaced by dots. At the + time of writing this documentation, the default value is 50. -This command resets the nesting depth of the formatter used for -pretty-printing to its default value (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. -.. cmd:: Test Printing Depth. +.. opt:: Printing Unfocused -This command displays the current nesting depth used for display. + 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 -.. cmd:: Unset Printing Compact Contexts. + This option controls the printing of the “(dependent evars: …)” line when + ``-emacs`` is passed. -This command resets the displaying of goals contexts to non compact -mode (default at the time of writing this documentation). Non compact -means that consecutive variables of different types are printed on -different lines. - - -.. cmd:: Set Printing Compact Contexts. - -This command sets the displaying of goals contexts to compact mode. -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 Set Printing -Width above). - - -.. cmd:: Test Printing Compact Contexts. - -This command displays the current state of compaction of goal. - - -.. cmd:: Unset Printing Unfocused. - -This command resets the displaying of goals to focused goals only -(default). Unfocused goals are created by focusing other goals with -bullets (see :ref:`TODO-7.2.7-bullets`) or curly braces (see `7.2.6-curly-braces`). - - -.. cmd:: Set Printing Unfocused. - -This command enables the displaying of unfocused goals. The goals are -displayed after the focused ones and are distinguished by a separator. - - -.. cmd:: Test Printing Unfocused. - -This command displays the current state of unfocused goals display. - - -.. cmd:: Set Printing Dependent Evars Line. - -This command enables the printing of the “(dependent evars: …)” line -when -emacs is passed. - - -.. cmd:: Unset Printing Dependent Evars Line. - -This command disables the printing of the “(dependent evars: …)” line -when -emacs is passed. +.. _vernac-controlling-the-reduction-strategies: Controlling the reduction strategies and the conversion algorithm ---------------------------------------------------------------------- @@ -1232,84 +1071,83 @@ 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 [`98`]. It is +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:`TODO-4.3-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:`TODO-8.7-performing-computations`, :ref:`TODO-8.16-automatizing`, :ref:`TODO-7.1-switching-on-off-proof-editing-mode` - - -Error messages: +.. cmd:: Opaque {+ @qualid } + This command has an effect on unfoldable constants, i.e. on constants + defined by :cmd:`Definition` or :cmd:`Let` (with an explicit body), or by a command + assimilated to a definition such as :cmd:`Fixpoint`, :cmd:`Program Definition`, etc, + or by a proof ended by :cmd:`Defined`. The command tells not to unfold the + constants in the :n:`@qualid` sequence in tactics using δ-conversion (unfolding + a constant is replacing it by its definition). -.. exn:: The reference @qualid was not found in the current environment + :cmd:`Opaque` has also an effect on the conversion algorithm of |Coq|, telling + it to delay the unfolding of a constant as much as possible when |Coq| + has to check the conversion (see Section :ref:`conversion-rules`) of two distinct + applied constants. -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. + .. cmdv:: Global Opaque {+ @qualid } + :name: Global Opaque -.. cmd:: Transparent {+ @qualid }. + The scope of :cmd:`Opaque` is limited to the current section, or current + file, unless the variant :cmd:`Global Opaque` is used. -This command is the converse of `Opaque`` and it applies on unfoldable -constants to restore their unfoldability after an Opaque command. + See also: sections :ref:`performingcomputations`, :ref:`tactics-automatizing`, + :ref:`proof-editing-mode` -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. + .. exn:: The reference @qualid was not found in the current environment. -The scope of Transparent is limited to the current section, or current -file, unless the variant ``Global Transparent`` is -used. + There is no constant referred by :n:`@qualid` in the environment. + Nevertheless, if you asked :cmd:`Opaque` `foo` `bar` and if `bar` does + not exist, `foo` is set opaque. +.. cmd:: Transparent {+ @qualid } -Error messages: + This command is the converse of :cmd:`Opaque` and it applies on unfoldable + constants to restore their unfoldability after an Opaque command. + Note in particular that constants defined by a proof ended by Qed are + not unfoldable and Transparent has no effect on them. This is to keep + with the usual mathematical practice of *proof irrelevance*: what + matters in a mathematical development is the sequence of lemma + statements, not their actual proofs. This distinguishes lemmas from + the usual defined constants, whose actual values are of course + relevant in general. -.. exn:: The reference @qualid was not found in the current environment + .. cmdv:: Global Transparent {+ @qualid } + :name: Global Transparent -There is no constant referred by :n:`@qualid` in the environment. + The scope of Transparent is limited to the current section, or current + file, unless the variant :cmd:`Global Transparent` is + used. + .. exn:: The reference @qualid was not found in the current environment. + There is no constant referred by :n:`@qualid` in the environment. -See also: sections :ref:`TODO-8.7-performing-computations`, :ref:`TODO-8.16-automatizing`, :ref:`TODO-7.1-switching-on-off-proof-editing-mode` + See also: sections :ref:`performingcomputations`, + :ref:`tactics-automatizing`, :ref:`proof-editing-mode` +.. _vernac-strategy: -.. cmd:: Strategy @level [ {+ @qualid } ]. +.. 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. + 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): + 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). @@ -1322,52 +1160,42 @@ Levels can be one of the following (higher to lower): + ``expand`` : level of constants that should be expanded first (behaves like −∞) + .. cmdv:: Local Strategy @level [ {+ @qualid } ] -These directives survive section and module closure, unless the -command is prefixed by Local. In the latter case, the behavior -regarding sections and modules is the same as for the ``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. - - + These directives survive section and module closure, unless the + command is prefixed by ``Local``. In the latter case, the behavior + regarding sections and modules is the same as for the :cmd:`Transparent` and + :cmd:`Opaque` commands. -Variants: +.. cmd:: Print Strategy @qualid -.. cmdv:: Print Strategies. + 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. -Print all the currently non-transparent strategies. + .. exn:: The reference is not unfoldable. + .. cmdv:: Print Strategies + Print all the currently non-transparent strategies. -.. cmd:: Declare Reduction @ident := @convtactic. -This command allows giving a short name to a reduction expression, for -instance lazy beta delta [foo bar]. This short name can then be used -in ``Eval`` :n:`@ident` ``in`` ... or ``eval`` directives. This command -accepts the -Local modifier, for discarding this reduction name at the end of the -file or module. For the moment the name cannot be qualified. In -particular declaring the same name in several modules or in several -functor applications will be refused if these declarations are not -local. The name :n:`@ident` cannot be used directly as an Ltac tactic, but -nothing prevents the user to also perform a -``Ltac`` `ident` ``:=`` `convtactic`. +.. 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:`TODO-8.7-performing-computations` + See also: sections :ref:`performingcomputations` .. _controlling-locality-of-commands: @@ -1376,8 +1204,8 @@ Controlling the locality of commands ----------------------------------------- -.. cmd:: Local @command. -.. cmd:: Global @command. +.. 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: @@ -1386,29 +1214,29 @@ 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:`TODO-2.8-coercions`) and ``Strategy`` (see Section :ref:`TODO-6.10.3-strategy`) commands belong - to this category. + current section or module it occurs in. As an example, the :cmd:`Coercion` + and :cmd:`Strategy` commands belong to this category. + Commands whose default behavior is to stop their effect at the end - of the section they occur in but to extent their effect outside the - module or library file they occur in. For these commands, the Local - modifier limits the effect of the command to the current module if the - command does not occur in a section and the Global modifier extends - the effect outside the current sections and current module if the - command occurs in a section. As an example, the ``Implicit Arguments`` (see - Section :ref:`TODO-2.7-implicit-arguments`), Ltac (see Chapter :ref:`TODO-9-tactic-language`) or ``Notation`` (see Section - :ref:`TODO-12.1-notations`) 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. + of the section they occur in but to extent their effect outside the module or + library file they occur in. For these commands, the Local modifier limits the + effect of the command to the current module if the command does not occur in a + section and the Global modifier extends the effect outside the current + sections and current module if the command occurs in a section. As an example, + the :cmd:`Arguments`, :cmd:`Ltac` or :cmd:`Notation` commands belong + to this category. Notice that a subclass of these commands do not support + extension of their scope outside sections at all and the Global is not + applicable to them. + Commands whose default behavior is to stop their effect at the end - of the section or module they occur in. For these commands, the Global + 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:`TODO-6.10-opaque`) commands belong to this category. + occurs in. The :cmd:`Transparent` and :cmd:`Opaque` + (see Section :ref:`vernac-controlling-the-reduction-strategies`) commands + belong to this category. + Commands whose default behavior is to extend their effect outside sections but not outside modules when they occur in a section and to extend their effect outside the module or library file they occur in when no section contains them.For these commands, the Local modifier limits the effect to the current section or module while the Global modifier extends the effect outside the module even when the command - occurs in a section. The ``Set`` and ``Unset`` commands belong to this + occurs in a section. The :cmd:`Set` and :cmd:`Unset` commands belong to this category. |