|
1 % |
|
2 \begin{isabellebody}% |
|
3 \def\isabellecontext{Typedef}% |
|
4 % |
|
5 \isamarkupsection{Introducing new types} |
|
6 % |
|
7 \begin{isamarkuptext}% |
|
8 \label{sec:adv-typedef} |
|
9 By now we have seen a number of ways for introducing new types, for example |
|
10 type synonyms, recursive datatypes and records. For most applications, this |
|
11 repertoire should be quite sufficient. Very occasionally you may feel the |
|
12 need for a more advanced type. If you cannot avoid that type, and you are |
|
13 quite certain that it is not definable by any of the standard means, |
|
14 then read on. |
|
15 \begin{warn} |
|
16 Types in HOL must be non-empty; otherwise the quantifier rules would be |
|
17 unsound, because $\exists x. x=x$ is a theorem. |
|
18 \end{warn}% |
|
19 \end{isamarkuptext}% |
|
20 % |
|
21 \isamarkupsubsection{Declaring new types} |
|
22 % |
|
23 \begin{isamarkuptext}% |
|
24 \label{sec:typedecl} |
|
25 The most trivial way of introducing a new type is by a \bfindex{type |
|
26 declaration}:% |
|
27 \end{isamarkuptext}% |
|
28 \isacommand{typedecl}\ my{\isacharunderscore}new{\isacharunderscore}type% |
|
29 \begin{isamarkuptext}% |
|
30 \noindent\indexbold{*typedecl}% |
|
31 This does not define the type at all but merely introduces its name, \isa{my{\isacharunderscore}new{\isacharunderscore}type}. Thus we know nothing about this type, except that it is |
|
32 non-empty. Such declarations without definitions are |
|
33 useful only if that type can be viewed as a parameter of a theory and we do |
|
34 not intend to impose any restrictions on it. A typical example is given in |
|
35 \S\ref{sec:VMC}, where we define transition relations over an arbitrary type |
|
36 of states without any internal structure. |
|
37 |
|
38 In principle we can always get rid of such type declarations by making those |
|
39 types parameters of every other type, thus keeping the theory generic. In |
|
40 practice, however, the resulting clutter can sometimes make types hard to |
|
41 read. |
|
42 |
|
43 If you are looking for a quick and dirty way of introducing a new type |
|
44 together with its properties: declare the type and state its properties as |
|
45 axioms. Example:% |
|
46 \end{isamarkuptext}% |
|
47 \isacommand{axioms}\isanewline |
|
48 just{\isacharunderscore}one{\isacharcolon}\ {\isachardoublequote}{\isasymexists}{\isacharbang}\ x{\isacharcolon}{\isacharcolon}my{\isacharunderscore}new{\isacharunderscore}type{\isachardot}\ True{\isachardoublequote}% |
|
49 \begin{isamarkuptext}% |
|
50 \noindent |
|
51 However, we strongly discourage this approach, except at explorative stages |
|
52 of your development. It is extremely easy to write down contradictory sets of |
|
53 axioms, in which case you will be able to prove everything but it will mean |
|
54 nothing. In the above case it also turns out that the axiomatic approach is |
|
55 unnecessary: a one-element type called \isa{unit} is already defined in HOL.% |
|
56 \end{isamarkuptext}% |
|
57 % |
|
58 \isamarkupsubsection{Defining new types} |
|
59 % |
|
60 \begin{isamarkuptext}% |
|
61 \label{sec:typedef} |
|
62 Now we come to the most general method of safely introducing a new type, the |
|
63 \bfindex{type definition}. All other methods, for example |
|
64 \isacommand{datatype}, are based on it. The principle is extremely simple: |
|
65 any non-empty subset of an existing type can be turned into a new type. Thus |
|
66 a type definition is merely a notational device: you introduce a new name for |
|
67 a subset of an existing type. This does not add any logical power to HOL, |
|
68 because you could base all your work directly on the subset of the existing |
|
69 type. However, the resulting theories could easily become undigestible |
|
70 because instead of implicit types you would have explicit sets in your |
|
71 formulae. |
|
72 |
|
73 Let us work a simple example, the definition of a three-element type. |
|
74 It is easily represented by the first three natural numbers:% |
|
75 \end{isamarkuptext}% |
|
76 \isacommand{typedef}\ three\ {\isacharequal}\ {\isachardoublequote}{\isacharbraceleft}n{\isachardot}\ n\ {\isasymle}\ {\isadigit{2}}{\isacharbraceright}{\isachardoublequote}% |
|
77 \begin{isamarkuptxt}% |
|
78 \noindent\indexbold{*typedef}% |
|
79 In order to enforce that the representing set on the right-hand side is |
|
80 non-empty, this definition actually starts a proof to that effect: |
|
81 \begin{isabelle}% |
|
82 \ {\isadigit{1}}{\isachardot}\ {\isasymexists}x{\isachardot}\ x\ {\isasymin}\ {\isacharbraceleft}n{\isachardot}\ n\ {\isasymle}\ {\isadigit{2}}{\isacharbraceright}% |
|
83 \end{isabelle} |
|
84 Fortunately, this is easy enough to show: take 0 as a witness.% |
|
85 \end{isamarkuptxt}% |
|
86 \isacommand{apply}{\isacharparenleft}rule{\isacharunderscore}tac\ x\ {\isacharequal}\ {\isadigit{0}}\ \isakeyword{in}\ exI{\isacharparenright}\isanewline |
|
87 \isacommand{by}\ simp% |
|
88 \begin{isamarkuptext}% |
|
89 This type definition introduces the new type \isa{three} and asserts |
|
90 that it is a \emph{copy} of the set \isa{{\isacharbraceleft}{\isadigit{0}}{\isacharcomma}\ {\isadigit{1}}{\isacharcomma}\ {\isadigit{2}}{\isacharbraceright}}. This assertion |
|
91 is expressed via a bijection between the \emph{type} \isa{three} and the |
|
92 \emph{set} \isa{{\isacharbraceleft}{\isadigit{0}}{\isacharcomma}\ {\isadigit{1}}{\isacharcomma}\ {\isadigit{2}}{\isacharbraceright}}. To this end, the command declares the following |
|
93 constants behind the scenes: |
|
94 \begin{center} |
|
95 \begin{tabular}{rcl} |
|
96 \isa{three} &::& \isa{nat\ set} \\ |
|
97 \isa{Rep{\isacharunderscore}three} &::& \isa{three\ {\isasymRightarrow}\ nat}\\ |
|
98 \isa{Abs{\isacharunderscore}three} &::& \isa{nat\ {\isasymRightarrow}\ three} |
|
99 \end{tabular} |
|
100 \end{center} |
|
101 Constant \isa{three} is just an abbreviation (\isa{three{\isacharunderscore}def}): |
|
102 \begin{isabelle}% |
|
103 \ \ \ \ \ three\ {\isasymequiv}\ {\isacharbraceleft}n{\isachardot}\ n\ {\isasymle}\ {\isadigit{2}}{\isacharbraceright}% |
|
104 \end{isabelle} |
|
105 The situation is best summarized with the help of the following diagram, |
|
106 where squares are types and circles are sets: |
|
107 \begin{center} |
|
108 \unitlength1mm |
|
109 \thicklines |
|
110 \begin{picture}(100,40) |
|
111 \put(3,13){\framebox(15,15){\isa{three}}} |
|
112 \put(55,5){\framebox(30,30){\isa{three}}} |
|
113 \put(70,32){\makebox(0,0){\isa{nat}}} |
|
114 \put(70,20){\circle{40}} |
|
115 \put(10,15){\vector(1,0){60}} |
|
116 \put(25,14){\makebox(0,0)[tl]{\isa{Rep{\isacharunderscore}three}}} |
|
117 \put(70,25){\vector(-1,0){60}} |
|
118 \put(25,26){\makebox(0,0)[bl]{\isa{Abs{\isacharunderscore}three}}} |
|
119 \end{picture} |
|
120 \end{center} |
|
121 Finally, \isacommand{typedef} asserts that \isa{Rep{\isacharunderscore}three} is |
|
122 surjective on the subset \isa{three} and \isa{Abs{\isacharunderscore}three} and \isa{Rep{\isacharunderscore}three} are inverses of each other: |
|
123 \begin{center} |
|
124 \begin{tabular}{rl} |
|
125 \isa{Rep{\isacharunderscore}three\ x\ {\isasymin}\ three} &~~ (\isa{Rep{\isacharunderscore}three}) \\ |
|
126 \isa{Abs{\isacharunderscore}three\ {\isacharparenleft}Rep{\isacharunderscore}three\ x{\isacharparenright}\ {\isacharequal}\ x} &~~ (\isa{Rep{\isacharunderscore}three{\isacharunderscore}inverse}) \\ |
|
127 \isa{y\ {\isasymin}\ three\ {\isasymLongrightarrow}\ Rep{\isacharunderscore}three\ {\isacharparenleft}Abs{\isacharunderscore}three\ y{\isacharparenright}\ {\isacharequal}\ y} &~~ (\isa{Abs{\isacharunderscore}three{\isacharunderscore}inverse}) |
|
128 \end{tabular} |
|
129 \end{center} |
|
130 |
|
131 From the above example it should be clear what \isacommand{typedef} does |
|
132 in general: simply replace the name \isa{three} and the set |
|
133 \isa{{\isacharbraceleft}n{\isachardot}\ n\ {\isasymle}\ {\isadigit{2}}{\isacharbraceright}} by the respective arguments. |
|
134 |
|
135 Our next step is to define the basic functions expected on the new type. |
|
136 Although this depends on the type at hand, the following strategy works well: |
|
137 \begin{itemize} |
|
138 \item define a small kernel of basic functions such that all further |
|
139 functions you anticipate can be defined on top of that kernel. |
|
140 \item define the kernel in terms of corresponding functions on the |
|
141 representing type using \isa{Abs} and \isa{Rep} to convert between the |
|
142 two levels. |
|
143 \end{itemize} |
|
144 In our example it suffices to give the three elements of type \isa{three} |
|
145 names:% |
|
146 \end{isamarkuptext}% |
|
147 \isacommand{constdefs}\isanewline |
|
148 \ \ A{\isacharcolon}{\isacharcolon}\ three\isanewline |
|
149 \ {\isachardoublequote}A\ {\isasymequiv}\ Abs{\isacharunderscore}three\ {\isadigit{0}}{\isachardoublequote}\isanewline |
|
150 \ \ B{\isacharcolon}{\isacharcolon}\ three\isanewline |
|
151 \ {\isachardoublequote}B\ {\isasymequiv}\ Abs{\isacharunderscore}three\ {\isadigit{1}}{\isachardoublequote}\isanewline |
|
152 \ \ C\ {\isacharcolon}{\isacharcolon}\ three\isanewline |
|
153 \ {\isachardoublequote}C\ {\isasymequiv}\ Abs{\isacharunderscore}three\ {\isadigit{2}}{\isachardoublequote}% |
|
154 \begin{isamarkuptext}% |
|
155 So far, everything was easy. But it is clear that reasoning about \isa{three} will be hell if we have to go back to \isa{nat} every time. Thus our |
|
156 aim must be to raise our level of abstraction by deriving enough theorems |
|
157 about type \isa{three} to characterize it completely. And those theorems |
|
158 should be phrased in terms of \isa{A}, \isa{B} and \isa{C}, not \isa{Abs{\isacharunderscore}three} and \isa{Rep{\isacharunderscore}three}. Because of the simplicity of the example, |
|
159 we merely need to prove that \isa{A}, \isa{B} and \isa{C} are distinct |
|
160 and that they exhaust the type. |
|
161 |
|
162 We start with a helpful version of injectivity of \isa{Abs{\isacharunderscore}three} on the |
|
163 representing subset:% |
|
164 \end{isamarkuptext}% |
|
165 \isacommand{lemma}\ {\isacharbrackleft}simp{\isacharbrackright}{\isacharcolon}\isanewline |
|
166 \ {\isachardoublequote}{\isasymlbrakk}\ x\ {\isasymin}\ three{\isacharsemicolon}\ y\ {\isasymin}\ three\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ {\isacharparenleft}Abs{\isacharunderscore}three\ x\ {\isacharequal}\ Abs{\isacharunderscore}three\ y{\isacharparenright}\ {\isacharequal}\ {\isacharparenleft}x{\isacharequal}y{\isacharparenright}{\isachardoublequote}% |
|
167 \begin{isamarkuptxt}% |
|
168 \noindent |
|
169 We prove both directions separately. From \isa{Abs{\isacharunderscore}three\ x\ {\isacharequal}\ Abs{\isacharunderscore}three\ y} |
|
170 we derive \isa{Rep{\isacharunderscore}three\ {\isacharparenleft}Abs{\isacharunderscore}three\ x{\isacharparenright}\ {\isacharequal}\ Rep{\isacharunderscore}three\ {\isacharparenleft}Abs{\isacharunderscore}three\ y{\isacharparenright}} (via |
|
171 \isa{arg{\isacharunderscore}cong}: \isa{{\isacharquery}x\ {\isacharequal}\ {\isacharquery}y\ {\isasymLongrightarrow}\ {\isacharquery}f\ {\isacharquery}x\ {\isacharequal}\ {\isacharquery}f\ {\isacharquery}y}), and thus the required \isa{x\ {\isacharequal}\ y} by simplification with \isa{Abs{\isacharunderscore}three{\isacharunderscore}inverse}. The other direction |
|
172 is trivial by simplification:% |
|
173 \end{isamarkuptxt}% |
|
174 \isacommand{apply}{\isacharparenleft}rule\ iffI{\isacharparenright}\isanewline |
|
175 \ \isacommand{apply}{\isacharparenleft}drule{\isacharunderscore}tac\ f\ {\isacharequal}\ Rep{\isacharunderscore}three\ \isakeyword{in}\ arg{\isacharunderscore}cong{\isacharparenright}\isanewline |
|
176 \ \isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}Abs{\isacharunderscore}three{\isacharunderscore}inverse{\isacharparenright}\isanewline |
|
177 \isacommand{by}\ simp% |
|
178 \begin{isamarkuptext}% |
|
179 \noindent |
|
180 Analogous lemmas can be proved in the same way for arbitrary type definitions. |
|
181 |
|
182 Distinctness of \isa{A}, \isa{B} and \isa{C} follows immediately |
|
183 if we expand their definitions and rewrite with the above simplification rule:% |
|
184 \end{isamarkuptext}% |
|
185 \isacommand{lemma}\ {\isachardoublequote}A\ {\isasymnoteq}\ B\ {\isasymand}\ B\ {\isasymnoteq}\ A\ {\isasymand}\ A\ {\isasymnoteq}\ C\ {\isasymand}\ C\ {\isasymnoteq}\ A\ {\isasymand}\ B\ {\isasymnoteq}\ C\ {\isasymand}\ C\ {\isasymnoteq}\ B{\isachardoublequote}\isanewline |
|
186 \isacommand{by}{\isacharparenleft}simp\ add{\isacharcolon}A{\isacharunderscore}def\ B{\isacharunderscore}def\ C{\isacharunderscore}def\ three{\isacharunderscore}def{\isacharparenright}% |
|
187 \begin{isamarkuptext}% |
|
188 \noindent |
|
189 Of course we rely on the simplifier to solve goals like \isa{{\isadigit{0}}\ {\isasymnoteq}\ {\isadigit{1}}}. |
|
190 |
|
191 The fact that \isa{A}, \isa{B} and \isa{C} exhaust type \isa{three} is |
|
192 best phrased as a case distinction theorem: if you want to prove \isa{P\ x} |
|
193 (where \isa{x} is of type \isa{three}) it suffices to prove \isa{P\ A}, |
|
194 \isa{P\ B} and \isa{P\ C}. First we prove the analogous proposition for the |
|
195 representation:% |
|
196 \end{isamarkuptext}% |
|
197 \isacommand{lemma}\ cases{\isacharunderscore}lemma{\isacharcolon}\ {\isachardoublequote}{\isasymlbrakk}\ Q\ {\isadigit{0}}{\isacharsemicolon}\ Q\ {\isadigit{1}}{\isacharsemicolon}\ Q\ {\isadigit{2}}{\isacharsemicolon}\ n\ {\isacharcolon}\ three\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ \ Q{\isacharparenleft}n{\isacharcolon}{\isacharcolon}nat{\isacharparenright}{\isachardoublequote}% |
|
198 \begin{isamarkuptxt}% |
|
199 \noindent |
|
200 Expanding \isa{three{\isacharunderscore}def} yields the premise \isa{n\ {\isasymle}\ {\isadigit{2}}}. Repeated |
|
201 elimination with \isa{le{\isacharunderscore}SucE} |
|
202 \begin{isabelle}% |
|
203 \ \ \ \ \ {\isasymlbrakk}{\isacharquery}m\ {\isasymle}\ Suc\ {\isacharquery}n{\isacharsemicolon}\ {\isacharquery}m\ {\isasymle}\ {\isacharquery}n\ {\isasymLongrightarrow}\ {\isacharquery}R{\isacharsemicolon}\ {\isacharquery}m\ {\isacharequal}\ Suc\ {\isacharquery}n\ {\isasymLongrightarrow}\ {\isacharquery}R{\isasymrbrakk}\ {\isasymLongrightarrow}\ {\isacharquery}R% |
|
204 \end{isabelle} |
|
205 reduces \isa{n\ {\isasymle}\ {\isadigit{2}}} to the three cases \isa{n\ {\isasymle}\ {\isadigit{0}}}, \isa{n\ {\isacharequal}\ {\isadigit{1}}} and |
|
206 \isa{n\ {\isacharequal}\ {\isadigit{2}}} which are trivial for simplification:% |
|
207 \end{isamarkuptxt}% |
|
208 \isacommand{apply}{\isacharparenleft}simp\ add{\isacharcolon}three{\isacharunderscore}def{\isacharparenright}\isanewline |
|
209 \isacommand{apply}{\isacharparenleft}{\isacharparenleft}erule\ le{\isacharunderscore}SucE{\isacharparenright}{\isacharplus}{\isacharparenright}\isanewline |
|
210 \isacommand{apply}\ simp{\isacharunderscore}all\isanewline |
|
211 \isacommand{done}% |
|
212 \begin{isamarkuptext}% |
|
213 Now the case distinction lemma on type \isa{three} is easy to derive if you know how to:% |
|
214 \end{isamarkuptext}% |
|
215 \isacommand{lemma}\ three{\isacharunderscore}cases{\isacharcolon}\ {\isachardoublequote}{\isasymlbrakk}\ P\ A{\isacharsemicolon}\ P\ B{\isacharsemicolon}\ P\ C\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ P\ x{\isachardoublequote}% |
|
216 \begin{isamarkuptxt}% |
|
217 \noindent |
|
218 We start by replacing the \isa{x} by \isa{Abs{\isacharunderscore}three\ {\isacharparenleft}Rep{\isacharunderscore}three\ x{\isacharparenright}}:% |
|
219 \end{isamarkuptxt}% |
|
220 \isacommand{apply}{\isacharparenleft}rule\ subst{\isacharbrackleft}OF\ Rep{\isacharunderscore}three{\isacharunderscore}inverse{\isacharbrackright}{\isacharparenright}% |
|
221 \begin{isamarkuptxt}% |
|
222 \noindent |
|
223 This substitution step worked nicely because there was just a single |
|
224 occurrence of a term of type \isa{three}, namely \isa{x}. |
|
225 When we now apply the above lemma, \isa{Q} becomes \isa{{\isasymlambda}n{\isachardot}\ P\ {\isacharparenleft}Abs{\isacharunderscore}three\ n{\isacharparenright}} because \isa{Rep{\isacharunderscore}three\ x} is the only term of type \isa{nat}:% |
|
226 \end{isamarkuptxt}% |
|
227 \isacommand{apply}{\isacharparenleft}rule\ cases{\isacharunderscore}lemma{\isacharparenright}% |
|
228 \begin{isamarkuptxt}% |
|
229 \begin{isabelle}% |
|
230 \ {\isadigit{1}}{\isachardot}\ {\isasymlbrakk}P\ A{\isacharsemicolon}\ P\ B{\isacharsemicolon}\ P\ C{\isasymrbrakk}\ {\isasymLongrightarrow}\ P\ {\isacharparenleft}Abs{\isacharunderscore}three\ {\isadigit{0}}{\isacharparenright}\isanewline |
|
231 \ {\isadigit{2}}{\isachardot}\ {\isasymlbrakk}P\ A{\isacharsemicolon}\ P\ B{\isacharsemicolon}\ P\ C{\isasymrbrakk}\ {\isasymLongrightarrow}\ P\ {\isacharparenleft}Abs{\isacharunderscore}three\ {\isadigit{1}}{\isacharparenright}\isanewline |
|
232 \ {\isadigit{3}}{\isachardot}\ {\isasymlbrakk}P\ A{\isacharsemicolon}\ P\ B{\isacharsemicolon}\ P\ C{\isasymrbrakk}\ {\isasymLongrightarrow}\ P\ {\isacharparenleft}Abs{\isacharunderscore}three\ {\isadigit{2}}{\isacharparenright}\isanewline |
|
233 \ {\isadigit{4}}{\isachardot}\ {\isasymlbrakk}P\ A{\isacharsemicolon}\ P\ B{\isacharsemicolon}\ P\ C{\isasymrbrakk}\ {\isasymLongrightarrow}\ Rep{\isacharunderscore}three\ x\ {\isasymin}\ three% |
|
234 \end{isabelle} |
|
235 The resulting subgoals are easily solved by simplification:% |
|
236 \end{isamarkuptxt}% |
|
237 \isacommand{apply}{\isacharparenleft}simp{\isacharunderscore}all\ add{\isacharcolon}A{\isacharunderscore}def\ B{\isacharunderscore}def\ C{\isacharunderscore}def\ Rep{\isacharunderscore}three{\isacharparenright}\isanewline |
|
238 \isacommand{done}% |
|
239 \begin{isamarkuptext}% |
|
240 \noindent |
|
241 This concludes the derivation of the characteristic theorems for |
|
242 type \isa{three}. |
|
243 |
|
244 The attentive reader has realized long ago that the |
|
245 above lengthy definition can be collapsed into one line:% |
|
246 \end{isamarkuptext}% |
|
247 \isacommand{datatype}\ three{\isacharprime}\ {\isacharequal}\ A\ {\isacharbar}\ B\ {\isacharbar}\ C% |
|
248 \begin{isamarkuptext}% |
|
249 \noindent |
|
250 In fact, the \isacommand{datatype} command performs internally more or less |
|
251 the same derivations as we did, which gives you some idea what life would be |
|
252 like without \isacommand{datatype}. |
|
253 |
|
254 Although \isa{three} could be defined in one line, we have chosen this |
|
255 example to demonstrate \isacommand{typedef} because its simplicity makes the |
|
256 key concepts particularly easy to grasp. If you would like to see a |
|
257 nontrivial example that cannot be defined more directly, we recommend the |
|
258 definition of \emph{finite multisets} in the HOL library. |
|
259 |
|
260 Let us conclude by summarizing the above procedure for defining a new type. |
|
261 Given some abstract axiomatic description $P$ of a type $ty$ in terms of a |
|
262 set of functions $F$, this involves three steps: |
|
263 \begin{enumerate} |
|
264 \item Find an appropriate type $\tau$ and subset $A$ which has the desired |
|
265 properties $P$, and make a type definition based on this representation. |
|
266 \item Define the required functions $F$ on $ty$ by lifting |
|
267 analogous functions on the representation via $Abs_ty$ and $Rep_ty$. |
|
268 \item Prove that $P$ holds for $ty$ by lifting $P$ from the representation. |
|
269 \end{enumerate} |
|
270 You can now forget about the representation and work solely in terms of the |
|
271 abstract functions $F$ and properties $P$.% |
|
272 \end{isamarkuptext}% |
|
273 \end{isabellebody}% |
|
274 %%% Local Variables: |
|
275 %%% mode: latex |
|
276 %%% TeX-master: "root" |
|
277 %%% End: |