32 and proved by assumption (Isar short hand ``.''). It enriches the |
30 and proved by assumption (Isar short hand ``.''). It enriches the |
33 local proof context by the theorems |
31 local proof context by the theorems |
34 also obtained in the interpretation from Section~\ref{sec:po-first}, |
32 also obtained in the interpretation from Section~\ref{sec:po-first}, |
35 and @{text int.less_def} may directly be used to unfold the |
33 and @{text int.less_def} may directly be used to unfold the |
36 definition. Theorems from the local interpretation disappear after |
34 definition. Theorems from the local interpretation disappear after |
37 leaving the proof context --- that is, after the closing a |
35 leaving the proof context --- that is, after the succeeding |
38 \isakeyword{next} or \isakeyword{qed} statement. *} |
36 \isakeyword{next} or \isakeyword{qed} statement. *} |
39 |
37 |
40 |
38 |
41 subsection {* Further Interpretations *} |
39 subsection {* Further Interpretations *} |
42 |
40 |
43 text {* Further interpretations are necessary for |
41 text {* Further interpretations are necessary for |
44 the other locales. In @{text lattice} the operations @{text \<sqinter>} and |
42 the other locales. In @{text lattice} the operations~@{text \<sqinter>} |
45 @{text \<squnion>} are substituted by @{term "min :: int \<Rightarrow> int \<Rightarrow> int"} and |
43 and~@{text \<squnion>} are substituted by @{term "min :: int \<Rightarrow> int \<Rightarrow> int"} |
46 @{term "max :: int \<Rightarrow> int \<Rightarrow> int"}. The entire proof for the |
44 and @{term "max :: int \<Rightarrow> int \<Rightarrow> int"}. The entire proof for the |
47 interpretation is reproduced to give an example of a more |
45 interpretation is reproduced to give an example of a more |
48 elaborate interpretation proof. *} |
46 elaborate interpretation proof. Note that the equations are named |
|
47 so they can be used in a later example. *} |
49 |
48 |
50 interpretation %visible int: lattice "op \<le> :: int \<Rightarrow> int \<Rightarrow> bool" |
49 interpretation %visible int: lattice "op \<le> :: int \<Rightarrow> int \<Rightarrow> bool" |
51 where "lattice.meet op \<le> (x::int) y = min x y" |
50 where int_min_eq: "lattice.meet op \<le> (x::int) y = min x y" |
52 and "lattice.join op \<le> (x::int) y = max x y" |
51 and int_max_eq: "lattice.join op \<le> (x::int) y = max x y" |
53 proof - |
52 proof - |
54 show "lattice (op \<le> :: int \<Rightarrow> int \<Rightarrow> bool)" |
53 show "lattice (op \<le> :: int \<Rightarrow> int \<Rightarrow> bool)" |
55 txt {* \normalsize We have already shown that this is a partial |
54 txt {* \normalsize We have already shown that this is a partial |
56 order, *} |
55 order, *} |
57 apply unfold_locales |
56 apply unfold_locales |
58 txt {* \normalsize hence only the lattice axioms remain to be |
57 txt {* \normalsize hence only the lattice axioms remain to be |
59 shown: @{subgoals [display]} After unfolding @{text is_inf} and |
58 shown. |
60 @{text is_sup}, *} |
59 @{subgoals [display]} |
|
60 By @{text is_inf} and @{text is_sup}, *} |
61 apply (unfold int.is_inf_def int.is_sup_def) |
61 apply (unfold int.is_inf_def int.is_sup_def) |
62 txt {* \normalsize the goals become @{subgoals [display]} |
62 txt {* \normalsize the goals are transformed to these |
63 This can be solved by Presburger arithmetic, which is contained |
63 statements: |
64 in @{text arith}. *} |
64 @{subgoals [display]} |
|
65 This is Presburger arithmetic, which can be solved by the |
|
66 method @{text arith}. *} |
65 by arith+ |
67 by arith+ |
66 txt {* \normalsize In order to show the equations, we put ourselves |
68 txt {* \normalsize In order to show the equations, we put ourselves |
67 in a situation where the lattice theorems can be used in a |
69 in a situation where the lattice theorems can be used in a |
68 convenient way. *} |
70 convenient way. *} |
69 then interpret int: lattice "op \<le> :: int \<Rightarrow> int \<Rightarrow> bool" . |
71 then interpret int: lattice "op \<le> :: int \<Rightarrow> int \<Rightarrow> bool" . |
96 @{thm [source] int.less_total} from locale @{text total_order}: \\ |
98 @{thm [source] int.less_total} from locale @{text total_order}: \\ |
97 \quad @{thm int.less_total} |
99 \quad @{thm int.less_total} |
98 \end{tabular} |
100 \end{tabular} |
99 \end{center} |
101 \end{center} |
100 \hrule |
102 \hrule |
101 \caption{Interpreted theorems for @{text \<le>} on the integers.} |
103 \caption{Interpreted theorems for~@{text \<le>} on the integers.} |
102 \label{tab:int-lattice} |
104 \label{tab:int-lattice} |
103 \end{table} |
105 \end{table} |
104 |
106 |
105 \begin{itemize} |
107 \begin{itemize} |
106 \item |
108 \item |
107 Locale @{text distrib_lattice} was also interpreted. Since the |
109 Locale @{text distrib_lattice} was also interpreted. Since the |
108 locale hierarcy reflects that total orders are distributive |
110 locale hierarchy reflects that total orders are distributive |
109 lattices, the interpretation of the latter was inserted |
111 lattices, the interpretation of the latter was inserted |
110 automatically with the interpretation of the former. In general, |
112 automatically with the interpretation of the former. In general, |
111 interpretation of a locale will also interpret all locales further |
113 interpretation traverses the locale hierarchy upwards and interprets |
112 up in the hierarchy, regardless whether imported or proved via the |
114 all encountered locales, regardless whether imported or proved via |
113 \isakeyword{sublocale} command. |
115 the \isakeyword{sublocale} command. Existing interpretations are |
|
116 skipped avoiding duplicate work. |
114 \item |
117 \item |
115 Theorem @{thm [source] int.less_total} makes use of @{term "op <"} |
118 The predicate @{term "op <"} appears in theorem @{thm [source] |
|
119 int.less_total} |
116 although an equation for the replacement of @{text "op \<sqsubset>"} was only |
120 although an equation for the replacement of @{text "op \<sqsubset>"} was only |
117 given in the interpretation of @{text partial_order}. These |
121 given in the interpretation of @{text partial_order}. The |
118 equations are pushed downwards the hierarchy for related |
122 interpretation equations are pushed downwards the hierarchy for |
119 interpretations --- that is, for interpretations that share the |
123 related interpretations --- that is, for interpretations that share |
120 instance for parameters they have in common. |
124 the instances of parameters they have in common. |
121 \end{itemize} |
125 \end{itemize} |
122 In the next section, the divisibility relation on the natural |
|
123 numbers will be explored. |
|
124 *} |
126 *} |
125 |
|
126 |
|
127 subsection {* Interpretations for Divisibility *} |
|
128 |
|
129 text {* In this section, further examples of interpretations are |
|
130 presented. Impatient readers may skip this section at first |
|
131 reading. |
|
132 |
|
133 Divisibility on the natural numbers is a distributive lattice |
|
134 but not a total order. Interpretation again proceeds |
|
135 incrementally. In order to distinguish divisibility from the order |
|
136 relation $\le$, we use the qualifier @{text nat_dvd} for |
|
137 divisibility. *} |
|
138 |
|
139 interpretation nat_dvd: partial_order "op dvd :: nat \<Rightarrow> nat \<Rightarrow> bool" |
|
140 where "partial_order.less op dvd (x::nat) y = (x dvd y \<and> x \<noteq> y)" |
|
141 proof - |
|
142 show "partial_order (op dvd :: nat \<Rightarrow> nat \<Rightarrow> bool)" |
|
143 by unfold_locales (auto simp: dvd_def) |
|
144 then interpret nat_dvd: partial_order "op dvd :: nat \<Rightarrow> nat \<Rightarrow> bool" . |
|
145 show "partial_order.less op dvd (x::nat) y = (x dvd y \<and> x \<noteq> y)" |
|
146 apply (unfold nat_dvd.less_def) |
|
147 apply auto |
|
148 done |
|
149 qed |
|
150 |
|
151 text {* Note that in Isabelle/HOL there is no operator for strict |
|
152 divisibility. Instead, we substitute @{term "x dvd y \<and> x \<noteq> y"}. *} |
|
153 |
|
154 interpretation nat_dvd: lattice "op dvd :: nat \<Rightarrow> nat \<Rightarrow> bool" |
|
155 where nat_dvd_meet_eq: |
|
156 "lattice.meet (op dvd :: nat \<Rightarrow> nat \<Rightarrow> bool) = gcd" |
|
157 and nat_dvd_join_eq: |
|
158 "lattice.join (op dvd :: nat \<Rightarrow> nat \<Rightarrow> bool) = lcm" |
|
159 proof - |
|
160 show "lattice (op dvd :: nat \<Rightarrow> nat \<Rightarrow> bool)" |
|
161 apply unfold_locales |
|
162 apply (unfold nat_dvd.is_inf_def nat_dvd.is_sup_def) |
|
163 apply (rule_tac x = "gcd x y" in exI) |
|
164 apply auto [1] |
|
165 apply (rule_tac x = "lcm x y" in exI) |
|
166 apply (auto intro: lcm_least_nat) |
|
167 done |
|
168 then interpret nat_dvd: lattice "op dvd :: nat \<Rightarrow> nat \<Rightarrow> bool" . |
|
169 show "lattice.meet (op dvd :: nat \<Rightarrow> nat \<Rightarrow> bool) = gcd" |
|
170 apply (auto simp add: expand_fun_eq) |
|
171 apply (unfold nat_dvd.meet_def) |
|
172 apply (rule the_equality) |
|
173 apply (unfold nat_dvd.is_inf_def) |
|
174 by auto |
|
175 show "lattice.join (op dvd :: nat \<Rightarrow> nat \<Rightarrow> bool) = lcm" |
|
176 apply (auto simp add: expand_fun_eq) |
|
177 apply (unfold nat_dvd.join_def) |
|
178 apply (rule the_equality) |
|
179 apply (unfold nat_dvd.is_sup_def) |
|
180 apply (auto intro: lcm_least_nat iff: lcm_unique_nat) |
|
181 done |
|
182 qed |
|
183 |
|
184 text {* The replacement equations @{thm [source] nat_dvd_meet_eq} and |
|
185 @{thm [source] nat_dvd_join_eq} are theorems of current theories. |
|
186 They are named so that they can be used in the main part of the |
|
187 subsequent interpretation. *} |
|
188 |
|
189 interpretation %visible nat_dvd: |
|
190 distrib_lattice "op dvd :: nat \<Rightarrow> nat \<Rightarrow> bool" |
|
191 apply unfold_locales |
|
192 txt {* \normalsize @{subgoals [display]} |
|
193 Distributivity of lattice meet and join needs to be shown. This is |
|
194 distributivity of gcd and lcm, as becomes apparent when unfolding |
|
195 the replacement equations from the previous interpretation: *} |
|
196 unfolding nat_dvd_meet_eq nat_dvd_join_eq |
|
197 txt {* \normalsize @{subgoals [display]} |
|
198 This is a result of number theory: *} |
|
199 by (rule UniqueFactorization.gcd_lcm_distrib_nat) |
|
200 |
|
201 text {* Theorems that are available in the theory after these |
|
202 interpretations are shown in Table~\ref{tab:nat-dvd-lattice}. |
|
203 |
|
204 \begin{table} |
|
205 \hrule |
|
206 \vspace{2ex} |
|
207 \begin{center} |
|
208 \begin{tabular}{l} |
|
209 @{thm [source] nat_dvd.less_def} from locale @{text partial_order}: \\ |
|
210 \quad @{thm nat_dvd.less_def} \\ |
|
211 @{thm [source] nat_dvd.meet_left} from locale @{text lattice}: \\ |
|
212 \quad @{thm nat_dvd.meet_left} \\ |
|
213 @{thm [source] nat_dvd.join_distr} from locale @{text distrib_lattice}: \\ |
|
214 \quad @{thm nat_dvd.join_distr} \\ |
|
215 \end{tabular} |
|
216 \end{center} |
|
217 \hrule |
|
218 \caption{Interpreted theorems for @{text dvd} on the natural numbers.} |
|
219 \label{tab:nat-dvd-lattice} |
|
220 \end{table} |
|
221 *} |
|
222 |
|
223 |
|
224 subsection {* Inspecting Interpretations of a Locale *} |
|
225 |
127 |
226 text {* The interpretations for a locale $n$ within the current |
128 text {* The interpretations for a locale $n$ within the current |
227 theory may be inspected with \isakeyword{print\_interps}~$n$. This |
129 theory may be inspected with \isakeyword{print\_interps}~$n$. This |
228 prints the list of instances of $n$, for which interpretations exist. |
130 prints the list of instances of $n$, for which interpretations exist. |
229 For example, \isakeyword{print\_interps} @{term partial_order} |
131 For example, \isakeyword{print\_interps} @{term partial_order} |
230 outputs the following: |
132 outputs the following: |
|
133 \begin{small} |
231 \begin{alltt} |
134 \begin{alltt} |
232 int! : partial_order "op \(\le\)" |
135 int! : partial_order "op \(\le\)" |
233 nat_dvd! : partial_order "op dvd" |
|
234 \end{alltt} |
136 \end{alltt} |
235 The interpretation qualifiers on the left are decorated with an |
137 \end{small} |
236 exclamation point, which means that they are mandatory. Qualifiers |
138 Of course, there is only one interpretation. |
|
139 The interpretation qualifier on the left is decorated with an |
|
140 exclamation point. This means that it is mandatory. Qualifiers |
237 can either be \emph{mandatory} or \emph{optional}, designated by |
141 can either be \emph{mandatory} or \emph{optional}, designated by |
238 ``!'' or ``?'' respectively. Mandatory qualifiers must occur in a |
142 ``!'' or ``?'' respectively. Mandatory qualifiers must occur in a |
239 name reference while optional ones need not. Mandatory qualifiers |
143 name reference while optional ones need not. Mandatory qualifiers |
240 prevent accidental hiding of names, while optional qualifers can be |
144 prevent accidental hiding of names, while optional qualifiers can be |
241 more convenient to use. For \isakeyword{interpretation}, the |
145 more convenient to use. For \isakeyword{interpretation}, the |
242 default for qualifiers without an explicit designator is ``!''. |
146 default is ``!''. |
243 *} |
147 *} |
244 |
148 |
245 |
149 |
246 section {* Locale Expressions \label{sec:expressions} *} |
150 section {* Locale Expressions \label{sec:expressions} *} |
247 |
151 |
248 text {* |
152 text {* |
249 A map @{term \<phi>} between partial orders @{text \<sqsubseteq>} and @{text \<preceq>} |
153 A map~@{term \<phi>} between partial orders~@{text \<sqsubseteq>} and~@{text \<preceq>} |
250 is called order preserving if @{text "x \<sqsubseteq> y"} implies @{text "\<phi> x \<preceq> |
154 is called order preserving if @{text "x \<sqsubseteq> y"} implies @{text "\<phi> x \<preceq> |
251 \<phi> y"}. This situation is more complex than those encountered so |
155 \<phi> y"}. This situation is more complex than those encountered so |
252 far: it involves two partial orders, and it is desirable to use the |
156 far: it involves two partial orders, and it is desirable to use the |
253 existing locale for both. |
157 existing locale for both. |
254 |
158 |
255 A locale for order preserving maps requires three parameters: @{text |
159 A locale for order preserving maps requires three parameters: @{text |
256 le} (\isakeyword{infixl}~@{text \<sqsubseteq>}), @{text le'} |
160 le}~(\isakeyword{infixl}~@{text \<sqsubseteq>}) and @{text |
257 (\isakeyword{infixl}~@{text \<preceq>}) for the orders and @{text \<phi>} for the |
161 le'}~(\isakeyword{infixl}~@{text \<preceq>}) for the orders and~@{text \<phi>} |
258 map. |
162 for the map. |
259 |
163 |
260 In order to reuse the existing locale for partial orders, which has |
164 In order to reuse the existing locale for partial orders, which has |
261 the single parameter @{text le}, it must be imported twice, once |
165 the single parameter~@{text le}, it must be imported twice, once |
262 mapping its parameter to @{text le} (\isakeyword{infixl}~@{text \<sqsubseteq>}) |
166 mapping its parameter to~@{text le} from the new locale and once |
263 from the new locale and once to @{text le'} |
167 to~@{text le'}. This can be achieved with a compound locale |
264 (\isakeyword{infixl}~@{text \<preceq>}). This can be achieved with a locale |
|
265 expression. |
168 expression. |
266 |
169 |
267 A \emph{locale expression} is a sequence of \emph{locale instances} |
170 In general, a locale expression is a sequence of \emph{locale instances} |
268 separated by ``$\textbf{+}$'' and followed by a \isakeyword{for} |
171 separated by~``$\textbf{+}$'' and followed by a \isakeyword{for} |
269 clause. |
172 clause. |
270 An instance has the following format: |
173 An instance has the following format: |
271 \begin{quote} |
174 \begin{quote} |
272 \textit{qualifier} \textbf{:} \textit{locale-name} |
175 \textit{qualifier} \textbf{:} \textit{locale-name} |
273 \textit{parameter-instantiation} |
176 \textit{parameter-instantiation} |
274 \end{quote} |
177 \end{quote} |
275 We have already seen locale instances as arguments to |
178 We have already seen locale instances as arguments to |
276 \isakeyword{interpretation} in Section~\ref{sec:interpretation}. |
179 \isakeyword{interpretation} in Section~\ref{sec:interpretation}. |
277 The qualifier serves to disambiguate the names from different |
180 As before, the qualifier serves to disambiguate names from |
278 instances of the same locale. |
181 different instances of the same locale. While in |
279 |
182 \isakeyword{interpretation} qualifiers default to mandatory, in |
280 Since the parameters @{text le} and @{text le'} are to be partial |
183 import and in the \isakeyword{sublocale} command, they default to |
|
184 optional. |
|
185 |
|
186 Since the parameters~@{text le} and~@{text le'} are to be partial |
281 orders, our locale for order preserving maps will import the these |
187 orders, our locale for order preserving maps will import the these |
282 instances: |
188 instances: |
|
189 \begin{small} |
283 \begin{alltt} |
190 \begin{alltt} |
284 le: partial_order le |
191 le: partial_order le |
285 le': partial_order le' |
192 le': partial_order le' |
286 \end{alltt} |
193 \end{alltt} |
287 For matter of convenience we choose the parameter names also as |
194 \end{small} |
288 qualifiers. This is an arbitrary decision. Technically, qualifiers |
195 For matter of convenience we choose to name parameter names and |
|
196 qualifiers alike. This is an arbitrary decision. Technically, qualifiers |
289 and parameters are unrelated. |
197 and parameters are unrelated. |
290 |
198 |
291 Having determined the instances, let us turn to the \isakeyword{for} |
199 Having determined the instances, let us turn to the \isakeyword{for} |
292 clause. It serves to declare locale parameters in the same way as |
200 clause. It serves to declare locale parameters in the same way as |
293 the context element \isakeyword{fixes} does. Context elements can |
201 the context element \isakeyword{fixes} does. Context elements can |
294 only occur after the import section, and therefore the parameters |
202 only occur after the import section, and therefore the parameters |
295 referred to inthe instances must be declared in the \isakeyword{for} |
203 referred to in the instances must be declared in the \isakeyword{for} |
296 clause.% |
204 clause. The \isakeyword{for} clause is also where the syntax of these |
297 \footnote{Since all parameters can be declared in the \isakeyword{for} |
|
298 clause, the context element \isakeyword{fixes} is not needed in |
|
299 locales. It is provided for compatibility with the long goals |
|
300 format, where the context element also occurs.} |
|
301 The \isakeyword{for} clause is also where the syntax of these |
|
302 parameters is declared. |
205 parameters is declared. |
303 |
206 |
304 Two context elements for the map parameter @{text \<phi>} and the |
207 Two context elements for the map parameter~@{text \<phi>} and the |
305 assumptions that it is order perserving complete the locale |
208 assumptions that it is order preserving complete the locale |
306 declaration. *} |
209 declaration. *} |
307 |
210 |
308 locale order_preserving = |
211 locale order_preserving = |
309 le: partial_order le + le': partial_order le' |
212 le: partial_order le + le': partial_order le' |
310 for le (infixl "\<sqsubseteq>" 50) and le' (infixl "\<preceq>" 50) + |
213 for le (infixl "\<sqsubseteq>" 50) and le' (infixl "\<preceq>" 50) + |
312 assumes hom_le: "x \<sqsubseteq> y \<Longrightarrow> \<phi> x \<preceq> \<phi> y" |
215 assumes hom_le: "x \<sqsubseteq> y \<Longrightarrow> \<phi> x \<preceq> \<phi> y" |
313 |
216 |
314 text (in order_preserving) {* Here are examples of theorems that are |
217 text (in order_preserving) {* Here are examples of theorems that are |
315 available in the locale: |
218 available in the locale: |
316 |
219 |
317 @{thm [source] hom_le}: @{thm hom_le} |
220 \hspace*{1em}@{thm [source] hom_le}: @{thm hom_le} |
318 |
221 |
319 @{thm [source] le.less_le_trans}: @{thm le.less_le_trans} |
222 \hspace*{1em}@{thm [source] le.less_le_trans}: @{thm le.less_le_trans} |
320 |
223 |
321 @{thm [source] le'.less_le_trans}: |
224 \hspace*{1em}@{thm [source] le'.less_le_trans}: |
322 @{thm [display, indent=2] le'.less_le_trans} |
225 @{thm [display, indent=4] le'.less_le_trans} |
323 |
|
324 While there is infix syntax for the strict operation associated to |
226 While there is infix syntax for the strict operation associated to |
325 @{term "op \<sqsubseteq>"}, there is none for the strict version of @{term |
227 @{term "op \<sqsubseteq>"}, there is none for the strict version of @{term |
326 "op \<preceq>"}. The abbreviation @{text less} with its infix syntax is only |
228 "op \<preceq>"}. The abbreviation @{text less} with its infix syntax is only |
327 available for the original instance it was declared for. We may |
229 available for the original instance it was declared for. We may |
328 introduce the abbreviation @{text less'} with infix syntax @{text \<prec>} |
230 introduce the abbreviation @{text less'} with infix syntax~@{text \<prec>} |
329 with this declaration: *} |
231 with the following declaration: *} |
330 |
232 |
331 abbreviation (in order_preserving) |
233 abbreviation (in order_preserving) |
332 less' (infixl "\<prec>" 50) where "less' \<equiv> partial_order.less le'" |
234 less' (infixl "\<prec>" 50) where "less' \<equiv> partial_order.less le'" |
333 |
235 |
334 text (in order_preserving) {* Now the theorem is displayed nicely as |
236 text (in order_preserving) {* Now the theorem is displayed nicely as |
335 @{thm [source] le'.less_le_trans}: |
237 @{thm [source] le'.less_le_trans}: |
336 @{thm [display, indent=2] le'.less_le_trans} *} |
238 @{thm [display, indent=2] le'.less_le_trans} *} |
337 |
239 |
338 |
240 text {* There are short notations for locale expressions. These are |
339 subsection {* Default Instantiations and Implicit Parameters *} |
241 discussed in the following. *} |
340 |
242 |
341 text {* It is possible to omit parameter instantiations in a locale |
243 |
342 expression. In that case, the instantiation defaults to the name of |
244 subsection {* Default Instantiations *} |
343 the parameter itself. That is, the locale expression @{text |
245 |
|
246 text {* |
|
247 It is possible to omit parameter instantiations. The |
|
248 instantiation then defaults to the name of |
|
249 the parameter itself. For example, the locale expression @{text |
344 partial_order} is short for @{text "partial_order le"}, since the |
250 partial_order} is short for @{text "partial_order le"}, since the |
345 locale's single parameter is @{text le}. We took advantage of this |
251 locale's single parameter is~@{text le}. We took advantage of this |
346 short hand in the \isakeyword{sublocale} declarations of |
252 in the \isakeyword{sublocale} declarations of |
347 Section~\ref{sec:changing-the-hierarchy}. *} |
253 Section~\ref{sec:changing-the-hierarchy}. *} |
348 |
254 |
|
255 |
|
256 subsection {* Implicit Parameters \label{sec:implicit-parameters} *} |
349 |
257 |
350 text {* In a locale expression that occurs within a locale |
258 text {* In a locale expression that occurs within a locale |
351 declaration, omitted parameters additionally extend the (possibly |
259 declaration, omitted parameters additionally extend the (possibly |
352 empty) \isakeyword{for} clause. |
260 empty) \isakeyword{for} clause. |
353 |
261 |
354 The \isakeyword{for} clause is a |
262 The \isakeyword{for} clause is a general construct of Isabelle/Isar |
355 general construct of Isabelle/Isar to mark names from the preceding |
263 to mark names occurring in the preceding declaration as ``arbitrary |
356 declaration as ``arbitrary but fixed''. This is necessary for |
264 but fixed''. This is necessary for example, if the name is already |
357 example, if the name is already bound in a surrounding context. In |
265 bound in a surrounding context. In a locale expression, names |
358 a locale expression, names occurring in parameter instantiations |
266 occurring in parameter instantiations should be bound by a |
359 should be bound by a \isakeyword{for} clause whenever these names |
267 \isakeyword{for} clause whenever these names are not introduced |
360 are not introduced elsewhere in the context --- for example, on the |
268 elsewhere in the context --- for example, on the left hand side of a |
361 left hand side of a \isakeyword{sublocale} declaration. |
269 \isakeyword{sublocale} declaration. |
362 |
270 |
363 There is an exception to this rule in locale declarations, where the |
271 There is an exception to this rule in locale declarations, where the |
364 \isakeyword{for} clause servers to declare locale parameters. Here, |
272 \isakeyword{for} clause serves to declare locale parameters. Here, |
365 locale parameters for which no parameter instantiation is given are |
273 locale parameters for which no parameter instantiation is given are |
366 implicitly added, with their mixfix syntax, at the beginning of the |
274 implicitly added, with their mixfix syntax, at the beginning of the |
367 \isakeyword{for} clause. For example, in a locale declaration, the |
275 \isakeyword{for} clause. For example, in a locale declaration, the |
368 expression @{text partial_order} is short for |
276 expression @{text partial_order} is short for |
|
277 \begin{small} |
369 \begin{alltt} |
278 \begin{alltt} |
370 partial_order le \isakeyword{for} le (\isakeyword{infixl} "\(\sqsubseteq\)" 50)\textrm{.} |
279 partial_order le \isakeyword{for} le (\isakeyword{infixl} "\(\sqsubseteq\)" 50)\textrm{.} |
371 \end{alltt} |
280 \end{alltt} |
372 This short hand was used in the locale declarations of |
281 \end{small} |
|
282 This short hand was used in the locale declarations throughout |
373 Section~\ref{sec:import}. |
283 Section~\ref{sec:import}. |
374 *} |
284 *} |
375 |
285 |
376 text{* |
286 text{* |
377 The following locale declarations provide more examples. A map |
287 The following locale declarations provide more examples. A |
378 @{text \<phi>} is a lattice homomorphism if it preserves meet and |
288 map~@{text \<phi>} is a lattice homomorphism if it preserves meet and |
379 join. *} |
289 join. *} |
380 |
290 |
381 locale lattice_hom = |
291 locale lattice_hom = |
382 le: lattice + le': lattice le' for le' (infixl "\<preceq>" 50) + |
292 le: lattice + le': lattice le' for le' (infixl "\<preceq>" 50) + |
383 fixes \<phi> |
293 fixes \<phi> |
384 assumes hom_meet: "\<phi> (x \<sqinter> y) = le'.meet (\<phi> x) (\<phi> y)" |
294 assumes hom_meet: "\<phi> (x \<sqinter> y) = le'.meet (\<phi> x) (\<phi> y)" |
385 and hom_join: "\<phi> (x \<squnion> y) = le'.join (\<phi> x) (\<phi> y)" |
295 and hom_join: "\<phi> (x \<squnion> y) = le'.join (\<phi> x) (\<phi> y)" |
386 |
296 |
387 text {* We omit the parameter instantiation in the first instance of |
297 text {* The parameter instantiation in the first instance of @{term |
388 @{term lattice}. This causes the parameter @{text le} to be added |
298 lattice} is omitted. This causes the parameter~@{text le} to be |
389 to the \isakeyword{for} clause, and the locale has parameters |
299 added to the \isakeyword{for} clause, and the locale has |
390 @{text le} and @{text le'}. |
300 parameters~@{text le},~@{text le'} and, of course,~@{text \<phi>}. |
391 |
301 |
392 Before turning to the second example, we complete the locale by |
302 Before turning to the second example, we complete the locale by |
393 provinding infix syntax for the meet and join operations of the |
303 providing infix syntax for the meet and join operations of the |
394 second lattice. |
304 second lattice. |
395 *} |
305 *} |
396 |
306 |
397 context lattice_hom begin |
307 context lattice_hom begin |
398 abbreviation meet' (infixl "\<sqinter>''" 50) where "meet' \<equiv> le'.meet" |
308 abbreviation meet' (infixl "\<sqinter>''" 50) where "meet' \<equiv> le'.meet" |
399 abbreviation join' (infixl "\<squnion>''" 50) where "join' \<equiv> le'.join" |
309 abbreviation join' (infixl "\<squnion>''" 50) where "join' \<equiv> le'.join" |
400 end |
310 end |
401 |
311 |
402 text {* The next example pushes the short hand facilities. A |
312 text {* The next example makes radical use of the short hand |
403 homomorphism is an endomorphism if both orders coincide. *} |
313 facilities. A homomorphism is an endomorphism if both orders |
|
314 coincide. *} |
404 |
315 |
405 locale lattice_end = lattice_hom _ le |
316 locale lattice_end = lattice_hom _ le |
406 |
317 |
407 text {* The notation @{text _} enables to omit a parameter in a |
318 text {* The notation~@{text _} enables to omit a parameter in a |
408 positional instantiation. The omitted parameter, @{text le} becomes |
319 positional instantiation. The omitted parameter,~@{text le} becomes |
409 the parameter of the declared locale and is, in the following |
320 the parameter of the declared locale and is, in the following |
410 position used to instantiate the second parameter of @{text |
321 position, used to instantiate the second parameter of @{text |
411 lattice_hom}. The effect is that of identifying the first in second |
322 lattice_hom}. The effect is that of identifying the first in second |
412 parameter of the homomorphism locale. *} |
323 parameter of the homomorphism locale. *} |
413 |
324 |
414 text {* The inheritance diagram of the situation we have now is shown |
325 text {* The inheritance diagram of the situation we have now is shown |
415 in Figure~\ref{fig:hom}, where the dashed line depicts an |
326 in Figure~\ref{fig:hom}, where the dashed line depicts an |
416 interpretation which is introduced below. Renamings are |
327 interpretation which is introduced below. Parameter instantiations |
417 indicated by $\sqsubseteq \mapsto \preceq$ etc. By looking at the |
328 are indicated by $\sqsubseteq \mapsto \preceq$ etc. By looking at |
418 inheritance diagram it would seem |
329 the inheritance diagram it would seem |
419 that two identical copies of each of the locales @{text |
330 that two identical copies of each of the locales @{text |
420 partial_order} and @{text lattice} are imported by @{text |
331 partial_order} and @{text lattice} are imported by @{text |
421 lattice_end}. This is not the case! Inheritance paths with |
332 lattice_end}. This is not the case! Inheritance paths with |
422 identical morphisms are automatically detected and |
333 identical morphisms are automatically detected and |
423 the conclusions of the respective locales appear only once. |
334 the conclusions of the respective locales appear only once. |
470 Theorems and other declarations --- syntax, in particular --- from |
381 Theorems and other declarations --- syntax, in particular --- from |
471 the locale @{text order_preserving} are now active in @{text |
382 the locale @{text order_preserving} are now active in @{text |
472 lattice_hom}, for example |
383 lattice_hom}, for example |
473 @{thm [source] hom_le}: |
384 @{thm [source] hom_le}: |
474 @{thm [display, indent=2] hom_le} |
385 @{thm [display, indent=2] hom_le} |
|
386 This theorem will be useful in the following section. |
475 *} |
387 *} |
476 |
388 |
477 (* |
389 |
478 section {* Conditional Interpretation *} |
390 section {* Conditional Interpretation *} |
|
391 |
|
392 text {* There are situations where an interpretation is not possible |
|
393 in the general case since the desired property is only valid if |
|
394 certain conditions are fulfilled. Take, for example, the function |
|
395 @{text "\<lambda>i. n * i"} that scales its argument by a constant factor. |
|
396 This function is order preserving (and even a lattice endomorphism) |
|
397 with respect to @{term "op \<le>"} provided @{text "n \<ge> 0"}. |
|
398 |
|
399 It is not possible to express this using a global interpretation, |
|
400 because it is in general unspecified whether~@{term n} is |
|
401 non-negative, but one may make an interpretation in an inner context |
|
402 of a proof where full information is available. |
|
403 This is not fully satisfactory either, since potentially |
|
404 interpretations may be required to make interpretations in many |
|
405 contexts. What is |
|
406 required is an interpretation that depends on the condition --- and |
|
407 this can be done with the \isakeyword{sublocale} command. For this |
|
408 purpose, we introduce a locale for the condition. *} |
479 |
409 |
480 locale non_negative = |
410 locale non_negative = |
481 fixes n :: int |
411 fixes n :: int |
482 assumes non_negative: "0 \<le> n" |
412 assumes non_neg: "0 \<le> n" |
483 |
413 |
484 interpretation partial_order "op \<le> :: int \<Rightarrow> int \<Rightarrow> bool" |
414 text {* It is again convenient to make the interpretation in an |
485 where "partial_order.less op \<le> (x::int) y = (x < y)" |
415 incremental fashion, first for order preserving maps, the for |
486 sorry |
416 lattice endomorphisms. *} |
487 |
417 |
488 sublocale non_negative \<subseteq> order_preserving "op \<le>" "op \<le>" "\<lambda>i. n * i" |
418 sublocale non_negative \<subseteq> |
489 apply unfold_locales using non_negative apply - by (rule mult_left_mono) |
419 order_preserving "op \<le>" "op \<le>" "\<lambda>i. n * i" |
490 |
420 using non_neg by unfold_locales (rule mult_left_mono) |
491 interpretation lattice "op \<le> :: int \<Rightarrow> int \<Rightarrow> bool" |
421 |
492 where min_eq: "lattice.meet op \<le> (x::int) y = min x y" |
422 text {* While the proof of the previous interpretation |
493 and max_eq: "lattice.join op \<le> (x::int) y = max x y" |
423 is straightforward from monotonicity lemmas for~@{term "op *"}, the |
494 sorry |
424 second proof follows a useful pattern. *} |
495 |
425 |
496 apply unfold_locales unfolding is_inf_def is_sup_def by arith+ |
426 sublocale %visible non_negative \<subseteq> lattice_end "op \<le>" "\<lambda>i. n * i" |
497 |
427 proof (unfold_locales, unfold int_min_eq int_max_eq) |
498 |
428 txt {* \normalsize Unfolding the locale predicates \emph{and} the |
499 sublocale non_negative \<subseteq> lattice_end "op \<le>" "\<lambda>i. n * i" |
429 interpretation equations immediately yields two subgoals that |
500 apply unfold_locales unfolding min_eq max_eq apply (case_tac "x \<le> y") |
430 reflect the core conjecture. |
501 unfolding min_def apply auto apply arith |
431 @{subgoals [display]} |
502 apply (rule sym) |
432 It is now necessary to show, in the context of @{term |
503 apply (rule the_equality) |
433 non_negative}, that multiplication by~@{term n} commutes with |
504 proof |
434 @{term min} and @{term max}. *} |
505 |
435 qed (auto simp: hom_le) |
506 locale fspace_po = partial_order |
436 |
507 sublocale fspace_po \<subseteq> fspace: partial_order "\<lambda>f g. \<forall>x. f x \<sqsubseteq> g x" |
437 text (in order_preserving) {* The lemma @{thm [source] hom_le} |
508 (* fspace needed to disambiguate less etc *) |
438 simplifies a proof that would have otherwise been lengthy and we may |
509 apply unfold_locales |
439 consider making it a default rule for the simplifier: *} |
510 apply auto |
440 |
511 apply (rule) apply auto apply (blast intro: trans) done |
441 lemmas (in order_preserving) hom_le [simp] |
512 |
442 |
513 *) |
443 |
|
444 subsection {* Avoiding Infinite Chains of Interpretations |
|
445 \label{sec:infinite-chains} *} |
|
446 |
|
447 text {* Similar situations arise frequently in formalisations of |
|
448 abstract algebra where it is desirable to express that certain |
|
449 constructions preserve certain properties. For example, polynomials |
|
450 over rings are rings, or --- an example from the domain where the |
|
451 illustrations of this tutorial are taken from --- a partial order |
|
452 may be obtained for a function space by point-wise lifting of the |
|
453 partial order of the co-domain. This corresponds to the following |
|
454 interpretation: *} |
|
455 |
|
456 sublocale %visible partial_order \<subseteq> f: partial_order "\<lambda>f g. \<forall>x. f x \<sqsubseteq> g x" |
|
457 oops |
|
458 |
|
459 text {* Unfortunately this is a cyclic interpretation that leads to an |
|
460 infinite chain, namely |
|
461 @{text [display, indent=2] "partial_order \<subseteq> partial_order (\<lambda>f g. \<forall>x. f x \<sqsubseteq> g x) \<subseteq> |
|
462 partial_order (\<lambda>f g. \<forall>x y. f x y \<sqsubseteq> g x y) \<subseteq> \<dots>"} |
|
463 and the interpretation is rejected. |
|
464 |
|
465 Instead it is necessary to declare a locale that is logically |
|
466 equivalent to @{term partial_order} but serves to collect facts |
|
467 about functions spaces where the co-domain is a partial order, and |
|
468 to make the interpretation in its context: *} |
|
469 |
|
470 locale fun_partial_order = partial_order |
|
471 |
|
472 sublocale fun_partial_order \<subseteq> |
|
473 f: partial_order "\<lambda>f g. \<forall>x. f x \<sqsubseteq> g x" |
|
474 by unfold_locales (fast,rule,fast,blast intro: trans) |
|
475 |
|
476 text {* It is quite common in abstract algebra that such a construction |
|
477 maps a hierarchy of algebraic structures (or specifications) to a |
|
478 related hierarchy. By means of the same lifting, a function space |
|
479 is a lattice if its co-domain is a lattice: *} |
|
480 |
|
481 locale fun_lattice = fun_partial_order + lattice |
|
482 |
|
483 sublocale fun_lattice \<subseteq> f: lattice "\<lambda>f g. \<forall>x. f x \<sqsubseteq> g x" |
|
484 proof unfold_locales |
|
485 fix f g |
|
486 have "partial_order.is_inf (\<lambda>f g. \<forall>x. f x \<sqsubseteq> g x) f g (\<lambda>x. f x \<sqinter> g x)" |
|
487 apply (rule is_infI) apply rule+ apply (drule spec, assumption)+ done |
|
488 then show "\<exists>inf. partial_order.is_inf (\<lambda>f g. \<forall>x. f x \<sqsubseteq> g x) f g inf" |
|
489 by fast |
|
490 next |
|
491 fix f g |
|
492 have "partial_order.is_sup (\<lambda>f g. \<forall>x. f x \<sqsubseteq> g x) f g (\<lambda>x. f x \<squnion> g x)" |
|
493 apply (rule is_supI) apply rule+ apply (drule spec, assumption)+ done |
|
494 then show "\<exists>sup. partial_order.is_sup (\<lambda>f g. \<forall>x. f x \<sqsubseteq> g x) f g sup" |
|
495 by fast |
|
496 qed |
|
497 |
514 |
498 |
515 section {* Further Reading *} |
499 section {* Further Reading *} |
516 |
500 |
517 text {* More information on locales and their interpretation is |
501 text {* More information on locales and their interpretation is |
518 available. For the locale hierarchy of import and interpretation |
502 available. For the locale hierarchy of import and interpretation |
519 dependencies see \cite{Ballarin2006a}; interpretations in theories |
503 dependencies see~\cite{Ballarin2006a}; interpretations in theories |
520 and proofs are covered in \cite{Ballarin2006b}. In the latter, I |
504 and proofs are covered in~\cite{Ballarin2006b}. In the latter, I |
521 show how interpretation in proofs enables to reason about families |
505 show how interpretation in proofs enables to reason about families |
522 of algebraic structures, which cannot be expressed with locales |
506 of algebraic structures, which cannot be expressed with locales |
523 directly. |
507 directly. |
524 |
508 |
525 Haftmann and Wenzel \cite{HaftmannWenzel2007} overcome a restriction |
509 Haftmann and Wenzel~\cite{HaftmannWenzel2007} overcome a restriction |
526 of axiomatic type classes through a combination with locale |
510 of axiomatic type classes through a combination with locale |
527 interpretation. The result is a Haskell-style class system with a |
511 interpretation. The result is a Haskell-style class system with a |
528 facility to generate ML and Haskell code. Classes are sufficient for |
512 facility to generate ML and Haskell code. Classes are sufficient for |
529 simple specifications with a single type parameter. The locales for |
513 simple specifications with a single type parameter. The locales for |
530 orders and lattices presented in this tutorial fall into this |
514 orders and lattices presented in this tutorial fall into this |
531 category. Order preserving maps, homomorphisms and vector spaces, |
515 category. Order preserving maps, homomorphisms and vector spaces, |
532 on the other hand, do not. |
516 on the other hand, do not. |
533 |
517 |
534 The locales reimplementation for Isabelle 2009 provides, among other |
518 The locales reimplementation for Isabelle 2009 provides, among other |
535 improvements, a clean intergration with Isabelle/Isar's local theory |
519 improvements, a clean integration with Isabelle/Isar's local theory |
536 mechnisms, which are described in \cite{HaftmannWenzel2009}. |
520 mechanisms, which are described in another paper by Haftmann and |
537 |
521 Wenzel~\cite{HaftmannWenzel2009}. |
538 The original work of Kamm\"uller on locales \cite{KammullerEtAl1999} |
522 |
539 may be of interest from a historical perspective. The mathematical |
523 The original work of Kamm\"uller on locales~\cite{KammullerEtAl1999} |
540 background on orders and lattices is taken from Jacobson's textbook |
524 may be of interest from a historical perspective. My previous |
541 on algebra \cite[Chapter~8]{Jacobson1985}. |
525 report on locales and locale expressions~\cite{Ballarin2004a} |
|
526 describes a simpler form of expressions than available now and is |
|
527 outdated. The mathematical background on orders and lattices is |
|
528 taken from Jacobson's textbook on algebra~\cite[Chapter~8]{Jacobson1985}. |
542 |
529 |
543 The sources of this tutorial, which include all proofs, are |
530 The sources of this tutorial, which include all proofs, are |
544 available with the Isabelle distribution at |
531 available with the Isabelle distribution at |
545 \url{http://isabelle.in.tum.de}. |
532 \url{http://isabelle.in.tum.de}. |
546 *} |
533 *} |