Tutorial.v

Description

TheCoqProofAssistantATutorialNovember21,20061Versionv8.1GérardHuet,GillesKahnandChristinePaulin MohringLogiCalProject1ThisresearchwaspartlysupportedbyISTworkinggroup“Types”Vv8.1,November21,2006cINRIA1999 2004(C OQ versions7.x)c2004 2006(C OQ v8.x)GettingstartedCOQ isaProofAssistantforaLogicalFrameworkknownastheCalculusofInductiveConstructions. Itallows the interactive construction of formal proofs, and also the manipulation of functional programsconsistentlywiththeirspecifications. Itrunsasacomputerprogramonmanyarchitectures. Itisavailablewithavarietyofuserinterfaces. ThepresentdocumentdoesnotattempttopresentacomprehensiveviewofallthepossibilitiesofCOQ,butrathertopresentinthemostelementarymanneratutorialonthebasicspecification language, called Gallina, in which formal axiomatisations may be developed, and on themain proof tools. For more advanced information, the reader could refer to the COQ Reference ManualortheCoq’Art,anewbookbyY.BertotandP.Castéranonpracticalusesofthe COQ system.Coq can be used from a standard teletype like shell window but preferably through the graphical1userinterfaceCoqIde .Instructionsoninstallationprocedures,aswellasmorecomprehensivedocumentation,maybefoundinthestandarddistributionofCOQ,whichmaybeobtainedfromCOQwebsitehttp://coq.inria.fr.In the following, we assume that COQ is called from a standard teletype like shell window. AllexamplesprecededbythepromptingsequenceCoq < representuserinput,terminatedbyaperiod ...

Informations

• Publié par: Unjio
• Nombre de lectures: 8
• Langue: English

Extrait

The Coq Proof Assistant

A Tutorial

November 21, 2006

Version v8.1 1

Gérard Huet, Gilles Kahn and Christine Paulin-Mohring

LogiCal Project

1 This research was partly supported by IST working group “Types”

Vv8.1,

November

21,

2006

OQ

 c INRIA 1999-2004 (C  c INRIA 2004-2006 (C OQ

versions versions

7.x) 8.x)

Getting started

C OQ the Calculus of Inductive Constructions. Itis a Proof Assistant for a Logical Framework known as allows the interactive construction of formal proofs, and also the manipulation of functional programs consistently with their specifications. It runs as a computer program on many architectures. It is available with a variety of user interfaces. The present document does not attempt to present a comprehensive view of all the possibilities of C OQ , but rather to present in the most elementary manner a tutorial on the basic specification language, called Gallina, in which formal axiomatisations may be developed, and on the main proof tools. For more advanced information, the reader could refer to the C OQ Reference Manual or theCoq’ArtY. Bertot and P. Castéran on practical uses of the C, a new book by OQ system. Coq can be used from a standard teletype-like shell window but preferably through the graphical user interface CoqIde 1 . Instructions on installation procedures, as well as more comprehensive documentation, may be found in the standard distribution of C OQ , which may be obtained from C OQ web sitehttp://coq.inria.fr. In the following, we assume that C OQ is called from a standard teletype-like shell window. All examples preceded by the prompting sequenceCoq <represent user input, terminated by a period. The following lines usually show C OQ ’s answer as it appears on the users screen. When used from a graphical user interface such as CoqIde, the prompt is not displayed: user input is given in one window and C OQ ’s answers are displayed in a different window. The sequence of such examples is a valid C OQ session, unless otherwise specified. version This of the tutorial has been prepared on a PC workstation running Linux. The standard invocation of C OQ delivers a message such as: unix:~> coqtop Welcome to Coq 8.0 (Mar 2004) Coq < The first line gives a banner stating the precise version of C OQ  should always returnused. You this banner when you report an anomaly to our hot-linelial.cniir.arfcoq-bugs@pauor on our bug- tracking system :http//coq.inria.fr/bin/coq-bugs:

1 Alternative graphical interfaces exist: Proof General and Pcoq. 3

4

Chapter 1

Basic Predicate Calculus

