146 |
146 |
147 lemma Mutex_in_program [simp,TC]: "Mutex \<in> program" |
147 lemma Mutex_in_program [simp,TC]: "Mutex \<in> program" |
148 by (simp add: Mutex_def) |
148 by (simp add: Mutex_def) |
149 |
149 |
150 |
150 |
151 method_setup constrains = {* |
|
152 Method.ctxt_args (fn ctxt => |
|
153 Method.METHOD (fn facts => |
|
154 gen_constrains_tac (local_clasimpset_of ctxt) 1)) *} |
|
155 "for proving safety properties" |
|
156 |
|
157 |
|
158 declare Mutex_def [THEN def_prg_Init, simp] |
151 declare Mutex_def [THEN def_prg_Init, simp] |
159 ML |
152 ML |
160 {* |
153 {* |
161 program_defs_ref := [thm"Mutex_def"] |
154 program_defs_ref := [thm"Mutex_def"] |
162 *} |
155 *} |
189 declare IV_def [THEN def_set_simp, simp] |
182 declare IV_def [THEN def_set_simp, simp] |
190 declare bad_IU_def [THEN def_set_simp, simp] |
183 declare bad_IU_def [THEN def_set_simp, simp] |
191 |
184 |
192 lemma IU: "Mutex \<in> Always(IU)" |
185 lemma IU: "Mutex \<in> Always(IU)" |
193 apply (rule AlwaysI, force) |
186 apply (rule AlwaysI, force) |
194 apply (unfold Mutex_def, constrains, auto) |
187 apply (unfold Mutex_def, safety, auto) |
195 done |
188 done |
196 |
189 |
197 lemma IV: "Mutex \<in> Always(IV)" |
190 lemma IV: "Mutex \<in> Always(IV)" |
198 apply (rule AlwaysI, force) |
191 apply (rule AlwaysI, force) |
199 apply (unfold Mutex_def, constrains) |
192 apply (unfold Mutex_def, safety) |
200 done |
193 done |
201 |
194 |
202 (*The safety property: mutual exclusion*) |
195 (*The safety property: mutual exclusion*) |
203 lemma mutual_exclusion: "Mutex \<in> Always({s \<in> state. ~(s`m = #3 & s`n = #3)})" |
196 lemma mutual_exclusion: "Mutex \<in> Always({s \<in> state. ~(s`m = #3 & s`n = #3)})" |
204 apply (rule Always_weaken) |
197 apply (rule Always_weaken) |
212 apply (drule_tac [2] j = x in zle_zless_trans, auto) |
205 apply (drule_tac [2] j = x in zle_zless_trans, auto) |
213 done |
206 done |
214 |
207 |
215 lemma "Mutex \<in> Always(bad_IU)" |
208 lemma "Mutex \<in> Always(bad_IU)" |
216 apply (rule AlwaysI, force) |
209 apply (rule AlwaysI, force) |
217 apply (unfold Mutex_def, constrains, auto) |
210 apply (unfold Mutex_def, safety, auto) |
218 apply (subgoal_tac "#1 $<= #3") |
211 apply (subgoal_tac "#1 $<= #3") |
219 apply (drule_tac x = "#1" and y = "#3" in zle_trans, auto) |
212 apply (drule_tac x = "#1" and y = "#3" in zle_trans, auto) |
220 apply (simp (no_asm) add: not_zless_iff_zle [THEN iff_sym]) |
213 apply (simp (no_asm) add: not_zless_iff_zle [THEN iff_sym]) |
221 apply auto |
214 apply auto |
222 (*Resulting state: n=1, p=false, m=4, u=false. |
215 (*Resulting state: n=1, p=false, m=4, u=false. |
227 |
220 |
228 |
221 |
229 (*** Progress for U ***) |
222 (*** Progress for U ***) |
230 |
223 |
231 lemma U_F0: "Mutex \<in> {s \<in> state. s`m=#2} Unless {s \<in> state. s`m=#3}" |
224 lemma U_F0: "Mutex \<in> {s \<in> state. s`m=#2} Unless {s \<in> state. s`m=#3}" |
232 by (unfold Unless_def Mutex_def, constrains) |
225 by (unfold Unless_def Mutex_def, safety) |
233 |
226 |
234 lemma U_F1: |
227 lemma U_F1: |
235 "Mutex \<in> {s \<in> state. s`m=#1} LeadsTo {s \<in> state. s`p = s`v & s`m = #2}" |
228 "Mutex \<in> {s \<in> state. s`m=#1} LeadsTo {s \<in> state. s`p = s`v & s`m = #2}" |
236 by (unfold Mutex_def, ensures_tac U1) |
229 by (unfold Mutex_def, ensures_tac U1) |
237 |
230 |
279 |
272 |
280 |
273 |
281 (*** Progress for V ***) |
274 (*** Progress for V ***) |
282 |
275 |
283 lemma V_F0: "Mutex \<in> {s \<in> state. s`n=#2} Unless {s \<in> state. s`n=#3}" |
276 lemma V_F0: "Mutex \<in> {s \<in> state. s`n=#2} Unless {s \<in> state. s`n=#3}" |
284 by (unfold Unless_def Mutex_def, constrains) |
277 by (unfold Unless_def Mutex_def, safety) |
285 |
278 |
286 lemma V_F1: "Mutex \<in> {s \<in> state. s`n=#1} LeadsTo {s \<in> state. s`p = not(s`u) & s`n = #2}" |
279 lemma V_F1: "Mutex \<in> {s \<in> state. s`n=#1} LeadsTo {s \<in> state. s`p = not(s`u) & s`n = #2}" |
287 by (unfold Mutex_def, ensures_tac "V1") |
280 by (unfold Mutex_def, ensures_tac "V1") |
288 |
281 |
289 lemma V_F2: "Mutex \<in> {s \<in> state. s`p=1 & s`n = #2} LeadsTo {s \<in> state. s`n = #3}" |
282 lemma V_F2: "Mutex \<in> {s \<in> state. s`p=1 & s`n = #2} LeadsTo {s \<in> state. s`n = #3}" |