Mercurial > cpdt > repo

comparison src/Universes.v @ 227:d8c54a25c81f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Update DataStruct with a new reason to use reflexive types; start Universes
author Adam Chlipala <adamc@hcoop.net>
date Wed, 18 Nov 2009 15:38:01 -0500
parents
children 0be1a42b3035
comparison
equal deleted inserted replaced
226:9d0b9577f8b1 227:d8c54a25c81f
1 (* Copyright (c) 2009, Adam Chlipala
2 *
3 * This work is licensed under a
4 * Creative Commons Attribution-Noncommercial-No Derivative Works 3.0
5 * Unported License.
6 * The license text is available at:
7 * http://creativecommons.org/licenses/by-nc-nd/3.0/
8 *)
9
10 (* begin hide *)
11 Require Import DepList.
12
13 Set Implicit Arguments.
14 (* end hide *)
15
16
17 (** %\chapter{Universes and Axioms}% *)
18
19 (** Many traditional theorems can be proved in Coq without special knowledge of CIC, the logic behind the prover. A development just seems to be using a particular ASCII notation for standard formulas based on set theory. Nonetheless, as we saw in Chapter 4, CIC differs from set theory in making it possible to define the usual logical connectives as derived notions. The foundation of it all is a dependently-typed functional programming language, based on dependent function types and inductive type families. By using the facilities of this language directly, we can accomplish some things much more easily than in mainstream math.
20
21 Gallina, which adds features to the more theoretical CIC, is the logic implemented in Coq. It has a relatively simple foundation that can be defined rigorously in a page or two of formal proof rules. Still, there are some important subtleties that have practical ramifications. This chapter focuses on those subtleties, avoiding formal metatheory in favor of example code. *)
22
23
24 (** * The [Type] Hierarchy *)
25
26 (** Every object in Gallina has a type. *)
27
28 Check 0.
29 (** %\vspace{-.15in}% [[
30 0
31 : nat
32
33 ]]
34
35 It is natural enough that zero be considered as a natural number. *)
36
37 Check nat.
38 (** %\vspace{-.15in}% [[
39 nat
40 : Set
41
42 ]]
43
44 From a set theory perspective, it is unsurprising to consider the natural numbers as a "set." *)
45
46 Check Set.
47 (** %\vspace{-.15in}% [[
48 Set
49 : Type
50
51 ]]
52
53 The type [Set] may be considered as the set of all sets, a concept that set theory handles in terms of %\textit{%#<i>#classes#</i>#%}%. In Coq, this more general notion is [Type]. *)
54
55 Check Type.
56 (** %\vspace{-.15in}% [[
57 Type
58 : Type
59
60 ]]
61
62 Strangely enough, [Type] appears to be its own type. It is known that polymorphic languages with this property are inconsistent. That is, using such a language to encode proofs is unwise, because it is possible to "prove" any theorem. What is really going on here?
63
64 Let us repeat some of our queries after toggling a flag related to Coq's printing behavior. *)
65
66 Set Printing Universes.
67
68 Check nat.
69 (** %\vspace{-.15in}% [[
70 nat
71 : Set
72 ]] *)
73
74 (** printing $ %({}*% #(<a/>*# *)
75 (** printing ^ %*{})% #*<a/>)# *)
76
77 Check Set.
78 (** %\vspace{-.15in}% [[
79 Set
80 : Type $ (0)+1 ^
81
82 ]] *)
83
84 Check Type.
85 (** %\vspace{-.15in}% [[
86 Type $ Top.3 ^
87 : Type $ (Top.3)+1 ^
88
89 ]]
90
91 Occurrences of [Type] are annotated with some additional information, inside comments. These annotations have to do with the secret behind [Type]: it really stands for an infinite hierarchy of types. The type of [Set] is [Type0], the type of [Type0] is [Type1], the type of [Type1] is [Type2], and so on. This is how we avoid the "[Type : Type]" paradox. As a convenience, the universe hierarchy drives Coq's one variety of subtyping. Any term whose type is [Type] at level [i] is automatically also described by [Type] at level [j] when [j > i].
92
93 In the outputs of our first [Check] query, we see that the type level of [Set]'s type is [(0)+1]. Here [0] stands for the level of [Set], and we increment it to arrive at the level that %\textit{%#<i>#classifies#</i>#%}% [Set].
94
95 In the second query's output, we see that the occurrence of [Type] that we check is assigned a fresh %\textit{%#<i>#universe variable#</i>#%}% [Top.3]. The output type increments [Top.3] to move up a level in the universe hierarchy. As we write code that uses definitions whose types mention universe variables, unification may refine the values of those variables. Luckily, the user rarely has to worry about the details.
96
97 Another crucial concept in CIC is %\textit{%#<i>#predicativity#</i>#%}%. Consider these queries. *)
98
99 Check forall T : nat, fin T.
100 (** %\vspace{-.15in}% [[
101 forall T : nat, fin T
102 : Set
103 ]] *)
104
105 Check forall T : Set, T.
106 (** %\vspace{-.15in}% [[
107 forall T : Set, T
108 : Type $ max(0, (0)+1) ^
109 ]] *)
110
111 Check forall T : Type, T.
112 (** %\vspace{-.15in}% [[
113 forall T : Type $ Top.9 ^ , T
114 : Type $ max(Top.9, (Top.9)+1) ^
115
116 ]]
117
118 These outputs demonstrate the rule for determining which universe a [forall] type lives in. In particular, for a type [forall x : T1, T2], we take the maximum of the universes of [T1] and [T2]. In the first example query, both [T1] ([nat]) and [T2] ([fin T]) are in [Set], so the [forall] type is in [Set], too. In the second query, [T1] is [Set], which is at level [(0)+1]; and [T2] is [T], which is at level [0]. Thus, the [forall] exists at the maximum of these two levels. The third example illustrates the same outcome, where we replace [Set] with an occurrence of [Type] that is assigned universe variable [Top.9]. This universe variable appears in the places where [0] appeared in the previous query.
119
120 The behind-the-scenes manipulation of universe variables gives us predicativity. Consider this simple definition of a polymorphic identity function. *)
121
122 Definition id (T : Set) (x : T) : T := x.
123
124 Check id 0.
125 (** %\vspace{-.15in}% [[
126 id 0
127 : nat
128
129 Check id Set.
130
131 Error: Illegal application (Type Error):
132 ...
133 The 1st term has type "Type (* (Top.15)+1 *)" which should be coercible to "Set".
134
135 ]]
136
137 The parameter [T] of [id] must be instantiated with a [Set]. [nat] is a [Set], but [Set] is not. We can try fixing the problem by generalizing our definition of [id]. *)
138
139 Reset id.
140 Definition id (T : Type) (x : T) : T := x.
141 Check id 0.
142 (** %\vspace{-.15in}% [[
143 id 0
144 : nat
145 ]] *)
146
147 Check id Set.
148 (** %\vspace{-.15in}% [[
149 id Set
150 : Type $ Top.17 ^
151 ]] *)
152
153 Check id Type.
154 (** %\vspace{-.15in}% [[
155 id Type $ Top.18 ^
156 : Type $ Top.19 ^
157 ]] *)
158
159 (** So far so good. As we apply [id] to different [T] values, the inferred index for [T]'s [Type] occurrence automatically moves higher up the type hierarchy.
160
161 [[
162 Check id id.
163
164 Error: Universe inconsistency (cannot enforce Top.16 < Top.16).
165
166 ]]
167
168 This error message reminds us that the universe variable for [T] still exists, even though it is usually hidden. To apply [id] to itself, that variable would need to be less than itself in the type hierarchy. Universe inconsistency error messages announce cases like this one where a term could only type-check by violating an implied constraint over universe variables. Such errors demonstrate that [Type] is %\textit{%#<i>#predicative#</i>#%}%, where this word has a CIC meaning closely related to its usual mathematical meaning. A predicative system enforces the constraint that, for any object of quantified type, none of those quantifiers may never be instantiated with the object itself. Impredicativity is associated with popular paradoxes in set theory, involving inconsistent constructions like "the set of all sets that do not contain themselves." Similar paradoxes result from uncontrolled impredicativity in Coq. *)
169
170
171 (** ** Inductive Definitions *)
172
173 (** Predicativity restrictions also apply to inductive definitions. As an example, let us consider a type of expression trees that allows injection of any native Coq value. The idea is that an [exp T] stands for a reflected expression of type [T].
174
175 [[
176 Inductive exp : Set -> Set :=
177 | Const : forall T : Set, T -> exp T
178 | Pair : forall T1 T2, exp T1 -> exp T2 -> exp (T1 * T2)
179 | Eq : forall T, exp T -> exp T -> exp bool.
180
181 Error: Large non-propositional inductive types must be in Type.
182
183 ]]
184
185 This definition is %\textit{%#<i>#large#</i>#%}% in the sense that at least one of its constructors takes an argument whose type has type [Type]. Coq would be inconsistent if we allowed definitions like this one in their full generality. Instead, we must change [exp] to live in [Type]. We will go even further and move [exp]'s index to [Type] as well. *)
186
187 Inductive exp : Type -> Type :=
188 | Const : forall T, T -> exp T
189 | Pair : forall T1 T2, exp T1 -> exp T2 -> exp (T1 * T2)
190 | Eq : forall T, exp T -> exp T -> exp bool.
191
192 (** This definition is accepted. We can build some sample expressions. *)
193
194 Check Const 0.
195 (** %\vspace{-.15in}% [[
196 Const 0
197 : exp nat
198 ]] *)
199
200 Check Pair (Const 0) (Const tt).
201 (** %\vspace{-.15in}% [[
202 Pair (Const 0) (Const tt)
203 : exp (nat * unit)
204 ]] *)
205
206 Check Eq (Const Set) (Const Type).
207 (** %\vspace{-.15in}% [[
208 Eq (Const Set) (Const Type (* Top.59 *))
209 : exp bool
210
211 ]]
212
213 We can check many expressions, including fancy expressions that include types. However, it is not hard to hit a type-checking wall.
214
215 [[
216 Check Const (Const O).
217
218 Error: Universe inconsistency (cannot enforce Top.42 < Top.42).
219
220 ]]
221
222 We are unable to instantiate the parameter [T] of [Const] with an [exp] type. To see why, it is helpful to print the annotated version of [exp]'s inductive definition. *)
223
224 Print exp.
225 (** %\vspace{-.15in}% [[
226 Inductive exp
227 : Type $ Top.8 ^ ->
228 Type
229 $ max(0, (Top.11)+1, (Top.14)+1, (Top.15)+1, (Top.19)+1) ^ :=
230 Const : forall T : Type $ Top.11 ^ , T -> exp T
231 | Pair : forall (T1 : Type $ Top.14 ^ ) (T2 : Type $ Top.15 ^ ),
232 exp T1 -> exp T2 -> exp (T1 * T2)
233 | Eq : forall T : Type $ Top.19 ^ , exp T -> exp T -> exp bool
234
235 ]]
236
237 We see that the index type of [exp] has been assigned to universe level [Top.8]. In addition, each of the four occurrences of [Type] in the types of the constructors gets its own universe variable. Each of these variables appears explicitly in the type of [exp]. In particular, any type [exp T] lives at a universe level found by incrementing by one the maximum of the four argument variables. A consequence of this is that [exp] %\textit{%#<i>#must#</i>#%}% live at a higher universe level than any type which may be passed to one of its constructors. This consequence led to the universe inconsistency.
238
239 Strangely, the universe variable [Top.8] only appears in one place. Is there no restriction imposed on which types are valid arguments to [exp]? In fact, there is a restriction, but it only appears in a global set of universe constraints that are maintained "off to the side," not appearing explicitly in types. We can print the current database. *)
240
241 Print Universes.
242 (** %\vspace{-.15in}% [[
243 Top.19 < Top.9 <= Top.8
244 Top.15 < Top.9 <= Top.8 <= Coq.Init.Datatypes.38
245 Top.14 < Top.9 <= Top.8 <= Coq.Init.Datatypes.37
246 Top.11 < Top.9 <= Top.8
247
248 ]]
249
250 [Print Universes] outputs many more constraints, but we have collected only those that mention [Top] variables. We see one constraint for each universe variable associated with a constructor argument from [exp]'s definition. [Top.19] is the type argument to [Eq]. The constraint for [Top.19] effectively says that [Top.19] must be less than [Top.8], the universe of [exp]'s indices; an intermediate variable [Top.9] appears as an artifact of the way the constraint was generated.
251
252 The next constraint, for [Top.15], is more complicated. This is the universe of the second argument to the [Pair] constructor. Not only must [Top.15] be less than [Top.8], but it also comes out that [Top.8] must be less than [Coq.Init.Datatypes.38]. What is this new universe variable? It is from the definition of the [prod] inductive family, to which types of the form [A * B] are desugared. *)
253
254 Print prod.
255 (** %\vspace{-.15in}% [[
256 Inductive prod (A : Type $ Coq.Init.Datatypes.37 ^ )
257 (B : Type $ Coq.Init.Datatypes.38 ^ )
258 : Type $ max(Coq.Init.Datatypes.37, Coq.Init.Datatypes.38) ^ :=
259 pair : A -> B -> A * B
260
261 ]]
262
263 We see that the constraint is enforcing that indices to [exp] must not live in a higher universe level than [B]-indices to [prod]. The next constraint above establishes a symmetric condition for [A].
264
265 Thus it is apparent that Coq maintains a tortuous set of universe variable inequalities behind the scenes. It may look like some functions are polymorphic in the universe levels of their arguments, but what is really happening is imperative updating of a system of constraints, such that all uses of a function are consistent with a global set of universe levels. When the constraint system may not be evolved soundly, we get a universe inconsistency error.
266
267 %\medskip%
268
269 Something interesting is revealed in the annotated definition of [prod]. A type [prod A B] lives at a universe that is the maximum of the universes of [A] and [B]. From our earlier experiments, we might expect that [prod]'s universe would in fact need to be %\textit{%#<i>#one higher#</i>#%}% than the maximum. The critical difference is that, in the definition of [prod], [A] and [B] are defined as %\textit{%#<i>#parameters#</i>#%}%; that is, they appear named to the left of the main colon, rather than appearing (possibly unnamed) to the right.
270
271 Parameters are not as flexible as normal inductive type arguments. The range types of all of the constructors of a parameterized type must share the same indices. Nonetheless, when it is possible to define a polymorphic type in this way, we gain the ability to use the new type family in more ways, without triggering universe inconsistencies. For instance, nested pairs of types are perfectly legal. *)
272
273 Check (nat, (Type, Set)).
274 (** %\vspace{-.15in}% [[
275 (nat, (Type $ Top.44 ^ , Set))
276 : Set * (Type $ Top.45 ^ * Type $ Top.46 ^ )
277
278 ]]
279
280 The same cannot be done with a counterpart to [prod] that does not use parameters. *)
281
282 Inductive prod' : Type -> Type -> Type :=
283 | pair' : forall A B : Type, A -> B -> prod' A B.
284
285 (** [[
286 Check (pair' nat (pair' Type Set)).
287
288 Error: Universe inconsistency (cannot enforce Top.51 < Top.51).
289
290 ]]
291
292 The key benefit parameters bring us is the ability to avoid quantifying over types in the types of constructors. Such quantification induces less-than constraints, while parameters only introduce less-than-or-equal-to constraints. *)