src/HOL/Bali/Evaln.thy
changeset 62042 6c6ccf573479
parent 60754 02924903a6fd
child 62390 842917225d56
equal deleted inserted replaced
62041:52a87574bca9 62042:6c6ccf573479
     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;
    65                       G\<turnstile>Norm s0 \<midarrow>e1.[e2]=\<succ>v\<midarrow>n\<rightarrow> s2'"
    65                       G\<turnstile>Norm s0 \<midarrow>e1.[e2]=\<succ>v\<midarrow>n\<rightarrow> s2'"
    66 
    66 
    67 
    67 
    68 
    68 
    69 
    69 
    70 --{* evaluation of expressions *}
    70 \<comment>\<open>evaluation of expressions\<close>
    71 
    71 
    72 | NewC: "\<lbrakk>G\<turnstile>Norm s0 \<midarrow>Init C\<midarrow>n\<rightarrow> s1;
    72 | NewC: "\<lbrakk>G\<turnstile>Norm s0 \<midarrow>Init C\<midarrow>n\<rightarrow> s1;
    73           G\<turnstile>     s1 \<midarrow>halloc (CInst C)\<succ>a\<rightarrow> s2\<rbrakk> \<Longrightarrow>
    73           G\<turnstile>     s1 \<midarrow>halloc (CInst C)\<succ>a\<rightarrow> s2\<rbrakk> \<Longrightarrow>
    74                                   G\<turnstile>Norm s0 \<midarrow>NewC C-\<succ>Addr a\<midarrow>n\<rightarrow> s2"
    74                                   G\<turnstile>Norm s0 \<midarrow>NewC C-\<succ>Addr a\<midarrow>n\<rightarrow> s2"
    75 
    75 
   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]]
   509   show ?thesis .
   509   show ?thesis .
   510 qed
   510 qed
   511 
   511 
   512 declare [[simproc del: wt_expr wt_var wt_exprs wt_stmt]]
   512 declare [[simproc del: wt_expr wt_var wt_exprs wt_stmt]]
   513 
   513 
   514 subsubsection {* eval implies evaln *}
   514 subsubsection \<open>eval implies evaln\<close>
   515 lemma eval_evaln: 
   515 lemma eval_evaln: 
   516   assumes eval: "G\<turnstile>s0 \<midarrow>t\<succ>\<rightarrow> (v,s1)"
   516   assumes eval: "G\<turnstile>s0 \<midarrow>t\<succ>\<rightarrow> (v,s1)"
   517   shows  "\<exists>n. G\<turnstile>s0 \<midarrow>t\<succ>\<midarrow>n\<rightarrow> (v,s1)"
   517   shows  "\<exists>n. G\<turnstile>s0 \<midarrow>t\<succ>\<midarrow>n\<rightarrow> (v,s1)"
   518 using eval 
   518 using eval 
   519 proof (induct)
   519 proof (induct)
   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