1.1 An overview of the specification language Gallina A formal development in Gallina consists in a sequence ofdeclarationsanddefinitions may also. You send C OQ commandswhich are not really part of the formal development, but correspond to information requests, or service routine invocations. For instance, the command: Coq < Quit. terminates the current session. 1.1.1 Declarations A declaration associates anamewith aspecification. A name corresponds roughly to an identifier in a programming language, i.e. to a string of letters, digits, and a few ASCII symbols like underscore (_) and prime (’ use case distinction, so that the names), starting with a letter. WeAandaare distinct. Certain strings are reserved as key-words of C OQ , and thus are forbidden as user identifiers. A specification is a formal expression which classifies the notion which is being declared. There are basically three kinds of specifications:logical propositions,mathematical collections, andabstract types. They are classified by the three basic sorts of the system, called respectivelyProp,Set, andType, which are themselves atomic abstract types. Every valid expressionein Gallina is associated with a specification, itself a valid expression, called itstypeτ(E). We writee:τ(E)for the judgment thateis of typeE. You may request C OQ to return to you the type of a valid expression by using the commandCheck: Coq < Check O. 2 || 0 < 0 : nat Thus we know that the identifierO(the name ‘O’, not to be confused with the numeral ‘0’ which is not a proper identifier!) is known in the current context, and that its type is the specificationnat. This specification is itself classified as a mathematical collection, as we may readily check: Coq < Check nat. 2 || 0 < nat : Set The specificationSetis an abstract type, one of the basic sorts of the Gallina language, whereas the notionsnatandOare notions which are defined in the arithmetic prelude, automatically loaded when running the C OQ system.

5

We start by introducing a so-called section name. The role of sections is to structure the modelisation by limiting the scope of parameters, hypotheses and definitions. It will also give a convenient way to reset part of the development. Coq < Section Declaration. 2 || 0 < With what we already know, we may now enter in the system a declaration, corresponding to the informal mathematicslet n be a natural number. Coq < Variable n : nat. 3 || 0 < n is assumed If we want to translate a more precise statement, such aslet n be a positive natural number, we have to add another declaration, which will declare explicitly the hypothesisPos_n, with specification the proper logical proposition: Coq < Hypothesis Pos n : (gt n 0). _ || 0 < _ 4 Pos n is assumed Indeed we may check that the relationgtis known with the right type in the current context: Coq < Check gt. 5 || 0 < gt : nat -> nat -> Prop which tells us thatgtis a function expecting two arguments of typenatin order to build a log- ical proposition. What happens here is similar to what we are used to in a functional programming language: we may compose the (specification) typenatwith the (abstract) typePropof logical propo- sitions through the arrow function constructor, in order to get a functional typenat->Prop: Coq < Check (nat -> Prop). 5 || 0 < nat -> Prop : Type which may be composed again withnatin order to obtain the typenat->nat->Propof binary relations over natural numbers. Actuallynat->nat->Propis an abbreviation fornat->(nat->Prop). Functional notions may be composed in the usual way. An expressionfof typeA→Bmay be applied to an expressioneof typeAin order to form the expression(f e)of typeB. Here we get that the expression(gt n)is well-formed of typenat->Prop, and thus that the expression(gt n O), which abbreviates((gt n) O), is a well-formed proposition. Coq < Check gt n O. 5 || 0 < n > 0 : Prop 1.1.2 Definitions The initial prelude contains a few arithmetic definitions:natis defined as a mathematical collection (typeSet), constantsO,S,plus, are defined as objects of types respectivelynat,nat->nat, and nat->nat->nat. You may introduce new definitions, which link a name to a well-typed value. For instance, we may introduce the constantoneas being defined to be equal to the successor of zero: Coq < Definition one := (S O). 5 || 0 < one is defined We may optionally indicate the required type:

6

