Mercurial > cpdt > repo

comparison src/Equality.v @ 122:7cbf0376702f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Definitional equality
author Adam Chlipala <adamc@hcoop.net>
date Sat, 18 Oct 2008 15:32:59 -0400
parents 61e5622b1195
children 9ccd215e5112
comparison
equal deleted inserted replaced
121:61e5622b1195 122:7cbf0376702f
17 17
18 18
19 (** %\chapter{Reasoning About Equality Proofs}% *) 19 (** %\chapter{Reasoning About Equality Proofs}% *)
20 20
21 (** In traditional mathematics, the concept of equality is usually taken as a given. On the other hand, in type theory, equality is a very contentious subject. There are at least three different notions of equality that are important, and researchers are actively investigating new definitions of what it means for two terms to be equal. Even once we fix a notion of equality, there are inevitably tricky issues that arise in proving properties of programs that manipulate equality proofs explicitly. In this chapter, we will focus on design patterns for circumventing these tricky issues, and we will introduce the different notions of equality as they are germane. *) 21 (** In traditional mathematics, the concept of equality is usually taken as a given. On the other hand, in type theory, equality is a very contentious subject. There are at least three different notions of equality that are important, and researchers are actively investigating new definitions of what it means for two terms to be equal. Even once we fix a notion of equality, there are inevitably tricky issues that arise in proving properties of programs that manipulate equality proofs explicitly. In this chapter, we will focus on design patterns for circumventing these tricky issues, and we will introduce the different notions of equality as they are germane. *)
22
23
24 (** * The Definitional Equality *)
25
26 (** We have seen many examples so far where proof goals follow "by computation." That is, we apply computational reduction rules to reduce the goal to a normal form, at which point it follows trivially. Exactly when this works and when it does not depends on the details of Coq's %\textit{%#<i>#definitional equality#</i>#%}%. This is an untyped binary relation appearing in the formal metatheory of CIC. CIC contains a typing rule allowing the conclusion $E : T$ from the premise $E : T'$ and a proof that $T$ and $T'$ are definitionally equal.
27
28 The [cbv] tactic will help us illustrate the rules of Coq's definitional equality. We redefine the natural number predecessor function in a somewhat convoluted way and construct a manual proof that it returns [1] when applied to [0]. *)
29
30 Definition pred' (x : nat) :=
31 match x with
32 | O => O
33 | S n' => let y := n' in y
34 end.
35
36 Theorem reduce_me : pred' 1 = 0.
37 (** CIC follows the traditions of lambda calculus in associating reduction rules with Greek letters. Coq can certainly be said to support the familiar alpha reduction rule, which allows capture-avoiding renaming of bound variables, but we never need to apply alpha explicitly, since Coq uses a de Bruijn representation that encodes terms canonically.
38
39 The delta rule is for unfolding global definitions. We can use it here to unfold the definition of [pred']. We do this with the [cbv] tactic, which takes a list of reduction rules and makes as many call-by-value reduction steps as possible, using only those rules. There is an analogous tactic [lazy] for call-by-name reduction. *)
40
41 cbv delta.
42 (** [[
43
44 ============================
45 (fun x : nat => match x with
46 | 0 => 0
47 | S n' => let y := n' in y
48 end) 1 = 0
49 ]]
50
51 At this point, we want to apply the famous beta reduction of lambda calculus, to simplify the application of a known function abstraction. *)
52
53 cbv beta.
54 (** [[
55
56 ============================
57 match 1 with
58 | 0 => 0
59 | S n' => let y := n' in y
60 end = 0
61 ]]
62
63 Next on the list is the iota reduction, which simplifies a single [match] term by determining which pattern matches. *)
64
65 cbv iota.
66 (** [[
67
68 ============================
69 (fun n' : nat => let y := n' in y) 0 = 0
70 ]]
71
72 Now we need another beta reduction. *)
73
74 cbv beta.
75 (** [[
76
77 ============================
78 (let y := 0 in y) = 0
79 ]]
80
81 The final reduction rule is zeta, which replaces a [let] expression by its body with the appropriate term subsituted. *)
82
83 cbv zeta.
84 (** [[
85
86 ============================
87 0 = 0
88 ]] *)
89
90 reflexivity.
91 Qed.
92
93 (** The standard [eq] relation is critically dependent on the definitional equality. [eq] is often called a %\textit{%#<i>#propositional equality#</i>#%}%, because it reifies definitional equality as a proposition that may or may not hold. Standard axiomatizations of an equality predicate in first-order logic define equality in terms of properties it has, like reflexivity, symmetry, and transitivity. In contrast, for [eq] in Coq, those properties are implicit in the properties of the definitional equality, which are built into CIC's metatheory and the implementation of Gallina. We could add new rules to the definitional equality, and [eq] would keep its definition and methods of use.
94
95 This all may make it sound like the choice of [eq]'s definition is unimportant. To the contrary, in this chapter, we will see examples where alternate definitions may simplify proofs. Before that point, we will introduce effective proof methods for goals that use proofs of the standard propositional equality "as data." *)
22 96
23 97
24 (** * Heterogeneous Lists Revisited *) 98 (** * Heterogeneous Lists Revisited *)
25 99
26 (** One of our example dependent data structures from the last chapter was heterogeneous lists and their associated "cursor" type. *) 100 (** One of our example dependent data structures from the last chapter was heterogeneous lists and their associated "cursor" type. *)