src/HOL/Bali/Evaln.thy
changeset 69597 ff784d5a5bfb
parent 68451 c34aa23a1fb6
child 78099 4d9349989d94
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
     7 
     7 
     8 theory Evaln imports TypeSafe begin
     8 theory Evaln imports TypeSafe begin
     9 
     9 
    10 
    10 
    11 text \<open>
    11 text \<open>
    12 Variant of @{term eval} relation with counter for bounded recursive depth. 
    12 Variant of \<^term>\<open>eval\<close> relation with counter for bounded recursive depth. 
    13 In principal @{term evaln} could replace @{term eval}.
    13 In principal \<^term>\<open>evaln\<close> could replace \<^term>\<open>eval\<close>.
    14 
    14 
    15 Validity of the axiomatic semantics builds on @{term evaln}. 
    15 Validity of the axiomatic semantics builds on \<^term>\<open>evaln\<close>. 
    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 
    17 to derive a proof for the body. To prove the method rule sound we need to 
    17 to derive a proof for the body. To prove the method rule sound we need to 
    18 perform induction on the recursion depth. 
    18 perform induction on the recursion depth. 
    19 For the completeness proof of the axiomatic semantics the notion of the most
    19 For the completeness proof of the axiomatic semantics the notion of the most
    20 general formula is used. The most general formula right now builds on the 
    20 general formula is used. The most general formula right now builds on the 
    21 ordinary evaluation relation @{term eval}. 
    21 ordinary evaluation relation \<^term>\<open>eval\<close>. 
    22 So sometimes we have to switch between @{term evaln} and @{term eval} and vice 
    22 So sometimes we have to switch between \<^term>\<open>evaln\<close> and \<^term>\<open>eval\<close> and vice 
    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>\<open>evaln\<close> also does all the technical accessibility tests 
    25 @{term check_field_access} and @{term check_method_access} like @{term eval}. 
    25 \<^term>\<open>check_field_access\<close> and \<^term>\<open>check_method_access\<close> like \<^term>\<open>eval\<close>. 
    26 If it would omit them @{term evaln} and @{term eval} would only be equivalent 
    26 If it would omit them \<^term>\<open>evaln\<close> and \<^term>\<open>eval\<close> would only be equivalent 
    27 for welltyped, and definitely assigned terms.
    27 for welltyped, and definitely assigned terms.
    28 \<close>
    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"
   250 done
   250 done
   251 
   251 
   252 text \<open>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>\<open>In1l\<close> into terms) always evaluates to ordinary values 
   256  (injection @{term In1} into generalised values @{term vals}). 
   256  (injection \<^term>\<open>In1\<close> into generalised values \<^term>\<open>vals\<close>). 
   257 \<close>
   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 
   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}))\<close>
   293     | _ => SOME (mk_meta_eq @{thm evaln_stmt_eq}))\<close>
   294 
   294 
   295 ML \<open>ML_Thms.bind_thms ("evaln_AbruptIs", sum3_instantiate @{context} @{thm evaln.Abrupt})\<close>
   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'
   356 done
   356 done
   357 
   357 
   358 simproc_setup evaln_abrupt ("G\<turnstile>(Some xc,s) \<midarrow>e\<succ>\<midarrow>n\<rightarrow> (w,s')") = \<open>
   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>\<open>Pair\<close>, _) $ (Const (\<^const_name>\<open>Some\<close>,_) $ _)$ _))
   362         => NONE
   362         => NONE
   363     | _ => SOME (mk_meta_eq @{thm evaln_abrupt}))
   363     | _ => SOME (mk_meta_eq @{thm evaln_abrupt}))
   364 \<close>
   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"
   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 \<open>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}])\<close>)
   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: if_split)
   456 apply (auto split del: if_split)
   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]]