1 (* Title: HOLCF/Bifinite.thy |
|
2 Author: Brian Huffman |
|
3 *) |
|
4 |
|
5 header {* Bifinite domains *} |
|
6 |
|
7 theory Bifinite |
|
8 imports Algebraic Map_Functions Countable |
|
9 begin |
|
10 |
|
11 subsection {* Class of bifinite domains *} |
|
12 |
|
13 text {* |
|
14 We define a ``domain'' as a pcpo that is isomorphic to some |
|
15 algebraic deflation over the universal domain; this is equivalent |
|
16 to being omega-bifinite. |
|
17 |
|
18 A predomain is a cpo that, when lifted, becomes a domain. |
|
19 *} |
|
20 |
|
21 class predomain = cpo + |
|
22 fixes liftdefl :: "('a::cpo) itself \<Rightarrow> defl" |
|
23 fixes liftemb :: "'a\<^sub>\<bottom> \<rightarrow> udom" |
|
24 fixes liftprj :: "udom \<rightarrow> 'a\<^sub>\<bottom>" |
|
25 assumes predomain_ep: "ep_pair liftemb liftprj" |
|
26 assumes cast_liftdefl: "cast\<cdot>(liftdefl TYPE('a::cpo)) = liftemb oo liftprj" |
|
27 |
|
28 syntax "_LIFTDEFL" :: "type \<Rightarrow> logic" ("(1LIFTDEFL/(1'(_')))") |
|
29 translations "LIFTDEFL('t)" \<rightleftharpoons> "CONST liftdefl TYPE('t)" |
|
30 |
|
31 class "domain" = predomain + pcpo + |
|
32 fixes emb :: "'a::cpo \<rightarrow> udom" |
|
33 fixes prj :: "udom \<rightarrow> 'a::cpo" |
|
34 fixes defl :: "'a itself \<Rightarrow> defl" |
|
35 assumes ep_pair_emb_prj: "ep_pair emb prj" |
|
36 assumes cast_DEFL: "cast\<cdot>(defl TYPE('a)) = emb oo prj" |
|
37 |
|
38 syntax "_DEFL" :: "type \<Rightarrow> defl" ("(1DEFL/(1'(_')))") |
|
39 translations "DEFL('t)" \<rightleftharpoons> "CONST defl TYPE('t)" |
|
40 |
|
41 interpretation "domain": pcpo_ep_pair emb prj |
|
42 unfolding pcpo_ep_pair_def |
|
43 by (rule ep_pair_emb_prj) |
|
44 |
|
45 lemmas emb_inverse = domain.e_inverse |
|
46 lemmas emb_prj_below = domain.e_p_below |
|
47 lemmas emb_eq_iff = domain.e_eq_iff |
|
48 lemmas emb_strict = domain.e_strict |
|
49 lemmas prj_strict = domain.p_strict |
|
50 |
|
51 subsection {* Domains have a countable compact basis *} |
|
52 |
|
53 text {* |
|
54 Eventually it should be possible to generalize this to an unpointed |
|
55 variant of the domain class. |
|
56 *} |
|
57 |
|
58 interpretation compact_basis: |
|
59 ideal_completion below Rep_compact_basis "approximants::'a::domain \<Rightarrow> _" |
|
60 proof - |
|
61 obtain Y where Y: "\<forall>i. Y i \<sqsubseteq> Y (Suc i)" |
|
62 and DEFL: "DEFL('a) = (\<Squnion>i. defl_principal (Y i))" |
|
63 by (rule defl.obtain_principal_chain) |
|
64 def approx \<equiv> "\<lambda>i. (prj oo cast\<cdot>(defl_principal (Y i)) oo emb) :: 'a \<rightarrow> 'a" |
|
65 interpret defl_approx: approx_chain approx |
|
66 proof (rule approx_chain.intro) |
|
67 show "chain (\<lambda>i. approx i)" |
|
68 unfolding approx_def by (simp add: Y) |
|
69 show "(\<Squnion>i. approx i) = ID" |
|
70 unfolding approx_def |
|
71 by (simp add: lub_distribs Y DEFL [symmetric] cast_DEFL cfun_eq_iff) |
|
72 show "\<And>i. finite_deflation (approx i)" |
|
73 unfolding approx_def |
|
74 apply (rule domain.finite_deflation_p_d_e) |
|
75 apply (rule finite_deflation_cast) |
|
76 apply (rule defl.compact_principal) |
|
77 apply (rule below_trans [OF monofun_cfun_fun]) |
|
78 apply (rule is_ub_thelub, simp add: Y) |
|
79 apply (simp add: lub_distribs Y DEFL [symmetric] cast_DEFL) |
|
80 done |
|
81 qed |
|
82 (* FIXME: why does show ?thesis fail here? *) |
|
83 show "ideal_completion below Rep_compact_basis (approximants::'a \<Rightarrow> _)" .. |
|
84 qed |
|
85 |
|
86 subsection {* Chains of approx functions *} |
|
87 |
|
88 definition u_approx :: "nat \<Rightarrow> udom\<^sub>\<bottom> \<rightarrow> udom\<^sub>\<bottom>" |
|
89 where "u_approx = (\<lambda>i. u_map\<cdot>(udom_approx i))" |
|
90 |
|
91 definition sfun_approx :: "nat \<Rightarrow> (udom \<rightarrow>! udom) \<rightarrow> (udom \<rightarrow>! udom)" |
|
92 where "sfun_approx = (\<lambda>i. sfun_map\<cdot>(udom_approx i)\<cdot>(udom_approx i))" |
|
93 |
|
94 definition prod_approx :: "nat \<Rightarrow> udom \<times> udom \<rightarrow> udom \<times> udom" |
|
95 where "prod_approx = (\<lambda>i. cprod_map\<cdot>(udom_approx i)\<cdot>(udom_approx i))" |
|
96 |
|
97 definition sprod_approx :: "nat \<Rightarrow> udom \<otimes> udom \<rightarrow> udom \<otimes> udom" |
|
98 where "sprod_approx = (\<lambda>i. sprod_map\<cdot>(udom_approx i)\<cdot>(udom_approx i))" |
|
99 |
|
100 definition ssum_approx :: "nat \<Rightarrow> udom \<oplus> udom \<rightarrow> udom \<oplus> udom" |
|
101 where "ssum_approx = (\<lambda>i. ssum_map\<cdot>(udom_approx i)\<cdot>(udom_approx i))" |
|
102 |
|
103 lemma approx_chain_lemma1: |
|
104 assumes "m\<cdot>ID = ID" |
|
105 assumes "\<And>d. finite_deflation d \<Longrightarrow> finite_deflation (m\<cdot>d)" |
|
106 shows "approx_chain (\<lambda>i. m\<cdot>(udom_approx i))" |
|
107 by (rule approx_chain.intro) |
|
108 (simp_all add: lub_distribs finite_deflation_udom_approx assms) |
|
109 |
|
110 lemma approx_chain_lemma2: |
|
111 assumes "m\<cdot>ID\<cdot>ID = ID" |
|
112 assumes "\<And>a b. \<lbrakk>finite_deflation a; finite_deflation b\<rbrakk> |
|
113 \<Longrightarrow> finite_deflation (m\<cdot>a\<cdot>b)" |
|
114 shows "approx_chain (\<lambda>i. m\<cdot>(udom_approx i)\<cdot>(udom_approx i))" |
|
115 by (rule approx_chain.intro) |
|
116 (simp_all add: lub_distribs finite_deflation_udom_approx assms) |
|
117 |
|
118 lemma u_approx: "approx_chain u_approx" |
|
119 using u_map_ID finite_deflation_u_map |
|
120 unfolding u_approx_def by (rule approx_chain_lemma1) |
|
121 |
|
122 lemma sfun_approx: "approx_chain sfun_approx" |
|
123 using sfun_map_ID finite_deflation_sfun_map |
|
124 unfolding sfun_approx_def by (rule approx_chain_lemma2) |
|
125 |
|
126 lemma prod_approx: "approx_chain prod_approx" |
|
127 using cprod_map_ID finite_deflation_cprod_map |
|
128 unfolding prod_approx_def by (rule approx_chain_lemma2) |
|
129 |
|
130 lemma sprod_approx: "approx_chain sprod_approx" |
|
131 using sprod_map_ID finite_deflation_sprod_map |
|
132 unfolding sprod_approx_def by (rule approx_chain_lemma2) |
|
133 |
|
134 lemma ssum_approx: "approx_chain ssum_approx" |
|
135 using ssum_map_ID finite_deflation_ssum_map |
|
136 unfolding ssum_approx_def by (rule approx_chain_lemma2) |
|
137 |
|
138 subsection {* Type combinators *} |
|
139 |
|
140 definition |
|
141 defl_fun1 :: |
|
142 "(nat \<Rightarrow> 'a \<rightarrow> 'a) \<Rightarrow> ((udom \<rightarrow> udom) \<rightarrow> ('a \<rightarrow> 'a)) \<Rightarrow> (defl \<rightarrow> defl)" |
|
143 where |
|
144 "defl_fun1 approx f = |
|
145 defl.basis_fun (\<lambda>a. |
|
146 defl_principal (Abs_fin_defl |
|
147 (udom_emb approx oo f\<cdot>(Rep_fin_defl a) oo udom_prj approx)))" |
|
148 |
|
149 definition |
|
150 defl_fun2 :: |
|
151 "(nat \<Rightarrow> 'a \<rightarrow> 'a) \<Rightarrow> ((udom \<rightarrow> udom) \<rightarrow> (udom \<rightarrow> udom) \<rightarrow> ('a \<rightarrow> 'a)) |
|
152 \<Rightarrow> (defl \<rightarrow> defl \<rightarrow> defl)" |
|
153 where |
|
154 "defl_fun2 approx f = |
|
155 defl.basis_fun (\<lambda>a. |
|
156 defl.basis_fun (\<lambda>b. |
|
157 defl_principal (Abs_fin_defl |
|
158 (udom_emb approx oo |
|
159 f\<cdot>(Rep_fin_defl a)\<cdot>(Rep_fin_defl b) oo udom_prj approx))))" |
|
160 |
|
161 lemma cast_defl_fun1: |
|
162 assumes approx: "approx_chain approx" |
|
163 assumes f: "\<And>a. finite_deflation a \<Longrightarrow> finite_deflation (f\<cdot>a)" |
|
164 shows "cast\<cdot>(defl_fun1 approx f\<cdot>A) = udom_emb approx oo f\<cdot>(cast\<cdot>A) oo udom_prj approx" |
|
165 proof - |
|
166 have 1: "\<And>a. finite_deflation |
|
167 (udom_emb approx oo f\<cdot>(Rep_fin_defl a) oo udom_prj approx)" |
|
168 apply (rule ep_pair.finite_deflation_e_d_p) |
|
169 apply (rule approx_chain.ep_pair_udom [OF approx]) |
|
170 apply (rule f, rule finite_deflation_Rep_fin_defl) |
|
171 done |
|
172 show ?thesis |
|
173 by (induct A rule: defl.principal_induct, simp) |
|
174 (simp only: defl_fun1_def |
|
175 defl.basis_fun_principal |
|
176 defl.basis_fun_mono |
|
177 defl.principal_mono |
|
178 Abs_fin_defl_mono [OF 1 1] |
|
179 monofun_cfun below_refl |
|
180 Rep_fin_defl_mono |
|
181 cast_defl_principal |
|
182 Abs_fin_defl_inverse [unfolded mem_Collect_eq, OF 1]) |
|
183 qed |
|
184 |
|
185 lemma cast_defl_fun2: |
|
186 assumes approx: "approx_chain approx" |
|
187 assumes f: "\<And>a b. finite_deflation a \<Longrightarrow> finite_deflation b \<Longrightarrow> |
|
188 finite_deflation (f\<cdot>a\<cdot>b)" |
|
189 shows "cast\<cdot>(defl_fun2 approx f\<cdot>A\<cdot>B) = |
|
190 udom_emb approx oo f\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo udom_prj approx" |
|
191 proof - |
|
192 have 1: "\<And>a b. finite_deflation (udom_emb approx oo |
|
193 f\<cdot>(Rep_fin_defl a)\<cdot>(Rep_fin_defl b) oo udom_prj approx)" |
|
194 apply (rule ep_pair.finite_deflation_e_d_p) |
|
195 apply (rule ep_pair_udom [OF approx]) |
|
196 apply (rule f, (rule finite_deflation_Rep_fin_defl)+) |
|
197 done |
|
198 show ?thesis |
|
199 by (induct A B rule: defl.principal_induct2, simp, simp) |
|
200 (simp only: defl_fun2_def |
|
201 defl.basis_fun_principal |
|
202 defl.basis_fun_mono |
|
203 defl.principal_mono |
|
204 Abs_fin_defl_mono [OF 1 1] |
|
205 monofun_cfun below_refl |
|
206 Rep_fin_defl_mono |
|
207 cast_defl_principal |
|
208 Abs_fin_defl_inverse [unfolded mem_Collect_eq, OF 1]) |
|
209 qed |
|
210 |
|
211 definition u_defl :: "defl \<rightarrow> defl" |
|
212 where "u_defl = defl_fun1 u_approx u_map" |
|
213 |
|
214 definition sfun_defl :: "defl \<rightarrow> defl \<rightarrow> defl" |
|
215 where "sfun_defl = defl_fun2 sfun_approx sfun_map" |
|
216 |
|
217 definition prod_defl :: "defl \<rightarrow> defl \<rightarrow> defl" |
|
218 where "prod_defl = defl_fun2 prod_approx cprod_map" |
|
219 |
|
220 definition sprod_defl :: "defl \<rightarrow> defl \<rightarrow> defl" |
|
221 where "sprod_defl = defl_fun2 sprod_approx sprod_map" |
|
222 |
|
223 definition ssum_defl :: "defl \<rightarrow> defl \<rightarrow> defl" |
|
224 where "ssum_defl = defl_fun2 ssum_approx ssum_map" |
|
225 |
|
226 lemma cast_u_defl: |
|
227 "cast\<cdot>(u_defl\<cdot>A) = |
|
228 udom_emb u_approx oo u_map\<cdot>(cast\<cdot>A) oo udom_prj u_approx" |
|
229 using u_approx finite_deflation_u_map |
|
230 unfolding u_defl_def by (rule cast_defl_fun1) |
|
231 |
|
232 lemma cast_sfun_defl: |
|
233 "cast\<cdot>(sfun_defl\<cdot>A\<cdot>B) = |
|
234 udom_emb sfun_approx oo sfun_map\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo udom_prj sfun_approx" |
|
235 using sfun_approx finite_deflation_sfun_map |
|
236 unfolding sfun_defl_def by (rule cast_defl_fun2) |
|
237 |
|
238 lemma cast_prod_defl: |
|
239 "cast\<cdot>(prod_defl\<cdot>A\<cdot>B) = udom_emb prod_approx oo |
|
240 cprod_map\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo udom_prj prod_approx" |
|
241 using prod_approx finite_deflation_cprod_map |
|
242 unfolding prod_defl_def by (rule cast_defl_fun2) |
|
243 |
|
244 lemma cast_sprod_defl: |
|
245 "cast\<cdot>(sprod_defl\<cdot>A\<cdot>B) = |
|
246 udom_emb sprod_approx oo |
|
247 sprod_map\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo |
|
248 udom_prj sprod_approx" |
|
249 using sprod_approx finite_deflation_sprod_map |
|
250 unfolding sprod_defl_def by (rule cast_defl_fun2) |
|
251 |
|
252 lemma cast_ssum_defl: |
|
253 "cast\<cdot>(ssum_defl\<cdot>A\<cdot>B) = |
|
254 udom_emb ssum_approx oo ssum_map\<cdot>(cast\<cdot>A)\<cdot>(cast\<cdot>B) oo udom_prj ssum_approx" |
|
255 using ssum_approx finite_deflation_ssum_map |
|
256 unfolding ssum_defl_def by (rule cast_defl_fun2) |
|
257 |
|
258 subsection {* Lemma for proving domain instances *} |
|
259 |
|
260 text {* |
|
261 A class of domains where @{const liftemb}, @{const liftprj}, |
|
262 and @{const liftdefl} are all defined in the standard way. |
|
263 *} |
|
264 |
|
265 class liftdomain = "domain" + |
|
266 assumes liftemb_eq: "liftemb = udom_emb u_approx oo u_map\<cdot>emb" |
|
267 assumes liftprj_eq: "liftprj = u_map\<cdot>prj oo udom_prj u_approx" |
|
268 assumes liftdefl_eq: "liftdefl TYPE('a::cpo) = u_defl\<cdot>DEFL('a)" |
|
269 |
|
270 text {* Temporarily relax type constraints. *} |
|
271 |
|
272 setup {* |
|
273 fold Sign.add_const_constraint |
|
274 [ (@{const_name defl}, SOME @{typ "'a::pcpo itself \<Rightarrow> defl"}) |
|
275 , (@{const_name emb}, SOME @{typ "'a::pcpo \<rightarrow> udom"}) |
|
276 , (@{const_name prj}, SOME @{typ "udom \<rightarrow> 'a::pcpo"}) |
|
277 , (@{const_name liftdefl}, SOME @{typ "'a::pcpo itself \<Rightarrow> defl"}) |
|
278 , (@{const_name liftemb}, SOME @{typ "'a::pcpo u \<rightarrow> udom"}) |
|
279 , (@{const_name liftprj}, SOME @{typ "udom \<rightarrow> 'a::pcpo u"}) ] |
|
280 *} |
|
281 |
|
282 lemma liftdomain_class_intro: |
|
283 assumes liftemb: "(liftemb :: 'a u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb" |
|
284 assumes liftprj: "(liftprj :: udom \<rightarrow> 'a u) = u_map\<cdot>prj oo udom_prj u_approx" |
|
285 assumes liftdefl: "liftdefl TYPE('a) = u_defl\<cdot>DEFL('a)" |
|
286 assumes ep_pair: "ep_pair emb (prj :: udom \<rightarrow> 'a)" |
|
287 assumes cast_defl: "cast\<cdot>DEFL('a) = emb oo (prj :: udom \<rightarrow> 'a)" |
|
288 shows "OFCLASS('a, liftdomain_class)" |
|
289 proof |
|
290 show "ep_pair liftemb (liftprj :: udom \<rightarrow> 'a u)" |
|
291 unfolding liftemb liftprj |
|
292 by (intro ep_pair_comp ep_pair_u_map ep_pair ep_pair_udom u_approx) |
|
293 show "cast\<cdot>LIFTDEFL('a) = liftemb oo (liftprj :: udom \<rightarrow> 'a u)" |
|
294 unfolding liftemb liftprj liftdefl |
|
295 by (simp add: cfcomp1 cast_u_defl cast_defl u_map_map) |
|
296 next |
|
297 qed fact+ |
|
298 |
|
299 text {* Restore original type constraints. *} |
|
300 |
|
301 setup {* |
|
302 fold Sign.add_const_constraint |
|
303 [ (@{const_name defl}, SOME @{typ "'a::domain itself \<Rightarrow> defl"}) |
|
304 , (@{const_name emb}, SOME @{typ "'a::domain \<rightarrow> udom"}) |
|
305 , (@{const_name prj}, SOME @{typ "udom \<rightarrow> 'a::domain"}) |
|
306 , (@{const_name liftdefl}, SOME @{typ "'a::predomain itself \<Rightarrow> defl"}) |
|
307 , (@{const_name liftemb}, SOME @{typ "'a::predomain u \<rightarrow> udom"}) |
|
308 , (@{const_name liftprj}, SOME @{typ "udom \<rightarrow> 'a::predomain u"}) ] |
|
309 *} |
|
310 |
|
311 subsection {* Class instance proofs *} |
|
312 |
|
313 subsubsection {* Universal domain *} |
|
314 |
|
315 instantiation udom :: liftdomain |
|
316 begin |
|
317 |
|
318 definition [simp]: |
|
319 "emb = (ID :: udom \<rightarrow> udom)" |
|
320 |
|
321 definition [simp]: |
|
322 "prj = (ID :: udom \<rightarrow> udom)" |
|
323 |
|
324 definition |
|
325 "defl (t::udom itself) = (\<Squnion>i. defl_principal (Abs_fin_defl (udom_approx i)))" |
|
326 |
|
327 definition |
|
328 "(liftemb :: udom u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb" |
|
329 |
|
330 definition |
|
331 "(liftprj :: udom \<rightarrow> udom u) = u_map\<cdot>prj oo udom_prj u_approx" |
|
332 |
|
333 definition |
|
334 "liftdefl (t::udom itself) = u_defl\<cdot>DEFL(udom)" |
|
335 |
|
336 instance |
|
337 using liftemb_udom_def liftprj_udom_def liftdefl_udom_def |
|
338 proof (rule liftdomain_class_intro) |
|
339 show "ep_pair emb (prj :: udom \<rightarrow> udom)" |
|
340 by (simp add: ep_pair.intro) |
|
341 show "cast\<cdot>DEFL(udom) = emb oo (prj :: udom \<rightarrow> udom)" |
|
342 unfolding defl_udom_def |
|
343 apply (subst contlub_cfun_arg) |
|
344 apply (rule chainI) |
|
345 apply (rule defl.principal_mono) |
|
346 apply (simp add: below_fin_defl_def) |
|
347 apply (simp add: Abs_fin_defl_inverse finite_deflation_udom_approx) |
|
348 apply (rule chainE) |
|
349 apply (rule chain_udom_approx) |
|
350 apply (subst cast_defl_principal) |
|
351 apply (simp add: Abs_fin_defl_inverse finite_deflation_udom_approx) |
|
352 done |
|
353 qed |
|
354 |
|
355 end |
|
356 |
|
357 subsubsection {* Lifted cpo *} |
|
358 |
|
359 instantiation u :: (predomain) liftdomain |
|
360 begin |
|
361 |
|
362 definition |
|
363 "emb = liftemb" |
|
364 |
|
365 definition |
|
366 "prj = liftprj" |
|
367 |
|
368 definition |
|
369 "defl (t::'a u itself) = LIFTDEFL('a)" |
|
370 |
|
371 definition |
|
372 "(liftemb :: 'a u u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb" |
|
373 |
|
374 definition |
|
375 "(liftprj :: udom \<rightarrow> 'a u u) = u_map\<cdot>prj oo udom_prj u_approx" |
|
376 |
|
377 definition |
|
378 "liftdefl (t::'a u itself) = u_defl\<cdot>DEFL('a u)" |
|
379 |
|
380 instance |
|
381 using liftemb_u_def liftprj_u_def liftdefl_u_def |
|
382 proof (rule liftdomain_class_intro) |
|
383 show "ep_pair emb (prj :: udom \<rightarrow> 'a u)" |
|
384 unfolding emb_u_def prj_u_def |
|
385 by (rule predomain_ep) |
|
386 show "cast\<cdot>DEFL('a u) = emb oo (prj :: udom \<rightarrow> 'a u)" |
|
387 unfolding emb_u_def prj_u_def defl_u_def |
|
388 by (rule cast_liftdefl) |
|
389 qed |
|
390 |
|
391 end |
|
392 |
|
393 lemma DEFL_u: "DEFL('a::predomain u) = LIFTDEFL('a)" |
|
394 by (rule defl_u_def) |
|
395 |
|
396 subsubsection {* Strict function space *} |
|
397 |
|
398 instantiation sfun :: ("domain", "domain") liftdomain |
|
399 begin |
|
400 |
|
401 definition |
|
402 "emb = udom_emb sfun_approx oo sfun_map\<cdot>prj\<cdot>emb" |
|
403 |
|
404 definition |
|
405 "prj = sfun_map\<cdot>emb\<cdot>prj oo udom_prj sfun_approx" |
|
406 |
|
407 definition |
|
408 "defl (t::('a \<rightarrow>! 'b) itself) = sfun_defl\<cdot>DEFL('a)\<cdot>DEFL('b)" |
|
409 |
|
410 definition |
|
411 "(liftemb :: ('a \<rightarrow>! 'b) u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb" |
|
412 |
|
413 definition |
|
414 "(liftprj :: udom \<rightarrow> ('a \<rightarrow>! 'b) u) = u_map\<cdot>prj oo udom_prj u_approx" |
|
415 |
|
416 definition |
|
417 "liftdefl (t::('a \<rightarrow>! 'b) itself) = u_defl\<cdot>DEFL('a \<rightarrow>! 'b)" |
|
418 |
|
419 instance |
|
420 using liftemb_sfun_def liftprj_sfun_def liftdefl_sfun_def |
|
421 proof (rule liftdomain_class_intro) |
|
422 show "ep_pair emb (prj :: udom \<rightarrow> 'a \<rightarrow>! 'b)" |
|
423 unfolding emb_sfun_def prj_sfun_def |
|
424 using ep_pair_udom [OF sfun_approx] |
|
425 by (intro ep_pair_comp ep_pair_sfun_map ep_pair_emb_prj) |
|
426 show "cast\<cdot>DEFL('a \<rightarrow>! 'b) = emb oo (prj :: udom \<rightarrow> 'a \<rightarrow>! 'b)" |
|
427 unfolding emb_sfun_def prj_sfun_def defl_sfun_def cast_sfun_defl |
|
428 by (simp add: cast_DEFL oo_def sfun_eq_iff sfun_map_map) |
|
429 qed |
|
430 |
|
431 end |
|
432 |
|
433 lemma DEFL_sfun: |
|
434 "DEFL('a::domain \<rightarrow>! 'b::domain) = sfun_defl\<cdot>DEFL('a)\<cdot>DEFL('b)" |
|
435 by (rule defl_sfun_def) |
|
436 |
|
437 subsubsection {* Continuous function space *} |
|
438 |
|
439 text {* |
|
440 Types @{typ "'a \<rightarrow> 'b"} and @{typ "'a u \<rightarrow>! 'b"} are isomorphic. |
|
441 *} |
|
442 |
|
443 definition |
|
444 "encode_cfun = (\<Lambda> f. sfun_abs\<cdot>(fup\<cdot>f))" |
|
445 |
|
446 definition |
|
447 "decode_cfun = (\<Lambda> g x. sfun_rep\<cdot>g\<cdot>(up\<cdot>x))" |
|
448 |
|
449 lemma decode_encode_cfun [simp]: "decode_cfun\<cdot>(encode_cfun\<cdot>x) = x" |
|
450 unfolding encode_cfun_def decode_cfun_def |
|
451 by (simp add: eta_cfun) |
|
452 |
|
453 lemma encode_decode_cfun [simp]: "encode_cfun\<cdot>(decode_cfun\<cdot>y) = y" |
|
454 unfolding encode_cfun_def decode_cfun_def |
|
455 apply (simp add: sfun_eq_iff strictify_cancel) |
|
456 apply (rule cfun_eqI, case_tac x, simp_all) |
|
457 done |
|
458 |
|
459 instantiation cfun :: (predomain, "domain") liftdomain |
|
460 begin |
|
461 |
|
462 definition |
|
463 "emb = (udom_emb sfun_approx oo sfun_map\<cdot>prj\<cdot>emb) oo encode_cfun" |
|
464 |
|
465 definition |
|
466 "prj = decode_cfun oo (sfun_map\<cdot>emb\<cdot>prj oo udom_prj sfun_approx)" |
|
467 |
|
468 definition |
|
469 "defl (t::('a \<rightarrow> 'b) itself) = sfun_defl\<cdot>DEFL('a u)\<cdot>DEFL('b)" |
|
470 |
|
471 definition |
|
472 "(liftemb :: ('a \<rightarrow> 'b) u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb" |
|
473 |
|
474 definition |
|
475 "(liftprj :: udom \<rightarrow> ('a \<rightarrow> 'b) u) = u_map\<cdot>prj oo udom_prj u_approx" |
|
476 |
|
477 definition |
|
478 "liftdefl (t::('a \<rightarrow> 'b) itself) = u_defl\<cdot>DEFL('a \<rightarrow> 'b)" |
|
479 |
|
480 instance |
|
481 using liftemb_cfun_def liftprj_cfun_def liftdefl_cfun_def |
|
482 proof (rule liftdomain_class_intro) |
|
483 have "ep_pair encode_cfun decode_cfun" |
|
484 by (rule ep_pair.intro, simp_all) |
|
485 thus "ep_pair emb (prj :: udom \<rightarrow> 'a \<rightarrow> 'b)" |
|
486 unfolding emb_cfun_def prj_cfun_def |
|
487 apply (rule ep_pair_comp) |
|
488 apply (rule ep_pair_comp) |
|
489 apply (intro ep_pair_sfun_map ep_pair_emb_prj) |
|
490 apply (rule ep_pair_udom [OF sfun_approx]) |
|
491 done |
|
492 show "cast\<cdot>DEFL('a \<rightarrow> 'b) = emb oo (prj :: udom \<rightarrow> 'a \<rightarrow> 'b)" |
|
493 unfolding emb_cfun_def prj_cfun_def defl_cfun_def cast_sfun_defl |
|
494 by (simp add: cast_DEFL oo_def cfun_eq_iff sfun_map_map) |
|
495 qed |
|
496 |
|
497 end |
|
498 |
|
499 lemma DEFL_cfun: |
|
500 "DEFL('a::predomain \<rightarrow> 'b::domain) = sfun_defl\<cdot>DEFL('a u)\<cdot>DEFL('b)" |
|
501 by (rule defl_cfun_def) |
|
502 |
|
503 subsubsection {* Cartesian product *} |
|
504 |
|
505 text {* |
|
506 Types @{typ "('a * 'b) u"} and @{typ "'a u \<otimes> 'b u"} are isomorphic. |
|
507 *} |
|
508 |
|
509 definition |
|
510 "encode_prod_u = (\<Lambda>(up\<cdot>(x, y)). (:up\<cdot>x, up\<cdot>y:))" |
|
511 |
|
512 definition |
|
513 "decode_prod_u = (\<Lambda>(:up\<cdot>x, up\<cdot>y:). up\<cdot>(x, y))" |
|
514 |
|
515 lemma decode_encode_prod_u [simp]: "decode_prod_u\<cdot>(encode_prod_u\<cdot>x) = x" |
|
516 unfolding encode_prod_u_def decode_prod_u_def |
|
517 by (case_tac x, simp, rename_tac y, case_tac y, simp) |
|
518 |
|
519 lemma encode_decode_prod_u [simp]: "encode_prod_u\<cdot>(decode_prod_u\<cdot>y) = y" |
|
520 unfolding encode_prod_u_def decode_prod_u_def |
|
521 apply (case_tac y, simp, rename_tac a b) |
|
522 apply (case_tac a, simp, case_tac b, simp, simp) |
|
523 done |
|
524 |
|
525 instantiation prod :: (predomain, predomain) predomain |
|
526 begin |
|
527 |
|
528 definition |
|
529 "liftemb = |
|
530 (udom_emb sprod_approx oo sprod_map\<cdot>emb\<cdot>emb) oo encode_prod_u" |
|
531 |
|
532 definition |
|
533 "liftprj = |
|
534 decode_prod_u oo (sprod_map\<cdot>prj\<cdot>prj oo udom_prj sprod_approx)" |
|
535 |
|
536 definition |
|
537 "liftdefl (t::('a \<times> 'b) itself) = sprod_defl\<cdot>DEFL('a u)\<cdot>DEFL('b u)" |
|
538 |
|
539 instance proof |
|
540 have "ep_pair encode_prod_u decode_prod_u" |
|
541 by (rule ep_pair.intro, simp_all) |
|
542 thus "ep_pair liftemb (liftprj :: udom \<rightarrow> ('a \<times> 'b) u)" |
|
543 unfolding liftemb_prod_def liftprj_prod_def |
|
544 apply (rule ep_pair_comp) |
|
545 apply (rule ep_pair_comp) |
|
546 apply (intro ep_pair_sprod_map ep_pair_emb_prj) |
|
547 apply (rule ep_pair_udom [OF sprod_approx]) |
|
548 done |
|
549 show "cast\<cdot>LIFTDEFL('a \<times> 'b) = liftemb oo (liftprj :: udom \<rightarrow> ('a \<times> 'b) u)" |
|
550 unfolding liftemb_prod_def liftprj_prod_def liftdefl_prod_def |
|
551 by (simp add: cast_sprod_defl cast_DEFL cfcomp1 sprod_map_map) |
|
552 qed |
|
553 |
|
554 end |
|
555 |
|
556 instantiation prod :: ("domain", "domain") "domain" |
|
557 begin |
|
558 |
|
559 definition |
|
560 "emb = udom_emb prod_approx oo cprod_map\<cdot>emb\<cdot>emb" |
|
561 |
|
562 definition |
|
563 "prj = cprod_map\<cdot>prj\<cdot>prj oo udom_prj prod_approx" |
|
564 |
|
565 definition |
|
566 "defl (t::('a \<times> 'b) itself) = prod_defl\<cdot>DEFL('a)\<cdot>DEFL('b)" |
|
567 |
|
568 instance proof |
|
569 show "ep_pair emb (prj :: udom \<rightarrow> 'a \<times> 'b)" |
|
570 unfolding emb_prod_def prj_prod_def |
|
571 using ep_pair_udom [OF prod_approx] |
|
572 by (intro ep_pair_comp ep_pair_cprod_map ep_pair_emb_prj) |
|
573 next |
|
574 show "cast\<cdot>DEFL('a \<times> 'b) = emb oo (prj :: udom \<rightarrow> 'a \<times> 'b)" |
|
575 unfolding emb_prod_def prj_prod_def defl_prod_def cast_prod_defl |
|
576 by (simp add: cast_DEFL oo_def cfun_eq_iff cprod_map_map) |
|
577 qed |
|
578 |
|
579 end |
|
580 |
|
581 lemma DEFL_prod: |
|
582 "DEFL('a::domain \<times> 'b::domain) = prod_defl\<cdot>DEFL('a)\<cdot>DEFL('b)" |
|
583 by (rule defl_prod_def) |
|
584 |
|
585 lemma LIFTDEFL_prod: |
|
586 "LIFTDEFL('a::predomain \<times> 'b::predomain) = sprod_defl\<cdot>DEFL('a u)\<cdot>DEFL('b u)" |
|
587 by (rule liftdefl_prod_def) |
|
588 |
|
589 subsubsection {* Strict product *} |
|
590 |
|
591 instantiation sprod :: ("domain", "domain") liftdomain |
|
592 begin |
|
593 |
|
594 definition |
|
595 "emb = udom_emb sprod_approx oo sprod_map\<cdot>emb\<cdot>emb" |
|
596 |
|
597 definition |
|
598 "prj = sprod_map\<cdot>prj\<cdot>prj oo udom_prj sprod_approx" |
|
599 |
|
600 definition |
|
601 "defl (t::('a \<otimes> 'b) itself) = sprod_defl\<cdot>DEFL('a)\<cdot>DEFL('b)" |
|
602 |
|
603 definition |
|
604 "(liftemb :: ('a \<otimes> 'b) u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb" |
|
605 |
|
606 definition |
|
607 "(liftprj :: udom \<rightarrow> ('a \<otimes> 'b) u) = u_map\<cdot>prj oo udom_prj u_approx" |
|
608 |
|
609 definition |
|
610 "liftdefl (t::('a \<otimes> 'b) itself) = u_defl\<cdot>DEFL('a \<otimes> 'b)" |
|
611 |
|
612 instance |
|
613 using liftemb_sprod_def liftprj_sprod_def liftdefl_sprod_def |
|
614 proof (rule liftdomain_class_intro) |
|
615 show "ep_pair emb (prj :: udom \<rightarrow> 'a \<otimes> 'b)" |
|
616 unfolding emb_sprod_def prj_sprod_def |
|
617 using ep_pair_udom [OF sprod_approx] |
|
618 by (intro ep_pair_comp ep_pair_sprod_map ep_pair_emb_prj) |
|
619 next |
|
620 show "cast\<cdot>DEFL('a \<otimes> 'b) = emb oo (prj :: udom \<rightarrow> 'a \<otimes> 'b)" |
|
621 unfolding emb_sprod_def prj_sprod_def defl_sprod_def cast_sprod_defl |
|
622 by (simp add: cast_DEFL oo_def cfun_eq_iff sprod_map_map) |
|
623 qed |
|
624 |
|
625 end |
|
626 |
|
627 lemma DEFL_sprod: |
|
628 "DEFL('a::domain \<otimes> 'b::domain) = sprod_defl\<cdot>DEFL('a)\<cdot>DEFL('b)" |
|
629 by (rule defl_sprod_def) |
|
630 |
|
631 subsubsection {* Discrete cpo *} |
|
632 |
|
633 definition discr_approx :: "nat \<Rightarrow> 'a::countable discr u \<rightarrow> 'a discr u" |
|
634 where "discr_approx = (\<lambda>i. \<Lambda>(up\<cdot>x). if to_nat (undiscr x) < i then up\<cdot>x else \<bottom>)" |
|
635 |
|
636 lemma chain_discr_approx [simp]: "chain discr_approx" |
|
637 unfolding discr_approx_def |
|
638 by (rule chainI, simp add: monofun_cfun monofun_LAM) |
|
639 |
|
640 lemma lub_discr_approx [simp]: "(\<Squnion>i. discr_approx i) = ID" |
|
641 apply (rule cfun_eqI) |
|
642 apply (simp add: contlub_cfun_fun) |
|
643 apply (simp add: discr_approx_def) |
|
644 apply (case_tac x, simp) |
|
645 apply (rule lub_eqI) |
|
646 apply (rule is_lubI) |
|
647 apply (rule ub_rangeI, simp) |
|
648 apply (drule ub_rangeD) |
|
649 apply (erule rev_below_trans) |
|
650 apply simp |
|
651 apply (rule lessI) |
|
652 done |
|
653 |
|
654 lemma inj_on_undiscr [simp]: "inj_on undiscr A" |
|
655 using Discr_undiscr by (rule inj_on_inverseI) |
|
656 |
|
657 lemma finite_deflation_discr_approx: "finite_deflation (discr_approx i)" |
|
658 proof |
|
659 fix x :: "'a discr u" |
|
660 show "discr_approx i\<cdot>x \<sqsubseteq> x" |
|
661 unfolding discr_approx_def |
|
662 by (cases x, simp, simp) |
|
663 show "discr_approx i\<cdot>(discr_approx i\<cdot>x) = discr_approx i\<cdot>x" |
|
664 unfolding discr_approx_def |
|
665 by (cases x, simp, simp) |
|
666 show "finite {x::'a discr u. discr_approx i\<cdot>x = x}" |
|
667 proof (rule finite_subset) |
|
668 let ?S = "insert (\<bottom>::'a discr u) ((\<lambda>x. up\<cdot>x) ` undiscr -` to_nat -` {..<i})" |
|
669 show "{x::'a discr u. discr_approx i\<cdot>x = x} \<subseteq> ?S" |
|
670 unfolding discr_approx_def |
|
671 by (rule subsetI, case_tac x, simp, simp split: split_if_asm) |
|
672 show "finite ?S" |
|
673 by (simp add: finite_vimageI) |
|
674 qed |
|
675 qed |
|
676 |
|
677 lemma discr_approx: "approx_chain discr_approx" |
|
678 using chain_discr_approx lub_discr_approx finite_deflation_discr_approx |
|
679 by (rule approx_chain.intro) |
|
680 |
|
681 instantiation discr :: (countable) predomain |
|
682 begin |
|
683 |
|
684 definition |
|
685 "liftemb = udom_emb discr_approx" |
|
686 |
|
687 definition |
|
688 "liftprj = udom_prj discr_approx" |
|
689 |
|
690 definition |
|
691 "liftdefl (t::'a discr itself) = |
|
692 (\<Squnion>i. defl_principal (Abs_fin_defl (liftemb oo discr_approx i oo liftprj)))" |
|
693 |
|
694 instance proof |
|
695 show "ep_pair liftemb (liftprj :: udom \<rightarrow> 'a discr u)" |
|
696 unfolding liftemb_discr_def liftprj_discr_def |
|
697 by (rule ep_pair_udom [OF discr_approx]) |
|
698 show "cast\<cdot>LIFTDEFL('a discr) = liftemb oo (liftprj :: udom \<rightarrow> 'a discr u)" |
|
699 unfolding liftemb_discr_def liftprj_discr_def liftdefl_discr_def |
|
700 apply (subst contlub_cfun_arg) |
|
701 apply (rule chainI) |
|
702 apply (rule defl.principal_mono) |
|
703 apply (simp add: below_fin_defl_def) |
|
704 apply (simp add: Abs_fin_defl_inverse |
|
705 ep_pair.finite_deflation_e_d_p [OF ep_pair_udom [OF discr_approx]] |
|
706 approx_chain.finite_deflation_approx [OF discr_approx]) |
|
707 apply (intro monofun_cfun below_refl) |
|
708 apply (rule chainE) |
|
709 apply (rule chain_discr_approx) |
|
710 apply (subst cast_defl_principal) |
|
711 apply (simp add: Abs_fin_defl_inverse |
|
712 ep_pair.finite_deflation_e_d_p [OF ep_pair_udom [OF discr_approx]] |
|
713 approx_chain.finite_deflation_approx [OF discr_approx]) |
|
714 apply (simp add: lub_distribs) |
|
715 done |
|
716 qed |
|
717 |
|
718 end |
|
719 |
|
720 subsubsection {* Strict sum *} |
|
721 |
|
722 instantiation ssum :: ("domain", "domain") liftdomain |
|
723 begin |
|
724 |
|
725 definition |
|
726 "emb = udom_emb ssum_approx oo ssum_map\<cdot>emb\<cdot>emb" |
|
727 |
|
728 definition |
|
729 "prj = ssum_map\<cdot>prj\<cdot>prj oo udom_prj ssum_approx" |
|
730 |
|
731 definition |
|
732 "defl (t::('a \<oplus> 'b) itself) = ssum_defl\<cdot>DEFL('a)\<cdot>DEFL('b)" |
|
733 |
|
734 definition |
|
735 "(liftemb :: ('a \<oplus> 'b) u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb" |
|
736 |
|
737 definition |
|
738 "(liftprj :: udom \<rightarrow> ('a \<oplus> 'b) u) = u_map\<cdot>prj oo udom_prj u_approx" |
|
739 |
|
740 definition |
|
741 "liftdefl (t::('a \<oplus> 'b) itself) = u_defl\<cdot>DEFL('a \<oplus> 'b)" |
|
742 |
|
743 instance |
|
744 using liftemb_ssum_def liftprj_ssum_def liftdefl_ssum_def |
|
745 proof (rule liftdomain_class_intro) |
|
746 show "ep_pair emb (prj :: udom \<rightarrow> 'a \<oplus> 'b)" |
|
747 unfolding emb_ssum_def prj_ssum_def |
|
748 using ep_pair_udom [OF ssum_approx] |
|
749 by (intro ep_pair_comp ep_pair_ssum_map ep_pair_emb_prj) |
|
750 show "cast\<cdot>DEFL('a \<oplus> 'b) = emb oo (prj :: udom \<rightarrow> 'a \<oplus> 'b)" |
|
751 unfolding emb_ssum_def prj_ssum_def defl_ssum_def cast_ssum_defl |
|
752 by (simp add: cast_DEFL oo_def cfun_eq_iff ssum_map_map) |
|
753 qed |
|
754 |
|
755 end |
|
756 |
|
757 lemma DEFL_ssum: |
|
758 "DEFL('a::domain \<oplus> 'b::domain) = ssum_defl\<cdot>DEFL('a)\<cdot>DEFL('b)" |
|
759 by (rule defl_ssum_def) |
|
760 |
|
761 subsubsection {* Lifted HOL type *} |
|
762 |
|
763 instantiation lift :: (countable) liftdomain |
|
764 begin |
|
765 |
|
766 definition |
|
767 "emb = emb oo (\<Lambda> x. Rep_lift x)" |
|
768 |
|
769 definition |
|
770 "prj = (\<Lambda> y. Abs_lift y) oo prj" |
|
771 |
|
772 definition |
|
773 "defl (t::'a lift itself) = DEFL('a discr u)" |
|
774 |
|
775 definition |
|
776 "(liftemb :: 'a lift u \<rightarrow> udom) = udom_emb u_approx oo u_map\<cdot>emb" |
|
777 |
|
778 definition |
|
779 "(liftprj :: udom \<rightarrow> 'a lift u) = u_map\<cdot>prj oo udom_prj u_approx" |
|
780 |
|
781 definition |
|
782 "liftdefl (t::'a lift itself) = u_defl\<cdot>DEFL('a lift)" |
|
783 |
|
784 instance |
|
785 using liftemb_lift_def liftprj_lift_def liftdefl_lift_def |
|
786 proof (rule liftdomain_class_intro) |
|
787 note [simp] = cont_Rep_lift cont_Abs_lift Rep_lift_inverse Abs_lift_inverse |
|
788 have "ep_pair (\<Lambda>(x::'a lift). Rep_lift x) (\<Lambda> y. Abs_lift y)" |
|
789 by (simp add: ep_pair_def) |
|
790 thus "ep_pair emb (prj :: udom \<rightarrow> 'a lift)" |
|
791 unfolding emb_lift_def prj_lift_def |
|
792 using ep_pair_emb_prj by (rule ep_pair_comp) |
|
793 show "cast\<cdot>DEFL('a lift) = emb oo (prj :: udom \<rightarrow> 'a lift)" |
|
794 unfolding emb_lift_def prj_lift_def defl_lift_def cast_DEFL |
|
795 by (simp add: cfcomp1) |
|
796 qed |
|
797 |
|
798 end |
|
799 |
|
800 end |
|