29 |
29 |
30 lift :: "[nat, ('b * ((nat=>'b) * 'c)) program] => ((nat=>'b) * 'c) program" |
30 lift :: "[nat, ('b * ((nat=>'b) * 'c)) program] => ((nat=>'b) * 'c) program" |
31 "lift i == rename (lift_map i)" |
31 "lift i == rename (lift_map i)" |
32 |
32 |
33 (*simplifies the expression of specifications*) |
33 (*simplifies the expression of specifications*) |
34 constdefs |
34 sub :: "['a, 'a=>'b] => 'b" |
35 sub :: ['a, 'a=>'b] => 'b |
35 "sub == %i f. f i" |
36 "sub == %i f. f i" |
36 |
37 |
37 |
|
38 declare insert_map_def [simp] delete_map_def [simp] |
|
39 |
|
40 lemma insert_map_inverse: "delete_map i (insert_map i x f) = f" |
|
41 apply (rule ext) |
|
42 apply (simp (no_asm)) |
|
43 done |
|
44 |
|
45 lemma insert_map_delete_map_eq: "(insert_map i x (delete_map i g)) = g(i:=x)" |
|
46 apply (rule ext) |
|
47 apply (auto split add: nat_diff_split) |
|
48 done |
|
49 |
|
50 (*** Injectiveness proof ***) |
|
51 |
|
52 lemma insert_map_inject1: "(insert_map i x f) = (insert_map i y g) ==> x=y" |
|
53 apply (drule_tac x = i in fun_cong) |
|
54 apply (simp (no_asm_use)) |
|
55 done |
|
56 |
|
57 lemma insert_map_inject2: "(insert_map i x f) = (insert_map i y g) ==> f=g" |
|
58 apply (drule_tac f = "delete_map i" in arg_cong) |
|
59 apply (simp (no_asm_use) add: insert_map_inverse) |
|
60 done |
|
61 |
|
62 lemma insert_map_inject': |
|
63 "(insert_map i x f) = (insert_map i y g) ==> x=y & f=g" |
|
64 by (blast dest: insert_map_inject1 insert_map_inject2) |
|
65 |
|
66 lemmas insert_map_inject = insert_map_inject' [THEN conjE, elim!] |
|
67 |
|
68 (*The general case: we don't assume i=i'*) |
|
69 lemma lift_map_eq_iff [iff]: |
|
70 "(lift_map i (s,(f,uu)) = lift_map i' (s',(f',uu'))) |
|
71 = (uu = uu' & insert_map i s f = insert_map i' s' f')" |
|
72 apply (unfold lift_map_def, auto) |
|
73 done |
|
74 |
|
75 (*The !!s allows the automatic splitting of the bound variable*) |
|
76 lemma drop_map_lift_map_eq [simp]: "!!s. drop_map i (lift_map i s) = s" |
|
77 apply (unfold lift_map_def drop_map_def) |
|
78 apply (force intro: insert_map_inverse) |
|
79 done |
|
80 |
|
81 lemma inj_lift_map: "inj (lift_map i)" |
|
82 apply (unfold lift_map_def) |
|
83 apply (rule inj_onI, auto) |
|
84 done |
|
85 |
|
86 (*** Surjectiveness proof ***) |
|
87 |
|
88 lemma lift_map_drop_map_eq [simp]: "!!s. lift_map i (drop_map i s) = s" |
|
89 apply (unfold lift_map_def drop_map_def) |
|
90 apply (force simp add: insert_map_delete_map_eq) |
|
91 done |
|
92 |
|
93 lemma drop_map_inject [dest!]: "(drop_map i s) = (drop_map i s') ==> s=s'" |
|
94 apply (drule_tac f = "lift_map i" in arg_cong) |
|
95 apply (simp (no_asm_use)) |
|
96 done |
|
97 |
|
98 lemma surj_lift_map: "surj (lift_map i)" |
|
99 apply (rule surjI) |
|
100 apply (rule lift_map_drop_map_eq) |
|
101 done |
|
102 |
|
103 lemma bij_lift_map [iff]: "bij (lift_map i)" |
|
104 apply (simp (no_asm) add: bij_def inj_lift_map surj_lift_map) |
|
105 done |
|
106 |
|
107 lemma inv_lift_map_eq [simp]: "inv (lift_map i) = drop_map i" |
|
108 by (rule inv_equality, auto) |
|
109 |
|
110 lemma inv_drop_map_eq [simp]: "inv (drop_map i) = lift_map i" |
|
111 by (rule inv_equality, auto) |
|
112 |
|
113 lemma bij_drop_map [iff]: "bij (drop_map i)" |
|
114 by (simp del: inv_lift_map_eq add: inv_lift_map_eq [symmetric] bij_imp_bij_inv) |
|
115 |
|
116 (*sub's main property!*) |
|
117 lemma sub_apply [simp]: "sub i f = f i" |
|
118 apply (simp (no_asm) add: sub_def) |
|
119 done |
|
120 |
|
121 (*** lift_set ***) |
|
122 |
|
123 lemma lift_set_empty [simp]: "lift_set i {} = {}" |
|
124 by (unfold lift_set_def, auto) |
|
125 |
|
126 lemma lift_set_iff: "(lift_map i x : lift_set i A) = (x : A)" |
|
127 apply (unfold lift_set_def) |
|
128 apply (rule inj_lift_map [THEN inj_image_mem_iff]) |
|
129 done |
|
130 |
|
131 (*Do we really need both this one and its predecessor?*) |
|
132 lemma lift_set_iff2 [iff]: |
|
133 "((f,uu) : lift_set i A) = ((f i, (delete_map i f, uu)) : A)" |
|
134 by (simp (no_asm_simp) add: lift_set_def mem_rename_set_iff drop_map_def) |
|
135 |
|
136 |
|
137 lemma lift_set_mono: "A<=B ==> lift_set i A <= lift_set i B" |
|
138 apply (unfold lift_set_def) |
|
139 apply (erule image_mono) |
|
140 done |
|
141 |
|
142 lemma lift_set_Un_distrib: "lift_set i (A Un B) = lift_set i A Un lift_set i B" |
|
143 apply (unfold lift_set_def) |
|
144 apply (simp (no_asm_simp) add: image_Un) |
|
145 done |
|
146 |
|
147 lemma lift_set_Diff_distrib: "lift_set i (A-B) = lift_set i A - lift_set i B" |
|
148 apply (unfold lift_set_def) |
|
149 apply (rule inj_lift_map [THEN image_set_diff]) |
|
150 done |
|
151 |
|
152 |
|
153 (*** the lattice operations ***) |
|
154 |
|
155 lemma bij_lift [iff]: "bij (lift i)" |
|
156 apply (simp (no_asm) add: lift_def) |
|
157 done |
|
158 |
|
159 lemma lift_SKIP [simp]: "lift i SKIP = SKIP" |
|
160 apply (unfold lift_def) |
|
161 apply (simp (no_asm_simp)) |
|
162 done |
|
163 |
|
164 lemma lift_Join [simp]: "lift i (F Join G) = lift i F Join lift i G" |
|
165 apply (unfold lift_def) |
|
166 apply (simp (no_asm_simp)) |
|
167 done |
|
168 |
|
169 lemma lift_JN [simp]: "lift j (JOIN I F) = (JN i:I. lift j (F i))" |
|
170 apply (unfold lift_def) |
|
171 apply (simp (no_asm_simp)) |
|
172 done |
|
173 |
|
174 (*** Safety: co, stable, invariant ***) |
|
175 |
|
176 lemma lift_constrains: |
|
177 "(lift i F : (lift_set i A) co (lift_set i B)) = (F : A co B)" |
|
178 apply (unfold lift_def lift_set_def) |
|
179 apply (simp (no_asm_simp) add: rename_constrains) |
|
180 done |
|
181 |
|
182 lemma lift_stable: |
|
183 "(lift i F : stable (lift_set i A)) = (F : stable A)" |
|
184 apply (unfold lift_def lift_set_def) |
|
185 apply (simp (no_asm_simp) add: rename_stable) |
|
186 done |
|
187 |
|
188 lemma lift_invariant: |
|
189 "(lift i F : invariant (lift_set i A)) = (F : invariant A)" |
|
190 apply (unfold lift_def lift_set_def) |
|
191 apply (simp (no_asm_simp) add: rename_invariant) |
|
192 done |
|
193 |
|
194 lemma lift_Constrains: |
|
195 "(lift i F : (lift_set i A) Co (lift_set i B)) = (F : A Co B)" |
|
196 apply (unfold lift_def lift_set_def) |
|
197 apply (simp (no_asm_simp) add: rename_Constrains) |
|
198 done |
|
199 |
|
200 lemma lift_Stable: |
|
201 "(lift i F : Stable (lift_set i A)) = (F : Stable A)" |
|
202 apply (unfold lift_def lift_set_def) |
|
203 apply (simp (no_asm_simp) add: rename_Stable) |
|
204 done |
|
205 |
|
206 lemma lift_Always: |
|
207 "(lift i F : Always (lift_set i A)) = (F : Always A)" |
|
208 apply (unfold lift_def lift_set_def) |
|
209 apply (simp (no_asm_simp) add: rename_Always) |
|
210 done |
|
211 |
|
212 (*** Progress: transient, ensures ***) |
|
213 |
|
214 lemma lift_transient: |
|
215 "(lift i F : transient (lift_set i A)) = (F : transient A)" |
|
216 |
|
217 apply (unfold lift_def lift_set_def) |
|
218 apply (simp (no_asm_simp) add: rename_transient) |
|
219 done |
|
220 |
|
221 lemma lift_ensures: |
|
222 "(lift i F : (lift_set i A) ensures (lift_set i B)) = |
|
223 (F : A ensures B)" |
|
224 apply (unfold lift_def lift_set_def) |
|
225 apply (simp (no_asm_simp) add: rename_ensures) |
|
226 done |
|
227 |
|
228 lemma lift_leadsTo: |
|
229 "(lift i F : (lift_set i A) leadsTo (lift_set i B)) = |
|
230 (F : A leadsTo B)" |
|
231 apply (unfold lift_def lift_set_def) |
|
232 apply (simp (no_asm_simp) add: rename_leadsTo) |
|
233 done |
|
234 |
|
235 lemma lift_LeadsTo: |
|
236 "(lift i F : (lift_set i A) LeadsTo (lift_set i B)) = |
|
237 (F : A LeadsTo B)" |
|
238 apply (unfold lift_def lift_set_def) |
|
239 apply (simp (no_asm_simp) add: rename_LeadsTo) |
|
240 done |
|
241 |
|
242 |
|
243 (** guarantees **) |
|
244 |
|
245 lemma lift_lift_guarantees_eq: |
|
246 "(lift i F : (lift i ` X) guarantees (lift i ` Y)) = |
|
247 (F : X guarantees Y)" |
|
248 |
|
249 apply (unfold lift_def) |
|
250 apply (subst bij_lift_map [THEN rename_rename_guarantees_eq, symmetric]) |
|
251 apply (simp (no_asm_simp) add: o_def) |
|
252 done |
|
253 |
|
254 lemma lift_guarantees_eq_lift_inv: "(lift i F : X guarantees Y) = |
|
255 (F : (rename (drop_map i) ` X) guarantees (rename (drop_map i) ` Y))" |
|
256 by (simp add: bij_lift_map [THEN rename_guarantees_eq_rename_inv] lift_def) |
|
257 |
|
258 |
|
259 (*** We devote an ENORMOUS effort to proving lift_transient_eq_disj, |
|
260 which is used only in TimerArray and perhaps isn't even essential |
|
261 there! |
|
262 ***) |
|
263 |
|
264 (*To preserve snd means that the second component is there just to allow |
|
265 guarantees properties to be stated. Converse fails, for lift i F can |
|
266 change function components other than i*) |
|
267 lemma lift_preserves_snd_I: "F : preserves snd ==> lift i F : preserves snd" |
|
268 apply (drule_tac w1=snd in subset_preserves_o [THEN subsetD]) |
|
269 apply (simp (no_asm_simp) add: lift_def rename_preserves) |
|
270 apply (simp (no_asm_use) add: lift_map_def o_def split_def) |
|
271 done |
|
272 |
|
273 lemma delete_map_eqE': |
|
274 "(delete_map i g) = (delete_map i g') ==> EX x. g = g'(i:=x)" |
|
275 apply (drule_tac f = "insert_map i (g i) " in arg_cong) |
|
276 apply (simp (no_asm_use) add: insert_map_delete_map_eq) |
|
277 apply (erule exI) |
|
278 done |
|
279 |
|
280 lemmas delete_map_eqE = delete_map_eqE' [THEN exE, elim!] |
|
281 |
|
282 lemma delete_map_neq_apply: |
|
283 "[| delete_map j g = delete_map j g'; i~=j |] ==> g i = g' i" |
|
284 by force |
|
285 |
|
286 (*A set of the form (A <*> UNIV) ignores the second (dummy) state component*) |
|
287 |
|
288 lemma vimage_o_fst_eq [simp]: "(f o fst) -` A = (f-`A) <*> UNIV" |
|
289 by auto |
|
290 |
|
291 lemma vimage_sub_eq_lift_set [simp]: |
|
292 "(sub i -`A) <*> UNIV = lift_set i (A <*> UNIV)" |
|
293 by auto |
|
294 |
|
295 lemma mem_lift_act_iff [iff]: |
|
296 "((s,s') : extend_act (%(x,u::unit). lift_map i x) act) = |
|
297 ((drop_map i s, drop_map i s') : act)" |
|
298 apply (unfold extend_act_def, auto) |
|
299 apply (rule bexI, auto) |
|
300 done |
|
301 |
|
302 lemma preserves_snd_lift_stable: |
|
303 "[| F : preserves snd; i~=j |] |
|
304 ==> lift j F : stable (lift_set i (A <*> UNIV))" |
|
305 apply (auto simp add: lift_def lift_set_def stable_def constrains_def rename_def extend_def mem_rename_set_iff) |
|
306 apply (auto dest!: preserves_imp_eq simp add: lift_map_def drop_map_def) |
|
307 apply (drule_tac x = i in fun_cong, auto) |
|
308 done |
|
309 |
|
310 (*If i~=j then lift j F does nothing to lift_set i, and the |
|
311 premise ensures A<=B.*) |
|
312 lemma constrains_imp_lift_constrains: |
|
313 "[| F i : (A <*> UNIV) co (B <*> UNIV); |
|
314 F j : preserves snd |] |
|
315 ==> lift j (F j) : (lift_set i (A <*> UNIV)) co (lift_set i (B <*> UNIV))" |
|
316 apply (case_tac "i=j") |
|
317 apply (simp add: lift_def lift_set_def rename_constrains) |
|
318 apply (erule preserves_snd_lift_stable[THEN stableD, THEN constrains_weaken_R], assumption) |
|
319 apply (erule constrains_imp_subset [THEN lift_set_mono]) |
|
320 done |
|
321 |
|
322 (** Lemmas for the transient theorem **) |
|
323 |
|
324 lemma insert_map_upd_same: "(insert_map i t f)(i := s) = insert_map i s f" |
|
325 by (rule ext, auto) |
|
326 |
|
327 lemma insert_map_upd: |
|
328 "(insert_map j t f)(i := s) = |
|
329 (if i=j then insert_map i s f |
|
330 else if i<j then insert_map j t (f(i:=s)) |
|
331 else insert_map j t (f(i - Suc 0 := s)))" |
|
332 apply (rule ext) |
|
333 apply (simp split add: nat_diff_split) |
|
334 done |
|
335 |
|
336 lemma insert_map_eq_diff: |
|
337 "[| insert_map i s f = insert_map j t g; i~=j |] |
|
338 ==> EX g'. insert_map i s' f = insert_map j t g'" |
|
339 apply (subst insert_map_upd_same [symmetric]) |
|
340 apply (erule ssubst) |
|
341 apply (simp only: insert_map_upd if_False split: split_if, blast) |
|
342 done |
|
343 |
|
344 lemma lift_map_eq_diff: |
|
345 "[| lift_map i (s,(f,uu)) = lift_map j (t,(g,vv)); i~=j |] |
|
346 ==> EX g'. lift_map i (s',(f,uu)) = lift_map j (t,(g',vv))" |
|
347 apply (unfold lift_map_def, auto) |
|
348 apply (blast dest: insert_map_eq_diff) |
|
349 done |
|
350 |
|
351 |
|
352 ML |
|
353 {* |
|
354 bind_thm ("export_mem_extend_act_iff", export mem_extend_act_iff) |
|
355 *} |
|
356 |
|
357 |
|
358 lemma lift_transient_eq_disj: |
|
359 "F : preserves snd |
|
360 ==> (lift i F : transient (lift_set j (A <*> UNIV))) = |
|
361 (i=j & F : transient (A <*> UNIV) | A={})" |
|
362 apply (case_tac "i=j") |
|
363 apply (auto simp add: lift_transient) |
|
364 apply (auto simp add: lift_set_def lift_def transient_def rename_def extend_def Domain_extend_act) |
|
365 apply (drule subsetD, blast) |
|
366 apply auto |
|
367 apply (rename_tac s f uu s' f' uu') |
|
368 apply (subgoal_tac "f'=f & uu'=uu") |
|
369 prefer 2 apply (force dest!: preserves_imp_eq, auto) |
|
370 apply (drule sym) |
|
371 apply (drule subsetD) |
|
372 apply (rule ImageI) |
|
373 apply (erule bij_lift_map [THEN good_map_bij, |
|
374 THEN export_mem_extend_act_iff [THEN iffD2]], force) |
|
375 apply (erule lift_map_eq_diff [THEN exE], auto) |
|
376 done |
|
377 |
|
378 (*USELESS??*) |
|
379 lemma lift_map_image_Times: "lift_map i ` (A <*> UNIV) = |
|
380 (UN s:A. UN f. {insert_map i s f}) <*> UNIV" |
|
381 apply (auto intro!: bexI image_eqI simp add: lift_map_def) |
|
382 apply (rule split_conv [symmetric]) |
|
383 done |
|
384 |
|
385 lemma lift_preserves_eq: |
|
386 "(lift i F : preserves v) = (F : preserves (v o lift_map i))" |
|
387 by (simp add: lift_def rename_preserves) |
|
388 |
|
389 (*A useful rewrite. If o, sub have been rewritten out already then can also |
|
390 use it as rewrite_rule [sub_def, o_def] lift_preserves_sub*) |
|
391 lemma lift_preserves_sub: |
|
392 "F : preserves snd |
|
393 ==> lift i F : preserves (v o sub j o fst) = |
|
394 (if i=j then F : preserves (v o fst) else True)" |
|
395 apply (drule subset_preserves_o [THEN subsetD]) |
|
396 apply (simp add: lift_preserves_eq o_def drop_map_lift_map_eq) |
|
397 apply (simp cong del: if_weak_cong add: lift_map_def eq_commute split_def o_def, auto) |
|
398 done |
|
399 |
|
400 |
|
401 (*** Lemmas to handle function composition (o) more consistently ***) |
|
402 |
|
403 (*Lets us prove one version of a theorem and store others*) |
|
404 lemma o_equiv_assoc: "f o g = h ==> f' o f o g = f' o h" |
|
405 by (simp add: expand_fun_eq o_def) |
|
406 |
|
407 lemma o_equiv_apply: "f o g = h ==> ALL x. f(g x) = h x" |
|
408 by (simp add: expand_fun_eq o_def) |
|
409 |
|
410 lemma fst_o_lift_map: "sub i o fst o lift_map i = fst" |
|
411 apply (rule ext) |
|
412 apply (auto simp add: o_def lift_map_def sub_def) |
|
413 done |
|
414 |
|
415 lemma snd_o_lift_map: "snd o lift_map i = snd o snd" |
|
416 apply (rule ext) |
|
417 apply (auto simp add: o_def lift_map_def) |
|
418 done |
|
419 |
|
420 |
|
421 (*** More lemmas about extend and project |
|
422 They could be moved to {Extend,Project}.ML, but DON'T need the locale ***) |
|
423 |
|
424 lemma extend_act_extend_act: "extend_act h' (extend_act h act) = |
|
425 extend_act (%(x,(y,y')). h'(h(x,y),y')) act" |
|
426 apply (auto elim!: rev_bexI simp add: extend_act_def, blast) |
|
427 done |
|
428 |
|
429 lemma project_act_project_act: "project_act h (project_act h' act) = |
|
430 project_act (%(x,(y,y')). h'(h(x,y),y')) act" |
|
431 by (auto elim!: rev_bexI simp add: project_act_def) |
|
432 |
|
433 lemma project_act_extend_act: |
|
434 "project_act h (extend_act h' act) = |
|
435 {(x,x'). EX s s' y y' z. (s,s') : act & |
|
436 h(x,y) = h'(s,z) & h(x',y') = h'(s',z)}" |
|
437 by (simp add: extend_act_def project_act_def, blast) |
|
438 |
|
439 |
|
440 (*** OK and "lift" ***) |
|
441 |
|
442 lemma act_in_UNION_preserves_fst: |
|
443 "act <= {(x,x'). fst x = fst x'} ==> act : UNION (preserves fst) Acts" |
|
444 apply (rule_tac a = "mk_program (UNIV,{act},UNIV) " in UN_I) |
|
445 apply (auto simp add: preserves_def stable_def constrains_def) |
|
446 done |
|
447 |
|
448 |
|
449 ML |
|
450 {* |
|
451 bind_thm ("export_Acts_extend", export Acts_extend); |
|
452 bind_thm ("export_AllowedActs_extend", export AllowedActs_extend) |
|
453 *} |
|
454 |
|
455 lemma UNION_OK_lift_I: |
|
456 "[| ALL i:I. F i : preserves snd; |
|
457 ALL i:I. UNION (preserves fst) Acts <= AllowedActs (F i) |] |
|
458 ==> OK I (%i. lift i (F i))" |
|
459 apply (auto simp add: OK_def lift_def rename_def export_Acts_extend) |
|
460 apply (simp (no_asm) add: export_AllowedActs_extend project_act_extend_act) |
|
461 apply (rename_tac "act") |
|
462 apply (subgoal_tac |
|
463 "{(x, x'). \<exists>s f u s' f' u'. |
|
464 ((s, f, u), s', f', u') : act & |
|
465 lift_map j x = lift_map i (s, f, u) & |
|
466 lift_map j x' = lift_map i (s', f', u') } |
|
467 <= { (x,x') . fst x = fst x'}") |
|
468 apply (blast intro: act_in_UNION_preserves_fst, clarify) |
|
469 apply (drule_tac x = j in fun_cong)+ |
|
470 apply (drule_tac x = i in bspec, assumption) |
|
471 apply (frule preserves_imp_eq, auto) |
|
472 done |
|
473 |
|
474 lemma OK_lift_I: |
|
475 "[| ALL i:I. F i : preserves snd; |
|
476 ALL i:I. preserves fst <= Allowed (F i) |] |
|
477 ==> OK I (%i. lift i (F i))" |
|
478 by (simp add: safety_prop_AllowedActs_iff_Allowed UNION_OK_lift_I) |
|
479 |
|
480 |
|
481 lemma Allowed_lift [simp]: "Allowed (lift i F) = lift i ` (Allowed F)" |
|
482 by (simp add: lift_def Allowed_rename) |
|
483 |
|
484 lemma lift_image_preserves: "lift i ` preserves v = preserves (v o drop_map i)" |
|
485 apply (simp (no_asm) add: rename_image_preserves lift_def inv_lift_map_eq) |
|
486 done |
38 |
487 |
39 end |
488 end |