diff options
Diffstat (limited to 'doc/sphinx')
43 files changed, 2939 insertions, 2600 deletions
diff --git a/doc/sphinx/README.rst b/doc/sphinx/README.rst index 0802b5d0b4..e20469bb8b 100644 --- a/doc/sphinx/README.rst +++ b/doc/sphinx/README.rst @@ -358,6 +358,13 @@ In addition to the objects and directives above, the ``coqrst`` Sphinx plugin de <http://www.sphinx-doc.org/en/stable/markup/para.html#directive-productionlist>`_ and reference its tokens using ``:token:`…```. +``:gdef:`` Marks the definition of a glossary term inline in the text. Matching :term:`XXX` + constructs will link to it. The term will also appear in the Glossary Index. + + Example:: + + A :gdef:`prime` number is divisible only by itself and 1. + Common mistakes =============== diff --git a/doc/sphinx/_static/notations.css b/doc/sphinx/_static/notations.css index 733a73bd21..9546f7107e 100644 --- a/doc/sphinx/_static/notations.css +++ b/doc/sphinx/_static/notations.css @@ -215,6 +215,14 @@ margin-bottom: 0.28em; } +.term-defn { + font-style: italic; +} + +.std-term { + color: #2980B9; /* override if :visited */ +} + /* We can't display nested blocks otherwise */ code, .rst-content tt, .rst-content code { background: transparent !important; diff --git a/doc/sphinx/_templates/versions.html b/doc/sphinx/_templates/versions.html new file mode 100644 index 0000000000..967d00d2bf --- /dev/null +++ b/doc/sphinx/_templates/versions.html @@ -0,0 +1,48 @@ +{# Forked from versions.html in sphinx_rtd_theme 0.4.3 #} + +{# +The MIT License (MIT) + +Copyright (c) 2013-2018 Dave Snider, Read the Docs, Inc. & contributors + +Permission is hereby granted, free of charge, to any person obtaining a copy of +this software and associated documentation files (the "Software"), to deal in +the Software without restriction, including without limitation the rights to +use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software is furnished to do so, +subject to the following conditions: + +The above copyright notice and this permission notice shall be included in all +copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS +FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR +COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER +IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN +CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. +#} + +{% if not READTHEDOCS %} + <div class="rst-versions" data-toggle="rst-versions" role="note" aria-label="versions"> + <span class="rst-current-version" data-toggle="rst-current-version"> + <span class="fa fa-book"> Other versions</span> + v: {{ version }} + <span class="fa fa-caret-down"></span> + </span> + <div class="rst-other-versions"> + <dl> + <dt>{{ _('Versions') }}</dt> + {% for slug, url in versions %} + <dd><a href="{{ url }}">{{ slug }}</a></dd> + {% endfor %} + </dl> + <dl> + <dt>{{ _('Downloads') }}</dt> + {% for type, url in downloads %} + <dd><a href="{{ url }}">{{ type }}</a></dd> + {% endfor %} + </dl> + </div> + </div> +{% endif %} diff --git a/doc/sphinx/addendum/generalized-rewriting.rst b/doc/sphinx/addendum/generalized-rewriting.rst index 315c9d4a80..759f630b85 100644 --- a/doc/sphinx/addendum/generalized-rewriting.rst +++ b/doc/sphinx/addendum/generalized-rewriting.rst @@ -529,7 +529,7 @@ pass additional arguments such as ``using relation``. setoid_symmetry {? in @ident} setoid_transitivity setoid_rewrite {? @orientation} @term {? at @occurrences} {? in @ident} - setoid_replace @term with @term {? using relation @term} {? in @ident} {? by @tactic} + setoid_replace @term with @term {? using relation @term} {? in @ident} {? by @ltac_expr3} :name: setoid_reflexivity; setoid_symmetry; setoid_transitivity; setoid_rewrite; setoid_replace The ``using relation`` arguments cannot be passed to the unprefixed form. diff --git a/doc/sphinx/addendum/implicit-coercions.rst b/doc/sphinx/addendum/implicit-coercions.rst index 1f33775a01..a6dc15da55 100644 --- a/doc/sphinx/addendum/implicit-coercions.rst +++ b/doc/sphinx/addendum/implicit-coercions.rst @@ -37,6 +37,8 @@ In addition to these user-defined classes, we have two built-in classes: * ``Funclass``, the class of functions; its objects are all the terms with a functional type, i.e. of form :g:`forall x:A,B`. +Formally, the syntax of classes is defined as: + .. insertprodn class class .. prodn:: @@ -257,7 +259,7 @@ Activating the Printing of Coercions :name: Printing Coercion Specifies a set of qualids for which coercions are always displayed. Use the - :cmd:`Add @table` and :cmd:`Remove @table` commands to update the set of qualids. + :cmd:`Add` and :cmd:`Remove` commands to update the set of qualids. .. _coercions-classes-as-records: diff --git a/doc/sphinx/addendum/micromega.rst b/doc/sphinx/addendum/micromega.rst index f706633da9..77bf58aac6 100644 --- a/doc/sphinx/addendum/micromega.rst +++ b/doc/sphinx/addendum/micromega.rst @@ -1,4 +1,4 @@ -.. _ micromega: +.. _micromega: Micromega: tactics for solving arithmetic goals over ordered rings ================================================================== diff --git a/doc/sphinx/addendum/omega.rst b/doc/sphinx/addendum/omega.rst index daca43e65e..e1b1ee8e8d 100644 --- a/doc/sphinx/addendum/omega.rst +++ b/doc/sphinx/addendum/omega.rst @@ -1,4 +1,4 @@ -.. _omega: +.. _omega_chapter: Omega: a solver for quantifier-free problems in Presburger Arithmetic ===================================================================== @@ -7,20 +7,18 @@ Omega: a solver for quantifier-free problems in Presburger Arithmetic .. warning:: - The :tacn:`omega` tactic is about to be deprecated in favor of the - :tacn:`lia` tactic. The goal is to consolidate the arithmetic - solving capabilities of Coq into a single engine; moreover, - :tacn:`lia` is in general more powerful than :tacn:`omega` (it is a - complete Presburger arithmetic solver while :tacn:`omega` was known - to be incomplete). - - Work is in progress to make sure that there are no regressions - (including no performance regression) when switching from - :tacn:`omega` to :tacn:`lia` in existing projects. However, we - already recommend using :tacn:`lia` in new or refactored proof - scripts. We also ask that you report (in our `bug tracker - <https://github.com/coq/coq/issues>`_) any issue you encounter, - especially if the issue was not present in :tacn:`omega`. + The :tacn:`omega` tactic is deprecated in favor of the :tacn:`lia` + tactic. The goal is to consolidate the arithmetic solving + capabilities of Coq into a single engine; moreover, :tacn:`lia` is + in general more powerful than :tacn:`omega` (it is a complete + Presburger arithmetic solver while :tacn:`omega` was known to be + incomplete). + + It is recommended to switch from :tacn:`omega` to :tacn:`lia` in existing + projects. We also ask that you report (in our `bug tracker + <https://github.com/coq/coq/issues>`_) any issue you encounter, especially + if the issue was not present in :tacn:`omega`. If no new issues are + reported, :tacn:`omega` will be removed soon. Note that replacing :tacn:`omega` with :tacn:`lia` can break non-robust proof scripts which rely on incompleteness bugs of @@ -30,6 +28,11 @@ Description of ``omega`` ------------------------ .. tacn:: omega + :name: omega + + .. deprecated:: 8.12 + + Use :tacn:`lia` instead. :tacn:`omega` is a tactic for solving goals in Presburger arithmetic, i.e. for proving formulas made of equations and inequalities over the @@ -118,7 +121,7 @@ loaded by .. example:: - .. coqtop:: all + .. coqtop:: all warn Require Import Omega. diff --git a/doc/sphinx/addendum/program.rst b/doc/sphinx/addendum/program.rst index d09f23edb6..b5618c5721 100644 --- a/doc/sphinx/addendum/program.rst +++ b/doc/sphinx/addendum/program.rst @@ -290,7 +290,7 @@ optional identifier is used when multiple functions have unsolved obligations (e.g. when defining mutually recursive blocks). The optional tactic is replaced by the default one if not specified. -.. cmd:: {? {| Local | Global } } Obligation Tactic := @tactic +.. cmd:: {? {| Local | Global } } Obligation Tactic := @ltac_expr :name: Obligation Tactic Sets the default obligation solving tactic applied to all obligations @@ -314,11 +314,11 @@ optional tactic is replaced by the default one if not specified. Start the proof of the next unsolved obligation. -.. cmd:: Solve Obligations {? {? of @ident} with @tactic} +.. cmd:: Solve Obligations {? {? of @ident} with @ltac_expr} Tries to solve each obligation of ``ident`` using the given ``tactic`` or the default one. -.. cmd:: Solve All Obligations {? with @tactic} +.. cmd:: Solve All Obligations {? with @ltac_expr} Tries to solve each obligation of every program using the given tactic or the default one (useful for mutually recursive definitions). diff --git a/doc/sphinx/addendum/sprop.rst b/doc/sphinx/addendum/sprop.rst index 9acdd18b89..b19239ed22 100644 --- a/doc/sphinx/addendum/sprop.rst +++ b/doc/sphinx/addendum/sprop.rst @@ -7,27 +7,26 @@ SProp (proof irrelevant propositions) The status of strict propositions is experimental. + In particular, conversion checking through bytecode or native code + compilation currently does not understand proof irrelevance. + This section describes the extension of |Coq| with definitionally proof irrelevant propositions (types in the sort :math:`\SProp`, also known as strict propositions) as described in :cite:`Gilbert:POPL2019`. -Using :math:`\SProp` may be prevented by passing ``-disallow-sprop`` -to the |Coq| program or using :flag:`Allow StrictProp`. +Use of |SProp| may be disabled by passing ``-disallow-sprop`` to the +|Coq| program or by turning the :flag:`Allow StrictProp` flag off. .. flag:: Allow StrictProp :name: Allow StrictProp - Allows using :math:`\SProp` when set and forbids it when unset. The - initial value depends on whether you used the command line - ``-disallow-sprop`` and ``-allow-sprop``. - -.. exn:: SProp not allowed, you need to Set Allow StrictProp or to use the -allow-sprop command-line-flag. - :undocumented: - -.. coqtop:: none + Enables or disables the use of |SProp|. It is enabled by default. + The command-line flag ``-disallow-sprop`` disables |SProp| at + startup. - Set Allow StrictProp. + .. exn:: SProp is disallowed because the "Allow StrictProp" flag is off. + :undocumented: Some of the definitions described in this document are available through ``Coq.Logic.StrictProp``, which see. @@ -38,29 +37,35 @@ Basic constructs The purpose of :math:`\SProp` is to provide types where all elements are convertible: -.. coqdoc:: +.. coqtop:: all - Definition irrelevance (A:SProp) (P:A -> Prop) (x:A) (v:P x) (y:A) : P y := v. + Theorem irrelevance (A : SProp) (P : A -> Prop) : forall x : A, P x -> forall y : A, P y. + Proof. + intros * Hx *. + exact Hx. + Qed. Since we have definitional :ref:`eta-expansion` for functions, the property of being a type of definitionally irrelevant values is impredicative, and so is :math:`\SProp`: -.. coqdoc:: +.. coqtop:: all Check fun (A:Type) (B:A -> SProp) => (forall x:A, B x) : SProp. -.. warning:: - - Conversion checking through bytecode or native code compilation - currently does not understand proof irrelevance. - In order to keep conversion tractable, cumulativity for :math:`\SProp` -is forbidden: +is forbidden, unless the :flag:`Cumulative StrictProp` flag is turned +on: .. coqtop:: all Fail Check (fun (A:SProp) => A : Type). + Set Cumulative StrictProp. + Check (fun (A:SProp) => A : Type). + +.. coqtop:: none + + Unset Cumulative StrictProp. We can explicitly lift strict propositions into the relevant world by using a wrapping inductive type. The inductive stops definitional @@ -240,3 +245,10 @@ so correctly converts ``x`` and ``y``. the kernel when it is passed a term with incorrect relevance marks. To avoid conversion issues as in ``late_mark`` you may wish to use it to find when your tactics are producing incorrect marks. + +.. flag:: Cumulative StrictProp + :name: Cumulative StrictProp + + Set this flag (it is off by default) to make the kernel accept + cumulativity between |SProp| and other universes. This makes + typechecking incomplete. diff --git a/doc/sphinx/addendum/type-classes.rst b/doc/sphinx/addendum/type-classes.rst index bd4c276571..903aa266e2 100644 --- a/doc/sphinx/addendum/type-classes.rst +++ b/doc/sphinx/addendum/type-classes.rst @@ -241,7 +241,7 @@ binders. For example: Definition lt `{eqa : EqDec A, ! Ord eqa} (x y : A) := andb (le x y) (neqb x y). -The ``!`` modifier switches the way a binder is parsed back to the regular +The ``!`` modifier switches the way a binder is parsed back to the usual interpretation of Coq. In particular, it uses the implicit arguments mechanism if available, as shown in the example. @@ -323,7 +323,7 @@ Summary of the commands .. cmdv:: Existing Class @ident - This variant declares a class a posteriori from a constant or + This variant declares a class from a previously declared constant or inductive definition. No methods or instances are defined. .. warn:: @ident is already declared as a typeclass @@ -394,7 +394,7 @@ few other commands related to typeclasses. :name: typeclasses eauto This proof search tactic implements the resolution engine that is run - implicitly during type-checking. This tactic uses a different resolution + implicitly during type checking. This tactic uses a different resolution engine than :tacn:`eauto` and :tacn:`auto`. The main differences are the following: diff --git a/doc/sphinx/addendum/universe-polymorphism.rst b/doc/sphinx/addendum/universe-polymorphism.rst index a08495badd..2958d866ac 100644 --- a/doc/sphinx/addendum/universe-polymorphism.rst +++ b/doc/sphinx/addendum/universe-polymorphism.rst @@ -227,7 +227,7 @@ constraints by prefixing the level names with symbols. Because inductive subtypings are only produced by comparing inductives to themselves with universes changed, they amount to variance information: each universe is either invariant, covariant or -irrelevant (there are no contravariant subtypings in Coq), +irrelevant (there are no contravariant subtypings in |Coq|), respectively represented by the symbols `=`, `+` and `*`. Here we see that :g:`list` binds an irrelevant universe, so any two @@ -426,6 +426,19 @@ mode, introduced universe names can be referred to in terms. Note that local universe names shadow global universe names. During a proof, one can use :cmd:`Show Universes` to display the current context of universes. +It is possible to provide only some universe levels and let |Coq| infer the others +by adding a :g:`+` in the list of bound universe levels: + +.. coqtop:: all + + Fail Definition foobar@{u} : Type@{u} := Type. + Definition foobar@{u +} : Type@{u} := Type. + Set Printing Universes. + Print foobar. + +This can be used to find which universes need to be explicitly bound in a given +definition. + Definitions can also be instantiated explicitly, giving their full instance: diff --git a/doc/sphinx/appendix/indexes/index.rst b/doc/sphinx/appendix/indexes/index.rst index 2ece726df7..7dd0f62a9f 100644 --- a/doc/sphinx/appendix/indexes/index.rst +++ b/doc/sphinx/appendix/indexes/index.rst @@ -11,16 +11,17 @@ find what you are looking for. .. toctree:: - ../../genindex + ../../std-glossindex ../../coq-cmdindex ../../coq-tacindex + ../../coq-attrindex ../../coq-optindex ../../coq-exnindex - ../../coq-attrindex + ../../genindex For reference, here are direct links to the documentation of: -- :ref:`flags, options and tables <flags-options-tables>`; +- :ref:`attributes` +- :ref:`flags-options-tables`; - controlling the display of warning messages with the :opt:`Warnings` option; -- :ref:`gallina-attributes`. diff --git a/doc/sphinx/changes.rst b/doc/sphinx/changes.rst index 31fb1b7382..453b8597f9 100644 --- a/doc/sphinx/changes.rst +++ b/doc/sphinx/changes.rst @@ -55,7 +55,8 @@ __ 811Reals_ Additionally, while the :tacn:`omega` tactic is not yet deprecated in this version of Coq, it should soon be the case and we already recommend users to switch to :tacn:`lia` in new proof scripts (see -also the warning message in the :ref:`corresponding chapter <omega>`). +also the warning message in the :ref:`corresponding chapter +<omega_chapter>`). The ``dev/doc/critical-bugs`` file documents the known critical bugs of |Coq| and affected releases. See the `Changes in 8.11+beta1`_ @@ -326,7 +327,7 @@ Changes in 8.11+beta1 the documentation by Théo Zimmermann and Jim Fehrle). - **Added:** Ltac2 tactic notations with “constr” arguments can specify the - interpretation scope for these arguments; + notation scope for these arguments; see :ref:`ltac2_notations` for details (`#10289 <https://github.com/coq/coq/pull/10289>`_, by Vincent Laporte). @@ -481,10 +482,12 @@ Changes in 8.11+beta1 .. _811Reals: - **Added:** - Module `Reals.ConstructiveCauchyReals` defines constructive real numbers + Module `Reals.Cauchy.ConstructiveCauchyReals` defines constructive real numbers by Cauchy sequences of rational numbers (`#10445 <https://github.com/coq/coq/pull/10445>`_, by Vincent Semeria, with the help and review of Guillaume Melquiond and Bas Spitters). + This module is not meant to be imported directly, please import + `Reals.Abstract.ConstructiveReals` instead. - **Added:** New module `Reals.ClassicalDedekindReals` defines Dedekind real numbers as boolean-valued functions along with 3 logical axioms: @@ -1556,14 +1559,13 @@ changes: - Vernacular: - - Experimental support for :ref:`attributes <gallina-attributes>` on + - Experimental support for :term:`attributes <attribute>` on commands, by Vincent Laporte, as in ``#[local] Lemma foo : bar.`` Tactics and tactic notations now support the ``deprecated`` attribute. - Removed deprecated commands ``Arguments Scope`` and ``Implicit - Arguments`` in favor of :cmd:`Arguments (scopes)` and - :cmd:`Arguments`, with the help of Jasper Hugunin. + Arguments`` in favor of :cmd:`Arguments`, with the help of Jasper Hugunin. - New flag :flag:`Uniform Inductive Parameters` by Jasper Hugunin to avoid repeating uniform parameters in constructor declarations. @@ -2401,9 +2403,9 @@ Tactics - Tactic "auto with real" can now discharge comparisons of literals. - The types of variables in patterns of "match" are now - beta-iota-reduced after type-checking. This has an impact on the + beta-iota-reduced after type checking. This has an impact on the type of the variables that the tactic "refine" introduces in the - context, producing types a priori closer to the expectations. + context, producing types that should be closer to the expectations. - In "Tactic Notation" or "TACTIC EXTEND", entry "constr_with_bindings" now uses type classes and rejects terms with unresolved holes, like @@ -3469,7 +3471,7 @@ Tactics native_compute now strictly interpret it as the head of a pattern starting with this reference. -- The "change p with c" tactic semantics changed, now type-checking +- The "change p with c" tactic semantics changed, now type checking "c" at each matching occurrence "t" of the pattern "p", and converting "t" with "c". @@ -4836,7 +4838,7 @@ Type classes - Declaring axiomatic type class instances in Module Type should be now done via new command "Declare Instance", while the syntax "Instance" now always provides a concrete instance, both in and out of Module Type. -- Use [Existing Class foo] to declare foo as a class a posteriori. +- Use [Existing Class foo] to declare a preexisting object [foo] as a class. [foo] can be an inductive type or a constant definition. No projections or instances are defined. - Various bug fixes and improvements: support for defined fields, @@ -4846,7 +4848,7 @@ Type classes Vernacular commands - New command "Timeout <n> <command>." interprets a command and a timeout - interrupts the interpretation after <n> seconds. + interrupts the execution after <n> seconds. - New command "Compute <expr>." is a shortcut for "Eval vm_compute in <expr>". - New command "Fail <command>." interprets a command and is successful iff the command fails on an error (but not an anomaly). Handy for tests and @@ -6031,7 +6033,7 @@ main motivations were syntax. Together with the revision of the concrete syntax, a new mechanism of -*interpretation scopes* permits to reuse the same symbols (typically +, +*notation scopes* permits to reuse the same symbols (typically +, -, \*, /, <, <=) in various mathematical theories without any ambiguities for |Coq|, leading to a largely improved readability of |Coq| scripts. New commands to easily add new symbols are also provided. @@ -6069,7 +6071,7 @@ translator from old to new syntax released with |Coq| is also their work with contributions by Olivier Desmettre. Hugo Herbelin is the main designer and implementer of the notion of -interpretation scopes and of the commands for easily adding new +notation scopes and of the commands for easily adding new notations. Hugo Herbelin is the main implementer of the restructured standard library. @@ -6291,12 +6293,12 @@ Syntax extensions - "Grammar" for terms disappears - "Grammar" for tactics becomes "Tactic Notation" - "Syntax" disappears -- Introduction of a notion of interpretation scope allowing to use the +- Introduction of a notion of notation scope allowing to use the same notations in various contexts without using specific delimiters (e.g the same expression "4<=3+x" is interpreted either in "nat", "positive", "N" (previously "entier"), "Z", "R", depending on which - interpretation scope is currently open) [see documentation for details] -- Notation now mandatorily requires a precedence and associativity + Notation scope is currently open) [see documentation for details] +- Notation now requires a precedence and associativity (default was to set precedence to 1 and associativity to none) Revision of the standard library @@ -6373,7 +6375,7 @@ New syntax with no dependency of t1 and t2 in the arguments of the constructors; this may cause incompatibilities for files translated using coq 8.0beta -Interpretation scopes +Notation scopes - Delimiting key %bool for bool_scope added - Import no more needed to activate argument scopes from a module diff --git a/doc/sphinx/conf.py b/doc/sphinx/conf.py index 2ed9ec21b3..4136b406de 100755 --- a/doc/sphinx/conf.py +++ b/doc/sphinx/conf.py @@ -183,18 +183,10 @@ todo_include_todos = False nitpicky = True nitpick_ignore = [ ('token', token) for token in [ - 'assums', 'binders', 'collection', - 'dirpath', - 'ind_body', 'modpath', - 'module', - 'simple_tactic', - 'symbol', - 'term_pattern', - 'term_pattern_string', - 'toplevel_selector', + 'tactic', ]] # -- Options for HTML output ---------------------------------------------- @@ -210,6 +202,7 @@ html_theme = 'sphinx_rtd_theme' # Theme options are theme-specific and customize the look and feel of a theme # further. For a list of options available for each theme, see the # documentation. +PDF_URL = "https://github.com/coq/coq/releases/download/V{version}/coq-{version}-reference-manual.pdf" html_theme_options = { 'collapse_navigation': False } @@ -218,7 +211,26 @@ html_context = { 'github_user': 'coq', 'github_repo': 'coq', 'github_version': 'master', - 'conf_py_path': '/doc/sphinx/' + 'conf_py_path': '/doc/sphinx/', + # Versions and downloads listed in the versions menu (see _templates/versions.html) + 'versions': [ + ("master", "https://coq.github.io/doc/master/refman/"), + ("stable", "https://coq.inria.fr/distrib/current/refman/"), + ("v8.11", "https://coq.github.io/doc/v8.11/refman/"), + ("v8.10", "https://coq.github.io/doc/v8.10/refman/"), + ("v8.9", "https://coq.github.io/doc/v8.9/refman/"), + ("8.8", "https://coq.inria.fr/distrib/V8.8.2/refman/"), + ("8.7", "https://coq.inria.fr/distrib/V8.7.2/refman/"), + ("8.6", "https://coq.inria.fr/distrib/V8.6.1/refman/"), + ("8.5", "https://coq.inria.fr/distrib/V8.5pl3/refman/"), + ("8.4", "https://coq.inria.fr/distrib/V8.4pl6/refman/"), + ("8.3", "https://coq.inria.fr/distrib/V8.3pl5/refman/"), + ("8.2", "https://coq.inria.fr/distrib/V8.2pl3/refman/"), + ("8.1", "https://coq.inria.fr/distrib/V8.1pl6/refman/"), + ("8.0", "https://coq.inria.fr/distrib/V8.0/doc/") + ], + 'downloads': ([("PDF", PDF_URL.format(version=version))] + if coq_config.is_a_released_version else []) } # Add any paths that contain custom themes here, relative to this directory. diff --git a/doc/sphinx/coq-attrindex.rst b/doc/sphinx/coq-attrindex.rst index f2ace20374..a0c8bba90d 100644 --- a/doc/sphinx/coq-attrindex.rst +++ b/doc/sphinx/coq-attrindex.rst @@ -1,5 +1,9 @@ :orphan: +.. hack to get index in TOC + +.. _attribute_index: + --------------- Attribute index --------------- diff --git a/doc/sphinx/coq-optindex.rst b/doc/sphinx/coq-optindex.rst index 0961bea61f..e03b2abc32 100644 --- a/doc/sphinx/coq-optindex.rst +++ b/doc/sphinx/coq-optindex.rst @@ -2,6 +2,8 @@ .. hack to get index in TOC +.. _options_index: + ------------------------------- Flags, options and tables index ------------------------------- diff --git a/doc/sphinx/coqdoc.css b/doc/sphinx/coqdoc.css deleted file mode 100644 index a325a33842..0000000000 --- a/doc/sphinx/coqdoc.css +++ /dev/null @@ -1,338 +0,0 @@ -/************************************************************************/ -/* * The Coq Proof Assistant / The Coq Development Team */ -/* v * Copyright INRIA, CNRS and contributors */ -/* <O___,, * (see version control and CREDITS file for authors & dates) */ -/* \VV/ **************************************************************/ -/* // * This file is distributed under the terms of the */ -/* * GNU Lesser General Public License Version 2.1 */ -/* * (see LICENSE file for the text of the license) */ -/************************************************************************/ -body { padding: 0px 0px; - margin: 0px 0px; - background-color: white } - -#page { display: block; - padding: 0px; - margin: 0px; - padding-bottom: 10px; } - -#header { display: block; - position: relative; - padding: 0; - margin: 0; - vertical-align: middle; - border-bottom-style: solid; - border-width: thin } - -#header h1 { padding: 0; - margin: 0;} - - -/* Contents */ - -#main{ display: block; - padding: 10px; - font-family: sans-serif; - font-size: 100%; - line-height: 100% } - -#main h1 { line-height: 95% } /* allow for multi-line headers */ - -#main a.idref:visited {color : #416DFF; text-decoration : none; } -#main a.idref:link {color : #416DFF; text-decoration : none; } -#main a.idref:hover {text-decoration : none; } -#main a.idref:active {text-decoration : none; } - -#main a.modref:visited {color : #416DFF; text-decoration : none; } -#main a.modref:link {color : #416DFF; text-decoration : none; } -#main a.modref:hover {text-decoration : none; } -#main a.modref:active {text-decoration : none; } - -#main .keyword { color : #cf1d1d } -#main { color: black } - -.section { background-color: rgb(60%,60%,100%); - padding-top: 13px; - padding-bottom: 13px; - padding-left: 3px; - margin-top: 5px; - margin-bottom: 5px; - font-size : 175% } - -h2.section { background-color: rgb(80%,80%,100%); - padding-left: 3px; - padding-top: 12px; - padding-bottom: 10px; - font-size : 130% } - -h3.section { background-color: rgb(90%,90%,100%); - padding-left: 3px; - padding-top: 7px; - padding-bottom: 7px; - font-size : 115% } - -h4.section { -/* - background-color: rgb(80%,80%,80%); - max-width: 20em; - padding-left: 5px; - padding-top: 5px; - padding-bottom: 5px; -*/ - background-color: white; - padding-left: 0px; - padding-top: 0px; - padding-bottom: 0px; - font-size : 100%; - font-weight : bold; - text-decoration : underline; - } - -#main .doc { margin: 0px; - font-family: sans-serif; - font-size: 100%; - line-height: 125%; - max-width: 40em; - color: black; - padding: 10px; - background-color: #90bdff } - -.inlinecode { - display: inline; -/* font-size: 125%; */ - color: #666666; - font-family: monospace } - -.doc .inlinecode { - display: inline; - font-size: 120%; - color: rgb(30%,30%,70%); - font-family: monospace } - -.doc .inlinecode .id { - color: rgb(30%,30%,70%); -} - -.inlinecodenm { - display: inline; - color: #444444; -} - -.doc .code { - display: inline; - font-size: 120%; - color: rgb(30%,30%,70%); - font-family: monospace } - -.comment { - display: inline; - font-family: monospace; - color: rgb(50%,50%,80%); -} - -.code { - display: block; -/* padding-left: 15px; */ - font-size: 110%; - font-family: monospace; - } - -table.infrule { - border: 0px; - margin-left: 50px; - margin-top: 10px; - margin-bottom: 10px; -} - -td.infrule { - font-family: monospace; - text-align: center; -/* color: rgb(35%,35%,70%); */ - padding: 0px; - line-height: 100%; -} - -tr.infrulemiddle hr { - margin: 1px 0 1px 0; -} - -.infrulenamecol { - color: rgb(60%,60%,60%); - font-size: 80%; - padding-left: 1em; - padding-bottom: 0.1em -} - -/* Pied de page */ - -#footer { font-size: 65%; - font-family: sans-serif; } - -/* Identifiers: <span class="id" title="...">) */ - -.id { display: inline; } - -.id[title="constructor"] { - color: rgb(60%,0%,0%); -} - -.id[title="var"] { - color: rgb(40%,0%,40%); -} - -.id[title="variable"] { - color: rgb(40%,0%,40%); -} - -.id[title="definition"] { - color: rgb(0%,40%,0%); -} - -.id[title="abbreviation"] { - color: rgb(0%,40%,0%); -} - -.id[title="lemma"] { - color: rgb(0%,40%,0%); -} - -.id[title="instance"] { - color: rgb(0%,40%,0%); -} - -.id[title="projection"] { - color: rgb(0%,40%,0%); -} - -.id[title="method"] { - color: rgb(0%,40%,0%); -} - -.id[title="inductive"] { - color: rgb(0%,0%,80%); -} - -.id[title="record"] { - color: rgb(0%,0%,80%); -} - -.id[title="class"] { - color: rgb(0%,0%,80%); -} - -.id[title="keyword"] { - color : #cf1d1d; -/* color: black; */ -} - -/* Deprecated rules using the 'type' attribute of <span> (not xhtml valid) */ - -.id[type="constructor"] { - color: rgb(60%,0%,0%); -} - -.id[type="var"] { - color: rgb(40%,0%,40%); -} - -.id[type="variable"] { - color: rgb(40%,0%,40%); -} - -.id[type="definition"] { - color: rgb(0%,40%,0%); -} - -.id[type="abbreviation"] { - color: rgb(0%,40%,0%); -} - -.id[type="lemma"] { - color: rgb(0%,40%,0%); -} - -.id[type="instance"] { - color: rgb(0%,40%,0%); -} - -.id[type="projection"] { - color: rgb(0%,40%,0%); -} - -.id[type="method"] { - color: rgb(0%,40%,0%); -} - -.id[type="inductive"] { - color: rgb(0%,0%,80%); -} - -.id[type="record"] { - color: rgb(0%,0%,80%); -} - -.id[type="class"] { - color: rgb(0%,0%,80%); -} - -.id[type="keyword"] { - color : #cf1d1d; -/* color: black; */ -} - -.inlinecode .id { - color: rgb(0%,0%,0%); -} - - -/* TOC */ - -#toc h2 { - padding: 10px; - background-color: rgb(60%,60%,100%); -} - -#toc li { - padding-bottom: 8px; -} - -/* Index */ - -#index { - margin: 0; - padding: 0; - width: 100%; -} - -#index #frontispiece { - margin: 1em auto; - padding: 1em; - width: 60%; -} - -.booktitle { font-size : 140% } -.authors { font-size : 90%; - line-height: 115%; } -.moreauthors { font-size : 60% } - -#index #entrance { - text-align: center; -} - -#index #entrance .spacer { - margin: 0 30px 0 30px; -} - -#index #footer { - position: absolute; - bottom: 0; -} - -.paragraph { - height: 0.75em; -} - -ul.doclist { - margin-top: 0em; - margin-bottom: 0em; -} diff --git a/doc/sphinx/history.rst b/doc/sphinx/history.rst index 153dc1f368..02821613cc 100644 --- a/doc/sphinx/history.rst +++ b/doc/sphinx/history.rst @@ -210,7 +210,7 @@ definitions of “inversion predicates”. Version 1 ~~~~~~~~~ -This software is a prototype type-checker for a higher-order logical +This software is a prototype type checker for a higher-order logical formalism known as the Theory of Constructions, presented in his PhD thesis by Thierry Coquand, with influences from Girard's system F and de Bruijn's Automath. The metamathematical analysis of the system is @@ -409,7 +409,7 @@ synthesized with the help of tactics, it was entirely re-checked by the engine. Thus there was no need to certify the tactics, and the system took advantage of this fact by having tactics ignore the universe levels, universe consistency check being relegated to the -final type-checking pass. This induced a certain puzzlement in early +final type checking pass. This induced a certain puzzlement in early users who saw, after a successful proof search, their ``QED`` followed by silence, followed by a failure message due to a universe inconsistency… @@ -1396,7 +1396,7 @@ Tactics Extraction (See details in plugins/extraction/CHANGES and README): - An experimental Scheme extraction is provided. -- Concerning Ocaml, extracted code is now ensured to always type-check, +- Concerning OCaml, extracted code is now ensured to always type check, thanks to automatic inserting of Obj.magic. - Experimental extraction of Coq new modules to Ocaml modules. diff --git a/doc/sphinx/language/cic.rst b/doc/sphinx/language/cic.rst index 09a3897a06..b125d21a3c 100644 --- a/doc/sphinx/language/cic.rst +++ b/doc/sphinx/language/cic.rst @@ -24,9 +24,9 @@ to a type and takes the form “*for all x of type* :math:`T`, :math:`P`”. The “:math:`x` *of type* :math:`T`” is written “:math:`x:T`”. Informally, “:math:`x:T`” can be thought as “:math:`x` *belongs to* :math:`T`”. -The types of types are *sorts*. Types and sorts are themselves terms +The types of types are called :gdef:`sort`\s. Types and sorts are themselves terms so that terms, types and sorts are all components of a common -syntactic language of terms which is described in Section :ref:`terms` but, +syntactic language of terms which is described in Section :ref:`terms`. But first, we describe sorts. @@ -1108,6 +1108,75 @@ between universes for inductive types in the Type hierarchy. Check infinite_loop (lam (@id Lam)) : False. +.. example:: Non strictly positive occurrence + + It is less obvious why inductive type definitions with occurences + that are positive but not strictly positive are harmful. + We will see that in presence of an impredicative type they + are unsound: + + .. coqtop:: all + + Fail Inductive A: Type := introA: ((A -> Prop) -> Prop) -> A. + + If we were to accept this definition we could derive a contradiction + by creating an injective function from :math:`A → \Prop` to :math:`A`. + + This function is defined by composing the injective constructor of + the type :math:`A` with the function :math:`λx. λz. z = x` injecting + any type :math:`T` into :math:`T → \Prop`. + + .. coqtop:: none + + Unset Positivity Checking. + Inductive A: Type := introA: ((A -> Prop) -> Prop) -> A. + Set Positivity Checking. + + .. coqtop:: all + + Definition f (x: A -> Prop): A := introA (fun z => z = x). + + .. coqtop:: in + + Lemma f_inj: forall x y, f x = f y -> x = y. + Proof. + unfold f; intros ? ? H; injection H. + set (F := fun z => z = y); intro HF. + symmetry; replace (y = x) with (F y). + + unfold F; reflexivity. + + rewrite <- HF; reflexivity. + Qed. + + The type :math:`A → \Prop` can be understood as the powerset + of the type :math:`A`. To derive a contradiction from the + injective function :math:`f` we use Cantor's classic diagonal + argument. + + .. coqtop:: all + + Definition d: A -> Prop := fun x => exists s, x = f s /\ ~s x. + Definition fd: A := f d. + + .. coqtop:: in + + Lemma cantor: (d fd) <-> ~(d fd). + Proof. + split. + + intros [s [H1 H2]]; unfold fd in H1. + replace d with s. + * assumption. + * apply f_inj; congruence. + + intro; exists d; tauto. + Qed. + + Lemma bad: False. + Proof. + pose cantor; tauto. + Qed. + + This derivation was first presented by Thierry Coquand and Christine + Paulin in :cite:`CP90`. + .. _Template-polymorphism: Template polymorphism diff --git a/doc/sphinx/language/core/basic.rst b/doc/sphinx/language/core/basic.rst new file mode 100644 index 0000000000..9473cc5a15 --- /dev/null +++ b/doc/sphinx/language/core/basic.rst @@ -0,0 +1,520 @@ +============================= +Basic notions and conventions +============================= + +This section provides some essential notions and conventions for reading +the manual. + +We start by explaining the syntax and lexical conventions used in the +manual. Then, we present the essential vocabulary necessary to read +the rest of the manual. Other terms are defined throughout the manual. +The reader may refer to the :ref:`glossary index <glossary_index>` +for a complete list of defined terms. Finally, we describe the various types of +settings that |Coq| provides. + +Syntax and lexical conventions +------------------------------ + +Syntax conventions +~~~~~~~~~~~~~~~~~~ + +The syntax described in this documentation is equivalent to that +accepted by the |Coq| parser, but the grammar has been edited +to improve readability and presentation. + +In the grammar presented in this manual, the terminal symbols are +black (e.g. :n:`forall`), whereas the nonterminals are green, italic +and hyperlinked (e.g. :n:`@term`). Some syntax is represented +graphically using the following kinds of blocks: + +:n:`{? item }` + An optional item. + +:n:`{+ item }` + A list of one or more items. + +:n:`{* item }` + An optional list of items. + +:n:`{+s item}` + A list of one or more items separated by "s" (e.g. :n:`item__1 s item__2 s item__3`). + +:n:`{*s item}` + An optional list of items separated by "s". + +:n:`{| item__1 | item__2 | ... }` + Alternatives (either :n:`item__1` or :n:`item__2` or ...). + +`Precedence levels +<https://en.wikipedia.org/wiki/Order_of_operations>`_ that are +implemented in the |Coq| parser are shown in the documentation by +appending the level to the nonterminal name (as in :n:`@term100` or +:n:`@ltac_expr3`). + +.. note:: + + |Coq| uses an extensible parser. Plugins and the :ref:`notation + system <syntax-extensions-and-notation-scopes>` can extend the + syntax at run time. Some notations are defined in the prelude, + which is loaded by default. The documented grammar doesn't include + these notations. Precedence levels not used by the base grammar + are omitted from the documentation, even though they could still be + populated by notations or plugins. + + Furthermore, some parsing rules are only activated in certain + contexts (:ref:`interactive proof mode <proofhandling>`, + :ref:`custom entries <custom-entries>`...). + +.. warning:: + + Given the complexity of these parsing rules, it would be extremely + difficult to create an external program that can properly parse a + |Coq| document. Therefore, tool writers are advised to delegate + parsing to |Coq|, by communicating with it, for instance through + `SerAPI <https://github.com/ejgallego/coq-serapi>`_. + +.. seealso:: :cmd:`Print Grammar` + +.. _lexical-conventions: + +Lexical conventions +~~~~~~~~~~~~~~~~~~~ + +Blanks + Space, newline and horizontal tab are considered blanks. + Blanks are ignored but they separate tokens. + +Comments + Comments are enclosed between ``(*`` and ``*)``. They can be nested. + They can contain any character. However, embedded :n:`@string` literals must be + correctly closed. Comments are treated as blanks. + +Identifiers + Identifiers, written :n:`@ident`, are sequences of letters, digits, ``_`` and + ``'``, that do not start with a digit or ``'``. That is, they are + recognized by the following grammar (except that the string ``_`` is reserved; + it is not a valid identifier): + + .. insertprodn ident subsequent_letter + + .. prodn:: + ident ::= @first_letter {* @subsequent_letter } + first_letter ::= {| a .. z | A .. Z | _ | @unicode_letter } + subsequent_letter ::= {| @first_letter | @digit | ' | @unicode_id_part } + + All characters are meaningful. In particular, identifiers are case-sensitive. + :production:`unicode_letter` non-exhaustively includes Latin, + Greek, Gothic, Cyrillic, Arabic, Hebrew, Georgian, Hangul, Hiragana + and Katakana characters, CJK ideographs, mathematical letter-like + symbols and non-breaking space. :production:`unicode_id_part` + non-exhaustively includes symbols for prime letters and subscripts. + +Numerals + Numerals are sequences of digits with an optional fractional part + and exponent, optionally preceded by a minus sign. :n:`@int` is an integer; + a numeral without fractional or exponent parts. :n:`@num` is a non-negative + integer. Underscores embedded in the digits are ignored, for example + ``1_000_000`` is the same as ``1000000``. + + .. insertprodn numeral digit + + .. prodn:: + numeral ::= {+ @digit } {? . {+ @digit } } {? {| e | E } {? {| + | - } } {+ @digit } } + int ::= {? - } {+ @digit } + num ::= {+ @digit } + digit ::= 0 .. 9 + +Strings + Strings begin and end with ``"`` (double quote). Use ``""`` to represent + a double quote character within a string. In the grammar, strings are + identified with :production:`string`. + +Keywords + The following character sequences are reserved keywords that cannot be + used as identifiers:: + + _ Axiom CoFixpoint Definition Fixpoint Hypothesis Parameter Prop + SProp Set Theorem Type Variable as at cofix discriminated else end + fix for forall fun if in let match return then where with + + Note that notations and plugins may define additional keywords. + +Other tokens + The set of + tokens defined at any given time can vary because the :cmd:`Notation` + command can define new tokens. A :cmd:`Require` command may load more notation definitions, + while the end of a :cmd:`Section` may remove notations. Some notations + are defined in the standard library (see :ref:`thecoqlibrary`) and are generally + loaded automatically at startup time. + + Here are the character sequences that |Coq| directly defines as tokens + without using :cmd:`Notation`:: + + ! #[ % & ' ( () (bfs) (dfs) ) * ** + , - -> + . .( .. ... / : ::= := :> :>> ; < <+ <- <: + <<: <= = => > >-> >= ? @ @{ [ [= ] _ + `( `{ { {| | |- || } + + When multiple tokens match the beginning of a sequence of characters, + the longest matching token is used. + Occasionally you may need to insert spaces to separate tokens. For example, + if ``~`` and ``~~`` are both defined as tokens, the inputs ``~ ~`` and + ``~~`` generate different tokens, whereas if `~~` is not defined, then the + two inputs are equivalent. + +Essential vocabulary +-------------------- + +This section presents the most essential notions to understand the +rest of the |Coq| manual: :term:`terms <term>` and :term:`types +<type>` on the one hand, :term:`commands <command>` and :term:`tactics +<tactic>` on the other hand. + +.. glossary:: + + term + + Terms are the basic expressions of |Coq|. Terms can represent + mathematical expressions, propositions and proofs, but also + executable programs and program types. + + Here is the top-level syntax of terms. Each of the listed + constructs is presented in a dedicated section. Some of these + constructs (like :n:`@term_forall_or_fun`) are part of the core + language that the kernel of |Coq| understands and are therefore + described in :ref:`this chapter <core-language>`, while + others (like :n:`@term_if`) are language extensions that are + presented in :ref:`the next chapter <extensions>`. + + .. insertprodn term qualid_annotated + + .. prodn:: + term ::= @term_forall_or_fun + | @term_let + | @term_if + | @term_fix + | @term_cofix + | @term100 + term100 ::= @term_cast + | @term10 + term10 ::= @term_application + | @one_term + one_term ::= @term_explicit + | @term1 + term1 ::= @term_projection + | @term_scope + | @term0 + term0 ::= @qualid_annotated + | @sort + | @primitive_notations + | @term_evar + | @term_match + | @term_record + | @term_generalizing + | @term_ltac + | ( @term ) + qualid_annotated ::= @qualid {? @univ_annot } + + .. note:: + + Many :term:`commands <command>` and :term:`tactics <tactic>` + use :n:`@one_term` (in the syntax of their arguments) rather + than :n:`@term`. The former need to be enclosed in + parentheses unless they're very simple, such as a single + identifier. This avoids confusing a space-separated list of + terms or identifiers with a :n:`@term_application`. + + type + + To be valid and accepted by the |Coq| kernel, a term needs an + associated type. We express this relationship by “:math:`x` *of + type* :math:`T`”, which we write as “:math:`x:T`”. Informally, + “:math:`x:T`” can be thought as “:math:`x` *belongs to* + :math:`T`”. + + The |Coq| kernel is a type checker: it verifies that a term has + the expected type by applying a set of typing rules (see + :ref:`Typing-rules`). If that's indeed the case, we say that the + term is :gdef:`well-typed`. + + A special feature of the |Coq| language is that types can depend + on terms (we say that the language is `dependently-typed + <https://en.wikipedia.org/wiki/Dependent_type>`_). Because of + this, types and terms share a common syntax. All types are terms, + but not all terms are types: + + .. insertprodn type type + + .. prodn:: + type ::= @term + + Intuitively, types may be viewed as sets containing terms. We + say that a type is :gdef:`inhabited` if it contains at least one + term (i.e. if we can find a term which is associated with this + type). We call such terms :gdef:`witness`\es. Note that deciding + whether a type is inhabited is `undecidable + <https://en.wikipedia.org/wiki/Undecidable_problem>`_. + + Formally, types can be used to construct logical foundations for + mathematics alternative to the standard `"set theory" + <https://en.wikipedia.org/wiki/Set_theory>`_: we call such + logical foundations `"type theories" + <https://en.wikipedia.org/wiki/Type_theory>`_. |Coq| is based on + the Calculus of Inductive Constructions, which is a particular + instance of type theory. + + sentence + + |Coq| documents are made of a series of sentences that contain + :term:`commands <command>` or :term:`tactics <tactic>`, generally + terminated with a period and optionally decorated with + :term:`attributes <attribute>`. + + .. insertprodn document sentence + + .. prodn:: + document ::= {* @sentence } + sentence ::= {? @attributes } @command . + | {? @attributes } {? @num : } @query_command . + | {? @attributes } {? @toplevel_selector } @ltac_expr {| . | ... } + | @control_command + + :n:`@ltac_expr` syntax supports both simple and compound + :term:`tactics <tactic>`. For example: ``split`` is a simple + tactic while ``split; auto`` combines two simple tactics. + + command + + A :production:`command` can be used to modify the state of a |Coq| + document, for instance by declaring a new object, or to get + information about the current state. + + By convention, command names begin with uppercase letters. + Commands appear in the HTML documentation in blue or gray boxes + after the label "Command". In the pdf, they appear after the + boldface label "Command:". Commands are listed in the + :ref:`command_index`. Example: + + .. cmd:: Comments {* @string } + + This command prints "Comments ok" and does not change anything + to the state of the document. + + tactic + + Tactics specify how to transform the current proof state as a + step in creating a proof. They are syntactically valid only when + |Coq| is in proof mode, such as after a :cmd:`Theorem` command + and before any subsequent proof-terminating command such as + :cmd:`Qed`. See :ref:`proofhandling` for more on proof mode. + + By convention, tactic names begin with lowercase letters. Tactic + appear in the HTML documentation in blue or gray boxes after the + label "Tactic". In the pdf, they appear after the boldface label + "Tactic:". Tactics are listed in the :ref:`tactic_index`. + +Settings +-------- + +There are several mechanisms for changing the behavior of |Coq|. The +:term:`attribute` mechanism is used to modify the behavior of a single +:term:`sentence`. The :term:`flag`, :term:`option` and :term:`table` +mechanisms are used to modify the behavior of |Coq| more globally in a +document or project. + +.. _attributes: + +Attributes +~~~~~~~~~~ + +An :gdef:`attribute` modifies the behavior of a single sentence. +Syntactically, most commands and tactics can be decorated with +attributes (cf. :n:`@sentence`), but attributes not supported by the +command or tactic will trigger :warn:`This command does not support +this attribute`. + +.. insertprodn attributes legacy_attr + +.. prodn:: + attributes ::= {* #[ {*, @attribute } ] } {* @legacy_attr } + attribute ::= @ident {? @attr_value } + attr_value ::= = @string + | ( {*, @attribute } ) + legacy_attr ::= {| Local | Global } + | {| Polymorphic | Monomorphic } + | {| Cumulative | NonCumulative } + | Private + | Program + +The order of top-level attributes doesn't affect their meaning. ``#[foo,bar]``, ``#[bar,foo]``, +``#[foo]#[bar]`` and ``#[bar]#[foo]`` are equivalent. + +The legacy attributes (:n:`@legacy_attr`) provide an older, alternate syntax +for certain attributes. They are equivalent to new attributes as follows: + +================ ================================ +Legacy attribute New attribute +================ ================================ +`Local` :attr:`local` +`Global` :attr:`global` +`Polymorphic` :attr:`universes(polymorphic)` +`Monomorphic` :attr:`universes(monomorphic)` +`Cumulative` :attr:`universes(cumulative)` +`NonCumulative` :attr:`universes(noncumulative)` +`Private` :attr:`private(matching)` +`Program` :attr:`program` +================ ================================ + +Attributes appear in the HTML documentation in blue or gray boxes +after the label "Attribute". In the pdf, they appear after the +boldface label "Attribute:". Attributes are listed in the +:ref:`attribute_index`. + +.. warn:: This command does not support this attribute: @ident. + :name: This command does not support this attribute + + This warning is configured to behave as an error by default. You + may turn it into a normal warning by using the :opt:`Warnings` option: + + .. coqtop:: none + + Set Silent. + + .. coqtop:: all warn + + Set Warnings "unsupported-attributes". + #[ foo ] Comments. + +.. _flags-options-tables: + +Flags, Options and Tables +~~~~~~~~~~~~~~~~~~~~~~~~~ + +The following types of settings can be used to change the behavior of |Coq| in +subsequent commands and tactics (see :ref:`set_unset_scope_qualifiers` for a +more precise description of the scope of these settings): + +* A :gdef:`flag` has a boolean value, such as :flag:`Universe Polymorphism`. +* An :gdef:`option` generally has a numeric or string value, such as :opt:`Firstorder Depth`. +* A :gdef:`table` contains a set of :token:`string`\s or :token:`qualid`\s. +* In addition, some commands provide settings, such as :cmd:`Extraction Language`. + +.. FIXME Convert "Extraction Language" to an option. + +Flags, options and tables are identified by a series of identifiers, each with an initial +capital letter. + +Flags, options and tables appear in the HTML documentation in blue or +gray boxes after the labels "Flag", "Option" and "Table". In the pdf, +they appear after a boldface label. They are listed in the +:ref:`options_index`. + +.. cmd:: Set @setting_name {? {| @int | @string } } + :name: Set + + .. insertprodn setting_name setting_name + + .. prodn:: + setting_name ::= {+ @ident } + + If :n:`@setting_name` is a flag, no value may be provided; the flag + is set to on. + If :n:`@setting_name` is an option, a value of the appropriate type + must be provided; the option is set to the specified value. + + This command supports the :attr:`local`, :attr:`global` and :attr:`export` attributes. + They are described :ref:`here <set_unset_scope_qualifiers>`. + + .. warn:: There is no flag or option with this name: "@setting_name". + + This warning message can be raised by :cmd:`Set` and + :cmd:`Unset` when :n:`@setting_name` is unknown. It is a + warning rather than an error because this helps library authors + produce |Coq| code that is compatible with several |Coq| versions. + To preserve the same behavior, they may need to set some + compatibility flags or options that did not exist in previous + |Coq| versions. + +.. cmd:: Unset @setting_name + :name: Unset + + If :n:`@setting_name` is a flag, it is set to off. If :n:`@setting_name` is an option, it is + set to its default value. + + This command supports the :attr:`local`, :attr:`global` and :attr:`export` attributes. + They are described :ref:`here <set_unset_scope_qualifiers>`. + +.. cmd:: Add @setting_name {+ {| @qualid | @string } } + + Adds the specified values to the table :n:`@setting_name`. + +.. cmd:: Remove @setting_name {+ {| @qualid | @string } } + + Removes the specified value from the table :n:`@setting_name`. + +.. cmd:: Test @setting_name {? for {+ {| @qualid | @string } } } + + If :n:`@setting_name` is a flag or option, prints its current value. + If :n:`@setting_name` is a table: if the `for` clause is specified, reports + whether the table contains each specified value, otherwise this is equivalent to + :cmd:`Print Table`. The `for` clause is not valid for flags and options. + + .. exn:: There is no flag, option or table with this name: "@setting_name". + + This error message is raised when calling the :cmd:`Test` + command (without the `for` clause), or the :cmd:`Print Table` + command, for an unknown :n:`@setting_name`. + + .. exn:: There is no qualid-valued table with this name: "@setting_name". + There is no string-valued table with this name: "@setting_name". + + These error messages are raised when calling the :cmd:`Add` or + :cmd:`Remove` commands, or the :cmd:`Test` command with the + `for` clause, if :n:`@setting_name` is unknown or does not have + the right type. + +.. cmd:: Print Options + + Prints the current value of all flags and options, and the names of all tables. + +.. cmd:: Print Table @setting_name + + Prints the values in the table :n:`@setting_name`. + +.. cmd:: Print Tables + + A synonym for :cmd:`Print Options`. + +.. _set_unset_scope_qualifiers: + +Locality attributes supported by :cmd:`Set` and :cmd:`Unset` +^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ + +The :cmd:`Set` and :cmd:`Unset` commands support the :attr:`local`, +:attr:`global` and :attr:`export` locality attributes: + +* no attribute: the original setting is *not* restored at the end of + the current module or section. +* :attr:`local` (or alternatively, the ``Local`` prefix): the setting + is applied within the current module or section. The original value + of the setting is restored at the end of the current module or + section. +* :attr:`export` (or alternatively, the ``Export`` prefix): similar to + :attr:`local`, the original value of the setting is restored at the + end of the current module or section. In addition, if the value is + set in a module, then :cmd:`Import`\-ing the module sets the option + or flag. +* :attr:`global` (or alternatively, the ``Global`` prefix): the + original setting is *not* restored at the end of the current module + or section. In addition, if the value is set in a file, then + :cmd:`Require`\-ing the file sets the option. + +Newly opened modules and sections inherit the current settings. + +.. note:: + + We discourage using the :attr:`global` attribute with the :cmd:`Set` and + :cmd:`Unset` commands. If your goal is to define + project-wide settings, you should rather use the command-line + arguments ``-set`` and ``-unset`` for setting flags and options + (cf. :ref:`command-line-options`). diff --git a/doc/sphinx/language/core/index.rst b/doc/sphinx/language/core/index.rst index 5ee960d99b..5e83672463 100644 --- a/doc/sphinx/language/core/index.rst +++ b/doc/sphinx/language/core/index.rst @@ -6,23 +6,26 @@ Core language At the heart of the Coq proof assistant is the Coq kernel. While users have access to a language with many convenient features such as -notations, implicit arguments, etc. (that are presented in the -:ref:`next chapter <extensions>`), such complex terms get translated -down to a core language (the Calculus of Inductive Constructions) that -the kernel understands, and which we present here. Furthermore, while -users can build proofs interactively using tactics (see Chapter +:ref:`notations <syntax-extensions-and-notation-scopes>`, +:ref:`implicit arguments <ImplicitArguments>`, etc. (presented in the +:ref:`next chapter <extensions>`), those features are translated into +the core language (the Calculus of Inductive Constructions) that the +kernel understands, which we present here. Furthermore, while users +can build proofs interactively using tactics (see Chapter :ref:`writing-proofs`), the role of these tactics is to incrementally build a "proof term" which the kernel will verify. More precisely, a -proof term is a term of the Calculus of Inductive Constructions whose -type corresponds to a theorem statement. The kernel is a type checker -which verifies that terms have their expected type. +proof term is a :term:`term` of the Calculus of Inductive +Constructions whose :term:`type` corresponds to a theorem statement. +The kernel is a type checker which verifies that terms have their +expected types. -This separation between the kernel on the one hand and the elaboration -engine and tactics on the other hand follows what is known as the "de -Bruijn criterion" (keeping a small and well delimited trusted code +This separation between the kernel on one hand and the +:ref:`elaboration engine <extensions>` and :ref:`tactics +<writing-proofs>` on the other follows what is known as the :gdef:`de +Bruijn criterion` (keeping a small and well delimited trusted code base within a proof assistant which can be much more complex). This -separation makes it possible to reduce the trust in the whole system -to trusting a smaller, critical component: the kernel. In particular, +separation makes it necessary to trust only a smaller, critical +component (the kernel) instead of the entire system. In particular, users may rely on external plugins that provide advanced and complex tactics without fear of these tactics being buggy, because the kernel will have to check their output. @@ -30,6 +33,7 @@ will have to check their output. .. toctree:: :maxdepth: 1 + basic ../gallina-specification-language ../cic records diff --git a/doc/sphinx/language/core/records.rst b/doc/sphinx/language/core/records.rst index d380d83d6c..0080f1d052 100644 --- a/doc/sphinx/language/core/records.rst +++ b/doc/sphinx/language/core/records.rst @@ -15,14 +15,17 @@ expressions. In this sense, the :cmd:`Record` construction allows defining .. cmd:: {| Record | Structure } @record_definition {* with @record_definition } :name: Record; Structure - .. insertprodn record_definition field_body + .. insertprodn record_definition field_def .. prodn:: record_definition ::= {? > } @ident_decl {* @binder } {? : @type } {? @ident } %{ {*; @record_field } %} {? @decl_notations } - record_field ::= {* #[ {*, @attr } ] } @name {? @field_body } {? %| @num } {? @decl_notations } + record_field ::= {* #[ {*, @attribute } ] } @name {? @field_body } {? %| @num } {? @decl_notations } field_body ::= {* @binder } @of_type | {* @binder } @of_type := @term | {* @binder } := @term + term_record ::= %{%| {* @field_def } %|%} + field_def ::= @qualid {* @binder } := @term + Each :n:`@record_definition` defines a record named by :n:`@ident_decl`. The constructor name is given by :n:`@ident`. @@ -112,13 +115,13 @@ You can override the display format for specified types by adding entries to the :name: Printing Record Specifies a set of qualids which are displayed as records. Use the - :cmd:`Add @table` and :cmd:`Remove @table` commands to update the set of qualids. + :cmd:`Add` and :cmd:`Remove` commands to update the set of qualids. .. table:: Printing Constructor @qualid :name: Printing Constructor Specifies a set of qualids which are displayed as constructors. Use the - :cmd:`Add @table` and :cmd:`Remove @table` commands to update the set of qualids. + :cmd:`Add` and :cmd:`Remove` commands to update the set of qualids. This syntax can also be used for pattern matching. diff --git a/doc/sphinx/language/extensions/arguments-command.rst b/doc/sphinx/language/extensions/arguments-command.rst new file mode 100644 index 0000000000..34a48b368b --- /dev/null +++ b/doc/sphinx/language/extensions/arguments-command.rst @@ -0,0 +1,440 @@ +.. _ArgumentsCommand: + +Setting properties of a function's arguments +++++++++++++++++++++++++++++++++++++++++++++ + +.. cmd:: Arguments @smart_qualid {* @arg_specs } {* , {* @implicits_alt } } {? : {+, @args_modifier } } + :name: Arguments + + .. insertprodn smart_qualid args_modifier + + .. prodn:: + smart_qualid ::= @qualid + | @by_notation + by_notation ::= @string {? % @scope_key } + argument_spec ::= {? ! } @name {? % @scope_key } + arg_specs ::= @argument_spec + | / + | & + | ( {+ @argument_spec } ) {? % @scope_key } + | [ {+ @argument_spec } ] {? % @scope_key } + | %{ {+ @argument_spec } %} {? % @scope_key } + implicits_alt ::= @name + | [ {+ @name } ] + | %{ {+ @name } %} + args_modifier ::= simpl nomatch + | simpl never + | default implicits + | clear implicits + | clear scopes + | clear bidirectionality hint + | rename + | assert + | extra scopes + | clear scopes and implicits + | clear implicits and scopes + + Specifies properties of the arguments of a function after the function has already + been defined. It gives fine-grained + control over the elaboration process (i.e. the translation of Gallina language + extensions into the core language used by the kernel). The command's effects include: + + * Making arguments implicit. Afterward, implicit arguments + must be omitted in any expression that applies :token:`smart_qualid`. + * Declaring that some arguments of a given function should + be interpreted in a given scope. + * Affecting when the :tacn:`simpl` and :tacn:`cbn` tactics unfold the function. + See :ref:`Args_effect_on_unfolding`. + * Providing bidirectionality hints. See :ref:`bidirectionality_hints`. + + This command supports the :attr:`local` and :attr:`global` attributes. + Default behavior is to limit the effect to the current section but also to + extend their effect outside the current module or library file. + Applying :attr:`local` limits the effect of the command to the current module if + it's not in a section. Applying :attr:`global` within a section extends the + effect outside the current sections and current module in which the command appears. + + `/` + the function will be unfolded only if it's applied to at least the + arguments appearing before the `/`. See :ref:`Args_effect_on_unfolding`. + + .. exn:: The / modifier may only occur once. + :undocumented: + + `&` + tells the type checking algorithm to first type check the arguments + before the `&` and then to propagate information from that typing context + to type check the remaining arguments. See :ref:`bidirectionality_hints`. + + .. exn:: The & modifier may only occur once. + :undocumented: + + :n:`( ... ) {? % @scope }` + :n:`(@name__1 @name__2 ...)%@scope` is shorthand for :n:`@name__1%@scope @name__2%@scope ...` + + :n:`[ ... ] {? % @scope }` + declares the enclosed names as implicit, non-maximally inserted. + :n:`[@name__1 @name__2 ... ]%@scope` is equivalent to :n:`[@name__1]%@scope [@name__2]%@scope ...` + + :n:`%{ ... %} {? % @scope }` + declares the enclosed names as implicit, maximally inserted. + :n:`%{@name__1 @name__2 ... %}%@scope` is equivalent to :n:`%{@name__1%}%@scope %{@name__2%}%@scope ...` + + `!` + the function will be unfolded only if all the arguments marked with `!` + evaulate to constructors. See :ref:`Args_effect_on_unfolding`. + + :n:`@name {? % @scope }` + a *formal parameter* of the function :n:`@smart_qualid` (i.e. + the parameter name used in the function definition). Unless `rename` is specified, + the list of :n:`@name`\s must be a prefix of the formal parameters, including all implicit + arguments. `_` can be used to skip over a formal parameter. + :token:`scope` can be either a scope name or its delimiting key. See :ref:`binding_to_scope`. + + `clear implicits` + makes all implicit arguments into explicit arguments + `default implicits` + automatically determine the implicit arguments of the object. + See :ref:`auto_decl_implicit_args`. + `rename` + rename implicit arguments for the object. See the example :ref:`here <renaming_implicit_arguments>`. + `assert` + assert that the object has the expected number of arguments with the + expected names. See the example here: :ref:`renaming_implicit_arguments`. + + .. warn:: This command is just asserting the names of arguments of @qualid. If this is what you want, add ': assert' to silence the warning. If you want to clear implicit arguments, add ': clear implicits'. If you want to clear notation scopes, add ': clear scopes' + :undocumented: + + `clear scopes` + clears argument scopes of :n:`@smart_qualid` + `extra scopes` + defines extra argument scopes, to be used in case of coercion to ``Funclass`` + (see the :ref:`implicitcoercions` chapter) or with a computed type. + `simpl nomatch` + prevents performing a simplification step for :n:`@smart_qualid` + that would expose a match construct in the head position. See :ref:`Args_effect_on_unfolding`. + `simpl never` + prevents performing a simplification step for :n:`@smart_qualid`. See :ref:`Args_effect_on_unfolding`. + + `clear bidirectionality hint` + removes the bidirectionality hint, the `&` + + :n:`@implicits_alt` + use to specify alternative implicit argument declarations + for functions that can only be + applied to a fixed number of arguments (excluding, for instance, + functions whose type is polymorphic). + For parsing, the longest list of implicit arguments matching the function application + is used to select which implicit arguments are inserted. + For printing, the alternative with the most implicit arguments is used; the + implict arguments will be omitted if :flag:`Printing Implicit` is not set. + See the example :ref:`here<example_more_implicits>`. + + .. todo the above feature seems a bit unnatural and doesn't play well with partial + application. See https://github.com/coq/coq/pull/11718#discussion_r408841762 + + Use :cmd:`About` to view the current implicit arguments setting for a :token:`smart_qualid`. + + Or use the :cmd:`Print Implicit` command to see the implicit arguments + of an object (see :ref:`displaying-implicit-args`). + +Manual declaration of implicit arguments +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. example:: + + .. coqtop:: reset all + + Inductive list (A : Type) : Type := + | nil : list A + | cons : A -> list A -> list A. + + Check (cons nat 3 (nil nat)). + + Arguments cons [A] _ _. + + Arguments nil {A}. + + Check (cons 3 nil). + + Fixpoint map (A B : Type) (f : A -> B) (l : list A) : list B := + match l with nil => nil | cons a t => cons (f a) (map A B f t) end. + + Fixpoint length (A : Type) (l : list A) : nat := + match l with nil => 0 | cons _ m => S (length A m) end. + + Arguments map [A B] f l. + + Arguments length {A} l. (* A has to be maximally inserted *) + + Check (fun l:list (list nat) => map length l). + +.. _example_more_implicits: + +.. example:: Multiple alternatives with :n:`@implicits_alt` + + .. coqtop:: all + + Arguments map [A B] f l, [A] B f l, A B f l. + + Check (fun l => map length l = map (list nat) nat length l). + +.. _auto_decl_implicit_args: + +Automatic declaration of implicit arguments +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + The ":n:`default implicits`" :token:`args_modifier` clause tells |Coq| to automatically determine the + implicit arguments of the object. + + Auto-detection is governed by flags specifying whether strict, + contextual, or reversible-pattern implicit arguments must be + considered or not (see :ref:`controlling-strict-implicit-args`, :ref:`controlling-contextual-implicit-args`, + :ref:`controlling-rev-pattern-implicit-args` and also :ref:`controlling-insertion-implicit-args`). + +.. example:: Default implicits + + .. coqtop:: reset all + + Inductive list (A:Set) : Set := + | nil : list A + | cons : A -> list A -> list A. + + Arguments cons : default implicits. + + Print Implicit cons. + + Arguments nil : default implicits. + + Print Implicit nil. + + Set Contextual Implicit. + + Arguments nil : default implicits. + + Print Implicit nil. + +The computation of implicit arguments takes account of the unfolding +of constants. For instance, the variable ``p`` below has type +``(Transitivity R)`` which is reducible to +``forall x,y:U, R x y -> forall z:U, R y z -> R x z``. As the variables ``x``, ``y`` and ``z`` +appear strictly in the body of the type, they are implicit. + +.. coqtop:: all + + Parameter X : Type. + + Definition Relation := X -> X -> Prop. + + Definition Transitivity (R:Relation) := forall x y:X, R x y -> forall z:X, R y z -> R x z. + + Parameters (R : Relation) (p : Transitivity R). + + Arguments p : default implicits. + + Print p. + + Print Implicit p. + + Parameters (a b c : X) (r1 : R a b) (r2 : R b c). + + Check (p r1 r2). + + +.. _renaming_implicit_arguments: + +Renaming implicit arguments +~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +.. example:: (continued) Renaming implicit arguments + + .. coqtop:: all + + Arguments p [s t] _ [u] _: rename. + + Check (p r1 (u:=c)). + + Check (p (s:=a) (t:=b) r1 (u:=c) r2). + + Fail Arguments p [s t] _ [w] _ : assert. + +.. _binding_to_scope: + +Binding arguments to a scope +~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + + The following command declares that the first two arguments of :g:`plus_fct` + are in the :token:`scope` delimited by the key ``F`` (``Rfun_scope``) and the third + argument is in the scope delimited by the key ``R`` (``R_scope``). + + .. coqdoc:: + + Arguments plus_fct (f1 f2)%F x%R. + + When interpreting a term, if some of the arguments of :token:`smart_qualid` are built + from a notation, then this notation is interpreted in the scope stack + extended by the scope bound (if any) to this argument. The effect of + the scope is limited to the argument itself. It does not propagate to + subterms but the subterms that, after interpretation of the notation, + turn to be themselves arguments of a reference are interpreted + accordingly to the argument scopes bound to this reference. + +.. note:: + + In notations, the subterms matching the identifiers of the + notations are interpreted in the scope in which the identifiers + occurred at the time of the declaration of the notation. Here is an + example: + + .. coqtop:: all + + Parameter g : bool -> bool. + Declare Scope mybool_scope. + + Notation "@@" := true (only parsing) : bool_scope. + Notation "@@" := false (only parsing): mybool_scope. + + Bind Scope bool_scope with bool. + Notation "# x #" := (g x) (at level 40). + Check # @@ #. + Arguments g _%mybool_scope. + Check # @@ #. + Delimit Scope mybool_scope with mybool. + Check # @@%mybool #. + +.. _Args_effect_on_unfolding: + +Effects of :cmd:`Arguments` on unfolding +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + ++ `simpl never` indicates that a constant should never be unfolded by :tacn:`cbn`, + :tacn:`simpl` or :tacn:`hnf`: + + .. example:: + + .. coqtop:: all + + Arguments minus n m : simpl never. + + After that command an expression like :g:`(minus (S x) y)` is left + untouched by the tactics :tacn:`cbn` and :tacn:`simpl`. + ++ A constant can be marked to be unfolded only if it's applied to at least + the arguments appearing before the `/` in a :cmd:`Arguments` command. + + .. example:: + + .. coqtop:: all + + Definition fcomp A B C f (g : A -> B) (x : A) : C := f (g x). + Arguments fcomp {A B C} f g x /. + Notation "f \o g" := (fcomp f g) (at level 50). + + After that command the expression :g:`(f \o g)` is left untouched by + :tacn:`simpl` while :g:`((f \o g) t)` is reduced to :g:`(f (g t))`. + The same mechanism can be used to make a constant volatile, i.e. + always unfolded. + + .. example:: + + .. coqtop:: all + + Definition volatile := fun x : nat => x. + Arguments volatile / x. + ++ A constant can be marked to be unfolded only if an entire set of + arguments evaluates to a constructor. The ``!`` symbol can be used to mark + such arguments. + + .. example:: + + .. coqtop:: all + + Arguments minus !n !m. + + After that command, the expression :g:`(minus (S x) y)` is left untouched + by :tacn:`simpl`, while :g:`(minus (S x) (S y))` is reduced to :g:`(minus x y)`. + ++ `simpl nomatch` indicates that a constant should not be unfolded if it would expose + a `match` construct in the head position. This affects the :tacn:`cbn`, + :tacn:`simpl` and :tacn:`hnf` tactics. + + .. example:: + + .. coqtop:: all + + Arguments minus n m : simpl nomatch. + + In this case, :g:`(minus (S (S x)) (S y))` is simplified to :g:`(minus (S x) y)` + even if an extra simplification is possible. + + In detail: the tactic :tacn:`simpl` first applies :math:`\beta`:math:`\iota`-reduction. Then, it + expands transparent constants and tries to reduce further using :math:`\beta`:math:`\iota`-reduction. + But, when no :math:`\iota` rule is applied after unfolding then + :math:`\delta`-reductions are not applied. For instance trying to use :tacn:`simpl` on + :g:`(plus n O) = n` changes nothing. + + +.. _bidirectionality_hints: + +Bidirectionality hints +~~~~~~~~~~~~~~~~~~~~~~ + +When type-checking an application, Coq normally does not use information from +the context to infer the types of the arguments. It only checks after the fact +that the type inferred for the application is coherent with the expected type. +Bidirectionality hints make it possible to specify that after type-checking the +first arguments of an application, typing information should be propagated from +the context to help inferring the types of the remaining arguments. + +.. todo the following text is a start on better wording but not quite complete. + See https://github.com/coq/coq/pull/11718#discussion_r410219992 + + .. + Two common methods to determine the type of a construct are: + + * *type checking*, which is verifying that a construct matches a known type, and + * *type inference*, with is inferring the type of a construct by analyzing the construct. + + Methods that combine these approaches are known as *bidirectional typing*. + Coq normally uses only the first approach to infer the types of arguments, + then later verifies that the inferred type is consistent with the expected type. + *Bidirectionality hints* specify to use both methods: after type checking the + first arguments of an application (appearing before the `&` in :cmd:`Arguments`), + typing information from them is propagated to the remaining arguments to help infer their types. + +An :cmd:`Arguments` command containing :n:`@arg_specs__1 & @arg_specs__2` +provides bidirectionality hints. +It tells the typechecking algorithm, when type checking +applications of :n:`@qualid`, to first type check the arguments in +:n:`@arg_specs__1` and then propagate information from the typing context to +type check the remaining arguments (in :n:`@arg_specs__2`). + +.. example:: Bidirectionality hints + + In a context where a coercion was declared from ``bool`` to ``nat``: + + .. coqtop:: in reset + + Definition b2n (b : bool) := if b then 1 else 0. + Coercion b2n : bool >-> nat. + + Coq cannot automatically coerce existential statements over ``bool`` to + statements over ``nat``, because the need for inserting a coercion is known + only from the expected type of a subterm: + + .. coqtop:: all + + Fail Check (ex_intro _ true _ : exists n : nat, n > 0). + + However, a suitable bidirectionality hint makes the example work: + + .. coqtop:: all + + Arguments ex_intro _ _ & _ _. + Check (ex_intro _ true _ : exists n : nat, n > 0). + +Coq will attempt to produce a term which uses the arguments you +provided, but in some cases involving Program mode the arguments after +the bidirectionality starts may be replaced by convertible but +syntactically different terms. diff --git a/doc/sphinx/language/extensions/implicit-arguments.rst b/doc/sphinx/language/extensions/implicit-arguments.rst index fb762a00f1..73b1b65097 100644 --- a/doc/sphinx/language/extensions/implicit-arguments.rst +++ b/doc/sphinx/language/extensions/implicit-arguments.rst @@ -105,28 +105,26 @@ This corresponds to a class of non-dependent implicit arguments that are solved based on the structure of their type only. -Maximal or non maximal insertion of implicit arguments -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Maximal and non-maximal insertion of implicit arguments +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -In case a function is partially applied, and the next argument to be -applied is an implicit argument, two disciplines are applicable. In -the first case, the function is considered to have no arguments -furtherly: one says that the implicit argument is not maximally -inserted. In the second case, the function is considered to be -implicitly applied to the implicit arguments it is waiting for: one -says that the implicit argument is maximally inserted. +When a function is partially applied and the next argument to +apply is an implicit argument, the application can be interpreted in two ways. +If the next argument is declared as *maximally inserted*, the partial +application will include that argument. Otherwise, the argument is +*non-maximally inserted* and the partial application will not include that argument. Each implicit argument can be declared to be inserted maximally or non -maximally. In Coq, maximally-inserted implicit arguments are written between curly braces -"{ }" and non-maximally-inserted implicit arguments are written in square brackets "[ ]". +maximally. In Coq, maximally inserted implicit arguments are written between curly braces +"{ }" and non-maximally inserted implicit arguments are written in square brackets "[ ]". .. seealso:: :flag:`Maximal Implicit Insertion` Trailing Implicit Arguments +++++++++++++++++++++++++++ -An implicit argument is considered trailing when all following arguments are declared -implicit. Trailing implicit arguments cannot be declared non maximally inserted, +An implicit argument is considered *trailing* when all following arguments are +implicit. Trailing implicit arguments must be declared as maximally inserted; otherwise they would never be inserted. .. exn:: Argument @name is a trailing implicit, so it can't be declared non maximal. Please use %{ %} instead of [ ]. @@ -141,10 +139,9 @@ otherwise they would never be inserted. Casual use of implicit arguments ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -In a given expression, if it is clear that some argument of a function -can be inferred from the type of the other arguments, the user can -force the given argument to be guessed by replacing it by “_”. If -possible, the correct argument will be automatically generated. +If an argument of a function application can be inferred from the type +of the other arguments, the user can force inference of the argument +by replacing it with `_`. .. exn:: Cannot infer a term for this placeholder. :name: Cannot infer a term for this placeholder. (Casual use of implicit arguments) @@ -156,12 +153,8 @@ possible, the correct argument will be automatically generated. Declaration of implicit arguments ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -In case one wants that some arguments of a given object (constant, -inductive types, constructors, assumptions, local or not) are always -inferred by |Coq|, one may declare once and for all which are the -expected implicit arguments of this object. There are two ways to do -this, *a priori* and *a posteriori*. - +Implicit arguments can be declared when a function is declared or +afterwards, using the :cmd:`Arguments` command. Implicit Argument Binders +++++++++++++++++++++++++ @@ -172,18 +165,20 @@ Implicit Argument Binders implicit_binders ::= %{ {+ @name } {? : @type } %} | [ {+ @name } {? : @type } ] -In the first setting, one wants to explicitly give the implicit -arguments of a declared object as part of its definition. To do this, -one has to surround the bindings of implicit arguments by curly -braces or square braces: +In the context of a function definition, these forms specify that +:token:`name` is an implicit argument. The first form, with curly +braces, makes :token:`name` a maximally inserted implicit argument. The second +form, with square brackets, makes :token:`name` a non-maximally inserted implicit argument. + +For example: .. coqtop:: all Definition id {A : Type} (x : A) : A := x. -This automatically declares the argument A of id as a maximally -inserted implicit argument. One can then do as-if the argument was -absent in every situation but still be able to specify it if needed: +declares the argument `A` of `id` as a maximally +inserted implicit argument. `A` may be omitted +in applications of `id` but may be specified if needed: .. coqtop:: all @@ -191,7 +186,7 @@ absent in every situation but still be able to specify it if needed: Goal forall A, compose id id = id (A:=A). -For non maximally inserted implicit arguments, use square brackets: +For non-maximally inserted implicit arguments, use square brackets: .. coqtop:: all @@ -203,8 +198,7 @@ For non maximally inserted implicit arguments, use square brackets: Print Implicit map. -The syntax is supported in all top-level definitions: -:cmd:`Definition`, :cmd:`Fixpoint`, :cmd:`Lemma` and so on. For (co-)inductive datatype +For (co-)inductive datatype declarations, the semantics are the following: an inductive parameter declared as an implicit argument need not be repeated in the inductive definition and will become implicit for the inductive type and the constructors. @@ -225,11 +219,12 @@ The syntax is also supported in internal binders. For instance, in the following kinds of expressions, the type of each declaration present in :token:`binders` can be bracketed to mark the declaration as implicit: -:n:`fun (@ident:forall {* @binder }, @type) => @term`, -:n:`forall (@ident:forall {* @binder }, @type), @type`, -:n:`let @ident {* @binder } := @term in @term`, -:n:`fix @ident {* @binder } := @term in @term` and -:n:`cofix @ident {* @binder } := @term in @term`. +* :n:`fun (@ident:forall {* @binder }, @type) => @term`, +* :n:`forall (@ident:forall {* @binder }, @type), @type`, +* :n:`let @ident {* @binder } := @term in @term`, +* :n:`fix @ident {* @binder } := @term in @term` and +* :n:`cofix @ident {* @binder } := @term in @term`. + Here is an example: .. coqtop:: all @@ -259,190 +254,6 @@ Here is an example: Check let g {x:nat} (H:x=x) {x} (H:x=x) := x in 0. - -Declaring Implicit Arguments -++++++++++++++++++++++++++++ - - - -.. cmd:: Arguments @smart_qualid {* @argument_spec_block } {* , {* @more_implicits_block } } {? : {+, @arguments_modifier } } - :name: Arguments - - .. insertprodn smart_qualid arguments_modifier - - .. prodn:: - smart_qualid ::= @qualid - | @by_notation - by_notation ::= @string {? % @ident } - argument_spec_block ::= @argument_spec - | / - | & - | ( {+ @argument_spec } ) {? % @ident } - | [ {+ @argument_spec } ] {? % @ident } - | %{ {+ @argument_spec } %} {? % @ident } - argument_spec ::= {? ! } @name {? % @ident } - more_implicits_block ::= @name - | [ {+ @name } ] - | %{ {+ @name } %} - arguments_modifier ::= simpl nomatch - | simpl never - | default implicits - | clear bidirectionality hint - | clear implicits - | clear scopes - | clear scopes and implicits - | clear implicits and scopes - | rename - | assert - | extra scopes - - This command sets implicit arguments *a posteriori*, - where the list of :n:`@name`\s is a prefix of the list of - arguments of :n:`@smart_qualid`. Arguments in square - brackets are declared as implicit and arguments in curly brackets are declared as - maximally inserted. - - After the command is issued, implicit arguments can and must be - omitted in any expression that applies :token:`qualid`. - - This command supports the :attr:`local` and :attr:`global` attributes. - Default behavior is to limit the effect to the current section but also to - extend their effect outside the current module or library file. - Applying :attr:`local` limits the effect of the command to the current module if - it's not in a section. Applying :attr:`global` within a section extends the - effect outside the current sections and current module if the command occurs. - - A command containing :n:`@argument_spec_block & @argument_spec_block` - provides :ref:`bidirectionality_hints`. - - Use the :n:`@more_implicits_block` to specify multiple implicit arguments declarations - for names of constants, inductive types, constructors and lemmas that can only be - applied to a fixed number of arguments (excluding, for instance, - constants whose type is polymorphic). - The longest applicable list of implicit arguments will be used to select which - implicit arguments are inserted. - For printing, the omitted arguments are the ones of the longest list of implicit - arguments of the sequence. See the example :ref:`here<example_more_implicits>`. - - The :n:`@arguments_modifier` values have various effects: - - * :n:`clear implicits` - clears implicit arguments - * :n:`default implicits` - automatically determine the implicit arguments of the object. - See :ref:`auto_decl_implicit_args`. - * :n:`rename` - rename implicit arguments for the object - * :n:`assert` - assert that the object has the expected number of arguments with the - expected names. See the example here: :ref:`renaming_implicit_arguments`. - -.. exn:: The / modifier may only occur once. - :undocumented: - -.. exn:: The & modifier may only occur once. - :undocumented: - -.. example:: - - .. coqtop:: reset all - - Inductive list (A : Type) : Type := - | nil : list A - | cons : A -> list A -> list A. - - Check (cons nat 3 (nil nat)). - - Arguments cons [A] _ _. - - Arguments nil {A}. - - Check (cons 3 nil). - - Fixpoint map (A B : Type) (f : A -> B) (l : list A) : list B := - match l with nil => nil | cons a t => cons (f a) (map A B f t) end. - - Fixpoint length (A : Type) (l : list A) : nat := - match l with nil => 0 | cons _ m => S (length A m) end. - - Arguments map [A B] f l. - - Arguments length {A} l. (* A has to be maximally inserted *) - - Check (fun l:list (list nat) => map length l). - -.. _example_more_implicits: - -.. example:: Multiple implicit arguments with :n:`@more_implicits_block` - - .. coqtop:: all - - Arguments map [A B] f l, [A] B f l, A B f l. - - Check (fun l => map length l = map (list nat) nat length l). - -.. note:: - Use the :cmd:`Print Implicit` command to see the implicit arguments - of an object (see :ref:`displaying-implicit-args`). - -.. _auto_decl_implicit_args: - -Automatic declaration of implicit arguments -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - - The :n:`default implicits @arguments_modifier` clause tells |Coq| to automatically determine the - implicit arguments of the object. - - Auto-detection is governed by flags specifying whether strict, - contextual, or reversible-pattern implicit arguments must be - considered or not (see :ref:`controlling-strict-implicit-args`, :ref:`controlling-contextual-implicit-args`, - :ref:`controlling-rev-pattern-implicit-args` and also :ref:`controlling-insertion-implicit-args`). - -.. example:: Default implicits - - .. coqtop:: reset all - - Inductive list (A:Set) : Set := - | nil : list A - | cons : A -> list A -> list A. - - Arguments cons : default implicits. - - Print Implicit cons. - - Arguments nil : default implicits. - - Print Implicit nil. - - Set Contextual Implicit. - - Arguments nil : default implicits. - - Print Implicit nil. - -The computation of implicit arguments takes account of the unfolding -of constants. For instance, the variable ``p`` below has type -``(Transitivity R)`` which is reducible to -``forall x,y:U, R x y -> forall z:U, R y z -> R x z``. As the variables ``x``, ``y`` and ``z`` -appear strictly in the body of the type, they are implicit. - -.. coqtop:: all - - Parameter X : Type. - - Definition Relation := X -> X -> Prop. - - Definition Transitivity (R:Relation) := forall x y:X, R x y -> forall z:X, R y z -> R x z. - - Parameters (R : Relation) (p : Transitivity R). - - Arguments p : default implicits. - - Print p. - - Print Implicit p. - - Parameters (a b c : X) (r1 : R a b) (r2 : R b c). - - Check (p r1 r2). - - Mode for automatic declaration of implicit arguments ++++++++++++++++++++++++++++++++++++++++++++++++++++ @@ -514,7 +325,7 @@ and the automatic declaration mode in on, the manual implicit arguments are adde automatically declared ones. In that case, and when the flag :flag:`Maximal Implicit Insertion` is set to off, -some trailing implicit arguments can be inferred to be non maximally inserted. In +some trailing implicit arguments can be inferred to be non-maximally inserted. In this case, they are converted to maximally inserted ones. .. example:: @@ -540,34 +351,23 @@ application. Use the :n:`(@ident := @term)` form of :token:`arg` to do so, where :token:`ident` is the name of the implicit argument and :token:`term` is its corresponding explicit term. Alternatively, one can deactivate the hiding of implicit arguments for a single function application using the -:n:`@ @qualid {? @univ_annot } {* @term1 }` form of :token:`term10`. +:n:`@@qualid_annotated {+ @term1 }` form of :token:`term_application`. .. example:: Syntax for explicitly giving implicit arguments (continued) .. coqtop:: all + Parameter X : Type. + Definition Relation := X -> X -> Prop. + Definition Transitivity (R:Relation) := forall x y:X, R x y -> forall z:X, R y z -> R x z. + Parameters (R : Relation) (p : Transitivity R). + Arguments p : default implicits. + Print Implicit p. + Parameters (a b c : X) (r1 : R a b) (r2 : R b c). Check (p r1 (z:=c)). Check (p (x:=a) (y:=b) r1 (z:=c) r2). - -.. _renaming_implicit_arguments: - -Renaming implicit arguments -~~~~~~~~~~~~~~~~~~~~~~~~~~~ - -.. example:: (continued) Renaming implicit arguments - - .. coqtop:: all - - Arguments p [s t] _ [u] _: rename. - - Check (p r1 (u:=c)). - - Check (p (s:=a) (t:=b) r1 (u:=c) r2). - - Fail Arguments p [s t] _ [w] _ : assert. - .. _displaying-implicit-args: Displaying implicit arguments @@ -620,6 +420,30 @@ but succeeds in Deactivation of implicit arguments for parsing ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. insertprodn term_explicit term_explicit + +.. prodn:: + term_explicit ::= @ @qualid_annotated + +This syntax can be used to disable implicit arguments for a single +function. + +.. example:: + + The function `id` has one implicit argument and one explicit + argument. + + .. coqtop:: all reset + + Check (id 0). + Definition id' := @id. + + The function `id'` has no implicit argument. + + .. coqtop:: all + + Check (id' nat 0). + .. flag:: Parsing Explicit Turning this flag on (it is off by default) deactivates the use of implicit arguments. @@ -629,6 +453,19 @@ Deactivation of implicit arguments for parsing to be given as if no arguments were implicit. By symmetry, this also affects printing. +.. example:: + + We can reproduce the example above using the :flag:`Parsing + Explicit` flag: + + .. coqtop:: all reset + + Set Parsing Explicit. + Definition id' := id. + Unset Parsing Explicit. + Check (id 1). + Check (id' nat 1). + .. _canonical-structure-declaration: Canonical structures @@ -668,7 +505,7 @@ in :ref:`canonicalstructures`; here only a simple example is given. Here is an example. - .. coqtop:: all + .. coqtop:: all reset Require Import Relations. @@ -806,7 +643,7 @@ Implicit generalization .. index:: `[! ] .. index:: `(! ) -.. insertprodn generalizing_binder typeclass_constraint +.. insertprodn generalizing_binder term_generalizing .. prodn:: generalizing_binder ::= `( {+, @typeclass_constraint } ) @@ -815,7 +652,8 @@ Implicit generalization typeclass_constraint ::= {? ! } @term | %{ @name %} : {? ! } @term | @name : {? ! } @term - + term_generalizing ::= `%{ @term %} + | `( @term ) Implicit generalization is an automatic elaboration of a statement with free variables into a closed statement where these variables are @@ -827,7 +665,7 @@ surrounding it with \`{ }, or \`[ ] or \`( ). Terms surrounded by \`{ } introduce their free variables as maximally inserted implicit arguments, terms surrounded by \`[ ] introduce them as -non maximally inserted implicit arguments and terms surrounded by \`( ) +non-maximally inserted implicit arguments and terms surrounded by \`( ) introduce them as explicit arguments. Generalizing binders always introduce their free variables as diff --git a/doc/sphinx/language/extensions/index.rst b/doc/sphinx/language/extensions/index.rst index 627e7f0acb..fc2ce03093 100644 --- a/doc/sphinx/language/extensions/index.rst +++ b/doc/sphinx/language/extensions/index.rst @@ -20,6 +20,7 @@ language presented in the :ref:`previous chapter <core-language>`. implicit-arguments ../../addendum/extended-pattern-matching ../../user-extensions/syntax-extensions + arguments-command ../../addendum/implicit-coercions ../../addendum/type-classes ../../addendum/canonical-structures diff --git a/doc/sphinx/language/gallina-extensions.rst b/doc/sphinx/language/gallina-extensions.rst index a859aa46eb..5b78280edc 100644 --- a/doc/sphinx/language/gallina-extensions.rst +++ b/doc/sphinx/language/gallina-extensions.rst @@ -30,6 +30,11 @@ under its expanded form (see :flag:`Printing Matching`). Pattern-matching on boolean values: the if expression ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. insertprodn term_if term_if + +.. prodn:: + term_if ::= if @term {? {? as @name } return @term100 } then @term else @term + For inductive types with exactly two constructors and for pattern matching expressions that do not depend on the arguments of the constructors, it is possible to use a ``if … then … else`` notation. For instance, the definition @@ -238,7 +243,7 @@ written using the first destructuring let syntax. Note that this only applies to pattern matching instances entered with :g:`match`. It doesn't affect pattern matching explicitly entered with a destructuring :g:`let`. - Use the :cmd:`Add @table` and :cmd:`Remove @table` commands to update this set. + Use the :cmd:`Add` and :cmd:`Remove` commands to update this set. Printing matching on booleans @@ -252,7 +257,7 @@ which types are written this way: :name: Printing If Specifies a set of qualids for which pattern matching is displayed using - ``if`` … ``then`` … ``else`` …. Use the :cmd:`Add @table` and :cmd:`Remove @table` + ``if`` … ``then`` … ``else`` …. Use the :cmd:`Add` and :cmd:`Remove` commands to update this set. This example emphasizes what the printing settings offer. @@ -316,11 +321,11 @@ together, as well as a means of massive abstraction. parameters given by the :n:`@module_binder`\s. (A *functor* is a function from modules to modules.) - .. todo: would like to find a better term than "interactive", not very descriptive - :n:`@of_module_type` specifies the module type. :n:`{+ <: @module_type_inl }` starts a module that satisfies each :n:`@module_type_inl`. + .. todo: would like to find a better term than "interactive", not very descriptive + :n:`:= {+<+ @module_expr_inl }` specifies the body of a module or functor definition. If it's not specified, then the module is defined *interactively*, meaning that the module is defined as a series of commands terminated with :cmd:`End` @@ -422,7 +427,12 @@ are now available through the dot notation. If :n:`@module_binder`\s are specified, declares a functor with parameters given by the list of :token:`module_binder`\s. -.. cmd:: Import {+ @qualid } +.. cmd:: Import {+ @filtered_import } + + .. insertprodn filtered_import filtered_import + + .. prodn:: + filtered_import ::= @qualid {? ( {+, @qualid {? ( .. ) } } ) } If :token:`qualid` denotes a valid basic module (i.e. its module type is a signature), makes its components available by their short names. @@ -465,12 +475,50 @@ are now available through the dot notation. Check B.T. -.. cmd:: Export {+ @qualid } + Appending a module name with a parenthesized list of names will + make only those names available with short names, not other names + defined in the module nor will it activate other features. + + The names to import may be constants, inductive types and + constructors, and notation aliases (for instance, Ltac definitions + cannot be selectively imported). If they are from an inner module + to the one being imported, they must be prefixed by the inner path. + + The name of an inductive type may also be followed by ``(..)`` to + import it, its constructors and its eliminators if they exist. For + this purpose "eliminator" means a constant in the same module whose + name is the inductive type's name suffixed by one of ``_sind``, + ``_ind``, ``_rec`` or ``_rect``. + + .. example:: + + .. coqtop:: reset in + + Module A. + Module B. + Inductive T := C. + Definition U := nat. + End B. + Definition Z := Prop. + End A. + Import A(B.T(..), Z). + + .. coqtop:: all + + Check B.T. + Check B.C. + Check Z. + Fail Check B.U. + Check A.B.U. + +.. cmd:: Export {+ @filtered_import } :name: Export Similar to :cmd:`Import`, except that when the module containing this command is imported, the :n:`{+ @qualid }` are imported as well. + The selective import syntax also works with Export. + .. exn:: @qualid is not a module. :undocumented: @@ -563,12 +611,9 @@ module can be accessed using the dot notation: Parameter x : T. End SIG. -The following definition of :g:`N` using the module type expression :g:`SIG` with +The definition of :g:`N` using the module type expression :g:`SIG` with :g:`Definition T := nat` is equivalent to the following one: -.. todo: what is other definition referred to above? - "Module N' : SIG with Definition T := nat. End N`." is not it. - .. coqtop:: in Module Type SIG'. @@ -719,7 +764,7 @@ accessible, absolute names can never be hidden. Locate nat. -.. seealso:: Commands :cmd:`Locate` and :cmd:`Locate Library`. +.. seealso:: Commands :cmd:`Locate`. .. _libraries-and-filesystem: @@ -812,7 +857,7 @@ Printing constructions in full .. flag:: Printing All Coercions, implicit arguments, the type of pattern matching, but also - notations (see :ref:`syntaxextensionsandinterpretationscopes`) can obfuscate the behavior of some + notations (see :ref:`syntax-extensions-and-notation-scopes`) can obfuscate the behavior of some tactics (typically the tactics applying to occurrences of subterms are sensitive to the implicit arguments). Turning this flag on deactivates all high-level printing features such as coercions, @@ -823,6 +868,16 @@ Printing constructions in full :flag:`Printing Projections`, and :flag:`Printing Notations`. To reactivate the high-level printing features, use the command ``Unset Printing All``. + .. note:: In some cases, setting :flag:`Printing All` may display terms + that are so big they become very hard to read. One technique to work around + this is use :cmd:`Undelimit Scope` and/or :cmd:`Close Scope` to turn off the + printing of notations bound to particular scope(s). This can be useful when + notations in a given scope are getting in the way of understanding + a goal, but turning off all notations with :flag:`Printing All` would make + the goal unreadable. + + .. see a contrived example here: https://github.com/coq/coq/pull/11718#discussion_r415481854 + .. _printing-universes: Printing universes @@ -863,7 +918,8 @@ Existential variables .. insertprodn term_evar term_evar .. prodn:: - term_evar ::= ?[ @ident ] + term_evar ::= _ + | ?[ @ident ] | ?[ ?@ident ] | ?@ident {? @%{ {+; @ident := @term } %} } @@ -1056,51 +1112,3 @@ Literal values (of type :g:`Float64.t`) are extracted to literal OCaml values (of type :g:`float`) written in hexadecimal notation and wrapped into the :g:`Float64.of_float` constructor, e.g.: :g:`Float64.of_float (0x1p+0)`. - -.. _bidirectionality_hints: - -Bidirectionality hints ----------------------- - -When type-checking an application, Coq normally does not use information from -the context to infer the types of the arguments. It only checks after the fact -that the type inferred for the application is coherent with the expected type. -Bidirectionality hints make it possible to specify that after type-checking the -first arguments of an application, typing information should be propagated from -the context to help inferring the types of the remaining arguments. - -An :cmd:`Arguments` command containing :n:`@argument_spec_block__1 & @argument_spec_block__2` -provides :ref:`bidirectionality_hints`. -It tells the typechecking algorithm, when type-checking -applications of :n:`@qualid`, to first type-check the arguments in -:n:`@argument_spec_block__1` and then propagate information from the typing context to -type-check the remaining arguments (in :n:`@argument_spec_block__2`). - -.. example:: Bidirectionality hints - - In a context where a coercion was declared from ``bool`` to ``nat``: - - .. coqtop:: in reset - - Definition b2n (b : bool) := if b then 1 else 0. - Coercion b2n : bool >-> nat. - - Coq cannot automatically coerce existential statements over ``bool`` to - statements over ``nat``, because the need for inserting a coercion is known - only from the expected type of a subterm: - - .. coqtop:: all - - Fail Check (ex_intro _ true _ : exists n : nat, n > 0). - - However, a suitable bidirectionality hint makes the example work: - - .. coqtop:: all - - Arguments ex_intro _ _ & _ _. - Check (ex_intro _ true _ : exists n : nat, n > 0). - -Coq will attempt to produce a term which uses the arguments you -provided, but in some cases involving Program mode the arguments after -the bidirectionality starts may be replaced by convertible but -syntactically different terms. diff --git a/doc/sphinx/language/gallina-specification-language.rst b/doc/sphinx/language/gallina-specification-language.rst index f4592f8f37..353bed1b3d 100644 --- a/doc/sphinx/language/gallina-specification-language.rst +++ b/doc/sphinx/language/gallina-specification-language.rst @@ -7,197 +7,13 @@ This chapter describes Gallina, the specification language of Coq. It allows developing mathematical theories and to prove specifications of programs. The theories are built from axioms, hypotheses, parameters, lemmas, theorems and -definitions of constants, functions, predicates and sets. The syntax of logical -objects involved in theories is described in Section :ref:`term`. The -language of commands, called *The Vernacular* is described in Section -:ref:`vernacular`. - -In Coq, logical objects are typed to ensure their logical correctness. The -rules implemented by the typing algorithm are described in Chapter :ref:`calculusofinductiveconstructions`. - - -.. About the grammars in the manual - ================================ - - Grammars are presented in Backus-Naur form (BNF). Terminal symbols are - set in black ``typewriter font``. In addition, there are special notations for - regular expressions. - - An expression enclosed in square brackets ``[…]`` means at most one - occurrence of this expression (this corresponds to an optional - component). - - The notation “``entry sep … sep entry``” stands for a non empty sequence - of expressions parsed by entry and separated by the literal “``sep``” [1]_. - - Similarly, the notation “``entry … entry``” stands for a non empty - sequence of expressions parsed by the “``entry``” entry, without any - separator between. - - At the end, the notation “``[entry sep … sep entry]``” stands for a - possibly empty sequence of expressions parsed by the “``entry``” entry, - separated by the literal “``sep``”. - -.. _lexical-conventions: - -Lexical conventions -=================== - -Blanks - Space, newline and horizontal tab are considered blanks. - Blanks are ignored but they separate tokens. - -Comments - Comments are enclosed between ``(*`` and ``*)``. They can be nested. - They can contain any character. However, embedded :n:`@string` literals must be - correctly closed. Comments are treated as blanks. - -Identifiers - Identifiers, written :n:`@ident`, are sequences of letters, digits, ``_`` and - ``'``, that do not start with a digit or ``'``. That is, they are - recognized by the following grammar (except that the string ``_`` is reserved; - it is not a valid identifier): - - .. insertprodn ident subsequent_letter - - .. prodn:: - ident ::= @first_letter {* @subsequent_letter } - first_letter ::= {| a .. z | A .. Z | _ | @unicode_letter } - subsequent_letter ::= {| @first_letter | @digit | ' | @unicode_id_part } - - All characters are meaningful. In particular, identifiers are case-sensitive. - :production:`unicode_letter` non-exhaustively includes Latin, - Greek, Gothic, Cyrillic, Arabic, Hebrew, Georgian, Hangul, Hiragana - and Katakana characters, CJK ideographs, mathematical letter-like - symbols and non-breaking space. :production:`unicode_id_part` - non-exhaustively includes symbols for prime letters and subscripts. - -Numerals - Numerals are sequences of digits with an optional fractional part - and exponent, optionally preceded by a minus sign. :n:`@int` is an integer; - a numeral without fractional or exponent parts. :n:`@num` is a non-negative - integer. Underscores embedded in the digits are ignored, for example - ``1_000_000`` is the same as ``1000000``. - - .. insertprodn numeral digit - - .. prodn:: - numeral ::= {+ @digit } {? . {+ @digit } } {? {| e | E } {? {| + | - } } {+ @digit } } - int ::= {? - } {+ @digit } - num ::= {+ @digit } - digit ::= 0 .. 9 - -Strings - Strings begin and end with ``"`` (double quote). Use ``""`` to represent - a double quote character within a string. In the grammar, strings are - identified with :production:`string`. - -Keywords - The following character sequences are reserved keywords that cannot be - used as identifiers:: - - _ Axiom CoFixpoint Definition Fixpoint Hypothesis IF Parameter Prop - SProp Set Theorem Type Variable as at by cofix discriminated else - end exists exists2 fix for forall fun if in lazymatch let match - multimatch return then using where with - - Note that plugins may define additional keywords when they are loaded. - -Other tokens - The set of - tokens defined at any given time can vary because the :cmd:`Notation` - command can define new tokens. A :cmd:`Require` command may load more notation definitions, - while the end of a :cmd:`Section` may remove notations. Some notations - are defined in the basic library (see :ref:`thecoqlibrary`) and are normally - loaded automatically at startup time. - - Here are the character sequences that Coq directly defines as tokens - without using :cmd:`Notation` (omitting 25 specialized tokens that begin with - ``#int63_``):: - - ! #[ % & ' ( () (bfs) (dfs) ) * ** + , - -> - . .( .. ... / : ::= := :> :>> ; < <+ <- <: - <<: <= = => > >-> >= ? @ @{ [ [= ] _ - `( `{ { {| | |- || } - - When multiple tokens match the beginning of a sequence of characters, - the longest matching token is used. - Occasionally you may need to insert spaces to separate tokens. For example, - if ``~`` and ``~~`` are both defined as tokens, the inputs ``~ ~`` and - ``~~`` generate different tokens, whereas if `~~` is not defined, then the - two inputs are equivalent. +definitions of constants, functions, predicates and sets. .. _term: Terms ===== -Syntax of terms ---------------- - -The following grammars describe the basic syntax of the terms of the -*Calculus of Inductive Constructions* (also called Cic). The formal -presentation of Cic is given in Chapter :ref:`calculusofinductiveconstructions`. Extensions of this syntax -are given in Chapter :ref:`extensionsofgallina`. How to customize the syntax -is described in Chapter :ref:`syntaxextensionsandinterpretationscopes`. - -.. insertprodn term field_def - -.. prodn:: - term ::= forall @open_binders , @term - | fun @open_binders => @term - | @term_let - | if @term {? {? as @name } return @term100 } then @term else @term - | @term_fix - | @term_cofix - | @term100 - term100 ::= @term_cast - | @term10 - term10 ::= @term1 {+ @arg } - | @ @qualid {? @univ_annot } {* @term1 } - | @term1 - arg ::= ( @ident := @term ) - | @term1 - one_term ::= @term1 - | @ @qualid {? @univ_annot } - term1 ::= @term_projection - | @term0 % @ident - | @term0 - term0 ::= @qualid {? @univ_annot } - | @sort - | @numeral - | @string - | _ - | @term_evar - | @term_match - | ( @term ) - | %{%| {* @field_def } %|%} - | `%{ @term %} - | `( @term ) - | ltac : ( @ltac_expr ) - field_def ::= @qualid {* @binder } := @term - -.. note:: - - Many commands and tactics use :n:`@one_term` rather than :n:`@term`. - The former need to be enclosed in parentheses unless they're very - simple, such as a single identifier. This avoids confusing a space-separated - list of terms with a :n:`@term1` applied to a list of arguments. - -.. _types: - -Types ------ - -.. prodn:: - type ::= @term - -:n:`@type`\s are a subset of :n:`@term`\s; not every :n:`@term` is a :n:`@type`. -Every term has an associated type, which -can be determined by applying the :ref:`typing-rules`. Distinct terms -may share the same type, for example 0 and 1 are both of type `nat`, the -natural numbers. - .. _gallina-identifiers: Qualified identifiers and simple identifiers @@ -223,9 +39,15 @@ Field identifiers, written :n:`@field_ident`, are identifiers prefixed by Numerals and strings -------------------- +.. insertprodn primitive_notations primitive_notations + +.. prodn:: + primitive_notations ::= @numeral + | @string + Numerals and strings have no predefined semantics in the calculus. They are merely notations that can be bound to objects through the notation mechanism -(see Chapter :ref:`syntaxextensionsandinterpretationscopes` for details). +(see Chapter :ref:`syntax-extensions-and-notation-scopes` for details). Initially, numerals are bound to Peano’s representation of natural numbers (see :ref:`datatypes`). @@ -352,6 +174,12 @@ Section :ref:`let-in`). Products: forall ---------------- +.. insertprodn term_forall_or_fun term_forall_or_fun + +.. prodn:: + term_forall_or_fun ::= forall @open_binders , @term + | fun @open_binders => @term + The expression :n:`forall @ident : @type, @term` denotes the *product* of the variable :n:`@ident` of type :n:`@type`, over the term :n:`@term`. As for abstractions, :g:`forall` is followed by a binder list, and products @@ -373,12 +201,18 @@ the propositional implication and function types. Applications ------------ -The expression :n:`@term__fun @term` denotes the application of -:n:`@term__fun` (which is expected to have a function type) to -:token:`term`. +.. insertprodn term_application arg + +.. prodn:: + term_application ::= @term1 {+ @arg } + | @ @qualid_annotated {+ @term1 } + arg ::= ( @ident := @term ) + | @term1 + +:n:`@term__fun @term` denotes applying the function :n:`@term__fun` to :token:`term`. -The expression :n:`@term__fun {+ @term__i }` denotes the application -of the term :n:`@term__fun` to the arguments :n:`@term__i`. It is +:n:`@term__fun {+ @term__i }` denotes applying +:n:`@term__fun` to the arguments :n:`@term__i`. It is equivalent to :n:`( … ( @term__fun @term__1 ) … ) @term__n`: associativity is to the left. @@ -458,7 +292,7 @@ Definition by cases: match pattern10 ::= @pattern1 as @name | @pattern1 {* @pattern1 } | @ @qualid {* @pattern1 } - pattern1 ::= @pattern0 % @ident + pattern1 ::= @pattern0 % @scope_key | @pattern0 pattern0 ::= @qualid | %{%| {* @qualid := @pattern } %|%} @@ -636,29 +470,6 @@ co-recursion. It is the local counterpart of the :cmd:`CoFixpoint` command. When The Vernacular ============== -.. insertprodn vernacular vernacular - -.. prodn:: - vernacular ::= {* {? @all_attrs } {| @command | @ltac_expr } . } - -The top-level input to |Coq| is a series of :production:`command`\s and :production:`tactic`\s, -each terminated with a period -and optionally decorated with :ref:`gallina-attributes`. :n:`@ltac_expr` syntax supports both simple -and compound tactics. For example: ``split`` is a simple tactic while ``split; auto`` combines two -simple tactics. - -Tactics specify how to transform the current proof state as a step in creating a proof. They -are syntactically valid only when |Coq| is in proof mode, such as after a :cmd:`Theorem` command -and before any subsequent proof-terminating command such as :cmd:`Qed`. See :ref:`proofhandling` for more -on proof mode. - -By convention, command names begin with uppercase letters, while -tactic names begin with lowercase letters. Commands appear in the -HTML documentation in blue boxes after the label "Command". In the pdf, they appear -after the boldface label "Command:". Commands are listed in the :ref:`command_index`. - -Similarly, tactics appear after the label "Tactic". Tactics are listed in the :ref:`tactic_index`. - .. _gallina-assumptions: Assumptions @@ -694,7 +505,7 @@ has type :n:`@type`. of an object of this type) is accepted as a postulate. :cmd:`Axiom`, :cmd:`Conjecture`, :cmd:`Parameter` and their plural forms - are equivalent. They can take the :attr:`local` attribute (see :ref:`gallina-attributes`), + are equivalent. They can take the :attr:`local` :term:`attribute`, which makes the defined :n:`@ident`\s accessible by :cmd:`Import` and its variants only through their fully qualified names. @@ -718,7 +529,7 @@ has type :n:`@type`. :name: @ident already exists. (Axiom) :undocumented: -.. warn:: @ident is declared as a local axiom [local-declaration,scope] +.. warn:: @ident is declared as a local axiom Warning generated when using :cmd:`Variable` or its equivalent instead of :n:`Local Parameter` or its equivalent. @@ -761,7 +572,7 @@ Section :ref:`typing-rules`. | {* @binder } : @type These commands bind :n:`@term` to the name :n:`@ident` in the environment, - provided that :n:`@term` is well-typed. They can take the :attr:`local` attribute (see :ref:`gallina-attributes`), + provided that :n:`@term` is well-typed. They can take the :attr:`local` :term:`attribute`, which makes the defined :n:`@ident` accessible by :cmd:`Import` and its variants only through their fully qualified names. If :n:`@reduce` is present then :n:`@ident` is bound to the result of the specified @@ -1243,7 +1054,7 @@ The ability to define co-inductive types by constructors, hereafter called a bit long: this is due to dependent pattern-matching which implies propositional η-equality, which itself would require full η-conversion for subject reduction to hold, but full η-conversion is not acceptable as it would -make type-checking undecidable. +make type checking undecidable. Since the introduction of primitive records in Coq 8.5, an alternative presentation is available, called *negative co-inductive types*. This consists @@ -1636,82 +1447,6 @@ the proof and adds it to the environment. #. One can also use :cmd:`Admitted` in place of :cmd:`Qed` to turn the current asserted statement into an axiom and exit the proof editing mode. -.. _gallina-attributes: - -Attributes ------------ - -.. insertprodn all_attrs legacy_attr - -.. prodn:: - all_attrs ::= {* #[ {*, @attr } ] } {* @legacy_attr } - attr ::= @ident {? @attr_value } - attr_value ::= = @string - | ( {*, @attr } ) - legacy_attr ::= {| Local | Global } - | {| Polymorphic | Monomorphic } - | {| Cumulative | NonCumulative } - | Private - | Program - -Attributes modify the behavior of a command or tactic. -Syntactically, most commands and tactics can be decorated with attributes, but -attributes not supported by the command or tactic will be flagged as errors. - -The order of top-level attributes doesn't affect their meaning. ``#[foo,bar]``, ``#[bar,foo]``, -``#[foo]#[bar]`` and ``#[bar]#[foo]`` are equivalent. - -The legacy attributes (:n:`@legacy_attr`) provide an older, alternate syntax -for certain attributes. They are equivalent to new attributes as follows: - -================ ================================ -Legacy attribute New attribute -================ ================================ -`Local` :attr:`local` -`Global` :attr:`global` -`Polymorphic` :attr:`universes(polymorphic)` -`Monomorphic` :attr:`universes(monomorphic)` -`Cumulative` :attr:`universes(cumulative)` -`NonCumulative` :attr:`universes(noncumulative)` -`Private` :attr:`private(matching)` -`Program` :attr:`program` -================ ================================ - -.. attr:: deprecated ( {? since = @string , } {? note = @string } ) - :name: deprecated - - At least one of :n:`since` or :n:`note` must be present. If both are present, - either one may appear first and they must be separated by a comma. - - This attribute is supported by the following commands: :cmd:`Ltac`, - :cmd:`Tactic Notation`, :cmd:`Notation`, :cmd:`Infix`. - - It can trigger the following warnings: - - .. warn:: Tactic @qualid is deprecated since @string__since. @string__note. - Tactic Notation @qualid is deprecated since @string__since. @string__note. - Notation @string is deprecated since @string__since. @string__note. - - :n:`@qualid` or :n:`@string` is the notation, :n:`@string__since` is the version number, - :n:`@string__note` is the note (usually explains the replacement). - - .. example:: - - .. coqtop:: all reset warn - - #[deprecated(since="8.9.0", note="Use idtac instead.")] - Ltac foo := idtac. - - Goal True. - Proof. - now foo. - Abort. - -.. warn:: Unsupported attribute - - This warning is an error by default. It is caused by using a - command with some attribute it does not understand. - .. [1] Except if the inductive type is empty in which case there is no equation that can be used to infer the return type. diff --git a/doc/sphinx/practical-tools/coq-commands.rst b/doc/sphinx/practical-tools/coq-commands.rst index 958d295219..58fd49c390 100644 --- a/doc/sphinx/practical-tools/coq-commands.rst +++ b/doc/sphinx/practical-tools/coq-commands.rst @@ -175,14 +175,8 @@ and ``coqtop``, unless stated otherwise: :-refrom *dirpath* *qualid*, -require-export-from *dirpath* *qualid*: Load |Coq| compiled library :n:`@qualid` and transitively import it. This is equivalent to running :n:`From` :n:`@dirpath` :cmd:`Require Export` :n:`@qualid`. :-batch: Exit just after argument parsing. Available for ``coqtop`` only. -:-compile *file.v*: Deprecated; use ``coqc`` instead. Compile file *file.v* into *file.vo*. This option - implies -batch (exit just after argument parsing). It is available only - for `coqtop`, as this behavior is the purpose of ``coqc``. -:-compile-verbose *file.v*: Deprecated. Use ``coqc -verbose``. Same as -compile but also output the - content of *file.v* as it is compiled. :-verbose: Output the content of the input file as it is compiled. - This option is available for ``coqc`` only; it is the counterpart of - -compile-verbose. + This option is available for ``coqc`` only. :-vos: Indicate |Coq| to skip the processing of opaque proofs (i.e., proofs ending with ``Qed`` or ``Admitted``), output a ``.vos`` files instead of a ``.vo`` file, and to load ``.vos`` files instead of ``.vo`` files @@ -380,7 +374,7 @@ Compiled libraries checker (coqchk) ---------------------------------------- The ``coqchk`` command takes a list of library paths as argument, described either -by their logical name or by their physical filename, hich must end in ``.vo``. The +by their logical name or by their physical filename, which must end in ``.vo``. The corresponding compiled libraries (``.vo`` files) are searched in the path, recursively processing the libraries they depend on. The content of all these libraries is then type checked. The effect of ``coqchk`` is only to return with diff --git a/doc/sphinx/practical-tools/coqide.rst b/doc/sphinx/practical-tools/coqide.rst index b1f392c337..42e752841d 100644 --- a/doc/sphinx/practical-tools/coqide.rst +++ b/doc/sphinx/practical-tools/coqide.rst @@ -1,3 +1,5 @@ +.. |GtkSourceView| replace:: :smallcaps:`GtkSourceView` + .. _coqintegrateddevelopmentenvironment: |Coq| Integrated Development Environment @@ -98,19 +100,6 @@ processed color, though their preceding proofs have the processed color. Notice that for all these buttons, except for the "gears" button, their operations are also available in the menu, where their keyboard shortcuts are given. -Proof folding ------------------- - -As your script grows bigger and bigger, it might be useful to hide the -proofs of your theorems and lemmas. - -This feature is toggled via the Hide entry of the Navigation menu. The -proof shall be enclosed between ``Proof.`` and ``Qed.``, both with their final -dots. The proof that shall be hidden or revealed is the first one -whose beginning statement (such as ``Theorem``) precedes the insertion -cursor. - - Vernacular commands, templates ----------------------------------- @@ -158,7 +147,18 @@ presented as a notebook. The first section is for selecting the text font used for scripts, goal and message windows. -The second and third sections are for controlling colors and style. +The second and third sections are for controlling colors and style of +the three main buffers. A predefined |Coq| highlighting style as well +as standard |GtkSourceView| styles are available. Other styles can be +added e.g. in ``$HOME/.local/share/gtksourceview-3.0/styles/`` (see +the general documentation about |GtkSourceView| for the various +possibilities). Note that the style of the rest of graphical part of +Coqide is not under the control of |GtkSourceView| but of GTK+ and +governed by files such as ``settings.ini`` and ``gtk.css`` in +``$XDG_CONFIG_HOME/gtk-3.0`` or files in +``$HOME/.themes/NameOfTheme/gtk-3.0``, as well as the environment +variable ``GTK_THEME`` (search on internet for the various +possibilities). The fourth section is for customizing the editor. It includes in particular the ability to activate an Emacs mode named @@ -206,7 +206,7 @@ Displaying Unicode symbols ~~~~~~~~~~~~~~~~~~~~~~~~~~ You just need to define suitable notations as described in the chapter -:ref:`syntaxextensionsandinterpretationscopes`. For example, to use the +:ref:`syntax-extensions-and-notation-scopes`. For example, to use the mathematical symbols ∀ and ∃, you may define: .. coqtop:: in diff --git a/doc/sphinx/practical-tools/utilities.rst b/doc/sphinx/practical-tools/utilities.rst index d61e5ddce7..408f8fc3ec 100644 --- a/doc/sphinx/practical-tools/utilities.rst +++ b/doc/sphinx/practical-tools/utilities.rst @@ -42,6 +42,8 @@ As of today it is possible to build Coq projects using two tools: - coq_makefile, which is distributed by Coq and is based on generating a makefile, - Dune, the standard OCaml build tool, which, since version 1.9, supports building Coq libraries. +.. _coq_makefile: + Building a |Coq| project with coq_makefile ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -243,16 +245,17 @@ file timing data: COQDEP Fast.v COQDEP Slow.v COQC Slow.v - Slow (user: 0.34 mem: 395448 ko) + Slow.vo (user: 0.34 mem: 395448 ko) COQC Fast.v - Fast (user: 0.01 mem: 45184 ko) + Fast.vo (user: 0.01 mem: 45184 ko) + ``pretty-timed`` this target stores the output of ``make TIMED=1`` into - ``time-of-build.log``, and displays a table of the times, sorted from - slowest to fastest, which is also stored in ``time-of-build-pretty.log``. - If you want to construct the ``log`` for targets other than the default - one, you can pass them via the variable ``TGTS``, e.g., ``make pretty-timed + ``time-of-build.log``, and displays a table of the times and peak + memory usages, sorted from slowest to fastest, which is also + stored in ``time-of-build-pretty.log``. If you want to construct + the ``log`` for targets other than the default one, you can pass + them via the variable ``TGTS``, e.g., ``make pretty-timed TGTS="a.vo b.vo"``. .. note:: @@ -269,24 +272,29 @@ file timing data: ``TIMING_REAL=1`` to ``make pretty-timed`` will use real times rather than user times in the table. + .. note:: + Passing ``TIMING_INCLUDE_MEM=0`` to ``make`` will result in the + tables not including peak memory usage information. Passing + ``TIMING_SORT_BY_MEM=1`` to ``make`` will result in the tables + be sorted by peak memory usage rather than by the time taken. + .. example:: For example, the output of ``make pretty-timed`` may look like this: :: - COQDEP Fast.v - COQDEP Slow.v + COQDEP VFILES COQC Slow.v - Slow (user: 0.36 mem: 393912 ko) + Slow.vo (real: 0.52, user: 0.39, sys: 0.12, mem: 394648 ko) COQC Fast.v - Fast (user: 0.05 mem: 45992 ko) - Time | File Name - -------------------- - 0m00.41s | Total - -------------------- - 0m00.36s | Slow - 0m00.05s | Fast + Fast.vo (real: 0.06, user: 0.02, sys: 0.03, mem: 56980 ko) + Time | Peak Mem | File Name + -------------------------------------------- + 0m00.41s | 394648 ko | Total Time / Peak Mem + -------------------------------------------- + 0m00.39s | 394648 ko | Slow.vo + 0m00.02s | 56980 ko | Fast.vo + ``print-pretty-timed-diff`` @@ -323,7 +331,15 @@ file timing data: .. note:: Just like ``pretty-timed``, this table defaults to using user - times. Pass ``TIMING_REAL=1`` to ``make`` on the command line to show real times instead. + times. Pass ``TIMING_REAL=1`` to ``make`` on the command line + to show real times instead. + + .. note:: + Just like ``pretty-timed``, passing ``TIMING_INCLUDE_MEM=0`` to + ``make`` will result in the tables not including peak memory + usage information. Passing ``TIMING_SORT_BY_MEM=1`` to + ``make`` will result in the tables be sorted by peak memory + usage rather than by the time taken. .. example:: @@ -332,12 +348,12 @@ file timing data: :: - After | File Name | Before || Change | % Change - -------------------------------------------------------- - 0m00.39s | Total | 0m00.35s || +0m00.03s | +11.42% - -------------------------------------------------------- - 0m00.37s | Slow | 0m00.01s || +0m00.36s | +3600.00% - 0m00.02s | Fast | 0m00.34s || -0m00.32s | -94.11% + After | Peak Mem | File Name | Before | Peak Mem || Change || Change (mem) | % Change | % Change (mem) + ----------------------------------------------------------------------------------------------------------------------------- + 0m00.43s | 394700 ko | Total Time / Peak Mem | 0m00.41s | 394648 ko || +0m00.01s || 52 ko | +4.87% | +0.01% + ----------------------------------------------------------------------------------------------------------------------------- + 0m00.39s | 394700 ko | Fast.vo | 0m00.02s | 56980 ko || +0m00.37s || 337720 ko | +1850.00% | +592.69% + 0m00.04s | 56772 ko | Slow.vo | 0m00.39s | 394648 ko || -0m00.35s || -337876 ko | -89.74% | -85.61% The following targets and ``Makefile`` variables allow collection of per- diff --git a/doc/sphinx/proof-engine/detailed-tactic-examples.rst b/doc/sphinx/proof-engine/detailed-tactic-examples.rst index 0ace9ef5b9..b63ae32311 100644 --- a/doc/sphinx/proof-engine/detailed-tactic-examples.rst +++ b/doc/sphinx/proof-engine/detailed-tactic-examples.rst @@ -353,7 +353,7 @@ the optional tactic of the ``Hint Rewrite`` command. .. coqtop:: in reset - Require Import Omega. + Require Import Lia. .. coqtop:: in @@ -367,7 +367,7 @@ the optional tactic of the ``Hint Rewrite`` command. .. coqtop:: in - Hint Rewrite g0 g1 g2 using omega : base1. + Hint Rewrite g0 g1 g2 using lia : base1. .. coqtop:: in diff --git a/doc/sphinx/proof-engine/ltac.rst b/doc/sphinx/proof-engine/ltac.rst index b2b426ada5..b184311bef 100644 --- a/doc/sphinx/proof-engine/ltac.rst +++ b/doc/sphinx/proof-engine/ltac.rst @@ -174,6 +174,14 @@ mode but it can also be used in toplevel definitions as shown below. ltac_def : `ident` [`ident` ... `ident`] := `ltac_expr` : `qualid` [`ident` ... `ident`] ::= `ltac_expr` +Tactics in terms +~~~~~~~~~~~~~~~~ + +.. insertprodn term_ltac term_ltac + +.. prodn:: + term_ltac ::= ltac : ( @ltac_expr ) + .. _ltac-semantics: Semantics @@ -258,6 +266,9 @@ following form: Goal selectors ~~~~~~~~~~~~~~ +.. todo: mention this applies to Print commands and the Info command + + We can restrict the application of a tactic to a subset of the currently focused goals with: @@ -471,7 +482,7 @@ Soft cut ~~~~~~~~ Another way of restricting backtracking is to restrict a tactic to a -single success *a posteriori*: +single success: .. tacn:: once @ltac_expr :name: once @@ -1712,6 +1723,7 @@ performance issue. .. coqtop:: reset in + Set Warnings "-omega-is-deprecated". Require Import Coq.omega.Omega. Ltac mytauto := tauto. @@ -1774,16 +1786,22 @@ performance issue. and allow displaying and resetting the profile from tactic scripts for benchmarking purposes. +.. warn:: Ltac Profiler encountered an invalid stack (no \ + self node). This can happen if you reset the profile during \ + tactic execution + + Currently, :tacn:`reset ltac profile` is not very well-supported, + as it clears all profiling information about all tactics, including + ones above the current tactic. As a result, the profiler has + trouble understanding where it is in tactic execution. This mixes + especially poorly with backtracking into multi-success tactics. In + general, non-top-level calls to :tacn:`reset ltac profile` should + be avoided. + You can also pass the ``-profile-ltac`` command line option to ``coqc``, which turns the :flag:`Ltac Profiling` flag 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 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ diff --git a/doc/sphinx/proof-engine/ltac2.rst b/doc/sphinx/proof-engine/ltac2.rst index 06106a6b4c..1e35160205 100644 --- a/doc/sphinx/proof-engine/ltac2.rst +++ b/doc/sphinx/proof-engine/ltac2.rst @@ -213,25 +213,63 @@ There is dedicated syntax for list and array literals. Ltac Definitions ~~~~~~~~~~~~~~~~ -.. cmd:: Ltac2 {? mutable} {? rec} @lident := @ltac2_term +.. cmd:: Ltac2 {? mutable} {? rec} @lident := @ltac2_value :name: Ltac2 This command defines a new global Ltac2 value. - For semantic reasons, the body of the Ltac2 definition must be a syntactical - value, that is, a function, a constant or a pure constructor recursively applied to - values. + The body of an Ltac2 definition is required to be a syntactical value + that is, a function, a constant, a pure constructor recursively applied to + values or a (non-recursive) let binding of a value in a value. + + .. productionlist:: coq + ltac2_value: fun `ltac2_var` => `ltac2_term` + : `ltac2_qualid` + : `ltac2_constructor` `ltac2_value` ... `ltac2_value` + : `ltac2_var` + : let `ltac2_var` := `ltac2_value` in `ltac2_value` If ``rec`` is set, the tactic is expanded into a recursive binding. If ``mutable`` is set, the definition can be redefined at a later stage (see below). -.. cmd:: Ltac2 Set @qualid := @ltac2_term +.. cmd:: Ltac2 Set @qualid {? as @lident} := @ltac2_term :name: Ltac2 Set This command redefines a previous ``mutable`` definition. Mutable definitions act like dynamic binding, i.e. at runtime, the last defined value for this entry is chosen. This is useful for global flags and the like. + The previous value of the binding can be optionally accessed using the `as` + binding syntax. + + .. example:: Dynamic nature of mutable cells + + .. coqtop:: all + + Ltac2 mutable x := true. + Ltac2 y := x. + Ltac2 Eval y. + Ltac2 Set x := false. + Ltac2 Eval y. + + .. example:: Interaction with recursive calls + + + .. coqtop:: all + + Ltac2 mutable rec f b := match b with true => 0 | _ => f true end. + Ltac2 Set f := fun b => + match b with true => 1 | _ => f true end. + Ltac2 Eval (f false). + Ltac2 Set f as oldf := fun b => + match b with true => 2 | _ => oldf false end. + Ltac2 Eval (f false). + + In the definition, the `f` in the body is resolved statically + because the definition is marked recursive. In the first re-definition, + the `f` in the body is resolved dynamically. This is witnessed by + the second re-definition. + Reduction ~~~~~~~~~ @@ -510,9 +548,9 @@ Static semantics **************** During internalization, Coq variables are resolved and antiquotations are -type-checked as Ltac2 terms, effectively producing a ``glob_constr`` in Coq +type checked as Ltac2 terms, effectively producing a ``glob_constr`` in Coq implementation terminology. Note that although it went through the -type-checking of **Ltac2**, the resulting term has not been fully computed and +type checking of **Ltac2**, the resulting term has not been fully computed and is potentially ill-typed as a runtime **Coq** term. .. example:: @@ -523,12 +561,12 @@ is potentially ill-typed as a runtime **Coq** term. Ltac2 myconstr () := constr:(nat -> 0). -Term antiquotations are type-checked in the enclosing Ltac2 typing context +Term antiquotations are type checked in the enclosing Ltac2 typing context of the corresponding term expression. .. example:: - The following will type-check, with type `constr`. + The following will type check, with type `constr`. .. coqdoc:: @@ -539,7 +577,7 @@ expanded by the Coq binders from the term. .. example:: - The following Ltac2 expression will **not** type-check:: + The following Ltac2 expression will **not** type check:: `constr:(fun x : nat => ltac2:(exact x))` `(* Error: Unbound variable 'x' *)` @@ -583,7 +621,7 @@ Dynamic semantics ***************** During evaluation, a quoted term is fully evaluated to a kernel term, and is -in particular type-checked in the current environment. +in particular type checked in the current environment. Evaluation of a quoted term goes as follows. @@ -602,7 +640,7 @@ whole expression will thus evaluate to the term :g:`fun H : nat => H`. `let tac () := hyp @H in constr:(fun H : nat => ltac2:(tac ()))` -Many standard tactics perform type-checking of their argument before going +Many standard tactics perform type checking of their argument before going further. It is your duty to ensure that terms are well-typed when calling such tactics. Failure to do so will result in non-recoverable exceptions. @@ -700,7 +738,7 @@ The following scopes are built-in. + parses :n:`c = @term` and produces :n:`constr:(c)` - This scope can be parameterized by a list of delimiting keys of interpretation + This scope can be parameterized by a list of delimiting keys of notation scopes (as described in :ref:`LocalInterpretationRulesForNotations`), describing how to interpret the parsed term. For instance, :n:`constr(A, B)` parses :n:`c = @term` and produces :n:`constr:(c%A%B)`. diff --git a/doc/sphinx/proof-engine/proof-handling.rst b/doc/sphinx/proof-engine/proof-handling.rst index 03eebc32f9..cf4d432f64 100644 --- a/doc/sphinx/proof-engine/proof-handling.rst +++ b/doc/sphinx/proof-engine/proof-handling.rst @@ -41,8 +41,8 @@ terms are called *proof terms*. .. _proof-editing-mode: -Switching on/off the proof editing mode -------------------------------------------- +Entering and leaving proof editing mode +--------------------------------------- The proof editing mode is entered by asserting a statement, which typically is the assertion of a theorem using an assertion command like :cmd:`Theorem`. The @@ -90,9 +90,7 @@ list of assertion commands is given in :ref:`Assertions`. The command .. cmd:: Save @ident :name: Save - Forces the name of the original goal to be :token:`ident`. This - command can only be used if the original goal - was opened using the :cmd:`Goal` command. + Forces the name of the original goal to be :token:`ident`. .. cmd:: Admitted @@ -821,7 +819,7 @@ in compacted hypotheses: .. .. image:: ../_static/diffs-coqide-compacted.png - :alt: coqide with Set Diffs on with compacted hyptotheses + :alt: coqide with Set Diffs on with compacted hypotheses Controlling the effect of proof editing commands ------------------------------------------------ diff --git a/doc/sphinx/proof-engine/ssreflect-proof-language.rst b/doc/sphinx/proof-engine/ssreflect-proof-language.rst index 90a991794f..4be18ccda9 100644 --- a/doc/sphinx/proof-engine/ssreflect-proof-language.rst +++ b/doc/sphinx/proof-engine/ssreflect-proof-language.rst @@ -286,7 +286,7 @@ example, the null and all list function(al)s can be defined as follows: .. coqtop:: all Variable d: Set. - Fixpoint null (s : list d) := + Definition null (s : list d) := if s is nil then true else false. Variable a : d -> bool. Fixpoint all (s : list d) : bool := @@ -1624,9 +1624,15 @@ previous :token:`i_item` have been performed. The second entry in the :token:`i_view` grammar rule, ``/ltac:(`` :token:`tactic` ``)``, executes :token:`tactic`. -Notations can be used to name tactics, for example:: +Notations can be used to name tactics, for example - Notation myop := (ltac:(some ltac code)) : ssripat_scope. +.. coqtop:: none + + Tactic Notation "my" "ltac" "code" := idtac. + +.. coqtop:: in warn + + Notation "'myop'" := (ltac:(my ltac code)) : ssripat_scope. lets one write just ``/myop`` in the intro pattern. Note the scope annotation: views are interpreted opening the ``ssripat`` scope. @@ -2607,7 +2613,7 @@ After the :token:`i_pattern`, a list of binders is allowed. .. coqtop:: reset none From Coq Require Import ssreflect. - From Coq Require Import Omega. + From Coq Require Import ZArith Lia. Set Implicit Arguments. Unset Strict Implicit. Unset Printing Implicit Defensive. @@ -2615,7 +2621,7 @@ After the :token:`i_pattern`, a list of binders is allowed. .. coqtop:: all Lemma test : True. - have H x (y : nat) : 2 * x + y = x + x + y by omega. + have H x (y : nat) : 2 * x + y = x + x + y by lia. A proof term provided after ``:=`` can mention these bound variables (that are automatically introduced with the given names). @@ -2625,7 +2631,7 @@ with parentheses even if no type is specified: .. coqtop:: all restart - have (x) : 2 * x = x + x by omega. + have (x) : 2 * x = x + x by lia. The :token:`i_item` and :token:`s_item` can be used to interpret the asserted hypothesis with views (see section :ref:`views_and_reflection_ssr`) or simplify the resulting @@ -2668,9 +2674,9 @@ context entry name. Arguments Sub {_} _ _. Lemma test n m (H : m + 1 < n) : True. - have @i : 'I_n by apply: (Sub m); omega. + have @i : 'I_n by apply: (Sub m); lia. -Note that the subterm produced by :tacn:`omega` is in general huge and +Note that the subterm produced by :tacn:`lia` is in general huge and uninteresting, and hence one may want to hide it. For this purpose the ``[: name ]`` intro pattern and the tactic ``abstract`` (see :ref:`abstract_ssr`) are provided. @@ -2680,7 +2686,7 @@ For this purpose the ``[: name ]`` intro pattern and the tactic .. coqtop:: all abort Lemma test n m (H : m + 1 < n) : True. - have [:pm] @i : 'I_n by apply: (Sub m); abstract: pm; omega. + have [:pm] @i : 'I_n by apply: (Sub m); abstract: pm; lia. The type of ``pm`` can be cleaned up by its annotation ``(*1*)`` by just simplifying it. The annotations are there for technical reasons only. @@ -2694,7 +2700,7 @@ with have and an explicit term, they must be used as follows: Lemma test n m (H : m + 1 < n) : True. have [:pm] @i : 'I_n := Sub m pm. - by omega. + by lia. In this case the abstract constant ``pm`` is assigned by using it in the term that follows ``:=`` and its corresponding goal is left to be @@ -2712,7 +2718,7 @@ makes use of it). .. coqtop:: all abort Lemma test n m (H : m + 1 < n) : True. - have [:pm] @i k : 'I_(n+k) by apply: (Sub m); abstract: pm k; omega. + have [:pm] @i k : 'I_(n+k) by apply: (Sub m); abstract: pm k; lia. Last, notice that the use of intro patterns for abstract constants is orthogonal to the transparent flag ``@`` for have. @@ -2963,7 +2969,7 @@ illustrated in the following example. .. coqtop:: reset none - From Coq Require Import ssreflect Omega. + From Coq Require Import ssreflect Lia. Set Implicit Arguments. Unset Strict Implicit. Unset Printing Implicit Defensive. diff --git a/doc/sphinx/proof-engine/tactics.rst b/doc/sphinx/proof-engine/tactics.rst index 19573eee43..439f7fb9f6 100644 --- a/doc/sphinx/proof-engine/tactics.rst +++ b/doc/sphinx/proof-engine/tactics.rst @@ -51,6 +51,11 @@ specified, the default selector is used. tactic_invocation : `toplevel_selector` : `tactic`. : `tactic`. +.. todo: fully describe selectors. At the moment, ltac has a fairly complete description + +.. todo: mention selectors can be applied to some commands, such as + Check, Search, SearchHead, SearchPattern, SearchRewrite. + .. opt:: Default Goal Selector "@toplevel_selector" :name: Default Goal Selector @@ -1870,6 +1875,7 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) Lemma induction_test : forall n:nat, n = n -> n <= n. intros n H. induction n. + exact (le_n 0). .. exn:: Not an inductive product. :undocumented: @@ -2071,7 +2077,7 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) Now we are in a contradictory context and the proof can be solved. - .. coqtop:: all + .. coqtop:: all abort inversion H. @@ -2099,68 +2105,7 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) See also the larger example of :tacn:`dependent induction` and an explanation of the underlying technique. -.. tacn:: function induction (@qualid {+ @term}) - :name: function induction - - 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:`advanced-recursive-functions`) or - ``Functional Scheme`` (see :ref:`functional-scheme`). - Note that this tactic is only available after a ``Require Import FunInd``. - -.. example:: - - .. coqtop:: reset all - - Require Import FunInd. - Functional Scheme minus_ind := Induction for minus Sort Prop. - Check minus_ind. - Lemma le_minus (n m:nat) : n - m <= n. - functional induction (minus n m) using minus_ind; simpl; auto. - Qed. - -.. note:: - :n:`(@qualid {+ @term})` must be a correct full application - of :n:`@qualid`. In particular, the rules for implicit arguments are the - same as usual. For example use :n:`@qualid` if you want to write implicit - arguments explicitly. - -.. note:: - Parentheses around :n:`@qualid {+ @term}` are not mandatory and can be skipped. - -.. note:: - :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:`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:`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:`advanced-recursive-functions`) - and by using :g:`Functional Scheme` after a normal definition using - :g:`Fixpoint` or :g:`Definition`. See :ref:`advanced-recursive-functions` - for details. - -.. seealso:: :ref:`advanced-recursive-functions`, :ref:`functional-scheme` and :tacn:`inversion` - -.. exn:: Cannot find induction information on @qualid. - :undocumented: - -.. exn:: Not the right number of induction arguments. - :undocumented: - -.. tacv:: functional induction (@qualid {+ @term}) as @simple_intropattern using @term with @bindings_list - - Similarly to :tacn:`induction` and :tacn:`elim`, this allows giving - explicitly the name of the introduced variables, the induction principle, and - the values of dependent premises of the elimination scheme, including - *predicates* for mutual induction when :n:`@qualid` is part of a mutually - recursive definition. +.. seealso:: :tacn:`functional induction` .. tacn:: discriminate @term :name: discriminate @@ -2667,6 +2612,8 @@ and an explanation of the underlying technique. assumption. Qed. +.. seealso:: :tacn:`functional inversion` + .. tacn:: fix @ident @num :name: fix @@ -2885,6 +2832,11 @@ simply :g:`t=u` dropping the implicit type of :g:`t` and :g:`u`. If :n:`@ident` is a local definition of the form :n:`@ident := t`, it is also unfolded and cleared. + If :n:`@ident` is a section variable it is expected to have no + indirect occurrences in the goal, i.e. that no global declarations + implicitly depending on the section variable must be present in the + goal. + .. note:: + When several hypotheses have the form :n:`@ident = t` or :n:`t = @ident`, the first one is used. @@ -2898,9 +2850,11 @@ simply :g:`t=u` dropping the implicit type of :g:`t` and :g:`u`. .. tacv:: subst - This applies subst repeatedly from top to bottom to all identifiers of the + This applies :tacn:`subst` repeatedly from top to bottom to all hypotheses of the context for which an equality of the form :n:`@ident = t` or :n:`t = @ident` - or :n:`@ident := t` exists, with :n:`@ident` not occurring in ``t``. + or :n:`@ident := t` exists, with :n:`@ident` not occurring in + ``t`` and :n:`@ident` not a section variable with indirect + dependencies in the goal. .. flag:: Regular Subst Tactic @@ -2926,6 +2880,15 @@ simply :g:`t=u` dropping the implicit type of :g:`t` and :g:`u`. hypotheses, which without the flag it may break. default. + .. exn:: Cannot find any non-recursive equality over :n:`@ident`. + :undocumented: + + .. exn:: Section variable :n:`@ident` occurs implicitly in global declaration :n:`@qualid` present in hypothesis :n:`@ident`. + Section variable :n:`@ident` occurs implicitly in global declaration :n:`@qualid` present in the conclusion. + + Raised when the variable is a section variable with indirect + dependencies in the goal. + .. tacn:: stepl @term :name: stepl @@ -3032,8 +2995,8 @@ following: For backward compatibility, the notation :n:`in {+ @ident}` performs the conversion in hypotheses :n:`{+ @ident}`. -.. tacn:: cbv {* @flag} - lazy {* @flag} +.. tacn:: {? @strategy_flag } + lazy {? @strategy_flag } :name: cbv; lazy These parameterized reduction tactics apply to any goal and perform @@ -3129,8 +3092,10 @@ the conversion in hypotheses :n:`{+ @ident}`. .. flag:: NativeCompute Timing This flag causes all calls to the native compiler to print - timing information for the compilation, execution, and - reification phases of native compilation. + timing information for the conversion to native code, + compilation, execution, and reification phases of native + compilation. Timing is printed in units of seconds of + wall-clock time. .. flag:: NativeCompute Profiling @@ -3180,6 +3145,7 @@ the conversion in hypotheses :n:`{+ @ident}`. head normal form according to the :math:`\beta`:math:`\delta`:math:`\iota`:math:`\zeta`-reduction rules, i.e. it reduces the head of the goal until it becomes a product or an irreducible term. All inner :math:`\beta`:math:`\iota`-redexes are also reduced. + The behavior of both :tacn:`hnf` can be tuned using the :cmd:`Arguments` command. Example: The term :g:`fun n : nat => S n + S n` is not reduced by :n:`hnf`. @@ -3206,76 +3172,10 @@ the conversion in hypotheses :n:`{+ @ident}`. The :tacn:`cbn` tactic accepts the same flags as :tacn:`cbv` and :tacn:`lazy`. The behavior of both :tacn:`simpl` and :tacn:`cbn` - can be tuned using the Arguments vernacular command as follows: - - + A constant can be marked to be never unfolded by :tacn:`cbn` or - :tacn:`simpl`: - - .. example:: - - .. coqtop:: all - - Arguments minus n m : simpl never. - - After that command an expression like :g:`(minus (S x) y)` is left - untouched by the tactics :tacn:`cbn` and :tacn:`simpl`. - - + A constant can be marked to be unfolded only if applied to enough - arguments. The number of arguments required can be specified using the - ``/`` symbol in the argument list of the :cmd:`Arguments` command. - - .. example:: - - .. coqtop:: all - - Definition fcomp A B C f (g : A -> B) (x : A) : C := f (g x). - Arguments fcomp {A B C} f g x /. - Notation "f \o g" := (fcomp f g) (at level 50). - - After that command the expression :g:`(f \o g)` is left untouched by - :tacn:`simpl` while :g:`((f \o g) t)` is reduced to :g:`(f (g t))`. - The same mechanism can be used to make a constant volatile, i.e. - always unfolded. - - .. example:: - - .. coqtop:: all - - Definition volatile := fun x : nat => x. - Arguments volatile / x. - - + A constant can be marked to be unfolded only if an entire set of - arguments evaluates to a constructor. The ``!`` symbol can be used to mark - such arguments. - - .. example:: - - .. coqtop:: all - - Arguments minus !n !m. - - After that command, the expression :g:`(minus (S x) y)` is left untouched - by :tacn:`simpl`, while :g:`(minus (S x) (S y))` is reduced to :g:`(minus x y)`. - - + A special heuristic to determine if a constant has to be unfolded - can be activated with the following command: - - .. example:: - - .. coqtop:: all - - Arguments minus n m : simpl nomatch. - - The heuristic avoids to perform a simplification step that would expose a - match construct in head position. For example the expression - :g:`(minus (S (S x)) (S y))` is simplified to :g:`(minus (S x) y)` - even if an extra simplification is possible. + can be tuned using the :cmd:`Arguments` command. - In detail, the tactic :tacn:`simpl` first applies :math:`\beta`:math:`\iota`-reduction. Then, it - expands transparent constants and tries to reduce further using :math:`\beta`:math:`\iota`-reduction. - But, when no :math:`\iota` rule is applied after unfolding then - :math:`\delta`-reductions are not applied. For instance trying to use :tacn:`simpl` on - :g:`(plus n O) = n` changes nothing. + .. todo add "See <subsection about controlling the behavior of reduction strategies>" + to TBA section Notice that only transparent constants whose name can be reused in the recursive calls are possibly unfolded by :tacn:`simpl`. For instance a @@ -3471,6 +3371,128 @@ the conversion in hypotheses :n:`{+ @ident}`. This is the most general syntax that combines the different variants. +.. tacn:: with_strategy @strategy_level_or_var [ {+ @smart_qualid } ] @ltac_expr3 + :name: with_strategy + + Executes :token:`ltac_expr3`, applying the alternate unfolding + behavior that the :cmd:`Strategy` command controls, but only for + :token:`ltac_expr3`. This can be useful for guarding calls to + reduction in tactic automation to ensure that certain constants are + never unfolded by tactics like :tacn:`simpl` and :tacn:`cbn` or to + ensure that unfolding does not fail. + + .. note:: + + This tactic unfortunately does not yet play well with tactic + internalization, resulting in interpretation-time errors when + you try to use it directly with opaque identifiers, as seen in + the first (failing) use of :tacn:`with_strategy` in the + following example. This can be worked around by binding the + identifier to an |Ltac| variable, and this issue should + disappear in a future version of |Coq|; see `#12179 + <https://github.com/coq/coq/issues/12179>`_. + + .. example:: + + .. coqtop:: all reset abort + + Opaque id. + Goal id 10 = 10. + Fail unfold id. + Fail with_strategy transparent [id] unfold id. + let id' := id in with_strategy transparent [id] unfold id'. + + .. warning:: + + Use this tactic with care, as effects do not persist past the + end of the proof script. Notably, this fine-tuning of the + conversion strategy is not in effect during :cmd:`Qed` nor + :cmd:`Defined`, so this tactic is most useful either in + combination with :tacn:`abstract`, which will check the proof + early while the fine-tuning is still in effect, or to guard + calls to conversion in tactic automation to ensure that, e.g., + :tacn:`unfold` does not fail just because the user made a + constant :cmd:`Opaque`. + + This can be illustrated with the following example involving the + factorial function. + + .. coqtop:: in reset + + Fixpoint fact (n : nat) : nat := + match n with + | 0 => 1 + | S n' => n * fact n' + end. + + Suppose now that, for whatever reason, we want in general to + unfold the :g:`id` function very late during conversion: + + .. coqtop:: in + + Strategy 1000 [id]. + + If we try to prove :g:`id (fact n) = fact n` by + :tacn:`reflexivity`, it will now take time proportional to + :math:`n!`, because |Coq| will keep unfolding :g:`fact` and + :g:`*` and :g:`+` before it unfolds :g:`id`, resulting in a full + computation of :g:`fact n` (in unary, because we are using + :g:`nat`), which takes time :math:`n!`. We can see this cross + the relevant threshold at around :math:`n = 9`: + + .. coqtop:: all abort + + Goal True. + Time assert (id (fact 8) = fact 8) by reflexivity. + Time assert (id (fact 9) = fact 9) by reflexivity. + + Note that behavior will be the same if you mark :g:`id` as + :g:`Opaque` because while most reduction tactics refuse to + unfold :g:`Opaque` constants, conversion treats :g:`Opaque` as + merely a hint to unfold this constant last. + + We can get around this issue by using :tacn:`with_strategy`: + + .. coqtop:: all + + Goal True. + Fail Timeout 1 assert (id (fact 100) = fact 100) by reflexivity. + Time assert (id (fact 100) = fact 100) by with_strategy -1 [id] reflexivity. + + However, when we go to close the proof, we will run into + trouble, because the reduction strategy changes are local to the + tactic passed to :tacn:`with_strategy`. + + .. coqtop:: all abort fail + + exact I. + Timeout 1 Defined. + + We can fix this issue by using :tacn:`abstract`: + + .. coqtop:: all + + Goal True. + Time assert (id (fact 100) = fact 100) by with_strategy -1 [id] abstract reflexivity. + exact I. + Time Defined. + + On small examples this sort of behavior doesn't matter, but + because |Coq| is a super-linear performance domain in so many + places, unless great care is taken, tactic automation using + :tacn:`with_strategy` may not be robustly performant when + scaling the size of the input. + + .. warning:: + + In much the same way this tactic does not play well with + :cmd:`Qed` and :cmd:`Defined` without using :tacn:`abstract` as + an intermediary, this tactic does not play well with ``coqchk``, + even when used with :tacn:`abstract`, due to the inability of + tactics to persist information about conversion hints in the + proof term. See `#12200 + <https://github.com/coq/coq/issues/12200>`_ for more details. + Conversion tactics applied to hypotheses ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -4003,10 +4025,10 @@ At Coq startup, only the core database is nonempty and can be used. :arith: This database contains all lemmas about Peano’s arithmetic proved in the directories Init and Arith. -:zarith: contains lemmas about binary signed integers from the directories - theories/ZArith. When required, the module Omega also extends the - database zarith with a high-cost hint that calls ``omega`` on equations - and inequalities in ``nat`` or ``Z``. +:zarith: contains lemmas about binary signed integers from the + directories theories/ZArith. The database also contains + high-cost hints that call :tacn:`lia` on equations and + inequalities in ``nat`` or ``Z``. :bool: contains lemmas about booleans, mostly from directory theories/Bool. @@ -4597,42 +4619,6 @@ symbol :g:`=`. Analogous to :tacn:`dependent rewrite ->` but uses the equality from right to left. -Inversion ---------- - -.. tacn:: functional inversion @ident - :name: functional 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:`advanced-recursive-functions`). Note that this tactic is only - available after a ``Require Import FunInd``. - - .. exn:: Hypothesis @ident must contain at least one Function. - :undocumented: - - .. exn:: Cannot find inversion information for hypothesis @ident. - - This error may be raised when some inversion lemma failed to be generated by - Function. - - - .. tacv:: functional inversion @num - - This does the same thing as :n:`intros until @num` followed by - :n:`functional inversion @ident` where :token:`ident` is the - identifier for the last introduced hypothesis. - - .. tacv:: functional inversion @ident @qualid - functional inversion @num @qualid - - If the hypothesis :token:`ident` (or :token:`num`) has a type of the form - :n:`@qualid__1 {+ @term__i } = @qualid__2 {+ @term__j }` where - :n:`@qualid__1` and :n:`@qualid__2` are valid candidates to - functional inversion, this variant allows choosing which :token:`qualid` - is inverted. - Classical tactics ----------------- @@ -4689,18 +4675,6 @@ Automating The goal is not of the form :g:`t = u`. Especially note that :tacn:`btauto` doesn't introduce variables into the context on its own. -.. tacn:: omega - :name: omega - - The tactic :tacn:`omega`, due to Pierre Crégut, is an automatic decision - procedure for Presburger arithmetic. It solves quantifier-free - 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:`omega`). - - .. tacn:: ring :name: ring diff --git a/doc/sphinx/proof-engine/vernacular-commands.rst b/doc/sphinx/proof-engine/vernacular-commands.rst index dacfcb3d5f..7191444bac 100644 --- a/doc/sphinx/proof-engine/vernacular-commands.rst +++ b/doc/sphinx/proof-engine/vernacular-commands.rst @@ -6,18 +6,28 @@ Vernacular commands .. _displaying: Displaying --------------- +---------- .. _Print: -.. cmd:: Print @qualid - :name: Print +.. cmd:: Print {? Term } @smart_qualid {? @univ_name_list } + + .. insertprodn univ_name_list univ_name_list + + .. prodn:: + univ_name_list ::= @%{ {* @name } %} - This command displays on the screen information about the declared or - defined object referred by :n:`@qualid`. + Displays definitions of terms, including opaque terms, for the object :n:`@smart_qualid`. - Error messages: + * :n:`Term` - a syntactic marker to allow printing a term + that is the same as one of the various :n:`Print` commands. For example, + :cmd:`Print All` is a different command, while :n:`Print Term All` shows + information on the object whose name is ":n:`All`". + + * :n:`@univ_name_list` - locally renames the + polymorphic universes of :n:`@smart_qualid`. + The name `_` means the usual name is printed. .. exn:: @qualid not a defined object. :undocumented: @@ -29,350 +39,146 @@ Displaying :undocumented: - .. cmdv:: Print Term @qualid - :name: Print Term - - This is a synonym of :cmd:`Print` :n:`@qualid` when :n:`@qualid` - denotes a global constant. - - .. cmdv:: Print {? Term } @qualid\@@name - - This locally renames the polymorphic universes of :n:`@qualid`. - An underscore means the usual name is printed. - - -.. cmd:: About @qualid - :name: About - - This displays various information about the object - denoted by :n:`@qualid`: its kind (module, constant, assumption, inductive, - constructor, abbreviation, …), long name, type, implicit arguments and - argument scopes. It does not print the body of definitions or proofs. - - .. cmdv:: About @qualid\@@name - - This locally renames the polymorphic universes of :n:`@qualid`. - An underscore means the usual name is printed. - - .. cmd:: Print All This command displays information about the current state of the environment, including sections and modules. - .. cmdv:: Inspect @num - :name: Inspect - - This command displays the :n:`@num` last objects of the - current environment, including sections and modules. - - .. cmdv:: Print Section @ident - - The name :n:`@ident` should correspond to a currently open section, - this command displays the objects defined since the beginning of this - section. - - -.. _flags-options-tables: - -Flags, Options and Tables ------------------------------ - -Coq has many settings to control its behavior. Setting types include flags, options -and tables: - -* A :production:`flag` has a boolean value, such as :flag:`Asymmetric Patterns`. -* An :production:`option` generally has a numeric or string value, such as :opt:`Firstorder Depth`. -* A :production:`table` contains a set of strings or qualids. -* In addition, some commands provide settings, such as :cmd:`Extraction Language`. - -.. FIXME Convert "Extraction Language" to an option. - -Flags, options and tables are identified by a series of identifiers, each with an initial -capital letter. - -.. cmd:: Set @flag - :name: Set - - Sets :token:`flag` on. - -.. cmd:: Unset @flag - :name: Unset - - Sets :token:`flag` off. - -.. cmd:: Test @flag - - Prints the current value of :token:`flag`. - - -.. cmd:: Set @option {| @num | @string } - :name: Set @option - - Sets :token:`option` to the specified value. - -.. cmd:: Unset @option - :name: Unset @option - - Sets :token:`option` to its default value. - -.. cmd:: Test @option - - Prints the current value of :token:`option`. - -.. cmd:: Print Options - - Prints the current value of all flags and options, and the names of all tables. - +.. cmd:: Inspect @num -.. cmd:: Add @table {| @string | @qualid } - :name: Add @table + This command displays the :n:`@num` last objects of the + current environment, including sections and modules. - Adds the specified value to :token:`table`. +.. cmd:: Print Section @qualid -.. cmd:: Remove @table {| @string | @qualid } - :name: Remove @table + Displays the objects defined since the beginning of the section named :n:`@qualid`. - Removes the specified value from :token:`table`. + .. todo: "A.B" is permitted but unnecessary for modules/sections. + should the command just take an @ident? -.. cmd:: Test @table for {| @string | @qualid } - :name: Test @table for - - Reports whether :token:`table` contains the specified value. - -.. cmd:: Print Table @table - :name: Print Table @table - - Prints the values in :token:`table`. - -.. cmd:: Test @table - - A synonym for :cmd:`Print Table @table`. - -.. cmd:: Print Tables - - A synonym for :cmd:`Print Options`. - -Locality attributes supported by :cmd:`Set` and :cmd:`Unset` -```````````````````````````````````````````````````````````` - -The :cmd:`Set` and :cmd:`Unset` commands support the :attr:`local`, -:attr:`global` and :attr:`export` locality attributes: - -* no attribute: the original setting is *not* restored at the end of - the current module or section. -* :attr:`local` (an alternative syntax is to use the ``Local`` - prefix): the setting is applied within the current module or - section. The original value of the setting is restored at the end - of the current module or section. -* :attr:`export` (an alternative syntax is to use the ``Export`` - prefix): similar to :attr:`local`, the original value of the setting - is restored at the end of the current module or section. In - addition, if the value is set in a module, then :cmd:`Import`\-ing - the module sets the option or flag. -* :attr:`global` (an alternative syntax is to use the ``Global`` - prefix): the original setting is *not* restored at the end of the - current module or section. In addition, if the value is set in a - file, then :cmd:`Require`\-ing the file sets the option. - -Newly opened modules and sections inherit the current settings. - -.. note:: +Query commands +-------------- - The use of the :attr:`global` attribute with the :cmd:`Set` and - :cmd:`Unset` commands is discouraged. If your goal is to define - project-wide settings, you should rather use the command-line - arguments ``-set`` and ``-unset`` for setting flags and options - (cf. :ref:`command-line-options`). +Unlike other commands, :production:`query_command`\s may be prefixed with +a goal selector (:n:`@num:`) to specify which goal context it applies to. +If no selector is provided, +the command applies to the current goal. If no proof is open, then the command only applies +to accessible objects. (see Section :ref:`invocation-of-tactics`). -.. _requests-to-the-environment: +.. cmd:: About @smart_qualid {? @univ_name_list } -Requests to the environment -------------------------------- + Displays information about the :n:`@smart_qualid` object, which, + if a proof is open, may be a hypothesis of the selected goal, + or an accessible theorem, axiom, etc.: + its kind (module, constant, assumption, inductive, + constructor, abbreviation, …), long name, type, implicit arguments and + argument scopes (as set in the definition of :token:`smart_qualid` or + subsequently with the :cmd:`Arguments` command). It does not print the body of definitions or proofs. .. 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. - - .. cmdv:: @selector: Check @term - - This variant specifies on which subgoal to perform typing - (see Section :ref:`invocation-of-tactics`). - + Displays the type of :n:`@term`. When called in proof mode, the + term is checked in the local context of the selected goal. .. cmd:: Eval @red_expr 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). + Performs the specified reduction on :n:`@term` and displays + the resulting term with its type. If a proof is open, :n:`@term` + may reference hypotheses of the selected goal. .. seealso:: Section :ref:`performingcomputations`. .. cmd:: Compute @term - This command performs a call-by-value evaluation of term by using the - bytecode-based virtual machine. It is a shortcut for ``Eval vm_compute in`` - :n:`@term`. + Evaluates :n:`@term` using the bytecode-based virtual machine. + It is a shortcut for :cmd:`Eval` :n:`vm_compute in @term`. .. seealso:: Section :ref:`performingcomputations`. +.. cmd:: Search {+ {? - } @search_item } {? {| inside | outside } {+ @qualid } } -.. cmd:: Print Assumptions @qualid - - This commands display all the assumptions (axioms, parameters and - variables) a theorem or definition depends on. Especially, it informs - on the assumptions with respect to which the validity of a theorem - relies. - - .. cmdv:: Print Opaque Dependencies @qualid - :name: Print Opaque Dependencies - - Displays the set of opaque constants :n:`@qualid` relies on in addition to - the assumptions. - - .. cmdv:: Print Transparent Dependencies @qualid - :name: Print Transparent Dependencies - - Displays the set of transparent constants :n:`@qualid` relies on - in addition to the assumptions. - - .. cmdv:: Print All Dependencies @qualid - :name: Print All Dependencies - - Displays all assumptions and constants :n:`@qualid` relies on. - - -.. cmd:: Search @qualid + .. insertprodn search_item search_item - 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. + .. prodn:: + search_item ::= @one_term + | @string {? % @scope_key } - .. exn:: The reference @qualid was not found in the current environment. - - There is no constant in the environment named qualid. - - .. cmdv:: Search @string - - If :n:`@string` is a valid identifier, this command - displays the name and type of all objects (theorems, axioms, etc) of - the current context whose name contains string. If string is a - notation’s string denoting some reference :n:`@qualid` (referred to by its - main symbol as in `"+"` or by its notation’s string as in `"_ + _"` or - `"_ 'U' _"`, see Section :ref:`notations`), the command works like ``Search`` :n:`@qualid`. - - .. cmdv:: Search @string%@ident + Displays the name and type of all hypotheses of the + selected goal (if any) and theorems of the current context + matching :n:`@search_item`\s. + It's useful for finding the names 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 :token:`ident` (see Section :ref:`LocalInterpretationRulesForNotations`). + * :n:`@one_term` - Search for objects containing a subterm matching the pattern + :n:`@one_term` in which holes of the pattern are indicated by `_` or :n:`?@ident`. + If the same :n:`?@ident` occurs more than once in the pattern, all occurrences must + match the same value. - .. cmdv:: Search @term_pattern + * :n:`@string` - If :n:`@string` is a substring of a valid identifier, + search for objects whose name contains :n:`@string`. If :n:`@string` is a notation + string associated with a :n:`@qualid`, that's equivalent to :cmd:`Search` :n:`@qualid`. + For example, specifying `"+"` or `"_ + _"`, which are notations for `Nat.add`, are equivalent + to :cmd:`Search` `Nat.add`. - This searches for all statements or types of - definition that contains a subterm that matches the pattern - :token:`term_pattern` (holes of the pattern are either denoted by `_` or by - :n:`?@ident` when non linear patterns are expected). + * :n:`% @scope` - limits the search to the scope bound to + the delimiting key :n:`@scope`, such as, for example, :n:`%nat`. + This clause may be used only if :n:`@string` contains a notation string. + (see Section :ref:`LocalInterpretationRulesForNotations`) - .. cmdv:: Search {+ {? -}@term_pattern_string} + If you specify multiple :n:`@search_item`\s, all the conditions must be satisfied + for the object to be displayed. The minus sign `-` excludes objects that contain + the :n:`@search_item`. - 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. + Additional clauses: - .. cmdv:: Search {+ {? -}@term_pattern_string} inside {+ @qualid } + * :n:`inside {+ @qualid }` - limit the search to the specified modules + * :n:`outside {+ @qualid }` - exclude the specified modules from the search - This restricts the search to constructions defined in the modules - named by the given :n:`qualid` sequence. - - .. cmdv:: Search {+ {? -}@term_pattern_string} outside {+ @qualid } - - This restricts the search to constructions not defined in the modules - named by the given :n:`qualid` sequence. - - .. cmdv:: @selector: Search {+ {? -}@term_pattern_string} - - 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. + .. exn:: Module/section @qualid not found. - .. example:: + There is no constant in the environment named :n:`@qualid`, where :n:`@qualid` + is in an `inside` or `outside` clause. - .. coqtop:: in + .. example:: :cmd:`Search` examples - Require Import ZArith. + .. coqtop:: in - .. coqtop:: all + Require Import ZArith. - Search Z.mul Z.add "distr". + .. coqtop:: all - Search "+"%Z "*"%Z "distr" -positive -Prop. + Search Z.mul Z.add "distr". + Search "+"%Z "*"%Z "distr" -Prop. + Search (?x * _ + ?x * _)%Z outside OmegaLemmas. - Search (?x * _ + ?x * _)%Z outside OmegaLemmas. +.. cmd:: SearchHead @one_term {? {| inside | outside } {+ @qualid } } -.. cmd:: SearchHead @term + Displays the name and type of all hypotheses of the + selected goal (if any) and theorems of the current context that have the + form :n:`{? forall {* @binder }, } {* P__i -> } C` where :n:`@one_term` + matches a prefix of `C`. For example, a :n:`@one_term` of `f _ b` + matches `f a b`, which is a prefix of `C` when `C` is `f a b c`. - 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. + See :cmd:`Search` for an explanation of the `inside`/`outside` clauses. - .. example:: + .. example:: :cmd:`SearchHead` examples .. coqtop:: reset all SearchHead le. - SearchHead (@eq bool). - .. cmdv:: SearchHead @term inside {+ @qualid } - - This restricts the search to constructions defined in the modules named - by the given :n:`qualid` sequence. - - .. cmdv:: SearchHead @term outside {+ @qualid } - - This restricts the search to constructions not defined in the modules - named by the given :n:`qualid` sequence. - - .. exn:: Module/section @qualid not found. - - No module :n:`@qualid` has been required (see Section :ref:`compiled-files`). - - .. cmdv:: @selector: SearchHead @term +.. cmd:: SearchPattern @one_term {? {| inside | outside } {+ @qualid } } - 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. + Displays the name and type of all hypotheses of the + selected goal (if any) and theorems of the current context + ending with :n:`{? forall {* @binder }, } {* P__i -> } C` that match the pattern + :n:`@one_term`. - .. note:: Up to |Coq| version 8.4, ``SearchHead`` was named ``Search``. + See :cmd:`Search` for an explanation of the `inside`/`outside` clauses. - -.. cmd:: SearchPattern @term - - This command displays the name and type of all hypothesis of the - current goal (if any) and theorems of the current context whose - statement’s conclusion or last hypothesis and conclusion matches the - expressionterm where holes in the latter are denoted by `_`. - It is a variant of :n:`Search @term_pattern` that does not look for subterms - but searches for statements whose conclusion has exactly the expected - form, or whose statement finishes by the given series of - hypothesis/conclusion. - - .. example:: + .. example:: :cmd:`SearchPattern` examples .. coqtop:: in @@ -381,123 +187,118 @@ Requests to the environment .. coqtop:: all SearchPattern (_ + _ = _ + _). - SearchPattern (nat -> bool). - SearchPattern (forall l : list _, _ l l). - Patterns need not be linear: you can express that the same expression - must occur in two places by using pattern variables `?ident`. - - - .. example:: - .. coqtop:: all SearchPattern (?X1 + _ = _ + ?X1). - .. cmdv:: SearchPattern @term inside {+ @qualid } +.. cmd:: SearchRewrite @one_term {? {| inside | outside } {+ @qualid } } + + Displays the name and type of all hypotheses of the + selected goal (if any) and theorems of the current context that have the form + :n:`{? forall {* @binder }, } {* P__i -> } LHS = RHS` where :n:`@one_term` + matches either `LHS` or `RHS`. + + See :cmd:`Search` for an explanation of the `inside`/`outside` clauses. - This restricts the search to constructions defined in the modules - named by the given :n:`qualid` sequence. + .. example:: :cmd:`SearchRewrite` examples - .. cmdv:: SearchPattern @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. - .. cmdv:: @selector: SearchPattern @term + .. coqtop:: all - 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. + SearchRewrite (_ + _ + _). +.. table:: Search Blacklist @string + :name: Search Blacklist -.. cmd:: SearchRewrite @term + Specifies a set of strings used to exclude lemmas from the results of :cmd:`Search`, + :cmd:`SearchHead`, :cmd:`SearchPattern` and :cmd:`SearchRewrite` queries. A lemma whose + fully-qualified name contains any of the strings will be excluded from the + search results. The default blacklisted substrings are ``_subterm``, ``_subproof`` and + ``Private_``. - 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 “_”. + Use the :cmd:`Add` and :cmd:`Remove` commands to update the set of + blacklisted strings. - .. example:: - .. coqtop:: in +.. _requests-to-the-environment: - Require Import Arith. +Requests to the environment +------------------------------- - .. coqtop:: all +.. cmd:: Print Assumptions @smart_qualid - SearchRewrite (_ + _ + _). + Displays all the assumptions (axioms, parameters and + variables) a theorem or definition depends on. - .. cmdv:: SearchRewrite @term inside {+ @qualid } + The message "Closed under the global context" indicates that the theorem or + definition has no dependencies. - This restricts the search to constructions defined in the modules - named by the given :n:`qualid` sequence. +.. cmd:: Print Opaque Dependencies @smart_qualid - .. cmdv:: SearchRewrite @term outside {+ @qualid } + Displays the assumptions and opaque constants that :n:`@smart_qualid` depends on. - This restricts the search to constructions not defined in the modules - named by the given :n:`qualid` sequence. +.. cmd:: Print Transparent Dependencies @smart_qualid - .. cmdv:: @selector: SearchRewrite @term + Displays the assumptions and transparent constants that :n:`@smart_qualid` depends on. - This specifies the goal on which to - search hypothesis (see Section :ref:`invocation-of-tactics`). - By default the 1st goal is - searched. This variant can be combined with other variants presented - here. +.. cmd:: Print All Dependencies @smart_qualid -.. note:: + Displays all the assumptions and constants :n:`@smart_qualid` depends on. - .. table:: Search Blacklist @string - :name: Search Blacklist +.. cmd:: Locate @smart_qualid - Specifies a set of strings used to exclude lemmas from the results of :cmd:`Search`, - :cmd:`SearchHead`, :cmd:`SearchPattern` and :cmd:`SearchRewrite` queries. A lemma whose - fully-qualified name contains any of the strings will be excluded from the - search results. The default blacklisted substrings are ``_subterm``, ``_subproof`` and - ``Private_``. + Displays the full name of objects from |Coq|'s various qualified namespaces such as terms, + modules and Ltac. It also displays notation definitions. - Use the :cmd:`Add @table` and :cmd:`Remove @table` commands to update the set of - blacklisted strings. + If the argument is: -.. cmd:: Locate @qualid + * :n:`@qualid` - displays the full name of objects that + end with :n:`@qualid`, thereby showing the module they are defined in. + * :n:`@string {? "%" @ident }` - displays the definition of a notation. :n:`@string` + can be a single token in the notation such as "`->`" or a pattern that matches the + notation. See :ref:`locating-notations`. - 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 namespaces of |Coq|: terms, modules, Ltac, etc. + .. todo somewhere we should list all the qualified namespaces - .. example:: +.. cmd:: Locate Term @smart_qualid - .. coqtop:: all + Like :cmd:`Locate`, but limits the search to terms - Locate nat. +.. cmd:: Locate Module @qualid - Locate Datatypes.O. + Like :cmd:`Locate`, but limits the search to modules - Locate Init.Datatypes.O. +.. cmd:: Locate Ltac @qualid - Locate Coq.Init.Datatypes.O. + Like :cmd:`Locate`, but limits the search to tactics - Locate I.Dont.Exist. +.. cmd:: Locate Library @qualid - .. cmdv:: Locate Term @qualid + Displays the full name, status and file system path of the module :n:`@qualid`, whether loaded or not. - As Locate but restricted to terms. +.. cmd:: Locate File @string - .. cmdv:: Locate Module @qualid + Displays the file system path of the file ending with :n:`@string`. + Typically, :n:`@string` has a suffix such as ``.cmo`` or ``.vo`` or ``.v`` file, such as :n:`Nat.v`. - As Locate but restricted to modules. + .. todo: also works for directory names such as "Data" (parent of Nat.v) + also "Data/Nat.v" works, but not a substring match - .. cmdv:: Locate Ltac @qualid +.. example:: Locate examples - As Locate but restricted to tactics. + .. coqtop:: all -.. seealso:: Section :ref:`locating-notations` + Locate nat. + Locate Datatypes.O. + Locate Init.Datatypes.O. + Locate Coq.Init.Datatypes.O. + Locate I.Dont.Exist. .. _printing-flags: @@ -522,35 +323,32 @@ Loading files |Coq| offers the possibility of loading different parts of a whole development stored in separate files. Their contents will be loaded as if they were entered from the keyboard. This means that the loaded -files are ASCII files containing sequences of commands for |Coq|’s +files are text files containing sequences of commands for |Coq|’s toplevel. This kind of file is called a *script* for |Coq|. The standard (and default) extension of |Coq|’s script files is .v. -.. cmd:: Load @ident +.. cmd:: Load {? Verbose } {| @string | @ident } - This command loads the file named :n:`ident`.v, searching successively in + Loads a file. If :n:`@ident` is specified, the command loads a file + named :n:`@ident.v`, searching successively in each of the directories specified in the *loadpath*. (see Section :ref:`libraries-and-filesystem`) - Files loaded this way cannot leave proofs open, and the ``Load`` - command cannot be used inside a proof either. - - .. cmdv:: Load @string + If :n:`@string` is specified, it must specify a complete filename. + `~` and .. abbreviations are + allowed as well as shell variables. If no extension is specified, |Coq| + will use the default extension ``.v``. - 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``. + Files loaded this way can't leave proofs open, nor can :cmd:`Load` + be used inside a proof. - .. cmdv:: Load Verbose @ident - Load Verbose @string + We discourage the use of :cmd:`Load`; use :cmd:`Require` instead. + :cmd:`Require` loads `.vo` files that were previously + compiled from `.v` files. - Display, while loading, - the answers of |Coq| to each command (including tactics) contained in - the loaded file. - - .. seealso:: Section :ref:`controlling-display`. + :n:`Verbose` displays the |Coq| output for each command and tactic + in the loaded file, as if the commands and tactics were entered interactively. .. exn:: Can’t find file @ident on loadpath. :undocumented: @@ -568,67 +366,50 @@ Compiled files This section describes the commands used to load compiled files (see Chapter :ref:`thecoqcommands` for documentation on how to compile a file). A compiled -file is a particular case of module called *library file*. - - -.. cmd:: Require @qualid - - This command looks in the loadpath for a file containing module :n:`@qualid` - and adds the corresponding module to the environment of |Coq|. As - library files have dependencies in other library files, the command - :cmd:`Require` :n:`@qualid` recursively requires all library files the module - qualid depends on and adds the corresponding modules to the - environment of |Coq| too. |Coq| assumes that the compiled files have been - produced by a valid |Coq| compiler and their contents are then not - replayed nor rechecked. - - To locate the file in the file system, :n:`@qualid` is decomposed under the - form :n:`dirpath.@ident` and the file :n:`@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. +file is a particular case of a module called a *library file*. + +.. cmd:: Require {? {| Import | Export } } {+ @qualid } + :name: Require; Require Import; Require Export - .. cmdv:: Require Import @qualid - :name: Require Import + Loads compiled modules into the |Coq| environment. For each :n:`@qualid`, which has the form + :n:`{* @ident__prefix . } @ident`, the command searches for the logical name represented + by the :n:`@ident__prefix`\s and loads the compiled file :n:`@ident.vo` from the associated + filesystem directory. - This loads and declares the module :n:`@qualid` - and its dependencies then imports the contents of :n:`@qualid` as described - for :cmd:`Import`. It does not import the modules that - :n:`@qualid` depends on unless these modules were themselves required in module - :n:`@qualid` - using :cmd:`Require Export`, or recursively required - through a series 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. + The process is applied recursively to all the loaded files; + if they contain :cmd:`Require` commands, those commands are executed as well. + The compiled files must have been compiled with the same version of |Coq|. + The compiled files are neither replayed nor rechecked. - .. cmdv:: Require Export @qualid - :name: Require Export + * :n:`Import` - additionally does an :cmd:`Import` on the loaded module, making components defined + in the module available by their short names + * :n:`Export` - additionally does an :cmd:`Export` on the loaded module, making components defined + in the module available by their short names *and* marking them to be exported by the current + module - 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.` + If the required module has already been loaded, :n:`Import` and :n:`Export` make the command + equivalent to :cmd:`Import` or :cmd:`Export`. + + The loadpath must contain the same mapping used to compile the file + (see Section :ref:`libraries-and-filesystem`). If + several files match, one of them is picked in an unspecified fashion. + Therefore, library authors should use a unique name for each module and + users are encouraged to use fully-qualified names + or the :cmd:`From ... Require` command to load files. - .. cmdv:: Require {| Import | Export } {+ @qualid } - This loads the - modules named by the :token:`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``. + .. todo common user error on dirpaths see https://github.com/coq/coq/pull/11961#discussion_r402852390 - .. cmdv:: From @dirpath Require @qualid - :name: From ... Require ... + .. cmd:: From @dirpath Require {? {| Import | Export } } {+ @qualid } + :name: From ... Require - This command acts as :cmd:`Require`, but picks - any library whose absolute name is of the form :n:`@dirpath.@dirpath’.@qualid` - for some :n:`@dirpath’`. This is useful to ensure that the :token:`qualid` library - comes from a given package by making explicit its absolute root. + Works like :cmd:`Require`, but loads, for each :n:`@qualid`, + the library whose fully-qualified name matches :n:`@dirpath.{* @ident . }@qualid` + for some :n:`{* @ident . }`. This is useful to ensure that the :n:`@qualid` library + comes from a particular package. - .. exn:: Cannot load qualid: no physical path bound to dirpath. + .. exn:: Cannot load @qualid: no physical path bound to @dirpath. :undocumented: .. exn:: Cannot find library foo in loadpath. @@ -637,7 +418,7 @@ file is a particular case of module called *library file*. file foo.vo. Either foo.v exists but is not compiled or foo.vo is in a directory which is not in your LoadPath (see Section :ref:`libraries-and-filesystem`). - .. exn:: Compiled library @ident.vo makes inconsistent assumptions over library qualid. + .. exn:: Compiled library @ident.vo makes inconsistent assumptions over library @qualid. The command tried to load library file :n:`@ident`.vo that depends on some specific version of library :n:`@qualid` which is not the @@ -651,13 +432,13 @@ file is a particular case of module called *library file*. |Coq| compiled module, or it was compiled with an incompatible version of |Coq|. - .. exn:: The file :n:`@ident.vo` contains library dirpath and not library dirpath’. - - The library file :n:`@dirpath’` is indirectly required by the - ``Require`` command but it is bound in the current loadpath to the - file :n:`@ident.vo` which was bound to a different library name :token:`dirpath` at - the time it was compiled. + .. exn:: The file @ident.vo contains library @qualid__1 and not library @qualid__2. + The library :n:`@qualid__2` is indirectly required by a :cmd:`Require` or + :cmd:`From ... Require` command. The loadpath maps :n:`@qualid__2` to :n:`@ident.vo`, + which was compiled using a loadpath that bound it to :n:`@qualid__1`. Usually + the appropriate solution is to recompile :n:`@ident.v` using the correct loadpath. + See :ref:`libraries-and-filesystem`. .. warn:: Require inside a module is deprecated and strongly discouraged. You can Require a module at toplevel and optionally Import it inside another one. @@ -672,27 +453,22 @@ file is a particular case of module called *library file*. .. cmd:: Declare ML Module {+ @string } - This commands loads the OCaml compiled files - with names given by the :token:`string` sequence - (dynamic link). It is mainly used to load tactics dynamically. The - files are searched into the current OCaml loadpath (see the - command :cmd:`Add ML Path`). - 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 commands dynamically loads OCaml compiled code from + a :n:`.mllib` file. + It is used to load plugins dynamically. The + files must be accessible in the current OCaml loadpath (see the + command :cmd:`Add ML Path`). The :n:`.mllib` suffix may be omitted. - .. cmdv:: Local Declare ML Module {+ @string } + This command is reserved for plugin developers, who should provide + a .v file containing the command. Users of the plugins will then generally + load the .v file. - This variant is not exported to the modules that import the module - where they occur, even if outside a section. + This command supports the :attr:`local` attribute. If present, + the listed files are not exported, even if they're outside a section. .. exn:: File not found on loadpath: @string. :undocumented: - .. exn:: Loading of ML object file forbidden in a native Coq. - :undocumented: - .. cmd:: Print ML Modules @@ -707,7 +483,7 @@ Loadpath ------------ Loadpaths are preferably managed using |Coq| command line options (see -Section `libraries-and-filesystem`) but there remain vernacular commands to manage them +Section :ref:`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. @@ -717,22 +493,27 @@ the toplevel, and using them in source files is discouraged. This command displays the current working directory. -.. cmd:: Cd @string +.. cmd:: Cd {? @string } - This command changes the current directory according to :token:`string` which - can be any valid path. + If :n:`@string` is specified, changes the current directory according to :token:`string` which + can be any valid path. Otherwise, it displays the current directory. - .. cmdv:: Cd - Is equivalent to Pwd. +.. cmd:: Add LoadPath @string as @dirpath + .. insertprodn dirpath dirpath -.. cmd:: Add LoadPath @string as @dirpath + .. prodn:: + dirpath ::= {* @ident . } @ident This command is equivalent to the command line option - :n:`-Q @string @dirpath`. It adds the physical directory string to the current - |Coq| loadpath and maps it to the logical directory dirpath. + :n:`-Q @string @dirpath`. It adds a mapping to the loadpath from + the logical name :n:`@dirpath` to the file system directory :n:`@string`. + * :n:`@dirpath` is a prefix of a module name. The module name hierarchy + follows the file system hierarchy. On Linux, for example, the prefix + `A.B.C` maps to the directory :n:`@string/B/C`. Avoid using spaces after a `.` in the + path because the parser will interpret that as the end of a command or tactic. .. cmd:: Add Rec LoadPath @string as @dirpath @@ -746,42 +527,24 @@ the toplevel, and using them in source files is discouraged. This command removes the path :n:`@string` from the current |Coq| loadpath. -.. cmd:: Print LoadPath +.. cmd:: Print LoadPath {? @dirpath } - This command displays the current |Coq| loadpath. - - .. cmdv:: Print LoadPath @dirpath - - Works as :cmd:`Print LoadPath` but displays only - the paths that extend the :n:`@dirpath` prefix. + This command displays the current |Coq| loadpath. If :n:`@dirpath` is specified, + displays only the paths that extend that prefix. .. cmd:: Add ML Path @string This command adds the path :n:`@string` to the current OCaml - loadpath (see the command `Declare ML Module`` in Section :ref:`compiled-files`). + loadpath (cf. :cmd:`Declare ML Module`). -.. cmd:: Print ML Path @string +.. cmd:: Print ML Path This command displays the current OCaml loadpath. This command makes sense only under the bytecode version of ``coqtop``, i.e. using option ``-byte`` - (see the command Declare ML Module in Section :ref:`compiled-files`). - -.. _locate-file: - -.. cmd:: Locate File @string - - This command displays the location of file string in the current - loadpath. Typically, string is a ``.cmo`` or ``.vo`` or ``.v`` file. - - -.. cmd:: Locate Library @dirpath - - This command gives the status of the |Coq| module dirpath. It tells if - the module is loaded and if not searches in the load path for a module - of logical name :n:`@dirpath`. + (cf. :cmd:`Declare ML Module`). .. _backtracking: @@ -804,30 +567,22 @@ interactively, they cannot be part of a vernacular file loaded via .. exn:: @ident: no such entry. :undocumented: - .. cmdv:: Reset Initial - - Goes back to the initial state, just after the start - of the interactive session. +.. cmd:: Reset Initial + Goes back to the initial state, just after the start + of the interactive session. -.. cmd:: Back - This command undoes all the effects of the last vernacular command. - Commands read from a vernacular file via a :cmd:`Load` are considered as a - single command. Proof management commands are also handled by this - command (see Chapter :ref:`proofhandling`). For that, Back may have to undo more than - one command in order to reach a state where the proof management - information is available. For instance, when the last command is a - :cmd:`Qed`, the management information about the closed proof has been - discarded. In this case, :cmd:`Back` will then undo all the proof steps up to - the statement of this proof. +.. cmd:: Back {? @num } - .. cmdv:: Back @num - - Undo :n:`@num` vernacular commands. As for Back, some extra - commands may be undone in order to reach an adequate state. For - instance Back :n:`@num` will not re-enter a closed proof, but rather go just - before that proof. + Undoes all the effects of the last :n:`@num @sentence`\s. If + :n:`@num` is not specified, the command undoes one sentence. + Sentences read from a `.v` file via a :cmd:`Load` are considered a + single sentence. While :cmd:`Back` can undo tactics and commands executed + within proof mode, once you exit proof mode, such as with :cmd:`Qed`, all + the statements executed within are thereafter considered a single sentence. + :cmd:`Back` immediately following :cmd:`Qed` gets you back to the state + just after the statement of the proof. .. exn:: Invalid backtrack. @@ -848,18 +603,17 @@ interactively, they cannot be part of a vernacular file loaded via Quitting and debugging -------------------------- - .. cmd:: Quit - This command permits to quit |Coq|. + Causes |Coq| to exit. Valid only in coqtop. .. cmd:: Drop - This is used mostly as a debug facility by |Coq|’s implementers and does - not concern the casual user. This command permits to leave |Coq| - temporarily and enter the OCaml toplevel. The OCaml - command: + This command temporarily enters the OCaml toplevel. + It is a debug facility used by |Coq|’s implementers. Valid only in the + bytecode version of coqtop. + The OCaml command: :: @@ -884,49 +638,53 @@ Quitting and debugging (see Section `customization-by-environment-variables`). -.. TODO : command is not a syntax entry - -.. cmd:: Time @command +.. cmd:: Time @sentence - This command executes the vernacular command :n:`@command` and displays the + Executes :n:`@sentence` and displays the time needed to execute it. -.. cmd:: Redirect @string @command +.. cmd:: Redirect @string @sentence - This command executes the vernacular command :n:`@command`, redirecting its - output to ":n:`@string`.out". + Executes :n:`@sentence`, redirecting its + output to the file ":n:`@string`.out". -.. cmd:: Timeout @num @command +.. cmd:: Timeout @num @sentence - 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 + Executes :n:`@sentence`. If the operation + has not terminated after :n:`@num` seconds, then it is interrupted and an error message is displayed. .. opt:: Default Timeout @num :name: Default Timeout - 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. + If set, each :n:`@sentence` is treated as if it was prefixed with :cmd:`Timeout` :n:`@num`, + except for :cmd:`Timeout` commands themselves. If unset, + no timeout is applied. -.. cmd:: Fail @command +.. cmd:: Fail @sentence For debugging scripts, sometimes it is desirable to know whether a - command or a tactic fails. If the given :n:`@command` fails, then - :n:`Fail @command` succeeds (excepts in the case of - critical errors, like a "stack overflow"), without changing the - proof state, and in interactive mode, the system prints a message + command or a tactic fails. If :n:`@sentence` fails, then + :n:`Fail @sentence` succeeds (except for + critical errors, such as "stack overflow"), without changing the + proof state. In interactive mode, the system prints a message confirming the failure. .. exn:: The command has not failed! - If the given :n:`@command` succeeds, then :n:`Fail @command` + If the given :n:`@command` succeeds, then :n:`Fail @sentence` fails with this error message. +.. note:: + + :cmd:`Time`, :cmd:`Redirect`, :cmd:`Timeout` and :cmd:`Fail` are + :production:`control_command`\s. For these commands, attributes and goal + selectors, when specified, are part of the :n:`@sentence` argument, and thus come after + the control command prefix and before the inner command or tactic. For + example: `Time #[ local ] Definition foo := 0.` or `Fail Timeout 10 all: auto.` .. _controlling-display: @@ -1008,13 +766,16 @@ 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 } +.. cmd:: Opaque {+ @smart_qualid } + + This command accepts the :attr:`global` attribute. By default, the scope + of :cmd:`Opaque` is limited to the current section or module. 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 + constants in the :n:`@smart_qualid` sequence in tactics using δ-conversion (unfolding a constant is replacing it by its definition). :cmd:`Opaque` has also an effect on the conversion algorithm of |Coq|, telling @@ -1022,24 +783,15 @@ described first. has to check the conversion (see Section :ref:`conversion-rules`) of two distinct applied constants. - .. cmdv:: Global Opaque {+ @qualid } - :name: Global Opaque - - The scope of :cmd:`Opaque` is limited to the current section, or current - file, unless the variant :cmd:`Global Opaque` is used. - .. seealso:: Sections :ref:`performingcomputations`, :ref:`tactics-automating`, :ref:`proof-editing-mode` - .. exn:: The reference @qualid was not found in the current environment. - - There is no constant referred by :n:`@qualid` in the environment. - Nevertheless, if you asked :cmd:`Opaque` `foo` `bar` and if `bar` does - not exist, `foo` is set opaque. +.. cmd:: Transparent {+ @smart_qualid } -.. cmd:: Transparent {+ @qualid } + This command accepts the :attr:`global` attribute. By default, the scope + of :cmd:`Transparent` is limited to the current section or module. This command is the converse of :cmd:`Opaque` and it applies on unfoldable constants to restore their unfoldability after an Opaque command. @@ -1052,16 +804,9 @@ described first. the usual defined constants, whose actual values are of course relevant in general. - .. cmdv:: Global Transparent {+ @qualid } - :name: Global Transparent - - The scope of Transparent is limited to the current section, or current - file, unless the variant :cmd:`Global Transparent` is - used. - .. exn:: The reference @qualid was not found in the current environment. - There is no constant referred by :n:`@qualid` in the environment. + There is no constant named :n:`@qualid` in the environment. .. seealso:: @@ -1070,63 +815,68 @@ described first. .. _vernac-strategy: -.. cmd:: Strategy @level [ {+ @qualid } ] +.. cmd:: Strategy {+ @strategy_level [ {+ @smart_qualid } ] } + + .. insertprodn strategy_level strategy_level_or_var + + .. prodn:: + strategy_level ::= opaque + | @int + | expand + | transparent + strategy_level_or_var ::= @strategy_level + | @ident + + This command accepts the :attr:`local` attribute, which limits its effect + to the current section or module, in which case the section and module + behavior is the same as :cmd:`Opaque` and :cmd:`Transparent` (without :attr:`global`). - This command generalizes the behavior of Opaque and Transparent + This command generalizes the behavior of the :cmd:`Opaque` and :cmd:`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` + command associates a :n:`@strategy_level` with the qualified names in the :n:`@smart_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. - .. prodn:: level ::= {| opaque | @num | expand } - Levels can be one of the following (higher to lower): + ``opaque`` : level of opaque constants. They cannot be expanded by tactics (behaves like +∞, see next item). - + :n:`@num` : levels indexed by an integer. Level 0 corresponds to the + + :n:`@int` : levels indexed by an integer. Level 0 corresponds to the default behavior, which corresponds to transparent constants. This - level can also be referred to as transparent. Negative levels + level can also be referred to as ``transparent``. Negative levels correspond to constants to be expanded before normal transparent constants, while positive levels correspond to constants to be expanded after normal transparent constants. + ``expand`` : level of constants that should be expanded first (behaves like −∞) + + ``transparent`` : Equivalent to level 0 - .. cmdv:: Local Strategy @level [ {+ @qualid } ] - - These directives survive section and module closure, unless the - command is prefixed by ``Local``. In the latter case, the behavior - regarding sections and modules is the same as for the :cmd:`Transparent` and - :cmd:`Opaque` commands. - +.. cmd:: Print Strategy @smart_qualid -.. 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 + This command prints the strategy currently associated with :n:`@smart_qualid`. It + fails if :n:`@smart_qualid` is not an unfoldable reference, that is, neither a variable nor a constant. .. exn:: The reference is not unfoldable. :undocumented: - .. cmdv:: Print Strategies +.. cmd:: Print Strategies - Print all the currently non-transparent strategies. + Print all the currently non-transparent strategies. .. cmd:: Declare Reduction @ident := @red_expr - This command allows giving a short name to a reduction expression, for + Declares a short name for the reduction expression :n:`@red_expr`, for instance ``lazy beta delta [foo bar]``. This short name can then be used - in :n:`Eval @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 is not qualified. In + in :n:`Eval @ident in` or ``eval`` constructs. This command + accepts the :attr:`local` attribute, which indicates that the reduction + will be discarded at the end of the + file or module. The name is not qualified. In particular declaring the same name in several modules or in several functor applications will be rejected if these declarations are not local. The name :n:`@ident` cannot be used directly as an Ltac tactic, but @@ -1220,6 +970,8 @@ Controlling Typing Flags Print the status of the three typing flags: guard checking, positivity checking and universe checking. +See also :flag:`Cumulative StrictProp` in the |SProp| chapter. + .. example:: .. coqtop:: all reset @@ -1272,14 +1024,15 @@ in support libraries of plug-ins. .. _exposing-constants-to-ocaml-libraries: Exposing constants to OCaml libraries -```````````````````````````````````````````````````````````````` +````````````````````````````````````` .. cmd:: Register @qualid__1 as @qualid__2 - This command exposes the constant :n:`@qualid__1` to OCaml libraries under - the name :n:`@qualid__2`. This constant can then be dynamically located - calling :n:`Coqlib.lib_ref "@qualid__2"`; i.e., there is no need to known - where is the constant defined (file, module, library, etc.). + Makes the constant :n:`@qualid__1` accessible to OCaml libraries under + the name :n:`@qualid__2`. The constant can then be dynamically located + in OCaml code by + calling :n:`Coqlib.lib_ref "@qualid__2"`. The OCaml code doesn't need + to know where the constant is defined (what file, module, library, etc.). As a special case, when the first segment of :n:`@qualid__2` is :g:`kernel`, the constant is exposed to the kernel. For instance, the `Int63` module @@ -1289,27 +1042,41 @@ Exposing constants to OCaml libraries Register bool as kernel.ind_bool. - This makes the kernel aware of what is the type of boolean values. This - information is used for instance to define the return type of the - :g:`#int63_eq` primitive. + This makes the kernel aware of the `bool` type, which is used, for example, + to define the return type of the :g:`#int63_eq` primitive. .. seealso:: :ref:`primitive-integers` Inlining hints for the fast reduction machines -```````````````````````````````````````````````````````````````` +`````````````````````````````````````````````` .. cmd:: Register Inline @qualid - This command gives as a hint to the reduction machines (VM and native) that + Gives a hint to the reduction machines (VM and native) that the body of the constant :n:`@qualid` should be inlined in the generated code. Registering primitive operations ```````````````````````````````` -.. cmd:: Primitive @ident__1 := #@ident__2. +.. cmd:: Primitive @ident {? : @term } := #@ident__prim + + Makes the primitive type or primitive operator :n:`#@ident__prim` defined in OCaml + accessible in |Coq| commands and tactics. + For internal use by implementors of |Coq|'s standard library or standard library + replacements. No space is allowed after the `#`. Invalid values give a syntax + error. + + For example, the standard library files `Int63.v` and `PrimFloat.v` use :cmd:`Primitive` + to support, respectively, the features described in :ref:`primitive-integers` and + :ref:`primitive-floats`. + + The types associated with an operator must be declared to the kernel before declaring operations + that use the type. Do this with :cmd:`Primitive` for primitive types and + :cmd:`Register` with the :g:`kernel` prefix for other types. For example, + in `Int63.v`, `#int63_type` must be declared before the associated operations. + + .. exn:: The type @ident must be registered before this construction can be typechecked. + :undocumented: - Declares :n:`@ident__1` as the primitive operator :n:`#@ident__2`. When - running this command, the type of the primitive should be already known by - the kernel (this is achieved through this command for primitive types and - through the :cmd:`Register` command with the :g:`kernel` name-space for other - types). + The type must be defined with :cmd:`Primitive` command before this + :cmd:`Primitive` command (declaring an operation using the type) will succeed. diff --git a/doc/sphinx/std-glossindex.rst b/doc/sphinx/std-glossindex.rst new file mode 100644 index 0000000000..91e9da20fe --- /dev/null +++ b/doc/sphinx/std-glossindex.rst @@ -0,0 +1,9 @@ +:orphan: + +.. hack to get index in TOC + +.. _glossary_index: + +-------------- +Glossary index +-------------- diff --git a/doc/sphinx/user-extensions/proof-schemes.rst b/doc/sphinx/user-extensions/proof-schemes.rst index 34197c4fcf..e05be7c2c2 100644 --- a/doc/sphinx/user-extensions/proof-schemes.rst +++ b/doc/sphinx/user-extensions/proof-schemes.rst @@ -190,146 +190,7 @@ Combined Scheme Check tree_forest_mutrect. -.. _functional-scheme: - -Generation of induction principles with ``Functional`` ``Scheme`` ------------------------------------------------------------------ - - -.. cmd:: Functional Scheme @ident__0 := Induction for @ident' Sort @sort {* with @ident__i := Induction for @ident__i' Sort @sort} - - This command is a high-level experimental tool for - generating automatically induction principles corresponding to - (possibly mutually recursive) functions. First, it must be made - available via ``Require Import FunInd``. - Each :n:`@ident__i` is a different mutually defined function - name (the names must be in the same order as when they were defined). This - command generates the induction principle for each :n:`@ident__i`, following - the recursive structure and case analyses of the corresponding function - :n:`@ident__i'`. - -.. warning:: - - There is a difference between induction schemes generated by the command - :cmd:`Functional Scheme` and these generated by the :cmd:`Function`. Indeed, - :cmd:`Function` generally produces smaller principles that are closer to how - a user would implement them. See :ref:`advanced-recursive-functions` for details. - -.. example:: - - Induction scheme for div2. - - We define the function div2 as follows: - - .. coqtop:: all - - Require Import FunInd. - Require Import Arith. - - Fixpoint div2 (n:nat) : nat := - match n with - | O => 0 - | S O => 0 - | S (S n') => S (div2 n') - end. - - The definition of a principle of induction corresponding to the - recursive structure of `div2` is defined by the command: - - .. coqtop:: all - - Functional Scheme div2_ind := Induction for div2 Sort Prop. - - You may now look at the type of div2_ind: - - .. coqtop:: all - - Check div2_ind. - - We can now prove the following lemma using this principle: - - .. coqtop:: all - - Lemma div2_le' : forall n:nat, div2 n <= n. - intro n. - pattern n, (div2 n). - apply div2_ind; intros. - auto with arith. - auto with arith. - simpl; auto with arith. - Qed. - - We can use directly the functional induction (:tacn:`function induction`) tactic instead - of the pattern/apply trick: - - .. coqtop:: all - - Reset div2_le'. - - Lemma div2_le : forall n:nat, div2 n <= n. - intro n. - functional induction (div2 n). - auto with arith. - auto with arith. - auto with arith. - Qed. - -.. example:: - - Induction scheme for tree_size. - - We define trees by the following mutual inductive type: - - .. original LaTeX had "Variable" instead of "Axiom", which generates an ugly warning - - .. coqtop:: reset all - - Axiom A : Set. - - Inductive tree : Set := - node : A -> forest -> tree - with forest : Set := - | empty : forest - | cons : tree -> forest -> forest. - - We define the function tree_size that computes the size of a tree or a - forest. Note that we use ``Function`` which generally produces better - principles. - - .. coqtop:: all - - Require Import FunInd. - - Function tree_size (t:tree) : nat := - match t with - | node A f => S (forest_size f) - end - with forest_size (f:forest) : nat := - match f with - | empty => 0 - | cons t f' => (tree_size t + forest_size f') - end. - - Notice that the induction principles ``tree_size_ind`` and ``forest_size_ind`` - generated by ``Function`` are not mutual. - - .. coqtop:: all - - Check tree_size_ind. - - Mutual induction principles following the recursive structure of ``tree_size`` - and ``forest_size`` can be generated by the following command: - - .. coqtop:: all - - Functional Scheme tree_size_ind2 := Induction for tree_size Sort Prop - with forest_size_ind2 := Induction for forest_size Sort Prop. - - You may now look at the type of `tree_size_ind2`: - - .. coqtop:: all - - Check tree_size_ind2. +.. seealso:: :ref:`functional-scheme` .. _derive-inversion: diff --git a/doc/sphinx/user-extensions/syntax-extensions.rst b/doc/sphinx/user-extensions/syntax-extensions.rst index 669975ba7e..ea5ad79a80 100644 --- a/doc/sphinx/user-extensions/syntax-extensions.rst +++ b/doc/sphinx/user-extensions/syntax-extensions.rst @@ -1,7 +1,7 @@ -.. _syntaxextensionsandinterpretationscopes: +.. _syntax-extensions-and-notation-scopes: -Syntax extensions and interpretation scopes -======================================================== +Syntax extensions and notation scopes +===================================== In this chapter, we introduce advanced commands to modify the way Coq parses and prints objects, i.e. the translations between the concrete @@ -14,7 +14,7 @@ variant of :cmd:`Notation` which does not modify the parser; this provides a form of :ref:`abbreviation <Abbreviations>`. It is sometimes expected that the same symbolic notation has different meanings in different contexts; to achieve this form of overloading, |Coq| offers a notion -of :ref:`interpretation scopes <Scopes>`. +of :ref:`notation scopes <Scopes>`. The main command to provide custom notations for tactics is :cmd:`Tactic Notation`. .. coqtop:: none @@ -26,33 +26,43 @@ The main command to provide custom notations for tactics is :cmd:`Tactic Notatio Notations --------- + Basic notations ~~~~~~~~~~~~~~~ -.. cmd:: Notation +.. cmd:: Notation @string := @one_term {? ( {+, @syntax_modifier } ) } {? : @scope_name } + + Defines a *notation*, an alternate syntax for entering or displaying + a specific term or term pattern. + + This command supports the :attr:`local` attribute, which limits its effect to the + current module. + If the command is inside a section, its effect is limited to the section. - A *notation* is a symbolic expression denoting some term or term - pattern. + Specifying :token:`scope_name` associates the notation with that scope. Otherwise + it is a *lonely notation*, that is, not associated with a scope. -A typical notation is the use of the infix symbol ``/\`` to denote the -logical conjunction (and). Such a notation is declared by + .. todo indentation of this chapter is not consistent with other chapters. Do we have a standard? + +For example, the following definition permits using the infix expression :g:`A /\ B` +to represent :g:`(and A B)`: .. coqtop:: in Notation "A /\ B" := (and A B). -The expression :g:`(and A B)` is the abbreviated term and the string :g:`"A /\ B"` -(called a *notation*) tells how it is symbolically written. +:g:`"A /\ B"` is a *notation*, which tells how to represent the abbreviated term +:g:`(and A B)`. -A notation is always surrounded by double quotes (except when the +Notations must be in double quotes, except when the abbreviation has the form of an ordinary applicative expression; -see :ref:`Abbreviations`). The notation is composed of *tokens* separated by -spaces. Identifiers in the string (such as ``A`` and ``B``) are the *parameters* -of the notation. Each of them must occur at least once in the denoted term. The +see :ref:`Abbreviations`. The notation consists of *tokens* separated by +spaces. Alphanumeric strings (such as ``A`` and ``B``) are the *parameters* +of the notation. Each of them must occur at least once in the abbreviated term. The other elements of the string (such as ``/\``) are the *symbols*. -An identifier can be used as a symbol but it must be surrounded by -single quotes to avoid the confusion with a parameter. Similarly, +Substrings enclosed in single quotes are treated as literals. This is necessary +for substrings that would otherwise be interpreted as :n:`@ident`\s. Similarly, every symbol of at least 3 characters and starting with a simple quote must be quoted (then it starts by two single quotes). Here is an example. @@ -63,7 +73,8 @@ example. A notation binds a syntactic expression to a term. Unless the parser and pretty-printer of Coq already know how to deal with the syntactic -expression (see :ref:`ReservingNotations`), explicit precedences and +expression (such as through :cmd:`Reserved Notation` or for notations +that contain only literals), explicit precedences and associativity rules have to be given. .. note:: @@ -104,13 +115,12 @@ Similarly, an associativity is needed to decide whether :g:`True /\ False /\ Fal defaults to :g:`True /\ (False /\ False)` (right associativity) or to :g:`(True /\ False) /\ False` (left associativity). We may even consider that the expression is not well-formed and that parentheses are mandatory (this is a “no -associativity”) [#no_associativity]_. We do not know of a special convention of -the associativity of disjunction and conjunction, so let us apply for instance a +associativity”) [#no_associativity]_. We do not know of a special convention for +the associativity of disjunction and conjunction, so let us apply right associativity (which is the choice of Coq). -Precedence levels and associativity rules of notations have to be -given between parentheses in a list of :token:`modifiers` that the :cmd:`Notation` -command understands. Here is how the previous examples refine. +Precedence levels and associativity rules of notations are specified with a list of +parenthesized :n:`@syntax_modifier`\s. Here is how the previous examples refine: .. coqtop:: in @@ -158,8 +168,8 @@ One can also define notations for binders. Notation "{ x : A | P }" := (sig A (fun x => P)). In the last case though, there is a conflict with the notation for -type casts. The notation for types casts, as shown by the command :cmd:`Print -Grammar constr` is at level 100. To avoid ``x : A`` being parsed as a type cast, +type casts. The notation for type casts, as shown by the command :cmd:`Print +Grammar` `constr` is at level 100. To avoid ``x : A`` being parsed as a type cast, it is necessary to put ``x`` at a level below 100, typically 99. Hence, a correct definition is the following: @@ -204,16 +214,6 @@ have to be observed for notations starting with a symbol, e.g., rules starting with “\ ``{``\ ” or “\ ``(``\ ” should be put at level 0. The list of Coq predefined notations can be found in the chapter on :ref:`thecoqlibrary`. -.. cmd:: Print Grammar constr. - - This command displays the current state of the Coq term parser. - -.. cmd:: Print Grammar pattern. - - This displays the state of the subparser of patterns (the parser used in the - grammar of the ``match with`` constructions). - - Displaying symbolic notations ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -252,8 +252,7 @@ bar of the notation. Check (sig (fun x : nat => x=x)). -The second, more powerful control on printing is by using the format -:token:`modifier`. Here is an example +The second, more powerful control on printing is by using :n:`@syntax_modifier`\s. Here is an example .. coqtop:: all @@ -301,8 +300,8 @@ expression is performed at definition time. Type checking is done only at the time of use of the notation. .. note:: Sometimes, a notation is expected only for the parser. To do - so, the option ``only parsing`` is allowed in the list of :token:`modifiers` - of :cmd:`Notation`. Conversely, the ``only printing`` :token:`modifier` can be + so, the option ``only parsing`` is allowed in the list of :n:`@syntax_modifier`\s + in :cmd:`Notation`. Conversely, the ``only printing`` :n:`@syntax_modifier` can be used to declare that a notation should only be used for printing and should not declare a parsing rule. In particular, such notations do not modify the parser. @@ -313,13 +312,14 @@ The Infix command The :cmd:`Infix` command is a shortcut for declaring notations for infix symbols. -.. cmd:: Infix @string := @term {? (@modifiers) } +.. cmd:: Infix @string := @one_term {? ( {+, @syntax_modifier } ) } {? : @scope_name } This command is equivalent to - :n:`Notation "x @symbol y" := (@term x y) {? (@modifiers) }.` + :n:`Notation "x @string y" := (@one_term x y) {? ( {+, @syntax_modifier } ) } {? : @scope_name }` - where ``x`` and ``y`` are fresh names. Here is an example. + where ``x`` and ``y`` are fresh names and omitting the quotes around :n:`@string`. + Here is an example: .. coqtop:: in @@ -330,7 +330,7 @@ symbols. Reserving notations ~~~~~~~~~~~~~~~~~~~ -.. cmd:: Reserved Notation @string {? (@modifiers) } +.. cmd:: Reserved Notation @string {? ( {+, @syntax_modifier } ) } A given notation may be used in different contexts. Coq expects all uses of the notation to be defined at the same precedence and with the @@ -349,26 +349,34 @@ Reserving notations .. note:: The notations mentioned in the module :ref:`init-notations` are reserved. Hence their precedence and associativity cannot be changed. - .. cmdv:: Reserved Infix "@symbol" {* @modifiers} + .. cmd:: Reserved Infix @string {? ( {+, @syntax_modifier } ) } This command declares an infix parsing rule without giving its interpretation. - When a format is attached to a reserved notation, it is used by + When a format is attached to a reserved notation (with the `format` + :token:`syntax_modifier`), it is used by default by all subsequent interpretations of the corresponding - notation. A specific interpretation can provide its own format - overriding the default format though. + notation. Individual interpretations can override the format. Simultaneous definition of terms and notations ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Thanks to reserved notations, the inductive, co-inductive, record, recursive and -corecursive definitions can benefit from customized notations. To do this, insert -a ``where`` notation clause after the definition of the (co)inductive type or +Thanks to reserved notations, inductive, co-inductive, record, recursive and +corecursive definitions can use customized notations. To do this, insert +a :token:`decl_notations` clause after the definition of the (co)inductive type or (co)recursive term (or after the definition of each of them in case of mutual definitions). The exact syntax is given by :n:`@decl_notation` for inductive, co-inductive, recursive and corecursive definitions and in :ref:`record-types` -for records. Here are examples: +for records. + + .. insertprodn decl_notations decl_notation + + .. prodn:: + decl_notations ::= where @decl_notation {* and @decl_notation } + decl_notation ::= @string := @one_term {? ( only parsing ) } {? : @scope_name } + +Here are examples: .. coqtop:: in @@ -403,8 +411,29 @@ Displaying information about notations .. seealso:: - :flag:`Printing All` - To disable other elements in addition to notations. + :flag:`Printing All` to disable other elements in addition to notations. + + +.. cmd:: Print Grammar @ident + + Shows the grammar for the nonterminal :token:`ident`, which must be one of the following: + + - `constr` - for :token:`term`\s + - `pattern` - for :token:`pattern`\s + - `tactic` - for currently-defined tactic notations, :token:`tactic`\s and tacticals + (corresponding to :token:`ltac_expr` in the documentation). + - `vernac` - for :token:`command`\s + + The first three of these give the precedence and associativity for each construct. + For example, these lines printed by `Print Grammar tactic` indicates that the `try` construct + is at level 3 and right-associative. `SELF` represents the `tactic_expr` nonterminal + at level 5 (the top level):: + + | "3" RIGHTA + [ IDENT "try"; SELF + + Note that the productions printed by this command are represented in the form used by + |Coq|'s parser (coqpp), which differs from how productions are shown in the documentation. .. _locating-notations: @@ -427,7 +456,7 @@ Inheritance of the properties of arguments of constants bound to a notation If the right-hand side of a notation is a partially applied constant, the notation inherits the implicit arguments (see -:ref:`ImplicitArguments`) and interpretation scopes (see +:ref:`ImplicitArguments`) and notation scopes (see :ref:`Scopes`) of the constant. For instance: .. coqtop:: in reset @@ -441,7 +470,7 @@ the notation inherits the implicit arguments (see As an exception, if the right-hand side is just of the form :n:`@@qualid`, this conventionally stops the inheritance of implicit -arguments (but not of interpretation scopes). +arguments (but not of notation scopes). Notations and binders ~~~~~~~~~~~~~~~~~~~~~ @@ -471,7 +500,7 @@ application of the notation: Check sigma z : nat, z = 0. -Notice the :token:`modifier` ``x ident`` in the declaration of the +Note the :n:`@syntax_modifier x ident` in the declaration of the notation. It tells to parse :g:`x` as a single identifier. Binders bound in the notation and parsed as patterns @@ -491,7 +520,7 @@ binder. Here is an example: Check subset '(x,y), x+y=0. -The :token:`modifier` ``p pattern`` in the declaration of the notation tells to parse +The :n:`@syntax_modifier p pattern` in the declaration of the notation tells to parse :g:`p` as a pattern. Note that a single variable is both an identifier and a pattern, so, e.g., the following also works: @@ -501,7 +530,7 @@ pattern, so, e.g., the following also works: If one wants to prevent such a notation to be used for printing when the pattern is reduced to a single identifier, one has to use instead -the :token:`modifier` ``p strict pattern``. For parsing, however, a +the :n:`@syntax_modifier p strict pattern`. For parsing, however, a ``strict pattern`` will continue to include the case of a variable. Here is an example showing the difference: @@ -541,7 +570,7 @@ that ``x`` is parsed as a term at level 99 (as done in the notation for :g:`sumbool`), but that this term has actually to be an identifier. The notation :g:`{ x | P }` is already defined in the standard -library with the ``as ident`` :token:`modifier`. We cannot redefine it but +library with the ``as ident`` :n:`@syntax_modifier`. We cannot redefine it but one can define an alternative notation, say :g:`{ p such that P }`, using instead ``as pattern``. @@ -561,7 +590,7 @@ is just an identifier, one could have said ``p at level 99 as strict pattern``. Note also that in the absence of a ``as ident``, ``as strict pattern`` or -``as pattern`` :token:`modifier`\s, the default is to consider sub-expressions occurring +``as pattern`` :n:`@syntax_modifier`\s, the default is to consider sub-expressions occurring in binding position and parsed as terms to be ``as ident``. .. _NotationsWithBinders: @@ -640,7 +669,7 @@ and the terminating expression is ``nil``. Here are other examples: Notations with recursive patterns can be reserved like standard notations, they can also be declared within -:ref:`interpretation scopes <Scopes>`. +:ref:`notation scopes <Scopes>`. .. _RecursiveNotationsWithBinders: @@ -662,7 +691,7 @@ except that in the iterator position of the binding variable of a ``fun`` or a ``forall``. To specify that the part “``x .. y``” of the notation parses a sequence of -binders, ``x`` and ``y`` must be marked as ``binder`` in the list of :token:`modifiers` +binders, ``x`` and ``y`` must be marked as ``binder`` in the list of :n:`@syntax_modifier`\s of the notation. The binders of the parsed sequence are used to fill the occurrences of the first placeholder of the iterating pattern which is repeatedly nested as many times as the number of binders generated. If ever the @@ -740,10 +769,13 @@ Custom entries .. cmd:: Declare Custom Entry @ident - This command allows to define new grammar entries, called *custom + Defines new grammar entries, called *custom entries*, that can later be referred to using the entry name :n:`custom @ident`. + This command supports the :attr:`local` attribute, which limits the entry to the + current module. + .. example:: For instance, we may want to define an ad hoc @@ -887,67 +919,48 @@ gives a way to let any arbitrary expression which is not handled by the custom entry ``expr`` be parsed or printed by the main grammar of term up to the insertion of a pair of curly brackets. -.. cmd:: Print Custom Grammar @ident. +.. cmd:: Print Custom Grammar @ident :name: Print Custom Grammar This displays the state of the grammar for terms associated to the custom entry :token:`ident`. -Summary -~~~~~~~ - .. _NotationSyntax: -Syntax of notations -+++++++++++++++++++ - -The different syntactic forms taken by the commands declaring -notations are given below. The optional :production:`scope` is described in -:ref:`Scopes`. - -.. productionlist:: coq - notation : [Local] Notation `string` := `term` [(`modifiers`)] [: `scope`]. - : [Local] Infix `string` := `qualid` [(`modifiers`)] [: `scope`]. - : [Local] Reserved Notation `string` [(`modifiers`)] . - : Inductive `ind_body` [`decl_notations`] with … with `ind_body` [`decl_notations`]. - : CoInductive `ind_body` [`decl_notations`] with … with `ind_body` [`decl_notations`]. - : Fixpoint `fix_body` [`decl_notations`] with … with `fix_body` [`decl_notations`]. - : CoFixpoint `fix_body` [`decl_notations`] with … with `fix_body` [`decl_notations`]. - : [Local] Declare Custom Entry `ident`. - modifiers : `modifier`, … , `modifier` - modifier : at level `num` - : in custom `ident` - : in custom `ident` at level `num` - : `ident` , … , `ident` at level `num` [`binderinterp`] - : `ident` , … , `ident` at next level [`binderinterp`] - : `ident` `explicit_subentry` - : left associativity - : right associativity - : no associativity - : only parsing - : only printing - : format `string` - explicit_subentry : ident - : global - : bigint - : [strict] pattern [at level `num`] - : binder - : closed binder - : constr [`binderinterp`] - : constr at level `num` [`binderinterp`] - : constr at next level [`binderinterp`] - : custom [`binderinterp`] - : custom at level `num` [`binderinterp`] - : custom at next level [`binderinterp`] - binderinterp : as ident - : as pattern - : as strict pattern - -.. insertprodn decl_notations decl_notation +Syntax +~~~~~~~ -.. prodn:: - decl_notations ::= where @decl_notation {* and @decl_notation } - decl_notation ::= @string := @one_term {? ( only parsing ) } {? : @ident } +Here are the syntax elements used by the various notation commands. + + .. insertprodn syntax_modifier level + + .. prodn:: + syntax_modifier ::= at level @num + | in custom @ident {? at level @num } + | {+, @ident } at @level + | @ident at @level {? @binder_interp } + | @ident @explicit_subentry + | @ident @binder_interp + | left associativity + | right associativity + | no associativity + | only parsing + | only printing + | format @string {? @string } + explicit_subentry ::= ident + | global + | bigint + | strict pattern {? at level @num } + | binder + | closed binder + | constr {? at @level } {? @binder_interp } + | custom @ident {? at @level } {? @binder_interp } + | pattern {? at level @num } + binder_interp ::= as ident + | as pattern + | as strict pattern + level ::= level @num + | next level .. note:: No typing of the denoted expression is performed at definition time. Type checking is done only at the time of use of the notation. @@ -981,101 +994,86 @@ notations are given below. The optional :production:`scope` is described in due to legacy notation in the Coq standard library. It can be turned on with the ``-w disj-pattern-notation`` flag. -Persistence of notations -++++++++++++++++++++++++ - -Notations disappear when a section is closed. - -.. cmd:: Local Notation @notation +.. _Scopes: - Notations survive modules unless the command ``Local Notation`` is used instead - of :cmd:`Notation`. +Notation scopes +--------------- -.. cmd:: Local Declare Custom Entry @ident +A *notation scope* is a set of notations for terms with their +interpretations. Notation scopes provide a weak, purely +syntactic form of notation overloading: a symbol may +refer to different definitions depending on which notation scopes +are currently open. For instance, the infix symbol ``+`` can be +used to refer to distinct definitions of the addition operator, +such as for natural numbers, integers or reals. +Notation scopes can include an interpretation for numerals and +strings with the :cmd:`Numeral Notation` and :cmd:`String Notation` commands. - Custom entries survive modules unless the command ``Local Declare - Custom Entry`` is used instead of :cmd:`Declare Custom Entry`. + .. insertprodn scope scope_key -.. _Scopes: + .. prodn:: + scope ::= @scope_name + | @scope_key + scope_name ::= @ident + scope_key ::= @ident -Interpretation scopes ----------------------- +Each notation scope has a single :token:`scope_name`, which by convention +ends with the suffix "_scope", as in "nat_scope". One or more :token:`scope_key`\s +(delimiting keys) may be associated with a notation scope with the :cmd:`Delimit Scope` command. +Most commands use :token:`scope_name`; :token:`scope_key`\s are used within :token:`term`\s. -An *interpretation scope* is a set of notations for terms with their -interpretations. Interpretation scopes provide a weak, purely -syntactical form of notation overloading: the same notation, for -instance the infix symbol ``+``, can be used to denote distinct -definitions of the additive operator. Depending on which interpretation -scopes are currently open, the interpretation is different. -Interpretation scopes can include an interpretation for numerals and -strings, either at the OCaml level or using :cmd:`Numeral Notation` -or :cmd:`String Notation`. +.. cmd:: Declare Scope @scope_name -.. cmd:: Declare Scope @scope - - This adds a new scope named :n:`@scope`. Note that the initial - state of Coq declares by default the following interpretation scopes: + Declares a new notation scope. Note that the initial + state of Coq declares the following notation scopes: ``core_scope``, ``type_scope``, ``function_scope``, ``nat_scope``, ``bool_scope``, ``list_scope``, ``int_scope``, ``uint_scope``. -The syntax to associate a notation to a scope is given -:ref:`above <NotationSyntax>`. Here is a typical example which declares the -notation for conjunction in the scope ``type_scope``. - -.. coqtop:: in - - Notation "A /\ B" := (and A B) : type_scope. - -.. note:: A notation not defined in a scope is called a *lonely* - notation. No example of lonely notations can be found in the - initial state of Coq though. - + Use commands such as :cmd:`Notation` to add notations to the scope. Global interpretation rules for notations ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ At any time, the interpretation of a notation for a term is done within -a *stack* of interpretation scopes and lonely notations. In case a -notation has several interpretations, the actual interpretation is the -one defined by (or in) the more recently declared (or opened) lonely -notation (or interpretation scope) which defines this notation. -Typically if a given notation is defined in some scope ``scope`` but has -also an interpretation not assigned to a scope, then, if ``scope`` is open -before the lonely interpretation is declared, then the lonely -interpretation is used (and this is the case even if the -interpretation of the notation in scope is given after the lonely -interpretation: otherwise said, only the order of lonely -interpretations and opening of scopes matters, and not the declaration -of interpretations within a scope). +a *stack* of notation scopes and lonely notations. If a +notation is defined in multiple scopes, |Coq| uses the interpretation from +the most recently opened notation scope or declared lonely notation. -.. cmd:: Open Scope @scope +Note that "stack" is a misleading name. Each scope or lonely notation can only appear in +the stack once. New items are pushed onto the top of the stack, except that +adding a item that's already in the stack moves it to the top of the stack instead. +Scopes are removed by name (e.g. by :cmd:`Close Scope`) wherever they are in the +stack, rather than through "pop" operations. - The command to add a scope to the interpretation scope stack is - :n:`Open Scope @scope`. +Use the :cmd:`Print Visibility` command to display the current notation scope stack. -.. cmd:: Close Scope @scope +.. cmd:: Open Scope @scope - It is also possible to remove a scope from the interpretation scope - stack by using the command :n:`Close Scope @scope`. + Adds a scope to the notation scope stack. If the scope is already present, + the command moves it to the top of the stack. - Notice that this command does not only cancel the last :n:`Open Scope @scope` - but all its invocations. + If the command appears in a section: By default, the scope is only added within the + section. Specifying :attr:`global` marks the scope for export as part of the current + module. Specifying :attr:`local` behaves like the default. -.. note:: ``Open Scope`` and ``Close Scope`` do not survive the end of sections - where they occur. When defined outside of a section, they are exported - to the modules that import the module where they occur. + If the command does not appear in a section: By default, the scope marks the scope for + export as part of the current module. Specifying :attr:`local` prevents exporting the scope. + Specifying :attr:`global` behaves like the default. -.. cmd:: Local Open Scope @scope. - Local Close Scope @scope. +.. cmd:: Close Scope @scope - These variants are not exported to the modules that import the module where - they occur, even if outside a section. + Removes a scope from the notation scope stack. -.. cmd:: Global Open Scope @scope. - Global Close Scope @scope. + If the command appears in a section: By default, the scope is only removed within the + section. Specifying :attr:`global` marks the scope removal for export as part of the current + module. Specifying :attr:`local` behaves like the default. - These variants survive sections. They behave as if Global were absent when - not inside a section. + If the command does not appear in a section: By default, the scope marks the scope removal for + export as part of the current module. Specifying :attr:`local` prevents exporting the removal. + Specifying :attr:`global` behaves like the default. + + .. todo: Strange notion, exporting something that _removes_ a scope. + See https://github.com/coq/coq/pull/11718#discussion_r413667817 .. _LocalInterpretationRulesForNotations: @@ -1085,123 +1083,40 @@ Local interpretation rules for notations In addition to the global rules of interpretation of notations, some ways to change the interpretation of subterms are available. -Local opening of an interpretation scope -+++++++++++++++++++++++++++++++++++++++++ - -It is possible to locally extend the interpretation scope stack using the syntax -:n:`(@term)%@ident` (or simply :n:`@term%@ident` for atomic terms), where :token:`ident` is a -special identifier called *delimiting key* and bound to a given scope. +Opening a notation scope locally +++++++++++++++++++++++++++++++++ -In such a situation, the term term, and all its subterms, are -interpreted in the scope stack extended with the scope bound to :token:`ident`. +.. insertprodn term_scope term_scope -.. cmd:: Delimit Scope @scope with @ident - - To bind a delimiting key to a scope, use the command - :n:`Delimit Scope @scope with @ident` - -.. cmd:: Undelimit Scope @scope - - To remove a delimiting key of a scope, use the command - :n:`Undelimit Scope @scope` - -Binding arguments of a constant to an interpretation scope -+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - -.. cmd:: Arguments @qualid {+ @name%@ident} - :name: Arguments (scopes) - - It is possible to set in advance that some arguments of a given constant have - to be interpreted in a given scope. The command is - :n:`Arguments @qualid {+ @name%@ident}` where the list is a prefix of the - arguments of ``qualid`` optionally annotated with their scope :token:`ident`. Grouping - round parentheses can be used to decorate multiple arguments with the same - scope. :token:`ident` can be either a scope name or its delimiting key. For - example the following command puts the first two arguments of :g:`plus_fct` - in the scope delimited by the key ``F`` (``Rfun_scope``) and the last - argument in the scope delimited by the key ``R`` (``R_scope``). - - .. coqdoc:: - - Arguments plus_fct (f1 f2)%F x%R. - - The ``Arguments`` command accepts scopes decoration to all grouping - parentheses. In the following example arguments A and B are marked as - maximally inserted implicit arguments and are put into the ``type_scope`` scope. - - .. coqdoc:: - - Arguments respectful {A B}%type (R R')%signature _ _. - - When interpreting a term, if some of the arguments of :token:`qualid` are built - from a notation, then this notation is interpreted in the scope stack - extended by the scope bound (if any) to this argument. The effect of - the scope is limited to the argument itself. It does not propagate to - subterms but the subterms that, after interpretation of the notation, - turn to be themselves arguments of a reference are interpreted - accordingly to the argument scopes bound to this reference. - - .. cmdv:: Arguments @qualid : clear scopes - - This command can be used to clear argument scopes of :token:`qualid`. - - .. cmdv:: Arguments @qualid {+ @name%@ident} : extra scopes - - Defines extra argument scopes, to be used in case of coercion to ``Funclass`` - (see the :ref:`implicitcoercions` chapter) or with a computed type. - - .. cmdv:: Global Arguments @qualid {+ @name%@ident} - - This behaves like :n:`Arguments qualid {+ @name%@ident}` but survives when a - section is closed instead of stopping working at section closing. Without the - ``Global`` modifier, the effect of the command stops when the section it belongs - to ends. - - .. cmdv:: Local Arguments @qualid {+ @name%@ident} - - This behaves like :n:`Arguments @qualid {+ @name%@ident}` but does not - survive modules and files. Without the ``Local`` modifier, the effect of the - command is visible from within other modules or files. - -.. seealso:: - - The command :cmd:`About` can be used to show the scopes bound to the - arguments of a function. +.. prodn:: + term_scope ::= @term0 % @scope_key -.. note:: +The notation scope stack can be locally extended within +a :token:`term` with the syntax +:n:`(@term)%@scope_key` (or simply :n:`@term0%@scope_key` for atomic terms). - In notations, the subterms matching the identifiers of the - notations are interpreted in the scope in which the identifiers - occurred at the time of the declaration of the notation. Here is an - example: +In this case, :n:`@term` is +interpreted in the scope stack extended with the scope bound to :n:`@scope_key`. - .. coqtop:: all +.. cmd:: Delimit Scope @scope_name with @scope_key - Parameter g : bool -> bool. - Declare Scope mybool_scope. + Binds the delimiting key :token:`scope_key` to a scope. - Notation "@@" := true (only parsing) : bool_scope. - Notation "@@" := false (only parsing): mybool_scope. +.. cmd:: Undelimit Scope @scope_name - Bind Scope bool_scope with bool. - Notation "# x #" := (g x) (at level 40). - Check # @@ #. - Arguments g _%mybool_scope. - Check # @@ #. - Delimit Scope mybool_scope with mybool. - Check # @@%mybool #. + Removes the delimiting keys associated with a scope. -Binding types of arguments to an interpretation scope -+++++++++++++++++++++++++++++++++++++++++++++++++++++ +Binding types or coercion classes to a notation scope +++++++++++++++++++++++++++++++++++++++++++++++++++++++ -.. cmd:: Bind Scope @ident with {+ @class } +.. cmd:: Bind Scope @scope_name with {+ @class } - When an interpretation scope is naturally associated to a type (e.g. the - scope of operations on the natural numbers), it may be convenient to bind it - to this type. When a scope :token:`scope` is bound to a type :token:`type`, any function - gets its arguments of type :token:`type` interpreted by default in scope :token:`scope` - (this default behavior can however be overwritten by explicitly using the - command :cmd:`Arguments <Arguments (scopes)>`). + Binds the notation scope :token:`scope_name` to the type or coercion class :token:`class`. + When bound, arguments of that type for any function will be interpreted in + that scope by default. This default can be overridden for individual functions + with the :cmd:`Arguments` command. The association may be convenient + when a notation scope is naturally associated with a :token:`type` (e.g. + `nat` and the natural numbers). Whether the argument of a function has some type ``type`` is determined statically. For instance, if ``f`` is a polymorphic function of type @@ -1209,10 +1124,6 @@ Binding types of arguments to an interpretation scope then :g:`a` of type :g:`t` in :g:`f t a` is not recognized as an argument to be interpreted in scope ``scope``. - More generally, any coercion :n:`@class` (see the :ref:`implicitcoercions` chapter) - can be bound to an interpretation scope. The command to do it is - :n:`Bind Scope @scope with @class` - .. coqtop:: in reset Parameter U : Set. @@ -1232,13 +1143,13 @@ Binding types of arguments to an interpretation scope .. note:: When active, a bound scope has effect on all defined functions (even if they are defined after the :cmd:`Bind Scope` directive), except if argument scopes were assigned explicitly using the - :cmd:`Arguments <Arguments (scopes)>` command. + :cmd:`Arguments` command. .. note:: The scopes ``type_scope`` and ``function_scope`` also have a local effect on interpretation. See the next section. -The ``type_scope`` interpretation scope -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +The ``type_scope`` notation scope +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. index:: type_scope @@ -1253,8 +1164,8 @@ the type of a binder, the domain and codomain of implication, the codomain of products, and more generally any type argument of a declared or defined constant. -The ``function_scope`` interpretation scope -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +The ``function_scope`` notation scope +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. index:: function_scope @@ -1264,8 +1175,8 @@ recognized to be a ``Funclass`` instance, i.e., of type :g:`forall x:A, B` or :g:`A -> B`. -Interpretation scopes used in the standard library of Coq -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Notation scopes used in the standard library of Coq +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ We give an overview of the scopes used in the standard library of Coq. For a complete list of notations in each scope, use the commands :cmd:`Print @@ -1351,40 +1262,52 @@ Scopes` or :cmd:`Print Scope`. Displaying information about scopes ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -.. cmd:: Print Visibility +.. cmd:: Print Visibility {? @scope_name } - This displays the current stack of notations in scopes and lonely - notations that is used to interpret a notation. The top of the stack + Displays the current notation scope stack. The top of the stack is displayed last. Notations in scopes whose interpretation is hidden by the same notation in a more recently opened scope are not displayed. Hence each notation is displayed only once. - .. cmdv:: Print Visibility @scope - - This displays the current stack of notations in scopes and lonely - notations assuming that :token:`scope` is pushed on top of the stack. This is - useful to know how a subterm locally occurring in the scope :token:`scope` is - interpreted. + If :n:`@scope_name` is specified, + displays the current notation scope stack + as if the scope :n:`@scope_name` is pushed on top of the stack. This is + useful to see how a subterm occurring locally in the scope is + interpreted. .. cmd:: Print Scopes - This displays all the notations, delimiting keys and corresponding - classes of all the existing interpretation scopes. It also displays the - lonely notations. + Displays, for each existing notation scope, all accessible notations + (whether or not currently in the notation scope stack), + the most-recently defined delimiting key and the class the notation scope is bound to. + The display also includes lonely notations. + + .. todo should the command report all delimiting keys? + + Use the :cmd:`Print Visibility` command to display the current notation scope stack. - .. cmdv:: Print Scope @scope - :name: Print Scope +.. cmd:: Print Scope @scope_name + :name: Print Scope - This displays all the notations defined in the interpretation scope :token:`scope`. - It also displays the delimiting key if any and the class to which the - scope is bound, if any. + Displays all notations defined in the notation scope :n:`@scope_name`. + It also displays the delimiting key and the class to which the + scope is bound, if any. .. _Abbreviations: Abbreviations -------------- -.. cmd:: {? Local} Notation @ident {+ @ident} := @term {? (only parsing)}. +.. cmd:: Notation @ident {* @ident__parm } := @one_term {? ( only parsing ) } + :name: Notation (abbreviation) + + .. todo: for some reason, Sphinx doesn't complain about a duplicate name if + :name: is omitted + + Defines an abbreviation :token:`ident` with the parameters :n:`@ident__parm`. + + This command supports the :attr:`local` attribute, which limits the notation to the + current module. An *abbreviation* is a name, possibly applied to arguments, that denotes a (presumably) more complex expression. Here are examples: @@ -1412,6 +1335,14 @@ Abbreviations Check forall A:Prop, A <-> A. Check reflexive iff. + .. coqtop:: in + + Notation Plus1 B := (Nat.add B 1). + + .. coqtop:: all + + Compute (Plus1 3). + An abbreviation expects no precedence nor associativity, since it is parsed as an usual application. Abbreviations are used as much as possible by the Coq printers unless the modifier ``(only @@ -1448,7 +1379,7 @@ Abbreviations Like for notations, if the right-hand side of an abbreviation is a partially applied constant, the abbreviation inherits the implicit - arguments and interpretation scopes of the constant. As an + arguments and notation scopes of the constant. As an exception, if the right-hand side is just of the form :n:`@@qualid`, this conventionally stops the inheritance of implicit arguments. @@ -1457,64 +1388,88 @@ Abbreviations Numeral notations ----------------- -.. cmd:: Numeral Notation @ident__1 @ident__2 @ident__3 : @scope. +.. cmd:: Numeral Notation @qualid @qualid__parse @qualid__print : @scope_name {? @numeral_modifier } :name: Numeral Notation + .. insertprodn numeral_modifier numeral_modifier + + .. prodn:: + numeral_modifier ::= ( warning after @numeral ) + | ( abstract after @numeral ) + This command allows the user to customize the way numeral literals are parsed and printed. - The token :n:`@ident__1` should be the name of an inductive type, - while :n:`@ident__2` and :n:`@ident__3` should be the names of the - parsing and printing functions, respectively. The parsing function - :n:`@ident__2` should have one of the following types: - - * :n:`Decimal.int -> @ident__1` - * :n:`Decimal.int -> option @ident__1` - * :n:`Decimal.uint -> @ident__1` - * :n:`Decimal.uint -> option @ident__1` - * :n:`Z -> @ident__1` - * :n:`Z -> option @ident__1` - * :n:`Decimal.decimal -> @ident__1` - * :n:`Decimal.decimal -> option @ident__1` - - And the printing function :n:`@ident__3` should have one of the - following types: - - * :n:`@ident__1 -> Decimal.int` - * :n:`@ident__1 -> option Decimal.int` - * :n:`@ident__1 -> Decimal.uint` - * :n:`@ident__1 -> option Decimal.uint` - * :n:`@ident__1 -> Z` - * :n:`@ident__1 -> option Z` - * :n:`@ident__1 -> Decimal.decimal` - * :n:`@ident__1 -> option Decimal.decimal` - - When parsing, the application of the parsing function - :n:`@ident__2` to the number will be fully reduced, and universes - of the resulting term will be refreshed. - - Note that only fully-reduced ground terms (terms containing only - function application, constructors, inductive type families, - sorts, and primitive integers) will be considered for printing. - - .. cmdv:: Numeral Notation @ident__1 @ident__2 @ident__3 : @scope (warning after @num). - - When a literal larger than :token:`num` is parsed, a warning - message about possible stack overflow, resulting from evaluating - :n:`@ident__2`, will be displayed. - - .. cmdv:: Numeral Notation @ident__1 @ident__2 @ident__3 : @scope (abstract after @num). - - When a literal :g:`m` larger than :token:`num` is parsed, the - result will be :n:`(@ident__2 m)`, without reduction of this - application to a normal form. Here :g:`m` will be a - :g:`Decimal.int` or :g:`Decimal.uint` or :g:`Z`, depending on the - type of the parsing function :n:`@ident__2`. This allows for a - more compact representation of literals in types such as :g:`nat`, - and limits parse failures due to stack overflow. Note that a - warning will be emitted when an integer larger than :token:`num` - is parsed. Note that :n:`(abstract after @num)` has no effect - when :n:`@ident__2` lands in an :g:`option` type. + :n:`@qualid` + the name of an inductive type, + while :n:`@qualid__parse` and :n:`@qualid__print` should be the names of the + parsing and printing functions, respectively. The parsing function + :n:`@qualid__parse` should have one of the following types: + + * :n:`Decimal.int -> @qualid` + * :n:`Decimal.int -> option @qualid` + * :n:`Decimal.uint -> @qualid` + * :n:`Decimal.uint -> option @qualid` + * :n:`Z -> @qualid` + * :n:`Z -> option @qualid` + * :n:`Decimal.decimal -> @qualid` + * :n:`Decimal.decimal -> option @qualid` + + And the printing function :n:`@qualid__print` should have one of the + following types: + + * :n:`@qualid -> Decimal.int` + * :n:`@qualid -> option Decimal.int` + * :n:`@qualid -> Decimal.uint` + * :n:`@qualid -> option Decimal.uint` + * :n:`@qualid -> Z` + * :n:`@qualid -> option Z` + * :n:`@qualid -> Decimal.decimal` + * :n:`@qualid -> option Decimal.decimal` + + When parsing, the application of the parsing function + :n:`@qualid__parse` to the number will be fully reduced, and universes + of the resulting term will be refreshed. + + Note that only fully-reduced ground terms (terms containing only + function application, constructors, inductive type families, + sorts, and primitive integers) will be considered for printing. + + :n:`( warning after @numeral )` + displays a warning message about a possible stack + overflow when calling :n:`@qualid__parse` to parse a literal larger than :n:`@numeral`. + + .. warn:: Stack overflow or segmentation fault happens when working with large numbers in @type (threshold may vary depending on your system limits and on the command executed). + + When a :cmd:`Numeral Notation` is registered in the current scope + with :n:`(warning after @numeral)`, this warning is emitted when + parsing a numeral greater than or equal to :token:`numeral`. + + :n:`( abstract after @numeral )` + returns :n:`(@qualid__parse m)` when parsing a literal + :n:`m` that's greater than :n:`@numeral` rather than reducing it to a normal form. + Here :g:`m` will be a + :g:`Decimal.int` or :g:`Decimal.uint` or :g:`Z`, depending on the + type of the parsing function :n:`@qualid__parse`. This allows for a + more compact representation of literals in types such as :g:`nat`, + and limits parse failures due to stack overflow. Note that a + warning will be emitted when an integer larger than :token:`numeral` + is parsed. Note that :n:`(abstract after @numeral)` has no effect + when :n:`@qualid__parse` lands in an :g:`option` type. + + .. warn:: To avoid stack overflow, large numbers in @type are interpreted as applications of @qualid__parse. + + When a :cmd:`Numeral Notation` is registered in the current scope + with :n:`(abstract after @numeral)`, this warning is emitted when + parsing a numeral greater than or equal to :token:`numeral`. + Typically, this indicates that the fully computed representation + of numerals can be so large that non-tail-recursive OCaml + functions run out of stack space when trying to walk them. + + .. warn:: The 'abstract after' directive has no effect when the parsing function (@qualid__parse) targets an option type. + + As noted above, the :n:`(abstract after @num)` directive has no + effect when :n:`@qualid__parse` lands in an :g:`option` type. .. exn:: Cannot interpret this number as a value of type @type @@ -1524,22 +1479,16 @@ Numeral notations only for integers or non-negative integers, and the given numeral has a fractional or exponent part or is negative. - - .. exn:: @ident should go from Decimal.int to @type or (option @type). Instead of Decimal.int, the types Decimal.uint or Z or Int63.int or Decimal.decimal could be used (you may need to require BinNums or Decimal or Int63 first). + .. exn:: @qualid__parse should go from Decimal.int to @type or (option @type). Instead of Decimal.int, the types Decimal.uint or Z or Int63.int or Decimal.decimal could be used (you may need to require BinNums or Decimal or Int63 first). The parsing function given to the :cmd:`Numeral Notation` vernacular is not of the right type. - .. exn:: @ident should go from @type to Decimal.int or (option Decimal.int). Instead of Decimal.int, the types Decimal.uint or Z or Int63.int or Decimal.decimal could be used (you may need to require BinNums or Decimal or Int63 first). + .. exn:: @qualid__print should go from @type to Decimal.int or (option Decimal.int). Instead of Decimal.int, the types Decimal.uint or Z or Int63.int or Decimal.decimal could be used (you may need to require BinNums or Decimal or Int63 first). The printing function given to the :cmd:`Numeral Notation` vernacular is not of the right type. - .. exn:: @type is not an inductive type. - - Numeral notations can only be declared for inductive types with no - arguments. - .. exn:: Unexpected term @term while parsing a numeral notation. Parsing functions must always return ground terms, made up of @@ -1554,98 +1503,39 @@ Numeral notations concrete numeral expressed as a decimal. They may not return opaque constants. - .. exn:: Cannot interpret in @scope because @ident could not be found in the current environment. - - The inductive type used to register the numeral notation is no - longer available in the environment. Most likely, this is because - the numeral notation was declared inside a functor for an - inductive type inside the functor. This use case is not currently - supported. - - Alternatively, you might be trying to use a primitive token - notation from a plugin which forgot to specify which module you - must :g:`Require` for access to that notation. - - .. exn:: Syntax error: [prim:reference] expected after 'Notation' (in [vernac:command]). - - The type passed to :cmd:`Numeral Notation` must be a single - identifier. - - .. exn:: Syntax error: [prim:reference] expected after [prim:reference] (in [vernac:command]). - - Both functions passed to :cmd:`Numeral Notation` must be single - identifiers. - - .. exn:: The reference @ident was not found in the current environment. - - Identifiers passed to :cmd:`Numeral Notation` must exist in the - global environment. - - .. exn:: @ident is bound to a notation that does not denote a reference. - - Identifiers passed to :cmd:`Numeral Notation` must be global - references, or notations which denote to single identifiers. - - .. warn:: Stack overflow or segmentation fault happens when working with large numbers in @type (threshold may vary depending on your system limits and on the command executed). - - When a :cmd:`Numeral Notation` is registered in the current scope - with :n:`(warning after @num)`, this warning is emitted when - parsing a numeral greater than or equal to :token:`num`. - - .. warn:: To avoid stack overflow, large numbers in @type are interpreted as applications of @ident__2. - - When a :cmd:`Numeral Notation` is registered in the current scope - with :n:`(abstract after @num)`, this warning is emitted when - parsing a numeral greater than or equal to :token:`num`. - Typically, this indicates that the fully computed representation - of numerals can be so large that non-tail-recursive OCaml - functions run out of stack space when trying to walk them. - - For example - - .. coqtop:: all warn - - Check 90000. - - .. warn:: The 'abstract after' directive has no effect when the parsing function (@ident__2) targets an option type. - - As noted above, the :n:`(abstract after @num)` directive has no - effect when :n:`@ident__2` lands in an :g:`option` type. - String notations ----------------- -.. cmd:: String Notation @ident__1 @ident__2 @ident__3 : @scope. +.. cmd:: String Notation @qualid @qualid__parse @qualid__print : @scope_name :name: String Notation - This command allows the user to customize the way strings are parsed - and printed. + Allows the user to customize how strings are parsed and printed. - The token :n:`@ident__1` should be the name of an inductive type, - while :n:`@ident__2` and :n:`@ident__3` should be the names of the + The token :n:`@qualid` should be the name of an inductive type, + while :n:`@qualid__parse` and :n:`@qualid__print` should be the names of the parsing and printing functions, respectively. The parsing function - :n:`@ident__2` should have one of the following types: + :n:`@qualid__parse` should have one of the following types: - * :n:`Byte.byte -> @ident__1` - * :n:`Byte.byte -> option @ident__1` - * :n:`list Byte.byte -> @ident__1` - * :n:`list Byte.byte -> option @ident__1` + * :n:`Byte.byte -> @qualid` + * :n:`Byte.byte -> option @qualid` + * :n:`list Byte.byte -> @qualid` + * :n:`list Byte.byte -> option @qualid` - And the printing function :n:`@ident__3` should have one of the + The printing function :n:`@qualid__print` should have one of the following types: - * :n:`@ident__1 -> Byte.byte` - * :n:`@ident__1 -> option Byte.byte` - * :n:`@ident__1 -> list Byte.byte` - * :n:`@ident__1 -> option (list Byte.byte)` + * :n:`@qualid -> Byte.byte` + * :n:`@qualid -> option Byte.byte` + * :n:`@qualid -> list Byte.byte` + * :n:`@qualid -> option (list Byte.byte)` - When parsing, the application of the parsing function - :n:`@ident__2` to the string will be fully reduced, and universes - of the resulting term will be refreshed. + When parsing, the application of the parsing function + :n:`@qualid__parse` to the string will be fully reduced, and universes + of the resulting term will be refreshed. - Note that only fully-reduced ground terms (terms containing only - function application, constructors, inductive type families, - sorts, and primitive integers) will be considered for printing. + Note that only fully-reduced ground terms (terms containing only + function application, constructors, inductive type families, + sorts, and primitive integers) will be considered for printing. .. exn:: Cannot interpret this string as a value of type @type @@ -1653,21 +1543,16 @@ String notations the given string. This error is given when the interpretation function returns :g:`None`. - .. exn:: @ident should go from Byte.byte or (list Byte.byte) to @type or (option @type). + .. exn:: @qualid__parse should go from Byte.byte or (list Byte.byte) to @type or (option @type). The parsing function given to the :cmd:`String Notation` vernacular is not of the right type. - .. exn:: @ident should go from @type to Byte.byte or (option Byte.byte) or (list Byte.byte) or (option (list Byte.byte)). + .. exn:: @qualid__print should go from @type to Byte.byte or (option Byte.byte) or (list Byte.byte) or (option (list Byte.byte)). The printing function given to the :cmd:`String Notation` vernacular is not of the right type. - .. exn:: @type is not an inductive type. - - String notations can only be declared for inductive types with no - arguments. - .. exn:: Unexpected term @term while parsing a string notation. Parsing functions must always return ground terms, made up of @@ -1682,11 +1567,18 @@ String notations concrete string expressed as a decimal. They may not return opaque constants. - .. exn:: Cannot interpret in @scope because @ident could not be found in the current environment. +The following errors apply to both string and numeral notations: + + .. exn:: @type is not an inductive type. + + String and numeral notations can only be declared for inductive types with no + arguments. + + .. exn:: Cannot interpret in @scope_name because @qualid could not be found in the current environment. - The inductive type used to register the string notation is no + The inductive type used to register the string or numeral notation is no longer available in the environment. Most likely, this is because - the string notation was declared inside a functor for an + the notation was declared inside a functor for an inductive type inside the functor. This use case is not currently supported. @@ -1696,149 +1588,218 @@ String notations .. exn:: Syntax error: [prim:reference] expected after 'Notation' (in [vernac:command]). - The type passed to :cmd:`String Notation` must be a single + The type passed to :cmd:`String Notation` or :cmd:`Numeral Notation` must be a single qualified identifier. .. exn:: Syntax error: [prim:reference] expected after [prim:reference] (in [vernac:command]). - Both functions passed to :cmd:`String Notation` must be single + Both functions passed to :cmd:`String Notation` or :cmd:`Numeral Notation` must be single qualified identifiers. - .. exn:: The reference @ident was not found in the current environment. + .. todo: generally we don't document syntax errors. Is this a good execption? - Identifiers passed to :cmd:`String Notation` must exist in the - global environment. + .. exn:: @qualid is bound to a notation that does not denote a reference. - .. exn:: @ident is bound to a notation that does not denote a reference. + Identifiers passed to :cmd:`String Notation` or :cmd:`Numeral Notation` must be global + references, or notations which evaluate to single qualified identifiers. - Identifiers passed to :cmd:`String Notation` must be global - references, or notations which denote to single identifiers. + .. todo note on "single qualified identifiers" https://github.com/coq/coq/pull/11718#discussion_r415076703 .. _TacticNotation: Tactic Notations ----------------- -Tactic notations allow to customize the syntax of tactics. They have the following syntax: +Tactic notations allow customizing the syntax of tactics. + +.. todo move to the Ltac chapter + +.. todo to discuss after moving to the ltac chapter: + any words of wisdom on when to use tactic notation vs ltac? + can you run into problems if you shadow another tactic or tactic notation? + If so, how to avoid ambiguity? + +.. cmd:: Tactic Notation {? ( at level @num ) } {+ @ltac_production_item } := @ltac_expr + + .. insertprodn ltac_production_item ltac_production_item + + .. prodn:: + ltac_production_item ::= @string + | @ident {? ( @ident {? , @string } ) } + + Defines a *tactic notation*, which extends the parsing and pretty-printing of tactics. + + This command supports the :attr:`local` attribute, which limits the notation to the + current module. + + :token:`num` + The parsing precedence to assign to the notation. This information is particularly + relevant for notations for tacticals. Levels can be in the range 0 .. 5 (default is 5). + + :n:`{+ @ltac_production_item }` + The notation syntax. Notations for simple tactics should begin with a :token:`string`. + Note that `Tactic Notation foo := idtac` is not valid; it should be `Tactic Notation "foo" := idtac`. -.. productionlist:: coq - tacn : Tactic Notation [`tactic_level`] [`prod_item` … `prod_item`] := `tactic`. - prod_item : `string` | `tactic_argument_type`(`ident`) - tactic_level : (at level `num`) - tactic_argument_type : ident | simple_intropattern | reference - : hyp | hyp_list | ne_hyp_list - : constr | uconstr | constr_list | ne_constr_list - : integer | integer_list | ne_integer_list - : int_or_var | int_or_var_list | ne_int_or_var_list - : tactic | tactic0 | tactic1 | tactic2 | tactic3 - : tactic4 | tactic5 + .. todo: "Tactic Notation constr := idtac" gives a nice message, would be good to show + that message for the "foo" example above. -.. cmd:: Tactic Notation {? (at level @num)} {+ @prod_item} := @tactic. + :token:`string` + represents a literal value in the notation - A tactic notation extends the parser and pretty-printer of tactics with a new - rule made of the list of production items. It then evaluates into the - tactic expression ``tactic``. For simple tactics, it is recommended to use - a terminal symbol, i.e. a string, for the first production item. The - tactic level indicates the parsing precedence of the tactic notation. - This information is particularly relevant for notations of tacticals. - Levels 0 to 5 are available (default is 5). + :n:`@ident` + is the name of a grammar nonterminal listed in the table below. In a few cases, + to maintain backward compatibility, the name differs from the nonterminal name + used elsewhere in the documentation. - .. cmd:: Print Grammar tactic + :n:`( @ident__parm {? , @string__s } )` + :n:`@ident__parm` is the parameter name associated with :n:`@ident`. The :n:`@string__s` + is the separator string to use when :n:`@ident` specifies a list with separators + (i.e. :n:`@ident` ends with `_list_sep`). - To know the parsing precedences of the existing tacticals, use the command - ``Print Grammar tactic``. + :n:`@ltac_expr` + The tactic expression to substitute for the notation. :n:`@ident__parm` + tokens appearing in :n:`@ltac_expr` are substituted with the associated + nonterminal value. - Each type of tactic argument has a specific semantic regarding how it - is parsed and how it is interpreted. The semantic is described in the - following table. The last command gives examples of tactics which use - the corresponding kind of argument. + For example, the following command defines a notation with a single parameter `x`. + + .. coqtop:: in + + Tactic Notation "destruct_with_eqn" constr(x) := destruct x eqn:?. + + For a complex example, examine the 16 `Tactic Notation "setoid_replace"`\s + defined in :file:`$COQLIB/theories/Classes/SetoidTactics.v`, which are designed + to accept any subset of 4 optional parameters. + + The nonterminals that can specified in the tactic notation are: + + .. todo uconstr represents a type with holes. At the moment uconstr doesn't + appear in the documented grammar. Maybe worth ressurecting with a better name, + maybe "open_term"? + see https://github.com/coq/coq/pull/11718#discussion_r413721234 + + .. todo 'open_constr' appears to be another possible value based on the + the message from "Tactic Notation open_constr := idtac". + Also (at least) "ref", "string", "preident", "int" and "ssrpatternarg". + (from reading .v files). + Looks like any string passed to "make0" in the code is valid. But do + we want to support all these? + @JasonGross's opinion here: https://github.com/coq/coq/pull/11718#discussion_r415387421 .. list-table:: :header-rows: 1 - * - Tactic argument type - - parsed as - - interpreted as + * - Specified :token:`ident` + - Parsed as + - Interpreted as - as in tactic * - ``ident`` - - identifier + - :token:`ident` - a user-given name - - intro + - :tacn:`intro` * - ``simple_intropattern`` - - simple_intropattern + - :token:`simple_intropattern` - an introduction pattern - - assert as + - :tacn:`assert` `as` * - ``hyp`` - - identifier + - :token:`ident` - a hypothesis defined in context - - clear + - :tacn:`clear` * - ``reference`` - - qualified identifier + - :token:`qualid` - a global reference of term - - unfold + - :tacn:`unfold` + + * - ``smart_global`` + - :token:`smart_qualid` + - a global reference of term + - :tacn:`with_strategy` * - ``constr`` - - term + - :token:`term` - a term - - exact + - :tacn:`exact` * - ``uconstr`` - - term + - :token:`term` - an untyped term - - refine + - :tacn:`refine` * - ``integer`` - - integer + - :token:`int` - an integer - * - ``int_or_var`` - - identifier or integer + - :token:`int_or_var` - an integer - - do + - :tacn:`do` + + * - ``strategy_level`` + - :token:`strategy_level` + - a strategy level + - + + * - ``strategy_level_or_var`` + - :token:`strategy_level_or_var` + - a strategy level + - :tacn:`with_strategy` * - ``tactic`` - - tactic at level 5 + - :token:`ltac_expr` - a tactic - - * - ``tacticn`` - - tactic at level n - - a tactic + * - ``tactic``\ *n* (*n* in 0..5) + - :token:`ltac_expr`\ *n* + - a tactic at level *n* - * - *entry*\ ``_list`` - - list of *entry* + - :n:`{* entry }` - a list of how *entry* is interpreted - * - ``ne_``\ *entry*\ ``_list`` - - non-empty list of *entry* + - :n:`{+ entry }` - a list of how *entry* is interpreted - - .. note:: In order to be bound in tactic definitions, each syntactic - entry for argument type must include the case of a simple |Ltac| - identifier as part of what it parses. This is naturally the case for - ``ident``, ``simple_intropattern``, ``reference``, ``constr``, ... but not for ``integer``. - This is the reason for introducing a special entry ``int_or_var`` which - evaluates to integers only but which syntactically includes - identifiers in order to be usable in tactic definitions. + * - *entry*\ ``_list_sep`` + - :n:`{*s entry }` + - a list of how *entry* is interpreted + - - .. note:: The *entry*\ ``_list`` and ``ne_``\ *entry*\ ``_list`` entries can be used in - primitive tactics or in other notations at places where a list of the - underlying entry can be used: entry is either ``constr``, ``hyp``, ``integer`` - or ``int_or_var``. + * - ``ne_``\ *entry*\ ``_list_sep`` + - :n:`{+s entry }` + - a list of how *entry* is interpreted + - + + .. todo: notation doesn't support italics + + .. note:: In order to be bound in tactic definitions, each + syntactic entry for argument type must include the case + of a simple |Ltac| identifier as part of what it + parses. This is naturally the case for ``ident``, + ``simple_intropattern``, ``reference``, ``constr``, ... + but not for ``integer`` nor for ``strategy_level``. This + is the reason for introducing special entries + ``int_or_var`` and ``strategy_level_or_var`` which + evaluate to integers or strategy levels only, + respectively, but which syntactically includes + identifiers in order to be usable in tactic definitions. -.. cmdv:: Local Tactic Notation + .. note:: The *entry*\ ``_list*`` and ``ne_``\ *entry*\ ``_list*`` + entries can be used in primitive tactics or in other + notations at places where a list of the underlying entry + can be used: entry is either ``constr``, ``hyp``, + ``integer``, ``smart_qualid``, ``strategy_level``, + ``strategy_level_or_var``, or ``int_or_var``. - Tactic notations disappear when a section is closed. They survive when - a module is closed unless the command ``Local Tactic Notation`` is used instead - of :cmd:`Tactic Notation`. .. rubric:: Footnotes diff --git a/doc/sphinx/using/libraries/funind.rst b/doc/sphinx/using/libraries/funind.rst index ed00f3d455..40f9eedcf0 100644 --- a/doc/sphinx/using/libraries/funind.rst +++ b/doc/sphinx/using/libraries/funind.rst @@ -13,7 +13,7 @@ The following command is available when the ``FunInd`` library has been loaded v This command is a generalization of :cmd:`Fixpoint`. It is a wrapper for several ways of defining a function *and* other useful related objects, namely: an induction principle that reflects the recursive - structure of the function (see :tacn:`function induction`) and its fixpoint equality. + structure of the function (see :tacn:`functional induction`) and its fixpoint equality. This defines a function similar to those defined by :cmd:`Fixpoint`. As in :cmd:`Fixpoint`, the decreasing argument must be given (unless the function is not recursive), but it might not @@ -27,7 +27,7 @@ The following command is available when the ``FunInd`` library has been loaded v to structurally recursive functions (i.e. when :n:`@fixannot` is a :n:`struct` clause). - See :tacn:`function induction` and :cmd:`Functional Scheme` for how to use + See :tacn:`functional induction` and :cmd:`Functional Scheme` for how to use the induction principle to reason easily about the function. The form of the :n:`@fixannot` clause determines which definition mechanism :cmd:`Function` uses. @@ -166,4 +166,235 @@ terminating functions. :tacn:`functional inversion` will not be available for the function. -.. seealso:: :ref:`functional-scheme` and :tacn:`function induction` +Tactics +------- + +.. tacn:: functional induction (@qualid {+ @term}) + :name: functional induction + + The tactic functional induction performs case analysis and induction + following the definition of a function. It makes use of a principle + generated by :cmd:`Function` or :cmd:`Functional Scheme`. + Note that this tactic is only available after a ``Require Import FunInd``. + + .. example:: + + .. coqtop:: reset all + + Require Import FunInd. + Functional Scheme minus_ind := Induction for minus Sort Prop. + Check minus_ind. + Lemma le_minus (n m:nat) : n - m <= n. + functional induction (minus n m) using minus_ind; simpl; auto. + Qed. + + .. note:: + :n:`(@qualid {+ @term})` must be a correct full application + of :n:`@qualid`. In particular, the rules for implicit arguments are the + same as usual. For example use :n:`@qualid` if you want to write implicit + arguments explicitly. + + .. note:: + Parentheses around :n:`@qualid {+ @term}` are not mandatory and can be skipped. + + .. note:: + :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 :cmd:`Function` or :cmd:`Functional Scheme` command) + corresponding to the sort of the goal. Therefore + :tacn:`functional induction` may fail if the induction scheme :n:`@qualid` is not + defined. + + .. note:: + There is a difference between obtaining an induction scheme + for a function by using :cmd:`Function` + and by using :cmd:`Functional Scheme` after a normal definition using + :cmd:`Fixpoint` or :cmd:`Definition`. + + .. exn:: Cannot find induction information on @qualid. + :undocumented: + + .. exn:: Not the right number of induction arguments. + :undocumented: + + .. tacv:: functional induction (@qualid {+ @term}) as @simple_intropattern using @term with @bindings_list + + Similarly to :tacn:`induction` and :tacn:`elim`, this allows giving + explicitly the name of the introduced variables, the induction principle, and + the values of dependent premises of the elimination scheme, including + *predicates* for mutual induction when :n:`@qualid` is part of a mutually + recursive definition. + +.. tacn:: functional inversion @ident + :name: functional 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 :cmd:`Function`. + Note that this tactic is only available after a ``Require Import FunInd``. + + .. exn:: Hypothesis @ident must contain at least one Function. + :undocumented: + + .. exn:: Cannot find inversion information for hypothesis @ident. + + This error may be raised when some inversion lemma failed to be generated by + Function. + + + .. tacv:: functional inversion @num + + This does the same thing as :n:`intros until @num` followed by + :n:`functional inversion @ident` where :token:`ident` is the + identifier for the last introduced hypothesis. + + .. tacv:: functional inversion @ident @qualid + functional inversion @num @qualid + + If the hypothesis :token:`ident` (or :token:`num`) has a type of the form + :n:`@qualid__1 {+ @term__i } = @qualid__2 {+ @term__j }` where + :n:`@qualid__1` and :n:`@qualid__2` are valid candidates to + functional inversion, this variant allows choosing which :token:`qualid` + is inverted. + +.. _functional-scheme: + +Generation of induction principles with ``Functional`` ``Scheme`` +----------------------------------------------------------------- + + +.. cmd:: Functional Scheme @ident__0 := Induction for @ident' Sort @sort {* with @ident__i := Induction for @ident__i' Sort @sort} + + This command is a high-level experimental tool for + generating automatically induction principles corresponding to + (possibly mutually recursive) functions. First, it must be made + available via ``Require Import FunInd``. + Each :n:`@ident__i` is a different mutually defined function + name (the names must be in the same order as when they were defined). This + command generates the induction principle for each :n:`@ident__i`, following + the recursive structure and case analyses of the corresponding function + :n:`@ident__i'`. + +.. warning:: + + There is a difference between induction schemes generated by the command + :cmd:`Functional Scheme` and these generated by the :cmd:`Function`. Indeed, + :cmd:`Function` generally produces smaller principles that are closer to how + a user would implement them. See :ref:`advanced-recursive-functions` for details. + +.. example:: + + Induction scheme for div2. + + We define the function div2 as follows: + + .. coqtop:: all + + Require Import FunInd. + Require Import Arith. + + Fixpoint div2 (n:nat) : nat := + match n with + | O => 0 + | S O => 0 + | S (S n') => S (div2 n') + end. + + The definition of a principle of induction corresponding to the + recursive structure of `div2` is defined by the command: + + .. coqtop:: all + + Functional Scheme div2_ind := Induction for div2 Sort Prop. + + You may now look at the type of div2_ind: + + .. coqtop:: all + + Check div2_ind. + + We can now prove the following lemma using this principle: + + .. coqtop:: all + + Lemma div2_le' : forall n:nat, div2 n <= n. + intro n. + pattern n, (div2 n). + apply div2_ind; intros. + auto with arith. + auto with arith. + simpl; auto with arith. + Qed. + + We can use directly the functional induction (:tacn:`functional induction`) tactic instead + of the pattern/apply trick: + + .. coqtop:: all + + Reset div2_le'. + + Lemma div2_le : forall n:nat, div2 n <= n. + intro n. + functional induction (div2 n). + auto with arith. + auto with arith. + auto with arith. + Qed. + +.. example:: + + Induction scheme for tree_size. + + We define trees by the following mutual inductive type: + + .. original LaTeX had "Variable" instead of "Axiom", which generates an ugly warning + + .. coqtop:: reset all + + Axiom A : Set. + + Inductive tree : Set := + node : A -> forest -> tree + with forest : Set := + | empty : forest + | cons : tree -> forest -> forest. + + We define the function tree_size that computes the size of a tree or a + forest. Note that we use ``Function`` which generally produces better + principles. + + .. coqtop:: all + + Require Import FunInd. + + Function tree_size (t:tree) : nat := + match t with + | node A f => S (forest_size f) + end + with forest_size (f:forest) : nat := + match f with + | empty => 0 + | cons t f' => (tree_size t + forest_size f') + end. + + Notice that the induction principles ``tree_size_ind`` and ``forest_size_ind`` + generated by ``Function`` are not mutual. + + .. coqtop:: all + + Check tree_size_ind. + + Mutual induction principles following the recursive structure of ``tree_size`` + and ``forest_size`` can be generated by the following command: + + .. coqtop:: all + + Functional Scheme tree_size_ind2 := Induction for tree_size Sort Prop + with forest_size_ind2 := Induction for forest_size Sort Prop. + + You may now look at the type of `tree_size_ind2`: + + .. coqtop:: all + + Check tree_size_ind2. diff --git a/doc/sphinx/using/libraries/index.rst b/doc/sphinx/using/libraries/index.rst index ad10869439..0bd3054788 100644 --- a/doc/sphinx/using/libraries/index.rst +++ b/doc/sphinx/using/libraries/index.rst @@ -23,3 +23,4 @@ installed with the `opam package manager ../../addendum/extraction ../../addendum/miscellaneous-extensions funind + writing diff --git a/doc/sphinx/using/libraries/writing.rst b/doc/sphinx/using/libraries/writing.rst new file mode 100644 index 0000000000..325ea2af60 --- /dev/null +++ b/doc/sphinx/using/libraries/writing.rst @@ -0,0 +1,71 @@ +Writing Coq libraries and plugins +================================= + +This section presents the part of the Coq language that is useful only +to library and plugin authors. A tutorial for writing Coq plugins is +available in the Coq repository in `doc/plugin_tutorial +<https://github.com/coq/coq/tree/master/doc/plugin_tutorial>`_. + +Deprecating library objects or tactics +-------------------------------------- + +You may use the following :term:`attribute` to deprecate a notation or +tactic. When renaming a definition or theorem, you can introduce a +deprecated compatibility alias using :cmd:`Notation (abbreviation)` +(see :ref:`the example below <compatibility-alias>`). + +.. attr:: deprecated ( {? since = @string , } {? note = @string } ) + :name: deprecated + + At least one of :n:`since` or :n:`note` must be present. If both + are present, either one may appear first and they must be separated + by a comma. + + This attribute is supported by the following commands: :cmd:`Ltac`, + :cmd:`Tactic Notation`, :cmd:`Notation`, :cmd:`Infix`. + + It can trigger the following warnings: + + .. warn:: Tactic @qualid is deprecated since @string__since. @string__note. + Tactic Notation @qualid is deprecated since @string__since. @string__note. + Notation @string is deprecated since @string__since. @string__note. + + :n:`@qualid` or :n:`@string` is the notation, + :n:`@string__since` is the version number, :n:`@string__note` is + the note (usually explains the replacement). + +.. example:: Deprecating a tactic. + + .. coqtop:: all abort warn + + #[deprecated(since="0.9", note="Use idtac instead.")] + Ltac foo := idtac. + Goal True. + Proof. + now foo. + +.. _compatibility-alias: + +.. example:: Introducing a compatibility alias + + Let's say your library initially contained: + + .. coqtop:: in + + Definition foo x := S x. + + and you want to rename `foo` into `bar`, but you want to avoid breaking + your users' code without advanced notice. To do so, replace the previous + code by the following: + + .. coqtop:: in reset + + Definition bar x := S x. + #[deprecated(since="1.2", note="Use bar instead.")] + Notation foo := bar (only parsing). + + Then, the following code still works, but emits a warning: + + .. coqtop:: all warn + + Check (foo 0). |