equal
deleted
inserted
replaced
217 lemma induct_lemma: |
217 lemma induct_lemma: |
218 "[| client_prog \<squnion> G \<in> Incr(lift(giv)); client_prog ok G; G \<in> program |] |
218 "[| client_prog \<squnion> G \<in> Incr(lift(giv)); client_prog ok G; G \<in> program |] |
219 ==> client_prog \<squnion> G \<in> |
219 ==> client_prog \<squnion> G \<in> |
220 {s \<in> state. s`rel = k & <k,h> \<in> strict_prefix(nat) |
220 {s \<in> state. s`rel = k & <k,h> \<in> strict_prefix(nat) |
221 & <h, s`giv> \<in> prefix(nat) & h pfixGe s`ask} |
221 & <h, s`giv> \<in> prefix(nat) & h pfixGe s`ask} |
222 LeadsTo {s \<in> state. <k, s`rel> \<in> strict_prefix(nat) |
222 \<longmapsto>w {s \<in> state. <k, s`rel> \<in> strict_prefix(nat) |
223 & <s`rel, s`giv> \<in> prefix(nat) & |
223 & <s`rel, s`giv> \<in> prefix(nat) & |
224 <h, s`giv> \<in> prefix(nat) & |
224 <h, s`giv> \<in> prefix(nat) & |
225 h pfixGe s`ask}" |
225 h pfixGe s`ask}" |
226 apply (rule single_LeadsTo_I) |
226 apply (rule single_LeadsTo_I) |
227 prefer 2 apply simp |
227 prefer 2 apply simp |
246 lemma rel_progress_lemma: |
246 lemma rel_progress_lemma: |
247 "[| client_prog \<squnion> G \<in> Incr(lift(giv)); client_prog ok G; G \<in> program |] |
247 "[| client_prog \<squnion> G \<in> Incr(lift(giv)); client_prog ok G; G \<in> program |] |
248 ==> client_prog \<squnion> G \<in> |
248 ==> client_prog \<squnion> G \<in> |
249 {s \<in> state. <s`rel, h> \<in> strict_prefix(nat) |
249 {s \<in> state. <s`rel, h> \<in> strict_prefix(nat) |
250 & <h, s`giv> \<in> prefix(nat) & h pfixGe s`ask} |
250 & <h, s`giv> \<in> prefix(nat) & h pfixGe s`ask} |
251 LeadsTo {s \<in> state. <h, s`rel> \<in> prefix(nat)}" |
251 \<longmapsto>w {s \<in> state. <h, s`rel> \<in> prefix(nat)}" |
252 apply (rule_tac f = "\<lambda>x \<in> state. length(h) #- length(x`rel)" |
252 apply (rule_tac f = "\<lambda>x \<in> state. length(h) #- length(x`rel)" |
253 in LessThan_induct) |
253 in LessThan_induct) |
254 apply (auto simp add: vimage_def) |
254 apply (auto simp add: vimage_def) |
255 prefer 2 apply (force simp add: lam_def) |
255 prefer 2 apply (force simp add: lam_def) |
256 apply (rule single_LeadsTo_I) |
256 apply (rule single_LeadsTo_I) |
274 |
274 |
275 lemma progress_lemma: |
275 lemma progress_lemma: |
276 "[| client_prog \<squnion> G \<in> Incr(lift(giv)); client_prog ok G; G \<in> program |] |
276 "[| client_prog \<squnion> G \<in> Incr(lift(giv)); client_prog ok G; G \<in> program |] |
277 ==> client_prog \<squnion> G |
277 ==> client_prog \<squnion> G |
278 \<in> {s \<in> state. <h, s`giv> \<in> prefix(nat) & h pfixGe s`ask} |
278 \<in> {s \<in> state. <h, s`giv> \<in> prefix(nat) & h pfixGe s`ask} |
279 LeadsTo {s \<in> state. <h, s`rel> \<in> prefix(nat)}" |
279 \<longmapsto>w {s \<in> state. <h, s`rel> \<in> prefix(nat)}" |
280 apply (rule client_prog_Join_Always_rel_le_giv [THEN Always_LeadsToI], |
280 apply (rule client_prog_Join_Always_rel_le_giv [THEN Always_LeadsToI], |
281 assumption) |
281 assumption) |
282 apply (force simp add: client_prog_ok_iff) |
282 apply (force simp add: client_prog_ok_iff) |
283 apply (rule LeadsTo_weaken_L) |
283 apply (rule LeadsTo_weaken_L) |
284 apply (rule LeadsTo_Un [OF rel_progress_lemma |
284 apply (rule LeadsTo_Un [OF rel_progress_lemma |
289 |
289 |
290 (*Progress property: all tokens that are given will be released*) |
290 (*Progress property: all tokens that are given will be released*) |
291 lemma client_prog_progress: |
291 lemma client_prog_progress: |
292 "client_prog \<in> Incr(lift(giv)) guarantees |
292 "client_prog \<in> Incr(lift(giv)) guarantees |
293 (\<Inter>h \<in> list(nat). {s \<in> state. <h, s`giv> \<in> prefix(nat) & |
293 (\<Inter>h \<in> list(nat). {s \<in> state. <h, s`giv> \<in> prefix(nat) & |
294 h pfixGe s`ask} LeadsTo {s \<in> state. <h, s`rel> \<in> prefix(nat)})" |
294 h pfixGe s`ask} \<longmapsto>w {s \<in> state. <h, s`rel> \<in> prefix(nat)})" |
295 apply (rule guaranteesI) |
295 apply (rule guaranteesI) |
296 apply (blast intro: progress_lemma, auto) |
296 apply (blast intro: progress_lemma, auto) |
297 done |
297 done |
298 |
298 |
299 lemma client_prog_Allowed: |
299 lemma client_prog_Allowed: |