18 |
18 |
19 |
19 |
20 |
20 |
21 section "set of not yet initialzed classes" |
21 section "set of not yet initialzed classes" |
22 |
22 |
23 definition nyinitcls :: "prog \<Rightarrow> state \<Rightarrow> qtname set" where |
23 definition |
24 "nyinitcls G s \<equiv> {C. is_class G C \<and> \<not> initd C s}" |
24 nyinitcls :: "prog \<Rightarrow> state \<Rightarrow> qtname set" |
|
25 where "nyinitcls G s = {C. is_class G C \<and> \<not> initd C s}" |
25 |
26 |
26 lemma nyinitcls_subset_class: "nyinitcls G s \<subseteq> {C. is_class G C}" |
27 lemma nyinitcls_subset_class: "nyinitcls G s \<subseteq> {C. is_class G C}" |
27 apply (unfold nyinitcls_def) |
28 apply (unfold nyinitcls_def) |
28 apply fast |
29 apply fast |
29 done |
30 done |
111 done |
112 done |
112 |
113 |
113 |
114 |
114 section "init-le" |
115 section "init-le" |
115 |
116 |
116 definition init_le :: "prog \<Rightarrow> nat \<Rightarrow> state \<Rightarrow> bool" ("_\<turnstile>init\<le>_" [51,51] 50) where |
117 definition |
117 "G\<turnstile>init\<le>n \<equiv> \<lambda>s. card (nyinitcls G s) \<le> n" |
118 init_le :: "prog \<Rightarrow> nat \<Rightarrow> state \<Rightarrow> bool" ("_\<turnstile>init\<le>_" [51,51] 50) |
|
119 where "G\<turnstile>init\<le>n = (\<lambda>s. card (nyinitcls G s) \<le> n)" |
118 |
120 |
119 lemma init_le_def2 [simp]: "(G\<turnstile>init\<le>n) s = (card (nyinitcls G s)\<le>n)" |
121 lemma init_le_def2 [simp]: "(G\<turnstile>init\<le>n) s = (card (nyinitcls G s)\<le>n)" |
120 apply (unfold init_le_def) |
122 apply (unfold init_le_def) |
121 apply auto |
123 apply auto |
122 done |
124 done |
130 apply (rule card_nyinitcls_bound) |
132 apply (rule card_nyinitcls_bound) |
131 done |
133 done |
132 |
134 |
133 section "Most General Triples and Formulas" |
135 section "Most General Triples and Formulas" |
134 |
136 |
135 definition remember_init_state :: "state assn" ("\<doteq>") where |
137 definition |
136 "\<doteq> \<equiv> \<lambda>Y s Z. s = Z" |
138 remember_init_state :: "state assn" ("\<doteq>") |
|
139 where "\<doteq> \<equiv> \<lambda>Y s Z. s = Z" |
137 |
140 |
138 lemma remember_init_state_def2 [simp]: "\<doteq> Y = op =" |
141 lemma remember_init_state_def2 [simp]: "\<doteq> Y = op =" |
139 apply (unfold remember_init_state_def) |
142 apply (unfold remember_init_state_def) |
140 apply (simp (no_asm)) |
143 apply (simp (no_asm)) |
141 done |
144 done |
142 |
145 |
143 consts |
146 definition |
144 |
|
145 MGF ::"[state assn, term, prog] \<Rightarrow> state triple" ("{_} _\<succ> {_\<rightarrow>}"[3,65,3]62) |
147 MGF ::"[state assn, term, prog] \<Rightarrow> state triple" ("{_} _\<succ> {_\<rightarrow>}"[3,65,3]62) |
146 MGFn::"[nat , term, prog] \<Rightarrow> state triple" ("{=:_} _\<succ> {_\<rightarrow>}"[3,65,3]62) |
148 where "{P} t\<succ> {G\<rightarrow>} = {P} t\<succ> {\<lambda>Y s' s. G\<turnstile>s \<midarrow>t\<succ>\<rightarrow> (Y,s')}" |
147 |
149 |
148 defs |
150 definition |
149 |
151 MGFn :: "[nat, term, prog] \<Rightarrow> state triple" ("{=:_} _\<succ> {_\<rightarrow>}"[3,65,3]62) |
150 |
152 where "{=:n} t\<succ> {G\<rightarrow>} = {\<doteq> \<and>. G\<turnstile>init\<le>n} t\<succ> {G\<rightarrow>}" |
151 MGF_def: |
|
152 "{P} t\<succ> {G\<rightarrow>} \<equiv> {P} t\<succ> {\<lambda>Y s' s. G\<turnstile>s \<midarrow>t\<succ>\<rightarrow> (Y,s')}" |
|
153 |
|
154 MGFn_def: |
|
155 "{=:n} t\<succ> {G\<rightarrow>} \<equiv> {\<doteq> \<and>. G\<turnstile>init\<le>n} t\<succ> {G\<rightarrow>}" |
|
156 |
153 |
157 (* unused *) |
154 (* unused *) |
158 lemma MGF_valid: "wf_prog G \<Longrightarrow> G,{}\<Turnstile>{\<doteq>} t\<succ> {G\<rightarrow>}" |
155 lemma MGF_valid: "wf_prog G \<Longrightarrow> G,{}\<Turnstile>{\<doteq>} t\<succ> {G\<rightarrow>}" |
159 apply (unfold MGF_def) |
156 apply (unfold MGF_def) |
160 apply (simp add: ax_valids_def triple_valid_def2) |
157 apply (simp add: ax_valids_def triple_valid_def2) |
572 come up with a proper loop invariant, which intuitively states that we are |
569 come up with a proper loop invariant, which intuitively states that we are |
573 currently inside the evaluation of the loop. To define such an invariant, we |
570 currently inside the evaluation of the loop. To define such an invariant, we |
574 unroll the loop in iterated evaluations of the expression and evaluations of |
571 unroll the loop in iterated evaluations of the expression and evaluations of |
575 the loop body. *} |
572 the loop body. *} |
576 |
573 |
577 definition unroll :: "prog \<Rightarrow> label \<Rightarrow> expr \<Rightarrow> stmt \<Rightarrow> (state \<times> state) set" where |
574 definition |
578 |
575 unroll :: "prog \<Rightarrow> label \<Rightarrow> expr \<Rightarrow> stmt \<Rightarrow> (state \<times> state) set" where |
579 "unroll G l e c \<equiv> {(s,t). \<exists> v s1 s2. |
576 "unroll G l e c = {(s,t). \<exists> v s1 s2. |
580 G\<turnstile>s \<midarrow>e-\<succ>v\<rightarrow> s1 \<and> the_Bool v \<and> normal s1 \<and> |
577 G\<turnstile>s \<midarrow>e-\<succ>v\<rightarrow> s1 \<and> the_Bool v \<and> normal s1 \<and> |
581 G\<turnstile>s1 \<midarrow>c\<rightarrow> s2 \<and> t=(abupd (absorb (Cont l)) s2)}" |
578 G\<turnstile>s1 \<midarrow>c\<rightarrow> s2 \<and> t=(abupd (absorb (Cont l)) s2)}" |
582 |
579 |
583 |
580 |
584 lemma unroll_while: |
581 lemma unroll_while: |