1 (* Title: HOL/Bali/Evaln.thy |
1 (* Title: HOL/Bali/Evaln.thy |
2 Author: David von Oheimb and Norbert Schirmer |
2 Author: David von Oheimb and Norbert Schirmer |
3 *) |
3 *) |
4 subsection {* Operational evaluation (big-step) semantics of Java expressions and |
4 subsection \<open>Operational evaluation (big-step) semantics of Java expressions and |
5 statements |
5 statements |
6 *} |
6 \<close> |
7 |
7 |
8 theory Evaln imports TypeSafe begin |
8 theory Evaln imports TypeSafe begin |
9 |
9 |
10 |
10 |
11 text {* |
11 text \<open> |
12 Variant of @{term eval} relation with counter for bounded recursive depth. |
12 Variant of @{term eval} relation with counter for bounded recursive depth. |
13 In principal @{term evaln} could replace @{term eval}. |
13 In principal @{term evaln} could replace @{term eval}. |
14 |
14 |
15 Validity of the axiomatic semantics builds on @{term evaln}. |
15 Validity of the axiomatic semantics builds on @{term evaln}. |
16 For recursive method calls the axiomatic semantics rule assumes the method ok |
16 For recursive method calls the axiomatic semantics rule assumes the method ok |
23 versa. To make |
23 versa. To make |
24 this switch easy @{term evaln} also does all the technical accessibility tests |
24 this switch easy @{term evaln} also does all the technical accessibility tests |
25 @{term check_field_access} and @{term check_method_access} like @{term eval}. |
25 @{term check_field_access} and @{term check_method_access} like @{term eval}. |
26 If it would omit them @{term evaln} and @{term eval} would only be equivalent |
26 If it would omit them @{term evaln} and @{term eval} would only be equivalent |
27 for welltyped, and definitely assigned terms. |
27 for welltyped, and definitely assigned terms. |
28 *} |
28 \<close> |
29 |
29 |
30 inductive |
30 inductive |
31 evaln :: "[prog, state, term, nat, vals, state] \<Rightarrow> bool" |
31 evaln :: "[prog, state, term, nat, vals, state] \<Rightarrow> bool" |
32 ("_\<turnstile>_ \<midarrow>_\<succ>\<midarrow>_\<rightarrow> '(_, _')" [61,61,80,61,0,0] 60) |
32 ("_\<turnstile>_ \<midarrow>_\<succ>\<midarrow>_\<rightarrow> '(_, _')" [61,61,80,61,0,0] 60) |
33 and evarn :: "[prog, state, var, vvar, nat, state] \<Rightarrow> bool" |
33 and evarn :: "[prog, state, var, vvar, nat, state] \<Rightarrow> bool" |
44 "G\<turnstile>s \<midarrow>c \<midarrow>n\<rightarrow> s' \<equiv> G\<turnstile>s \<midarrow>In1r c\<succ>\<midarrow>n\<rightarrow> (\<diamondsuit> , s')" |
44 "G\<turnstile>s \<midarrow>c \<midarrow>n\<rightarrow> s' \<equiv> G\<turnstile>s \<midarrow>In1r c\<succ>\<midarrow>n\<rightarrow> (\<diamondsuit> , s')" |
45 | "G\<turnstile>s \<midarrow>e-\<succ>v \<midarrow>n\<rightarrow> s' \<equiv> G\<turnstile>s \<midarrow>In1l e\<succ>\<midarrow>n\<rightarrow> (In1 v , s')" |
45 | "G\<turnstile>s \<midarrow>e-\<succ>v \<midarrow>n\<rightarrow> s' \<equiv> G\<turnstile>s \<midarrow>In1l e\<succ>\<midarrow>n\<rightarrow> (In1 v , s')" |
46 | "G\<turnstile>s \<midarrow>e=\<succ>vf \<midarrow>n\<rightarrow> s' \<equiv> G\<turnstile>s \<midarrow>In2 e\<succ>\<midarrow>n\<rightarrow> (In2 vf, s')" |
46 | "G\<turnstile>s \<midarrow>e=\<succ>vf \<midarrow>n\<rightarrow> s' \<equiv> G\<turnstile>s \<midarrow>In2 e\<succ>\<midarrow>n\<rightarrow> (In2 vf, s')" |
47 | "G\<turnstile>s \<midarrow>e\<doteq>\<succ>v \<midarrow>n\<rightarrow> s' \<equiv> G\<turnstile>s \<midarrow>In3 e\<succ>\<midarrow>n\<rightarrow> (In3 v , s')" |
47 | "G\<turnstile>s \<midarrow>e\<doteq>\<succ>v \<midarrow>n\<rightarrow> s' \<equiv> G\<turnstile>s \<midarrow>In3 e\<succ>\<midarrow>n\<rightarrow> (In3 v , s')" |
48 |
48 |
49 --{* propagation of abrupt completion *} |
49 \<comment>\<open>propagation of abrupt completion\<close> |
50 |
50 |
51 | Abrupt: "G\<turnstile>(Some xc,s) \<midarrow>t\<succ>\<midarrow>n\<rightarrow> (undefined3 t,(Some xc,s))" |
51 | Abrupt: "G\<turnstile>(Some xc,s) \<midarrow>t\<succ>\<midarrow>n\<rightarrow> (undefined3 t,(Some xc,s))" |
52 |
52 |
53 |
53 |
54 --{* evaluation of variables *} |
54 \<comment>\<open>evaluation of variables\<close> |
55 |
55 |
56 | LVar: "G\<turnstile>Norm s \<midarrow>LVar vn=\<succ>lvar vn s\<midarrow>n\<rightarrow> Norm s" |
56 | LVar: "G\<turnstile>Norm s \<midarrow>LVar vn=\<succ>lvar vn s\<midarrow>n\<rightarrow> Norm s" |
57 |
57 |
58 | FVar: "\<lbrakk>G\<turnstile>Norm s0 \<midarrow>Init statDeclC\<midarrow>n\<rightarrow> s1; G\<turnstile>s1 \<midarrow>e-\<succ>a\<midarrow>n\<rightarrow> s2; |
58 | FVar: "\<lbrakk>G\<turnstile>Norm s0 \<midarrow>Init statDeclC\<midarrow>n\<rightarrow> s1; G\<turnstile>s1 \<midarrow>e-\<succ>a\<midarrow>n\<rightarrow> s2; |
59 (v,s2') = fvar statDeclC stat fn a s2; |
59 (v,s2') = fvar statDeclC stat fn a s2; |
127 then abupd (\<lambda> x. Some (Error CrossMethodJump)) s2 |
127 then abupd (\<lambda> x. Some (Error CrossMethodJump)) s2 |
128 else s2)\<rbrakk>\<Longrightarrow> |
128 else s2)\<rbrakk>\<Longrightarrow> |
129 G\<turnstile>Norm s0 \<midarrow>Body D c |
129 G\<turnstile>Norm s0 \<midarrow>Body D c |
130 -\<succ>the (locals (store s2) Result)\<midarrow>n\<rightarrow>abupd (absorb Ret) s3" |
130 -\<succ>the (locals (store s2) Result)\<midarrow>n\<rightarrow>abupd (absorb Ret) s3" |
131 |
131 |
132 --{* evaluation of expression lists *} |
132 \<comment>\<open>evaluation of expression lists\<close> |
133 |
133 |
134 | Nil: |
134 | Nil: |
135 "G\<turnstile>Norm s0 \<midarrow>[]\<doteq>\<succ>[]\<midarrow>n\<rightarrow> Norm s0" |
135 "G\<turnstile>Norm s0 \<midarrow>[]\<doteq>\<succ>[]\<midarrow>n\<rightarrow> Norm s0" |
136 |
136 |
137 | Cons: "\<lbrakk>G\<turnstile>Norm s0 \<midarrow>e -\<succ> v \<midarrow>n\<rightarrow> s1; |
137 | Cons: "\<lbrakk>G\<turnstile>Norm s0 \<midarrow>e -\<succ> v \<midarrow>n\<rightarrow> s1; |
138 G\<turnstile> s1 \<midarrow>es\<doteq>\<succ>vs\<midarrow>n\<rightarrow> s2\<rbrakk> \<Longrightarrow> |
138 G\<turnstile> s1 \<midarrow>es\<doteq>\<succ>vs\<midarrow>n\<rightarrow> s2\<rbrakk> \<Longrightarrow> |
139 G\<turnstile>Norm s0 \<midarrow>e#es\<doteq>\<succ>v#vs\<midarrow>n\<rightarrow> s2" |
139 G\<turnstile>Norm s0 \<midarrow>e#es\<doteq>\<succ>v#vs\<midarrow>n\<rightarrow> s2" |
140 |
140 |
141 |
141 |
142 --{* execution of statements *} |
142 \<comment>\<open>execution of statements\<close> |
143 |
143 |
144 | Skip: "G\<turnstile>Norm s \<midarrow>Skip\<midarrow>n\<rightarrow> Norm s" |
144 | Skip: "G\<turnstile>Norm s \<midarrow>Skip\<midarrow>n\<rightarrow> Norm s" |
145 |
145 |
146 | Expr: "\<lbrakk>G\<turnstile>Norm s0 \<midarrow>e-\<succ>v\<midarrow>n\<rightarrow> s1\<rbrakk> \<Longrightarrow> |
146 | Expr: "\<lbrakk>G\<turnstile>Norm s0 \<midarrow>e-\<succ>v\<midarrow>n\<rightarrow> s1\<rbrakk> \<Longrightarrow> |
147 G\<turnstile>Norm s0 \<midarrow>Expr e\<midarrow>n\<rightarrow> s1" |
147 G\<turnstile>Norm s0 \<midarrow>Expr e\<midarrow>n\<rightarrow> s1" |
195 |
195 |
196 declare split_if [split del] split_if_asm [split del] |
196 declare split_if [split del] split_if_asm [split del] |
197 option.split [split del] option.split_asm [split del] |
197 option.split [split del] option.split_asm [split del] |
198 not_None_eq [simp del] |
198 not_None_eq [simp del] |
199 split_paired_All [simp del] split_paired_Ex [simp del] |
199 split_paired_All [simp del] split_paired_Ex [simp del] |
200 setup {* map_theory_simpset (fn ctxt => ctxt delloop "split_all_tac") *} |
200 setup \<open>map_theory_simpset (fn ctxt => ctxt delloop "split_all_tac")\<close> |
201 |
201 |
202 inductive_cases evaln_cases: "G\<turnstile>s \<midarrow>t\<succ>\<midarrow>n\<rightarrow> (v, s')" |
202 inductive_cases evaln_cases: "G\<turnstile>s \<midarrow>t\<succ>\<midarrow>n\<rightarrow> (v, s')" |
203 |
203 |
204 inductive_cases evaln_elim_cases: |
204 inductive_cases evaln_elim_cases: |
205 "G\<turnstile>(Some xc, s) \<midarrow>t \<succ>\<midarrow>n\<rightarrow> (v, s')" |
205 "G\<turnstile>(Some xc, s) \<midarrow>t \<succ>\<midarrow>n\<rightarrow> (v, s')" |
236 |
236 |
237 declare split_if [split] split_if_asm [split] |
237 declare split_if [split] split_if_asm [split] |
238 option.split [split] option.split_asm [split] |
238 option.split [split] option.split_asm [split] |
239 not_None_eq [simp] |
239 not_None_eq [simp] |
240 split_paired_All [simp] split_paired_Ex [simp] |
240 split_paired_All [simp] split_paired_Ex [simp] |
241 declaration {* K (Simplifier.map_ss (fn ss => ss addloop ("split_all_tac", split_all_tac))) *} |
241 declaration \<open>K (Simplifier.map_ss (fn ss => ss addloop ("split_all_tac", split_all_tac)))\<close> |
242 |
242 |
243 lemma evaln_Inj_elim: "G\<turnstile>s \<midarrow>t\<succ>\<midarrow>n\<rightarrow> (w,s') \<Longrightarrow> case t of In1 ec \<Rightarrow> |
243 lemma evaln_Inj_elim: "G\<turnstile>s \<midarrow>t\<succ>\<midarrow>n\<rightarrow> (w,s') \<Longrightarrow> case t of In1 ec \<Rightarrow> |
244 (case ec of Inl e \<Rightarrow> (\<exists>v. w = In1 v) | Inr c \<Rightarrow> w = \<diamondsuit>) |
244 (case ec of Inl e \<Rightarrow> (\<exists>v. w = In1 v) | Inr c \<Rightarrow> w = \<diamondsuit>) |
245 | In2 e \<Rightarrow> (\<exists>v. w = In2 v) | In3 e \<Rightarrow> (\<exists>v. w = In3 v)" |
245 | In2 e \<Rightarrow> (\<exists>v. w = In2 v) | In3 e \<Rightarrow> (\<exists>v. w = In3 v)" |
246 apply (erule evaln_cases , auto) |
246 apply (erule evaln_cases , auto) |
247 apply (induct_tac "t") |
247 apply (induct_tac "t") |
248 apply (rename_tac a, induct_tac "a") |
248 apply (rename_tac a, induct_tac "a") |
249 apply auto |
249 apply auto |
250 done |
250 done |
251 |
251 |
252 text {* The following simplification procedures set up the proper injections of |
252 text \<open>The following simplification procedures set up the proper injections of |
253 terms and their corresponding values in the evaluation relation: |
253 terms and their corresponding values in the evaluation relation: |
254 E.g. an expression |
254 E.g. an expression |
255 (injection @{term In1l} into terms) always evaluates to ordinary values |
255 (injection @{term In1l} into terms) always evaluates to ordinary values |
256 (injection @{term In1} into generalised values @{term vals}). |
256 (injection @{term In1} into generalised values @{term vals}). |
257 *} |
257 \<close> |
258 |
258 |
259 lemma evaln_expr_eq: "G\<turnstile>s \<midarrow>In1l t\<succ>\<midarrow>n\<rightarrow> (w, s') = (\<exists>v. w=In1 v \<and> G\<turnstile>s \<midarrow>t-\<succ>v \<midarrow>n\<rightarrow> s')" |
259 lemma evaln_expr_eq: "G\<turnstile>s \<midarrow>In1l t\<succ>\<midarrow>n\<rightarrow> (w, s') = (\<exists>v. w=In1 v \<and> G\<turnstile>s \<midarrow>t-\<succ>v \<midarrow>n\<rightarrow> s')" |
260 by (auto, frule evaln_Inj_elim, auto) |
260 by (auto, frule evaln_Inj_elim, auto) |
261 |
261 |
262 lemma evaln_var_eq: "G\<turnstile>s \<midarrow>In2 t\<succ>\<midarrow>n\<rightarrow> (w, s') = (\<exists>vf. w=In2 vf \<and> G\<turnstile>s \<midarrow>t=\<succ>vf\<midarrow>n\<rightarrow> s')" |
262 lemma evaln_var_eq: "G\<turnstile>s \<midarrow>In2 t\<succ>\<midarrow>n\<rightarrow> (w, s') = (\<exists>vf. w=In2 vf \<and> G\<turnstile>s \<midarrow>t=\<succ>vf\<midarrow>n\<rightarrow> s')" |
266 by (auto, frule evaln_Inj_elim, auto) |
266 by (auto, frule evaln_Inj_elim, auto) |
267 |
267 |
268 lemma evaln_stmt_eq: "G\<turnstile>s \<midarrow>In1r t\<succ>\<midarrow>n\<rightarrow> (w, s') = (w=\<diamondsuit> \<and> G\<turnstile>s \<midarrow>t \<midarrow>n\<rightarrow> s')" |
268 lemma evaln_stmt_eq: "G\<turnstile>s \<midarrow>In1r t\<succ>\<midarrow>n\<rightarrow> (w, s') = (w=\<diamondsuit> \<and> G\<turnstile>s \<midarrow>t \<midarrow>n\<rightarrow> s')" |
269 by (auto, frule evaln_Inj_elim, auto, frule evaln_Inj_elim, auto) |
269 by (auto, frule evaln_Inj_elim, auto, frule evaln_Inj_elim, auto) |
270 |
270 |
271 simproc_setup evaln_expr ("G\<turnstile>s \<midarrow>In1l t\<succ>\<midarrow>n\<rightarrow> (w, s')") = {* |
271 simproc_setup evaln_expr ("G\<turnstile>s \<midarrow>In1l t\<succ>\<midarrow>n\<rightarrow> (w, s')") = \<open> |
272 fn _ => fn _ => fn ct => |
272 fn _ => fn _ => fn ct => |
273 (case Thm.term_of ct of |
273 (case Thm.term_of ct of |
274 (_ $ _ $ _ $ _ $ _ $ (Const _ $ _) $ _) => NONE |
274 (_ $ _ $ _ $ _ $ _ $ (Const _ $ _) $ _) => NONE |
275 | _ => SOME (mk_meta_eq @{thm evaln_expr_eq})) *} |
275 | _ => SOME (mk_meta_eq @{thm evaln_expr_eq}))\<close> |
276 |
276 |
277 simproc_setup evaln_var ("G\<turnstile>s \<midarrow>In2 t\<succ>\<midarrow>n\<rightarrow> (w, s')") = {* |
277 simproc_setup evaln_var ("G\<turnstile>s \<midarrow>In2 t\<succ>\<midarrow>n\<rightarrow> (w, s')") = \<open> |
278 fn _ => fn _ => fn ct => |
278 fn _ => fn _ => fn ct => |
279 (case Thm.term_of ct of |
279 (case Thm.term_of ct of |
280 (_ $ _ $ _ $ _ $ _ $ (Const _ $ _) $ _) => NONE |
280 (_ $ _ $ _ $ _ $ _ $ (Const _ $ _) $ _) => NONE |
281 | _ => SOME (mk_meta_eq @{thm evaln_var_eq})) *} |
281 | _ => SOME (mk_meta_eq @{thm evaln_var_eq}))\<close> |
282 |
282 |
283 simproc_setup evaln_exprs ("G\<turnstile>s \<midarrow>In3 t\<succ>\<midarrow>n\<rightarrow> (w, s')") = {* |
283 simproc_setup evaln_exprs ("G\<turnstile>s \<midarrow>In3 t\<succ>\<midarrow>n\<rightarrow> (w, s')") = \<open> |
284 fn _ => fn _ => fn ct => |
284 fn _ => fn _ => fn ct => |
285 (case Thm.term_of ct of |
285 (case Thm.term_of ct of |
286 (_ $ _ $ _ $ _ $ _ $ (Const _ $ _) $ _) => NONE |
286 (_ $ _ $ _ $ _ $ _ $ (Const _ $ _) $ _) => NONE |
287 | _ => SOME (mk_meta_eq @{thm evaln_exprs_eq})) *} |
287 | _ => SOME (mk_meta_eq @{thm evaln_exprs_eq}))\<close> |
288 |
288 |
289 simproc_setup evaln_stmt ("G\<turnstile>s \<midarrow>In1r t\<succ>\<midarrow>n\<rightarrow> (w, s')") = {* |
289 simproc_setup evaln_stmt ("G\<turnstile>s \<midarrow>In1r t\<succ>\<midarrow>n\<rightarrow> (w, s')") = \<open> |
290 fn _ => fn _ => fn ct => |
290 fn _ => fn _ => fn ct => |
291 (case Thm.term_of ct of |
291 (case Thm.term_of ct of |
292 (_ $ _ $ _ $ _ $ _ $ (Const _ $ _) $ _) => NONE |
292 (_ $ _ $ _ $ _ $ _ $ (Const _ $ _) $ _) => NONE |
293 | _ => SOME (mk_meta_eq @{thm evaln_stmt_eq})) *} |
293 | _ => SOME (mk_meta_eq @{thm evaln_stmt_eq}))\<close> |
294 |
294 |
295 ML {* ML_Thms.bind_thms ("evaln_AbruptIs", sum3_instantiate @{context} @{thm evaln.Abrupt}) *} |
295 ML \<open>ML_Thms.bind_thms ("evaln_AbruptIs", sum3_instantiate @{context} @{thm evaln.Abrupt})\<close> |
296 declare evaln_AbruptIs [intro!] |
296 declare evaln_AbruptIs [intro!] |
297 |
297 |
298 lemma evaln_Callee: "G\<turnstile>Norm s\<midarrow>In1l (Callee l e)\<succ>\<midarrow>n\<rightarrow> (v,s') = False" |
298 lemma evaln_Callee: "G\<turnstile>Norm s\<midarrow>In1l (Callee l e)\<succ>\<midarrow>n\<rightarrow> (v,s') = False" |
299 proof - |
299 proof - |
300 { fix s t v s' |
300 { fix s t v s' |
353 w=undefined3 e \<and> G\<turnstile>(Some xc,s) \<midarrow>e\<succ>\<midarrow>n\<rightarrow> (undefined3 e,(Some xc,s)))" |
353 w=undefined3 e \<and> G\<turnstile>(Some xc,s) \<midarrow>e\<succ>\<midarrow>n\<rightarrow> (undefined3 e,(Some xc,s)))" |
354 apply auto |
354 apply auto |
355 apply (frule evaln_abrupt_lemma, auto)+ |
355 apply (frule evaln_abrupt_lemma, auto)+ |
356 done |
356 done |
357 |
357 |
358 simproc_setup evaln_abrupt ("G\<turnstile>(Some xc,s) \<midarrow>e\<succ>\<midarrow>n\<rightarrow> (w,s')") = {* |
358 simproc_setup evaln_abrupt ("G\<turnstile>(Some xc,s) \<midarrow>e\<succ>\<midarrow>n\<rightarrow> (w,s')") = \<open> |
359 fn _ => fn _ => fn ct => |
359 fn _ => fn _ => fn ct => |
360 (case Thm.term_of ct of |
360 (case Thm.term_of ct of |
361 (_ $ _ $ _ $ _ $ _ $ _ $ (Const (@{const_name Pair}, _) $ (Const (@{const_name Some},_) $ _)$ _)) |
361 (_ $ _ $ _ $ _ $ _ $ _ $ (Const (@{const_name Pair}, _) $ (Const (@{const_name Some},_) $ _)$ _)) |
362 => NONE |
362 => NONE |
363 | _ => SOME (mk_meta_eq @{thm evaln_abrupt})) |
363 | _ => SOME (mk_meta_eq @{thm evaln_abrupt})) |
364 *} |
364 \<close> |
365 |
365 |
366 lemma evaln_LitI: "G\<turnstile>s \<midarrow>Lit v-\<succ>(if normal s then v else undefined)\<midarrow>n\<rightarrow> s" |
366 lemma evaln_LitI: "G\<turnstile>s \<midarrow>Lit v-\<succ>(if normal s then v else undefined)\<midarrow>n\<rightarrow> s" |
367 apply (case_tac "s", case_tac "a = None") |
367 apply (case_tac "s", case_tac "a = None") |
368 by (auto intro!: evaln.Lit) |
368 by (auto intro!: evaln.Lit) |
369 |
369 |
399 done |
399 done |
400 |
400 |
401 |
401 |
402 |
402 |
403 |
403 |
404 subsubsection {* evaln implies eval *} |
404 subsubsection \<open>evaln implies eval\<close> |
405 |
405 |
406 lemma evaln_eval: |
406 lemma evaln_eval: |
407 assumes evaln: "G\<turnstile>s0 \<midarrow>t\<succ>\<midarrow>n\<rightarrow> (v,s1)" |
407 assumes evaln: "G\<turnstile>s0 \<midarrow>t\<succ>\<midarrow>n\<rightarrow> (v,s1)" |
408 shows "G\<turnstile>s0 \<midarrow>t\<succ>\<rightarrow> (v,s1)" |
408 shows "G\<turnstile>s0 \<midarrow>t\<succ>\<rightarrow> (v,s1)" |
409 using evaln |
409 using evaln |
410 proof (induct) |
410 proof (induct) |
411 case (Loop s0 e b n s1 c s2 l s3) |
411 case (Loop s0 e b n s1 c s2 l s3) |
412 note `G\<turnstile>Norm s0 \<midarrow>e-\<succ>b\<rightarrow> s1` |
412 note \<open>G\<turnstile>Norm s0 \<midarrow>e-\<succ>b\<rightarrow> s1\<close> |
413 moreover |
413 moreover |
414 have "if the_Bool b |
414 have "if the_Bool b |
415 then (G\<turnstile>s1 \<midarrow>c\<rightarrow> s2) \<and> |
415 then (G\<turnstile>s1 \<midarrow>c\<rightarrow> s2) \<and> |
416 G\<turnstile>abupd (absorb (Cont l)) s2 \<midarrow>l\<bullet> While(e) c\<rightarrow> s3 |
416 G\<turnstile>abupd (absorb (Cont l)) s2 \<midarrow>l\<bullet> While(e) c\<rightarrow> s3 |
417 else s3 = s1" |
417 else s3 = s1" |
418 using Loop.hyps by simp |
418 using Loop.hyps by simp |
419 ultimately show ?case by (rule eval.Loop) |
419 ultimately show ?case by (rule eval.Loop) |
420 next |
420 next |
421 case (Try s0 c1 n s1 s2 C vn c2 s3) |
421 case (Try s0 c1 n s1 s2 C vn c2 s3) |
422 note `G\<turnstile>Norm s0 \<midarrow>c1\<rightarrow> s1` |
422 note \<open>G\<turnstile>Norm s0 \<midarrow>c1\<rightarrow> s1\<close> |
423 moreover |
423 moreover |
424 note `G\<turnstile>s1 \<midarrow>sxalloc\<rightarrow> s2` |
424 note \<open>G\<turnstile>s1 \<midarrow>sxalloc\<rightarrow> s2\<close> |
425 moreover |
425 moreover |
426 have "if G,s2\<turnstile>catch C then G\<turnstile>new_xcpt_var vn s2 \<midarrow>c2\<rightarrow> s3 else s3 = s2" |
426 have "if G,s2\<turnstile>catch C then G\<turnstile>new_xcpt_var vn s2 \<midarrow>c2\<rightarrow> s3 else s3 = s2" |
427 using Try.hyps by simp |
427 using Try.hyps by simp |
428 ultimately show ?case by (rule eval.Try) |
428 ultimately show ?case by (rule eval.Try) |
429 next |
429 next |
430 case (Init C c s0 s3 n s1 s2) |
430 case (Init C c s0 s3 n s1 s2) |
431 note `the (class G C) = c` |
431 note \<open>the (class G C) = c\<close> |
432 moreover |
432 moreover |
433 have "if inited C (globs s0) |
433 have "if inited C (globs s0) |
434 then s3 = Norm s0 |
434 then s3 = Norm s0 |
435 else G\<turnstile>Norm ((init_class_obj G C) s0) |
435 else G\<turnstile>Norm ((init_class_obj G C) s0) |
436 \<midarrow>(if C = Object then Skip else Init (super c))\<rightarrow> s1 \<and> |
436 \<midarrow>(if C = Object then Skip else Init (super c))\<rightarrow> s1 \<and> |
446 done |
446 done |
447 |
447 |
448 lemma evaln_nonstrict [rule_format (no_asm), elim]: |
448 lemma evaln_nonstrict [rule_format (no_asm), elim]: |
449 "G\<turnstile>s \<midarrow>t\<succ>\<midarrow>n\<rightarrow> (w, s') \<Longrightarrow> \<forall>m. n\<le>m \<longrightarrow> G\<turnstile>s \<midarrow>t\<succ>\<midarrow>m\<rightarrow> (w, s')" |
449 "G\<turnstile>s \<midarrow>t\<succ>\<midarrow>n\<rightarrow> (w, s') \<Longrightarrow> \<forall>m. n\<le>m \<longrightarrow> G\<turnstile>s \<midarrow>t\<succ>\<midarrow>m\<rightarrow> (w, s')" |
450 apply (erule evaln.induct) |
450 apply (erule evaln.induct) |
451 apply (tactic {* ALLGOALS (EVERY' [strip_tac @{context}, |
451 apply (tactic \<open>ALLGOALS (EVERY' [strip_tac @{context}, |
452 TRY o eresolve_tac @{context} @{thms Suc_le_D_lemma}, |
452 TRY o eresolve_tac @{context} @{thms Suc_le_D_lemma}, |
453 REPEAT o smp_tac @{context} 1, |
453 REPEAT o smp_tac @{context} 1, |
454 resolve_tac @{context} @{thms evaln.intros} THEN_ALL_NEW TRY o assume_tac @{context}]) *}) |
454 resolve_tac @{context} @{thms evaln.intros} THEN_ALL_NEW TRY o assume_tac @{context}])\<close>) |
455 (* 3 subgoals *) |
455 (* 3 subgoals *) |
456 apply (auto split del: split_if) |
456 apply (auto split del: split_if) |
457 done |
457 done |
458 |
458 |
459 lemmas evaln_nonstrict_Suc = evaln_nonstrict [OF _ le_refl [THEN le_SucI]] |
459 lemmas evaln_nonstrict_Suc = evaln_nonstrict [OF _ le_refl [THEN le_SucI]] |
595 case (Try s0 c1 s1 s2 catchC vn c2 s3) |
595 case (Try s0 c1 s1 s2 catchC vn c2 s3) |
596 from Try.hyps obtain n1 where |
596 from Try.hyps obtain n1 where |
597 "G\<turnstile>Norm s0 \<midarrow>c1\<midarrow>n1\<rightarrow> s1" |
597 "G\<turnstile>Norm s0 \<midarrow>c1\<midarrow>n1\<rightarrow> s1" |
598 by (iprover) |
598 by (iprover) |
599 moreover |
599 moreover |
600 note sxalloc = `G\<turnstile>s1 \<midarrow>sxalloc\<rightarrow> s2` |
600 note sxalloc = \<open>G\<turnstile>s1 \<midarrow>sxalloc\<rightarrow> s2\<close> |
601 moreover |
601 moreover |
602 from Try.hyps obtain n2 where |
602 from Try.hyps obtain n2 where |
603 "if G,s2\<turnstile>catch catchC then G\<turnstile>new_xcpt_var vn s2 \<midarrow>c2\<midarrow>n2\<rightarrow> s3 else s3 = s2" |
603 "if G,s2\<turnstile>catch catchC then G\<turnstile>new_xcpt_var vn s2 \<midarrow>c2\<midarrow>n2\<rightarrow> s3 else s3 = s2" |
604 by fastforce |
604 by fastforce |
605 ultimately |
605 ultimately |
611 from Fin obtain n1 n2 where |
611 from Fin obtain n1 n2 where |
612 "G\<turnstile>Norm s0 \<midarrow>c1\<midarrow>n1\<rightarrow> (x1, s1)" |
612 "G\<turnstile>Norm s0 \<midarrow>c1\<midarrow>n1\<rightarrow> (x1, s1)" |
613 "G\<turnstile>Norm s1 \<midarrow>c2\<midarrow>n2\<rightarrow> s2" |
613 "G\<turnstile>Norm s1 \<midarrow>c2\<midarrow>n2\<rightarrow> s2" |
614 by iprover |
614 by iprover |
615 moreover |
615 moreover |
616 note s3 = `s3 = (if \<exists>err. x1 = Some (Error err) |
616 note s3 = \<open>s3 = (if \<exists>err. x1 = Some (Error err) |
617 then (x1, s1) |
617 then (x1, s1) |
618 else abupd (abrupt_if (x1 \<noteq> None) x1) s2)` |
618 else abupd (abrupt_if (x1 \<noteq> None) x1) s2)\<close> |
619 ultimately |
619 ultimately |
620 have |
620 have |
621 "G\<turnstile>Norm s0 \<midarrow>c1 Finally c2\<midarrow>max n1 n2\<rightarrow> s3" |
621 "G\<turnstile>Norm s0 \<midarrow>c1 Finally c2\<midarrow>max n1 n2\<rightarrow> s3" |
622 by (blast intro: evaln.Fin dest: evaln_max2) |
622 by (blast intro: evaln.Fin dest: evaln_max2) |
623 then show ?case .. |
623 then show ?case .. |
624 next |
624 next |
625 case (Init C c s0 s3 s1 s2) |
625 case (Init C c s0 s3 s1 s2) |
626 note cls = `the (class G C) = c` |
626 note cls = \<open>the (class G C) = c\<close> |
627 moreover from Init.hyps obtain n where |
627 moreover from Init.hyps obtain n where |
628 "if inited C (globs s0) then s3 = Norm s0 |
628 "if inited C (globs s0) then s3 = Norm s0 |
629 else (G\<turnstile>Norm (init_class_obj G C s0) |
629 else (G\<turnstile>Norm (init_class_obj G C s0) |
630 \<midarrow>(if C = Object then Skip else Init (super c))\<midarrow>n\<rightarrow> s1 \<and> |
630 \<midarrow>(if C = Object then Skip else Init (super c))\<midarrow>n\<rightarrow> s1 \<and> |
631 G\<turnstile>set_lvars empty s1 \<midarrow>init c\<midarrow>n\<rightarrow> s2 \<and> |
631 G\<turnstile>set_lvars empty s1 \<midarrow>init c\<midarrow>n\<rightarrow> s2 \<and> |
648 then obtain n1 n2 where |
648 then obtain n1 n2 where |
649 "G\<turnstile>Norm s0 \<midarrow>init_comp_ty T\<midarrow>n1\<rightarrow> s1" |
649 "G\<turnstile>Norm s0 \<midarrow>init_comp_ty T\<midarrow>n1\<rightarrow> s1" |
650 "G\<turnstile>s1 \<midarrow>e-\<succ>i\<midarrow>n2\<rightarrow> s2" |
650 "G\<turnstile>s1 \<midarrow>e-\<succ>i\<midarrow>n2\<rightarrow> s2" |
651 by (iprover) |
651 by (iprover) |
652 moreover |
652 moreover |
653 note `G\<turnstile>abupd (check_neg i) s2 \<midarrow>halloc Arr T (the_Intg i)\<succ>a\<rightarrow> s3` |
653 note \<open>G\<turnstile>abupd (check_neg i) s2 \<midarrow>halloc Arr T (the_Intg i)\<succ>a\<rightarrow> s3\<close> |
654 ultimately |
654 ultimately |
655 have "G\<turnstile>Norm s0 \<midarrow>New T[e]-\<succ>Addr a\<midarrow>max n1 n2\<rightarrow> s3" |
655 have "G\<turnstile>Norm s0 \<midarrow>New T[e]-\<succ>Addr a\<midarrow>max n1 n2\<rightarrow> s3" |
656 by (blast intro: evaln.NewA dest: evaln_max2) |
656 by (blast intro: evaln.NewA dest: evaln_max2) |
657 then show ?case .. |
657 then show ?case .. |
658 next |
658 next |
659 case (Cast s0 e v s1 s2 castT) |
659 case (Cast s0 e v s1 s2 castT) |
660 then obtain n where |
660 then obtain n where |
661 "G\<turnstile>Norm s0 \<midarrow>e-\<succ>v\<midarrow>n\<rightarrow> s1" |
661 "G\<turnstile>Norm s0 \<midarrow>e-\<succ>v\<midarrow>n\<rightarrow> s1" |
662 by (iprover) |
662 by (iprover) |
663 moreover |
663 moreover |
664 note `s2 = abupd (raise_if (\<not> G,snd s1\<turnstile>v fits castT) ClassCast) s1` |
664 note \<open>s2 = abupd (raise_if (\<not> G,snd s1\<turnstile>v fits castT) ClassCast) s1\<close> |
665 ultimately |
665 ultimately |
666 have "G\<turnstile>Norm s0 \<midarrow>Cast castT e-\<succ>v\<midarrow>n\<rightarrow> s2" |
666 have "G\<turnstile>Norm s0 \<midarrow>Cast castT e-\<succ>v\<midarrow>n\<rightarrow> s2" |
667 by (rule evaln.Cast) |
667 by (rule evaln.Cast) |
668 then show ?case .. |
668 then show ?case .. |
669 next |
669 next |
670 case (Inst s0 e v s1 b T) |
670 case (Inst s0 e v s1 b T) |
671 then obtain n where |
671 then obtain n where |
672 "G\<turnstile>Norm s0 \<midarrow>e-\<succ>v\<midarrow>n\<rightarrow> s1" |
672 "G\<turnstile>Norm s0 \<midarrow>e-\<succ>v\<midarrow>n\<rightarrow> s1" |
673 by (iprover) |
673 by (iprover) |
674 moreover |
674 moreover |
675 note `b = (v \<noteq> Null \<and> G,snd s1\<turnstile>v fits RefT T)` |
675 note \<open>b = (v \<noteq> Null \<and> G,snd s1\<turnstile>v fits RefT T)\<close> |
676 ultimately |
676 ultimately |
677 have "G\<turnstile>Norm s0 \<midarrow>e InstOf T-\<succ>Bool b\<midarrow>n\<rightarrow> s1" |
677 have "G\<turnstile>Norm s0 \<midarrow>e InstOf T-\<succ>Bool b\<midarrow>n\<rightarrow> s1" |
678 by (rule evaln.Inst) |
678 by (rule evaln.Inst) |
679 then show ?case .. |
679 then show ?case .. |
680 next |
680 next |
740 then obtain n1 n2 where |
740 then obtain n1 n2 where |
741 "G\<turnstile>Norm s0 \<midarrow>e-\<succ>a'\<midarrow>n1\<rightarrow> s1" |
741 "G\<turnstile>Norm s0 \<midarrow>e-\<succ>a'\<midarrow>n1\<rightarrow> s1" |
742 "G\<turnstile>s1 \<midarrow>args\<doteq>\<succ>vs\<midarrow>n2\<rightarrow> s2" |
742 "G\<turnstile>s1 \<midarrow>args\<doteq>\<succ>vs\<midarrow>n2\<rightarrow> s2" |
743 by iprover |
743 by iprover |
744 moreover |
744 moreover |
745 note `invDeclC = invocation_declclass G mode (store s2) a' statT |
745 note \<open>invDeclC = invocation_declclass G mode (store s2) a' statT |
746 \<lparr>name=mn,parTs=pTs'\<rparr>` |
746 \<lparr>name=mn,parTs=pTs'\<rparr>\<close> |
747 moreover |
747 moreover |
748 note `s3 = init_lvars G invDeclC \<lparr>name=mn,parTs=pTs'\<rparr> mode a' vs s2` |
748 note \<open>s3 = init_lvars G invDeclC \<lparr>name=mn,parTs=pTs'\<rparr> mode a' vs s2\<close> |
749 moreover |
749 moreover |
750 note `s3'=check_method_access G accC' statT mode \<lparr>name=mn,parTs=pTs'\<rparr> a' s3` |
750 note \<open>s3'=check_method_access G accC' statT mode \<lparr>name=mn,parTs=pTs'\<rparr> a' s3\<close> |
751 moreover |
751 moreover |
752 from Call.hyps |
752 from Call.hyps |
753 obtain m where |
753 obtain m where |
754 "G\<turnstile>s3' \<midarrow>Methd invDeclC \<lparr>name=mn, parTs=pTs'\<rparr>-\<succ>v\<midarrow>m\<rightarrow> s4" |
754 "G\<turnstile>s3' \<midarrow>Methd invDeclC \<lparr>name=mn, parTs=pTs'\<rparr>-\<succ>v\<midarrow>m\<rightarrow> s4" |
755 by iprover |
755 by iprover |
771 from Body.hyps obtain n1 n2 where |
771 from Body.hyps obtain n1 n2 where |
772 evaln_init: "G\<turnstile>Norm s0 \<midarrow>Init D\<midarrow>n1\<rightarrow> s1" and |
772 evaln_init: "G\<turnstile>Norm s0 \<midarrow>Init D\<midarrow>n1\<rightarrow> s1" and |
773 evaln_c: "G\<turnstile>s1 \<midarrow>c\<midarrow>n2\<rightarrow> s2" |
773 evaln_c: "G\<turnstile>s1 \<midarrow>c\<midarrow>n2\<rightarrow> s2" |
774 by (iprover) |
774 by (iprover) |
775 moreover |
775 moreover |
776 note `s3 = (if \<exists>l. fst s2 = Some (Jump (Break l)) \<or> |
776 note \<open>s3 = (if \<exists>l. fst s2 = Some (Jump (Break l)) \<or> |
777 fst s2 = Some (Jump (Cont l)) |
777 fst s2 = Some (Jump (Cont l)) |
778 then abupd (\<lambda>x. Some (Error CrossMethodJump)) s2 |
778 then abupd (\<lambda>x. Some (Error CrossMethodJump)) s2 |
779 else s2)` |
779 else s2)\<close> |
780 ultimately |
780 ultimately |
781 have |
781 have |
782 "G\<turnstile>Norm s0 \<midarrow>Body D c-\<succ>the (locals (store s2) Result)\<midarrow>max n1 n2 |
782 "G\<turnstile>Norm s0 \<midarrow>Body D c-\<succ>the (locals (store s2) Result)\<midarrow>max n1 n2 |
783 \<rightarrow> abupd (absorb Ret) s3" |
783 \<rightarrow> abupd (absorb Ret) s3" |
784 by (iprover intro: evaln.Body dest: evaln_max2) |
784 by (iprover intro: evaln.Body dest: evaln_max2) |
794 then obtain n1 n2 where |
794 then obtain n1 n2 where |
795 "G\<turnstile>Norm s0 \<midarrow>Init statDeclC\<midarrow>n1\<rightarrow> s1" |
795 "G\<turnstile>Norm s0 \<midarrow>Init statDeclC\<midarrow>n1\<rightarrow> s1" |
796 "G\<turnstile>s1 \<midarrow>e-\<succ>a\<midarrow>n2\<rightarrow> s2" |
796 "G\<turnstile>s1 \<midarrow>e-\<succ>a\<midarrow>n2\<rightarrow> s2" |
797 by iprover |
797 by iprover |
798 moreover |
798 moreover |
799 note `s3 = check_field_access G accC statDeclC fn stat a s2'` |
799 note \<open>s3 = check_field_access G accC statDeclC fn stat a s2'\<close> |
800 and `(v, s2') = fvar statDeclC stat fn a s2` |
800 and \<open>(v, s2') = fvar statDeclC stat fn a s2\<close> |
801 ultimately |
801 ultimately |
802 have "G\<turnstile>Norm s0 \<midarrow>{accC,statDeclC,stat}e..fn=\<succ>v\<midarrow>max n1 n2\<rightarrow> s3" |
802 have "G\<turnstile>Norm s0 \<midarrow>{accC,statDeclC,stat}e..fn=\<succ>v\<midarrow>max n1 n2\<rightarrow> s3" |
803 by (iprover intro: evaln.FVar dest: evaln_max2) |
803 by (iprover intro: evaln.FVar dest: evaln_max2) |
804 then show ?case .. |
804 then show ?case .. |
805 next |
805 next |
807 then obtain n1 n2 where |
807 then obtain n1 n2 where |
808 "G\<turnstile>Norm s0 \<midarrow>e1-\<succ>a\<midarrow>n1\<rightarrow> s1" |
808 "G\<turnstile>Norm s0 \<midarrow>e1-\<succ>a\<midarrow>n1\<rightarrow> s1" |
809 "G\<turnstile>s1 \<midarrow>e2-\<succ>i\<midarrow>n2\<rightarrow> s2" |
809 "G\<turnstile>s1 \<midarrow>e2-\<succ>i\<midarrow>n2\<rightarrow> s2" |
810 by iprover |
810 by iprover |
811 moreover |
811 moreover |
812 note `(v, s2') = avar G i a s2` |
812 note \<open>(v, s2') = avar G i a s2\<close> |
813 ultimately |
813 ultimately |
814 have "G\<turnstile>Norm s0 \<midarrow>e1.[e2]=\<succ>v\<midarrow>max n1 n2\<rightarrow> s2'" |
814 have "G\<turnstile>Norm s0 \<midarrow>e1.[e2]=\<succ>v\<midarrow>max n1 n2\<rightarrow> s2'" |
815 by (blast intro!: evaln.AVar dest: evaln_max2) |
815 by (blast intro!: evaln.AVar dest: evaln_max2) |
816 then show ?case .. |
816 then show ?case .. |
817 next |
817 next |