Coq < Definition two : nat := S one. 6 || 0 < two is defined Actually C OQ allows several possible syntaxes: Coq < Definition three : nat := S two. 7 || 0 < three is defined Here is a way to define the doubling function, which expects an argumentmof typenatin order to build its result as(plus m m): Coq < Definition double (m:nat) := plus m m. 8 || 0 < double is defined This definition introduces the constantdoubledefined as the expressionfun m:nat => plus m m. The abstraction introduced byfun expression Theis explained as follows.fun x:A => eis well formed of typeA->Bin a context whenever the expressioneis well-formed of typeBin the given context to which we add the declaration thatxis of typeA. Herexis a bound, or dummy variable in the expression fun x:A => e. For instance we could as well have defineddoubleasfun n:nat => (plus n n). Bound (local) variables and free (global) variables may be mixed. For instance, we may define the function which adds the constantnto its argument as Coq < Definition add_n (m:nat) := plus m n. 9 || _ 0 < add n is defined However, note that here we may not rename the formal argumentmintonwithout capturing the free occurrence ofn, and thus changing the meaning of the defined notion. Binding operations are well known for instance in logic, where they are called quantifiers. Thus we may universally quantify a proposition such asm>in order to get a universal proposition0 ∀m∙m>0. Indeed this operator is available in C OQ , with the following syntax:forall m:nat, gt m O. Similarly to the case of the functional abstraction binding, we are obliged to declare explicitly the type of the quantified variable. We check: Coq < Check (forall m:nat, gt m 0). 10 || 0 < forall m : nat, m > 0 : Prop We may clean-up the development by removing the contents of the current section: Coq < Reset Declaration. 10 || 0 <

1.2 Introduction to the proof engine: Minimal Logic In the following, we are going to consider various propositions, built from atomic propositionsA,B,C. This may be done easily, by introducing these atoms as global variables declared of typeProp. It is easy to declare several names with the same specification: Coq < Section Minimal_Logic. 10 || 0 < Coq < Variables A B C : Prop. 11 || 0 < A is assumed B is assumed C is assumed We shall consider simple implications, such asA→B, read as “AimpliesB that we”. Remark overload the arrow symbol, which has been used above as the functionality type constructor, and which may be used as well as propositional connective: 7

