diff options
Diffstat (limited to 'doc/sphinx')
22 files changed, 673 insertions, 503 deletions
diff --git a/doc/sphinx/README.rst b/doc/sphinx/README.rst index 32de15ee31..1643baf0e8 100644 --- a/doc/sphinx/README.rst +++ b/doc/sphinx/README.rst @@ -239,6 +239,9 @@ In addition to the objects above, the ``coqrst`` Sphinx plugin defines the follo http://docutils.sourceforge.net/docs/ref/rst/directives.html#generic-admonition for more details. + Optionally, any text immediately following the ``.. example::`` header is + used as the example's title. + Example:: .. example:: Adding a hint to a database diff --git a/doc/sphinx/addendum/canonical-structures.rst b/doc/sphinx/addendum/canonical-structures.rst index 6843e9eaa1..3af3115a59 100644 --- a/doc/sphinx/addendum/canonical-structures.rst +++ b/doc/sphinx/addendum/canonical-structures.rst @@ -6,14 +6,14 @@ Canonical Structures :Authors: Assia Mahboubi and Enrico Tassi -This chapter explains the basics of Canonical Structure and how they can be used +This chapter explains the basics of canonical structures and how they can be used to overload notations and build a hierarchy of algebraic structures. The examples are taken from :cite:`CSwcu`. We invite the interested reader to refer to this paper for all the details that are omitted here for brevity. The interested reader shall also find in :cite:`CSlessadhoc` a detailed description -of another, complementary, use of Canonical Structures: advanced proof search. +of another, complementary, use of canonical structures: advanced proof search. This latter papers also presents many techniques one can employ to tune the -inference of Canonical Structures. +inference of canonical structures. Notation overloading @@ -38,21 +38,21 @@ of the terms that are compared. End theory. End EQ. -We use Coq modules as name spaces. This allows us to follow the same +We use Coq modules as namespaces. This allows us to follow the same pattern and naming convention for the rest of the chapter. The base -name space contains the definitions of the algebraic structure. To +namespace contains the definitions of the algebraic structure. To keep the example small, the algebraic structure ``EQ.type`` we are defining is very simplistic, and characterizes terms on which a binary relation is defined, without requiring such relation to validate any property. The inner theory module contains the overloaded notation ``==`` -and will eventually contain lemmas holding on all the instances of the +and will eventually contain lemmas holding all the instances of the algebraic structure (in this case there are no lemmas). Note that in practice the user may want to declare ``EQ.obj`` as a coercion, but we will not do that here. The following line tests that, when we assume a type ``e`` that is in -theEQ class, then we can relates two of its objects with ``==``. +theEQ class, we can relate two of its objects with ``==``. .. coqtop:: all @@ -312,7 +312,7 @@ The following script registers an ``LEQ`` class for ``nat`` and for the type constructor ``*``. It also tests that they work as expected. Unfortunately, these declarations are very verbose. In the following -subsection we show how to make these declaration more compact. +subsection we show how to make them more compact. .. coqtop:: all @@ -385,7 +385,7 @@ with message "T is not an EQ.type"”. The other utilities are used to ask |Coq| to solve a specific unification problem, that will in turn require the inference of some canonical structures. -They are explained in mode details in :cite:`CSwcu`. +They are explained in more details in :cite:`CSwcu`. We now have all we need to create a compact “packager” to declare instances of the ``LEQ`` class. diff --git a/doc/sphinx/addendum/extraction.rst b/doc/sphinx/addendum/extraction.rst index cb93d48a41..8c1eacf085 100644 --- a/doc/sphinx/addendum/extraction.rst +++ b/doc/sphinx/addendum/extraction.rst @@ -116,13 +116,13 @@ be optimized in order to be efficient (for instance, when using induction principles we do not want to compute all the recursive calls but only the needed ones). So the extraction mechanism provides an automatic optimization routine that will be called each time the user -want to generate |OCaml| programs. The optimizations can be split in two +wants to generate an |OCaml| program. The optimizations can be split in two groups: the type-preserving ones (essentially constant inlining and reductions) and the non type-preserving ones (some function abstractions of dummy types are removed when it is deemed safe in order to have more elegant types). Therefore some constants may not appear in the resulting monolithic |OCaml| program. In the case of modular extraction, -even if some inlining is done, the inlined constant are nevertheless +even if some inlining is done, the inlined constants are nevertheless printed, to ensure session-independent programs. Concerning Haskell, type-preserving optimizations are less useful @@ -185,7 +185,7 @@ The type-preserving optimizations are controlled by the following |Coq| options: **Inlining and printing of a constant declaration:** -A user can explicitly ask for a constant to be extracted by two means: +The user can explicitly ask for a constant to be extracted by two means: * by mentioning it on the extraction command line @@ -224,19 +224,18 @@ principles of extraction (logical parts and types). When an actual extraction takes place, an error is normally raised if the :cmd:`Extraction Implicit` declarations cannot be honored, that is -if any of the implicited variables still occurs in the final code. +if any of the implicit arguments still occurs in the final code. This behavior can be relaxed via the following option: .. opt:: Extraction SafeImplicits Default is on. When this option is off, a warning is emitted - instead of an error if some implicited variables still occur in the + instead of an error if some implicit arguments still occur in the final code of an extraction. This way, the extracted code may be obtained nonetheless and reviewed manually to locate the source of the issue - (in the code, some comments mark the location of these remaining - implicited variables). + (in the code, some comments mark the location of these remaining implicit arguments). Note that this extracted code might not compile or run properly, - depending of the use of these remaining implicited variables. + depending of the use of these remaining implicit arguments. Realizing axioms ~~~~~~~~~~~~~~~~ @@ -296,7 +295,7 @@ The number of type variables is checked by the system. For example: Realizing an axiom via :cmd:`Extract Constant` is only useful in the case of an informative axiom (of sort ``Type`` or ``Set``). A logical axiom -have no computational content and hence will not appears in extracted +has no computational content and hence will not appear in extracted terms. But a warning is nonetheless issued if extraction encounters a logical axiom. This warning reminds user that inconsistent logical axioms may lead to incorrect or non-terminating extracted terms. @@ -312,7 +311,7 @@ Realizing inductive types The system also provides a mechanism to specify ML terms for inductive types and constructors. For instance, the user may want to use the ML -native boolean type instead of |Coq| one. The syntax is the following: +native boolean type instead of the |Coq| one. The syntax is the following: .. cmd:: Extract Inductive @qualid => @string [ {+ @string } ] @@ -332,10 +331,10 @@ native boolean type instead of |Coq| one. The syntax is the following: branches in functional form, and then the inductive element to destruct. For instance, the match branch ``| S n => foo`` gives the functional form ``(fun n -> foo)``. Note that a constructor with no - argument is considered to have one unit argument, in order to block + arguments is considered to have one unit argument, in order to block early evaluation of the branch: ``| O => bar`` leads to the functional form ``(fun () -> bar)``. For instance, when extracting ``nat`` - into |OCaml| ``int``, the code to provide has type: + into |OCaml| ``int``, the code to be provided has type: ``(unit->'a)->(int->'a)->int->'a``. .. caution:: As for :cmd:`Extract Constant`, this command should be used with care: @@ -371,7 +370,7 @@ Typical examples are the following: When extracting to |OCaml|, if an inductive constructor or type has arity 2 and the corresponding string is enclosed by parentheses, and the string meets |OCaml|'s lexical criteria for an infix symbol, then the rest of the string is - used as infix constructor or type. + used as an infix constructor or type. .. coqtop:: in @@ -389,7 +388,7 @@ Avoiding conflicts with existing filenames ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ When using :cmd:`Extraction Library`, the names of the extracted files -directly depends from the names of the |Coq| files. It may happen that +directly depend on the names of the |Coq| files. It may happen that these filenames are in conflict with already existing files, either in the standard library of the target language or in other code that is meant to be linked with the extracted code. @@ -475,17 +474,18 @@ type-checker without any ``Obj.magic`` (see examples below). Some examples ------------- -We present here two examples of extractions, taken from the -|Coq| Standard Library. We choose |OCaml| as target language, -but all can be done in the other dialects with slight modifications. +We present here two examples of extraction, taken from the +|Coq| Standard Library. We choose |OCaml| as the target language, +but everything, with slight modifications, can also be done in the +other languages supported by extraction. We then indicate where to find other examples and tests of extraction. A detailed example: Euclidean division ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ The file ``Euclid`` contains the proof of Euclidean division. -The natural numbers used there are unary integers of type ``nat``, -defined by two constructors ``O`` and ``S``. +The natural numbers used here are unary, represented by the type``nat``, +which is defined by two constructors ``O`` and ``S``. This module contains a theorem ``eucl_dev``, whose type is:: forall b:nat, b > 0 -> forall a:nat, diveucl a b @@ -579,7 +579,7 @@ extraction test: * ``stalmarck`` : https://github.com/coq-contribs/stalmarck Note that ``continuations`` and ``multiplier`` are a bit particular. They are -examples of developments where ``Obj.magic`` are needed. This is -probably due to an heavy use of impredicativity. After compilation, those +examples of developments where ``Obj.magic`` is needed. This is +probably due to a heavy use of impredicativity. After compilation, those two examples run nonetheless, thanks to the correction of the extraction :cite:`Let02`. diff --git a/doc/sphinx/addendum/generalized-rewriting.rst b/doc/sphinx/addendum/generalized-rewriting.rst index e4d24a1f7e..197041dde9 100644 --- a/doc/sphinx/addendum/generalized-rewriting.rst +++ b/doc/sphinx/addendum/generalized-rewriting.rst @@ -25,13 +25,12 @@ The work is a complete rewrite of the previous implementation, based on the type class infrastructure. It also improves on and generalizes the previous implementation in several ways: - -+ User-extensible algorithm. The algorithm is separated in two parts: - generations of the rewriting constraints (done in ML) and solving of ++ User-extensible algorithm. The algorithm is separated into two parts: + generation of the rewriting constraints (written in ML) and solving these constraints using type class resolution. As type class resolution is extensible using tactics, this allows users to define general ways to solve morphism constraints. -+ Sub-relations. An example extension to the base algorithm is the ++ Subrelations. An example extension to the base algorithm is the ability to define one relation as a subrelation of another so that morphism declarations on one relation can be used automatically for the other. This is done purely using tactics and type class search. @@ -58,41 +57,41 @@ Relations and morphisms ~~~~~~~~~~~~~~~~~~~~~~~ A parametric *relation* ``R`` is any term of type -``forall (x1 :T1 ) ... (xn :Tn ), relation A``. +``forall (x1 : T1) ... (xn : Tn), relation A``. The expression ``A``, which depends on ``x1 ... xn`` , is called the *carrier* of the relation and ``R`` is said to be a relation over ``A``; the list ``x1,...,xn`` is the (possibly empty) list of parameters of the relation. -**Example 1 (Parametric relation):** +.. example:: Parametric relation -It is possible to implement finite sets of elements of type ``A`` as -unordered list of elements of type ``A``. -The function ``set_eq: forall (A: Type), relation (list A)`` -satisfied by two lists with the same elements is a parametric relation -over ``(list A)`` with one parameter ``A``. The type of ``set_eq`` -is convertible with ``forall (A: Type), list A -> list A -> Prop.`` + It is possible to implement finite sets of elements of type ``A`` as + unordered lists of elements of type ``A``. + The function ``set_eq: forall (A : Type), relation (list A)`` + satisfied by two lists with the same elements is a parametric relation + over ``(list A)`` with one parameter ``A``. The type of ``set_eq`` + is convertible with ``forall (A : Type), list A -> list A -> Prop.`` An *instance* of a parametric relation ``R`` with n parameters is any term -``(R t1 ... tn )``. +``(R t1 ... tn)``. Let ``R`` be a relation over ``A`` with ``n`` parameters. A term is a parametric proof of reflexivity for ``R`` if it has type -``forall (x1 :T1 ) ... (xn :Tn), reflexive (R x1 ... xn )``. +``forall (x1 : T1) ... (xn : Tn), reflexive (R x1 ... xn)``. Similar definitions are given for parametric proofs of symmetry and transitivity. -**Example 2 (Parametric relation (cont.)):** +.. example:: Parametric relation (continued) -The ``set_eq`` relation of the previous example can be proved to be -reflexive, symmetric and transitive. A parametric unary function ``f`` of type -``forall (x1 :T1 ) ... (xn :Tn ), A1 -> A2`` covariantly respects two parametric relation instances -``R1`` and ``R2`` if, whenever ``x``, ``y`` satisfy ``R1 x y``, their images (``f x``) and (``f y``) -satisfy ``R2 (f x) (f y)``. An ``f`` that respects its input and output -relations will be called a unary covariant *morphism*. We can also say -that ``f`` is a monotone function with respect to ``R1`` and ``R2`` . The -sequence ``x1 ... xn`` represents the parameters of the morphism. + The ``set_eq`` relation of the previous example can be proved to be + reflexive, symmetric and transitive. A parametric unary function ``f`` of type + ``forall (x1 : T1) ... (xn : Tn), A1 -> A2`` covariantly respects two parametric relation instances + ``R1`` and ``R2`` if, whenever ``x``, ``y`` satisfy ``R1 x y``, their images (``f x``) and (``f y``) + satisfy ``R2 (f x) (f y)``. An ``f`` that respects its input and output + relations will be called a unary covariant *morphism*. We can also say + that ``f`` is a monotone function with respect to ``R1`` and ``R2`` . The + sequence ``x1 ... xn`` represents the parameters of the morphism. Let ``R1`` and ``R2`` be two parametric relations. The *signature* of a -parametric morphism of type ``forall (x1 :T1 ) ... (xn :Tn ), A1 -> A2`` +parametric morphism of type ``forall (x1 : T1) ... (xn : Tn), A1 -> A2`` that covariantly respects two instances :math:`I_{R_1}` and :math:`I_{R_2}` of ``R1`` and ``R2`` is written :math:`I_{R_1} ++> I_{R_2}`. Notice that the special arrow ++>, which reminds the reader of covariance, is placed between the two relation @@ -118,29 +117,29 @@ covariant and contravariant. An instance of a parametric morphism :math:`f` with :math:`n` parameters is any term :math:`f \, t_1 \ldots t_n`. -**Example 3 (Morphisms):** +.. example:: Morphisms -Continuing the previous example, let ``union: forall (A: Type), list A -> list A -> list A`` -perform the union of two sets by appending one list to the other. ``union` is a binary -morphism parametric over ``A`` that respects the relation instance -``(set_eq A)``. The latter condition is proved by showing: + Continuing the previous example, let ``union: forall (A : Type), list A -> list A -> list A`` + perform the union of two sets by appending one list to the other. ``union` is a binary + morphism parametric over ``A`` that respects the relation instance + ``(set_eq A)``. The latter condition is proved by showing: -.. coqtop:: in + .. coqtop:: in - forall (A: Type) (S1 S1’ S2 S2’: list A), - set_eq A S1 S1’ -> - set_eq A S2 S2’ -> - set_eq A (union A S1 S2) (union A S1’ S2’). + forall (A : Type) (S1 S1’ S2 S2’ : list A), + set_eq A S1 S1’ -> + set_eq A S2 S2’ -> + set_eq A (union A S1 S2) (union A S1’ S2’). -The signature of the function ``union A`` is ``set_eq A ==> set_eq A ==> set_eq A`` -for all ``A``. + The signature of the function ``union A`` is ``set_eq A ==> set_eq A ==> set_eq A`` + for all ``A``. -**Example 4 (Contravariant morphism):** +.. example:: Contravariant morphisms -The division function ``Rdiv: R -> R -> R`` is a morphism of signature -``le ++> le --> le`` where ``le`` is the usual order relation over -real numbers. Notice that division is covariant in its first argument -and contravariant in its second argument. + The division function ``Rdiv : R -> R -> R`` is a morphism of signature + ``le ++> le --> le`` where ``le`` is the usual order relation over + real numbers. Notice that division is covariant in its first argument + and contravariant in its second argument. Leibniz equality is a relation and every function is a morphism that respects Leibniz equality. Unfortunately, Leibniz equality is not @@ -149,180 +148,178 @@ always the intended equality for a given structure. In the next section we will describe the commands to register terms as parametric relations and morphisms. Several tactics that deal with equality in Coq can also work with the registered relations. The exact -list of tactic will be given :ref:`in this section <tactics-enabled-on-user-provided-relations>`. -For instance, the tactic reflexivity can be used to close a goal ``R n n`` whenever ``R`` +list of tactics will be given :ref:`in this section <tactics-enabled-on-user-provided-relations>`. +For instance, the tactic reflexivity can be used to solve a goal ``R n n`` whenever ``R`` is an instance of a registered reflexive relation. However, the tactics that replace in a context ``C[]`` one term with another one related by ``R`` must verify that ``C[]`` is a morphism that respects the -intended relation. Currently the verification consists in checking +intended relation. Currently the verification consists of checking whether ``C[]`` is a syntactic composition of morphism instances that respects some obvious compatibility constraints. +.. example:: Rewriting -**Example 5 (Rewriting):** - -Continuing the previous examples, suppose that the user must prove -``set_eq int (union int (union int S1 S2) S2) (f S1 S2)`` under the -hypothesis ``H: set_eq int S2 (@nil int)``. It -is possible to use the ``rewrite`` tactic to replace the first two -occurrences of ``S2`` with ``@nil int`` in the goal since the -context ``set_eq int (union int (union int S1 nil) nil) (f S1 S2)``, -being a composition of morphisms instances, is a morphism. However the -tactic will fail replacing the third occurrence of ``S2`` unless ``f`` -has also been declared as a morphism. + Continuing the previous examples, suppose that the user must prove + ``set_eq int (union int (union int S1 S2) S2) (f S1 S2)`` under the + hypothesis ``H : set_eq int S2 (@nil int)``. It + is possible to use the ``rewrite`` tactic to replace the first two + occurrences of ``S2`` with ``@nil int`` in the goal since the + context ``set_eq int (union int (union int S1 nil) nil) (f S1 S2)``, + being a composition of morphisms instances, is a morphism. However the + tactic will fail replacing the third occurrence of ``S2`` unless ``f`` + has also been declared as a morphism. Adding new relations and morphisms ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -A parametric relation :g:`Aeq: forall (y1 : β1 ... ym : βm )`, -:g:`relation (A t1 ... tn)` over :g:`(A : αi -> ... αn -> Type)` can be -declared with the following command: +.. cmd:: Add Parametric Relation (x1 : T1) ... (xn : Tk) : (A t1 ... tn) (Aeq t′1 ... t′m) {? reflexivity proved by refl} {? symmetry proved by sym} {? transitivity proved by trans} as @ident -.. cmd:: Add Parametric Relation (x1 : T1) ... (xn : Tk) : (A t1 ... tn) (Aeq t′1 ... t′m ) {? reflexivity proved by refl} {? symmetry proved by sym} {? transitivity proved by trans} as @ident - -after having required the ``Setoid`` module with the ``Require Setoid`` -command. + This command declares a parametric relation :g:`Aeq: forall (y1 : β1 ... ym : βm)`, + :g:`relation (A t1 ... tn)` over :g:`(A : αi -> ... αn -> Type)`. -The :g:`@ident` gives a unique name to the morphism and it is used -by the command to generate fresh names for automatically provided -lemmas used internally. + The :token:`ident` gives a unique name to the morphism and it is used + by the command to generate fresh names for automatically provided + lemmas used internally. -Notice that the carrier and relation parameters may refer to the -context of variables introduced at the beginning of the declaration, -but the instances need not be made only of variables. Also notice that -``A`` is *not* required to be a term having the same parameters as ``Aeq``, -although that is often the case in practice (this departs from the -previous implementation). + Notice that the carrier and relation parameters may refer to the + context of variables introduced at the beginning of the declaration, + but the instances need not be made only of variables. Also notice that + ``A`` is *not* required to be a term having the same parameters as ``Aeq``, + although that is often the case in practice (this departs from the + previous implementation). + To use this command, you need to first import the module ``Setoid`` using + the command ``Require Import Setoid``. .. cmd:: Add Relation -In case the carrier and relations are not parametric, one can use this command -instead, whose syntax is the same except there is no local context. + In case the carrier and relations are not parametric, one can use this command + instead, whose syntax is the same except there is no local context. -The proofs of reflexivity, symmetry and transitivity can be omitted if -the relation is not an equivalence relation. The proofs must be -instances of the corresponding relation definitions: e.g. the proof of -reflexivity must have a type convertible to -:g:`reflexive (A t1 ... tn) (Aeq t′ 1 …t′ n )`. -Each proof may refer to the introduced variables as well. + The proofs of reflexivity, symmetry and transitivity can be omitted if + the relation is not an equivalence relation. The proofs must be + instances of the corresponding relation definitions: e.g. the proof of + reflexivity must have a type convertible to + :g:`reflexive (A t1 ... tn) (Aeq t′ 1 …t′ n)`. + Each proof may refer to the introduced variables as well. -**Example 6 (Parametric relation):** +.. example:: Parametric relation -For Leibniz equality, we may declare: + For Leibniz equality, we may declare: -.. coqtop:: in + .. coqtop:: in - Add Parametric Relation (A : Type) : A (@eq A) - [reflexivity proved by @refl_equal A] - ... + Add Parametric Relation (A : Type) : A (@eq A) + [reflexivity proved by @refl_equal A] + ... Some tactics (:tacn:`reflexivity`, :tacn:`symmetry`, :tacn:`transitivity`) work only on relations that respect the expected properties. The remaining tactics -(`replace`, :tacn:`rewrite` and derived tactics such as :tacn:`autorewrite`) do not +(:tacn:`replace`, :tacn:`rewrite` and derived tactics such as :tacn:`autorewrite`) do not require any properties over the relation. However, they are able to replace terms with related ones only in contexts that are syntactic compositions of parametric morphism instances declared with the following command. -.. cmd:: Add Parametric Morphism (x1 : T1 ) ... (xk : Tk ) : (f t1 ... tn ) with signature sig as @ident +.. cmd:: Add Parametric Morphism (x1 : T1) ... (xk : Tk) : (f t1 ... tn) with signature sig as @ident -The command declares ``f`` as a parametric morphism of signature ``sig``. The -identifier ``id`` gives a unique name to the morphism and it is used as -the base name of the type class instance definition and as the name of -the lemma that proves the well-definedness of the morphism. The -parameters of the morphism as well as the signature may refer to the -context of variables. The command asks the user to prove interactively -that ``f`` respects the relations identified from the signature. + This command declares ``f`` as a parametric morphism of signature ``sig``. The + identifier :token:`ident` gives a unique name to the morphism and it is used as + the base name of the type class instance definition and as the name of + the lemma that proves the well-definedness of the morphism. The + parameters of the morphism as well as the signature may refer to the + context of variables. The command asks the user to prove interactively + that ``f`` respects the relations identified from the signature. -**Example 7:** +.. example:: -We start the example by assuming a small theory over -homogeneous sets and we declare set equality as a parametric -equivalence relation and union of two sets as a parametric morphism. + We start the example by assuming a small theory over + homogeneous sets and we declare set equality as a parametric + equivalence relation and union of two sets as a parametric morphism. -.. coqtop:: in + .. coqtop:: in - Require Export Setoid. - Require Export Relation_Definitions. + Require Export Setoid. + Require Export Relation_Definitions. - Set Implicit Arguments. + Set Implicit Arguments. - Parameter set: Type -> Type. - Parameter empty: forall A, set A. - Parameter eq_set: forall A, set A -> set A -> Prop. - Parameter union: forall A, set A -> set A -> set A. + Parameter set : Type -> Type. + Parameter empty : forall A, set A. + Parameter eq_set : forall A, set A -> set A -> Prop. + Parameter union : forall A, set A -> set A -> set A. - Axiom eq_set_refl: forall A, reflexive _ (eq_set (A:=A)). - Axiom eq_set_sym: forall A, symmetric _ (eq_set (A:=A)). - Axiom eq_set_trans: forall A, transitive _ (eq_set (A:=A)). - Axiom empty_neutral: forall A (S: set A), eq_set (union S (empty A)) S. + Axiom eq_set_refl : forall A, reflexive _ (eq_set (A:=A)). + Axiom eq_set_sym : forall A, symmetric _ (eq_set (A:=A)). + Axiom eq_set_trans : forall A, transitive _ (eq_set (A:=A)). + Axiom empty_neutral : forall A (S : set A), eq_set (union S (empty A)) S. - Axiom union_compat: forall (A : Type), - forall x x' : set A, eq_set x x' -> - forall y y' : set A, eq_set y y' -> - eq_set (union x y) (union x' y'). + Axiom union_compat : + forall (A : Type), + forall x x' : set A, eq_set x x' -> + forall y y' : set A, eq_set y y' -> + eq_set (union x y) (union x' y'). - Add Parametric Relation A : (set A) (@eq_set A) - reflexivity proved by (eq_set_refl (A:=A)) - symmetry proved by (eq_set_sym (A:=A)) - transitivity proved by (eq_set_trans (A:=A)) - as eq_set_rel. + Add Parametric Relation A : (set A) (@eq_set A) + reflexivity proved by (eq_set_refl (A:=A)) + symmetry proved by (eq_set_sym (A:=A)) + transitivity proved by (eq_set_trans (A:=A)) + as eq_set_rel. - Add Parametric Morphism A : (@union A) with - signature (@eq_set A) ==> (@eq_set A) ==> (@eq_set A) as union_mor. - Proof. - exact (@union_compat A). - Qed. + Add Parametric Morphism A : (@union A) + with signature (@eq_set A) ==> (@eq_set A) ==> (@eq_set A) as union_mor. + Proof. + exact (@union_compat A). + Qed. -It is possible to reduce the burden of specifying parameters using -(maximally inserted) implicit arguments. If ``A`` is always set as -maximally implicit in the previous example, one can write: + It is possible to reduce the burden of specifying parameters using + (maximally inserted) implicit arguments. If ``A`` is always set as + maximally implicit in the previous example, one can write: -.. coqtop:: in + .. coqtop:: in - Add Parametric Relation A : (set A) eq_set - reflexivity proved by eq_set_refl - symmetry proved by eq_set_sym - transitivity proved by eq_set_trans - as eq_set_rel. + Add Parametric Relation A : (set A) eq_set + reflexivity proved by eq_set_refl + symmetry proved by eq_set_sym + transitivity proved by eq_set_trans + as eq_set_rel. -.. coqtop:: in + .. coqtop:: in - Add Parametric Morphism A : (@union A) with - signature eq_set ==> eq_set ==> eq_set as union_mor. + Add Parametric Morphism A : (@union A) with + signature eq_set ==> eq_set ==> eq_set as union_mor. -.. coqtop:: in + .. coqtop:: in - Proof. exact (@union_compat A). Qed. + Proof. exact (@union_compat A). Qed. -We proceed now by proving a simple lemma performing a rewrite step and -then applying reflexivity, as we would do working with Leibniz -equality. Both tactic applications are accepted since the required -properties over ``eq_set`` and ``union`` can be established from the two -declarations above. + We proceed now by proving a simple lemma performing a rewrite step and + then applying reflexivity, as we would do working with Leibniz + equality. Both tactic applications are accepted since the required + properties over ``eq_set`` and ``union`` can be established from the two + declarations above. -.. coqtop:: in + .. coqtop:: in - Goal forall (S: set nat), - eq_set (union (union S empty) S) (union S S). + Goal forall (S : set nat), + eq_set (union (union S empty) S) (union S S). -.. coqtop:: in + .. coqtop:: in - Proof. intros. rewrite empty_neutral. reflexivity. Qed. + Proof. intros. rewrite empty_neutral. reflexivity. Qed. -The tables of relations and morphisms are managed by the type class -instance mechanism. The behavior on section close is to generalize the -instances by the variables of the section (and possibly hypotheses -used in the proofs of instance declarations) but not to export them in -the rest of the development for proof search. One can use the -cmd:`Existing Instance` command to do so outside the section, using the name of the -declared morphism suffixed by ``_Morphism``, or use the ``Global`` modifier -for the corresponding class instance declaration -(see :ref:`First Class Setoids and Morphisms <first-class-setoids-and-morphisms>`) at -definition time. When loading a compiled file or importing a module, -all the declarations of this module will be loaded. + The tables of relations and morphisms are managed by the type class + instance mechanism. The behavior on section close is to generalize the + instances by the variables of the section (and possibly hypotheses + used in the proofs of instance declarations) but not to export them in + the rest of the development for proof search. One can use the + cmd:`Existing Instance` command to do so outside the section, using the name of the + declared morphism suffixed by ``_Morphism``, or use the ``Global`` modifier + for the corresponding class instance declaration + (see :ref:`First Class Setoids and Morphisms <first-class-setoids-and-morphisms>`) at + definition time. When loading a compiled file or importing a module, + all the declarations of this module will be loaded. Rewriting and non reflexive relations @@ -332,31 +329,31 @@ To replace only one argument of an n-ary morphism it is necessary to prove that all the other arguments are related to themselves by the respective relation instances. -**Example 8:** +.. example:: -To replace ``(union S empty)`` with ``S`` in ``(union (union S empty) S) (union S S)`` -the rewrite tactic must exploit the monotony of ``union`` (axiom ``union_compat`` -in the previous example). Applying ``union_compat`` by hand we are left with the -goal ``eq_set (union S S) (union S S)``. + To replace ``(union S empty)`` with ``S`` in ``(union (union S empty) S) (union S S)`` + the rewrite tactic must exploit the monotony of ``union`` (axiom ``union_compat`` + in the previous example). Applying ``union_compat`` by hand we are left with the + goal ``eq_set (union S S) (union S S)``. When the relations associated to some arguments are not reflexive, the tactic cannot automatically prove the reflexivity goals, that are left to the user. -Setoids whose relation are partial equivalence relations (PER) are -useful to deal with partial functions. Let ``R`` be a PER. We say that an +Setoids whose relations are partial equivalence relations (PER) are +useful for dealing with partial functions. Let ``R`` be a PER. We say that an element ``x`` is defined if ``R x x``. A partial function whose domain -comprises all the defined elements only is declared as a morphism that +comprises all the defined elements is declared as a morphism that respects ``R``. Every time a rewriting step is performed the user must prove that the argument of the morphism is defined. -**Example 9:** +.. example:: -Let ``eqO`` be ``fun x y => x = y /\ x <> 0`` (the -smaller PER over non zero elements). Division can be declared as a -morphism of signature ``eq ==> eq0 ==> eq``. Replace ``x`` with -``y`` in ``div x n = div y n`` opens the additional goal ``eq0 n n`` -that is equivalent to ``n = n /\ n <> 0``. + Let ``eqO`` be ``fun x y => x = y /\ x <> 0`` (the + smallest PER over non zero elements). Division can be declared as a + morphism of signature ``eq ==> eq0 ==> eq``. Replacing ``x`` with + ``y`` in ``div x n = div y n`` opens an additional goal ``eq0 n n`` + which is equivalent to ``n = n /\ n <> 0``. Rewriting and non symmetric relations @@ -371,44 +368,44 @@ a contravariant position. In a similar way, replacement in an hypothesis can be performed only if the replaced term occurs in a covariant position. -**Example 10 (Covariance and contravariance):** - -Suppose that division over real numbers has been defined as a morphism of signature -``Z.div: Z.lt ++> Z.lt --> Z.lt`` (i.e. ``Z.div`` is increasing in -its first argument, but decreasing on the second one). Let ``<`` -denotes ``Z.lt``. Under the hypothesis ``H: x < y`` we have -``k < x / y -> k < x / x``, but not ``k < y / x -> k < x / x``. Dually, -under the same hypothesis ``k < x / y -> k < y / y`` holds, but -``k < y / x -> k < y / y`` does not. Thus, if the current goal is -``k < x / x``, it is possible to replace only the second occurrence of -``x`` (in contravariant position) with ``y`` since the obtained goal -must imply the current one. On the contrary, if ``k < x / x`` is an -hypothesis, it is possible to replace only the first occurrence of -``x`` (in covariant position) with ``y`` since the current -hypothesis must imply the obtained one. - -Contrary to the previous implementation, no specific error message -will be raised when trying to replace a term that occurs in the wrong -position. It will only fail because the rewriting constraints are not -satisfiable. However it is possible to use the at modifier to specify -which occurrences should be rewritten. - -As expected, composing morphisms together propagates the variance -annotations by switching the variance every time a contravariant -position is traversed. - -**Example 11:** - -Let us continue the previous example and let us consider -the goal ``x / (x / x) < k``. The first and third occurrences of -``x`` are in a contravariant position, while the second one is in -covariant position. More in detail, the second occurrence of ``x`` -occurs covariantly in ``(x / x)`` (since division is covariant in -its first argument), and thus contravariantly in ``x / (x / x)`` -(since division is contravariant in its second argument), and finally -covariantly in ``x / (x / x) < k`` (since ``<``, as every -transitive relation, is contravariant in its first argument with -respect to the relation itself). +.. example:: Covariance and contravariance + + Suppose that division over real numbers has been defined as a morphism of signature + ``Z.div : Z.lt ++> Z.lt --> Z.lt`` (i.e. ``Z.div`` is increasing in + its first argument, but decreasing on the second one). Let ``<`` + denote ``Z.lt``. Under the hypothesis ``H : x < y`` we have + ``k < x / y -> k < x / x``, but not ``k < y / x -> k < x / x``. Dually, + under the same hypothesis ``k < x / y -> k < y / y`` holds, but + ``k < y / x -> k < y / y`` does not. Thus, if the current goal is + ``k < x / x``, it is possible to replace only the second occurrence of + ``x`` (in contravariant position) with ``y`` since the obtained goal + must imply the current one. On the contrary, if ``k < x / x`` is an + hypothesis, it is possible to replace only the first occurrence of + ``x`` (in covariant position) with ``y`` since the current + hypothesis must imply the obtained one. + + Contrary to the previous implementation, no specific error message + will be raised when trying to replace a term that occurs in the wrong + position. It will only fail because the rewriting constraints are not + satisfiable. However it is possible to use the at modifier to specify + which occurrences should be rewritten. + + As expected, composing morphisms together propagates the variance + annotations by switching the variance every time a contravariant + position is traversed. + +.. example:: + + Let us continue the previous example and let us consider + the goal ``x / (x / x) < k``. The first and third occurrences of + ``x`` are in a contravariant position, while the second one is in + covariant position. More in detail, the second occurrence of ``x`` + occurs covariantly in ``(x / x)`` (since division is covariant in + its first argument), and thus contravariantly in ``x / (x / x)`` + (since division is contravariant in its second argument), and finally + covariantly in ``x / (x / x) < k`` (since ``<``, as every + transitive relation, is contravariant in its first argument with + respect to the relation itself). Rewriting in ambiguous setoid contexts @@ -417,15 +414,14 @@ Rewriting in ambiguous setoid contexts One function can respect several different relations and thus it can be declared as a morphism having multiple signatures. -**Example 12:** - +.. example:: -Union over homogeneous lists can be given all the -following signatures: ``eq ==> eq ==> eq`` (``eq`` being the -equality over ordered lists) ``set_eq ==> set_eq ==> set_eq`` -(``set_eq`` being the equality over unordered lists up to duplicates), -``multiset_eq ==> multiset_eq ==> multiset_eq`` (``multiset_eq`` -being the equality over unordered lists). + Union over homogeneous lists can be given all the + following signatures: ``eq ==> eq ==> eq`` (``eq`` being the + equality over ordered lists) ``set_eq ==> set_eq ==> set_eq`` + (``set_eq`` being the equality over unordered lists up to duplicates), + ``multiset_eq ==> multiset_eq ==> multiset_eq`` (``multiset_eq`` + being the equality over unordered lists). To declare multiple signatures for a morphism, repeat the :cmd:`Add Morphism` command. @@ -435,7 +431,7 @@ rewrite request is ambiguous, since it is unclear what relations should be used to perform the rewriting. Contrary to the previous implementation, the tactic will always choose the first possible solution to the set of constraints generated by a rewrite and will not -try to find *all* possible solutions to warn the user about. +try to find *all* the possible solutions to warn the user about them. Commands and tactics @@ -457,7 +453,7 @@ hint database. For example, the declaration: .. coqtop:: in - Add Parametric Relation (x1 : T1) ... (xn : Tk) : (A t1 ... tn) (Aeq t′1 ... t′m) + Add Parametric Relation (x1 : T1) ... (xn : Tn) : (A t1 ... tn) (Aeq t′1 ... t′m) [reflexivity proved by refl] [symmetry proved by sym] [transitivity proved by trans] @@ -468,7 +464,7 @@ is equivalent to an instance declaration: .. coqtop:: in - Instance (x1 : T1) ... (xn : Tk) => id : @Equivalence (A t1 ... tn) (Aeq t′1 ... t′m) := + Instance (x1 : T1) ... (xn : Tn) => id : @Equivalence (A t1 ... tn) (Aeq t′1 ... t′m) := [Equivalence_Reflexive := refl] [Equivalence_Symmetric := sym] [Equivalence_Transitive := trans]. @@ -491,37 +487,37 @@ handled by encoding them as records. In the following example, the projections of the setoid relation and of the morphism function can be registered as parametric relations and morphisms. -**Example 13 (First class setoids):** +.. example:: First class setoids -.. coqtop:: in + .. coqtop:: in - Require Import Relation_Definitions Setoid. + Require Import Relation_Definitions Setoid. - Record Setoid: Type := - { car: Type; - eq: car -> car -> Prop; - refl: reflexive _ eq; - sym: symmetric _ eq; - trans: transitive _ eq - }. + Record Setoid : Type := + { car: Type; + eq: car -> car -> Prop; + refl: reflexive _ eq; + sym: symmetric _ eq; + trans: transitive _ eq + }. - Add Parametric Relation (s : Setoid) : (@car s) (@eq s) - reflexivity proved by (refl s) - symmetry proved by (sym s) - transitivity proved by (trans s) as eq_rel. + Add Parametric Relation (s : Setoid) : (@car s) (@eq s) + reflexivity proved by (refl s) + symmetry proved by (sym s) + transitivity proved by (trans s) as eq_rel. - Record Morphism (S1 S2:Setoid): Type := - { f: car S1 -> car S2; - compat: forall (x1 x2: car S1), eq S1 x1 x2 -> eq S2 (f x1) (f x2) - }. + Record Morphism (S1 S2 : Setoid) : Type := + { f: car S1 -> car S2; + compat: forall (x1 x2 : car S1), eq S1 x1 x2 -> eq S2 (f x1) (f x2) + }. - Add Parametric Morphism (S1 S2 : Setoid) (M : Morphism S1 S2) : - (@f S1 S2 M) with signature (@eq S1 ==> @eq S2) as apply_mor. - Proof. apply (compat S1 S2 M). Qed. + Add Parametric Morphism (S1 S2 : Setoid) (M : Morphism S1 S2) : + (@f S1 S2 M) with signature (@eq S1 ==> @eq S2) as apply_mor. + Proof. apply (compat S1 S2 M). Qed. - Lemma test: forall (S1 S2:Setoid) (m: Morphism S1 S2) - (x y: car S1), eq S1 x y -> eq S2 (f _ _ m x) (f _ _ m y). - Proof. intros. rewrite H. reflexivity. Qed. + Lemma test : forall (S1 S2 : Setoid) (m : Morphism S1 S2) + (x y : car S1), eq S1 x y -> eq S2 (f _ _ m x) (f _ _ m y). + Proof. intros. rewrite H. reflexivity. Qed. .. _tactics-enabled-on-user-provided-relations: @@ -539,33 +535,32 @@ pass additional arguments such as ``using relation``. .. tacv:: setoid_reflexivity :name: setoid_reflexivity -.. tacv:: setoid_symmetry [in @ident] +.. tacv:: setoid_symmetry {? in @ident} :name: setoid_symmetry .. tacv:: setoid_transitivity :name: setoid_transitivity -.. tacv:: setoid_rewrite [@orientation] @term [at @occs] [in @ident] +.. tacv:: setoid_rewrite {? @orientation} @term {? at @occs} {? in @ident} :name: setoid_rewrite -.. tacv:: setoid_replace @term with @term [in @ident] [using relation @term] [by @tactic] +.. tacv:: setoid_replace @term with @term {? in @ident} {? using relation @term} {? by @tactic} :name: setoid_replace - -The ``using relation`` arguments cannot be passed to the unprefixed form. -The latter argument tells the tactic what parametric relation should -be used to replace the first tactic argument with the second one. If -omitted, it defaults to the ``DefaultRelation`` instance on the type of -the objects. By default, it means the most recent ``Equivalence`` instance -in the environment, but it can be customized by declaring -new ``DefaultRelation`` instances. As Leibniz equality is a declared -equivalence, it will fall back to it if no other relation is declared -on a given type. + The ``using relation`` arguments cannot be passed to the unprefixed form. + The latter argument tells the tactic what parametric relation should + be used to replace the first tactic argument with the second one. If + omitted, it defaults to the ``DefaultRelation`` instance on the type of + the objects. By default, it means the most recent ``Equivalence`` instance + in the environment, but it can be customized by declaring + new ``DefaultRelation`` instances. As Leibniz equality is a declared + equivalence, it will fall back to it if no other relation is declared + on a given type. Every derived tactic that is based on the unprefixed forms of the tactics considered above will also work up to user defined relations. For instance, it is possible to register hints for :tacn:`autorewrite` that -are not proof of Leibniz equalities. In particular it is possible to +are not proofs of Leibniz equalities. In particular it is possible to exploit :tacn:`autorewrite` to simulate normalization in a term rewriting system up to user defined equalities. @@ -575,39 +570,39 @@ Printing relations and morphisms .. cmd:: Print Instances -This command can be used to show the list of currently -registered ``Reflexive`` (using ``Print Instances Reflexive``), ``Symmetric`` -or ``Transitive`` relations, Equivalences, PreOrders, PERs, and Morphisms -(implemented as ``Proper`` instances). When the rewriting tactics refuse -to replace a term in a context because the latter is not a composition -of morphisms, the :cmd:`Print Instances` command can be useful to understand -what additional morphisms should be registered. + This command can be used to show the list of currently + registered ``Reflexive`` (using ``Print Instances Reflexive``), ``Symmetric`` + or ``Transitive`` relations, Equivalences, PreOrders, PERs, and Morphisms + (implemented as ``Proper`` instances). When the rewriting tactics refuse + to replace a term in a context because the latter is not a composition + of morphisms, the :cmd:`Print Instances` command can be useful to understand + what additional morphisms should be registered. Deprecated syntax and backward incompatibilities ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Due to backward compatibility reasons, the following syntax for the -declaration of setoids and morphisms is also accepted. - .. cmd:: Add Setoid @A @Aeq @ST as @ident -where ``Aeq`` is a congruence relation without parameters, ``A`` is its carrier -and ``ST`` is an object of type (``Setoid_Theory A Aeq``) (i.e. a record -packing together the reflexivity, symmetry and transitivity lemmas). -Notice that the syntax is not completely backward compatible since the -identifier was not required. + This command for declaring setoids and morphisms is also accepted due + to backward compatibility reasons. + + Here ``Aeq`` is a congruence relation without parameters, ``A`` is its carrier + and ``ST`` is an object of type (``Setoid_Theory A Aeq``) (i.e. a record + packing together the reflexivity, symmetry and transitivity lemmas). + Notice that the syntax is not completely backward compatible since the + identifier was not required. .. cmd:: Add Morphism f : @ident :name: Add Morphism -The latter command also is restricted to the declaration of morphisms -without parameters. It is not fully backward compatible since the -property the user is asked to prove is slightly different: for n-ary -morphisms the hypotheses of the property are permuted; moreover, when -the morphism returns a proposition, the property is now stated using a -bi-implication in place of a simple implication. In practice, porting -an old development to the new semantics is usually quite simple. + This command is restricted to the declaration of morphisms + without parameters. It is not fully backward compatible since the + property the user is asked to prove is slightly different: for n-ary + morphisms the hypotheses of the property are permuted; moreover, when + the morphism returns a proposition, the property is now stated using a + bi-implication in place of a simple implication. In practice, porting + an old development to the new semantics is usually quite simple. Notice that several limitations of the old implementation have been lifted. In particular, it is now possible to declare several relations @@ -657,9 +652,8 @@ in ``Prop`` are implicitly translated to such applications). Indeed, when rewriting under a lambda, binding variable ``x``, say from ``P x`` to ``Q x`` using the relation iff, the tactic will generate a proof of ``pointwise_relation A iff (fun x => P x) (fun x => Q x)`` from the proof -of ``iff (P x) (Q x)`` and a constraint of the form Proper -``(pointwise_relation A iff ==> ?) m`` will be generated for the -surrounding morphism ``m``. +of ``iff (P x) (Q x)`` and a constraint of the form ``Proper (pointwise_relation A iff ==> ?) m`` +will be generated for the surrounding morphism ``m``. Hence, one can add higher-order combinators as morphisms by providing signatures using pointwise extension for the relations on the @@ -685,11 +679,11 @@ default. The semantics of the previous :tacn:`setoid_rewrite` implementation can almost be recovered using the ``at 1`` modifier. -Sub-relations +Subrelations ~~~~~~~~~~~~~ -Sub-relations can be used to specify that one relation is included in -another, so that morphisms signatures for one can be used for the +Subrelations can be used to specify that one relation is included in +another, so that morphism signatures for one can be used for the other. If a signature mentions a relation ``R`` on the left of an arrow ``==>``, then the signature also applies for any relation ``S`` that is smaller than ``R``, and the inverse applies on the right of an arrow. One @@ -702,7 +696,7 @@ two morphisms for conjunction: ``Proper (impl ==> impl ==> impl) and`` and rewriting constraints arising from a rewrite using ``iff``, ``impl`` or ``inverse impl`` through ``and``. -Sub-relations are implemented in ``Classes.Morphisms`` and are a prime +Subrelations are implemented in ``Classes.Morphisms`` and are a prime example of a mostly user-space extension of the algorithm. diff --git a/doc/sphinx/addendum/implicit-coercions.rst b/doc/sphinx/addendum/implicit-coercions.rst index 09faa06765..f134022eb6 100644 --- a/doc/sphinx/addendum/implicit-coercions.rst +++ b/doc/sphinx/addendum/implicit-coercions.rst @@ -31,7 +31,7 @@ A class with `n` parameters is any defined name with a type :g:`forall (x₁:A₁)..(xₙ:Aₙ),s` where ``s`` is a sort. Thus a class with parameters is considered as a single class and not as a family of classes. An object of a class ``C`` is any term of type :g:`C t₁ .. tₙ`. -In addition to these user-classes, we have two abstract classes: +In addition to these user-defined classes, we have two built-in classes: * ``Sortclass``, the class of sorts; its objects are the terms whose type is a @@ -50,11 +50,11 @@ Formally, the syntax of a classes is defined as: Coercions --------- -A name ``f`` can be declared as a coercion between a source user-class +A name ``f`` can be declared as a coercion between a source user-defined class ``C`` with `n` parameters and a target class ``D`` if one of these conditions holds: - * ``D`` is a user-class, then the type of ``f`` must have the form + * ``D`` is a user-defined class, then the type of ``f`` must have the form :g:`forall (x₁:A₁)..(xₙ:Aₙ)(y:C x₁..xₙ), D u₁..uₘ` where `m` is the number of parameters of ``D``. * ``D`` is ``Funclass``, then the type of ``f`` must have the form @@ -65,8 +65,8 @@ conditions holds: We then write :g:`f : C >-> D`. The restriction on the type of coercions is called *the uniform inheritance condition*. -.. note:: The abstract class ``Sortclass`` can be used as a source class, but - the abstract class ``Funclass`` cannot. +.. note:: The built-in class ``Sortclass`` can be used as a source class, but + the built-in class ``Funclass`` cannot. To coerce an object :g:`t:C t₁..tₙ` of ``C`` towards ``D``, we have to apply the coercion ``f`` to it; the obtained term :g:`f t₁..tₙ t` is @@ -95,7 +95,7 @@ We can now declare ``f`` as coercion from ``C'`` to ``D``, since we can The identity coercions have a special status: to coerce an object :g:`t:C' t₁..tₖ` -of ``C'`` towards ``C``, we does not have to insert explicitly ``Id_C'_C`` +of ``C'`` towards ``C``, we do not have to insert explicitly ``Id_C'_C`` since :g:`Id_C'_C t₁..tₖ t` is convertible with ``t``. However we "rewrite" the type of ``t`` to become an object of ``C``; in this case, it becomes :g:`C uₙ'..uₖ'` where each ``uᵢ'`` is the result of the @@ -121,7 +121,7 @@ by the coercions ``f₁..fₖ``. The application of a coercion path to a term consists of the successive application of its coercions. -Declaration of Coercions +Declaring Coercions ------------------------- .. cmd:: Coercion @qualid : @class >-> @class @@ -140,8 +140,8 @@ Declaration of Coercions .. warn:: Ambiguous path. - When the coercion :token:`qualid` is added to the inheritance graph, non - valid coercion paths are ignored; they are signaled by a warning + When the coercion :token:`qualid` is added to the inheritance graph, + invalid coercion paths are ignored; they are signaled by a warning displaying these paths of the form :g:`[f₁;..;fₙ] : C >-> D`. .. cmdv:: Local Coercion @qualid : @class >-> @class @@ -215,7 +215,7 @@ declaration, this constructor is declared as a coercion. .. cmdv:: Local Identity Coercion @ident : @ident >-> @ident - Idem but locally to the current section. + Same as ``Identity Coercion`` but locally to the current section. .. cmdv:: SubClass @ident := @type :name: SubClass @@ -319,7 +319,7 @@ Coercions and Modules Since |Coq| version 8.3, the coercions present in a module are activated only when the module is explicitly imported. Formerly, the coercions - were activated as soon as the module was required, whatever it was + were activated as soon as the module was required, whether it was imported or not. This option makes it possible to recover the behavior of the versions of @@ -387,8 +387,8 @@ We give now an example using identity coercions. In the case of functional arguments, we use the monotonic rule of -sub-typing. Approximatively, to coerce :g:`t:forall x:A,B` towards -:g:`forall x:A',B'`, one have to coerce ``A'`` towards ``A`` and ``B`` +sub-typing. To coerce :g:`t : forall x : A, B` towards +:g:`forall x : A', B'`, we have to coerce ``A'`` towards ``A`` and ``B`` towards ``B'``. An example is given below: .. coqtop:: all @@ -424,8 +424,8 @@ replaced by ``x:A'`` where ``A'`` is the result of the application to ``Sortclass`` if it exists. This case occurs in the abstraction :g:`fun x:A => t`, universal quantification :g:`forall x:A,B`, global variables and parameters of (co-)inductive definitions and -functions. In :g:`forall x:A,B`, such a coercion path may be applied -to ``B`` also if necessary. +functions. In :g:`forall x:A,B`, such a coercion path may also be applied +to ``B`` if necessary. .. coqtop:: all diff --git a/doc/sphinx/addendum/miscellaneous-extensions.rst b/doc/sphinx/addendum/miscellaneous-extensions.rst index b6c35d8fa7..0f2d35d044 100644 --- a/doc/sphinx/addendum/miscellaneous-extensions.rst +++ b/doc/sphinx/addendum/miscellaneous-extensions.rst @@ -32,6 +32,7 @@ When the proof ends two constants are defined: ends with ``Qed``, and transparent if the proof ends with ``Defined``. .. example:: + .. coqtop:: all Require Coq.derive.Derive. diff --git a/doc/sphinx/addendum/nsatz.rst b/doc/sphinx/addendum/nsatz.rst index 387d614956..9adeca46fc 100644 --- a/doc/sphinx/addendum/nsatz.rst +++ b/doc/sphinx/addendum/nsatz.rst @@ -1,63 +1,55 @@ .. include:: ../preamble.rst -.. _nsatz: +.. _nsatz_chapter: Nsatz: tactics for proving equalities in integral domains =========================================================== :Author: Loïc Pottier -The tactic `nsatz` proves goals of the form +.. tacn:: nsatz + :name: nsatz -:math:`\begin{array}{l} -\forall X_1,\ldots,X_n \in A,\\ -P_1(X_1,\ldots,X_n) = Q_1(X_1,\ldots,X_n) , \ldots , P_s(X_1,\ldots,X_n) =Q_s(X_1,\ldots,X_n)\\ -\vdash P(X_1,\ldots,X_n) = Q(X_1,\ldots,X_n)\\ -\end{array}` + This tactic is for solving goals of the form -where :math:`P, Q, P₁,Q₁,\ldots,Pₛ, Qₛ` are polynomials and :math:`A` is an integral -domain, i.e. a commutative ring with no zero divisor. For example, :math:`A` -can be :math:`\mathbb{R}`, :math:`\mathbb{Z}`, or :math:`\mathbb{Q}`. -Note that the equality :math:`=` used in these goals can be -any setoid equality (see :ref:`tactics-enabled-on-user-provided-relations`) , not only Leibnitz equality. + :math:`\begin{array}{l} + \forall X_1, \ldots, X_n \in A, \\ + P_1(X_1, \ldots, X_n) = Q_1(X_1, \ldots, X_n), \ldots, P_s(X_1, \ldots, X_n) = Q_s(X_1, \ldots, X_n) \\ + \vdash P(X_1, \ldots, X_n) = Q(X_1, \ldots, X_n) \\ + \end{array}` -It also proves formulas + where :math:`P, Q, P_1, Q_1, \ldots, P_s, Q_s` are polynomials and :math:`A` is an integral + domain, i.e. a commutative ring with no zero divisors. For example, :math:`A` + can be :math:`\mathbb{R}`, :math:`\mathbb{Z}`, or :math:`\mathbb{Q}`. + Note that the equality :math:`=` used in these goals can be + any setoid equality (see :ref:`tactics-enabled-on-user-provided-relations`) , not only Leibniz equality. -:math:`\begin{array}{l} -\forall X_1,\ldots,X_n \in A,\\ -P_1(X_1,\ldots,X_n) = Q_1(X_1,\ldots,X_n) \wedge \ldots \wedge P_s(X_1,\ldots,X_n) =Q_s(X_1,\ldots,X_n)\\ -\rightarrow P(X_1,\ldots,X_n) = Q(X_1,\ldots,X_n)\\ -\end{array}` + It also proves formulas -doing automatic introductions. + :math:`\begin{array}{l} + \forall X_1, \ldots, X_n \in A, \\ + P_1(X_1, \ldots, X_n) = Q_1(X_1, \ldots, X_n) \wedge \ldots \wedge P_s(X_1, \ldots, X_n) = Q_s(X_1, \ldots, X_n) \\ + \rightarrow P(X_1, \ldots, X_n) = Q(X_1, \ldots, X_n) \\ + \end{array}` + doing automatic introductions. -Using the basic tactic `nsatz` ------------------------------- - - -Load the Nsatz module: - -.. coqtop:: all - - Require Import Nsatz. - -and use the tactic `nsatz`. + You can load the ``Nsatz`` module with the command ``Require Import Nsatz``. More about `nsatz` --------------------- Hilbert’s Nullstellensatz theorem shows how to reduce proofs of -equalities on polynomials on a commutative ring :math:`A` with no zero divisor +equalities on polynomials on a commutative ring :math:`A` with no zero divisors to algebraic computations: it is easy to see that if a polynomial :math:`P` in :math:`A[X_1,\ldots,X_n]` verifies :math:`c P^r = \sum_{i=1}^{s} S_i P_i`, with :math:`c \in A`, :math:`c \not = 0`, :math:`r` a positive integer, and the :math:`S_i` s in :math:`A[X_1,\ldots,X_n ]`, then :math:`P` is zero whenever polynomials :math:`P_1,\ldots,P_s` are zero -(the converse is also true when :math:`A` is an algebraic closed field: the method is +(the converse is also true when :math:`A` is an algebraically closed field: the method is complete). -So, proving our initial problem can reduce into finding :math:`S_1,\ldots,S_s`, +So, solving our initial problem reduces to finding :math:`S_1, \ldots, S_s`, :math:`c` and :math:`r` such that :math:`c (P-Q)^r = \sum_{i} S_i (P_i-Q_i)`, which will be proved by the tactic ring. @@ -68,34 +60,31 @@ Buchberger algorithm. This computation is done after a step of *reification*, which is performed using :ref:`typeclasses`. -The ``Nsatz`` module defines the tactic `nsatz`, which can be used without -arguments, or with the syntax: - -| nsatz with radicalmax:=num%N strategy:=num%Z parameters:= :n:`{* var}` variables:= :n:`{* var}` +.. tacv:: nsatz with radicalmax:=@num%N strategy:=@num%Z parameters:=[{*, @ident}] variables:=[{*, @ident}] -where: + Most complete syntax for `nsatz`. -* `radicalmax` is a bound when for searching r s.t. - :math:`c (P−Q) r = \sum_{i=1..s} S_i (P i − Q i)` + * `radicalmax` is a bound when searching for r such that + :math:`c (P−Q) r = \sum_{i=1..s} S_i (P i − Q i)` -* `strategy` gives the order on variables :math:`X_1,\ldots,X_n` and the strategy - used in Buchberger algorithm (see :cite:`sugar` for details): + * `strategy` gives the order on variables :math:`X_1,\ldots,X_n` and the strategy + used in Buchberger algorithm (see :cite:`sugar` for details): - * strategy = 0: reverse lexicographic order and newest s-polynomial. - * strategy = 1: reverse lexicographic order and sugar strategy. - * strategy = 2: pure lexicographic order and newest s-polynomial. - * strategy = 3: pure lexicographic order and sugar strategy. + * strategy = 0: reverse lexicographic order and newest s-polynomial. + * strategy = 1: reverse lexicographic order and sugar strategy. + * strategy = 2: pure lexicographic order and newest s-polynomial. + * strategy = 3: pure lexicographic order and sugar strategy. -* `parameters` is the list of variables :math:`X_{i_1},\ldots,X_{i_k}` among - :math:`X_1,\ldots,X_n` which are considered as parameters: computation will be performed with - rational fractions in these variables, i.e. polynomials are considered - with coefficients in :math:`R(X_{i_1},\ldots,X_{i_k})`. In this case, the coefficient - :math:`c` can be a non constant polynomial in :math:`X_{i_1},\ldots,X_{i_k}`, and the tactic - produces a goal which states that :math:`c` is not zero. + * `parameters` is the list of variables :math:`X_{i_1},\ldots,X_{i_k}` among + :math:`X_1,\ldots,X_n` which are considered as parameters: computation will be performed with + rational fractions in these variables, i.e. polynomials are considered + with coefficients in :math:`R(X_{i_1},\ldots,X_{i_k})`. In this case, the coefficient + :math:`c` can be a non constant polynomial in :math:`X_{i_1},\ldots,X_{i_k}`, and the tactic + produces a goal which states that :math:`c` is not zero. -* `variables` is the list of the variables in the decreasing order in - which they will be used in Buchberger algorithm. If `variables` = `(@nil R)`, - then `lvar` is replaced by all the variables which are not in - `parameters`. + * `variables` is the list of the variables in the decreasing order in + which they will be used in the Buchberger algorithm. If `variables` = `(@nil R)`, + then `lvar` is replaced by all the variables which are not in + `parameters`. -See file `Nsatz.v` for many examples, especially in geometry. +See the file `Nsatz.v` for many examples, especially in geometry. diff --git a/doc/sphinx/addendum/parallel-proof-processing.rst b/doc/sphinx/addendum/parallel-proof-processing.rst index edb8676a5b..8ee8f52227 100644 --- a/doc/sphinx/addendum/parallel-proof-processing.rst +++ b/doc/sphinx/addendum/parallel-proof-processing.rst @@ -68,7 +68,7 @@ to modify the proof script accordingly. Proof blocks and error resilience -------------------------------------- -|Coq| 8.6 introduced a mechanism for error resiliency: in interactive +|Coq| 8.6 introduced a mechanism for error resilience: in interactive mode |Coq| is able to completely check a document containing errors instead of bailing out at the first failure. @@ -92,14 +92,14 @@ Caveats ```````` When a vernacular command fails the subsequent error messages may be -bogus, i.e. caused by the first error. Error resiliency for vernacular +bogus, i.e. caused by the first error. Error resilience for vernacular commands can be switched off by passing ``-async-proofs-command-error-resilience off`` to |CoqIDE|. An incorrect proof block detection can result into an incorrect error recovery and hence in bogus errors. Proof block detection cannot be precise for bullets or any other non well parenthesized proof -structure. Error resiliency can be turned off or selectively activated +structure. Error resilience can be turned off or selectively activated for any set of block kind passing to |CoqIDE| one of the following options: @@ -127,13 +127,14 @@ the very same button, that can also be used to see the list of errors and jump to the corresponding line. If a proof is processed asynchronously the corresponding Qed command -is colored using a lighter color that usual. This signals that the +is colored using a lighter color than usual. This signals that the proof has been delegated to a worker process (or will be processed lazily if the ``-async-proofs lazy`` option is used). Once finished, the worker process will provide the proof object, but this will not be automatically checked by the kernel of the main process. To force the kernel to check all the proof objects, one has to click the button -with the gears. Only then are all the universe constraints checked. +with the gears (Fully check the document) on the top bar. +Only then all the universe constraints are checked. Caveats ``````` @@ -149,7 +150,7 @@ To disable this feature, one can pass the ``-async-proofs off`` flag to default, pass the ``-async-proofs on`` flag to enable it. Proofs that are known to take little time to process are not delegated -to a worker process. The threshold can be configure with +to a worker process. The threshold can be configured with ``-async-proofs-delegation-threshold``. Default is 0.03 seconds. Batch mode @@ -157,7 +158,7 @@ Batch mode When |Coq| is used as a batch compiler by running `coqc` or `coqtop` -compile, it produces a `.vo` file for each `.v` file. A `.vo` file contains, -among other things, theorems statements and proofs. Hence to produce a +among other things, theorem statements and proofs. Hence to produce a .vo |Coq| need to process all the proofs of the `.v` file. The asynchronous processing of proofs can decouple the generation of a @@ -225,5 +226,5 @@ in all the shells from which |Coq| processes will be started. If one uses just one terminal running the bash shell, then ``export ‘coqworkmgr -j 4‘`` will do the job. -After that, all |Coq| processes, e.g. `coqide` and `coqc`, will honor the +After that, all |Coq| processes, e.g. `coqide` and `coqc`, will respect the limit, globally. diff --git a/doc/sphinx/addendum/program.rst b/doc/sphinx/addendum/program.rst index b685e68e43..28fe68d78d 100644 --- a/doc/sphinx/addendum/program.rst +++ b/doc/sphinx/addendum/program.rst @@ -38,12 +38,12 @@ obligations which need to be resolved to create the final term. Elaborating programs --------------------- -The main difference from |Coq| is that an object in a type T : Set can -be considered as an object of type { x : T | P} for any wellformed P : -Prop. If we go from T to the subset of T verifying property P, we must -prove that the object under consideration verifies it. Russell will -generate an obligation for every such coercion. In the other -direction, Russell will automatically insert a projection. +The main difference from |Coq| is that an object in a type :g:`T : Set` can +be considered as an object of type :g:`{x : T | P}` for any well-formed +:g:`P : Prop`. If we go from :g:`T` to the subset of :g:`T` verifying property +:g:`P`, we must prove that the object under consideration verifies it. Russell +will generate an obligation for every such coercion. In the other direction, +Russell will automatically insert a projection. Another distinction is the treatment of pattern-matching. Apart from the following differences, it is equivalent to the standard match @@ -67,7 +67,7 @@ operation (see :ref:`extendedpatternmatching`). (match x as y return (x = y -> _) with | 0 => fun H : x = 0 -> t | S n => fun H : x = S n -> u - end) (eq_refl n). + end) (eq_refl x). This permits to get the proper equalities in the context of proof obligations inside clauses, without which reasoning is very limited. @@ -75,7 +75,7 @@ operation (see :ref:`extendedpatternmatching`). + Generation of inequalities. If a pattern intersects with a previous one, an inequality is added in the context of the second branch. See for example the definition of div2 below, where the second branch is - typed in a context where ∀ p, _ <> S (S p). + typed in a context where :g:`∀ p, _ <> S (S p)`. + Coercion. If the object being matched is coercible to an inductive type, the corresponding coercion will be automatically inserted. This also works with the previous mechanism. @@ -88,7 +88,7 @@ coercions. This controls the special treatment of pattern-matching generating equalities and inequalities when using |Program| (it is on by default). All - pattern-matchings and let-patterns are handled using the standard algorithm + pattern-matches and let-patterns are handled using the standard algorithm of |Coq| (see :ref:`extendedpatternmatching`) when this option is deactivated. @@ -108,9 +108,9 @@ typechecker will fall back directly to |Coq|’s usual typing of dependent pattern-matching if a return or in clause is specified. Likewise, the if construct is not treated specially by |Program| so boolean tests in the code are not automatically reflected in the obligations. One can -use the dec combinator to get the correct hypotheses as in: +use the :g:`dec` combinator to get the correct hypotheses as in: -.. coqtop:: none +.. coqtop:: in Require Import Program Arith. @@ -120,7 +120,7 @@ use the dec combinator to get the correct hypotheses as in: if dec (leb n 0) then 0 else S (pred n). -The let tupling construct :g:`let (x1, ..., xn) := t in b` does not +The :g:`let` tupling construct :g:`let (x1, ..., xn) := t in b` does not produce an equality, contrary to the let pattern construct :g:`let ’(x1, ..., xn) := t in b`. Also, :g:`term :>` explicitly asks the system to coerce term to its support type. It can be useful in notations, for @@ -200,7 +200,7 @@ The structural fixpoint operator behaves just like the one of |Coq| (see :cmd:`Fixpoint`), except it may also generate obligations. It works with mutually recursive definitions too. -.. coqtop:: reset none +.. coqtop:: reset in Require Import Program Arith. @@ -264,7 +264,7 @@ Program Lemma Definition` and use it as the goal afterwards. Otherwise the proof will be started with the elaborated version as a goal. The :g:`Program` prefix can similarly be used as a prefix for - :g:`Variable`, :g:`Hypothesis`, :g:`Axiom` etc... + :g:`Variable`, :g:`Hypothesis`, :g:`Axiom` etc. .. _solving_obligations: @@ -300,7 +300,7 @@ 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 @tactic} Tries to solve each obligation of ``ident`` using the given ``tactic`` or the default one. @@ -322,13 +322,13 @@ optional tactic is replaced by the default one if not specified. .. opt:: Transparent Obligations - Control whether all obligations should be declared as transparent + Controls whether all obligations should be declared as transparent (the default), or if the system should infer which obligations can be declared opaque. .. opt:: Hide Obligations - Control whether obligations appearing in the + Controls whether obligations appearing in the term should be hidden as implicit arguments of the special constantProgram.Tactics.obligation. diff --git a/doc/sphinx/addendum/ring.rst b/doc/sphinx/addendum/ring.rst index 6a9b343ba8..d5c33dc1d4 100644 --- a/doc/sphinx/addendum/ring.rst +++ b/doc/sphinx/addendum/ring.rst @@ -13,7 +13,7 @@ The ring and field tactic families :Author: Bruno Barras, Benjamin Grégoire, Assia Mahboubi, Laurent Théry [#f1]_ -This chapter presents the tactics dedicated to deal with ring and +This chapter presents the tactics dedicated to dealing with ring and field equations. What does this tactic do? @@ -36,7 +36,7 @@ is strictly less than the following monomial according to the lexicographic order. It is an easy theorem to show that every polynomial is equivalent (modulo the ring properties) to exactly one canonical sum. This canonical sum is called the normal form of the polynomial. In fact, the actual representation shares -monomials with same prefixes. So what does ring? It normalizes polynomials over +monomials with same prefixes. So what does the ``ring`` tactic do? It normalizes polynomials over any ring or semi-ring structure. The basic use of ``ring`` is to simplify ring expressions, so that the user does not have to deal manually with the theorems of associativity and commutativity. @@ -59,9 +59,8 @@ The variables map It is frequent to have an expression built with :math:`+` and :math:`\times`, but rarely on variables only. Let us associate a number to each subterm of a -ring expression in the Gallina language. For example in the ring |nat|, consider -the expression: - +ring expression in the Gallina language. For example, consider this expression +in the semiring ``nat``: :: @@ -104,7 +103,7 @@ Concrete usage in Coq .. tacn:: ring The ``ring`` tactic solves equations upon polynomial expressions of a ring -(or semi-ring) structure. It proceeds by normalizing both hand sides +(or semi-ring) structure. It proceeds by normalizing both sides of the equation (w.r.t. associativity, commutativity and distributivity, constant propagation, rewriting of monomials) and comparing syntactically the results. @@ -112,9 +111,9 @@ comparing syntactically the results. .. tacn:: ring_simplify ``ring_simplify`` applies the normalization procedure described above to -the terms given. The tactic then replaces all occurrences of the terms +the given terms. The tactic then replaces all occurrences of the terms given in the conclusion of the goal by their normal forms. If no term -is given, then the conclusion should be an equation and both hand +is given, then the conclusion should be an equation and both sides are normalized. The tactic can also be applied in a hypothesis. The tactic must be loaded by ``Require Import Ring``. The ring structures @@ -187,7 +186,7 @@ Error messages: .. exn:: Cannot find a declared ring structure for equality @term. - Same as above is the case of the ``ring`` tactic. + Same as above in the case of the ``ring`` tactic. Adding a ring structure @@ -198,8 +197,8 @@ carrier set, an equality, and ring operations: ``Ring_theory.ring_theory`` and ``Ring_theory.semi_ring_theory``) satisfies the ring axioms. Semi- rings (rings without + inverse) are also supported. The equality can be either Leibniz equality, or any relation declared as a setoid (see -:ref:`tactics-enabled-on-user-provided-relations`). The definition of ring and semi-rings (see module -``Ring_theory``) is: +:ref:`tactics-enabled-on-user-provided-relations`). +The definitions of ring and semiring (see module ``Ring_theory``) are: .. coqtop:: in @@ -305,7 +304,7 @@ The syntax for adding a new ring is .. cmd:: Add Ring @ident : @term {? ( @ring_mod {* , @ring_mod } )} -The :n:`@ident` is not relevant. It is just used for error messages. The +The :n:`@ident` is not relevant. It is used just for error messages. The :n:`@term` is a proof that the ring signature satisfies the (semi-)ring axioms. The optional list of modifiers is used to tailor the behavior of the tactic. The following list describes their syntax and effects: @@ -386,7 +385,7 @@ sign :n:`@term` div :n:`@term` allows ``ring`` and ``ring_simplify`` to use monomials with - coefficient other than 1 in the rewriting. The term :n:`@term` is a proof + coefficients other than 1 in the rewriting. The term :n:`@term` is a proof that a given division function satisfies the specification of an euclidean division function (:n:`@term` has to be a proof of ``Ring_theory.div_theory``). For example, this function is called when @@ -414,13 +413,13 @@ Error messages: How does it work? ---------------------- -The code of ring is a good example of tactic written using *reflection*. -What is reflection? Basically, it is writing |Coq| tactics in |Coq|, rather -than in |OCaml|. From the philosophical point of view, it is -using the ability of the Calculus of Constructions to speak and reason -about itself. For the ring tactic we used Coq as a programming -language and also as a proof environment to build a tactic and to -prove it correctness. +The code of ``ring`` is a good example of a tactic written using *reflection*. +What is reflection? Basically, using it means that a part of a tactic is written +in Gallina, Coq's language of terms, rather than |Ltac| or |OCaml|. From the +philosophical point of view, reflection is using the ability of the Calculus of +Constructions to speak and reason about itself. For the ``ring`` tactic we used +Coq as a programming language and also as a proof environment to build a tactic +and to prove its correctness. The interested reader is strongly advised to have a look at the file ``Ring_polynom.v``. Here a type for polynomials is defined: @@ -452,7 +451,7 @@ Polynomials in normal form are defined as: where ``Pinj n P`` denotes ``P`` in which :math:`V_i` is replaced by :math:`V_{i+n}` , and ``PX P n Q`` denotes :math:`P \otimes V_1^n \oplus Q'`, `Q'` being `Q` where :math:`V_i` is replaced by :math:`V_{i+1}`. -Variables maps are represented by list of ring elements, and two +Variable maps are represented by lists of ring elements, and two interpretation functions, one that maps a variables map and a polynomial to an element of the concrete ring, and the second one that does the same for normal forms: @@ -490,18 +489,18 @@ concrete expression `p’`, which is the concrete normal form of `p`. This is su `p’` |la| |le| ========= ====== ==== -The user do not see the right part of the diagram. From outside, the -tactic behaves like a |bdi| simplification extended with AC rewriting -rules. Basically, the proof is only the application of the main -correctness theorem to well-chosen arguments. +The user does not see the right part of the diagram. From outside, the +tactic behaves like a |bdi| simplification extended with rewriting rules +for associativity and commutativity. Basically, the proof is only the +application of the main correctness theorem to well-chosen arguments. Dealing with fields ------------------------ .. tacn:: field -The ``field`` tactic is an extension of the ``ring`` to deal with rational -expression. Given a rational expression :math:`F = 0`. It first reduces the +The ``field`` tactic is an extension of the ``ring`` tactic that deals with rational +expressions. Given a rational expression :math:`F = 0`. It first reduces the expression `F` to a common denominator :math:`N/D = 0` where `N` and `D` are two ring expressions. For example, if we take :math:`F = (1 − 1/x) x − x + 1`, this gives :math:`N = (x − 1) x − x^2 + x` and :math:`D = x`. It then calls ring to solve @@ -523,7 +522,7 @@ structures can be declared to the system with the ``Add Field`` command (in ``plugins/setoid_ring``). It is exported by module ``Rbase``, so that requiring ``Rbase`` or ``Reals`` is enough to use the field tactics on real numbers. Rational numbers in canonical form are also declared as -a field in module ``Qcanon``. +a field in the module ``Qcanon``. .. example:: @@ -559,8 +558,8 @@ a field in module ``Qcanon``. performs the simplification in the conclusion of the goal, :math:`F_1 = F_2` becomes :math:`N_1 / D_1 = N_2 / D_2`. A normalization step (the same as the one for rings) is then applied to :math:`N_1`, :math:`D_1`, - :math:`N_2` and :math:`D_2`. This way, polynomials remain in factorized form during the - fraction simplifications. This yields smaller expressions when + :math:`N_2` and :math:`D_2`. This way, polynomials remain in factorized form during + fraction simplification. This yields smaller expressions when reducing to the same denominator since common factors can be canceled. .. tacv:: field_simplify [{* @term }] @@ -657,7 +656,7 @@ The syntax for adding a new field is .. cmd:: Add Field @ident : @term {? ( @field_mod {* , @field_mod } )} -The :n:`@ident` is not relevant. It is just used for error +The :n:`@ident` is not relevant. It is used just for error messages. :n:`@term` is a proof that the field signature satisfies the (semi-)field axioms. The optional list of modifiers is used to tailor the behavior of the tactic. @@ -704,9 +703,8 @@ it using reflection (see :cite:`Bou97`). Later, it was rewritten by Patrick Loiseleur: the new tactic does not any more require ``ACDSimpl`` to compile and it makes use of |bdi|-reduction not only to replace the rewriting steps, but also to achieve the -interleaving of computation and reasoning (see :ref:`discussion_reflection`). He also wrote a -few |ML| code for the ``Add Ring`` command, that allow to register new rings -dynamically. +interleaving of computation and reasoning (see :ref:`discussion_reflection`). He also wrote +some |ML| code for the ``Add Ring`` command that allows registering new rings dynamically. Proofs terms generated by ring are quite small, they are linear in the number of :math:`\oplus` and :math:`\otimes` operations in the normalized terms. Type-checking @@ -733,15 +731,15 @@ Then it is rewritten to ``34 − x + 2 * x + 12``, very far from the expected re Here rewriting is not sufficient: you have to do some kind of reduction (some kind of computation) to achieve the normalization. -The tactic ``ring`` is not only faster than a classical one: using -reflection, we get for free integration of computation and reasoning -that would be very complex to implement in the classic fashion. +The tactic ``ring`` is not only faster than the old one: by using +reflection, we get for free the integration of computation and reasoning +that would be very difficult to implement without it. Is it the ultimate way to write tactics? The answer is: yes and no. -The ``ring`` tactic uses intensively the conversion rule of |Cic|, that is -replaces proof by computation the most as it is possible. It can be -useful in all situations where a classical tactic generates huge proof -terms. Symbolic Processing and Tautologies are in that case. But there +The ``ring`` tactic intensively uses the conversion rules of the Calculus of +Inductive Constructions, i.e. it replaces proofs by computations as much as possible. +It can be useful in all situations where a classical tactic generates huge proof +terms, like symbolic processing and tautologies. But there are also tactics like ``auto`` or ``linear`` that do many complex computations, using side-effects and backtracking, and generate a small proof term. Clearly, it would be significantly less efficient to replace them by @@ -750,12 +748,12 @@ tactics using reflection. Another idea suggested by Benjamin Werner: reflection could be used to couple an external tool (a rewriting program or a model checker) with |Coq|. We define (in |Coq|) a type of terms, a type of *traces*, and -prove a correction theorem that states that *replaying traces* is safe -w.r.t some interpretation. Then we let the external tool do every +prove a correctness theorem that states that *replaying traces* is safe +with respect to some interpretation. Then we let the external tool do every computation (using side-effects, backtracking, exception, or others features that are not available in pure lambda calculus) to produce -the trace: now we can check in |Coq| that the trace has the expected -semantic by applying the correction lemma. +the trace. Now we can check in |Coq| that the trace has the expected +semantics by applying the correctness theorem. diff --git a/doc/sphinx/addendum/universe-polymorphism.rst b/doc/sphinx/addendum/universe-polymorphism.rst index 6e7ccba63c..f245fab5ca 100644 --- a/doc/sphinx/addendum/universe-polymorphism.rst +++ b/doc/sphinx/addendum/universe-polymorphism.rst @@ -72,7 +72,7 @@ different. This can be seen when the :opt:`Printing Universes` option is on: Now :g:`pidentity` is used at two different levels: at the head of the application it is instantiated at ``Top.3`` while in the argument position it is instantiated at ``Top.4``. This definition is only valid as long as -``Top.4`` is strictly smaller than ``Top.3``, as show by the constraints. Note +``Top.4`` is strictly smaller than ``Top.3``, as shown by the constraints. Note that this definition is monomorphic (not universe polymorphic), so the two universes (in this case ``Top.3`` and ``Top.4``) are actually global levels. diff --git a/doc/sphinx/biblio.bib b/doc/sphinx/biblio.bib index 3574bf6750..9cfcd7ae64 100644 --- a/doc/sphinx/biblio.bib +++ b/doc/sphinx/biblio.bib @@ -1,7 +1,7 @@ @String{jfp = "Journal of Functional Programming"} @String{lncs = "Lecture Notes in Computer Science"} @String{lnai = "Lecture Notes in Artificial Intelligence"} -@String{SV = "{Sprin-ger-Verlag}"} +@String{SV = "{Springer-Verlag}"} @InCollection{Asp00, Title = {Proof General: A Generic Tool for Proof Development}, @@ -258,7 +258,7 @@ s}, @InProceedings{Luttik97specificationof, author = {Sebastiaan P. Luttik and Eelco Visser}, booktitle = {2nd International Workshop on the Theory and Practice of Algebraic Specifications (ASF+SDF'97), Electronic Workshops in Computing}, - publisher = {Springer-Verlag}, + publisher = SV, title = {Specification of Rewriting Strategies}, year = {1997} } diff --git a/doc/sphinx/language/cic.rst b/doc/sphinx/language/cic.rst index 98e81ebc65..6e0c1e1b61 100644 --- a/doc/sphinx/language/cic.rst +++ b/doc/sphinx/language/cic.rst @@ -723,6 +723,7 @@ each :math:`T` in :math:`(t:T)∈Γ_I` can be written as: :math:`∀Γ_P,∀Γ_{ the sort of the inductive type t (not to be confused with :math:`\Sort` which is the set of sorts). .. example:: + The declaration for parameterized lists is: .. math:: @@ -741,6 +742,7 @@ the sort of the inductive type t (not to be confused with :math:`\Sort` which is | cons : A -> list A -> list A. .. example:: + The declaration for a mutual inductive definition of tree and forest is: @@ -763,6 +765,7 @@ the sort of the inductive type t (not to be confused with :math:`\Sort` which is | consf : tree -> forest -> forest. .. example:: + The declaration for a mutual inductive definition of even and odd is: .. math:: @@ -811,6 +814,7 @@ contains an inductive declaration. E[Γ] ⊢ c : C .. example:: + Provided that our environment :math:`E` contains inductive definitions we showed before, these two inference rules above enable us to conclude that: @@ -919,6 +923,7 @@ condition* for a constant :math:`X` in the following cases: .. example:: + For instance, if one considers the following variant of a tree type branching over the natural numbers: @@ -985,6 +990,7 @@ the Type hierarchy. .. example:: + It is well known that the existential quantifier can be encoded as an inductive definition. The following declaration introduces the second- order existential quantifier :math:`∃ X.P(X)`. @@ -1102,6 +1108,7 @@ sorts at each instance of a pattern-matching (see Section :ref:`Destructors`). A an example, let us consider the following definition: .. example:: + .. coqtop:: in Inductive option (A:Type) : Type := @@ -1118,6 +1125,7 @@ if :g:`option` is applied to a type in :math:`\Prop`, then, the result is not se if set in :math:`\Prop`. .. example:: + .. coqtop:: all Check (fun A:Set => option A). @@ -1126,6 +1134,7 @@ if set in :math:`\Prop`. Here is another example. .. example:: + .. coqtop:: in Inductive prod (A B:Type) : Type := pair : A -> B -> prod A B. @@ -1136,6 +1145,7 @@ none in :math:`\Type`, and in :math:`\Type` otherwise. In all cases, the three k eliminations schemes are allowed. .. example:: + .. coqtop:: all Check (fun A:Set => prod A). @@ -1324,6 +1334,7 @@ the extraction mechanism. Assume :math:`A` and :math:`B` are two propositions, a logical disjunction :math:`A ∨ B` is defined inductively by: .. example:: + .. coqtop:: in Inductive or (A B:Prop) : Prop := @@ -1334,6 +1345,7 @@ The following definition which computes a boolean value by case over the proof of :g:`or A B` is not accepted: .. example:: + .. coqtop:: all Fail Definition choice (A B: Prop) (x:or A B) := @@ -1357,6 +1369,7 @@ property which are provably different, contradicting the proof- irrelevance property which is sometimes a useful axiom: .. example:: + .. coqtop:: all Axiom proof_irrelevance : forall (P : Prop) (x y : P), x=y. @@ -1390,6 +1403,7 @@ be used for rewriting not only in logical propositions but also in any type. .. example:: + .. coqtop:: all Print eq_rec. @@ -1421,6 +1435,7 @@ We write :math:`\{c\}^P` for :math:`\{c:C\}^P` with :math:`C` the type of :math: .. example:: + The following term in concrete syntax:: match t as l return P' with @@ -1485,6 +1500,7 @@ definition :math:`\ind{r}{Γ_I}{Γ_C}` with :math:`Γ_C = [c_1 :C_1 ;…;c_n :C_ .. example:: + Below is a typing rule for the term shown in the previous example: .. inference:: list example @@ -1634,6 +1650,7 @@ The following definitions are correct, we enter them using the :cmd:`Fixpoint` command and show the internal representation. .. example:: + .. coqtop:: all Fixpoint plus (n m:nat) {struct n} : nat := @@ -1810,6 +1827,7 @@ option ``-impredicative-set``. For example, using the ordinary `coqtop` command, the following is rejected, .. example:: + .. coqtop:: all Fail Definition id: Set := forall X:Set,X->X. diff --git a/doc/sphinx/language/coq-library.rst b/doc/sphinx/language/coq-library.rst index 52c56d2bd2..9de30e2190 100644 --- a/doc/sphinx/language/coq-library.rst +++ b/doc/sphinx/language/coq-library.rst @@ -848,6 +848,7 @@ Notation Interpretation Precedence Associativity .. example:: + .. coqtop:: all reset Require Import ZArith. @@ -887,6 +888,7 @@ Notation Interpretation =============== =================== .. example:: + .. coqtop:: all reset Require Import Reals. @@ -906,6 +908,7 @@ tactics (see Chapter :ref:`tactics`), there are also: Proves that two real integer constants are different. .. example:: + .. coqtop:: all reset Require Import DiscrR. @@ -919,6 +922,7 @@ tactics (see Chapter :ref:`tactics`), there are also: Allows unfolding the ``Rabs`` constant and splits corresponding conjunctions. .. example:: + .. coqtop:: all reset Require Import Reals. @@ -933,6 +937,7 @@ tactics (see Chapter :ref:`tactics`), there are also: corresponding to the condition on each operand of the product. .. example:: + .. coqtop:: all reset Require Import Reals. diff --git a/doc/sphinx/language/gallina-extensions.rst b/doc/sphinx/language/gallina-extensions.rst index 394b928ada..7dd0a6e383 100644 --- a/doc/sphinx/language/gallina-extensions.rst +++ b/doc/sphinx/language/gallina-extensions.rst @@ -70,7 +70,9 @@ generates a variant type definition with just one constructor: To build an object of type :n:`@ident`, one should provide the constructor :n:`@ident₀` with the appropriate number of terms filling the fields of the record. -.. example:: Let us define the rational :math:`1/2`: +.. example:: + + Let us define the rational :math:`1/2`: .. coqtop:: in @@ -1849,15 +1851,15 @@ are named as expected. .. example:: (continued) -.. coqtop:: all + .. coqtop:: all - Arguments p [s t] _ [u] _: rename. + Arguments p [s t] _ [u] _: rename. - Check (p r1 (u:=c)). + Check (p r1 (u:=c)). - Check (p (s:=a) (t:=b) r1 (u:=c) r2). + Check (p (s:=a) (t:=b) r1 (u:=c) r2). - Fail Arguments p [s t] _ [w] _ : assert. + Fail Arguments p [s t] _ [w] _ : assert. .. _displaying-implicit-args: diff --git a/doc/sphinx/language/gallina-specification-language.rst b/doc/sphinx/language/gallina-specification-language.rst index 8250b4b3d6..da5cd00d72 100644 --- a/doc/sphinx/language/gallina-specification-language.rst +++ b/doc/sphinx/language/gallina-specification-language.rst @@ -758,6 +758,7 @@ Simple inductive types the case of annotated inductive types — cf. next section). .. example:: + The set of natural numbers is defined as: .. coqtop:: all @@ -976,6 +977,7 @@ Mutually defined inductive types reason, the parameters must be strictly the same for each inductive types. .. example:: + The typical example of a mutual inductive data type is the one for trees and forests. We assume given two types :g:`A` and :g:`B` as variables. It can be declared the following way. @@ -1048,6 +1050,7 @@ of the type. For co-inductive types, the only elimination principle is case analysis. .. example:: + An example of a co-inductive type is the type of infinite sequences of natural numbers, usually called streams. @@ -1067,6 +1070,7 @@ Definition of co-inductive predicates and blocks of mutually co-inductive definitions are also allowed. .. example:: + An example of a co-inductive predicate is the extensional equality on streams: @@ -1129,6 +1133,7 @@ constructions. .. example:: + One can define the addition function as : .. coqtop:: all @@ -1201,6 +1206,7 @@ constructions. inductive types. .. example:: + The size of trees and forests can be defined the following way: .. coqtop:: all diff --git a/doc/sphinx/practical-tools/utilities.rst b/doc/sphinx/practical-tools/utilities.rst index e15bcb8e2c..59bc2d22aa 100644 --- a/doc/sphinx/practical-tools/utilities.rst +++ b/doc/sphinx/practical-tools/utilities.rst @@ -218,6 +218,7 @@ file timing data: On ``Mac OS``, this works best if you’ve installed ``gnu-time``. .. example:: + For example, the output of ``make TIMED=1`` may look like this: @@ -295,6 +296,7 @@ file timing data: files which take effectively no time to compile. .. example:: + For example, the output table from ``make print-pretty-timed-diff`` may look like this: @@ -318,6 +320,7 @@ line timing data: line-by-line timing information. .. example:: + For example, running ``make all TIMING=1`` may result in a file like this: :: @@ -345,6 +348,7 @@ line timing data: This target requires python to build the table. .. example:: + For example, running ``print-pretty-single-time-diff`` might give a table like this: :: diff --git a/doc/sphinx/proof-engine/detailed-tactic-examples.rst b/doc/sphinx/proof-engine/detailed-tactic-examples.rst index 78719c1ef1..225df8d54c 100644 --- a/doc/sphinx/proof-engine/detailed-tactic-examples.rst +++ b/doc/sphinx/proof-engine/detailed-tactic-examples.rst @@ -341,8 +341,7 @@ involves conditional rewritings and shows how to deal with them using the optional tactic of the ``Hint Rewrite`` command. -.. example:: - Ackermann function +.. example:: Ackermann function .. coqtop:: in reset @@ -370,8 +369,7 @@ the optional tactic of the ``Hint Rewrite`` command. autorewrite with base0 using try reflexivity. -.. example:: - MacCarthy function +.. example:: MacCarthy function .. coqtop:: in reset diff --git a/doc/sphinx/proof-engine/proof-handling.rst b/doc/sphinx/proof-engine/proof-handling.rst index 44376080c3..a9d0c16376 100644 --- a/doc/sphinx/proof-engine/proof-handling.rst +++ b/doc/sphinx/proof-engine/proof-handling.rst @@ -375,6 +375,7 @@ or focus the next one. The following example script illustrates all these features: .. example:: + .. coqtop:: all Goal (((True /\ True) /\ True) /\ True) /\ True. @@ -511,6 +512,7 @@ Requesting information :token:`ident` .. example:: + .. coqtop:: all Show Match nat. diff --git a/doc/sphinx/proof-engine/ssreflect-proof-language.rst b/doc/sphinx/proof-engine/ssreflect-proof-language.rst index 6fb73a030f..8a2fc3996a 100644 --- a/doc/sphinx/proof-engine/ssreflect-proof-language.rst +++ b/doc/sphinx/proof-engine/ssreflect-proof-language.rst @@ -4632,6 +4632,7 @@ bookkeeping steps. .. example:: + The following example use the ``~~`` prenex notation for boolean negation: diff --git a/doc/sphinx/proof-engine/tactics.rst b/doc/sphinx/proof-engine/tactics.rst index 9b4d724e02..fdb04bf9a0 100644 --- a/doc/sphinx/proof-engine/tactics.rst +++ b/doc/sphinx/proof-engine/tactics.rst @@ -207,6 +207,7 @@ Applying theorems useful to advanced users. .. example:: + .. coqtop:: reset all Inductive Option : Set := @@ -281,7 +282,7 @@ Applying theorems :g:`t`:sub:`n` in the goal. See :tacn:`pattern` to transform the goal so that it gets the form :g:`(fun x => Q) u`:sub:`1` :g:`...` :g:`u`:sub:`n`. - .. exn:: Unable to unify ... with ... . + .. exn:: Unable to unify @term with @term. The apply tactic failed to match the conclusion of :token:`term` and the current goal. You can help the apply tactic by transforming your goal with @@ -366,6 +367,7 @@ Applying theorems .. warn:: When @term contains more than one non dependent product the tactic lapply only takes into account the first product. .. example:: + Assume we have a transitive relation ``R`` on ``nat``: .. coqtop:: reset in @@ -837,6 +839,7 @@ quantified variables or hypotheses until the goal is not any more a quantification or an implication. .. example:: + .. coqtop:: all Goal forall A B C:Prop, A \/ B /\ C -> (A -> C) -> C. @@ -958,6 +961,7 @@ quantification or an implication. .. exn:: Cannot move @ident after @ident : it depends on @ident. .. example:: + .. coqtop:: all Goal forall x :nat, x = 0 -> forall z y:nat, y=y-> 0=x. @@ -1082,6 +1086,7 @@ The name of the hypothesis in the proof-term, however, is left unchanged. obtain atomic ones. .. example:: + .. coqtop:: all Goal forall A B C:Prop, A /\ B /\ C \/ B /\ C \/ C /\ A -> C. @@ -1252,6 +1257,7 @@ Controlling the proof flow respect to some term. .. example:: + .. coqtop:: reset none Goal forall x y:nat, 0 <= x + y + y. @@ -1567,6 +1573,7 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) performs induction using this subterm. .. example:: + .. coqtop:: reset all Lemma induction_test : forall n:nat, n = n -> n <= n. @@ -1636,6 +1643,7 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) those are generalized as well in the statement to prove. .. example:: + .. coqtop:: reset all Lemma comm x y : x + y = y + x. @@ -1744,6 +1752,7 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) still get enough information in the proofs. .. example:: + .. coqtop:: reset all Lemma le_minus : forall n:nat, n < 1 -> n = 0. @@ -1809,6 +1818,7 @@ and an explanation of the underlying technique. Note that this tactic is only available after a ``Require Import FunInd``. .. example:: + .. coqtop:: reset all Require Import FunInd. @@ -2856,6 +2866,7 @@ the conversion in hypotheses :n:`{+ @ident}`. + A constant can be marked to be never unfolded by ``cbn`` or ``simpl``: .. example:: + .. coqtop:: all Arguments minus n m : simpl never. @@ -2868,6 +2879,7 @@ the conversion in hypotheses :n:`{+ @ident}`. ``/`` symbol in the argument list of the :cmd:`Arguments` vernacular command. .. example:: + .. coqtop:: all Definition fcomp A B C f (g : A -> B) (x : A) : C := f (g x). @@ -2880,6 +2892,7 @@ the conversion in hypotheses :n:`{+ @ident}`. always unfolded. .. example:: + .. coqtop:: all Definition volatile := fun x : nat => x. @@ -2890,6 +2903,7 @@ the conversion in hypotheses :n:`{+ @ident}`. such arguments. .. example:: + .. coqtop:: all Arguments minus !n !m. @@ -3180,6 +3194,7 @@ where :tacn:`auto` uses simple :tacn:`apply`). As a consequence, :tacn:`eauto` can solve such a goal: .. example:: + .. coqtop:: all Hint Resolve ex_intro. @@ -3748,6 +3763,7 @@ The following goal can be proved by :tacn:`tauto` whereas :tacn:`auto` would fail: .. example:: + .. coqtop:: reset all Goal forall (x:nat) (P:nat -> Prop), x = 0 \/ P x -> x <> 0 -> P x. @@ -3904,6 +3920,7 @@ equality must contain all the quantified variables in order for congruence to match against it. .. example:: + .. coqtop:: reset all Theorem T (A:Type) (f:A -> A) (g: A -> A -> A) a b: a=(f a) -> (g b (f a))=(f (f a)) -> (g a b)=(f (g b a)) -> (g a b)=a. @@ -3935,7 +3952,7 @@ match against it. discriminable equality but this proof could not be built in Coq because of dependently-typed functions. -.. exn:: Goal is solvable by congruence but some arguments are missing. Try congruence with ..., replacing metavariables by arbitrary terms. +.. exn:: Goal is solvable by congruence but some arguments are missing. Try congruence with {+ @term}, replacing metavariables by arbitrary terms. The decision procedure could solve the goal with the provision that additional arguments are supplied for some partially applied constructors. Any term of an @@ -3979,7 +3996,7 @@ succeeds, and results in an error otherwise. This tactic checks whether its arguments are unifiable, potentially instantiating existential variables. -.. exn:: Not unifiable. +.. exn:: Unable to unify @term with @term. .. tacv:: unify @term @term with @ident @@ -4315,6 +4332,7 @@ declare new field structures. All declared field structures can be printed with the Print Fields command. .. example:: + .. coqtop:: reset all Require Import Reals. @@ -4426,6 +4444,7 @@ Simple tactic macros A simple example has more value than a long explanation: .. example:: + .. coqtop:: reset all Ltac Solve := simpl; intros; auto. diff --git a/doc/sphinx/user-extensions/syntax-extensions.rst b/doc/sphinx/user-extensions/syntax-extensions.rst index dcefa293b1..37394386e6 100644 --- a/doc/sphinx/user-extensions/syntax-extensions.rst +++ b/doc/sphinx/user-extensions/syntax-extensions.rst @@ -146,7 +146,7 @@ expected to be inferred at typing time. Notation "x = y" := (@eq _ x y) (at level 70, no associativity). One can define *closed* notations whose both sides are symbols. In this case, -the default precedence level for the inner subexpression is 200, and the default +the default precedence level for the inner sub-expression is 200, and the default level for the notation itself is 0. .. coqtop:: in @@ -185,7 +185,7 @@ rules. Some simple left factorization work has to be done. Here is an example. Notation "x < y" := (lt x y) (at level 70). Notation "x < y < z" := (x < y /\ y < z) (at level 70). -In order to factorize the left part of the rules, the subexpression +In order to factorize the left part of the rules, the sub-expression referred by ``y`` has to be at the same level in both rules. However the default behavior puts ``y`` at the next level below 70 in the first rule (``no associativity`` is the default), and at the level 200 in the second @@ -209,7 +209,7 @@ of Coq predefined notations can be found in the chapter on :ref:`thecoqlibrary`. .. cmd:: Print Grammar pattern. This displays the state of the subparser of patterns (the parser used in the - grammar of the match with constructions). + grammar of the ``match with`` constructions). Displaying symbolic notations @@ -519,7 +519,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`` modifiers, the default is to consider subexpressions occurring +``as pattern`` modifiers, the default is to consider sub-expressions occurring in binding position and parsed as terms to be ``as ident``. .. _NotationsWithBinders: @@ -650,7 +650,7 @@ example of recursive notation with closed binders: A recursive pattern for binders can be used in position of a recursive pattern for terms. Here is an example: -.. coqtop:: in +.. coqtop:: in Notation "'FUNAPP' x .. y , f" := (fun x => .. (fun y => (.. (f x) ..) y ) ..) @@ -691,6 +691,117 @@ side. E.g.: Notation "'apply_id' f a1 .. an" := (.. (f a1) .. an) (at level 10, f ident, a1, an at level 9). +Custom entries +~~~~~~~~~~~~~~ + +.. cmd:: Declare Custom Entry @ident + + This command allows to define new grammar entries, called *custom + entries*, that can later be referred to using the entry name + :n:`custom @ident`. For instance, we may want to define an ad hoc + parser for arithmetical operations and proceed as follows: + +.. coqtop:: all + + Inductive Expr := + | One : Expr + | Mul : Expr -> Expr -> Expr + | Add : Expr -> Expr -> Expr. + + Declare Custom Entry expr. + Notation "[ e ]" := e (e custom expr at level 2). + Notation "1" := One (in custom expr at level 0). + Notation "x y" := (Mul x y) (in custom expr at level 1, left associativity). + Notation "x + y" := (Add x y) (in custom expr at level 2, left associativity). + Notation "( x )" := x (in custom expr, x at level 2). + Notation "{ x }" := x (in custom expr, x constr). + Notation "x" := x (in custom expr at level 0, x ident). + + Axiom f : nat -> Expr. + Check fun x y z => [1 + y z + {f x}]. + Unset Printing Notations. + Check fun x y z => [1 + y z + {f x}]. + Set Printing Notations. + Check fun e => match e with + | [1 + 1] => [1] + | [x y + z] => [x + y z] + | y => [y + e] + end. + +Custom entries have levels, like the main grammar of terms and grammar +of patterns have. The lower level is 0 and this is the level used by +default to put rules delimited with tokens on both ends. The level is +left to be inferred by Coq when using :n:`in custom @ident``. The +level is otherwise given explicitly by using the syntax :n:`in custom +@ident at level @num`, where :n:`@num` refers to the level. + +Levels are cumulative: a notation at level ``n`` of which the left end +is a term shall use rules at level less than ``n`` to parse this +sub-term. More precisely, it shall use rules at level strictly less +than ``n`` if the rule is declared with ``right associativity`` and +rules at level less or equal than ``n`` if the rule is declared with +``left associativity``. Similarly, a notation at level ``n`` of which +the right end is a term shall use by default rules at level strictly +less than ``n`` to parse this sub-term if the rule is declared left +associative and rules at level less or equal than ``n`` if the rule is +declared right associative. This is what happens for instance in the +rule ``Notation "x + y" := (Add x y) (in custom expr at level 2, left +associativity)`` where ``x`` is any expression parsed in entry +``expr`` at level less or equal than ``2`` (including, recursively, +the given rule) and ``y`` is any expression parsed in entry ``expr`` +at level strictly less than ``2``. + +Rules associated to an entry can refer different sub-entries. The +grammar entry name ``constr`` can be used to refer to the main grammar +of term as in the rule ``Notation "{ x }" := x (in custom expr at +level 0, x constr)`` which indicates that the subterm ``x`` should be +parsed using the main grammar. If not indicated, the level is computed +as for notations in ``constr``, e.g. using 200 as default level for +inner sub-expressions. The level can otherwise be indicated explicitly +by using ``constr at level n`` for some ``n``, or ``constr at next +level``. + +Conversely, custom entries can be used to parse sub-expressions of the +main grammar, or from another custom entry as is the case in +:g:`Notation "[ e ]" := e (e custom expr at level 2)` to indicate that +``e`` has to be parsed at level ``2`` of the grammar associated to the +custom entry ``expr``. The level can be omitted, as in :g:`Notation "[ e +]" := e (e custom expr)`, in which case Coq tries to infer it. + +In the absence of an explicit entry for parsing or printing a +sub-expression of a notation in a custom entry, the default is to +consider that this sub-expression is parsed or printed in the same +custom entry where the notation is defined. In particular, if ``x at +level n`` is used for a sub-expression of a notation defined in custom +entry ``foo``, it shall be understood the same as ``x custom foo at +level n``. + +In general, rules are required to be *productive* on the right-hand +side, i.e. that they are bound to an expression which is not +reduced to a single variable. If the rule is not productive on the +right-hand side, as it is the case above for :g:`Notation "( x )" := x +(in custom expr at level 0, x at level 2)` and :g:`Notation "{ x }" := +x (in custom expr at level 0, x constr)`, it is used as a *grammar +coercion* which means that it is used to parse or print an expression +which is not available in the current grammar at the current level of +parsing or printing for this grammar but which is available in another +grammar or in another level of the current grammar. For instance, +:g:`Notation "( x )" := x (in custom expr at level 0, x at level 2)` +tells that parentheses can be inserted to parse or print an expression +declared at level ``2`` of ``expr`` whenever this expression is +expected to be used as a subterm at level 0 or 1. This allows for +instance to parse and print :g:`Add x y` as a subterm of :g:`Mul (Add +x y) z` using the syntax ``(x + y) z``. Similarly, :g:`Notation "{ x }" +:= x (in custom expr at level 0, x constr)` gives a way to let any +arbitrary expression which is not in 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 Grammar @ident. + + This displays the state of the grammar for terms and grammar for + patterns associated to the custom entry :token:`ident`. + Summary ~~~~~~~ @@ -699,8 +810,8 @@ Summary Syntax of notations +++++++++++++++++++ -The different syntactic variants of the command Notation are given on the -following figure. The optional :production:`scope` is described in +The different syntactic forms taken by the commands declaring +notations are given below. The optional :production:`scope` is described in :ref:`Scopes`. .. productionlist:: coq @@ -711,22 +822,32 @@ following figure. The optional :production:`scope` is described in : | CoInductive `ind_body` [`decl_notation`] with … with `ind_body` [`decl_notation`]. : | Fixpoint `fix_body` [`decl_notation`] with … with `fix_body` [`decl_notation`]. : | CoFixpoint `cofix_body` [`decl_notation`] with … with `cofix_body` [`decl_notation`]. + : | [Local] Declare Custom Entry `ident`. decl_notation : [where `string` := `term` [: `scope`] and … and `string` := `term` [: `scope`]]. - modifiers : at level `natural` - : | `ident` , … , `ident` at level `natural` [`binderinterp`] + modifiers : 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` ident - : | `ident` global - : | `ident` bigint - : | `ident` [strict] pattern [at level `natural`] - : | `ident` binder - : | `ident` closed binder + : | `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 @@ -734,10 +855,11 @@ following figure. The optional :production:`scope` is described in .. 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. -.. note:: Many examples of Notation may be found in the files composing +.. note:: Some examples of Notation may be found in the files composing the initial state of Coq (see directory :file:`$COQLIB/theories/Init`). -.. note:: The notation ``"{ x }"`` has a special status in such a way that +.. note:: The notation ``"{ x }"`` has a special status in the main grammars of + terms and patterns so that complex notations of the form ``"x + { y }"`` or ``"x * { y }"`` can be nested with correct precedences. Especially, every notation involving a pattern of the form ``"{ x }"`` is parsed as a notation where the @@ -754,13 +876,18 @@ following figure. The optional :production:`scope` is described in Persistence of notations ++++++++++++++++++++++++ -Notations do not survive the end of sections. +Neither notations nor custom entries survive the end of sections. .. cmd:: Local Notation @notation Notations survive modules unless the command ``Local Notation`` is used instead of :cmd:`Notation`. +.. cmd:: Local Declare Custom Entry @ident + + Custom entries survive modules unless the command ``Local Declare + Custom Entry`` is used instead of :cmd:`Declare Custom Entry`. + .. _Scopes: Interpretation scopes @@ -1010,7 +1137,7 @@ The ``function_scope`` interpretation scope .. index:: function_scope -The scope ``function_scope`` also has a special status. +The scope ``function_scope`` also has a special status. It is temporarily activated each time the argument of a global reference is recognized to be a ``Funclass`` istance, i.e., of type :g:`forall x:A, B` or :g:`A -> B`. @@ -1025,11 +1152,11 @@ Scopes` or :cmd:`Print Scope`. ``type_scope`` This scope includes infix * for product types and infix + for sum types. It - is delimited by key ``type``, and bound to the coercion class + is delimited by key ``type``, and bound to the coercion class ``Sortclass``, as described above. ``function_scope`` - This scope is delimited by key ``function``, and bound to the coercion class + This scope is delimited by key ``function``, and bound to the coercion class ``Funclass``, as described above. ``nat_scope`` @@ -1207,7 +1334,7 @@ tactic language. Tactic notations obey the following syntax: .. productionlist:: coq tacn : Tactic Notation [`tactic_level`] [`prod_item` … `prod_item`] := `tactic`. prod_item : `string` | `tactic_argument_type`(`ident`) - tactic_level : (at level `natural`) + 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 @@ -1328,7 +1455,9 @@ tactic language. Tactic notations obey the following syntax: .. [#and_or_levels] which are the levels effectively chosen in the current implementation of Coq -.. [#no_associativity] Coq accepts notations declared as ``no associative`` but the parser on - which Coq is built, namely Camlp4, currently does not implement the - ``no associativity`` and replaces it by a ``left associativity``; hence it is - the same for Coq: ``no associativity`` is in fact ``left associativity``. +.. [#no_associativity] Coq accepts notations declared as ``no + associativity`` but the parser on which Coq is built, namely + Camlp5, currently does not implement ``no associativity`` and + replaces it with ``left associativity``; hence it is the same for + Coq: ``no associativity`` is in fact ``left associativity``, for + the purposes of parsing |