Coq free download, Coq download on software download

A free formal proof management system A proof done with Coq is mechanically checked by the machine. In particular, Coq allows:· to define functions or predicates,· to state mathematical theorems and software specifications,· to develop interactively formal proofs of these theorems,· to check these proofs by a relatively small certification "kernel".Coq also integrates a functional programming language:· functions and predicates can be evaluated efficiently,· a modular development system allows the reuse of theories,· certified programs can be automatically extracted to languages like Objective Caml, Haskell or Scheme.Coq is based on a framework called "Calculus of Inductive Constructions" that is both a logic and a functional programming language.As a proof development system, Coq provides both interactive proof methods and various certified decision and semi-decision algorithms. Coq provides a protocol for connecting with external computer algebra system or theorem provers.As a platform for the formalization of mathematics, Coq provides support for light notations and implicit contents. It also provides some support for reasoning on algebraic structures. Coq is available for Unix (including Mac OS X) and Windows 95/98/NT/XP/Vista systems.NOTE: Coq is developed, licensed and provided under the GNU Lesser General Public License. Requirements: · Objective Caml · GNU Make What's New in This Release: Language: · If a fixpoint is not written with an explicit { struct ... }, then all arguments are tried successively (from left to right) until one is found that satisfies the structural decreasing condition. · New experimental typeclass system giving ad-hoc polymorphism and overloading based on dependent records and implicit arguments. · New syntax "let 'pat := b in c" for let-binding using irrefutable patterns. · New syntax "forall {A}, T" for specifying maximally inserted implicit arguments in terms. · Sort of Record/Structure, Inductive and CoInductive defaults to Type if omitted. · Support for optional "where" notation clauses for record fields. · (Co)Inductive types can be defined as records (e.g. "CoInductive stream := { hd : nat; tl : stream }.") · New syntax "Theorem id1:t1 ... with idn:tn" for proving mutually dependent statements. · Support for sort-polymorphism on constants denoting inductive types. · Several evolutions of the module system (handling of module aliases, functorial module types, an Include feature, etc). · Prop now a subtype of Set (predicative and impredicative forms). · Recursive inductive types in Prop with a single constructor of which all arguments are in Prop is now considered to be a singleton type. It consequently supports all eliminations to Prop, Set and Type. As a consequence, Acc_rect has now a more direct proof . · New syntax to do implicit generalization in binders and inside terms. · New tentative syntax for introduction of record objects without mentioning the constructor {| field := body; ... |}, turning missing fields into holes (compatible with refine and Program). Vernacular commands: · Added option Global to "Arguments Scope" for section surviving. · Added option "Unset Elimination Schemes" to deactivate the automatic generation of elimination schemes. · Modification of the Scheme command so you can ask for the name to be automatically computed (e.g. Scheme Induction for nat Sort Set). · New command "Combined Scheme" to build combined mutual induction principles from existing mutual induction principles. · New command "Scheme Equality" to build a decidable (boolean) equality for simple inductive datatypes and a decision property over this equality (e.g. Scheme Equality for nat). · Added option "Set Equality Scheme" to make automatic the declaration of the boolean equality when possible. · Source of universe inconsistencies now printed when option "Set Printing Universes" is activated. · New option "Set Printing Existential Instances" for making the display of existential variable instances explicit. · Support for option "", and "-", for the "compute"/"cbv" reduction strategy, respectively meaning reduce only, or everything but, the constants id1 ... idn. "lazy" alone or followed by "", and "-" also supported, meaning apply all of beta-iota-zeta-delta, possibly restricting delta. · New command "Strategy" to control the expansion of constants during conversion tests. It generalizes commands Opaque and Transparent by introducing a range of levels. Lower levels are assigned to constants that should be expanded first. · New options Global and Local to Opaque and Transparent. · New command "Print Assumptions" to display all variables, parameters or axioms a theorem or definition relies on. · "Add Rec LoadPath" now provides references to libraries using partially qualified names (this holds also for coqtop/coqc option -R). · SearchAbout supports negated search criteria, reference to logical objects by their notation, and more generally search of subterms. · "Declare ML Module" now allows to import .cmxs files when Coq is compiled in native code with a version of OCaml that supports native Dynlink (>= 3.11). · New command "Create HintDb name " to explicitely declare a new hint database and optionaly turn on a discrimination net implementation to index all the lemmas in the database. · New commands "Hint Transparent" and "Hint Opaque" to set the unfolding status of definitions used by auto. This information is taken into account by the discrimination net and the unification algorithm. · "Hint Extern" now takes an optional pattern and applies the given tactic all the time if no pattern is given. · Specific sort constraints on Record now taken into account. · "Print LoadPath" supports a path argument to filter the display. Libraries: · Several parts of the libraries are now in Type, in particular FSets, SetoidList, ListSet, Sorting, Zmisc. This may induce a few incompatibilities. In case of trouble while fixing existing development, it may help to simply declare Set as an alias for Type (see file SetIsType). · New arithmetical library in theories/Numbers. It contains: * an abstract modular development of natural and integer arithmetics in Numbers/Natural/Abstract and Numbers/Integer/Abstract * an implementation of efficient computational bounded and unbounded integers that can be mapped to processor native arithmetics. See Numbers/Cyclic/Int31 for 31-bit integers and Numbers/Natural/BigN for unbounded natural numbers and Numbers/Integer/BigZ for unbounded integers. * some proofs that both older libraries Arith, ZArith and NArith and newer BigN and BigZ implement the abstract modular development. This allows in particular BigN and BigZ to already come with a large database of basic lemmas and some generic tactics (ring), This library has still an experimental status, as well as the processor-acceleration mechanism, but both its abstract and its concrete parts are already quite usable and could challenge the use of nat, N and Z in actual developments. Moreover, an extension of this framework to rational numbers is ongoing, and an efficient Q structure is already provided (see Numbers/Rational/BigQ), but this part is currently incomplete (no abstract layer and generic lemmas). · Many changes in FSets/FMaps. In practice, compatibility with earlier version should be fairly good, but some adaptations may be required. * Interfaces of unordered ("weak") and ordered sets have been factorized thanks to new features of Coq modules (in particular Include), see FSetInterface. Same for maps. Hints in these interfaces have been reworked (they are now placed in a "set" database). * To allow full subtyping between weak and ordered sets, a field "eq_dec" has been added to OrderedType. The old version of OrderedType is now called MiniOrderedType and functor MOT_to_OT allow to convert to the new version. The interfaces and implementations of sets now contain also such a "eq_dec" field. * FSetDecide, contributed by Aaron Bohannon, contains a decision procedure allowing to solve basic set-related goals (for instance, is a point in a particular set ?). See FSetProperties for examples. * Functors of properties have been improved, especially the ones about maps, that now propose some induction principles. Some properties of fold need less hypothesis. * More uniformity in implementations of sets and maps: they all use implicit arguments, and no longer export unnecessary scopes (see bug #1347) * Internal parts of the implementations based on AVL have evolved a lot. The main files FSetAVL and FMapAVL are now much more lightweight now. In particular, minor changes in some functions has allowed to fully separate the proofs of operational correctness from the proofs of well-balancing: well-balancing is critical for efficiency, but not anymore for proving that these trees implement our interfaces, hence we have moved these proofs into appendix files FSetFullAVL and FMapFullAVL. Moreover, a few functions like union and compare have been modified in order to be structural yet efficient. The appendix files also contains alternative versions of these few functions, much closer to the initial Ocaml code and written via the Function framework. · Library IntMap, subsumed by FSets/FMaps, has been removed from Coq Standard Library and moved into a user contribution Cachan/IntMap · Better computational behavior of some constants (eq_nat_dec and le_lt_dec more efficient, Z_lt_le_dec and Positive_as_OT.compare transparent, ...) (exceptional source of incompatibilities). · Boolean operators moved from module Bool to module Datatypes (may need to rename qualified references in script and force notations || and && to be at levels 50 and 40 respectively). · The constructors xI and xO of type positive now have postfix notations "~1" and "~0", allowing to write numbers in binary form easily, for instance 6 is 1~1~0 and 4*p is p~0~0 (see BinPos.v). · Improvements to NArith (Nminus, Nmin, Nmax), and to QArith (in particular a better power function). · Changes in ZArith: several additional lemmas (used in theories/Numbers), especially in Zdiv, Znumtheory, Zpower. Moreover, many results in Zdiv have been generalized: the divisor may simply be non-null instead of strictly positive (see lemmas with name ending by "_full"). An alternative file ZOdiv proposes a different behavior (the one of Ocaml) when dividing by negative numbers. · Changes in Arith: EqNat and Wf_nat now exported from Arith, some constructions on nat that were outside Arith are now in (e.g. iter_nat). · In SetoidList, eqlistA now expresses that two lists have similar elements at the same position, while the predicate previously called eqlistA is now equivlistA (this one only states that the lists contain the same elements, nothing more). · Changes in Reals: * Most statement in "sigT" (including the completeness axiom) are now in "sig" (in case of incompatibility, use proj1_sig instead of projT1, sig instead of sigT, etc). * More uniform naming scheme (identifiers in French moved to English, consistent use of 0 -zero -instead of O -letter O --, etc). * Lemma on prod_f_SO is now on prod_f_R0. * Useless hypothesis of ln_exists1 dropped. * New Rlogic.v states a few logical properties about R axioms. * RIneq.v extended and made cleaner. · Slight restructuration of the Logic library regarding choice and classical logic. Addition of files providing intuitionistic axiomatizations of descriptions: Epsilon.v, Description.v and IndefiniteDescription.v. · Definition of pred and minus made compatible with the structural decreasing criterion for use in fixpoints. · Files Relations/Rstar.v and Relations/Newman.v moved out to the user contribution repository (contribution CoC_History). New lemmas about transitive closure added and some bound variables renamed (exceptional risk of incompatibilities). Notations, coercions, implicit arguments and type inference: · More automation in the inference of the return clause of dependent pattern-matching problems. · Experimental allowance for omission of the clauses easily detectable as impossible in pattern-matching problems. · Improved inference of implicit arguments, now working inside record declarations. · New options "Set Maximal Implicit Insertion", "Set Reversible Pattern Implicit", "Set Strongly Strict Implicit" and "Set Printing Implicit Defensive" for controlling inference and use of implicit arguments. · New modifier in "Implicit Arguments" to force an implicit argument to be maximally inserted. · New options Global and Local to "Implicit Arguments" for section surviving or non export outside module. · Level "constr" moved from 9 to 8. · Structure/Record now printed as Record (unless option Printing All is set). · Support for parametric notations defining constants. · Insertion of coercions below product types refrains to unfold constants (possible source of incompatibility). · New support for fix/cofix in notations. Tactic Language: · Second-order pattern-matching now working in Ltac "match" clauses (syntax for second-order unification variable is "@?X"). · Support for matching on let bindings in match context using syntax "H := body" or "H := body : type". · (?X ?Y) patterns now match any application instead of only unary applications (possible source of incompatibility). · Ltac accepts integer arguments (syntax is "ltac:nnn" for nnn an integer). · The general sequence tactical "expr_0 ; " is extended so that at most one expr_i may have the form "expr .." or just "..". Also, n can be different from the number of subgoals generated by expr_0. In this case, the value of expr (or idtac in case of just "..") is applied to the intermediate subgoals to make the number of tactics equal to the number of subgoals. · A name used as the name of the parameter of a lemma (like f in "apply f_equal with (f:=t)") is now interpreted as a ltac variable if such a variable exists (this is a possible source of incompatibility and it can be fixed by renaming the variables of a ltac function into names that do not clash with the lemmas parameter names used in the tactic). · New syntax "Ltac tac ::= ..." to rebind a tactic to a new expression. · "let rec ... in ... " now supported for expressions without explicit parameters; interpretation is lazy to the contrary of "let ... in ..."; hence, the "rec" keyword can be used to turn the argument of a "let ... in ..." into a lazy one. · Patterns for hypotheses types in "match goal" are now interpreted in type_scope. · A bound variable whose name is not used elsewhere now serves as metavariable in "match" and it gets instantiated by an identifier (allow e.g. to extract the name of a statement like "exists x, P x"). · New printing of Ltac call trace for better debugging. · The C-zar (formerly know as declarative) proof language is now properly documented. Tactics: · New tactics "apply -> term", "apply term in ident", "apply ", "++>" and "==>" are now right associative notations declared at level 55 in scope signature_scope. Their introduction may break existing scripts that defined them as notations with different levels. One can use ] to indicate that should not be unfolded during unification for morphism resolution, by default all constants are transparent. · The 's semantics change when rewriting with a lemma: it can rewrite two different instantiations of the lemma at once. Use for (almost) the usual semantics. will also try to rewrite under binders now, and can succeed on different terms than before. In particular, it will unify under let-bound variables. When called through , the semantics are unchanged though. · has different semantics when used with parametric morphism: it will try to find a relation on the parameters too. The behavior has also changed with respect to default relations: the most recently declared Setoid/Relation will be used, the documentation explains how to customize this behavior. · Parametric Relation and Morphism are declared differently, using the new commands, documented in the manual. · Setoid_Theory is now an alias to Equivalence, scripts building objects of type Setoid_Theory need to unfold (or ) the definitions of Reflexive, Symmetric and Transitive in order to get the same goals as before. Scripts which introduced variables explicitely will not break. · The order of subgoals when doing with side-conditions is now always the same: first the new goal, then the conditions. · New standard library modules Classes.Morphisms declares standard morphisms on refl/sym/trans relations. Classes.Morphisms_Prop declares morphisms on propositional connectives and Classes.Morphisms_Relations on generalized predicate connectives. Classes.Equivalence declares notations and tactics related to equivalences and Classes.SetoidTactics defines the setoid_replace tactics and some support for the "Add *" interface, notably the tactic applied automatically before each "Add Morphism" proof. · User-defined subrelations are supported, as well as higher-order morphisms and rewriting under binders. The tactic is also extensible entirely in Ltac. The documentation has been updated to cover these features. · and now support the modifier to select occurrences to rewrite, and both use the code, even when rewriting with leibniz equality if occurrences are specified. Extraction: · Improved behavior of the Caml extraction of modules: name clashes should not happen anymore. · The command Extract Inductive has now a syntax for infix notations. This allows in particular to map Coq lists and pairs onto Caml ones: Extract Inductive list => list " "(::)" ]. Extract Inductive prod => "(*)" . · In pattern matchings, a default pattern "| _ -> ..." is now used whenever possible if several branches are identical. For instance, functions corresponding to decidability of equalities are now linear instead of quadratic. · A new instruction Extraction Blacklist id1 .. idn allows to prevent filename conflits with existing code, for instance when extracting module List to Ocaml. CoqIDE: · CoqIDE font defaults to monospace so as indentation to be meaningful. · CoqIDE supports nested goals and any other kind of declaration in the middle of a proof. · Undoing non-tactic commands in CoqIDE works faster. · New CoqIDE menu for activating display of various implicit informations. · Added the possibility to choose the location of tabs in coqide: (in Edit->Preferences->Misc) · New Open and Save As dialogs in CoqIDE which filter *.v files. Tools: · New stand-alone .vo files verifier "coqchk". · Extended -I coqtop/coqc option to specify a logical dir: "-I dir -as coqdir". · New coqtop/coqc option -exclude-dir to exclude subdirs for option -R. · The binary "parser" has been renamed to "coq-parser". · coqdoc · Improved coqdoc and dump of globalization information to give more meta-information on identifiers. All categories of Coq definitions are supported, which makes typesetting trivial in the generated documentation. · A "--interpolate" option permits to use typesetting information from the typechecked part of the file to typeset identifiers appearing in Coq escapings inside the documentation. · Better handling of utf8 ("--utf8" option) and respect of spaces in the source. · Support for hyperlinking and indexing developments in the TeX output. · New option "color" of the coqdoc style file to render identifiers using colors. · Additional macros in the TeX ouput allowing to customize indentation and size of empty lines. New environment "coqdoccode" for Coq code. Miscellaneous: · Coq installation provides enough files so that Ocaml's extensions need not the Coq sources to be compiled (this assumes O'Caml 3.10 and Camlp5). · New commands "Set Whelp Server" and "Set Whelp Getter" to customize the Whelp search tool. · Syntax of "Test Printing Let ref" and "Test Printing If ref" changed into "Test Printing Let for ref" and "Test Printing If for ref". · An overhauled build system (new Makefiles); see dev/doc/build-system.txt. · Add -browser option to configure script. · Build a shared library for the C part of Coq, and use it by default on non-(Windows or MacOS) systems. Bytecode executables are now pure. The behaviour is configurable with -coqrunbyteflags, -coqtoolsbyteflags and -custom configure options. · Complexity tests can be

Coq Related Software