Coq < Check (A -> B). 12 || 0 < A -> B : Prop Let us now embark on a simple proof. We want to prove the easy tautology((A→(B→C))→ (A→B)→(A→C) enter the proof engine by the command. WeGoal, followed by the conjecture we want to verify: Coq < Goal (A -> B -> C) -> (A -> B) -> A -> C. 12 || 0 < 1 subgoal A : Prop B : Prop C : Prop ============================ (A -> B -> C) -> (A -> B) -> A -> C The system displays the current goal below a double line, local hypotheses (there are none initially) being displayed above the line. We call the combination of local hypotheses with a goal ajudgmentWe. are now in an inner loop of the system, in proof mode. New commands are available in this mode, such astactics, which are proof combining primitives. A tactic operates on the current goal by attempting to construct a proof of the corresponding judgment, possibly from proofs of some hypothetical judgments, which are then added to the current list of conjectured judgments. For instance, theintrotactic is applicable to any judgment whose goal is an implication, by moving the proposition to the left of the application to the list of local hypotheses: Coq < intro H. 12 |Unnamed_thm| 1 < 1 subgoal A : Prop B : Prop C : Prop H : A -> B -> C ============================ (A -> B) -> A -> C Several introductions may be done in one step: Coq < intros H’ HA. 12 |Unnamed_thm| 2 < 1 subgoal A : Prop B : Prop C : Prop H : A -> B -> C H’ : A -> B HA : A ============================ C We notice thatC, the current goal, may be obtained from hypothesisH, provided the truth ofAand Bare established. The tacticapplyimplements this piece of reasoning: Coq < apply H. 12 |Unnamed_thm| 3 < 2 subgoals A : Prop B : Prop

8

C : Prop H : A -> B -> C H’ : A -> B HA : A ============================ A subgoal 2 is: B We are now in the situation where we have two judgments as conjectures that remain to be proved. Only the first is listed in full, for the others the system displays only the corresponding subgoal, without its local hypotheses list. Remark thatapplyhas kept the local hypotheses of its father judgment, which are still available for the judgments it generated. In order to solve the current goal, we just have to notice that it is exactly available as hypothesisHA: Coq < exact HA. 12 |Unnamed_thm| 4 < 1 subgoal A : Prop B : Prop C : Prop H : A -> B -> C H’ : A -> B HA : A ============================ B NowH 0 applies: Coq < apply H’. 12 |Unnamed_thm| 5 < 1 subgoal A : Prop B : Prop C : Prop H : A -> B -> C H’ : A -> B HA : A ============================ A And we may now conclude the proof as before, withexact HA.Actually, we may not bother with the nameHA, and just state that the current goal is solvable from the current local assumptions: Coq < assumption. 12 |Unnamed_thm| 6 < Proof completed. The proof is now finished. We may either discard it, by using the commandAbortwhich returns to the standard C OQ toplevel loop without further ado, or else save it as a lemma in the current context, y emmat _: under name sarivial l oq _ C < Save trivial lemma. 12 |Unnamed_thm| 7 < intro H. intros H’ HA. apply H. exact HA. apply H . ’ assumption. trivial lemma is defined _

9

As a comment, the system shows the proof script listing all tactic commands used in the proof. Let us redo the same proof with a few variations. First of all we may name the initial goal as a conjectured lemma: Coq < Lemma distr_impl : (A -> B -> C) -> (A -> B) -> A -> C. 13 || 0 < 1 subgoal A : Prop B : Prop C : Prop ============================ (A -> B -> C) -> (A -> B) -> A -> C Next, we may omit the names of local assumptions created by the introduction tactics, they can be automatically created by the proof engine as new non-clashing names. Coq < intros. 13 |distr_impl| 1 < 1 subgoal A : Prop B : Prop C : Prop H : A -> B -> C H0 : A -> B H1 : A ============================ C Theintrosarguments, effects as many individual applications oftactic, with no introas is legal. Then, we may compose several tactics together in sequence, or in parallel, throughtacticals, that is tactic combinators. The main constructions are the following: •T 1 ;T 2 (readT 1 thenT 2 ) applies tacticT 1 to the current goal, and then tacticT 2 to all the subgoals generated byT 1 . •T;[T 1 |T 2 |...|T n ]applies tacticTto the current goal, and then tacticT 1 to the first newly generated subgoal, ...,T n to the nth. We may thus complete the proof ofdistr_implwith one composite tactic: Coq < apply H; [ assumption | apply H0; assumption ]. 13 |distr_impl| 2 < Proof completed. Let us now save lemmadistr_impl: Coq < Save. 13 |distr_impl| 3 < intros. apply H; [ assumption | apply H0; assumption ]. _ p is distr im l defined HereSaveneeds no argument, since we gave the namedistr_implin advance; it is however possible to override the given name by giving a different argument to commandSave. Actually, such an easy combination of tacticsintro,applyandassumptionmay be found com- pletely automatically by an automatic tactic, calledauto, without user guidance: Coq < Lemma distr_imp : (A -> B -> C) -> (A -> B) -> A -> C. 14 || 0 < 1 subgoal

10

A : Prop B : Prop C : Prop ============================ (A -> B -> C) -> (A -> B) -> A -> C Coq < auto. 14 |distr_imp| 1 < Proof completed. This time, we do not save the proof, we just discard it with theAbortcommand: Coq < Abort. 14 |distr_imp| 2 < Current goal aborted At any point during a proof, we may useAbortto exit the proof mode and go back to Coq’s main loop. We may also useRestart may also use Weto restart from scratch the proof of the same lemma. Undoto backtrack one step, and more generallyUndo nto backtrack n steps. We end this section by showing a useful command,Inspect n., which inspects the global C OQ en- vironment, showing the lastndeclared notions: Coq < Inspect 3. 14 || 0 < *** [C : Prop] _lemma : (A -> B -> C) -> (A -> B) -trivial > A -> C distr_impl : (A -> B -> C) -> (A -> B) -> A -> C The declarations, whether global parameters or axioms, are shown preceded by***; definitions and lemmas are stated with their specification, but their value (or proof-term) is omitted.

1.3 Propositional Calculus 1.3.1 Conjunction We have seen howintroandapplytactics could be combined in order to prove implicational state- ments. More generally, C OQ favors a style of reasoning, calledNatural Deduction, which decomposes reasoning into so calledintroduction rules, which tell how to prove a goal whose main operator is a given propositional connective, andelimination rules, which tell how to use an hypothesis whose main opera- tor is the propositional connective. Let us show how to use these ideas for the propositional connectives /\and\/. Coq < Lemma and commutative : A /\ B -> B /\ A. _ 14 || 0 < 1 subgoal A : Prop B : Prop C : Prop ============================ A /\ B -> B /\ A Coq < intro. 14 |and commutative| 1 < 1 subgoal _ A : Prop B : Prop C : Prop H : A /\ B ============================ B /\ A

11