diff options
Diffstat (limited to 'doc')
26 files changed, 768 insertions, 2619 deletions
diff --git a/doc/refman/AddRefMan-pre.tex b/doc/refman/AddRefMan-pre.tex deleted file mode 100644 index 856a823de0..0000000000 --- a/doc/refman/AddRefMan-pre.tex +++ /dev/null @@ -1,63 +0,0 @@ -%\coverpage{Addendum to the Reference Manual}{\ } -%\addcontentsline{toc}{part}{Additional documentation} -%BEGIN LATEX -\setheaders{Presentation of the Addendum} -%END LATEX -\chapter*{Presentation of the Addendum} -%HEVEA\cutname{addendum.html} - -Here you will find several pieces of additional documentation for the -\Coq\ Reference Manual. Each of this chapters is concentrated on a -particular topic, that should interest only a fraction of the \Coq\ -users: that's the reason why they are apart from the Reference -Manual. - -\begin{description} - -\item[Extended pattern-matching] This chapter details the use of - generalized pattern-matching. It is contributed by Cristina Cornes - and Hugo Herbelin. - -\item[Implicit coercions] This chapter details the use of the coercion - mechanism. It is contributed by Amokrane Saïbi. - -%\item[Proof of imperative programs] This chapter explains how to -% prove properties of annotated programs with imperative features. -% It is contributed by Jean-Christophe Filliâtre - -\item[Program extraction] This chapter explains how to extract in practice ML - files from $\FW$ terms. It is contributed by Jean-Christophe - Filliâtre and Pierre Letouzey. - -\item[Program] This chapter explains the use of the \texttt{Program} - vernacular which allows the development of certified - programs in \Coq. It is contributed by Matthieu Sozeau and replaces - the previous \texttt{Program} tactic by Catherine Parent. - -%\item[Natural] This chapter is due to Yann Coscoy. It is the user -% manual of the tools he wrote for printing proofs in natural -% language. At this time, French and English languages are supported. - -\item[omega] \texttt{omega}, written by Pierre Crégut, solves a whole - class of arithmetic problems. - -\item[The {\tt ring} tactic] This is a tactic to do AC rewriting. This - chapter explains how to use it and how it works. - The chapter is contributed by Patrick Loiseleur. - -\item[The {\tt Setoid\_replace} tactic] This is a - tactic to do rewriting on types equipped with specific (only partially - substitutive) equality. The chapter is contributed by Clément Renard. - -\item[Calling external provers] This chapter describes several tactics - which call external provers. - -\end{description} - -\atableofcontents - - -%%% Local Variables: -%%% mode: latex -%%% TeX-master: "Reference-Manual" -%%% End: diff --git a/doc/refman/Reference-Manual.tex b/doc/refman/Reference-Manual.tex deleted file mode 100644 index ba4018d770..0000000000 --- a/doc/refman/Reference-Manual.tex +++ /dev/null @@ -1,134 +0,0 @@ -%\RequirePackage{ifpdf} -%\ifpdf -% \documentclass[11pt,a4paper,pdftex]{book} -%\else - \documentclass[11pt,a4paper]{book} -%\fi - -\usepackage[utf8]{inputenc} -\usepackage[T1]{fontenc} -\usepackage{textcomp} -\usepackage{times} -\usepackage{url} -\usepackage{verbatim} -\usepackage{amsmath} -\usepackage{amssymb} -\usepackage{alltt} -\usepackage{hevea} -\usepackage{ifpdf} -\usepackage[headings]{fullpage} -\usepackage{headers} % in this directory -\usepackage{multicol} -\usepackage{xspace} -\usepackage{pmboxdraw} -\usepackage{float} -\usepackage{color} - \definecolor{dkblue}{rgb}{0,0.1,0.5} - \definecolor{lightblue}{rgb}{0,0.5,0.5} - \definecolor{dkgreen}{rgb}{0,0.4,0} - \definecolor{dk2green}{rgb}{0.4,0,0} - \definecolor{dkviolet}{rgb}{0.6,0,0.8} - \definecolor{dkpink}{rgb}{0.2,0,0.6} -\usepackage{listings} - \def\lstlanguagefiles{coq-listing.tex} -\usepackage{tabularx} -\usepackage{array,longtable} - -\floatstyle{boxed} -\restylefloat{figure} - -% for coqide -\ifpdf % si on est pas en pdflatex - \usepackage[pdftex]{graphicx} -\else - \usepackage[dvips]{graphicx} -\fi - - -%\includeonly{Setoid} - -\input{../common/version.tex} -\input{../common/macros.tex}% extension .tex pour htmlgen -\input{../common/title.tex}% extension .tex pour htmlgen -%\input{headers} - -\usepackage[linktocpage,colorlinks,bookmarks=true,bookmarksnumbered=true]{hyperref} -% The manual advises to load hyperref package last to be able to redefine -% necessary commands. -% The above should work for both latex and pdflatex. Even if PDF is produced -% through DVI and PS using dvips and ps2pdf, hyperlinks should still work. -% linktocpage option makes page numbers, not section names, to be links in -% the table of contents. -% colorlinks option colors the links instead of using boxes. - -% The command \tocnumber was added to HEVEA in version 1.06-6. -% It instructs HEVEA to put chapter numbers into the table of -% content entries. The table of content is produced by HACHA using -% the options -tocbis -o toc.html. HEVEA produces a warning when -% a command is not recognized, so versions earlier than 1.06-6 can -% still be used. -%HEVEA\tocnumber - -\begin{document} -%BEGIN LATEX -\sloppy\hbadness=5000 -%END LATEX - -%BEGIN LATEX -\coverpage{Reference Manual} -{The Coq Development Team} -{This material may be distributed only subject to the terms and -conditions set forth in the Open Publication License, v1.0 or later -(the latest version is presently available at -\url{http://www.opencontent.org/openpub}). -Options A and B of the licence are {\em not} elected.} -%END LATEX - -%\defaultheaders - -%BEGIN LATEX -\tableofcontents -%END LATEX - -\part{The language} -%BEGIN LATEX -\defaultheaders -%END LATEX - - -\part{The proof engine} -\include{RefMan-ltac.v}% Writing tactics - -\lstset{language=SSR} -\lstset{moredelim=[is][]{|*}{*|}} -\lstset{moredelim=*[is][\itshape\rmfamily]{/*}{*/}} - -%BEGIN LATEX -\RefManCutCommand{BEGINADDENDUM=\thepage} -%END LATEX -\part{Addendum to the Reference Manual} -\include{AddRefMan-pre}% -%BEGIN LATEX -\RefManCutCommand{ENDADDENDUM=\thepage} -%END LATEX -\nocite{*} -\bibliographystyle{plain} -\bibliography{biblio} -\cutname{biblio.html} - -\printrefmanindex{default}{Global Index}{general-index.html} -\printrefmanindex{tactic}{Tactics Index}{tactic-index.html} -\printrefmanindex{command}{Vernacular Commands Index}{command-index.html} -\printrefmanindex{option}{Vernacular Options Index}{option-index.html} -\printrefmanindex{error}{Index of Error Messages}{error-index.html} - -%BEGIN LATEX -\cleardoublepage -\phantomsection -\addcontentsline{toc}{chapter}{\listfigurename} -\listoffigures -%END LATEX - -\end{document} - - diff --git a/doc/refman/biblio.bib b/doc/refman/biblio.bib deleted file mode 100644 index e69725838e..0000000000 --- a/doc/refman/biblio.bib +++ /dev/null @@ -1,1397 +0,0 @@ -@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}"} - -@InProceedings{Aud91, - author = {Ph. Audebaud}, - booktitle = {Proceedings of the sixth Conf. on Logic in Computer Science.}, - publisher = {IEEE}, - title = {Partial {Objects} in the {Calculus of Constructions}}, - year = {1991} -} - -@PhDThesis{Aud92, - author = {Ph. Audebaud}, - school = {{Universit\'e} Bordeaux I}, - title = {Extension du Calcul des Constructions par Points fixes}, - year = {1992} -} - -@InProceedings{Audebaud92b, - author = {Ph. Audebaud}, - booktitle = {{Proceedings of the 1992 Workshop on Types for Proofs and Programs}}, - editor = {{B. Nordstr\"om and K. Petersson and G. Plotkin}}, - note = {Also Research Report LIP-ENS-Lyon}, - pages = {21--34}, - title = {{CC+ : an extension of the Calculus of Constructions with fixpoints}}, - year = {1992} -} - -@InProceedings{Augustsson85, - author = {L. Augustsson}, - title = {{Compiling Pattern Matching}}, - booktitle = {Conference Functional Programming and -Computer Architecture}, - year = {1985} -} - -@Article{BaCo85, - author = {J.L. Bates and R.L. Constable}, - journal = {ACM transactions on Programming Languages and Systems}, - title = {Proofs as {Programs}}, - volume = {7}, - year = {1985} -} - -@Book{Bar81, - author = {H.P. Barendregt}, - publisher = {North-Holland}, - title = {The Lambda Calculus its Syntax and Semantics}, - year = {1981} -} - -@TechReport{Bar91, - author = {H. Barendregt}, - institution = {Catholic University Nijmegen}, - note = {In Handbook of Logic in Computer Science, Vol II}, - number = {91-19}, - title = {Lambda {Calculi with Types}}, - year = {1991} -} - -@Article{BeKe92, - author = {G. Bellin and J. Ketonen}, - journal = {Theoretical Computer Science}, - pages = {115--142}, - title = {A decision procedure revisited : Notes on direct logic, linear logic and its implementation}, - volume = {95}, - year = {1992} -} - -@Book{Bee85, - author = {M.J. Beeson}, - publisher = SV, - title = {Foundations of Constructive Mathematics, Metamathematical Studies}, - year = {1985} -} - -@Book{Bis67, - author = {E. Bishop}, - publisher = {McGraw-Hill}, - title = {Foundations of Constructive Analysis}, - year = {1967} -} - -@Book{BoMo79, - author = {R.S. Boyer and J.S. Moore}, - key = {BoMo79}, - publisher = {Academic Press}, - series = {ACM Monograph}, - title = {A computational logic}, - year = {1979} -} - -@MastersThesis{Bou92, - author = {S. Boutin}, - month = sep, - school = {{Universit\'e Paris 7}}, - title = {Certification d'un compilateur {ML en Coq}}, - year = {1992} -} - -@InProceedings{Bou97, - title = {Using reflection to build efficient and certified decision procedure -s}, - author = {S. Boutin}, - booktitle = {TACS'97}, - editor = {Martin Abadi and Takahashi Ito}, - publisher = SV, - series = lncs, - volume = 1281, - year = {1997} -} - -@PhDThesis{Bou97These, - author = {S. Boutin}, - title = {R\'eflexions sur les quotients}, - school = {Paris 7}, - year = 1997, - type = {th\`ese d'Universit\'e}, - month = apr -} - -@Article{Bru72, - author = {N.J. de Bruijn}, - journal = {Indag. Math.}, - title = {{Lambda-Calculus Notation with Nameless Dummies, a Tool for Automatic Formula Manipulation, with Application to the Church-Rosser Theorem}}, - volume = {34}, - year = {1972} -} - - -@InCollection{Bru80, - author = {N.J. de Bruijn}, - booktitle = {to H.B. Curry : Essays on Combinatory Logic, Lambda Calculus and Formalism.}, - editor = {J.P. Seldin and J.R. Hindley}, - publisher = {Academic Press}, - title = {A survey of the project {Automath}}, - year = {1980} -} - -@TechReport{COQ93, - author = {G. Dowek and A. Felty and H. Herbelin and G. Huet and C. Murthy and C. Parent and C. Paulin-Mohring and B. Werner}, - institution = {INRIA}, - month = may, - number = {154}, - title = {{The Coq Proof Assistant User's Guide Version 5.8}}, - year = {1993} -} - -@TechReport{COQ02, - author = {The Coq Development Team}, - institution = {INRIA}, - month = Feb, - number = {255}, - title = {{The Coq Proof Assistant Reference Manual Version 7.2}}, - year = {2002} -} - -@TechReport{CPar93, - author = {C. Parent}, - institution = {Ecole {Normale} {Sup\'erieure} de {Lyon}}, - month = oct, - note = {Also in~\cite{Nijmegen93}}, - number = {93-29}, - title = {Developing certified programs in the system {Coq}- {The} {Program} tactic}, - year = {1993} -} - -@PhDThesis{CPar95, - author = {C. Parent}, - school = {Ecole {Normale} {Sup\'erieure} de {Lyon}}, - title = {{Synth\`ese de preuves de programmes dans le Calcul des Constructions Inductives}}, - year = {1995} -} - -@Book{Caml, - author = {P. Weis and X. Leroy}, - publisher = {InterEditions}, - title = {Le langage Caml}, - year = {1993} -} - -@InProceedings{ChiPotSimp03, - author = {Laurent Chicli and Lo\"{\i}c Pottier and Carlos Simpson}, - title = {Mathematical Quotients and Quotient Types in Coq}, - booktitle = {TYPES}, - crossref = {DBLP:conf/types/2002}, - year = {2002} -} - -@TechReport{CoC89, - author = {Projet Formel}, - institution = {INRIA}, - number = {110}, - title = {{The Calculus of Constructions. Documentation and user's guide, Version 4.10}}, - year = {1989} -} - -@InProceedings{CoHu85a, - author = {Th. Coquand and G. Huet}, - address = {Linz}, - booktitle = {EUROCAL'85}, - publisher = SV, - series = LNCS, - title = {{Constructions : A Higher Order Proof System for Mechanizing Mathematics}}, - volume = {203}, - year = {1985} -} - -@InProceedings{CoHu85b, - author = {Th. Coquand and G. Huet}, - booktitle = {Logic Colloquium'85}, - editor = {The Paris Logic Group}, - publisher = {North-Holland}, - title = {{Concepts Math\'ematiques et Informatiques formalis\'es dans le Calcul des Constructions}}, - year = {1987} -} - -@Article{CoHu86, - author = {Th. Coquand and G. Huet}, - journal = {Information and Computation}, - number = {2/3}, - title = {The {Calculus of Constructions}}, - volume = {76}, - year = {1988} -} - -@InProceedings{CoPa89, - author = {Th. Coquand and C. Paulin-Mohring}, - booktitle = {Proceedings of Colog'88}, - editor = {P. Martin-L\"of and G. Mints}, - publisher = SV, - series = LNCS, - title = {Inductively defined types}, - volume = {417}, - year = {1990} -} - -@Book{Con86, - author = {R.L. {Constable et al.}}, - publisher = {Prentice-Hall}, - title = {{Implementing Mathematics with the Nuprl Proof Development System}}, - year = {1986} -} - -@PhDThesis{Coq85, - author = {Th. Coquand}, - month = jan, - school = {Universit\'e Paris~7}, - title = {Une Th\'eorie des Constructions}, - year = {1985} -} - -@InProceedings{Coq86, - author = {Th. Coquand}, - address = {Cambridge, MA}, - booktitle = {Symposium on Logic in Computer Science}, - publisher = {IEEE Computer Society Press}, - title = {{An Analysis of Girard's Paradox}}, - year = {1986} -} - -@InProceedings{Coq90, - author = {Th. Coquand}, - booktitle = {Logic and Computer Science}, - editor = {P. Oddifredi}, - note = {INRIA Research Report 1088, also in~\cite{CoC89}}, - publisher = {Academic Press}, - title = {{Metamathematical Investigations of a Calculus of Constructions}}, - year = {1990} -} - -@InProceedings{Coq91, - author = {Th. Coquand}, - booktitle = {Proceedings 9th Int. Congress of Logic, Methodology and Philosophy of Science}, - title = {{A New Paradox in Type Theory}}, - month = {August}, - year = {1991} -} - -@InProceedings{Coq92, - author = {Th. Coquand}, - title = {{Pattern Matching with Dependent Types}}, - year = {1992}, - crossref = {Bastad92} -} - -@InProceedings{Coquand93, - author = {Th. Coquand}, - booktitle = {Types for Proofs and Programs}, - editor = {H. Barendregt and T. Nipokow}, - publisher = SV, - series = LNCS, - title = {{Infinite objects in Type Theory}}, - volume = {806}, - year = {1993}, - pages = {62-78} -} - -@inproceedings{Corbineau08types, - author = {P. Corbineau}, - title = {A Declarative Language for the Coq Proof Assistant}, - editor = {M. Miculan and I. Scagnetto and F. Honsell}, - booktitle = {TYPES '07, Cividale del Friuli, Revised Selected Papers}, - publisher = {Springer}, - series = LNCS, - volume = {4941}, - year = {2007}, - pages = {69-84}, - ee = {http://dx.doi.org/10.1007/978-3-540-68103-8_5}, -} - -@PhDThesis{Cor97, - author = {C. Cornes}, - month = nov, - school = {{Universit\'e Paris 7}}, - title = {Conception d'un langage de haut niveau de représentation de preuves}, - type = {Th\`ese de Doctorat}, - year = {1997} -} - -@MastersThesis{Cou94a, - author = {J. Courant}, - month = sep, - school = {DEA d'Informatique, ENS Lyon}, - title = {Explicitation de preuves par r\'ecurrence implicite}, - year = {1994} -} - -@book{Cur58, - author = {Haskell B. Curry and Robert Feys and William Craig}, - title = {Combinatory Logic}, - volume = 1, - publisher = "North-Holland", - year = 1958, - note = {{\S{9E}}}, -} - -@InProceedings{Del99, - author = {Delahaye, D.}, - title = {Information Retrieval in a Coq Proof Library using - Type Isomorphisms}, - booktitle = {Proceedings of TYPES '99, L\"okeberg}, - publisher = SV, - series = lncs, - year = {1999}, - url = - "\\{\sf ftp://ftp.inria.fr/INRIA/Projects/coq/David.Delahaye/papers/}"# - "{\sf TYPES99-SIsos.ps.gz}" -} - -@InProceedings{Del00, - author = {Delahaye, D.}, - title = {A {T}actic {L}anguage for the {S}ystem {{\sf Coq}}}, - booktitle = {Proceedings of Logic for Programming and Automated Reasoning - (LPAR), Reunion Island}, - publisher = SV, - series = LNCS, - volume = {1955}, - pages = {85--95}, - month = {November}, - year = {2000}, - url = - "{\sf ftp://ftp.inria.fr/INRIA/Projects/coq/David.Delahaye/papers/}"# - "{\sf LPAR2000-ltac.ps.gz}" -} - -@InProceedings{DelMay01, - author = {Delahaye, D. and Mayero, M.}, - title = {{\tt Field}: une proc\'edure de d\'ecision pour les nombres r\'eels en {\Coq}}, - booktitle = {Journ\'ees Francophones des Langages Applicatifs, Pontarlier}, - publisher = {INRIA}, - month = {Janvier}, - year = {2001}, - url = - "\\{\sf ftp://ftp.inria.fr/INRIA/Projects/coq/David.Delahaye/papers/}"# - "{\sf JFLA2000-Field.ps.gz}" -} - -@TechReport{Dow90, - author = {G. Dowek}, - institution = {INRIA}, - number = {1283}, - title = {Naming and Scoping in a Mathematical Vernacular}, - type = {Research Report}, - year = {1990} -} - -@Article{Dow91a, - author = {G. Dowek}, - journal = {Compte-Rendus de l'Acad\'emie des Sciences}, - note = {The undecidability of Third Order Pattern Matching in Calculi with Dependent Types or Type Constructors}, - number = {12}, - pages = {951--956}, - title = {L'Ind\'ecidabilit\'e du Filtrage du Troisi\`eme Ordre dans les Calculs avec Types D\'ependants ou Constructeurs de Types}, - volume = {I, 312}, - year = {1991} -} - -@InProceedings{Dow91b, - author = {G. Dowek}, - booktitle = {Proceedings of Mathematical Foundation of Computer Science}, - note = {Also INRIA Research Report}, - pages = {151--160}, - publisher = SV, - series = LNCS, - title = {A Second Order Pattern Matching Algorithm in the Cube of Typed $\lambda$-calculi}, - volume = {520}, - year = {1991} -} - -@PhDThesis{Dow91c, - author = {G. Dowek}, - month = dec, - school = {Universit\'e Paris 7}, - title = {D\'emonstration automatique dans le Calcul des Constructions}, - year = {1991} -} - -@Article{Dow92a, - author = {G. Dowek}, - title = {The Undecidability of Pattern Matching in Calculi where Primitive Recursive Functions are Representable}, - year = 1993, - journal = tcs, - volume = 107, - number = 2, - pages = {349-356} -} - -@Article{Dow94a, - author = {G. Dowek}, - journal = {Annals of Pure and Applied Logic}, - volume = {69}, - pages = {135--155}, - title = {Third order matching is decidable}, - year = {1994} -} - -@InProceedings{Dow94b, - author = {G. Dowek}, - booktitle = {Proceedings of the second international conference on typed lambda calculus and applications}, - title = {Lambda-calculus, Combinators and the Comprehension Schema}, - year = {1995} -} - -@InProceedings{Dyb91, - author = {P. Dybjer}, - booktitle = {Logical Frameworks}, - editor = {G. Huet and G. Plotkin}, - pages = {59--79}, - publisher = {Cambridge University Press}, - title = {Inductive sets and families in {Martin-Löf's} - Type Theory and their set-theoretic semantics: An inversion principle for {Martin-L\"of's} type theory}, - volume = {14}, - year = {1991} -} - -@Article{Dyc92, - author = {Roy Dyckhoff}, - journal = {The Journal of Symbolic Logic}, - month = sep, - number = {3}, - title = {Contraction-free sequent calculi for intuitionistic logic}, - volume = {57}, - year = {1992} -} - -@MastersThesis{Fil94, - author = {J.-C. Filli\^atre}, - month = sep, - school = {DEA d'Informatique, ENS Lyon}, - title = {Une proc\'edure de d\'ecision pour le Calcul des Pr\'edicats Direct. Étude et impl\'ementation dans le syst\`eme {\Coq}}, - year = {1994} -} - -@TechReport{Filliatre95, - author = {J.-C. Filli\^atre}, - institution = {LIP-ENS-Lyon}, - title = {A decision procedure for Direct Predicate Calculus}, - type = {Research report}, - number = {96--25}, - year = {1995} -} - -@Article{Filliatre03jfp, - author = {J.-C. Filliâtre}, - title = {Verification of Non-Functional Programs - using Interpretations in Type Theory}, - journal = jfp, - volume = 13, - number = 4, - pages = {709--745}, - month = jul, - year = 2003, - note = {[English translation of \cite{Filliatre99}]}, - url = {http://www.lri.fr/~filliatr/ftp/publis/jphd.ps.gz}, - topics = {team, lri}, - type_publi = {irevcomlec} -} - -@PhDThesis{Filliatre99, - author = {J.-C. Filli\^atre}, - title = {Preuve de programmes imp\'eratifs en th\'eorie des types}, - type = {Thèse de Doctorat}, - school = {Universit\'e Paris-Sud}, - year = 1999, - month = {July}, - url = {\url{http://www.lri.fr/~filliatr/ftp/publis/these.ps.gz}} -} - -@Unpublished{Filliatre99c, - author = {J.-C. Filli\^atre}, - title = {{Formal Proof of a Program: Find}}, - month = {January}, - year = 2000, - note = {Submitted to \emph{Science of Computer Programming}}, - url = {\url{http://www.lri.fr/~filliatr/ftp/publis/find.ps.gz}} -} - -@InProceedings{FilliatreMagaud99, - author = {J.-C. Filli\^atre and N. Magaud}, - title = {Certification of sorting algorithms in the system {\Coq}}, - booktitle = {Theorem Proving in Higher Order Logics: - Emerging Trends}, - year = 1999, - url = {\url{http://www.lri.fr/~filliatr/ftp/publis/Filliatre-Magaud.ps.gz}} -} - -@Unpublished{Fle90, - author = {E. Fleury}, - month = jul, - note = {Rapport de Stage}, - title = {Implantation des algorithmes de {Floyd et de Dijkstra} dans le {Calcul des Constructions}}, - year = {1990} -} - -@Book{Fourier, - author = {Jean-Baptiste-Joseph Fourier}, - publisher = {Gauthier-Villars}, - title = {Fourier's method to solve linear - inequations/equations systems.}, - year = {1890} -} - -@InProceedings{Gim94, - author = {E. Gim\'enez}, - booktitle = {Types'94 : Types for Proofs and Programs}, - note = {Extended version in LIP research report 95-07, ENS Lyon}, - publisher = SV, - series = LNCS, - title = {Codifying guarded definitions with recursive schemes}, - volume = {996}, - year = {1994} -} - -@PhDThesis{Gim96, - author = {E. Gim\'enez}, - title = {Un calcul des constructions infinies et son application \'a la v\'erification de syst\`emes communicants}, - school = {\'Ecole Normale Sup\'erieure de Lyon}, - year = {1996} -} - -@TechReport{Gim98, - author = {E. Gim\'enez}, - title = {A Tutorial on Recursive Types in Coq}, - institution = {INRIA}, - year = 1998, - month = mar -} - -@Unpublished{GimCas05, - author = {E. Gim\'enez and P. Cast\'eran}, - title = {A Tutorial on [Co-]Inductive Types in Coq}, - institution = {INRIA}, - year = 2005, - month = jan, - note = {available at \url{http://coq.inria.fr/doc}} -} - -@InProceedings{Gimenez95b, - author = {E. Gim\'enez}, - booktitle = {Workshop on Types for Proofs and Programs}, - series = LNCS, - number = {1158}, - pages = {135-152}, - title = {An application of co-Inductive types in Coq: - verification of the Alternating Bit Protocol}, - editorS = {S. Berardi and M. Coppo}, - publisher = SV, - year = {1995} -} - -@InProceedings{Gir70, - author = {J.-Y. Girard}, - booktitle = {Proceedings of the 2nd Scandinavian Logic Symposium}, - publisher = {North-Holland}, - title = {Une extension de l'interpr\'etation de {G\"odel} \`a l'analyse, et son application \`a l'\'elimination des coupures dans l'analyse et la th\'eorie des types}, - year = {1970} -} - -@PhDThesis{Gir72, - author = {J.-Y. Girard}, - school = {Universit\'e Paris~7}, - title = {Interpr\'etation fonctionnelle et \'elimination des coupures de l'arithm\'etique d'ordre sup\'erieur}, - year = {1972} -} - -@Book{Gir89, - author = {J.-Y. Girard and Y. Lafont and P. Taylor}, - publisher = {Cambridge University Press}, - series = {Cambridge Tracts in Theoretical Computer Science 7}, - title = {Proofs and Types}, - year = {1989} -} - -@TechReport{Har95, - author = {John Harrison}, - title = {Metatheory and Reflection in Theorem Proving: A Survey and Critique}, - institution = {SRI International Cambridge Computer Science Research Centre,}, - year = 1995, - type = {Technical Report}, - number = {CRC-053}, - abstract = {http://www.cl.cam.ac.uk/users/jrh/papers.html} -} - -@MastersThesis{Hir94, - author = {D. Hirschkoff}, - month = sep, - school = {DEA IARFA, Ecole des Ponts et Chauss\'ees, Paris}, - title = {Écriture d'une tactique arithm\'etique pour le syst\`eme {\Coq}}, - year = {1994} -} - -@InProceedings{HofStr98, - author = {Martin Hofmann and Thomas Streicher}, - title = {The groupoid interpretation of type theory}, - booktitle = {Proceedings of the meeting Twenty-five years of constructive type theory}, - publisher = {Oxford University Press}, - year = {1998} -} - -@InCollection{How80, - author = {W.A. Howard}, - booktitle = {to H.B. Curry : Essays on Combinatory Logic, Lambda Calculus and Formalism.}, - editor = {J.P. Seldin and J.R. Hindley}, - note = {Unpublished 1969 Manuscript}, - publisher = {Academic Press}, - title = {The Formulae-as-Types Notion of Constructions}, - year = {1980} -} - -@InProceedings{Hue87tapsoft, - author = {G. Huet}, - title = {Programming of Future Generation Computers}, - booktitle = {Proceedings of TAPSOFT87}, - series = LNCS, - volume = 249, - pages = {276--286}, - year = 1987, - publisher = SV -} - -@InProceedings{Hue87, - author = {G. Huet}, - booktitle = {Programming of Future Generation Computers}, - editor = {K. Fuchi and M. Nivat}, - note = {Also in \cite{Hue87tapsoft}}, - publisher = {Elsevier Science}, - title = {Induction Principles Formalized in the {Calculus of Constructions}}, - year = {1988} -} - -@InProceedings{Hue88, - author = {G. Huet}, - booktitle = {A perspective in Theoretical Computer Science. Commemorative Volume for Gift Siromoney}, - editor = {R. Narasimhan}, - note = {Also in~\cite{CoC89}}, - publisher = {World Scientific Publishing}, - title = {{The Constructive Engine}}, - year = {1989} -} - -@Unpublished{Hue88b, - author = {G. Huet}, - title = {Extending the Calculus of Constructions with Type:Type}, - year = 1988, - note = {Unpublished} -} - -@Book{Hue89, - editor = {G. Huet}, - publisher = {Addison-Wesley}, - series = {The UT Year of Programming Series}, - title = {Logical Foundations of Functional Programming}, - year = {1989} -} - -@InProceedings{Hue92, - author = {G. Huet}, - booktitle = {Proceedings of 12th FST/TCS Conference, New Delhi}, - pages = {229--240}, - publisher = SV, - series = LNCS, - title = {The Gallina Specification Language : A case study}, - volume = {652}, - year = {1992} -} - -@Article{Hue94, - author = {G. Huet}, - journal = {J. Functional Programming}, - pages = {371--394}, - publisher = {Cambridge University Press}, - title = {Residual theory in $\lambda$-calculus: a formal development}, - volume = {4,3}, - year = {1994} -} - -@InCollection{HuetLevy79, - author = {G. Huet and J.-J. L\'{e}vy}, - title = {Call by Need Computations in Non-Ambigous -Linear Term Rewriting Systems}, - note = {Also research report 359, INRIA, 1979}, - booktitle = {Computational Logic, Essays in Honor of -Alan Robinson}, - editor = {J.-L. Lassez and G. Plotkin}, - publisher = {The MIT press}, - year = {1991} -} - -@Article{KeWe84, - author = {J. Ketonen and R. Weyhrauch}, - journal = {Theoretical Computer Science}, - pages = {297--307}, - title = {A decidable fragment of {P}redicate {C}alculus}, - volume = {32}, - year = {1984} -} - -@Book{Kle52, - author = {S.C. Kleene}, - publisher = {North-Holland}, - series = {Bibliotheca Mathematica}, - title = {Introduction to Metamathematics}, - year = {1952} -} - -@Book{Kri90, - author = {J.-L. Krivine}, - publisher = {Masson}, - series = {Etudes et recherche en informatique}, - title = {Lambda-calcul {types et mod\`eles}}, - year = {1990} -} - -@Book{LE92, - editor = {G. Huet and G. Plotkin}, - publisher = {Cambridge University Press}, - title = {Logical Environments}, - year = {1992} -} - -@Book{LF91, - editor = {G. Huet and G. Plotkin}, - publisher = {Cambridge University Press}, - title = {Logical Frameworks}, - year = {1991} -} - -@Article{Laville91, - author = {A. Laville}, - title = {Comparison of Priority Rules in Pattern -Matching and Term Rewriting}, - journal = {Journal of Symbolic Computation}, - volume = {11}, - pages = {321--347}, - year = {1991} -} - -@InProceedings{LePa94, - author = {F. Leclerc and C. Paulin-Mohring}, - booktitle = {{Types for Proofs and Programs, Types' 93}}, - editor = {H. Barendregt and T. Nipkow}, - publisher = SV, - series = {LNCS}, - title = {{Programming with Streams in Coq. A case study : The Sieve of Eratosthenes}}, - volume = {806}, - year = {1994} -} - -@TechReport{Leroy90, - author = {X. Leroy}, - title = {The {ZINC} experiment: an economical implementation -of the {ML} language}, - institution = {INRIA}, - number = {117}, - year = {1990} -} - -@InProceedings{Let02, - author = {P. Letouzey}, - title = {A New Extraction for Coq}, - booktitle = {TYPES}, - year = 2002, - crossref = {DBLP:conf/types/2002}, - url = {draft at \url{http://www.pps.jussieu.fr/~letouzey/download/extraction2002.ps.gz}} -} - -@PhDThesis{Luo90, - author = {Z. Luo}, - title = {An Extended Calculus of Constructions}, - school = {University of Edinburgh}, - year = {1990} -} - -@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}, - Title = {Specification of Rewriting Strategies}, - Year = {1997}} - -@Book{MaL84, - author = {{P. Martin-L\"of}}, - publisher = {Bibliopolis}, - series = {Studies in Proof Theory}, - title = {Intuitionistic Type Theory}, - year = {1984} -} - -@Article{MaSi94, - author = {P. Manoury and M. Simonot}, - title = {Automatizing Termination Proofs of Recursively Defined Functions.}, - journal = {TCS}, - volume = {135}, - number = {2}, - year = {1994}, - pages = {319-343}, -} - -@InProceedings{Miquel00, - author = {A. Miquel}, - title = {A Model for Impredicative Type Systems with Universes, -Intersection Types and Subtyping}, - booktitle = {{Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science (LICS'00)}}, - publisher = {IEEE Computer Society Press}, - year = {2000} -} - -@PhDThesis{Miquel01a, - author = {A. Miquel}, - title = {Le Calcul des Constructions implicite: syntaxe et s\'emantique}, - month = {dec}, - school = {{Universit\'e Paris 7}}, - year = {2001} -} - -@InProceedings{Miquel01b, - author = {A. Miquel}, - title = {The Implicit Calculus of Constructions: Extending Pure Type Systems with an Intersection Type Binder and Subtyping}, - booktitle = {{Proceedings of the fifth International Conference on Typed Lambda Calculi and Applications (TLCA01), Krakow, Poland}}, - publisher = SV, - series = {LNCS}, - number = 2044, - year = {2001} -} - -@InProceedings{MiWer02, - author = {A. Miquel and B. Werner}, - title = {The Not So Simple Proof-Irrelevant Model of CC}, - booktitle = {TYPES}, - year = {2002}, - pages = {240-258}, - ee = {http://link.springer.de/link/service/series/0558/bibs/2646/26460240.htm}, - crossref = {DBLP:conf/types/2002}, - bibsource = {DBLP, http://dblp.uni-trier.de} -} - -@proceedings{DBLP:conf/types/2002, - editor = {H. Geuvers and F. Wiedijk}, - title = {Types for Proofs and Programs, Second International Workshop, - TYPES 2002, Berg en Dal, The Netherlands, April 24-28, 2002, - Selected Papers}, - booktitle = {TYPES}, - publisher = SV, - series = LNCS, - volume = {2646}, - year = {2003}, - isbn = {3-540-14031-X}, - bibsource = {DBLP, http://dblp.uni-trier.de} -} - -@InProceedings{Moh89a, - author = {C. Paulin-Mohring}, - address = {Austin}, - booktitle = {Sixteenth Annual ACM Symposium on Principles of Programming Languages}, - month = jan, - publisher = {ACM}, - title = {Extracting ${F}_{\omega}$'s programs from proofs in the {Calculus of Constructions}}, - year = {1989} -} - -@PhDThesis{Moh89b, - author = {C. Paulin-Mohring}, - month = jan, - school = {{Universit\'e Paris 7}}, - title = {Extraction de programmes dans le {Calcul des Constructions}}, - year = {1989} -} - -@InProceedings{Moh93, - author = {C. Paulin-Mohring}, - booktitle = {Proceedings of the conference Typed Lambda Calculi and Applications}, - editor = {M. Bezem and J.-F. Groote}, - note = {Also LIP research report 92-49, ENS Lyon}, - number = {664}, - publisher = SV, - series = {LNCS}, - title = {{Inductive Definitions in the System Coq - Rules and Properties}}, - year = {1993} -} - -@Book{Moh97, - author = {C. Paulin-Mohring}, - month = jan, - publisher = {{ENS Lyon}}, - title = {{Le syst\`eme Coq. \mbox{Th\`ese d'habilitation}}}, - year = {1997} -} - -@MastersThesis{Mun94, - author = {C. Muñoz}, - month = sep, - school = {DEA d'Informatique Fondamentale, Universit\'e Paris 7}, - title = {D\'emonstration automatique dans la logique propositionnelle intuitionniste}, - year = {1994} -} - -@PhDThesis{Mun97d, - author = {C. Mu{\~{n}}oz}, - title = {Un calcul de substitutions pour la repr\'esentation - de preuves partielles en th\'eorie de types}, - school = {Universit\'e Paris 7}, - year = {1997}, - note = {Version en anglais disponible comme rapport de - recherche INRIA RR-3309}, - type = {Th\`ese de Doctorat} -} - -@Book{NoPS90, - author = {B. {Nordstr\"om} and K. Peterson and J. Smith}, - booktitle = {Information Processing 83}, - publisher = {Oxford Science Publications}, - series = {International Series of Monographs on Computer Science}, - title = {Programming in {Martin-L\"of's} Type Theory}, - year = {1990} -} - -@Article{Nor88, - author = {B. {Nordstr\"om}}, - journal = {BIT}, - title = {Terminating General Recursion}, - volume = {28}, - year = {1988} -} - -@Book{Odi90, - editor = {P. Odifreddi}, - publisher = {Academic Press}, - title = {Logic and Computer Science}, - year = {1990} -} - -@InProceedings{PaMS92, - author = {M. Parigot and P. Manoury and M. Simonot}, - address = {St. Petersburg, Russia}, - booktitle = {Logic Programming and automated reasoning}, - editor = {A. Voronkov}, - month = jul, - number = {624}, - publisher = SV, - series = {LNCS}, - title = {{ProPre : A Programming language with proofs}}, - year = {1992} -} - -@Article{PaWe92, - author = {C. Paulin-Mohring and B. Werner}, - journal = {Journal of Symbolic Computation}, - pages = {607--640}, - title = {{Synthesis of ML programs in the system Coq}}, - volume = {15}, - year = {1993} -} - -@Article{Par92, - author = {M. Parigot}, - journal = {Theoretical Computer Science}, - number = {2}, - pages = {335--356}, - title = {{Recursive Programming with Proofs}}, - volume = {94}, - year = {1992} -} - -@InProceedings{Parent95b, - author = {C. Parent}, - booktitle = {{Mathematics of Program Construction'95}}, - publisher = SV, - series = {LNCS}, - title = {{Synthesizing proofs from programs in -the Calculus of Inductive Constructions}}, - volume = {947}, - year = {1995} -} - -@InProceedings{Prasad93, - author = {K.V. Prasad}, - booktitle = {{Proceedings of CONCUR'93}}, - publisher = SV, - series = {LNCS}, - title = {{Programming with broadcasts}}, - volume = {715}, - year = {1993} -} - -@Book{RC95, - author = {di~Cosmo, R.}, - title = {Isomorphisms of Types: from $\lambda$-calculus to information - retrieval and language design}, - series = {Progress in Theoretical Computer Science}, - publisher = {Birkhauser}, - year = {1995}, - note = {ISBN-0-8176-3763-X} -} - -@TechReport{Rou92, - author = {J. Rouyer}, - institution = {INRIA}, - month = nov, - number = {1795}, - title = {{Développement de l'Algorithme d'Unification dans le Calcul des Constructions}}, - year = {1992} -} - -@Article{Rushby98, - title = {Subtypes for Specifications: Predicate Subtyping in - {PVS}}, - author = {John Rushby and Sam Owre and N. Shankar}, - journal = {IEEE Transactions on Software Engineering}, - pages = {709--720}, - volume = 24, - number = 9, - month = sep, - year = 1998 -} - -@TechReport{Saibi94, - author = {A. Sa\"{\i}bi}, - institution = {INRIA}, - month = dec, - number = {2345}, - title = {{Axiomatization of a lambda-calculus with explicit-substitutions in the Coq System}}, - year = {1994} -} - - -@MastersThesis{Ter92, - author = {D. Terrasse}, - month = sep, - school = {IARFA}, - title = {{Traduction de TYPOL en COQ. Application \`a Mini ML}}, - year = {1992} -} - -@TechReport{ThBeKa92, - author = {L. Th\'ery and Y. Bertot and G. Kahn}, - institution = {INRIA Sophia}, - month = may, - number = {1684}, - title = {Real theorem provers deserve real user-interfaces}, - type = {Research Report}, - year = {1992} -} - -@Book{TrDa89, - author = {A.S. Troelstra and D. van Dalen}, - publisher = {North-Holland}, - series = {Studies in Logic and the foundations of Mathematics, volumes 121 and 123}, - title = {Constructivism in Mathematics, an introduction}, - year = {1988} -} - -@PhDThesis{Wer94, - author = {B. Werner}, - school = {Universit\'e Paris 7}, - title = {Une th\'eorie des constructions inductives}, - type = {Th\`ese de Doctorat}, - year = {1994} -} - -@PhDThesis{Bar99, - author = {B. Barras}, - school = {Universit\'e Paris 7}, - title = {Auto-validation d'un système de preuves avec familles inductives}, - type = {Th\`ese de Doctorat}, - year = {1999} -} - -@Unpublished{ddr98, - author = {D. de Rauglaudre}, - title = {Camlp4 version 1.07.2}, - year = {1998}, - note = {In Camlp4 distribution} -} - -@Article{dowek93, - author = {G. Dowek}, - title = {{A Complete Proof Synthesis Method for the Cube of Type Systems}}, - journal = {Journal Logic Computation}, - volume = {3}, - number = {3}, - pages = {287--315}, - month = {June}, - year = {1993} -} - -@InProceedings{manoury94, - author = {P. Manoury}, - title = {{A User's Friendly Syntax to Define -Recursive Functions as Typed $\lambda-$Terms}}, - booktitle = {{Types for Proofs and Programs, TYPES'94}}, - series = {LNCS}, - volume = {996}, - month = jun, - year = {1994} -} - -@TechReport{maranget94, - author = {L. Maranget}, - institution = {INRIA}, - number = {2385}, - title = {{Two Techniques for Compiling Lazy Pattern Matching}}, - year = {1994} -} - -@InProceedings{puel-suarez90, - author = {L.Puel and A. Su\'arez}, - booktitle = {{Conference Lisp and Functional Programming}}, - series = {ACM}, - publisher = SV, - title = {{Compiling Pattern Matching by Term -Decomposition}}, - year = {1990} -} - -@MastersThesis{saidi94, - author = {H. Saidi}, - month = sep, - school = {DEA d'Informatique Fondamentale, Universit\'e Paris 7}, - title = {R\'esolution d'\'equations dans le syst\`eme T - de G\"odel}, - year = {1994} -} - -@inproceedings{sozeau06, - author = {Matthieu Sozeau}, - title = {Subset Coercions in {C}oq}, - year = {2007}, - booktitle = {TYPES'06}, - pages = {237-252}, - volume = {4502}, - publisher = "Springer", - series = {LNCS} -} - -@inproceedings{sozeau08, - Author = {Matthieu Sozeau and Nicolas Oury}, - booktitle = {TPHOLs'08}, - Pdf = {http://www.lri.fr/~sozeau/research/publications/drafts/classes.pdf}, - Title = {{F}irst-{C}lass {T}ype {C}lasses}, - Year = {2008}, -} - -@Misc{streicher93semantical, - author = {T. Streicher}, - title = {Semantical Investigations into Intensional Type Theory}, - note = {Habilitationsschrift, LMU Munchen.}, - year = {1993} -} - -@Misc{Pcoq, - author = {Lemme Team}, - title = {Pcoq a graphical user-interface for {Coq}}, - note = {\url{http://www-sop.inria.fr/lemme/pcoq/}} -} - -@Misc{ProofGeneral, - author = {David Aspinall}, - title = {Proof General}, - note = {\url{https://proofgeneral.github.io/}} -} - -@Book{CoqArt, - title = {Interactive Theorem Proving and Program Development. - Coq'Art: The Calculus of Inductive Constructions}, - author = {Yves Bertot and Pierre Castéran}, - publisher = {Springer Verlag}, - series = {Texts in Theoretical Computer Science. An EATCS series}, - year = 2004 -} - -@InCollection{wadler87, - author = {P. Wadler}, - title = {Efficient Compilation of Pattern Matching}, - booktitle = {The Implementation of Functional Programming -Languages}, - editor = {S.L. Peyton Jones}, - publisher = {Prentice-Hall}, - year = {1987} -} - -@inproceedings{DBLP:conf/types/CornesT95, - author = {Cristina Cornes and - Delphine Terrasse}, - title = {Automating Inversion of Inductive Predicates in Coq}, - booktitle = {TYPES}, - year = {1995}, - pages = {85-104}, - crossref = {DBLP:conf/types/1995}, - bibsource = {DBLP, http://dblp.uni-trier.de} -} -@proceedings{DBLP:conf/types/1995, - editor = {Stefano Berardi and - Mario Coppo}, - title = {Types for Proofs and Programs, International Workshop TYPES'95, - Torino, Italy, June 5-8, 1995, Selected Papers}, - booktitle = {TYPES}, - publisher = {Springer}, - series = {Lecture Notes in Computer Science}, - volume = {1158}, - year = {1996}, - isbn = {3-540-61780-9}, - bibsource = {DBLP, http://dblp.uni-trier.de} -} - -@inproceedings{DBLP:conf/types/McBride00, - author = {Conor McBride}, - title = {Elimination with a Motive}, - booktitle = {TYPES}, - year = {2000}, - pages = {197-216}, - ee = {http://link.springer.de/link/service/series/0558/bibs/2277/22770197.htm}, - crossref = {DBLP:conf/types/2000}, - bibsource = {DBLP, http://dblp.uni-trier.de} -} - -@proceedings{DBLP:conf/types/2000, - editor = {Paul Callaghan and - Zhaohui Luo and - James McKinna and - Robert Pollack}, - title = {Types for Proofs and Programs, International Workshop, TYPES - 2000, Durham, UK, December 8-12, 2000, Selected Papers}, - booktitle = {TYPES}, - publisher = {Springer}, - series = {Lecture Notes in Computer Science}, - volume = {2277}, - year = {2002}, - isbn = {3-540-43287-6}, - bibsource = {DBLP, http://dblp.uni-trier.de} -} - -@INPROCEEDINGS{sugar, - author = {Alessandro Giovini and Teo Mora and Gianfranco Niesi and Lorenzo Robbiano and Carlo Traverso}, - title = {"One sugar cube, please" or Selection strategies in the Buchberger algorithm}, - booktitle = { Proceedings of the ISSAC'91, ACM Press}, - year = {1991}, - pages = {5--4}, - publisher = {} -} - -@article{LeeWerner11, - author = {Gyesik Lee and - Benjamin Werner}, - title = {Proof-irrelevant model of {CC} with predicative induction - and judgmental equality}, - journal = {Logical Methods in Computer Science}, - volume = {7}, - number = {4}, - year = {2011}, - ee = {http://dx.doi.org/10.2168/LMCS-7(4:5)2011}, - bibsource = {DBLP, http://dblp.uni-trier.de} -} - -@Comment{cross-references, must be at end} - -@Book{Bastad92, - editor = {B. Nordstr\"om and K. Petersson and G. Plotkin}, - publisher = {Available by ftp at site ftp.inria.fr}, - title = {Proceedings of the 1992 Workshop on Types for Proofs and Programs}, - year = {1992} -} - -@Book{Nijmegen93, - editor = {H. Barendregt and T. Nipkow}, - publisher = SV, - series = LNCS, - title = {Types for Proofs and Programs}, - volume = {806}, - year = {1994} -} - -@article{ TheOmegaPaper, - author = "W. Pugh", - title = "The Omega test: a fast and practical integer programming algorithm for dependence analysis", - journal = "Communication of the ACM", - pages = "102--114", - year = "1992", -} - -@inproceedings{CSwcu, - hal_id = {hal-00816703}, - url = {http://hal.inria.fr/hal-00816703}, - title = {{Canonical Structures for the working Coq user}}, - author = {Mahboubi, Assia and Tassi, Enrico}, - booktitle = {{ITP 2013, 4th Conference on Interactive Theorem Proving}}, - publisher = {Springer}, - pages = {19-34}, - address = {Rennes, France}, - volume = {7998}, - editor = {Sandrine Blazy and Christine Paulin and David Pichardie }, - series = {LNCS }, - doi = {10.1007/978-3-642-39634-2\_5 }, - year = {2013}, -} - -@article{CSlessadhoc, - author = {Gonthier, Georges and Ziliani, Beta and Nanevski, Aleksandar and Dreyer, Derek}, - title = {How to Make Ad Hoc Proof Automation Less Ad Hoc}, - journal = {SIGPLAN Not.}, - issue_date = {September 2011}, - volume = {46}, - number = {9}, - month = sep, - year = {2011}, - issn = {0362-1340}, - pages = {163--175}, - numpages = {13}, - url = {http://doi.acm.org/10.1145/2034574.2034798}, - doi = {10.1145/2034574.2034798}, - acmid = {2034798}, - publisher = {ACM}, - address = {New York, NY, USA}, - keywords = {canonical structures, coq, custom proof automation, hoare type theory, interactive theorem proving, tactics, type classes}, -} - -@inproceedings{CompiledStrongReduction, - author = {Benjamin Gr{\'{e}}goire and - Xavier Leroy}, - editor = {Mitchell Wand and - Simon L. Peyton Jones}, - title = {A compiled implementation of strong reduction}, - booktitle = {Proceedings of the Seventh {ACM} {SIGPLAN} International Conference - on Functional Programming {(ICFP} '02), Pittsburgh, Pennsylvania, - USA, October 4-6, 2002.}, - pages = {235--246}, - publisher = {{ACM}}, - year = {2002}, - url = {http://doi.acm.org/10.1145/581478.581501}, - doi = {10.1145/581478.581501}, - timestamp = {Tue, 11 Jun 2013 13:49:16 +0200}, - biburl = {http://dblp.uni-trier.de/rec/bib/conf/icfp/GregoireL02}, - bibsource = {dblp computer science bibliography, http://dblp.org} -} - -@inproceedings{FullReduction, - author = {Mathieu Boespflug and - Maxime D{\'{e}}n{\`{e}}s and - Benjamin Gr{\'{e}}goire}, - editor = {Jean{-}Pierre Jouannaud and - Zhong Shao}, - title = {Full Reduction at Full Throttle}, - booktitle = {Certified Programs and Proofs - First International Conference, {CPP} - 2011, Kenting, Taiwan, December 7-9, 2011. Proceedings}, - series = {Lecture Notes in Computer Science}, - volume = {7086}, - pages = {362--377}, - publisher = {Springer}, - year = {2011}, - url = {http://dx.doi.org/10.1007/978-3-642-25379-9_26}, - doi = {10.1007/978-3-642-25379-9_26}, - timestamp = {Thu, 17 Nov 2011 13:33:48 +0100}, - biburl = {http://dblp.uni-trier.de/rec/bib/conf/cpp/BoespflugDG11}, - bibsource = {dblp computer science bibliography, http://dblp.org} -} diff --git a/doc/refman/coq-listing.tex b/doc/refman/coq-listing.tex deleted file mode 100644 index c69c3b1b81..0000000000 --- a/doc/refman/coq-listing.tex +++ /dev/null @@ -1,152 +0,0 @@ -%======================================================================= -% Listings LaTeX package style for Gallina + SSReflect (Assia Mahboubi 2007) - -\lstdefinelanguage{SSR} { - -% Anything betweeen $ becomes LaTeX math mode -mathescape=true, -% Comments may or not include Latex commands -texcl=false, - - -% Vernacular commands -morekeywords=[1]{ -From, Section, Module, End, Require, Import, Export, Defensive, Function, -Variable, Variables, Parameter, Parameters, Axiom, Hypothesis, Hypotheses, -Notation, Local, Tactic, Reserved, Scope, Open, Close, Bind, Delimit, -Definition, Let, Ltac, Fixpoint, CoFixpoint, Add, Morphism, Relation, -Implicit, Arguments, Set, Unset, Contextual, Strict, Prenex, Implicits, -Inductive, CoInductive, Record, Structure, Canonical, Coercion, -Theorem, Lemma, Corollary, Proposition, Fact, Remark, Example, -Proof, Goal, Save, Qed, Defined, Hint, Resolve, Rewrite, View, -Search, Show, Print, Printing, All, Graph, Projections, inside, -outside, Locate, Maximal}, - -% Gallina -morekeywords=[2]{forall, exists, exists2, fun, fix, cofix, struct, - match, with, end, as, in, return, let, if, is, then, else, - for, of, nosimpl}, - -% Sorts -morekeywords=[3]{Type, Prop}, - -% Various tactics, some are std Coq subsumed by ssr, for the manual purpose -morekeywords=[4]{ - pose, set, move, case, elim, apply, clear, - hnf, intro, intros, generalize, rename, pattern, after, - destruct, induction, using, refine, inversion, injection, - rewrite, congr, unlock, compute, ring, field, - replace, fold, unfold, change, cutrewrite, simpl, - have, gen, generally, suff, wlog, suffices, without, loss, nat_norm, - assert, cut, trivial, revert, bool_congr, nat_congr, abstract, - symmetry, transitivity, auto, split, left, right, autorewrite}, - -% Terminators -morekeywords=[5]{ - by, done, exact, reflexivity, tauto, romega, omega, - assumption, solve, contradiction, discriminate}, - - -% Control -morekeywords=[6]{do, last, first, try, idtac, repeat}, - -% Various symbols -% For the ssr manual we turn off the prettyprint of formulas -% literate= -% {->}{{$\rightarrow\,$}}2 -% {->}{{\tt ->}}3 -% {<-}{{$\leftarrow\,$}}2 -% {<-}{{\tt <-}}2 -% {>->}{{$\mapsto$}}3 -% {<=}{{$\leq$}}1 -% {>=}{{$\geq$}}1 -% {<>}{{$\neq$}}1 -% {/\\}{{$\wedge$}}2 -% {\\/}{{$\vee$}}2 -% {<->}{{$\leftrightarrow\;$}}3 -% {<=>}{{$\Leftrightarrow\;$}}3 -% {:nat}{{$~\in\mathbb{N}$}}3 -% {fforall\ }{{$\forall_f\,$}}1 -% {forall\ }{{$\forall\,$}}1 -% {exists\ }{{$\exists\,$}}1 -% {negb}{{$\neg$}}1 -% {spp}{{:*:\,}}1 -% {~}{{$\sim$}}1 -% {\\in}{{$\in\;$}}1 -% {/\\}{$\land\,$}1 -% {:*:}{{$*$}}2 -% {=>}{{$\,\Rightarrow\ $}}1 -% {=>}{{\tt =>}}2 -% {:=}{{{\tt:=}\,\,}}2 -% {==}{{$\equiv$}\,}2 -% {!=}{{$\neq$}\,}2 -% {^-1}{{$^{-1}$}}1 -% {elt'}{elt'}1 -% {=}{{\tt=}\,\,}2 -% {+}{{\tt+}\,\,}2, -literate= - {isn't }{{{\ttfamily\color{dkgreen} isn't }}}1, - -% Comments delimiters, we do turn this off for the manual -%comment=[s]{(*}{*)}, - -% Spaces are not displayed as a special character -showstringspaces=false, - -% String delimiters -morestring=[b]", -morestring=[d]", - -% Size of tabulations -tabsize=3, - -% Enables ASCII chars 128 to 255 -extendedchars=true, - -% Case sensitivity -sensitive=true, - -% Automatic breaking of long lines -breaklines=true, - -% Default style fors listings -basicstyle=\ttfamily, - -% Position of captions is bottom -captionpos=b, - -% Full flexible columns -columns=[l]fullflexible, - -% Style for (listings') identifiers -identifierstyle={\ttfamily\color{black}}, -% Note : highlighting of Coq identifiers is done through a new -% delimiter definition through an lstset at the begining of the -% document. Don't know how to do better. - -% Style for declaration keywords -keywordstyle=[1]{\ttfamily\color{dkviolet}}, - -% Style for gallina keywords -keywordstyle=[2]{\ttfamily\color{dkgreen}}, - -% Style for sorts keywords -keywordstyle=[3]{\ttfamily\color{lightblue}}, - -% Style for tactics keywords -keywordstyle=[4]{\ttfamily\color{dkblue}}, - -% Style for terminators keywords -keywordstyle=[5]{\ttfamily\color{red}}, - - -%Style for iterators -keywordstyle=[6]{\ttfamily\color{dkpink}}, - -% Style for strings -stringstyle=\ttfamily, - -% Style for comments -commentstyle=\rmfamily, - -} diff --git a/doc/refman/coqide-queries.png b/doc/refman/coqide-queries.png Binary files differdeleted file mode 100644 index 7a46ac4e68..0000000000 --- a/doc/refman/coqide-queries.png +++ /dev/null diff --git a/doc/refman/coqide.png b/doc/refman/coqide.png Binary files differdeleted file mode 100644 index e300401c9f..0000000000 --- a/doc/refman/coqide.png +++ /dev/null diff --git a/doc/refman/headers.hva b/doc/refman/headers.hva deleted file mode 100644 index 9714a29beb..0000000000 --- a/doc/refman/headers.hva +++ /dev/null @@ -1,44 +0,0 @@ -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% File headers.hva -% Hevea version of headers.sty -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% Commands for indexes -%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\usepackage{index} -\makeindex - - -\newindex{tactic}{tacidx}{tacind}{Tactics Index} -\newindex{command}{comidx}{comind}{Vernacular Commands Index} -\newindex{option}{optidx}{optind}{Vernacular Options Index} -\newindex{error}{erridx}{errind}{Index of Error Messages} -\renewindex{default}{idx}{ind}{Global Index} - -\newcommand{\printrefmanindex}[3]{% -\addcontentsline{toc}{chapter}{#2}% -\printindex[#1]% -\cutname{#3}% -} - -\newcommand{\tacindex}[1]{% -\index{#1@\texttt{#1}}\index[tactic]{#1@\texttt{#1}}} -\newcommand{\comindex}[1]{% -\index{#1@\texttt{#1}}\index[command]{#1@\texttt{#1}}} -\newcommand{\optindex}[1]{% -\index{#1@\texttt{#1}}\index[option]{#1@\texttt{#1}}} -\newcommand{\errindex}[1]{\texttt{#1}\index[error]{#1}} -\newcommand{\errindexbis}[2]{\texttt{#1}\index[error]{#2}} -\newcommand{\ttindex}[1]{\index{#1@\texttt{#1}}} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% For the Addendum table of contents -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\newcommand{\aauthor}[1]{{\LARGE \bf #1} \bigskip} % 3 \bigskip's that were here originally - % may be good for LaTeX but too much for HTML -\newcommand{\atableofcontents}{} -\newcommand{\achapter}[1]{\chapter{#1}} -\newcommand{\asection}{\section} -\newcommand{\asubsection}{\subsection} -\newcommand{\asubsubsection}{\subsubsection} diff --git a/doc/refman/headers.sty b/doc/refman/headers.sty deleted file mode 100644 index fb39f687d7..0000000000 --- a/doc/refman/headers.sty +++ /dev/null @@ -1,88 +0,0 @@ -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% File headers.sty -% Commands for pretty headers, multiple indexes, and the appendix. -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\usepackage{fancyhdr} - -\setlength{\headheight}{14pt} - -\pagestyle{fancyplain} - -\newcommand{\coqfooter}{\tiny Coq Reference Manual, V\coqversion{}, \today} - -\cfoot{} -\lfoot[{\coqfooter}]{} -\rfoot[]{{\coqfooter}} - -\newcommand{\setheaders}[1]{\rhead[\fancyplain{}{\textbf{#1}}]{\fancyplain{}{\thepage}}\lhead[\fancyplain{}{\thepage}]{\fancyplain{}{\textbf{#1}}}} -\newcommand{\defaultheaders}{\rhead[\fancyplain{}{\leftmark}]{\fancyplain{}{\thepage}}\lhead[\fancyplain{}{\thepage}]{\fancyplain{}{\rightmark}}} - -\renewcommand{\chaptermark}[1]{\markboth{{\bf \thechapter~#1}}{}} -\renewcommand{\sectionmark}[1]{\markright{\thesection~#1}} -\renewcommand{\contentsname}{% -\protect\setheaders{Table of contents}Table of contents} -\renewcommand{\bibname}{\protect\setheaders{Bibliography}% -\protect\RefManCutCommand{BEGINBIBLIO=\thepage}% -\protect\addcontentsline{toc}{chapter}{Bibliography}Bibliography} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% Commands for indexes -%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\usepackage{index} -\makeindex - -\newindex{tactic}{tacidx}{tacind}{Tactics Index} -\newindex{command}{comidx}{comind}{Vernacular Commands Index} -\newindex{option}{optidx}{optind}{Vernacular Options Index} -\newindex{error}{erridx}{errind}{Index of Error Messages} -\renewindex{default}{idx}{ind}{Global Index} - -\newcommand{\printrefmanindex}[3]{% -\cleardoublepage% -\phantomsection% -\setheaders{#2}% -\addcontentsline{toc}{chapter}{#2}% -\printindex[#1]% -\cutname{#3}% -} - -\newcommand{\tacindex}[1]{% -\index{#1@\texttt{#1}}\index[tactic]{#1@\texttt{#1}}} -\newcommand{\comindex}[1]{% -\index{#1@\texttt{#1}}\index[command]{#1@\texttt{#1}}} -\newcommand{\optindex}[1]{% -\index{#1@\texttt{#1}}\index[option]{#1@\texttt{#1}}} -\newcommand{\errindex}[1]{\texttt{#1}\index[error]{#1}} -\newcommand{\errindexbis}[2]{\texttt{#1}\index[error]{#2}} -\newcommand{\ttindex}[1]{\index{#1@\texttt{#1}}} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% For the Addendum table of contents -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\newcommand{\aauthor}[1]{{\LARGE \bf #1} \bigskip \bigskip \bigskip} -\newcommand{\atableofcontents}{\section*{Contents}\@starttoc{atoc}} -\newcommand{\achapter}[1]{ - \chapter{#1}\addcontentsline{atoc}{chapter}{#1}} -\newcommand{\asection}[1]{ - \section{#1}\addcontentsline{atoc}{section}{#1}} -\newcommand{\asubsection}[1]{ - \subsection{#1}\addcontentsline{atoc}{subsection}{#1}} -\newcommand{\asubsubsection}[1]{ - \subsubsection{#1}\addcontentsline{atoc}{subsubsection}{#1}} - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -% Reference-Manual.sh is generated to cut the Postscript -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -%\@starttoc{sh} -\newwrite\RefManCut@out% -\immediate\openout\RefManCut@out\jobname.sh -\newcommand{\RefManCutCommand}[1]{% -\immediate\write\RefManCut@out{#1}} -\newcommand{\RefManCutClose}{% -\immediate\closeout\RefManCut@out} - - -%%% Local Variables: -%%% mode: latex -%%% TeX-master: "Reference-Manual" -%%% End: diff --git a/doc/refman/index.html b/doc/refman/index.html deleted file mode 100644 index b937350e6e..0000000000 --- a/doc/refman/index.html +++ /dev/null @@ -1,14 +0,0 @@ -<HTML> - -<HEAD> - -<TITLE>The Coq Proof Assistant Reference Manual</TITLE> - -</HEAD> - -<FRAMESET ROWS=90%,*> - <FRAME SRC="cover.html" NAME="UP"> - <FRAME SRC="menu.html"> -</FRAMESET> - -</HTML> diff --git a/doc/refman/menu.html b/doc/refman/menu.html deleted file mode 100644 index 7312ad344c..0000000000 --- a/doc/refman/menu.html +++ /dev/null @@ -1,32 +0,0 @@ -<HTML> - -<BODY> - -<CENTER> - -<TABLE BORDER="0" CELLPADDING=10> -<TR> -<TD><CENTER><A HREF="cover.html" TARGET="UP"><FONT SIZE=2>Cover page</FONT></A></CENTER></TD> -<TD><CENTER><A HREF="toc.html" TARGET="UP"><FONT SIZE=2>Table of contents</FONT></A></CENTER></TD> -<TD><CENTER><A HREF="biblio.html" TARGET="UP"><FONT SIZE=2> -Bibliography</FONT></A></CENTER></TD> -<TD><CENTER><A HREF="general-index.html" TARGET="UP"><FONT SIZE=2> -Global Index -</FONT></A></CENTER></TD> -<TD><CENTER><A HREF="tactic-index.html" TARGET="UP"><FONT SIZE=2> -Tactics Index -</FONT></A></CENTER></TD> -<TD><CENTER><A HREF="command-index.html" TARGET="UP"><FONT SIZE=2> -Vernacular Commands Index -</FONT></A></CENTER></TD> -<TD><CENTER><A HREF="option-index.html" TARGET="UP"><FONT SIZE=2> -Vernacular Options Index -</FONT></A></CENTER></TD> -<TD><CENTER><A HREF="error-index.html" TARGET="UP"><FONT SIZE=2> -Index of Error Messages -</FONT></A></CENTER></TD> -</TABLE> - -</CENTER> - -</BODY></HTML> diff --git a/doc/sphinx/addendum/generalized-rewriting.rst b/doc/sphinx/addendum/generalized-rewriting.rst index d60387f4f6..e4dea34874 100644 --- a/doc/sphinx/addendum/generalized-rewriting.rst +++ b/doc/sphinx/addendum/generalized-rewriting.rst @@ -537,14 +537,19 @@ Notice, however, that using the prefixed tactics it is possible to pass additional arguments such as ``using relation``. .. tacv:: setoid_reflexivity + :name: setoid_reflexivity .. tacv:: setoid_symmetry [in @ident] + :name: setoid_symmetry .. tacv:: setoid_transitivity + :name: setoid_transitivity .. 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] + :name: setoid_replace The ``using relation`` arguments cannot be passed to the unprefixed form. @@ -583,7 +588,7 @@ Deprecated syntax and backward incompatibilities Due to backward compatibility reasons, the following syntax for the declaration of setoids and morphisms is also accepted. -.. tacv:: Add Setoid @A @Aeq @ST as @ident +.. 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 @@ -818,7 +823,8 @@ Usage ~~~~~ -.. tacv:: rewrite_strat @s [in @ident] +.. tacn:: rewrite_strat @s [in @ident] + :name: rewrite_strat Rewrite using the strategy s in hypothesis ident or the conclusion. diff --git a/doc/sphinx/addendum/implicit-coercions.rst b/doc/sphinx/addendum/implicit-coercions.rst index ec1b942e02..c48c2d7ce1 100644 --- a/doc/sphinx/addendum/implicit-coercions.rst +++ b/doc/sphinx/addendum/implicit-coercions.rst @@ -138,7 +138,7 @@ Declaration of Coercions .. exn:: @qualid does not respect the uniform inheritance condition .. exn:: Found target class ... instead of ... - .. warn:: Ambigous path: + .. warn:: Ambiguous path When the coercion `qualid` is added to the inheritance graph, non valid coercion paths are ignored; they are signaled by a warning @@ -218,6 +218,7 @@ declaration, this constructor is declared as a coercion. Idem but locally to the current section. .. cmdv:: SubClass @ident := @type. + :name: SubClass If `type` is a class `ident'` applied to some arguments then `ident` is defined and an identity coercion of name @@ -255,17 +256,16 @@ Displaying Available Coercions Activating the Printing of Coercions ------------------------------------- -.. cmd:: Set Printing Coercions. +.. opt:: Printing Coercions - This command forces all the coercions to be printed. - Conversely, to skip the printing of coercions, use - ``Unset Printing Coercions``. By default, coercions are not printed. + When on, this option forces all the coercions to be printed. + By default, coercions are not printed. -.. cmd:: Add Printing Coercion @qualid. +.. cmd:: Add Printing Coercion @qualid - This command forces coercion denoted by `qualid` to be printed. - To skip the printing of coercion `qualid`, use - ``Remove Printing Coercion`` `qualid`. By default, a coercion is never printed. + This command forces coercion denoted by :n:`@qualid` to be printed. To skip + the printing of coercion :n:`@qualid`, use :cmd:`Remove Printing Coercion`. By + default, a coercion is never printed. .. _coercions-classes-as-records: @@ -291,12 +291,10 @@ by extending the existing :cmd:`Record` macro. Its new syntax is: (this may fail if the uniform inheritance condition is not satisfied). -.. note:: +.. cmdv:: Structure {? >} @ident {? @binders} : @sort := {? @ident} { {+; @ident :{? >} @term } }. + :name: Structure - The keyword ``Structure`` is a synonym of ``Record``. - -.. - FIXME: \comindex{Structure} + This is a synonym of :cmd:`Record`. Coercions and Sections @@ -312,20 +310,17 @@ coercions which do not verify the uniform inheritance condition any longer are also forgotten. Coercions and Modules ---------------------= - -From |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 -imported or not. - -To recover the behavior of the versions of |Coq| prior to 8.3, use the -following command: +--------------------- -.. cmd:: Set Automatic Coercions Import. +.. opt:: Automatic Coercions Import -To cancel the effect of the option, use instead ``Unset Automatic Coercions Import``. + 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 + imported or not. + This option makes it possible to recover the behavior of the versions of + |Coq| prior to 8.3. Examples -------- diff --git a/doc/sphinx/addendum/micromega.rst b/doc/sphinx/addendum/micromega.rst index e850587c8a..4f8cc34d4a 100644 --- a/doc/sphinx/addendum/micromega.rst +++ b/doc/sphinx/addendum/micromega.rst @@ -13,20 +13,19 @@ tactics for solving arithmetic goals over :math:`\mathbb{Z}`, :math:`\mathbb{Q}` It also possible to get the tactics for integers by a ``Require Import Lia``, rationals ``Require Import Lqa`` and reals ``Require Import Lra``. -+ ``lia`` is a decision procedure for linear integer arithmetic (see Section :ref:`lia <lia>`); -+ ``nia`` is an incomplete proof procedure for integer non-linear - arithmetic (see Section :ref:`nia <nia>`); -+ ``lra`` is a decision procedure for linear (real or rational) arithmetic - (see Section :ref:`lra <lra>`); -+ ``nra`` is an incomplete proof procedure for non-linear (real or - rational) arithmetic (see Section :ref:`nra <nra>`); -+ ``psatz D n`` where ``D`` is :math:`\mathbb{Z}` or :math:`\mathbb{Q}` or :math:`\mathbb{R}`, and ++ :tacn:`lia` is a decision procedure for linear integer arithmetic; ++ :tacn:`nia` is an incomplete proof procedure for integer non-linear + arithmetic; ++ :tacn:`lra` is a decision procedure for linear (real or rational) arithmetic; ++ :tacn:`nra` is an incomplete proof procedure for non-linear (real or + rational) arithmetic; ++ :tacn:`psatz` ``D n`` where ``D`` is :math:`\mathbb{Z}` or :math:`\mathbb{Q}` or :math:`\mathbb{R}`, and ``n`` is an optional integer limiting the proof search depth is an incomplete proof procedure for non-linear arithmetic. It is based on John Harrison’s HOL Light driver to the external prover `csdp` [#]_. Note that the `csdp` driver is generating a *proof cache* which makes it possible to rerun scripts - even without `csdp` (see Section :ref:`psatz <psatz>`). + even without `csdp`. The tactics solve propositional formulas parameterized by atomic arithmetic expressions interpreted over a domain :math:`D` ∈ {ℤ, ℚ, ℝ}. @@ -91,12 +90,13 @@ For each conjunct :math:`C_i`, the tactic calls a oracle which searches for expression* that is normalized by the ring tactic (see :ref:`theringandfieldtacticfamilies`) and checked to be :math:`-1`. -.. _lra: - `lra`: a decision procedure for linear real and rational arithmetic ------------------------------------------------------------------- -The `lra` tactic is searching for *linear* refutations using Fourier +.. tacn:: lra + :name: lra + +This tactic is searching for *linear* refutations using Fourier elimination [#]_. As a result, this tactic explores a subset of the *Cone* defined as @@ -107,16 +107,17 @@ The deductive power of `lra` is the combined deductive power of tactic *e.g.*, :math:`x = 10 * x / 10` is solved by `lra`. -.. _lia: - `lia`: a tactic for linear integer arithmetic --------------------------------------------- -The tactic lia offers an alternative to the omega and romega tactic -(see :ref:`omega`). Roughly speaking, the deductive power of lia is -the combined deductive power of `ring_simplify` and `omega`. However, it -solves linear goals that `omega` and `romega` do not solve, such as the -following so-called *omega nightmare* :cite:`TheOmegaPaper`. +.. tacn:: lia + :name: lia + +This tactic offers an alternative to the :tacn:`omega` and :tac:`romega` +tactics. Roughly speaking, the deductive power of lia is the combined deductive +power of :tacn:`ring_simplify` and :tacn:`omega`. However, it solves linear +goals that :tacn:`omega` and :tacn:`romega` do not solve, such as the following +so-called *omega nightmare* :cite:`TheOmegaPaper`. .. coqtop:: in @@ -124,8 +125,8 @@ following so-called *omega nightmare* :cite:`TheOmegaPaper`. 27 <= 11 * x + 13 * y <= 45 -> -10 <= 7 * x - 9 * y <= 4 -> False. -The estimation of the relative efficiency of `lia` *vs* `omega` and `romega` -is under evaluation. +The estimation of the relative efficiency of :tacn:`lia` *vs* :tacn:`omega` and +:tacn:`romega` is under evaluation. High level view of `lia` ~~~~~~~~~~~~~~~~~~~~~~~~ @@ -182,12 +183,13 @@ Our current oracle tries to find an expression :math:`e` with a small range with an equation :math:`e = i` for :math:`i \in [c_1,c_2]` and recursively search for a proof. -.. _nra: - `nra`: a proof procedure for non-linear arithmetic -------------------------------------------------- -The `nra` tactic is an *experimental* proof procedure for non-linear +.. tacn:: nra + :name: nra + +This tactic is an *experimental* proof procedure for non-linear arithmetic. The tactic performs a limited amount of non-linear reasoning before running the linear prover of `lra`. This pre-processing does the following: @@ -202,21 +204,23 @@ does the following: After this pre-processing, the linear prover of `lra` searches for a proof by abstracting monomials by variables. -.. _nia: - `nia`: a proof procedure for non-linear integer arithmetic ---------------------------------------------------------- -The `nia` tactic is a proof procedure for non-linear integer arithmetic. +.. tacn:: nia + :name: nia + +This tactic is a proof procedure for non-linear integer arithmetic. It performs a pre-processing similar to `nra`. The obtained goal is solved using the linear integer prover `lia`. -.. _psatz: - `psatz`: a proof procedure for non-linear arithmetic ---------------------------------------------------- -The `psatz` tactic explores the :math:`\mathit{Cone}` by increasing degrees – hence the +.. tacn:: psatz + :name: psatz + +This tactic explores the :math:`\mathit{Cone}` by increasing degrees – hence the depth parameter :math:`n`. In theory, such a proof search is complete – if the goal is provable the search eventually stops. Unfortunately, the external oracle is using numeric (approximate) optimization techniques diff --git a/doc/sphinx/addendum/program.rst b/doc/sphinx/addendum/program.rst index 1c3fdeb430..be30d1bc4a 100644 --- a/doc/sphinx/addendum/program.rst +++ b/doc/sphinx/addendum/program.rst @@ -151,7 +151,7 @@ Program Definition obligations. Once solved using the commands shown below, it binds the final |Coq| term to the name ``ident`` in the environment. - .. exn:: ident already exists + .. exn:: @ident already exists (Program Definition) .. cmdv:: Program Definition @ident : @type := @term @@ -276,6 +276,7 @@ obligations (e.g. when defining mutually recursive blocks). The optional tactic is replaced by the default one if not specified. .. cmd:: {? Local|Global} Obligation Tactic := @tactic + :name: Obligation Tactic Sets the default obligation solving tactic applied to all obligations automatically, whether to solve them or when starting to prove one, diff --git a/doc/sphinx/addendum/type-classes.rst b/doc/sphinx/addendum/type-classes.rst index 8861cac8af..3e95bd8c45 100644 --- a/doc/sphinx/addendum/type-classes.rst +++ b/doc/sphinx/addendum/type-classes.rst @@ -314,28 +314,25 @@ optional priority can be declared, 0 being the highest priority as for auto hints. If the priority is not specified, it defaults to the number of non-dependent binders of the instance. -Variants: - - -.. cmd:: Instance ident {? @binders} : forall {? @binders}, Class t1 … tn [| priority] := @term +..cmdv:: Instance @ident {? @binders} : forall {? @binders}, Class t1 … tn [| priority] := @term This syntax is used for declaration of singleton class instances or for directly giving an explicit term of type ``forall binders, Class t1 … tn``. One need not even mention the unique field name for singleton classes. -.. cmd:: Global Instance +..cmdv:: Global Instance One can use the ``Global`` modifier on instances declared in a section so that their generalization is automatically redeclared after the section is closed. -.. cmd:: Program Instance +..cmdv:: Program Instance Switches the type-checking to Program (chapter :ref:`programs`) and uses the obligation mechanism to manage missing fields. -.. cmd:: Declare Instance +..cmdv:: Declare Instance In a Module Type, this command states that a corresponding concrete instance should exist in any implementation of thisModule Type. This @@ -370,14 +367,10 @@ Context Declares variables according to the given binding context, which might use :ref:`implicit-generalization`. +.. tacn:: typeclasses eauto -.. _typeclasses-eauto: - -``typeclasses eauto`` -~~~~~~~~~~~~~~~~~~~~~ - -The ``typeclasses eauto`` tactic uses a different resolution engine than -eauto and auto. The main differences are the following: +This tactic uses a different resolution engine than :tacn:`eauto` and +:tacn:`auto`. The main differences are the following: + Contrary to ``eauto`` and ``auto``, the resolution is done entirely in the new proof engine (as of Coq v8.6), meaning that backtracking is @@ -428,118 +421,114 @@ Variants: typeclass subgoals the same as other subgoals (no shelving of non-typeclass goals in particular). -.. _autoapply: - -``autoapply term with ident`` -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. tacn:: autoapply @term with @ident + :name: autoapply -The tactic autoapply applies a term using the transparency information -of the hint database ident, and does *no* typeclass resolution. This can -be used in ``Hint Extern``’s for typeclass instances (in the hint -database ``typeclass_instances``) to allow backtracking on the typeclass -subgoals created by the lemma application, rather than doing type class -resolution locally at the hint application time. + The tactic autoapply applies a term using the transparency information + of the hint database ident, and does *no* typeclass resolution. This can + be used in :cmd:`Hint Extern`’s for typeclass instances (in the hint + database ``typeclass_instances``) to allow backtracking on the typeclass + subgoals created by the lemma application, rather than doing type class + resolution locally at the hint application time. .. _TypeclassesTransparent: Typeclasses Transparent, Typclasses Opaque ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -.. cmd:: Typeclasses { Transparent | Opaque } {+ @ident} +.. cmd:: Typeclasses Transparent {+ @ident} - This commands defines the transparency of the given identifiers - during type class resolution. It is useful when some constants - prevent some unifications and make resolution fail. It is also useful - to declare constants which should never be unfolded during - proof-search, like fixpoints or anything which does not look like an - abbreviation. This can additionally speed up proof search as the - typeclass map can be indexed by such rigid constants (see - :ref:`thehintsdatabasesforautoandeauto`). By default, all constants - and local variables are considered transparent. One should take care - not to make opaque any constant that is used to abbreviate a type, - like: + This command defines makes the identifiers transparent during type class + resolution. -:: + .. cmdv:: Typeclasses Opaque {+ @ident} + :name: Typeclasses Opaque + + Make the identifiers opaque for typeclass search. It is useful when some + constants prevent some unifications and make resolution fail. It is also + useful to declare constants which should never be unfolded during + proof-search, like fixpoints or anything which does not look like an + abbreviation. This can additionally speed up proof search as the typeclass + map can be indexed by such rigid constants (see + :ref:`thehintsdatabasesforautoandeauto`). + + By default, all constants and local variables are considered transparent. One + should take care not to make opaque any constant that is used to abbreviate a + type, like: - relation A := A -> A -> Prop. + :: -This is equivalent to ``Hint Transparent, Opaque ident : typeclass_instances``. + relation A := A -> A -> Prop. + This is equivalent to ``Hint Transparent, Opaque ident : typeclass_instances``. -Set Typeclasses Dependency Order -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -This option (on by default since 8.6) respects the dependency order -between subgoals, meaning that subgoals which are depended on by other -subgoals come first, while the non-dependent subgoals were put before -the dependent ones previously (Coq v8.5 and below). This can result in -quite different performance behaviors of proof search. +.. opt:: Typeclasses Dependency Order + This option (on by default since 8.6) respects the dependency order + between subgoals, meaning that subgoals which are depended on by other + subgoals come first, while the non-dependent subgoals were put before + the dependent ones previously (Coq v8.5 and below). This can result in + quite different performance behaviors of proof search. -Set Typeclasses Filtered Unification -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -This option, available since Coq 8.6 and off by default, switches the -hint application procedure to a filter-then-unify strategy. To apply a -hint, we first check that the goal *matches* syntactically the -inferred or specified pattern of the hint, and only then try to -*unify* the goal with the conclusion of the hint. This can drastically -improve performance by calling unification less often, matching -syntactic patterns being very quick. This also provides more control -on the triggering of instances. For example, forcing a constant to -explicitely appear in the pattern will make it never apply on a goal -where there is a hole in that place. +.. opt:: Typeclasses Filtered Unification + This option, available since Coq 8.6 and off by default, switches the + hint application procedure to a filter-then-unify strategy. To apply a + hint, we first check that the goal *matches* syntactically the + inferred or specified pattern of the hint, and only then try to + *unify* the goal with the conclusion of the hint. This can drastically + improve performance by calling unification less often, matching + syntactic patterns being very quick. This also provides more control + on the triggering of instances. For example, forcing a constant to + explicitely appear in the pattern will make it never apply on a goal + where there is a hole in that place. -Set Typeclasses Limit Intros -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. opt:: Typeclasses Limit Intros -This option (on by default) controls the ability to apply hints while -avoiding (functional) eta-expansions in the generated proof term. It -does so by allowing hints that conclude in a product to apply to a -goal with a matching product directly, avoiding an introduction. -*Warning:* this can be expensive as it requires rebuilding hint -clauses dynamically, and does not benefit from the invertibility -status of the product introduction rule, resulting in potentially more -expensive proof-search (i.e. more useless backtracking). + This option (on by default) controls the ability to apply hints while + avoiding (functional) eta-expansions in the generated proof term. It + does so by allowing hints that conclude in a product to apply to a + goal with a matching product directly, avoiding an introduction. + *Warning:* this can be expensive as it requires rebuilding hint + clauses dynamically, and does not benefit from the invertibility + status of the product introduction rule, resulting in potentially more + expensive proof-search (i.e. more useless backtracking). -Set Typeclass Resolution For Conversion -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. opt:: Typeclass Resolution For Conversion -This option (on by default) controls the use of typeclass resolution -when a unification problem cannot be solved during elaboration/type- -inference. With this option on, when a unification fails, typeclass -resolution is tried before launching unification once again. + This option (on by default) controls the use of typeclass resolution + when a unification problem cannot be solved during elaboration/type- + inference. With this option on, when a unification fails, typeclass + resolution is tried before launching unification once again. -Set Typeclasses Strict Resolution -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. opt:: Typeclasses Strict Resolution -Typeclass declarations introduced when this option is set have a -stricter resolution behavior (the option is off by default). When -looking for unifications of a goal with an instance of this class, we -“freeze” all the existentials appearing in the goals, meaning that -they are considered rigid during unification and cannot be -instantiated. + Typeclass declarations introduced when this option is set have a + stricter resolution behavior (the option is off by default). When + looking for unifications of a goal with an instance of this class, we + “freeze” all the existentials appearing in the goals, meaning that + they are considered rigid during unification and cannot be + instantiated. -Set Typeclasses Unique Solutions -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. opt:: Typeclasses Unique Solutions -When a typeclass resolution is launched we ensure that it has a single -solution or fail. This ensures that the resolution is canonical, but -can make proof search much more expensive. + When a typeclass resolution is launched we ensure that it has a single + solution or fail. This ensures that the resolution is canonical, but + can make proof search much more expensive. -Set Typeclasses Unique Instances -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. opt:: Typeclasses Unique Instances -Typeclass declarations introduced when this option is set have a more -efficient resolution behavior (the option is off by default). When a -solution to the typeclass goal of this class is found, we never -backtrack on it, assuming that it is canonical. + Typeclass declarations introduced when this option is set have a more + efficient resolution behavior (the option is off by default). When a + solution to the typeclass goal of this class is found, we never + backtrack on it, assuming that it is canonical. Typeclasses eauto `:=` @@ -562,7 +551,7 @@ Typeclasses eauto `:=` Set Typeclasses Debug ~~~~~~~~~~~~~~~~~~~~~ -.. cmd:: Set Typeclasses Debug {? Verbosity @num} +.. opt:: Typeclasses Debug {? Verbosity @num} These options allow to see the resolution steps of typeclasses that are performed during search. The ``Debug`` option is synonymous to ``Debug @@ -570,11 +559,10 @@ Verbosity 1``, and ``Debug Verbosity 2`` provides more information (tried tactics, shelving of goals, etc…). -Set Refine Instance Mode -~~~~~~~~~~~~~~~~~~~~~~~~ +.. opt:: Refine Instance Mode -The option Refine Instance Mode allows to switch the behavior of -instance declarations made through the Instance command. +This options allows to switch the behavior of instance declarations made through +the Instance command. + When it is on (the default), instances that have unsolved holes in their proof-term silently open the proof mode with the remaining diff --git a/doc/sphinx/biblio.bib b/doc/sphinx/biblio.bib index ef50923c72..97231c9ecf 100644 --- a/doc/sphinx/biblio.bib +++ b/doc/sphinx/biblio.bib @@ -790,8 +790,7 @@ Matching and Term Rewriting}, @TechReport{Leroy90, author = {X. Leroy}, - title = {The {ZINC} experiment: an economical implementation -of the {ML} language}, + title = {The {ZINC} experiment: an economical implementation of the {ML} language}, institution = {INRIA}, number = {117}, year = {1990} diff --git a/doc/sphinx/credits.rst b/doc/sphinx/credits.rst index f3d9f57b42..a756597986 100644 --- a/doc/sphinx/credits.rst +++ b/doc/sphinx/credits.rst @@ -1373,17 +1373,16 @@ The OPAM repository for |Coq| packages has been maintained by Guillaume Melquiond, Matthieu Sozeau, Enrico Tassi with contributions from many users. A list of packages is available at https://coq.inria.fr/opam/www. -The 40 contributors for this version are Yves Bertot, Joachim -Breitner, Tej Chajed, Arthur Charguéraud, Jacques-Pascal Deplaix, Maxime -Dénès, Jim Fehrle, Yannick Forster, Gaëtan Gilbert, Jason Gross, Samuel -Gruetter, Thomas Hebb, Hugo Herbelin, Jasper Hugunin, Emilio Jesus -Gallego Arias, Ralf Jung, Johannes Kloos, Matej Košík, Robbert Krebbers, -Tony Beta Lambda, Vincent Laporte, Pierre Letouzey, Farzon Lotfi, -Cyprien Mangin, Guillaume Melquiond, Raphaël Monat, Carl Patenaude -Poulin, Pierre-Marie Pédrot, Matthew Ryan, Matt Quinn, Sigurd Schneider, -Bernhard Schommer, Matthieu Sozeau, Arnaud Spiwack, Paul Steckler, -Enrico Tassi, Anton Trunov, Martin Vassor, Vadim Zaliva and Théo -Zimmermann. +The 44 contributors for this version are Yves Bertot, Joachim Breitner, Tej +Chajed, Arthur Charguéraud, Jacques-Pascal Deplaix, Maxime Dénès, Jim Fehrle, +Julien Forest, Yannick Forster, Gaëtan Gilbert, Jason Gross, Samuel Gruetter, +Thomas Hebb, Hugo Herbelin, Jasper Hugunin, Emilio Jesus Gallego Arias, Ralf +Jung, Johannes Kloos, Matej Košík, Robbert Krebbers, Tony Beta Lambda, Vincent +Laporte, Peter LeFanu Lumsdaine, Pierre Letouzey, Farzon Lotfi, Cyprien Mangin, +Guillaume Melquiond, Raphaël Monat, Carl Patenaude Poulin, Pierre-Marie Pédrot, +Clément Pit-Claudel, Matthew Ryan, Matt Quinn, Sigurd Schneider, Bernhard +Schommer, Michael Soegtrop, Matthieu Sozeau, Arnaud Spiwack, Paul Steckler, +Enrico Tassi, Anton Trunov, Martin Vassor, Vadim Zaliva and Théo Zimmermann. Version 8.8 is the third release of |Coq| developed on a time-based development cycle. Its development spanned 6 months from the release of diff --git a/doc/sphinx/language/gallina-extensions.rst b/doc/sphinx/language/gallina-extensions.rst index f474eade71..a93e9b156d 100644 --- a/doc/sphinx/language/gallina-extensions.rst +++ b/doc/sphinx/language/gallina-extensions.rst @@ -148,7 +148,7 @@ available: It can be activated for printing with -.. cmd:: Set Printing Projections. +.. opt:: Printing Projections .. example:: @@ -249,7 +249,7 @@ printing of pattern-matching over primitive records. Primitive Record Types ++++++++++++++++++++++ -When the ``Set Primitive Projections`` option is on, definitions of +When the :opt:`Primitive Projections` option is on, definitions of record types change meaning. When a type is declared with primitive projections, its :g:`match` construct is disabled (see :ref:`primitive_projections` though). To eliminate the (co-)inductive type, one must use its defined primitive projections. @@ -328,7 +328,7 @@ patterns are allowed, as in ML-like languages. The extension just acts as a macro that is expanded during parsing into a sequence of match on simple patterns. Especially, a construction defined using the extended match is generally printed -under its expanded form (see ``Set Printing Matching`` in :ref:`controlling-match-pp`). +under its expanded form (see :opt:`Printing Matching`). See also: :ref:`extendedpatternmatching`. @@ -874,7 +874,7 @@ In the syntax of module application, the ! prefix indicates that any Starts an interactive module satisfying each `module_type`. - .. cmdv:: Module @ident {* @module_binding} <: {+<; @module_type }. + .. cmdv:: Module @ident {* @module_binding} <: {+<: @module_type }. Starts an interactive functor with parameters given by the list of `module_binding`. The output module type is verified against each `module_type`. @@ -955,7 +955,8 @@ Reserved commands inside an interactive module type: is a shortcut for the command ``Include`` `module` for each `module`. -.. cmd:: @assumption_keyword Inline @assums. +.. cmd:: @assumption_keyword Inline @assums + :name: Inline The instance of this assumption will be automatically expanded at functor application, except when this functor application is prefixed by a ``!`` annotation. @@ -1435,7 +1436,9 @@ For instance, the first argument of in module ``List.v`` is strict because :g:`list` is an inductive type and :g:`A` will always be inferable from the type :g:`list A` of the third argument of -:g:`cons`. On the contrary, the second argument of a term of type +:g:`cons`. Also, the first argument of :g:`cons` is strict with respect to the second one, +since the first argument is exactly the type of the second argument. +On the contrary, the second argument of a term of type :: forall P:nat->Prop, forall n:nat, P n -> ex nat P @@ -1506,10 +1509,10 @@ inserted. In the second case, the function is considered to be implicitly applied to the implicit arguments it is waiting for: one says that the implicit argument is maximally inserted. -Each implicit argument can be declared to have to be inserted -maximally or non maximally. This can be governed argument per argument -by the command ``Implicit Arguments`` (see Section :ref:`declare-implicit-args`) or globally by the -command ``Set Maximal Implicit Insertion`` (see Section :ref:`controlling-insertion-implicit-args`). +Each implicit argument can be declared to have to be inserted maximally or non +maximally. This can be governed argument per argument by the command ``Implicit +Arguments`` (see Section :ref:`declare-implicit-args`) or globally by the +:opt:`Maximal Implicit Insertion` option. See also :ref:`displaying-implicit-args`. @@ -1882,7 +1885,7 @@ arguments that are not detected as strict implicit arguments. This “defensive” mode can quickly make the display cumbersome so this can be deactivated by turning this option off. -See also: ``Set Printing All`` in :ref:`printing_constructions_full`. +See also: :opt:`Printing All`. Interaction with subtyping ~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -2134,9 +2137,9 @@ sensitive to the implicit arguments). Turning this option on deactivates all high-level printing features such as coercions, implicit arguments, returned type of pattern-matching, notations and various syntactic sugar for pattern-matching or record projections. -Otherwise said, ``Set Printing All`` includes the effects of the commands -``Set Printing Implicit``, ``Set Printing Coercions``, ``Set Printing Synth``, -``Unset Printing Projections``, and ``Unset Printing Notations``. To reactivate +Otherwise said, :opt:`Printing All` includes the effects of the options +:opt:`Printing Implicit`, :opt:`Printing Coercions`, :opt:`Printing Synth`, +:opt:`Printing Projections`, and :opt:`Printing Notations`. To reactivate the high-level printing features, use the command ``Unset Printing All``. .. _printing-universes: diff --git a/doc/sphinx/language/gallina-specification-language.rst b/doc/sphinx/language/gallina-specification-language.rst index 246f45b3e7..a9c4dd7588 100644 --- a/doc/sphinx/language/gallina-specification-language.rst +++ b/doc/sphinx/language/gallina-specification-language.rst @@ -557,9 +557,10 @@ has type :token:`type`. the global context. The fact asserted by *term* is thus assumed as a postulate. -.. exn:: @ident already exists +.. exn:: @ident already exists (Axiom) .. cmdv:: Parameter @ident : @term. + :name: Parameter Is equivalent to ``Axiom`` :token:`ident` : :token:`term` @@ -582,6 +583,7 @@ has type :token:`type`. qualified name to refer to them. .. cmdv:: Conjecture @ident : @term + :name: Conjecture Is equivalent to ``Axiom`` :token:`ident` : :token:`term`. @@ -594,7 +596,7 @@ will be unknown and every object using this variable will be explicitly parametrized (the variable is *discharged*). Using the ``Variable`` command out of any section is equivalent to using ``Local Parameter``. -.. exn:: @ident already exists +.. exn:: @ident already exists (Variable) .. cmdv:: Variable {+ @ident } : @term. @@ -607,6 +609,7 @@ of any section is equivalent to using ``Local Parameter``. .. cmdv:: Variables {+ ( {+ @ident } : @term) }. .. cmdv:: Hypothesis {+ ( {+ @ident } : @term) }. + :name: Hypothesis .. cmdv:: Hypotheses {+ ( {+ @ident } : @term) }. @@ -643,7 +646,7 @@ Section :ref:`typing-rules`. This command binds :token:`term` to the name :token:`ident` in the environment, provided that :token:`term` is well-typed. -.. exn:: @ident already exists +.. exn:: @ident already exists (Definition) .. cmdv:: Definition @ident : @term := @term. @@ -687,7 +690,7 @@ prefixed by the let-in definition ``let`` :token:`ident` ``:=`` :token:`term` ``in``. Using the ``Let`` command out of any section is equivalent to using ``Local Definition``. -.. exn:: @ident already exists +.. exn:: @ident already exists (Let) .. cmdv:: Let @ident : @term := @term. @@ -1245,20 +1248,25 @@ the theorem is bound to the name :token:`ident` in the environment. .. exn:: The term @term has type @type which should be Set, Prop or Type -.. exn:: @ident already exists +.. exn:: @ident already exists (Theorem) The name you provided is already defined. You have then to choose another name. .. cmdv:: Lemma @ident : @type. + :name: Lemma .. cmdv:: Remark @ident : @type. + :name: Remark .. cmdv:: Fact @ident : @type. + :name: Fact .. cmdv:: Corollary @ident : @type. + :name: Corollary .. cmdv:: Proposition @ident : @type. + :name: Proposition These commands are synonyms of ``Theorem`` :token:`ident` : :token:`type`. @@ -1273,16 +1281,16 @@ the theorem is bound to the name :token:`ident` in the environment. coinduction has to be done is assumed to be non ambiguous and is guessed by the system. - Like in a ``Fixpoint`` or ``CoFixpoint`` definition, the induction hypotheses - have to be used on *structurally smaller* arguments (for a ``Fixpoint``) or - be *guarded by a constructor* (for a ``CoFixpoint``). The verification that + Like in a :cmd:`Fixpoint` or :cmd:`CoFixpoint` definition, the induction hypotheses + have to be used on *structurally smaller* arguments (for a :cmd:`Fixpoint`) or + be *guarded by a constructor* (for a :cmd:`CoFixpoint`). The verification that recursive proof arguments are correct is done only at the time of registering the lemma in the environment. To know if the use of induction hypotheses is correct at some time of the interactive development of a proof, use the command :cmd:`Guarded`. - The command can be used also with ``Lemma``, ``Remark``, etc. instead of - ``Theorem``. + The command can be used also with :cmd:`Lemma`, :cmd:`Remark`, etc. instead of + :cmd:`Theorem`. .. cmdv:: Definition @ident : @type. @@ -1313,16 +1321,20 @@ the theorem is bound to the name :token:`ident` in the environment. This generalizes the syntax of CoFixpoint so that one or more bodies can be defined interactively using the proof editing mode. -.. cmd:: Proof. … Qed. +.. cmd:: Proof -A proof starts by the keyword Proof. Then Coq enters the proof editing mode -until the proof is completed. The proof editing mode essentially contains -tactics that are described in chapter :ref:`Tactics`. Besides tactics, there are -commands to manage the proof editing mode. They are described in Chapter -:ref:`proofhandling`. When the proof is completed it should be validated and -put in the environment using the keyword Qed. + A proof starts by the keyword Proof. Then Coq enters the proof editing mode + until the proof is completed. The proof editing mode essentially contains + tactics that are described in chapter :ref:`Tactics`. Besides tactics, there + are commands to manage the proof editing mode. They are described in Chapter + :ref:`proofhandling`. -.. exn:: @ident already exists +.. cmd:: Qed + + When the proof is completed it should be validated and put in the environment + using the keyword Qed. + +.. exn:: @ident already exists (Qed) .. note:: @@ -1341,14 +1353,16 @@ put in the environment using the keyword Qed. realizing some form of *proof-irrelevance*. To be able to unfold a proof, the proof should be ended by Defined (see below). -.. cmdv:: Proof. … Defined. +.. cmdv:: Defined + :name: Defined - Same as ``Proof. … Qed.`` but the proof is then declared transparent, - which means that its content can be explicitly used for - type-checking and that it can be unfolded in conversion tactics - (see :ref:`performingcomputations`, :cmd:`Opaque`, :cmd:`Transparent`). + Same as :cmd:`Qed` but the proof is then declared transparent, which means + that its content can be explicitly used for type-checking and that it can be + unfolded in conversion tactics (see :ref:`performingcomputations`, + :cmd:`Opaque`, :cmd:`Transparent`). -.. cmdv:: Proof. … Admitted. +.. cmdv:: Admitted. + :name: Admitted Turns the current asserted statement into an axiom and exits the proof mode. diff --git a/doc/sphinx/proof-engine/ltac.rst b/doc/sphinx/proof-engine/ltac.rst index 247d5d899c..7ab11889f5 100644 --- a/doc/sphinx/proof-engine/ltac.rst +++ b/doc/sphinx/proof-engine/ltac.rst @@ -178,6 +178,7 @@ Sequence A sequence is an expression of the following form: .. tacn:: @expr ; @expr + :name: ; The expression :n:`@expr__1` is evaluated to :n:`v__1`, which must be a tactic value. The tactic :n:`v__1` is applied to the current goal, @@ -193,6 +194,7 @@ Different tactics can be applied to the different goals using the following form: .. tacn:: [> {*| @expr }] + :name: [> ... | ... | ... ] (dispatch) The expressions :n:`@expr__i` are evaluated to :n:`v__i`, for i=0,...,n and all have to be tactics. The :n:`v__i` is applied to the @@ -240,6 +242,7 @@ We can restrict the application of a tactic to a subset of the currently focused goals with: .. tacn:: @toplevel_selector : @expr + :name: ... : ... (goal selector) We can also use selectors as a tactical, which allows to use them nested in a tactic expression, by using the keyword ``only``: @@ -269,6 +272,12 @@ focused goals with: In this variant, :n:`@expr` is applied to all focused goals. ``all:`` can only be used at the toplevel of a tactic expression. + .. tacv:: !: @expr + + In this variant, if exactly one goal is focused :n:`expr` is + applied to it. Otherwise the tactical fails. ``!:`` can only be + used at the toplevel of a tactic expression. + .. tacv:: par: @expr In this variant, :n:`@expr` is applied to all focused goals in parallel. @@ -290,6 +299,7 @@ For loop There is a for loop that repeats a tactic :token:`num` times: .. tacn:: do @num @expr + :name: do :n:`@expr` is evaluated to ``v`` which must be a tactic value. This tactic value ``v`` is applied :token:`num` times. Supposing :token:`num` > 1, after the @@ -303,6 +313,7 @@ Repeat loop We have a repeat loop with: .. tacn:: repeat @expr + :name: repeat :n:`@expr` is evaluated to ``v``. If ``v`` denotes a tactic, this tactic is applied to each focused goal independently. If the application succeeds, the @@ -316,6 +327,7 @@ Error catching We can catch the tactic errors with: .. tacn:: try @expr + :name: try :n:`@expr` is evaluated to ``v`` which must be a tactic value. The tactic value ``v`` is applied to each focused goal independently. If the application of @@ -329,6 +341,7 @@ Detecting progress We can check if a tactic made progress with: .. tacn:: progress expr + :name: progress :n:`@expr` is evaluated to v which must be a tactic value. The tactic value ``v`` is applied to each focued subgoal independently. If the application of ``v`` @@ -343,6 +356,7 @@ Backtracking branching We can branch with the following structure: .. tacn:: @expr__1 + @expr__2 + :name: + (backtracking branching) :n:`@expr__1` and :n:`@expr__2` are evaluated respectively to :n:`v__1` and :n:`v__2` which must be tactic values. The tactic value :n:`v__1` is applied to @@ -365,6 +379,7 @@ restrict to a local, left biased, branching and consider the first tactic to work (i.e. which does not fail) among a panel of tactics: .. tacn:: first [{*| @expr}] + :name: first The :n:`@expr__i` are evaluated to :n:`v__i` and :n:`v__i` must be tactic values, for i=1,...,n. Supposing n>1, it applies, in each focused @@ -396,6 +411,7 @@ Yet another way of branching without backtracking is the following structure: .. tacn:: @expr__1 || @expr__2 + :name: || (left-biased branching) :n:`@expr__1` and :n:`@expr__2` are evaluated respectively to :n:`v__1` and :n:`v__2` which must be tactic values. The tactic value :n:`v__1` is @@ -410,6 +426,7 @@ Generalized biased branching The tactic .. tacn:: tryif @expr__1 then @expr__2 else @expr__3 + :name: tryif is a generalization of the biased-branching tactics above. The expression :n:`@expr__1` is evaluated to :n:`v__1`, which is then @@ -430,6 +447,7 @@ Another way of restricting backtracking is to restrict a tactic to a single success *a posteriori*: .. tacn:: once @expr + :name: once :n:`@expr` is evaluated to ``v`` which must be a tactic value. The tactic value ``v`` is applied but only its first success is used. If ``v`` fails, @@ -443,6 +461,7 @@ Coq provides an experimental way to check that a tactic has *exactly one* success: .. tacn:: exactly_once @expr + :name: exactly_once :n:`@expr` is evaluated to ``v`` which must be a tactic value. The tactic value ``v`` is applied if it has at most one success. If ``v`` fails, @@ -467,6 +486,7 @@ Checking the failure Coq provides a derived tactic to check that a tactic *fails*: .. tacn:: assert_fails @expr + :name: assert_fails This behaves like :n:`tryif @expr then fail 0 tac "succeeds" else idtac`. @@ -477,6 +497,7 @@ Coq provides a derived tactic to check that a tactic has *at least one* success: .. tacn:: assert_succeeds @expr + :name: assert_suceeds This behaves like :n:`tryif (assert_fails tac) then fail 0 tac "fails" else idtac`. @@ -488,6 +509,7 @@ We may consider the first to solve (i.e. which generates no subgoal) among a panel of tactics: .. tacn:: solve [{*| @expr}] + :name: solve The :n:`@expr__i` are evaluated to :n:`v__i` and :n:`v__i` must be tactic values, for i=1,...,n. Supposing n>1, it applies :n:`v__1` to @@ -508,6 +530,7 @@ The constant :n:`idtac` is the identity tactic: it leaves any goal unchanged but it appears in the proof script. .. tacn:: idtac {* message_token} + :name: idtac This prints the given tokens. Strings and integers are printed literally. If a (term) variable is given, its contents are printed. @@ -516,6 +539,7 @@ Failing ~~~~~~~ .. tacn:: fail + :name: fail This is the always-failing tactic: it does not solve any goal. It is useful for defining other tacticals since it can be caught by @@ -543,6 +567,7 @@ Failing This is a combination of the previous variants. .. tacv:: gfail + :name: gfail This variant fails even if there are no goals left. @@ -565,6 +590,7 @@ We can force a tactic to stop if it has not finished after a certain amount of time: .. tacn:: timeout @num @expr + :name: timeout :n:`@expr` is evaluated to ``v`` which must be a tactic value. The tactic value ``v`` is applied normally, except that it is interrupted after :n:`@num` seconds @@ -586,6 +612,7 @@ Timing a tactic A tactic execution can be timed: .. tacn:: time @string @expr + :name: time evaluates :n:`@expr` and displays the time the tactic expression ran, whether it fails or successes. In case of several successes, the time for each successive @@ -600,6 +627,7 @@ Tactic expressions that produce terms can be timed with the experimental tactic .. tacn:: time_constr expr + :name: time_constr which evaluates :n:`@expr ()` and displays the time the tactic expression evaluated, assuming successful evaluation. Time is in seconds and is @@ -610,10 +638,12 @@ tactic implemented using the tactics .. tacn:: restart_timer @string + :name: restart_timer and .. tacn:: finish_timing {? @string} @string + :name: finish_timing which (re)set and display an optionally named timer, respectively. The parenthesized string argument to :n:`finish_timing` is also optional, and @@ -951,6 +981,7 @@ Testing boolean expressions ~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. tacn:: guard @test + :name: guard The :tacn:`guard` tactic tests a boolean expression, and fails if the expression evaluates to false. If the expression evaluates to true, it succeeds @@ -976,6 +1007,7 @@ Proving a subgoal as a separate lemma ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. tacn:: abstract @expr + :name: abstract From the outside, :n:`abstract @expr` is the same as :n:`solve @expr`. Internally it saves an auxiliary lemma called ``ident_subproofn`` where @@ -1000,6 +1032,7 @@ Proving a subgoal as a separate lemma don’t play well with asynchronous proofs. .. tacv:: transparent_abstract @expr + :name: transparent_abstract Save the subproof in a transparent lemma rather than an opaque one. @@ -1220,28 +1253,33 @@ performance bug. Unset Ltac Profiling. .. tacn:: start ltac profiling + :name: start ltac profiling This tactic behaves like :tacn:`idtac` but enables the profiler. .. tacn:: stop ltac profiling + :name: stop ltac profiling Similarly to :tacn:`start ltac profiling`, this tactic behaves like :tacn:`idtac`. Together, they allow you to exclude parts of a proof script from profiling. .. tacn:: reset ltac profile + :name: reset ltac profile This tactic behaves like the corresponding vernacular command and allow displaying and resetting the profile from tactic scripts for benchmarking purposes. .. tacn:: show ltac profile + :name: show ltac profile This tactic behaves like the corresponding vernacular command and allow displaying and resetting the profile from tactic scripts for benchmarking purposes. .. tacn:: show ltac profile @string + :name: show ltac profile This tactic behaves like the corresponding vernacular command and allow displaying and resetting the profile from tactic scripts for @@ -1261,6 +1299,7 @@ Run-time optimization tactic ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ .. tacn:: optimize_heap + :name: optimize_heap This tactic behaves like :n:`idtac`, except that running it compacts the heap in the OCaml run-time system. It is analogous to the Vernacular diff --git a/doc/sphinx/proof-engine/proof-handling.rst b/doc/sphinx/proof-engine/proof-handling.rst index a77b127ebe..86c94bab36 100644 --- a/doc/sphinx/proof-engine/proof-handling.rst +++ b/doc/sphinx/proof-engine/proof-handling.rst @@ -58,13 +58,14 @@ statement is eventually completed and validated, the statement is then bound to the name ``Unnamed_thm`` (or a variant of this name not already used for another statement). -.. cmd:: Qed. +.. cmd:: Qed + :name: Qed (interactive proof) This command is available in interactive editing proof mode when the proof is completed. Then ``Qed`` extracts a proof term from the proof script, switches back to Coq top-level and attaches the extracted proof term to the declared name of the original goal. This name is -added to the environment as an ``Opaque`` constant. +added to the environment as an opaque constant. .. exn:: Attempt to save an incomplete proof @@ -81,6 +82,7 @@ a while when the proof is large. In some exceptional cases one may even incur a memory overflow. .. cmdv:: Defined. + :name: Defined (interactive proof) Defines the proved term as a transparent constant. @@ -91,6 +93,7 @@ command (and the following ones) can only be used if the original goal has been opened using the ``Goal`` command. .. cmd:: Admitted. + :name: Admitted (interactive proof) This command is available in interactive editing proof mode to give up the current proof and declare the initial goal as an axiom. @@ -105,8 +108,8 @@ This command applies in proof editing mode. It is equivalent to That is, you have to give the full proof in one gulp, as a proof term (see Section :ref:`applyingtheorems`). - .. cmdv:: Proof. + :name: Proof (interactive proof) Is a noop which is useful to delimit the sequence of tactic commands which start a proof, after a ``Theorem`` command. It is a good practice to @@ -182,49 +185,51 @@ Proof using options The following options modify the behavior of ``Proof using``. -.. cmdv:: Set Default Proof Using "@expression". +.. opt:: Default Proof Using "@expression". -Use :n:`@expression` as the default ``Proof``` using value. E.g. ``Set Default -Proof Using "a b"``. will complete all ``Proof`` commands not followed by a -using part with using ``a`` ``b``. + Use :n:`@expression` as the default ``Proof``` using value. E.g. ``Set Default + Proof Using "a b"``. will complete all ``Proof`` commands not followed by a + using part with using ``a`` ``b``. -.. cmdv:: Set Suggest Proof Using. +.. opt:: Suggest Proof Using. -When ``Qed`` is performed, suggest a using annotation if the user did not -provide one. + When ``Qed`` is performed, suggest a using annotation if the user did not + provide one. .. _`nameaset`: Name a set of section hypotheses for ``Proof using`` ```````````````````````````````````````````````````` +.. cmd:: Collection @ident := @section_subset_expr + The command ``Collection`` can be used to name a set of section hypotheses, with the purpose of making ``Proof using`` annotations more compact. -.. cmdv:: Collection Some := x y z. +.. cmdv:: Collection Some := x y z Define the collection named "Some" containing ``x``, ``y`` and ``z``. -.. cmdv:: Collection Fewer := Some - z. +.. cmdv:: Collection Fewer := Some - z Define the collection named "Fewer" containing only ``x`` and ``y``. -.. cmdv:: Collection Many := Fewer + Some. -.. cmdv:: Collection Many := Fewer - Some. +.. cmdv:: Collection Many := Fewer + Some +.. cmdv:: Collection Many := Fewer - Some Define the collection named "Many" containing the set union or set difference of "Fewer" and "Some". -.. cmdv:: Collection Many := Fewer - (x y). +.. cmdv:: Collection Many := Fewer - (x y) Define the collection named "Many" containing the set difference of -"Fewer" and the unnamed collection ``x`` ``y``. +"Fewer" and the unnamed collection ``x`` ``y`` .. cmd:: Abort. @@ -288,6 +293,7 @@ backtracks one step. Repeats Undo :n:`@num` times. .. cmdv:: Restart. + :name: Restart This command restores the proof editing process to the original goal. @@ -424,11 +430,11 @@ Set Bullet Behavior The bullet behavior can be controlled by the following commands. -.. opt:: Bullet Behavior "None". +.. opt:: Bullet Behavior "None" This makes bullets inactive. -.. opt:: Bullet Behavior "Strict Subproofs". +.. opt:: Bullet Behavior "Strict Subproofs" This makes bullets active (this is the default behavior). @@ -551,7 +557,7 @@ Controlling the effect of proof editing commands ------------------------------------------------ -.. opt:: Hyps Limit @num. +.. opt:: Hyps Limit @num This option controls the maximum number of hypotheses displayed in goals after the application of a tactic. All the hypotheses remain usable @@ -560,7 +566,7 @@ When unset, it goes back to the default mode which is to print all available hypotheses. -.. opt:: Automatic Introduction. +.. opt:: Automatic Introduction This option controls the way binders are handled in assertion commands such as ``Theorem ident [binders] : form``. When the diff --git a/doc/sphinx/proof-engine/ssreflect-proof-language.rst b/doc/sphinx/proof-engine/ssreflect-proof-language.rst index 074c6f1e28..977a5b8fad 100644 --- a/doc/sphinx/proof-engine/ssreflect-proof-language.rst +++ b/doc/sphinx/proof-engine/ssreflect-proof-language.rst @@ -493,7 +493,10 @@ inferred from the whole context of the goal (see for example section Definitions ~~~~~~~~~~~ -The pose tactic allows to add a defined constant to a proof context. +.. tacn:: pose + :name: pose (ssreflect) + +This tactic allows to add a defined constant to a proof context. |SSR| generalizes this tactic in several ways. In particular, the |SSR| pose tactic supports *open syntax*: the body of the definition does not need surrounding parentheses. For instance: @@ -1349,6 +1352,7 @@ Discharge The general syntax of the discharging tactical ``:`` is: .. tacn:: @tactic {? @ident } : {+ @d_item } {? @clear_switch } + :name: ... : ... (ssreflect) .. prodn:: d_item ::= {? @occ_switch %| @clear_switch } @term @@ -1500,9 +1504,11 @@ side of an equation. The abstract tactic ``````````````````` -The ``abstract`` tactic assigns an ``abstract`` constant previously -introduced with the ``[: name ]`` intro pattern -(see section :ref:`introduction_ssr`). +.. tacn:: abstract: {+ d_item} + :name abstract (ssreflect) + +This tactic assigns an abstract constant previously introduced with the ``[: +name ]`` intro pattern (see section :ref:`introduction_ssr`). In a goal like the following:: @@ -1809,6 +1815,8 @@ of a :token:`d_item` immediately following this ``/`` switch, using the syntax: .. tacv:: case: {+ @d_item } / {+ @d_item } + :name: case (ssreflect) + .. tacv:: elim: {+ @d_item } / {+ @d_item } The :token:`d_item` on the right side of the ``/`` switch are discharged as @@ -2132,7 +2140,7 @@ tactic using the given second tactic, and fails if it does not succeed. Its analogue .. tacn:: @tactic ; first by @tactic - :name: first + :name: first (ssreflect) tries to solve the first subgoal generated by the first tactic using the second given tactic, and fails if it does not succeed. @@ -2212,7 +2220,7 @@ Iteration thanks to the do tactical, whose general syntax is: .. tacn:: do {? @mult } ( @tactic | [ {+| @tactic } ] ) - :name: do + :name: do (ssreflect) where :token:`mult` is a *multiplier*. @@ -2749,12 +2757,9 @@ type classes inference. No inference for ``t``. Unresolved instances are quantified in the (inferred) type of ``t`` and abstracted in ``t``. +.. opt:: SsrHave NoTCResolution -The behavior of |SSR| 1.4 and below (never resolve type classes) -can be restored with the option - -.. cmd:: Set SsrHave NoTCResolution. - + This option restores the behavior of |SSR| 1.4 and below (never resolve type classes). Variants: the suff and wlog tactics ``````````````````````````````````` @@ -3727,6 +3732,7 @@ We provide a special tactic unlock for unfolding such definitions while removing “locks”, e.g., the tactic: .. tacn:: unlock {? @occ_switch } @ident + :name: unlock replaces the occurrence(s) of :token:`ident` coded by the :token:`occ_switch` with the corresponding body. diff --git a/doc/sphinx/proof-engine/tactics.rst b/doc/sphinx/proof-engine/tactics.rst index 08aa7110d1..a3d06ae046 100644 --- a/doc/sphinx/proof-engine/tactics.rst +++ b/doc/sphinx/proof-engine/tactics.rst @@ -51,20 +51,22 @@ specified, the default selector is used. tactic_invocation : toplevel_selector : tactic. : |tactic . -.. cmd:: Set Default Goal Selector @toplevel_selector. +.. opt:: Default Goal Selector @toplevel_selector -After using this command, the default selector – used when no selector -is specified when applying a tactic – is set to the chosen value. The -initial value is 1, hence the tactics are, by default, applied to the -first goal. Using Set Default Goal Selector ‘‘all’’ will make is so -that tactics are, by default, applied to every goal simultaneously. -Then, to apply a tactic tac to the first goal only, you can write -1:tac. Although more selectors are available, only ‘‘all’’ or a single -natural number are valid default goal selectors. + This option controls the default selector, used when no selector is + specified when applying a tactic. The initial value is 1, hence the + tactics are, by default, applied to the first goal. -.. cmd:: Test Default Goal Selector. + Using value ``all`` will make it so that tactics are, by default, + applied to every goal simultaneously. Then, to apply a tactic tac + to the first goal only, you can write ``1:tac``. -This command displays the current default selector. + Using value ``!`` enforces that all tactics are used either on a + single focused goal or with a local selector (’’strict focusing + mode’’). + + Although more selectors are available, only ``all``, ``!`` or a + single natural number are valid default goal selectors. .. _bindingslist: @@ -123,14 +125,12 @@ following syntax: The role of an occurrence clause is to select a set of occurrences of a term in a goal. In the first case, the :n:`@ident {? at {* num}}` parts indicate that -occurrences have to be selected in the hypotheses named :n:`@ident`. If no numbers -are given for hypothesis :n:`@ident`, then all the occurrences of `term` in the -hypothesis are selected. If numbers are given, they refer to occurrences of -`term` when the term is printed using option ``Set Printing All`` (see -:ref:`printing_constructions_full`), counting from left to right. In -particular, occurrences of `term` in implicit arguments (see -:ref:`ImplicitArguments`) or coercions (see :ref:`Coercions`) -are counted. +occurrences have to be selected in the hypotheses named :n:`@ident`. If no +numbers are given for hypothesis :n:`@ident`, then all the occurrences of `term` +in the hypothesis are selected. If numbers are given, they refer to occurrences +of `term` when the term is printed using option :opt:`Printing All`, counting +from left to right. In particular, occurrences of `term` in implicit arguments +(see :ref:`ImplicitArguments`) or coercions (see :ref:`Coercions`) are counted. If a minus sign is given between at and the list of occurrences, it negates the condition so that the clause denotes all the occurrences @@ -175,6 +175,7 @@ term of the goal. Let ``T`` be our goal, let ``p`` be a term of type ``U`` then .. exn:: Not an exact proof. .. tacv:: eexact @term. + :name: eexact This tactic behaves like exact but is able to handle terms and goals with meta-variables. @@ -188,6 +189,7 @@ the goal. If it is the case, the subgoal is proved. Otherwise, it fails. .. exn:: No such assumption. .. tacv:: eassumption + :name: eassumption This tactic behaves like assumption but is able to handle goals with meta-variables. @@ -240,6 +242,7 @@ useful to advanced users. cast around it. .. tacv:: simple refine @term + :name: simple refine This tactic behaves like refine, but it does not shelve any subgoal. It does not perform any beta-reduction either. @@ -250,6 +253,7 @@ useful to advanced users. resolution of typeclasses. .. tacv:: simple notypeclasses refine @term + :name: simple notypeclasses refine This tactic behaves like ``simple refine`` except it performs typechecking without resolution of typeclasses. @@ -320,6 +324,7 @@ instantiate (see :ref:`Existential-Variables`). The instantiation is intended to be found later in the proof. .. tacv:: simple apply @term. + :name: simple apply This behaves like ``apply`` but it reasons modulo conversion only on subterms that contain no variables to instantiate. For instance, the following example @@ -342,11 +347,12 @@ does. .. tacv:: {? simple} apply {+, @term {? with @bindings_list}} .. tacv:: {? simple} eapply {+, @term {? with @bindings_list}} + :name: simple eapply This summarizes the different syntaxes for ``apply`` and ``eapply``. .. tacv:: lapply @term - :name: `lapply + :name: lapply This tactic applies to any goal, say :g:`G`. The argument term has to be well-formed in the current context, its type being reducible to a non-dependent @@ -437,7 +443,7 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. ``forall A, ... -> A``. Excluding this kind of lemma can be avoided by setting the following option: -.. opt:: Set Universal Lemma Under Conjunction. +.. opt:: Universal Lemma Under Conjunction This option, which preserves compatibility with versions of Coq prior to 8.4 is also available for :n:`apply @term in @ident` (see :tacn:`apply ... in`). @@ -522,8 +528,8 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. constructor of :g:`I`, then ``constructor i`` is equivalent to ``intros; apply c``:sub:`i`. -.. exn:: Not an inductive product. -.. exn:: Not enough constructors. +.. exn:: Not an inductive product +.. exn:: Not enough constructors .. tacv:: constructor @@ -541,34 +547,39 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. The terms in the @bindings_list are checked in the context where constructor is executed and not in the context where @apply is executed (the introductions are not taken into account). .. tacv:: split + :name: split This applies only if :g:`I` has a single constructor. It is then equivalent to :n:`constructor 1.`. It is typically used in the case of a conjunction :g:`A` :math:`\wedge` :g:`B`. -.. exn:: Not an inductive goal with 1 constructor. +.. exn:: Not an inductive goal with 1 constructor .. tacv:: exists @val + :name: exists This applies only if :g:`I` has a single constructor. It is then equivalent to :n:`intros; constructor 1 with @bindings_list.` It is typically used in the case of an existential quantification :math:`\exists`:g:`x, P(x).` -.. exn:: Not an inductive goal with 1 constructor. +.. exn:: Not an inductive goal with 1 constructor .. tacv:: exists @bindings_list This iteratively applies :n:`exists @bindings_list`. .. tacv:: left + :name: left + .. tacv:: right + :name: right These tactics apply only if :g:`I` has two constructors, for instance in the case of a disjunction :g:`A` :math:`\vee` :g:`B`. Then, they are respectively equivalent to ``constructor 1`` and ``constructor 2``. -.. exn:: Not an inductive goal with 2 constructors. +.. exn:: Not an inductive goal with 2 constructors .. tacv:: left with @bindings_list .. tacv:: right with @bindings_list @@ -579,15 +590,25 @@ sequence ``cut B. 2:apply H.`` where ``cut`` is described below. for the appropriate ``i``. .. tacv:: econstructor + :name: econstructor + .. tacv:: eexists + :name: eexists + .. tacv:: esplit + :name: esplit + .. tacv:: eleft + :name: eleft + .. tacv:: eright + :name: eright - These tactics and their variants behave like ``constructor``, ``exists``, - ``split``, ``left``, ``right`` and their variants but they introduce - existential variables instead of failing when the instantiation of a - variable cannot be found (cf. :tacn:`eapply` and :tacn:`apply`). + These tactics and their variants behave like :tacn:`constructor`, + :tacn:`exists`, :tacn:`split`, :tacn:`left`, :tacn:`right` and their variants + but they introduce existential variables instead of failing when the + instantiation of a variable cannot be found (cf. :tacn:`eapply` and + :tacn:`apply`). .. _managingthelocalcontext: @@ -618,7 +639,7 @@ the tactic ``intro`` applies the tactic ``hnf`` until the tactic ``intro`` can be applied or the goal is not head-reducible. .. exn:: No product even after head-reduction. -.. exn:: ident is already used. +.. exn:: @ident is already used. .. tacv:: intros @@ -829,15 +850,10 @@ quantification or an implication. so that all the arguments of the i-th constructors of the corresponding inductive type are introduced can be controlled with the following option: - .. cmd:: Set Bracketing Last Introduction Pattern. - - Force completion, if needed, when the last introduction pattern is a - disjunctive or conjunctive pattern (this is the default). - - .. cmd:: Unset Bracketing Last Introduction Pattern. + .. opt:: Bracketing Last Introduction Pattern - Deactivate completion when the last introduction pattern is a disjunctive or - conjunctive pattern. + Force completion, if needed, when the last introduction pattern is a + disjunctive or conjunctive pattern (on by default). .. tacn:: clear @ident :name: clear @@ -857,6 +873,7 @@ quantification or an implication. This is equivalent to :n:`clear @ident. ... clear @ident.` .. tacv:: clearbody @ident + :name: clearbody This tactic expects :n:`@ident` to be a local definition then clears its body. Otherwise said, this tactic turns a definition into an assumption. @@ -878,7 +895,7 @@ quantification or an implication. it. .. tacn:: revert {+ @ident} - :name: revert ... + :name: revert This applies to any goal with variables :n:`{+ @ident}`. It moves the hypotheses (possibly defined) to the goal, if this respects dependencies. This tactic is @@ -994,6 +1011,7 @@ The name of the hypothesis in the proof-term, however, is left unchanged. .. tacv:: eset (@ident {+ @binder} := @term ) in @goal_occurrences .. tacv:: eset @term in @goal_occurrences + :name: eset While the different variants of :tacn:`set` expect that no existential variables are generated by the tactic, :n:`eset` removes this constraint. In @@ -1001,6 +1019,7 @@ The name of the hypothesis in the proof-term, however, is left unchanged. :tacn:`epose`, i.e. when the :`@term` does not occur in the goal. .. tacv:: remember @term as @ident + :name: remember This behaves as :n:`set (@ident:= @term ) in *` and using a logical (Leibniz’s) equality instead of a local definition. @@ -1018,6 +1037,8 @@ The name of the hypothesis in the proof-term, however, is left unchanged. .. tacv:: eremember @term as @ident .. tacv:: eremember @term as @ident in @goal_occurrences .. tacv:: eremember @term as @ident eqn:@ident + :name: eremember + While the different variants of :n:`remember` expect that no existential variables are generated by the tactic, :n:`eremember` removes this constraint. @@ -1124,6 +1145,7 @@ Controlling the proof flow .. exn:: Variable @ident is already declared .. tacv:: eassert form as intro_pattern by tactic + :name: eassert .. tacv:: assert (@ident := @term) @@ -1133,6 +1155,7 @@ Controlling the proof flow to prove it. .. tacv:: pose proof @term {? as intro_pattern} + :name: pose proof This tactic behaves like :n:`assert T {? as intro_pattern} by exact @term` where :g:`T` is the type of :g:`term`. In particular, @@ -1146,6 +1169,7 @@ Controlling the proof flow the tactic, :n:`epose proof` removes this constraint. .. tacv:: enough (@ident : form) + :name: enough This adds a new hypothesis of name :n:`@ident` asserting :n:`form` to the goal the tactic :n:`enough` is applied to. A new subgoal stating :n:`form` is @@ -1171,13 +1195,17 @@ Controlling the proof flow applied to all of them. .. tacv:: eenough (@ident : form) by tactic + :name: eenough + .. tacv:: eenough form by tactic + .. tacv:: eenough form as intro_pattern by tactic While the different variants of :n:`enough` expect that no existential variables are generated by the tactic, :n:`eenough` removes this constraint. -.. tacv:: cut form +.. tacv:: cut @form + :name: cut This tactic applies to any goal. It implements the non-dependent case of the “App” rule given in :ref:`typing-rules`. (This is Modus Ponens inference @@ -1187,6 +1215,7 @@ Controlling the proof flow .. tacv:: specialize (ident {* @term}) {? as intro_pattern} .. tacv:: specialize ident with @bindings_list {? as intro_pattern} + :name: specialize The tactic :n:`specialize` works on local hypothesis :n:`@ident`. The premises of this hypothesis (either universal quantifications or @@ -1239,7 +1268,7 @@ name of the variable (here :g:`n`) is chosen based on :g:`T`. This is equivalent to :n:`generalize @term` but it generalizes only over the specified occurrences of :n:`@term` (counting from left to right on the - expression printed using option :g:`Set Printing All`). + expression printed using option :opt:`Printing All`). .. tacv:: generalize @term as @ident @@ -1428,6 +1457,7 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) dependent premises of the type of :n:`@term` (see :ref:`syntax of bindings <bindingslist>`). .. tacv:: edestruct @term + :name: edestruct This tactic behaves like :n:`destruct @term` except that it does not fail if the instance of a dependent premises of the type of :n:`@term` is not @@ -1454,6 +1484,7 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) the effects of the `with`, `as`, `eqn:`, `using`, and `in` clauses. .. tacv:: case term + :name: case The tactic :n:`case` is a more basic tactic to perform case analysis without recursion. It behaves as :n:`elim @term` but using a case-analysis @@ -1463,14 +1494,15 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) Analogous to :n:`elim @term with @bindings_list` above. -.. tacv:: ecase @term -.. tacv:: ecase @term with @bindings_list +.. tacv:: ecase @term {? with @bindings_list } + :name: ecase In case the type of :n:`@term` has dependent premises, or dependent premises whose values are not inferable from the :n:`with @bindings_list` clause, :n:`ecase` turns them into existential variables to be resolved later on. .. tacv:: simple destruct @ident + :name: simple destruct This tactic behaves as :n:`intros until @ident; case @ident` when :n:`@ident` is a quantified variable of the goal. @@ -1561,6 +1593,7 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) premises of the type of :n:`term` (see :ref:`bindings list <bindingslist>`). .. tacv:: einduction @term + :name: einduction This tactic behaves like :tacn:`induction` except that it does not fail if some dependent premise of the type of :n:`@term` is not inferable. Instead, @@ -1633,6 +1666,7 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) (see :ref:`bindings list <bindingslist>`). .. tacv:: eelim @term + :name: eelim In case the type of :n:`@term` has dependent premises, this turns them into existential variables to be resolved later on. @@ -1651,7 +1685,8 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) These are the most general forms of ``elim`` and ``eelim``. It combines the effects of the ``using`` clause and of the two uses of the ``with`` clause. -.. tacv:: elimtype form +.. tacv:: elimtype @form + :name: elimtype The argument :n:`form` must be inductively defined. :n:`elimtype I` is equivalent to :n:`cut I. intro Hn; elim Hn; clear Hn.` Therefore the @@ -1661,6 +1696,7 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) :n:`elimtype I; 2:exact t.` .. tacv:: simple induction @ident + :name: simple induction This tactic behaves as :n:`intros until @ident; elim @ident` when :n:`@ident` is a quantified variable of the goal. @@ -1745,6 +1781,7 @@ analysis on inductive or co-inductive objects (see :ref:`inductive-definitions`) other ones need not be further generalized. .. tacv:: dependent destruction @ident + :name: dependent destruction This performs the generalization of the instance :n:`@ident` but uses ``destruct`` instead of induction on the generalized hypothesis. This gives @@ -1854,6 +1891,7 @@ See also: :ref:`advanced-recursive-functions` .. tacv:: ediscriminate @num .. tacv:: ediscriminate @term {? with @bindings_list} + :name: ediscriminate This works the same as ``discriminate`` but if the type of :n:`@term`, or the type of the hypothesis referred to by :n:`@num`, has uninstantiated @@ -1933,6 +1971,7 @@ the use of a sigma type is avoided. .. tacv:: einjection @num .. tacv:: einjection @term {? with @bindings_list} + :name: einjection This works the same as :n:`injection` but if the type of :n:`@term`, or the type of the hypothesis referred to by :n:`@num`, has uninstantiated @@ -1960,17 +1999,19 @@ the use of a sigma type is avoided. to the number of new equalities. The original equality is erased if it corresponds to an hypothesis. -It is possible to ensure that :n:`injection @term` erases the original -hypothesis and leaves the generated equalities in the context rather -than putting them as antecedents of the current goal, as if giving -:n:`injection @term as` (with an empty list of names). To obtain this -behavior, the option ``Set Structural Injection`` must be activated. This -option is off by default. +.. opt:: Structural Injection + + This option ensure that :n:`injection @term` erases the original hypothesis + and leaves the generated equalities in the context rather than putting them + as antecedents of the current goal, as if giving :n:`injection @term as` + (with an empty list of names). This option is off by default. + +.. opt:: Keep Proof Equalities -By default, ``injection`` only creates new equalities between :n:`@terms` whose -type is in sort :g:`Type` or :g:`Set`, thus implementing a special behavior for -objects that are proofs of a statement in :g:`Prop`. This behavior can be -turned off by setting the option ``Set Keep Proof Equalities``. + By default, :tacn:`injection` only creates new equalities between :n:`@terms` + whose type is in sort :g:`Type` or :g:`Set`, thus implementing a special + behavior for objects that are proofs of a statement in :g:`Prop`. This option + controls this behavior. .. tacn:: inversion @ident :name: inversion @@ -1996,8 +2037,8 @@ turned off by setting the option ``Set Keep Proof Equalities``. equalities between expressions that appeared in the hypothesis that is being processed. By default, no equalities are generated if they relate two proofs (i.e. equalities between :n:`@terms` whose type is in sort - :g:`Prop`). This behavior can be turned off by using the option ``Set Keep - Proof Equalities``. + :g:`Prop`). This behavior can be turned off by using the option + :opt`Keep Proof Equalities`. .. tacv:: inversion @num @@ -2122,6 +2163,7 @@ turned off by setting the option ``Set Keep Proof Equalities``. :n:`dependent inversion_clear @ident with @term`. .. tacv:: simple inversion @ident + :name: simple inversion It is a very primitive inversion tactic that derives all the necessary equalities but it does not simplify the constraints as ``inversion`` does. @@ -2422,6 +2464,7 @@ subgoals. leading to failure if these n rewrites are not possible. .. tacv:: erewrite @term + :name: erewrite This tactic works as :n:`rewrite @term` but turning unresolved bindings into existential variables, if any, instead of @@ -2468,6 +2511,7 @@ subgoals. clause argument must not contain any type of nor value of. .. tacv:: cutrewrite <- (@term = @term) + :cutrewrite: This tactic is deprecated. It acts like :n:`replace @term with @term`, or, equivalently as :n:`enough (@term = @term) as <-`. @@ -2511,30 +2555,30 @@ unfolded and cleared. context for which an equality of the form :n:`@ident = t` or :n:`t = @ident` or :n:`@ident := t` exists, with :n:`@ident` not occurring in `t`. - .. note:: - The behavior of subst can be controlled using option ``Set Regular Subst - Tactic.`` When this option is activated, subst also deals with the - following corner cases: + .. opt:: Regular Subst Tactic - + A context with ordered hypotheses :n:`@ident`:sub:`1` :n:`= @ident`:sub:`2` - and :n:`@ident`:sub:`1` :n:`= t`, or :n:`t′ = @ident`:sub:`1`` with `t′` not - a variable, and no other hypotheses of the form :n:`@ident`:sub:`2` :n:`= u` - or :n:`u = @ident`:sub:`2`; without the option, a second call to - subst would be necessary to replace :n:`@ident`:sub:`2` by `t` or - `t′` respectively. - + The presence of a recursive equation which without the option would - be a cause of failure of :tacn:`subst`. - + A context with cyclic dependencies as with hypotheses :n:`@ident`:sub:`1` :n:`= f @ident`:sub:`2` - and :n:`@ident`:sub:`2` :n:`= g @ident`:sub:`1` which without the - option would be a cause of failure of :tacn:`subst`. + This option controls the behavior of :tacn:`subst`. When it is + activated, :tacn:`subst` also deals with the following corner cases: - Additionally, it prevents a local definition such as :n:`@ident := t` to be - unfolded which otherwise it would exceptionally unfold in configurations - containing hypotheses of the form :n:`@ident = u`, or :n:`u′ = @ident` - with `u′` not a variable. Finally, it preserves the initial order of - hypotheses, which without the option it may break. The option is on by - default. + + A context with ordered hypotheses :n:`@ident`:sub:`1` :n:`= @ident`:sub:`2` + and :n:`@ident`:sub:`1` :n:`= t`, or :n:`t′ = @ident`:sub:`1`` with `t′` not + a variable, and no other hypotheses of the form :n:`@ident`:sub:`2` :n:`= u` + or :n:`u = @ident`:sub:`2`; without the option, a second call to + subst would be necessary to replace :n:`@ident`:sub:`2` by `t` or + `t′` respectively. + + The presence of a recursive equation which without the option would + be a cause of failure of :tacn:`subst`. + + A context with cyclic dependencies as with hypotheses :n:`@ident`:sub:`1` :n:`= f @ident`:sub:`2` + and :n:`@ident`:sub:`2` :n:`= g @ident`:sub:`1` which without the + option would be a cause of failure of :tacn:`subst`. + + Additionally, it prevents a local definition such as :n:`@ident := t` to be + unfolded which otherwise it would exceptionally unfold in configurations + containing hypotheses of the form :n:`@ident = u`, or :n:`u′ = @ident` + with `u′` not a variable. Finally, it preserves the initial order of + hypotheses, which without the option it may break. The option is on by + default. .. tacn:: stepl @term @@ -2548,30 +2592,37 @@ where `eq` is typically a setoid equality. The application of :n:`stepl @term` then replaces the goal by :n:`R @term @term` and adds a new goal stating :n:`eq @term @term`. -Lemmas are added to the database using the command ``Declare Left Step @term.`` +.. cmd:: Declare Left Step @term + + Adds :n:`@term` to the database used by :tacn:`stepl`. + The tactic is especially useful for parametric setoids which are not accepted as regular setoids for :tacn:`rewrite` and :tacn:`setoid_replace` (see :ref:`Generalizedrewriting`). .. tacv:: stepl @term by tactic - This applies :n:`stepl @term` then applies tactic to the second goal. + This applies :n:`stepl @term` then applies tactic to the second goal. .. tacv:: stepr @term stepr @term by tactic + :name: stepr + + This behaves as :tacn:`stepl` but on the right-hand-side of the binary + relation. Lemmas are expected to be of the form :g:`forall x y z, R x y -> eq + y z -> R x z`. - This behaves as :tacn:`stepl` but on the right-hand-side of the binary - relation. Lemmas are expected to be of the form :g:`forall x y z, R x y -> eq - y z -> R x z` and are registered using the command ``Declare Right Step - @term.`` + .. cmd:: Declare Right Step @term + + Adds :n:`@term` to the database used by :tacn:`stepr`. .. tacn:: change @term :name: change - This tactic applies to any goal. It implements the rule ``Conv`` given in - :ref:`subtyping-rules`. :g:`change U` replaces the current goal `T` - with `U` providing that `U` is well-formed and that `T` and `U` are - convertible. + This tactic applies to any goal. It implements the rule ``Conv`` given in + :ref:`subtyping-rules`. :g:`change U` replaces the current goal `T` + with `U` providing that `U` is well-formed and that `T` and `U` are + convertible. .. exn:: Not convertible @@ -2709,6 +2760,7 @@ the conversion in hypotheses :n:`{+ @ident}`. and :n:`lazy beta delta -{+ @qualid} iota zeta`. .. tacv:: vm_compute + :name: vm_compute This tactic evaluates the goal using the optimized call-by-value evaluation bytecode-based virtual machine described in :cite:`CompiledStrongReduction`. @@ -2718,6 +2770,7 @@ the conversion in hypotheses :n:`{+ @ident}`. reflection-based tactics. .. tacv:: native_compute + :name: native_compute This tactic evaluates the goal by compilation to Objective Caml as described in :cite:`FullReduction`. If Coq is running in native code, it can be @@ -3108,7 +3161,7 @@ the :tacn:`auto` and :tacn:`trivial` tactics: .. opt:: Info Auto .. opt:: Debug Auto .. opt:: Info Trivial -.. opt:: Info Trivial +.. opt:: Debug Trivial See also: :ref:`The Hints Databases for auto and eauto <thehintsdatabasesforautoandeauto>` @@ -3263,188 +3316,203 @@ observationally different from the legacy one. The general command to add a hint to some databases :n:`{+ @ident}` is -.. cmd:: Hint hint_definition : {+ @ident} +.. cmd:: Hint @hint_definition : {+ @ident} -**Variants:** + .. cmdv:: Hint @hint_definition -.. cmd:: Hint hint_definition + No database name is given: the hint is registered in the core database. - No database name is given: the hint is registered in the core database. + .. cmdv:: Local Hint @hint_definition : {+ @ident} -.. cmd:: Local Hint hint_definition : {+ @ident} + This is used to declare hints that must not be exported to the other modules + that require and import the current module. Inside a section, the option + Local is useless since hints do not survive anyway to the closure of + sections. - This is used to declare hints that must not be exported to the other modules - that require and import the current module. Inside a section, the option - Local is useless since hints do not survive anyway to the closure of - sections. + .. cmdv:: Local Hint @hint_definition -.. cmd:: Local Hint hint_definition + Idem for the core database. - Idem for the core database. + .. cmdv:: Hint Resolve @term {? | {? @num} {? @pattern}} + :name: Hint Resolve -The ``hint_definition`` is one of the following expressions: + This command adds :n:`simple apply @term` to the hint list with the head + symbol of the type of :n:`@term`. The cost of that hint is the number of + subgoals generated by :n:`simple apply @term` or :n:`@num` if specified. The + associated :n:`@pattern` is inferred from the conclusion of the type of + :n:`@term` or the given :n:`@pattern` if specified. In case the inferred type + of :n:`@term` does not start with a product the tactic added in the hint list + is :n:`exact @term`. In case this type can however be reduced to a type + starting with a product, the tactic :n:`simple apply @term` is also stored in + the hints list. If the inferred type of :n:`@term` contains a dependent + quantification on a variable which occurs only in the premisses of the type + and not in its conclusion, no instance could be inferred for the variable by + unification with the goal. In this case, the hint is added to the hint list + of :tacn:`eauto` instead of the hint list of auto and a warning is printed. A + typical example of a hint that is used only by :tacn:`eauto` is a transitivity + lemma. -+ :n:`Resolve @term {? | {? @num} {? @pattern}}` - This command adds :n:`simple apply @term` to the hint list with the head symbol of the type of - :n:`@term`. The cost of that hint is the number of subgoals generated by - :n:`simple apply @term` or :n:`@num` if specified. The associated :n:`@pattern` - is inferred from the conclusion of the type of :n:`@term` or the given - :n:`@pattern` if specified. In case the inferred type of :n:`@term` does not - start with a product the tactic added in the hint list is :n:`exact @term`. - In case this type can however be reduced to a type starting with a product, - the tactic :n:`simple apply @term` is also stored in the hints list. If the - inferred type of :n:`@term` contains a dependent quantification on a variable - which occurs only in the premisses of the type and not in its conclusion, no - instance could be inferred for the variable by unification with the goal. In - this case, the hint is added to the hint list of :tacn:`eauto` instead of the - hint list of auto and a warning is printed. A typical example of a hint that - is used only by ``eauto`` is a transitivity lemma. + .. exn:: @term cannot be used as a hint - .. exn:: @term cannot be used as a hint + The head symbol of the type of :n:`@term` is a bound variable such that + this tactic cannot be associated to a constant. - The head symbol of the type of :n:`@term` is a bound variable such that - this tactic cannot be associated to a constant. + .. cmdv:: Hint Resolve {+ @term} - **Variants:** + Adds each :n:`Hint Resolve @term`. - + :n:`Resolve {+ @term}` - Adds each :n:`Resolve @term`. + .. cmdv:: Hint Resolve -> @term - + :n:`Resolve -> @term` - Adds the left-to-right implication of an equivalence as a hint (informally - the hint will be used as :n:`apply <- @term`, although as mentionned - before, the tactic actually used is a restricted version of ``apply``). + Adds the left-to-right implication of an equivalence as a hint (informally + the hint will be used as :n:`apply <- @term`, although as mentionned + before, the tactic actually used is a restricted version of + :tacn:`apply`). - + :n:`Resolve <- @term` - Adds the right-to-left implication of an equivalence as a hint. + .. cmdv:: Resolve <- @term -+ :n:`Immediate @term` - This command adds :n:`simple apply @term; trivial` to the hint list associated - with the head symbol of the type of :n:`@ident` in the given database. This - tactic will fail if all the subgoals generated by :n:`simple apply @term` are - not solved immediately by the ``trivial`` tactic (which only tries tactics - with cost 0).This command is useful for theorems such as the symmetry of - equality or :g:`n+1=m+1 -> n=m` that we may like to introduce with a limited - use in order to avoid useless proof-search.The cost of this tactic (which - never generates subgoals) is always 1, so that it is not used by ``trivial`` - itself. + Adds the right-to-left implication of an equivalence as a hint. - .. exn:: @term cannot be used as a hint + .. cmdv:: Hint Immediate @term + :name: Hint Immediate - **Variants:** + This command adds :n:`simple apply @term; trivial` to the hint list associated + with the head symbol of the type of :n:`@ident` in the given database. This + tactic will fail if all the subgoals generated by :n:`simple apply @term` are + not solved immediately by the ``trivial`` tactic (which only tries tactics + with cost 0).This command is useful for theorems such as the symmetry of + equality or :g:`n+1=m+1 -> n=m` that we may like to introduce with a limited + use in order to avoid useless proof-search. The cost of this tactic (which + never generates subgoals) is always 1, so that it is not used by :tacn:`trivial` + itself. - + :n:`Immediate {+ @term}` - Adds each :n:`Immediate @term`. + .. exn:: @term cannot be used as a hint -+ :n:`Constructors @ident` - If :n:`@ident` is an inductive type, this command adds all its constructors as - hints of type Resolve. Then, when the conclusion of current goal has the form - :n:`(@ident ...)`, ``auto`` will try to apply each constructor. + .. cmdv:: Immediate {+ @term} - .. exn:: @ident is not an inductive type + Adds each :n:`Hint Immediate @term`. - **Variants:** + .. cmdv:: Hint Constructors @ident + :name: Hint Constructors - + :n:`Constructors {+ @ident}` - Adds each :n:`Constructors @ident`. + If :n:`@ident` is an inductive type, this command adds all its constructors as + hints of type ``Resolve``. Then, when the conclusion of current goal has the form + :n:`(@ident ...)`, :tacn:`auto` will try to apply each constructor. -+ :n:`Unfold @qualid` - This adds the tactic :n:`unfold @qualid` to the hint list that will only be - used when the head constant of the goal is :n:`@ident`. - Its cost is 4. + .. exn:: @ident is not an inductive type - **Variants:** + .. cmdv:: Hint Constructors {+ @ident} - + :n:`Unfold {+ @ident}` - Adds each :n:`Unfold @ident`. + Adds each :n:`Hint Constructors @ident`. -+ :n:`Transparent`, :n:`Opaque @qualid` - This adds a transparency hint to the database, making :n:`@qualid` a - transparent or opaque constant during resolution. This information is used - during unification of the goal with any lemma in the database and inside the - discrimination network to relax or constrain it in the case of discriminated - databases. + .. cmdv:: Hint Unfold @qualid + :name: Hint Unfold - **Variants:** + This adds the tactic :n:`unfold @qualid` to the hint list that will only be + used when the head constant of the goal is :n:`@ident`. + Its cost is 4. - + :n:`Transparent`, :n:`Opaque {+ @ident}` - Declares each :n:`@ident` as a transparent or opaque constant. + .. cmdv:: Hint Unfold {+ @ident} -+ :n:`Extern @num {? @pattern} => tactic` - This hint type is to extend ``auto`` with tactics other than ``apply`` and - ``unfold``. For that, we must specify a cost, an optional :n:`@pattern` and a - :n:`tactic` to execute. Here is an example:: - - Hint Extern 4 (~(_ = _)) => discriminate. - - Now, when the head of the goal is a disequality, ``auto`` will try - discriminate if it does not manage to solve the goal with hints with a - cost less than 4. One can even use some sub-patterns of the pattern in - the tactic script. A sub-pattern is a question mark followed by an - identifier, like ``?X1`` or ``?X2``. Here is an example: - - .. example:: - .. coqtop:: reset all - - Require Import List. - Hint Extern 5 ({?X1 = ?X2} + {?X1 <> ?X2}) => generalize X1, X2; decide equality : eqdec. - Goal forall a b:list (nat * nat), {a = b} + {a <> b}. - Info 1 auto with eqdec. - -+ :n:`Cut @regexp` - - .. warning:: these hints currently only apply to typeclass - proof search and the ``typeclasses eauto`` tactic (:ref:`typeclasses-eauto`). - - This command can be used to cut the proof-search tree according to a regular - expression matching paths to be cut. The grammar for regular expressions is - the following. Beware, there is no operator precedence during parsing, one can - check with ``Print HintDb`` to verify the current cut expression: - - .. productionlist:: `regexp` - e : ident hint or instance identifier - :|_ any hint - :| e\|e′ disjunction - :| e e′ sequence - :| e * Kleene star - :| emp empty - :| eps epsilon - :| ( e ) - - The `emp` regexp does not match any search path while `eps` - matches the empty path. During proof search, the path of - successive successful hints on a search branch is recorded, as a - list of identifiers for the hints (note Hint Extern’s do not have - an associated identifier). - Before applying any hint :n:`@ident` the current path `p` extended with - :n:`@ident` is matched against the current cut expression `c` associated to - the hint database. If matching succeeds, the hint is *not* applied. The - semantics of ``Hint Cut e`` is to set the cut expression to ``c | e``, the - initial cut expression being `emp`. - -+ :n:`Mode @qualid {* (+ | ! | -)}` - This sets an optional mode of use of the identifier :n:`@qualid`. When - proof-search faces a goal that ends in an application of :n:`@qualid` to - arguments :n:`@term ... @term`, the mode tells if the hints associated to - :n:`@qualid` can be applied or not. A mode specification is a list of n ``+``, - ``!`` or ``-`` items that specify if an argument of the identifier is to be - treated as an input (``+``), if its head only is an input (``!``) or an output - (``-``) of the identifier. For a mode to match a list of arguments, input - terms and input heads *must not* contain existential variables or be - existential variables respectively, while outputs can be any term. Multiple - modes can be declared for a single identifier, in that case only one mode - needs to match the arguments for the hints to be applied.The head of a term - is understood here as the applicative head, or the match or projection - scrutinee’s head, recursively, casts being ignored. ``Hint Mode`` is - especially useful for typeclasses, when one does not want to support default - instances and avoid ambiguity in general. Setting a parameter of a class as an - input forces proof-search to be driven by that index of the class, with ``!`` - giving more flexibility by allowing existentials to still appear deeper in the - index but not at its head. + Adds each :n:`Hint Unfold @ident`. -.. note:: - One can use an ``Extern`` hint with no pattern to do pattern-matching on - hypotheses using ``match goal`` with inside the tactic. + .. cmdv:: Hint %( Transparent %| Opaque %) @qualid + :name: Hint ( Transparent | Opaque ) + + This adds a transparency hint to the database, making :n:`@qualid` a + transparent or opaque constant during resolution. This information is used + during unification of the goal with any lemma in the database and inside the + discrimination network to relax or constrain it in the case of discriminated + databases. + + .. cmdv:: Hint %(Transparent | Opaque) {+ @ident} + + Declares each :n:`@ident` as a transparent or opaque constant. + + .. cmdv:: Hint Extern @num {? @pattern} => tactic + + This hint type is to extend :tacn:`auto` with tactics other than :tacn:`apply` and + :tacn:`unfold`. For that, we must specify a cost, an optional :n:`@pattern` and a + :n:`@tactic` to execute. + + .. example:: + + .. coqtop:: in + + Hint Extern 4 (~(_ = _)) => discriminate. + + Now, when the head of the goal is a disequality, ``auto`` will try + discriminate if it does not manage to solve the goal with hints with a + cost less than 4. One can even use some sub-patterns of the pattern in + the tactic script. A sub-pattern is a question mark followed by an + identifier, like ``?X1`` or ``?X2``. Here is an example: + + .. example:: + + .. coqtop:: reset all + + Require Import List. + Hint Extern 5 ({?X1 = ?X2} + {?X1 <> ?X2}) => generalize X1, X2; decide equality : eqdec. + Goal forall a b:list (nat * nat), {a = b} + {a <> b}. + Info 1 auto with eqdec. + + .. cmdv:: Hint Cut @regexp + + .. warning:: + + These hints currently only apply to typeclass proof search and the + :tacn:`typeclasses eauto` tactic. + + This command can be used to cut the proof-search tree according to a regular + expression matching paths to be cut. The grammar for regular expressions is + the following. Beware, there is no operator precedence during parsing, one can + check with :cmd:`Print HintDb` to verify the current cut expression: + + .. productionlist:: `regexp` + e : ident hint or instance identifier + :|_ any hint + :| e\|e′ disjunction + :| e e′ sequence + :| e * Kleene star + :| emp empty + :| eps epsilon + :| ( e ) + + The `emp` regexp does not match any search path while `eps` + matches the empty path. During proof search, the path of + successive successful hints on a search branch is recorded, as a + list of identifiers for the hints (note Hint Extern’s do not have + an associated identifier). + Before applying any hint :n:`@ident` the current path `p` extended with + :n:`@ident` is matched against the current cut expression `c` associated to + the hint database. If matching succeeds, the hint is *not* applied. The + semantics of ``Hint Cut e`` is to set the cut expression to ``c | e``, the + initial cut expression being `emp`. + + .. cmdv:: Hint Mode @qualid {* (+ | ! | -)} + + This sets an optional mode of use of the identifier :n:`@qualid`. When + proof-search faces a goal that ends in an application of :n:`@qualid` to + arguments :n:`@term ... @term`, the mode tells if the hints associated to + :n:`@qualid` can be applied or not. A mode specification is a list of n ``+``, + ``!`` or ``-`` items that specify if an argument of the identifier is to be + treated as an input (``+``), if its head only is an input (``!``) or an output + (``-``) of the identifier. For a mode to match a list of arguments, input + terms and input heads *must not* contain existential variables or be + existential variables respectively, while outputs can be any term. Multiple + modes can be declared for a single identifier, in that case only one mode + needs to match the arguments for the hints to be applied.The head of a term + is understood here as the applicative head, or the match or projection + scrutinee’s head, recursively, casts being ignored. ``Hint Mode`` is + especially useful for typeclasses, when one does not want to support default + instances and avoid ambiguity in general. Setting a parameter of a class as an + input forces proof-search to be driven by that index of the class, with ``!`` + giving more flexibility by allowing existentials to still appear deeper in the + index but not at its head. + + .. note:: + + One can use an ``Extern`` hint with no pattern to do pattern-matching on + hypotheses using ``match goal`` with inside the tactic. Hint databases defined in the Coq standard library @@ -3578,31 +3646,28 @@ We propose a smooth transitional path by providing the ``Loose Hint Behavior`` option which accepts three flags allowing for a fine-grained handling of non-imported hints. -**Variants:** - -.. cmd:: Set Loose Hint Behavior "Lax" +.. opt:: Loose Hint Behavior %( "Lax" %| "Warn" %| "Strict" %) - This is the default, and corresponds to the historical behavior, that - is, hints defined outside of a section have a global scope. + This option accepts three values, which control the behavior of hints w.r.t. + :cmd:`Import`: -.. cmd:: Set Loose Hint Behavior "Warn" + - "Lax": this is the default, and corresponds to the historical behavior, + that is, hints defined outside of a section have a global scope. - When set, it outputs a warning when a non-imported hint is used. Note that - this is an over-approximation, because a hint may be triggered by a run that - will eventually fail and backtrack, resulting in the hint not being actually - useful for the proof. + - "Warn": outputs a warning when a non-imported hint is used. Note that this + is an over-approximation, because a hint may be triggered by a run that + will eventually fail and backtrack, resulting in the hint not being + actually useful for the proof. -.. cmd:: Set Loose Hint Behavior "Strict" - - When set, it changes the behavior of an unloaded hint to a immediate fail - tactic, allowing to emulate an import-scoped hint mechanism. + - "Strict": changes the behavior of an unloaded hint to a immediate fail + tactic, allowing to emulate an import-scoped hint mechanism. .. _tactics-implicit-automation: Setting implicit automation tactics ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -.. cmd:: Proof with tactic +.. cmd:: Proof with @tactic This command may be used to start a proof. It defines a default tactic to be used each time a tactic command ``tactic``:sub:`1` is ended by ``...``. @@ -3616,11 +3681,11 @@ Setting implicit automation tactics Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`proof-editing-mode` - .. cmdv:: Proof using {+ @ident} with tactic + .. cmdv:: Proof using {+ @ident} with @tactic Combines in a single line ``Proof with`` and ``Proof using``, see :ref:`proof-editing-mode` - .. cmd:: Declare Implicit Tactic tactic + .. cmd:: Declare Implicit Tactic @tactic This command declares a tactic to be used to solve implicit arguments that Coq does not know how to solve by unification. It is used every @@ -3684,11 +3749,12 @@ Therefore, the use of :tacn:`intros` in the previous proof is unnecessary. an instantiation of `x` is necessary. .. tacv:: dtauto + :name: dtauto - While :tacn:`tauto` recognizes inductively defined connectives isomorphic to - the standard connective ``and, prod, or, sum, False, Empty_set, unit, True``, - :tacn:`dtauto` recognizes also all inductive types with one constructors and - no indices, i.e. record-style connectives. + While :tacn:`tauto` recognizes inductively defined connectives isomorphic to + the standard connective ``and, prod, or, sum, False, Empty_set, unit, True``, + :tacn:`dtauto` recognizes also all inductive types with one constructors and + no indices, i.e. record-style connectives. .. tacn:: intuition @tactic :name: intuition @@ -3734,17 +3800,10 @@ some incompatibilities. Empty_set, unit, True``, :tacn:`dintuition` recognizes also all inductive types with one constructors and no indices, i.e. record-style connectives. -Some aspects of the tactic :tacn:`intuition` can be controlled using options. -To avoid that inner negations which do not need to be unfolded are -unfolded, use: - -.. cmd:: Unset Intuition Negation Unfolding +.. opt:: Intuition Negation Unfolding - -To do that all negations of the goal are unfolded even inner ones -(this is the default), use: - -.. cmd:: Set Intuition Negation Unfolding + Controls whether :tacn:`intuition` unfolds inner negations which do not need + to be unfolded. This option is on by default. .. tacn:: rtauto :name: rtauto @@ -3768,14 +3827,15 @@ first- order reasoning, written by Pierre Corbineau. It is not restricted to usual logical connectives but instead may reason about any first-order class inductive definition. -The default tactic used by :tacn:`firstorder` when no rule applies is :g:`auto -with \*`, it can be reset locally or globally using the ``Set Firstorder -Solver`` tactic vernacular command and printed using ``Print Firstorder -Solver``. +.. opt:: Firstorder Solver + + The default tactic used by :tacn:`firstorder` when no rule applies is + :g:`auto with *`, it can be reset locally or globally using this option and + printed using :cmd:`Print Firstorder Solver`. .. tacv:: firstorder @tactic - Tries to solve the goal with :n:`@tactic` when no logical rule may apply. + Tries to solve the goal with :n:`@tactic` when no logical rule may apply. .. tacv:: firstorder using {+ @qualid} @@ -3792,8 +3852,9 @@ Solver``. This combines the effects of the different variants of :tacn:`firstorder`. -Proof-search is bounded by a depth parameter which can be set by -typing the ``Set Firstorder Depth n`` vernacular command. +.. opt:: Firstorder Depth @natural + + This option controls the proof-search depth bound. .. tacn:: congruence :name: congruence @@ -4013,6 +4074,7 @@ symbol :g:`=`. .. tacv:: esimplify_eq @num .. tacv:: esimplify_eq @term {? with @bindings_list} + :name: esimplify_eq This works the same as ``simplify_eq`` but if the type of :n:`@term`, or the type of the hypothesis referred to by :n:`@num`, has uninstantiated @@ -4024,7 +4086,7 @@ symbol :g:`=`. :n:`intro @ident; simplify_eq @ident`. .. tacn:: dependent rewrite -> @ident - :name: dependent rewrite -> + :name: dependent rewrite This tactic applies to any goal. If :n:`@ident` has type :g:`(existT B a b)=(existT B a' b')` in the local context (i.e. each @@ -4292,7 +4354,7 @@ This tactics reverses the list of the focused goals. This tactic moves all goals under focus to a shelf. While on the shelf, goals will not be focused on. They can be solved by unification, or they can be called back into focus with the command - :tacn:`Unshelve`. + :cmd:`Unshelve`. .. tacv:: shelve_unifiable @@ -4308,8 +4370,7 @@ This tactics reverses the list of the focused goals. all:shelve_unifiable. reflexivity. -.. tacn:: Unshelve - :name: Unshelve +.. cmd:: Unshelve This command moves all the goals on the shelf (see :tacn:`shelve`) from the shelf into focus, by appending them to the end of the current diff --git a/doc/sphinx/proof-engine/vernacular-commands.rst b/doc/sphinx/proof-engine/vernacular-commands.rst index da4034fb8a..692ff294a6 100644 --- a/doc/sphinx/proof-engine/vernacular-commands.rst +++ b/doc/sphinx/proof-engine/vernacular-commands.rst @@ -39,6 +39,7 @@ This is a synonym to ``Print`` :n:`@qualid` when :n:`@qualid` denotes a global constant. .. cmdv:: About @qualid. + :name: About This displays various information about the object denoted by :n:`@qualid`: its kind (module, constant, assumption, inductive, @@ -61,6 +62,7 @@ Variants: .. cmdv:: Inspect @num. + :name: Inspect This command displays the :n:`@num` last objects of the current environment, including sections and modules. @@ -77,14 +79,11 @@ section. Flags, Options and Tables ----------------------------- -|Coq| configurability is based on flags (e.g. ``Set Printing All`` in -Section :ref:`printing_constructions_full`), options (e.g. ``Set Printing Widthinteger`` in Section -:ref:`controlling-display`), or tables (e.g. ``Add Printing Record ident``, in Section -:ref:`record-types`). -The names of flags, options and tables are made of non-empty sequences of identifiers -(conventionally with capital initial -letter). The general commands handling flags, options and tables are -given below. +|Coq| configurability is based on flags (e.g. :opt:`Printing All`), options +(e.g. :opt:`Printing Width`), or tables (e.g. :cmd:`Add Printing Record`). The +names of flags, options and tables are made of non-empty sequences of +identifiers (conventionally with capital initial letter). The general commands +handling flags, options and tables are given below. .. TODO : flag is not a syntax entry @@ -93,7 +92,6 @@ given below. This command switches :n:`@flag` on. The original state of :n:`@flag` is restored when the current module ends. - Variants: .. cmdv:: Local Set @flag. @@ -107,6 +105,11 @@ This command switches :n:`@flag` on. The original state of :n:`@flag` is *not* restored at the end of the module. Additionally, if set in a file, :n:`@flag` is switched on when the file is `Require`-d. +.. cmdv:: Export Set @flag. + + This command switches :n:`@flag` on. The original state + of :n:`@flag` is restored at the end of the current module, but :n:`@flag` + is switched on when this module is imported. .. cmd:: Unset @flag. @@ -128,6 +131,11 @@ This command switches :n:`@flag` off. The original state of :n:`@flag` is *not* restored at the end of the module. Additionally, if set in a file, :n:`@flag` is switched off when the file is `Require`-d. +.. cmdv:: Export Unset @flag. + + This command switches :n:`@flag` off. The original state + of :n:`@flag` is restored at the end of the current module, but :n:`@flag` + is switched off when this module is imported. .. cmd:: Test @flag. @@ -157,11 +165,16 @@ original value of :n:`@option` is *not* restored at the end of the module. Additionally, if set in a file, :n:`@option` is set to value when the file is `Require`-d. +.. cmdv:: Export Set @option. + + This command set :n:`@option` to :n:`@value`. The original state + of :n:`@option` is restored at the end of the current module, but :n:`@option` + is set to :n:`@value` when this module is imported. .. cmd:: Unset @option. -This command resets option to its default value. + This command turns off :n:`@option`. Variants: @@ -169,17 +182,20 @@ Variants: .. cmdv:: Local Unset @option. -This command resets :n:`@option` to its default -value. The original state of :n:`@option` is restored when the current -*section* ends. + This command turns off :n:`@option`. The original state of :n:`@option` is restored when the current + *section* ends. .. cmdv:: Global Unset @option. -This command resets :n:`@option` to its default -value. The original state of :n:`@option` is *not* restored at the end of the -module. Additionally, if unset in a file, :n:`@option` is reset to its -default value when the file is `Require`-d. + This command turns off :n:`@option`. The original state of :n:`@option` is *not* restored at the end of the + module. Additionally, if unset in a file, :n:`@option` is reset to its + default value when the file is `Require`-d. +.. cmdv:: Export Unset @option. + + This command turns off :n:`@option`. The original state of :n:`@option` is restored at the end of the + current module, but :n:`@option` is set to its default value when this module + is imported. .. cmd:: Test @option. @@ -190,9 +206,17 @@ This command prints the current value of :n:`@option`. .. TODO : table is not a syntax entry .. cmd:: Add @table @value. + :name: Add `table` `value` + .. cmd:: Remove @table @value. + :name: Remove `table` `value` + .. cmd:: Test @table @value. + :name: Test `table` `value` + .. cmd:: Test @table for @value. + :name: Test `table` for `value` + .. cmd:: Print Table @table. These are general commands for tables. @@ -256,11 +280,10 @@ See also: Section :ref:`performingcomputations`. .. cmd::Extraction @term. This command displays the extracted term from :n:`@term`. The extraction is -processed according to the distinction between ``Set`` and ``Prop``; that is -to say, between logical and computational content (see Section -:ref:`sorts`). The extracted term is displayed in OCaml -syntax, -where global identifiers are still displayed as in |Coq| terms. +processed according to the distinction between :g:`Set` and :g:`Prop`; that is +to say, between logical and computational content (see Section :ref:`sorts`). +The extracted term is displayed in OCaml syntax, where global identifiers are +still displayed as in |Coq| terms. Variants: @@ -698,9 +721,9 @@ The command did not find the file foo.vo. Either foo.v exists but is not compiled or foo.vo is in a directory which is not in your LoadPath (see Section :ref:`libraries-and-filesystem`). -.. exn:: Compiled library ident.vo makes inconsistent assumptions over library qualid +.. exn:: Compiled library @ident.vo makes inconsistent assumptions over library qualid -The command tried to load library file `ident.vo` that +The command tried to load library file :n:`@ident`.vo that depends on some specific version of library :n:`@qualid` which is not the one already loaded in the current |Coq| session. Probably `ident.v` was not properly recompiled with the last version of the file containing @@ -766,7 +789,7 @@ Error messages: .. exn:: File not found on loadpath : @string -.. exn:: Loading of ML object file forbidden in a native |Coq| +.. exn:: Loading of ML object file forbidden in a native Coq @@ -1030,16 +1053,13 @@ to |Coq| with the command: go();; +.. warning:: - -Warnings: - - -#. It only works with the bytecode version of |Coq| (i.e. `coqtop.byte`, - see Section `interactive-use`). -#. You must have compiled |Coq| from the source package and set the - environment variable COQTOP to the root of your copy of the sources - (see Section `customization-by-environment-variables`). + #. It only works with the bytecode version of |Coq| (i.e. `coqtop.byte`, + see Section `interactive-use`). + #. You must have compiled |Coq| from the source package and set the + environment variable COQTOP to the root of your copy of the sources + (see Section `customization-by-environment-variables`). @@ -1065,20 +1085,11 @@ expressed in seconds), then it is interrupted and an error message is displayed. -.. cmd:: Set Default Timeout @num. - -After using this command, all subsequent commands behave as if they -were passed to a Timeout command. Commands already starting by a -`Timeout` are unaffected. - - -.. cmd:: Unset Default Timeout. +.. opt:: Default Timeout @num -This command turns off the use of a default timeout. - -.. cmd:: Test Default Timeout. - -This command displays whether some default timeout has been set or not. + This option controls a default timeout for subsequent commands, as if they + were passed to a :cmd:`Timeout` command. Commands already starting by a + :cmd:`Timeout` are unaffected. .. cmd:: Fail @command. @@ -1099,128 +1110,58 @@ Error messages: Controlling display ----------------------- +.. opt:: Silent -.. cmd:: Set Silent. - -This command turns off the normal displaying. - - -.. cmd:: Unset Silent. - -This command turns the normal display on. - -.. todo:: check that spaces are handled well - -.. cmd:: Set Warnings ‘‘(@ident {* , @ident } )’’. - -This command configures the display of warnings. It is experimental, -and expects, between quotes, a comma-separated list of warning names -or categories. Adding - in front of a warning or category disables it, -adding + makes it an error. It is possible to use the special -categories all and default, the latter containing the warnings enabled -by default. The flags are interpreted from left to right, so in case -of an overlap, the flags on the right have higher priority, meaning -that `A,-A` is equivalent to `-A`. - - -.. cmd:: Set Search Output Name Only. - -This command restricts the output of search commands to identifier -names; turning it on causes invocations of ``Search``, ``SearchHead``, -``SearchPattern``, ``SearchRewrite`` etc. to omit types from their output, -printing only identifiers. - - -.. cmd:: Unset Search Output Name Only. - -This command turns type display in search results back on. - - -.. cmd:: Set Printing Width @integer. - -This command sets which left-aligned part of the width of the screen -is used for display. - - -.. cmd:: Unset Printing Width. - -This command resets the width of the screen used for display to its -default value (which is 78 at the time of writing this documentation). - - -.. cmd:: Test Printing Width. - -This command displays the current screen width used for display. - - -.. cmd:: Set Printing Depth @integer. - -This command sets the nesting depth of the formatter used for pretty- -printing. Beyond this depth, display of subterms is replaced by dots. - - -.. cmd:: Unset Printing Depth. - -This command resets the nesting depth of the formatter used for -pretty-printing to its default value (at the time of writing this -documentation, the default value is 50). - - -.. cmd:: Test Printing Depth. - -This command displays the current nesting depth used for display. - - -.. cmd:: Unset Printing Compact Contexts. - -This command resets the displaying of goals contexts to non compact -mode (default at the time of writing this documentation). Non compact -means that consecutive variables of different types are printed on -different lines. - - -.. cmd:: Set Printing Compact Contexts. - -This command sets the displaying of goals contexts to compact mode. -The printer tries to reduce the vertical size of goals contexts by -putting several variables (even if of different types) on the same -line provided it does not exceed the printing width (See Set Printing -Width above). - - -.. cmd:: Test Printing Compact Contexts. - -This command displays the current state of compaction of goal. + This option controls the normal displaying. +.. opt:: Warnings "{+, {? %( - %| + %) } @ident }" -.. cmd:: Unset Printing Unfocused. + This option configures the display of warnings. It is experimental, and + expects, between quotes, a comma-separated list of warning names or + categories. Adding - in front of a warning or category disables it, adding + + makes it an error. It is possible to use the special categories all and + default, the latter containing the warnings enabled by default. The flags are + interpreted from left to right, so in case of an overlap, the flags on the + right have higher priority, meaning that `A,-A` is equivalent to `-A`. -This command resets the displaying of goals to focused goals only -(default). Unfocused goals are created by focusing other goals with -bullets (see :ref:`bullets`) or curly braces (see `here <curly-braces>`). +.. opt:: Search Output Name Only + This option restricts the output of search commands to identifier names; + turning it on causes invocations of :cmd:`Search`, :cmd:`SearchHead`, + :cmd:`SearchPattern`, :cmd:`SearchRewrite` etc. to omit types from their + output, printing only identifiers. -.. cmd:: Set Printing Unfocused. +.. opt:: Printing Width @integer -This command enables the displaying of unfocused goals. The goals are -displayed after the focused ones and are distinguished by a separator. + This command sets which left-aligned part of the width of the screen is used + for display. At the time of writing this documentation, the default value + is 78. +.. opt:: Printing Depth @integer -.. cmd:: Test Printing Unfocused. + This option controls the nesting depth of the formatter used for pretty- + printing. Beyond this depth, display of subterms is replaced by dots. At the + time of writing this documentation, the default value is 50. -This command displays the current state of unfocused goals display. +.. opt:: Printing Compact Contexts + This option controls the compact display mode for goals contexts. When on, + the printer tries to reduce the vertical size of goals contexts by putting + several variables (even if of different types) on the same line provided it + does not exceed the printing width (see :opt:`Printing Width`). At the time + of writing this documentation, it is off by default. -.. cmd:: Set Printing Dependent Evars Line. +.. opt:: Printing Unfocused -This command enables the printing of the “(dependent evars: …)” line -when -emacs is passed. + This option controls whether unfocused goals are displayed. Such goals are + created by focusing other goals with bullets (see :ref:`bullets` or + :ref:`curly braces <curly-braces>`). It is off by default. +.. opt:: Printing Dependent Evars Line -.. cmd:: Unset Printing Dependent Evars Line. + This option controls the printing of the “(dependent evars: …)” line when + ``-emacs`` is passed. -This command disables the printing of the “(dependent evars: …)” line -when -emacs is passed. .. _vernac-controlling-the-reduction-strategies: @@ -1234,7 +1175,7 @@ conversion algorithm lazily compares applicative terms while the other is a brute-force but efficient algorithm that first normalizes the terms before comparing them. The second algorithm is based on a bytecode representation of terms similar to the bytecode -representation used in the ZINC virtual machine [`98`]. It is +representation used in the ZINC virtual machine :cite:`Leroy90`. It is especially useful for intensive computation of algebraic values, such as numbers, and for reflection-based tactics. The commands to fine- tune the reduction strategies and the lazy conversion algorithm are diff --git a/doc/sphinx/user-extensions/proof-schemes.rst b/doc/sphinx/user-extensions/proof-schemes.rst index 8a24a382a5..e12e4d897a 100644 --- a/doc/sphinx/user-extensions/proof-schemes.rst +++ b/doc/sphinx/user-extensions/proof-schemes.rst @@ -12,7 +12,7 @@ The ``Scheme`` command is a high-level tool for generating automatically (possibly mutual) induction principles for given types and sorts. Its syntax follows the schema: -.. cmd:: Scheme ident := Induction for ident' Sort sort {* with ident := Induction for ident' Sort sort} +.. cmd:: Scheme @ident := Induction for @ident Sort sort {* with @ident := Induction for @ident Sort sort} where each `ident'ᵢ` is a different inductive type identifier belonging to the same package of mutual inductive definitions. This @@ -20,17 +20,17 @@ command generates the `identᵢ`s to be mutually recursive definitions. Each term `identᵢ` proves a general principle of mutual induction for objects in type `identᵢ`. -.. cmdv:: Scheme ident := Minimality for ident' Sort sort {* with ident := Minimality for ident' Sort sort} +.. cmdv:: Scheme @ident := Minimality for @ident Sort sort {* with @ident := Minimality for @ident' Sort sort} Same as before but defines a non-dependent elimination principle more natural in case of inductively defined relations. -.. cmdv:: Scheme Equality for ident +.. cmdv:: Scheme Equality for @ident Tries to generate a Boolean equality and a proof of the decidability of the usual equality. If `ident` involves some other inductive types, their equality has to be defined first. -.. cmdv:: Scheme Induction for ident Sort sort {* with Induction for ident Sort sort} +.. cmdv:: Scheme Induction for @ident Sort sort {* with Induction for @ident Sort sort} If you do not provide the name of the schemes, they will be automatically computed from the sorts involved (works also with Minimality). @@ -103,6 +103,8 @@ induction for objects in type `identᵢ`. Automatic declaration of schemes ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +.. opt:: Elimination Schemes + It is possible to deactivate the automatic declaration of the induction principles when defining a new inductive type with the ``Unset Elimination Schemes`` command. It may be reactivated at any time with @@ -113,15 +115,22 @@ induction principles when defining a new inductive type with the This option controls whether types declared with the keywords :cmd:`Variant` and :cmd:`Record` get an automatic declaration of the induction principles. -In addition, the ``Case Analysis Schemes`` flag governs the generation of -case analysis lemmas for inductive types, i.e. corresponding to the -pattern-matching term alone and without fixpoint. -You can also activate the automatic declaration of those Boolean -equalities (see the second variant of ``Scheme``) with respectively the -commands ``Set Boolean Equality Schemes`` and ``Set Decidable Equality -Schemes``. However you have to be careful with this option since Coq may -now reject well-defined inductive types because it cannot compute a -Boolean equality for them. +.. opt:: Case Analysis Schemes + + This flag governs the generation of case analysis lemmas for inductive types, + i.e. corresponding to the pattern-matching term alone and without fixpoint. + +.. opt:: Boolean Equality Schemes + +.. opt:: Decidable Equality Schemes + +These flags control the automatic declaration of those Boolean equalities (see +the second variant of ``Scheme``). + +.. warning:: + + You have to be careful with this option since Coq may now reject well-defined + inductive types because it cannot compute a Boolean equality for them. .. opt:: Rewriting Schemes @@ -134,7 +143,7 @@ The ``Combined Scheme`` command is a tool for combining induction principles generated by the ``Scheme command``. Its syntax follows the schema : -.. cmd:: Combined Scheme ident from {+, ident} +.. cmd:: Combined Scheme @ident from {+, ident} where each identᵢ after the ``from`` is a different inductive principle that must belong to the same package of mutual inductive principle definitions. @@ -175,7 +184,7 @@ generating automatically induction principles corresponding to available via ``Require Import FunInd``. Its syntax then follows the schema: -.. cmd:: Functional Scheme ident := Induction for ident' Sort sort {* with ident := Induction for ident' Sort sort} +.. cmd:: Functional Scheme @ident := Induction for ident' Sort sort {* with @ident := Induction for @ident Sort sort} where each `ident'ᵢ` is a different mutually defined function name (the names must be in the same order as when they were defined). This @@ -316,7 +325,7 @@ Generation of inversion principles with ``Derive`` ``Inversion`` The syntax of ``Derive`` ``Inversion`` follows the schema: -.. cmd:: Derive Inversion ident with forall (x : T), I t Sort sort +.. cmd:: Derive Inversion @ident with forall (x : T), I t Sort sort This command generates an inversion principle for the `inversion … using` tactic. Let `I` be an inductive predicate and `x` the variables occurring @@ -325,17 +334,17 @@ sort `sort` corresponding to the instance `∀ (x:T), I t` with the name `ident` in the global environment. When applied, it is equivalent to having inverted the instance with the tactic `inversion`. -.. cmdv:: Derive Inversion_clear ident with forall (x:T), I t Sort sort +.. cmdv:: Derive Inversion_clear @ident with forall (x:T), I t Sort sort When applied, it is equivalent to having inverted the instance with the tactic inversion replaced by the tactic `inversion_clear`. -.. cmdv:: Derive Dependent Inversion ident with forall (x:T), I t Sort sort +.. cmdv:: Derive Dependent Inversion @ident with forall (x:T), I t Sort sort When applied, it is equivalent to having inverted the instance with the tactic `dependent inversion`. -.. cmdv:: Derive Dependent Inversion_clear ident with forall(x:T), I t Sort sort +.. cmdv:: Derive Dependent Inversion_clear @ident with forall(x:T), I t Sort sort When applied, it is equivalent to having inverted the instance with the tactic `dependent inversion_clear`. diff --git a/doc/sphinx/user-extensions/syntax-extensions.rst b/doc/sphinx/user-extensions/syntax-extensions.rst index 9965d5002d..c4a7121ce4 100644 --- a/doc/sphinx/user-extensions/syntax-extensions.rst +++ b/doc/sphinx/user-extensions/syntax-extensions.rst @@ -32,6 +32,8 @@ Notations Basic notations ~~~~~~~~~~~~~~~ +.. cmd:: Notation + A *notation* is a symbolic expression denoting some term or term pattern. @@ -1200,7 +1202,7 @@ Tactic notations allow to customize the syntax of the tactics of the tactic language. Tactic notations obey the following syntax: .. productionlist:: coq - tacn : [Local] Tactic Notation [`tactic_level`] [`prod_item` … `prod_item`] := `tactic`. + tacn : Tactic Notation [`tactic_level`] [`prod_item` … `prod_item`] := `tactic`. prod_item : `string` | `tactic_argument_type`(`ident`) tactic_level : (at level `natural`) tactic_argument_type : ident | simple_intropattern | reference @@ -1211,7 +1213,7 @@ tactic language. Tactic notations obey the following syntax: : | tactic | tactic0 | tactic1 | tactic2 | tactic3 : | tactic4 | tactic5 -.. cmd:: {? Local} Tactic Notation {? (at level @level)} {+ @prod_item} := @tactic. +.. cmd:: Tactic Notation {? (at level @level)} {+ @prod_item} := @tactic. A tactic notation extends the parser and pretty-printer of tactics with a new rule made of the list of production items. It then evaluates into the |
