Mercurial > cpdt > repo
comparison src/StackMachine.v @ 399:5986e9fd40b5
Start figuring out which coqdoc changes will be needed to produce a pretty final version
author | Adam Chlipala <adam@chlipala.net> |
---|---|
date | Fri, 08 Jun 2012 11:25:11 -0400 |
parents | 05efde66559d |
children | 539ed97750bb |
comparison
equal
deleted
inserted
replaced
398:05efde66559d | 399:5986e9fd40b5 |
---|---|
17 | 17 |
18 | 18 |
19 (** %\chapter{Some Quick Examples}% *) | 19 (** %\chapter{Some Quick Examples}% *) |
20 | 20 |
21 | 21 |
22 (** I will start off by jumping right in to a fully-worked set of examples, building certified compilers from increasingly complicated source languages to stack machines. We will meet a few useful tactics and see how they can be used in manual proofs, and we will also see how easily these proofs can be automated instead. This chapter is not meant to give full explanations of the features that are employed. Rather, it is meant more as an advertisement of what is possible. Later chapters will introduce all of the concepts in bottom-up fashion. | 22 (** I will start off by jumping right in to a fully worked set of examples, building certified compilers from increasingly complicated source languages to stack machines. We will meet a few useful tactics and see how they can be used in manual proofs, and we will also see how easily these proofs can be automated instead. This chapter is not meant to give full explanations of the features that are employed. Rather, it is meant more as an advertisement of what is possible. Later chapters will introduce all of the concepts in bottom-up fashion. |
23 | 23 |
24 As always, you can step through the source file %\texttt{%#<tt>#StackMachine.v#</tt>#%}% for this chapter interactively in Proof General. Alternatively, to get a feel for the whole lifecycle of creating a Coq development, you can enter the pieces of source code in this chapter in a new %\texttt{%#<tt>#.v#</tt>#%}% file in an Emacs buffer. If you do the latter, include two lines | 24 As always, you can step through the source file %\texttt{%#<tt>#StackMachine.v#</tt>#%}% for this chapter interactively in Proof General. Alternatively, to get a feel for the whole lifecycle of creating a Coq development, you can enter the pieces of source code in this chapter in a new %\texttt{%#<tt>#.v#</tt>#%}% file in an Emacs buffer. If you do the latter, include two lines |
25 | 25 |
26 %\index{Vernacular commands!Require}%[Require Import Bool] #<span class="inlinecode"><span class="id" type="var">#%\coqdocconstructor{%Arith%}%#</span></span># #<span class="inlinecode"><span class="id" type="var">#%\coqdocconstructor{%List%}%#</span></span># [CpdtTactics.] | 26 %\index{Vernacular commands!Require}%[Require Import Bool Arith List CpdtTactics.] |
27 | 27 |
28 %\noindent{}%and | 28 %\noindent{}%and |
29 | 29 |
30 %\index{Vernacular commands!Set Implicit Arguments}%[Set Implicit] #<span class="inlinecode"><span class="id" type="keyword">#%\coqdockw{%Arguments%}%#</span></span>#[.] | 30 %\index{Vernacular commands!Set Implicit Arguments}%[Set Implicit Arguments.] |
31 | 31 |
32 %\noindent{}%at the start of the file, to match some code hidden in this rendering of the chapter source. In general, similar commands will be hidden in the book rendering of each chapter's source code, so you will need to insert them in from-scratch replayings of the code that is presented. To be more specific, every chapter begins with some imports of other modules, followed by [Set Implicit] #<span class="inlinecode"><span class="id" type="keyword">#%\coqdockw{%Arguments%}%#</span></span>#[.], where the latter affects the default behavior of definitions regarding type inference. | 32 %\noindent{}%at the start of the file, to match some code hidden in this rendering of the chapter source. In general, similar commands will be hidden in the book rendering of each chapter's source code, so you will need to insert them in from-scratch replayings of the code that is presented. To be more specific, every chapter begins with some imports of other modules, followed by [Set Implicit Arguments.], where the latter affects the default behavior of definitions regarding type inference. |
33 *) | 33 *) |
34 | 34 |
35 | 35 |
36 (** * Arithmetic Expressions Over Natural Numbers *) | 36 (** * Arithmetic Expressions Over Natural Numbers *) |
37 | 37 |
62 | Plus => plus | 62 | Plus => plus |
63 | Times => mult | 63 | Times => mult |
64 end. | 64 end. |
65 | 65 |
66 (** The meaning of a binary operator is a binary function over naturals, defined with pattern-matching notation analogous to the %\texttt{%#<tt>#case#</tt>#%}% and %\texttt{%#<tt>#match#</tt>#%}% of ML and Haskell, and referring to the functions [plus] and [mult] from the Coq standard library. The keyword [Definition] is Coq's all-purpose notation for binding a term of the programming language to a name, with some associated syntactic sugar, like the notation we see here for defining a function. That sugar could be expanded to yield this definition: | 66 (** The meaning of a binary operator is a binary function over naturals, defined with pattern-matching notation analogous to the %\texttt{%#<tt>#case#</tt>#%}% and %\texttt{%#<tt>#match#</tt>#%}% of ML and Haskell, and referring to the functions [plus] and [mult] from the Coq standard library. The keyword [Definition] is Coq's all-purpose notation for binding a term of the programming language to a name, with some associated syntactic sugar, like the notation we see here for defining a function. That sugar could be expanded to yield this definition: |
67 | |
68 [[ | 67 [[ |
69 Definition binopDenote : binop -> nat -> nat -> nat := fun (b : binop) => | 68 Definition binopDenote : binop -> nat -> nat -> nat := fun (b : binop) => |
70 match b with | 69 match b with |
71 | Plus => plus | 70 | Plus => plus |
72 | Times => mult | 71 | Times => mult |
73 end. | 72 end. |
74 | |
75 ]] | 73 ]] |
76 | 74 |
77 In this example, we could also omit all of the type annotations, arriving at: | 75 In this example, we could also omit all of the type annotations, arriving at: |
78 | |
79 [[ | 76 [[ |
80 Definition binopDenote := fun b => | 77 Definition binopDenote := fun b => |
81 match b with | 78 match b with |
82 | Plus => plus | 79 | Plus => plus |
83 | Times => mult | 80 | Times => mult |
84 end. | 81 end. |
85 | |
86 ]] | 82 ]] |
87 | 83 |
88 Languages like Haskell and ML have a convenient %\index{principal types}\index{type inference}%_principal types_ property, which gives us strong guarantees about how effective type inference will be. Unfortunately, Coq's type system is so expressive that any kind of %``%#"#complete#"#%''% type inference is impossible, and the task even seems to be hard heuristically in practice. Nonetheless, Coq includes some very helpful heuristics, many of them copying the workings of Haskell and ML type-checkers for programs that fall in simple fragments of Coq's language. | 84 Languages like Haskell and ML have a convenient %\index{principal types}\index{type inference}%_principal types_ property, which gives us strong guarantees about how effective type inference will be. Unfortunately, Coq's type system is so expressive that any kind of %``%#"#complete#"#%''% type inference is impossible, and the task even seems to be hard heuristically in practice. Nonetheless, Coq includes some very helpful heuristics, many of them copying the workings of Haskell and ML type-checkers for programs that fall in simple fragments of Coq's language. |
89 | 85 |
90 This is as good a time as any to mention the preponderance of different languages associated with Coq. The theoretical foundation of Coq is a formal system called the %\index{Calculus of Inductive Constructions}\index{CIC|see{Calculus of Inductive Constructions}}%_Calculus of Inductive Constructions (CIC)_ %\cite{CIC}%, which is an extension of the older %\index{Calculus of Constructions}\index{CoC|see{Calculus of Constructions}}%_Calculus of Constructions (CoC)_ %\cite{CoC}%. CIC is quite a spartan foundation, which is helpful for proving metatheory but not so helpful for real development. Still, it is nice to know that it has been proved that CIC enjoys properties like %\index{strong normalization}%_strong normalization_ %\cite{CIC}%, meaning that every program (and, more importantly, every proof term) terminates; and %\index{relative consistency}%_relative consistency_ %\cite{SetsInTypes}% with systems like versions of %\index{Zermelo-Fraenkel set theory}%Zermelo-Fraenkel set theory, which roughly means that you can believe that Coq proofs mean that the corresponding propositions are %``%#"#really true,#"#%''% if you believe in set theory. | 86 This is as good a time as any to mention the preponderance of different languages associated with Coq. The theoretical foundation of Coq is a formal system called the%\index{Calculus of Inductive Constructions}\index{CIC|see{Calculus of Inductive Constructions}}% _Calculus of Inductive Constructions_ (CIC)%~\cite{CIC}%, which is an extension of the older%\index{Calculus of Constructions}\index{CoC|see{Calculus of Constructions}}% _Calculus of Constructions_ (CoC)%~\cite{CoC}%. CIC is quite a spartan foundation, which is helpful for proving metatheory but not so helpful for real development. Still, it is nice to know that it has been proved that CIC enjoys properties like%\index{strong normalization}% _strong normalization_ %\cite{CIC}%, meaning that every program (and, more importantly, every proof term) terminates; and%\index{relative consistency}% _relative consistency_ %\cite{SetsInTypes}% with systems like versions of %\index{Zermelo-Fraenkel set theory}%Zermelo-Fraenkel set theory, which roughly means that you can believe that Coq proofs mean that the corresponding propositions are %``%#"#really true,#"#%''% if you believe in set theory. |
91 | 87 |
92 Coq is actually based on an extension of CIC called %\index{Gallina}%_Gallina_. The text after the [:=] and before the period in the last code example is a term of Gallina. Gallina adds many useful features that are not compiled internally to more primitive CIC features. The important metatheorems about CIC have not been extended to the full breadth of these features, but most Coq users do not seem to lose much sleep over this omission. | 88 Coq is actually based on an extension of CIC called%\index{Gallina}% _Gallina_. The text after the [:=] and before the period in the last code example is a term of Gallina. Gallina adds many useful features that are not compiled internally to more primitive CIC features. The important metatheorems about CIC have not been extended to the full breadth of these features, but most Coq users do not seem to lose much sleep over this omission. |
93 | 89 |
94 Next, there is %\index{Ltac}%_Ltac_, Coq's domain-specific language for writing proofs and decision procedures. We will see some basic examples of Ltac later in this chapter, and much of this book is devoted to more involved Ltac examples. | 90 Next, there is%\index{Ltac}% _Ltac_, Coq's domain-specific language for writing proofs and decision procedures. We will see some basic examples of Ltac later in this chapter, and much of this book is devoted to more involved Ltac examples. |
95 | 91 |
96 Finally, commands like [Inductive] and [Definition] are part of %\index{Vernacular commands}%_the Vernacular_, which includes all sorts of useful queries and requests to the Coq system. Every Coq source file is a series of vernacular commands, where many command forms take arguments that are Gallina or Ltac programs. (Actually, Coq source files are more like _trees_ of vernacular commands, thanks to various nested scoping constructs.) | 92 Finally, commands like [Inductive] and [Definition] are part of%\index{Vernacular commands}% _the Vernacular_, which includes all sorts of useful queries and requests to the Coq system. Every Coq source file is a series of vernacular commands, where many command forms take arguments that are Gallina or Ltac programs. (Actually, Coq source files are more like _trees_ of vernacular commands, thanks to various nested scoping constructs.) |
97 | 93 |
98 %\medskip% | 94 %\medskip% |
99 | 95 |
100 We can give a simple definition of the meaning of an expression:%\index{Vernacular commands!Fixpoint}% *) | 96 We can give a simple definition of the meaning of an expression:%\index{Vernacular commands!Fixpoint}% *) |
101 | 97 |
201 (* begin hide *) | 197 (* begin hide *) |
202 Abort. | 198 Abort. |
203 (* end hide *) | 199 (* end hide *) |
204 (* begin thide *) | 200 (* begin thide *) |
205 | 201 |
206 (** Though a pencil-and-paper proof might clock out at this point, writing %``%#"#by a routine induction on [e],#"#%''% it turns out not to make sense to attack this proof directly. We need to use the standard trick of %\index{strengthening the induction hypothesis}%_strengthening the induction hypothesis_. We do that by proving an auxiliary lemma, using the command [Lemma] that is a synonym for [Theorem], conventionally used for less important theorems that appear in the proofs of primary theorems.%\index{Vernacular commands!Lemma}% *) | 202 (** Though a pencil-and-paper proof might clock out at this point, writing %``%#"#by a routine induction on [e],#"#%''% it turns out not to make sense to attack this proof directly. We need to use the standard trick of%\index{strengthening the induction hypothesis}% _strengthening the induction hypothesis_. We do that by proving an auxiliary lemma, using the command [Lemma] that is a synonym for [Theorem], conventionally used for less important theorems that appear in the proofs of primary theorems.%\index{Vernacular commands!Lemma}% *) |
207 | 203 |
208 Lemma compile_correct' : forall e p s, | 204 Lemma compile_correct' : forall e p s, |
209 progDenote (compile e ++ p) s = progDenote p (expDenote e :: s). | 205 progDenote (compile e ++ p) s = progDenote p (expDenote e :: s). |
210 | 206 |
211 (** After the period in the [Lemma] command, we are in %\index{interactive proof-editing mode}%_the interactive proof-editing mode_. We find ourselves staring at this ominous screen of text: | 207 (** After the period in the [Lemma] command, we are in%\index{interactive proof-editing mode}% _the interactive proof-editing mode_. We find ourselves staring at this ominous screen of text: |
212 | 208 |
213 [[ | 209 [[ |
214 1 subgoal | 210 1 subgoal |
215 | 211 |
216 ============================ | 212 ============================ |
221 | 217 |
222 Coq seems to be restating the lemma for us. What we are seeing is a limited case of a more general protocol for describing where we are in a proof. We are told that we have a single subgoal. In general, during a proof, we can have many pending %\index{subgoals}%subgoals, each of which is a logical proposition to prove. Subgoals can be proved in any order, but it usually works best to prove them in the order that Coq chooses. | 218 Coq seems to be restating the lemma for us. What we are seeing is a limited case of a more general protocol for describing where we are in a proof. We are told that we have a single subgoal. In general, during a proof, we can have many pending %\index{subgoals}%subgoals, each of which is a logical proposition to prove. Subgoals can be proved in any order, but it usually works best to prove them in the order that Coq chooses. |
223 | 219 |
224 Next in the output, we see our single subgoal described in full detail. There is a double-dashed line, above which would be our free variables and %\index{hypotheses}%hypotheses, if we had any. Below the line is the %\index{conclusion}%conclusion, which, in general, is to be proved from the hypotheses. | 220 Next in the output, we see our single subgoal described in full detail. There is a double-dashed line, above which would be our free variables and %\index{hypotheses}%hypotheses, if we had any. Below the line is the %\index{conclusion}%conclusion, which, in general, is to be proved from the hypotheses. |
225 | 221 |
226 We manipulate the proof state by running commands called %\index{tactics}%_tactics_. Let us start out by running one of the most important tactics:%\index{tactics!induction}% | 222 We manipulate the proof state by running commands called%\index{tactics}% _tactics_. Let us start out by running one of the most important tactics:%\index{tactics!induction}% |
227 *) | 223 *) |
228 | 224 |
229 induction e. | 225 induction e. |
230 | 226 |
231 (** We declare that this proof will proceed by induction on the structure of the expression [e]. This swaps out our initial subgoal for two new subgoals, one for each case of the inductive proof: | 227 (** We declare that this proof will proceed by induction on the structure of the expression [e]. This swaps out our initial subgoal for two new subgoals, one for each case of the inductive proof: |
269 We see that [intros] changes [forall]-bound variables at the beginning of a goal into free variables. | 265 We see that [intros] changes [forall]-bound variables at the beginning of a goal into free variables. |
270 | 266 |
271 To progress further, we need to use the definitions of some of the functions appearing in the goal. The [unfold] tactic replaces an identifier with its definition.%\index{tactics!unfold}% | 267 To progress further, we need to use the definitions of some of the functions appearing in the goal. The [unfold] tactic replaces an identifier with its definition.%\index{tactics!unfold}% |
272 *) | 268 *) |
273 | 269 |
274 (* begin hide *) | |
275 unfold compile. | 270 unfold compile. |
276 (* end hide *) | |
277 (** %\coqdockw{unfold} \coqdocdefinition{compile}.%#<tt>unfold compile.</tt># *) | |
278 (** [[ | 271 (** [[ |
279 n : nat | 272 n : nat |
280 s : stack | 273 s : stack |
281 p : list instr | 274 p : list instr |
282 ============================ | 275 ============================ |
284 progDenote p (expDenote (Const n) :: s) | 277 progDenote p (expDenote (Const n) :: s) |
285 | 278 |
286 ]] | 279 ]] |
287 *) | 280 *) |
288 | 281 |
289 (* begin hide *) | |
290 unfold expDenote. | 282 unfold expDenote. |
291 (* end hide *) | |
292 (** %\coqdockw{unfold} \coqdocdefinition{expDenote}.%#<tt>unfold expDenote.</tt># *) | |
293 (** [[ | 283 (** [[ |
294 n : nat | 284 n : nat |
295 s : stack | 285 s : stack |
296 p : list instr | 286 p : list instr |
297 ============================ | 287 ============================ |
299 | 289 |
300 ]] | 290 ]] |
301 | 291 |
302 We only need to unfold the first occurrence of [progDenote] to prove the goal. An [at] clause used with [unfold] specifies a particular occurrence of an identifier to unfold, where we count occurrences from left to right.%\index{tactics!unfold}% *) | 292 We only need to unfold the first occurrence of [progDenote] to prove the goal. An [at] clause used with [unfold] specifies a particular occurrence of an identifier to unfold, where we count occurrences from left to right.%\index{tactics!unfold}% *) |
303 | 293 |
304 (* begin hide *) | |
305 unfold progDenote at 1. | 294 unfold progDenote at 1. |
306 (* end hide *) | |
307 (** %\coqdockw{unfold} \coqdocdefinition{progDenote} \coqdoctac{at} 1.%#<tt>unfold progDenote at 1.</tt># *) | |
308 (** [[ | 295 (** [[ |
309 n : nat | 296 n : nat |
310 s : stack | 297 s : stack |
311 p : list instr | 298 p : list instr |
312 ============================ | 299 ============================ |
322 end) ((iConst n :: nil) ++ p) s = | 309 end) ((iConst n :: nil) ++ p) s = |
323 progDenote p (n :: s) | 310 progDenote p (n :: s) |
324 | 311 |
325 ]] | 312 ]] |
326 | 313 |
327 This last [unfold] has left us with an anonymous fixpoint version of [progDenote], which will generally happen when unfolding recursive definitions. Note that Coq has automatically renamed the [fix] arguments [p] and [s] to [p0] and [s0], to avoid clashes with our local free variables. There is also a subterm %\coqdocconstructor{None} (\coqdocvar{A}:=\coqdocdefinition{stack})%#<tt>None (A:=stack)</tt>#, which has an annotation specifying that the type of the term ought to be [option A]. This is phrased as an explicit instantiation of a named type parameter [A] from the definition of [option]. | 314 This last [unfold] has left us with an anonymous fixpoint version of [progDenote], which will generally happen when unfolding recursive definitions. Note that Coq has automatically renamed the [fix] arguments [p] and [s] to [p0] and [s0], to avoid clashes with our local free variables. There is also a subterm [None (A:=stack)], which has an annotation specifying that the type of the term ought to be [option A]. This is phrased as an explicit instantiation of a named type parameter [A] from the definition of [option]. |
328 | 315 |
329 Fortunately, in this case, we can eliminate the complications of anonymous recursion right away, since the structure of the argument ([iConst n :: nil) ++ p] is known, allowing us to simplify the internal pattern match with the [simpl] tactic, which applies the same reduction strategy that we used earlier with [Eval] (and whose details we still postpone).%\index{tactics!simpl}% | 316 Fortunately, in this case, we can eliminate the complications of anonymous recursion right away, since the structure of the argument ([iConst n :: nil) ++ p] is known, allowing us to simplify the internal pattern match with the [simpl] tactic, which applies the same reduction strategy that we used earlier with [Eval] (and whose details we still postpone).%\index{tactics!simpl}% |
330 *) | 317 *) |
331 | 318 |
332 simpl. | 319 simpl. |
349 ]] | 336 ]] |
350 | 337 |
351 Now we can unexpand the definition of [progDenote]:%\index{tactics!fold}% | 338 Now we can unexpand the definition of [progDenote]:%\index{tactics!fold}% |
352 *) | 339 *) |
353 | 340 |
354 (* begin hide *) | |
355 fold progDenote. | 341 fold progDenote. |
356 (* end hide *) | |
357 (** %\coqdockw{fold} \coqdocdefinition{progDenote}.%#<tt>fold progDenote.</tt># *) | |
358 (** [[ | 342 (** [[ |
359 n : nat | 343 n : nat |
360 s : stack | 344 s : stack |
361 p : list instr | 345 p : list instr |
362 ============================ | 346 ============================ |
386 | 370 |
387 ]] | 371 ]] |
388 | 372 |
389 We see our first example of %\index{hypotheses}%hypotheses above the double-dashed line. They are the inductive hypotheses [IHe1] and [IHe2] corresponding to the subterms [e1] and [e2], respectively. | 373 We see our first example of %\index{hypotheses}%hypotheses above the double-dashed line. They are the inductive hypotheses [IHe1] and [IHe2] corresponding to the subterms [e1] and [e2], respectively. |
390 | 374 |
391 We start out the same way as before, introducing new free variables and unfolding and folding the appropriate definitions. The seemingly frivolous [unfold]/%\coqdockw{fold}%#<tt>fold</tt># pairs are actually accomplishing useful work, because [unfold] will sometimes perform easy simplifications. %\index{tactics!intros}\index{tactics!unfold}\index{tactics!fold}% *) | 375 We start out the same way as before, introducing new free variables and unfolding and folding the appropriate definitions. The seemingly frivolous [unfold]/[fold] pairs are actually accomplishing useful work, because [unfold] will sometimes perform easy simplifications. %\index{tactics!intros}\index{tactics!unfold}\index{tactics!fold}% *) |
392 | 376 |
393 intros. | 377 intros. |
394 (* begin hide *) | |
395 unfold compile. | 378 unfold compile. |
396 fold compile. | 379 fold compile. |
397 unfold expDenote. | 380 unfold expDenote. |
398 fold expDenote. | 381 fold expDenote. |
399 (* end hide *) | |
400 (** %\coqdockw{unfold} \coqdocdefinition{compile}. | |
401 \coqdockw{fold} \coqdocdefinition{compile}. | |
402 \coqdockw{unfold} \coqdocdefinition{expDenote}. | |
403 \coqdockw{fold} \coqdocdefinition{expDenote}.% | |
404 #<tt>unfold compile. fold compile. unfold expDenote. fold expDenote.</tt># *) | |
405 | 382 |
406 (** Now we arrive at a point where the tactics we have seen so far are insufficient. No further definition unfoldings get us anywhere, so we will need to try something different. | 383 (** Now we arrive at a point where the tactics we have seen so far are insufficient. No further definition unfoldings get us anywhere, so we will need to try something different. |
407 | 384 |
408 [[ | 385 [[ |
409 b : binop | 386 b : binop |
429 app_assoc_reverse | 406 app_assoc_reverse |
430 : forall (A : Type) (l m n : list A), (l ++ m) ++ n = l ++ m ++ n | 407 : forall (A : Type) (l m n : list A), (l ++ m) ++ n = l ++ m ++ n |
431 | 408 |
432 ]] | 409 ]] |
433 | 410 |
434 If we did not already know the name of the theorem, we could use the %\index{Vernacular commands!SearchRewrite}\coqdockw{%#<tt>#SearchRewrite#</tt>#%}% command to find it, based on a pattern that we would like to rewrite: *) | 411 If we did not already know the name of the theorem, we could use the %\index{Vernacular commands!SearchRewrite}%[SearchRewrite] command to find it, based on a pattern that we would like to rewrite: *) |
435 | 412 |
436 (* begin hide *) | |
437 SearchRewrite ((_ ++ _) ++ _). | 413 SearchRewrite ((_ ++ _) ++ _). |
438 (* end hide *) | |
439 (** %\coqdockw{%#<tt>#SearchRewrite#</tt>#%}% [((_ ++ _) ++ _).] *) | |
440 (** [[ | 414 (** [[ |
441 app_assoc_reverse: | 415 app_assoc_reverse: |
442 forall (A : Type) (l m n : list A), (l ++ m) ++ n = l ++ m ++ n | 416 forall (A : Type) (l m n : list A), (l ++ m) ++ n = l ++ m ++ n |
443 ]] | 417 ]] |
444 %\vspace{-.25in}% | 418 %\vspace{-.25in}% |
479 ]] | 453 ]] |
480 | 454 |
481 Now we can apply a similar sequence of tactics to the one that ended the proof of the first case.%\index{tactics!unfold}\index{tactics!simpl}\index{tactics!fold}\index{tactics!reflexivity}% | 455 Now we can apply a similar sequence of tactics to the one that ended the proof of the first case.%\index{tactics!unfold}\index{tactics!simpl}\index{tactics!fold}\index{tactics!reflexivity}% |
482 *) | 456 *) |
483 | 457 |
484 (* begin hide *) | |
485 unfold progDenote at 1. | 458 unfold progDenote at 1. |
486 simpl. | 459 simpl. |
487 fold progDenote. | 460 fold progDenote. |
488 reflexivity. | 461 reflexivity. |
489 (* end hide *) | |
490 (** %\coqdockw{unfold} \coqdocdefinition{progDenote} \coqdoctac{at} 1. \coqdockw{simpl}. \coqdockw{fold} \coqdocdefinition{progDenote}. \coqdockw{reflexivity}.%#<tt>unfold progDenote at 1. simpl. fold progDenote. reflexivity.</tt># *) | |
491 | 462 |
492 (** And the proof is completed, as indicated by the message: *) | 463 (** And the proof is completed, as indicated by the message: *) |
493 | 464 |
494 (** %\coqdockw{Proof} \coqdockw{completed}.%#<tt>Proof completed.</tt># *) | 465 (** |
466 << | |
467 Proof completed. | |
468 >> | |
469 *) | |
495 | 470 |
496 (** And there lies our first proof. Already, even for simple theorems like this, the final proof script is unstructured and not very enlightening to readers. If we extend this approach to more serious theorems, we arrive at the unreadable proof scripts that are the favorite complaints of opponents of tactic-based proving. Fortunately, Coq has rich support for scripted automation, and we can take advantage of such a scripted tactic (defined elsewhere) to make short work of this lemma. We abort the old proof attempt and start again.%\index{Vernacular commands!Abort}% | 471 (** And there lies our first proof. Already, even for simple theorems like this, the final proof script is unstructured and not very enlightening to readers. If we extend this approach to more serious theorems, we arrive at the unreadable proof scripts that are the favorite complaints of opponents of tactic-based proving. Fortunately, Coq has rich support for scripted automation, and we can take advantage of such a scripted tactic (defined elsewhere) to make short work of this lemma. We abort the old proof attempt and start again.%\index{Vernacular commands!Abort}% |
497 *) | 472 *) |
498 | 473 |
499 Abort. | 474 Abort. |
505 induction e; crush. | 480 induction e; crush. |
506 Qed. | 481 Qed. |
507 | 482 |
508 (** We need only to state the basic inductive proof scheme and call a tactic that automates the tedious reasoning in between. In contrast to the period tactic terminator from our last proof, the %\index{tactics!semicolon}%semicolon tactic separator supports structured, compositional proofs. The tactic [t1; t2] has the effect of running [t1] and then running [t2] on each remaining subgoal. The semicolon is one of the most fundamental building blocks of effective proof automation. The period terminator is very useful for exploratory proving, where you need to see intermediate proof states, but final proofs of any serious complexity should have just one period, terminating a single compound tactic that probably uses semicolons. | 483 (** We need only to state the basic inductive proof scheme and call a tactic that automates the tedious reasoning in between. In contrast to the period tactic terminator from our last proof, the %\index{tactics!semicolon}%semicolon tactic separator supports structured, compositional proofs. The tactic [t1; t2] has the effect of running [t1] and then running [t2] on each remaining subgoal. The semicolon is one of the most fundamental building blocks of effective proof automation. The period terminator is very useful for exploratory proving, where you need to see intermediate proof states, but final proofs of any serious complexity should have just one period, terminating a single compound tactic that probably uses semicolons. |
509 | 484 |
510 The [crush] tactic comes from the library associated with this book and is not part of the Coq standard library. The book's library contains a number of other tactics that are especially helpful in highly-automated proofs. | 485 The [crush] tactic comes from the library associated with this book and is not part of the Coq standard library. The book's library contains a number of other tactics that are especially helpful in highly automated proofs. |
511 | 486 |
512 The %\index{Vernacular commands!Qed}%[Qed] command checks that the proof is finished and, if so, saves it. The tactic commands we have written above are an example of a _proof script_, or a series of Ltac programs; while [Qed] uses the result of the script to generate a _proof term_, a well-typed term of Gallina. To believe that a theorem is true, we only need to trust that the (relatively simple) checker for proof terms is correct; the use of proof scripts is immaterial. Part I of this book will introduce the principles behind encoding all proofs as terms of Gallina. | 487 The %\index{Vernacular commands!Qed}%[Qed] command checks that the proof is finished and, if so, saves it. The tactic commands we have written above are an example of a _proof script_, or a series of Ltac programs; while [Qed] uses the result of the script to generate a _proof term_, a well-typed term of Gallina. To believe that a theorem is true, we only need to trust that the (relatively simple) checker for proof terms is correct; the use of proof scripts is immaterial. Part I of this book will introduce the principles behind encoding all proofs as terms of Gallina. |
513 | 488 |
514 The proof of our main theorem is now easy. We prove it with four period-terminated tactics, though separating them with semicolons would work as well; the version here is easier to step through.%\index{tactics!intros}% *) | 489 The proof of our main theorem is now easy. We prove it with four period-terminated tactics, though separating them with semicolons would work as well; the version here is easier to step through.%\index{tactics!intros}% *) |
515 | 490 |
585 | 560 |
586 The inuitive explanation of [tbinop] is that a [tbinop t1 t2 t] is a binary operator whose operands should have types [t1] and [t2], and whose result has type [t]. For instance, constructor [TLt] (for less-than comparison of numbers) is assigned type [tbinop Nat Nat Bool], meaning the operator's arguments are naturals and its result is boolean. The type of [TEq] introduces a small bit of additional complication via polymorphism: we want to allow equality comparison of any two values of any type, as long as they have the _same_ type. | 561 The inuitive explanation of [tbinop] is that a [tbinop t1 t2 t] is a binary operator whose operands should have types [t1] and [t2], and whose result has type [t]. For instance, constructor [TLt] (for less-than comparison of numbers) is assigned type [tbinop Nat Nat Bool], meaning the operator's arguments are naturals and its result is boolean. The type of [TEq] introduces a small bit of additional complication via polymorphism: we want to allow equality comparison of any two values of any type, as long as they have the _same_ type. |
587 | 562 |
588 ML and Haskell have indexed algebraic datatypes. For instance, their list types are indexed by the type of data that the list carries. However, compared to Coq, ML and Haskell 98 place two important restrictions on datatype definitions. | 563 ML and Haskell have indexed algebraic datatypes. For instance, their list types are indexed by the type of data that the list carries. However, compared to Coq, ML and Haskell 98 place two important restrictions on datatype definitions. |
589 | 564 |
590 First, the indices of the range of each data constructor must be type variables bound at the top level of the datatype definition. There is no way to do what we did here, where we, for instance, say that [TPlus] is a constructor building a [tbinop] whose indices are all fixed at [Nat]. %\index{generalized algebraic datatypes}\index{GADTs|see{generalized algebraic datatypes}}%_Generalized algebraic datatypes (GADTs)_ %\cite{GADT}% are a popular feature in %\index{GHC Haskell}%GHC Haskell and other languages that removes this first restriction. | 565 First, the indices of the range of each data constructor must be type variables bound at the top level of the datatype definition. There is no way to do what we did here, where we, for instance, say that [TPlus] is a constructor building a [tbinop] whose indices are all fixed at [Nat]. %\index{generalized algebraic datatypes}\index{GADTs|see{generalized algebraic datatypes}}% _Generalized algebraic datatypes_ (GADT's)%~\cite{GADT}% are a popular feature in %\index{GHC Haskell}%GHC Haskell and other languages that removes this first restriction. |
591 | 566 |
592 The second restriction is not lifted by GADTs. In ML and Haskell, indices of types must be types and may not be _expressions_. In Coq, types may be indexed by arbitrary Gallina terms. Type indices can live in the same universe as programs, and we can compute with them just like regular programs. Haskell supports a hobbled form of computation in type indices based on %\index{Haskell}%multi-parameter type classes, and recent extensions like type functions bring Haskell programming even closer to %``%#"#real#"#%''% functional programming with types, but, without dependent typing, there must always be a gap between how one programs with types and how one programs normally. | 567 The second restriction is not lifted by GADT's. In ML and Haskell, indices of types must be types and may not be _expressions_. In Coq, types may be indexed by arbitrary Gallina terms. Type indices can live in the same universe as programs, and we can compute with them just like regular programs. Haskell supports a hobbled form of computation in type indices based on %\index{Haskell}%multi-parameter type classes, and recent extensions like type functions bring Haskell programming even closer to %``%#"#real#"#%''% functional programming with types, but, without dependent typing, there must always be a gap between how one programs with types and how one programs normally. |
593 *) | 568 *) |
594 | 569 |
595 (** We can define a similar type family for typed expressions, where a term of type [texp t] can be assigned object language type [t]. (It is conventional in the world of interactive theorem proving to call the language of the proof assistant the %\index{meta language}%_meta language_ and a language being formalized the %\index{object language}%_object language_.) *) | 570 (** We can define a similar type family for typed expressions, where a term of type [texp t] can be assigned object language type [t]. (It is conventional in the world of interactive theorem proving to call the language of the proof assistant the%\index{meta language}% _meta language_ and a language being formalized the%\index{object language}% _object language_.) *) |
596 | 571 |
597 Inductive texp : type -> Set := | 572 Inductive texp : type -> Set := |
598 | TNConst : nat -> texp Nat | 573 | TNConst : nat -> texp Nat |
599 | TBConst : bool -> texp Bool | 574 | TBConst : bool -> texp Bool |
600 | TBinop : forall t1 t2 t, tbinop t1 t2 t -> texp t1 -> texp t2 -> texp t. | 575 | TBinop : forall t1 t2 t, tbinop t1 t2 t -> texp t1 -> texp t2 -> texp t. |
617 | TEq Nat => beq_nat | 592 | TEq Nat => beq_nat |
618 | TEq Bool => eqb | 593 | TEq Bool => eqb |
619 | TLt => leb | 594 | TLt => leb |
620 end. | 595 end. |
621 | 596 |
622 (** This function has just a few differences from the denotation functions we saw earlier. First, [tbinop] is an indexed type, so its indices become additional arguments to [tbinopDenote]. Second, we need to perform a genuine %\index{dependent pattern matching}%_dependent pattern match_, where the necessary _type_ of each case body depends on the _value_ that has been matched. At this early stage, we will not go into detail on the many subtle aspects of Gallina that support dependent pattern-matching, but the subject is central to Part II of the book. | 597 (** This function has just a few differences from the denotation functions we saw earlier. First, [tbinop] is an indexed type, so its indices become additional arguments to [tbinopDenote]. Second, we need to perform a genuine%\index{dependent pattern matching}% _dependent pattern match_, where the necessary _type_ of each case body depends on the _value_ that has been matched. At this early stage, we will not go into detail on the many subtle aspects of Gallina that support dependent pattern-matching, but the subject is central to Part II of the book. |
623 | 598 |
624 The same tricks suffice to define an expression denotation function in an unsurprising way: | 599 The same tricks suffice to define an expression denotation function in an unsurprising way: |
625 *) | 600 *) |
626 | 601 |
627 Fixpoint texpDenote t (e : texp t) : typeDenote t := | 602 Fixpoint texpDenote t (e : texp t) : typeDenote t := |
643 (TNConst 7)). | 618 (TNConst 7)). |
644 (** [= 28 : typeDenote Nat] *) | 619 (** [= 28 : typeDenote Nat] *) |
645 | 620 |
646 Eval simpl in texpDenote (TBinop (TEq Nat) (TBinop TPlus (TNConst 2) (TNConst 2)) | 621 Eval simpl in texpDenote (TBinop (TEq Nat) (TBinop TPlus (TNConst 2) (TNConst 2)) |
647 (TNConst 7)). | 622 (TNConst 7)). |
648 (** [= ] %\coqdocconstructor{%#<tt>#false#</tt>#%}% [ : typeDenote Bool] *) | 623 (** [= false : typeDenote Bool] *) |
649 | 624 |
650 Eval simpl in texpDenote (TBinop TLt (TBinop TPlus (TNConst 2) (TNConst 2)) | 625 Eval simpl in texpDenote (TBinop TLt (TBinop TPlus (TNConst 2) (TNConst 2)) |
651 (TNConst 7)). | 626 (TNConst 7)). |
652 (** [= true : typeDenote Bool] *) | 627 (** [= true : typeDenote Bool] *) |
653 | 628 |
778 | 753 |
779 | 754 |
780 (** We can check that the compiler generates programs that behave appropriately on our sample programs from above: *) | 755 (** We can check that the compiler generates programs that behave appropriately on our sample programs from above: *) |
781 | 756 |
782 Eval simpl in tprogDenote (tcompile (TNConst 42) nil) tt. | 757 Eval simpl in tprogDenote (tcompile (TNConst 42) nil) tt. |
783 (** [= (42, tt) : vstack (][Nat :: nil)] *) | 758 (** [= (42, tt) : vstack (Nat :: nil)] *) |
784 | 759 |
785 Eval simpl in tprogDenote (tcompile (TBConst true) nil) tt. | 760 Eval simpl in tprogDenote (tcompile (TBConst true) nil) tt. |
786 (** [= (][true][, tt) : vstack (][Bool :: nil)] *) | 761 (** [= (true, tt) : vstack (Bool :: nil)] *) |
787 | 762 |
788 Eval simpl in tprogDenote (tcompile (TBinop TTimes (TBinop TPlus (TNConst 2) | 763 Eval simpl in tprogDenote (tcompile (TBinop TTimes (TBinop TPlus (TNConst 2) |
789 (TNConst 2)) (TNConst 7)) nil) tt. | 764 (TNConst 2)) (TNConst 7)) nil) tt. |
790 (** [= (28, tt) : vstack (][Nat :: nil)] *) | 765 (** [= (28, tt) : vstack (Nat :: nil)] *) |
791 | 766 |
792 Eval simpl in tprogDenote (tcompile (TBinop (TEq Nat) (TBinop TPlus (TNConst 2) | 767 Eval simpl in tprogDenote (tcompile (TBinop (TEq Nat) (TBinop TPlus (TNConst 2) |
793 (TNConst 2)) (TNConst 7)) nil) tt. | 768 (TNConst 2)) (TNConst 7)) nil) tt. |
794 (** [= (]%\coqdocconstructor{%#<tt>#false#</tt>#%}%[, tt) : vstack (][Bool :: nil)] *) | 769 (** [= (false, tt) : vstack (Bool :: nil)] *) |
795 | 770 |
796 Eval simpl in tprogDenote (tcompile (TBinop TLt (TBinop TPlus (TNConst 2) (TNConst 2)) | 771 Eval simpl in tprogDenote (tcompile (TBinop TLt (TBinop TPlus (TNConst 2) (TNConst 2)) |
797 (TNConst 7)) nil) tt. | 772 (TNConst 7)) nil) tt. |
798 (** [= (][true][, tt) : vstack (][Bool :: nil)] *) | 773 (** [= (true, tt) : vstack (Bool :: nil)] *) |
799 | 774 |
800 | 775 |
801 (** ** Translation Correctness *) | 776 (** ** Translation Correctness *) |
802 | 777 |
803 (** We can state a correctness theorem similar to the last one. *) | 778 (** We can state a correctness theorem similar to the last one. *) |
845 | 820 |
846 (** This one goes through completely automatically. | 821 (** This one goes through completely automatically. |
847 | 822 |
848 Some code behind the scenes registers [app_assoc_reverse] for use by [crush]. We must register [tconcat_correct] similarly to get the same effect:%\index{Vernacular commands!Hint Rewrite}% *) | 823 Some code behind the scenes registers [app_assoc_reverse] for use by [crush]. We must register [tconcat_correct] similarly to get the same effect:%\index{Vernacular commands!Hint Rewrite}% *) |
849 | 824 |
850 (* begin hide *) | |
851 Hint Rewrite tconcat_correct. | 825 Hint Rewrite tconcat_correct. |
852 (* end hide *) | |
853 (** %\noindent%[Hint] %\coqdockw{%#<tt>#Rewrite#</tt>#%}% [tconcat_correct.] *) | |
854 | 826 |
855 (** Here we meet the pervasive concept of a _hint_. Many proofs can be found through exhaustive enumerations of combinations of possible proof steps; hints provide the set of steps to consider. The tactic [crush] is applying such brute force search for us silently, and it will consider more possibilities as we add more hints. This particular hint asks that the lemma be used for left-to-right rewriting, and we ask for the hint to be added to the hint database called [cpdt], which is the database used by [crush]. In general, segragating hints into different databases is helpful to control the performance of proof search, in cases where domain knowledge allows us to narrow the set of proof steps to be considered in brute force search. Part III of this book considers such pragmatic aspects of proof search in much more detail. | 827 (** Here we meet the pervasive concept of a _hint_. Many proofs can be found through exhaustive enumerations of combinations of possible proof steps; hints provide the set of steps to consider. The tactic [crush] is applying such brute force search for us silently, and it will consider more possibilities as we add more hints. This particular hint asks that the lemma be used for left-to-right rewriting, and we ask for the hint to be added to the hint database called [cpdt], which is the database used by [crush]. In general, segragating hints into different databases is helpful to control the performance of proof search, in cases where domain knowledge allows us to narrow the set of proof steps to be considered in brute force search. Part III of this book considers such pragmatic aspects of proof search in much more detail. |
856 | 828 |
857 Now we are ready to return to [tcompile_correct'], proving it automatically this time. *) | 829 Now we are ready to return to [tcompile_correct'], proving it automatically this time. *) |
858 | 830 |
861 induction e; crush. | 833 induction e; crush. |
862 Qed. | 834 Qed. |
863 | 835 |
864 (** We can register this main lemma as another hint, allowing us to prove the final theorem trivially. *) | 836 (** We can register this main lemma as another hint, allowing us to prove the final theorem trivially. *) |
865 | 837 |
866 (* begin hide *) | |
867 Hint Rewrite tcompile_correct'. | 838 Hint Rewrite tcompile_correct'. |
868 (* end hide *) | |
869 (** %\noindent%[Hint ]%\coqdockw{%#<tt>#Rewrite#</tt>#%}%[ tcompile_correct'.] *) | |
870 | 839 |
871 Theorem tcompile_correct : forall t (e : texp t), | 840 Theorem tcompile_correct : forall t (e : texp t), |
872 tprogDenote (tcompile e nil) tt = (texpDenote e, tt). | 841 tprogDenote (tcompile e nil) tt = (texpDenote e, tt). |
873 crush. | 842 crush. |
874 Qed. | 843 Qed. |
875 (* end thide *) | 844 (* end thide *) |
876 | 845 |
877 (** It is probably worth emphasizing that we are doing more than building mathematical models. Our compilers are functional programs that can be executed efficiently. One strategy for doing so is based on %\index{program extraction}%_program extraction_, which generates OCaml code from Coq developments. For instance, we run a command to output the OCaml version of [tcompile]:%\index{Vernacular commands!Extraction}% *) | 846 (** It is probably worth emphasizing that we are doing more than building mathematical models. Our compilers are functional programs that can be executed efficiently. One strategy for doing so is based on%\index{program extraction}% _program extraction_, which generates OCaml code from Coq developments. For instance, we run a command to output the OCaml version of [tcompile]:%\index{Vernacular commands!Extraction}% *) |
878 | 847 |
879 (* begin hide *) | |
880 Extraction tcompile. | 848 Extraction tcompile. |
881 (* end hide *) | |
882 (** %\noindent\coqdockw{%#<tt>#Extraction#</tt>#%}%[ tcompile.] *) | |
883 | 849 |
884 (** << | 850 (** << |
885 let rec tcompile t e ts = | 851 let rec tcompile t e ts = |
886 match e with | 852 match e with |
887 | TNConst n -> | 853 | TNConst n -> |