author | paulson |
Mon, 11 Oct 1999 10:53:39 +0200 | |
changeset 7826 | c6a8b73b6c2a |
parent 7689 | affe0c2fdfbf |
child 7841 | 65d91d13fc13 |
permissions | -rw-r--r-- |
6828 | 1 |
(* Title: HOL/UNITY/Alloc |
2 |
ID: $Id$ |
|
3 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
|
4 |
Copyright 1998 University of Cambridge |
|
5 |
||
6 |
Specification of Chandy and Charpentier's Allocator |
|
7540 | 7 |
|
8 |
STOP USING o (COMPOSITION), since function application is naturally associative |
|
7689 | 9 |
|
10 |
guarantees_PLam_I looks wrong: refers to lift_prog |
|
6828 | 11 |
*) |
12 |
||
7399
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
13 |
|
7538 | 14 |
Goal "(ALL i: lessThan n. f i <= g i) --> sum f n <= sum g n"; |
15 |
by (induct_tac "n" 1); |
|
16 |
by Auto_tac; |
|
17 |
by (dres_inst_tac [("x","n")] bspec 1); |
|
18 |
by Auto_tac; |
|
19 |
by (arith_tac 1); |
|
20 |
qed_spec_mp "sum_mono"; |
|
21 |
||
7540 | 22 |
Goal "ALL xs. xs <= ys --> tokens xs <= tokens ys"; |
23 |
by (induct_tac "ys" 1); |
|
24 |
by (auto_tac (claset(), simpset() addsimps [prefix_Cons])); |
|
25 |
qed_spec_mp "tokens_mono_prefix"; |
|
26 |
||
27 |
Goalw [mono_def] "mono tokens"; |
|
28 |
by (blast_tac (claset() addIs [tokens_mono_prefix]) 1); |
|
29 |
qed "mono_tokens"; |
|
7399
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
30 |
|
6840 | 31 |
(*Generalized version allowing different clients*) |
32 |
Goal "[| Alloc : alloc_spec; \ |
|
33 |
\ Client : (lessThan Nclients) funcset client_spec; \ |
|
34 |
\ Network : network_spec |] \ |
|
35 |
\ ==> (extend sysOfAlloc Alloc) \ |
|
36 |
\ Join (extend sysOfClient (PLam (lessThan Nclients) Client)) \ |
|
37 |
\ Join Network : system_spec"; |
|
38 |
||
39 |
Goal "System : system_spec"; |
|
40 |
||
41 |
||
6828 | 42 |
Goalw [sysOfAlloc_def] "inj sysOfAlloc"; |
43 |
by (rtac injI 1); |
|
7347 | 44 |
by (auto_tac (claset() addSWrapper record_split_wrapper, simpset())); |
6828 | 45 |
qed "inj_sysOfAlloc"; |
46 |
||
47 |
Goalw [sysOfAlloc_def] "surj sysOfAlloc"; |
|
48 |
by (res_inst_tac [("f", "%s. ((| allocGiv = allocGiv s, \ |
|
49 |
\ allocAsk = allocAsk s, \ |
|
50 |
\ allocRel = allocRel s |), \ |
|
51 |
\ client s)")] surjI 1); |
|
7347 | 52 |
by (auto_tac (claset() addSWrapper record_split_wrapper, simpset())); |
6828 | 53 |
qed "surj_sysOfAlloc"; |
54 |
||
55 |
AddIffs [inj_sysOfAlloc, surj_sysOfAlloc]; |
|
56 |
||
7482 | 57 |
Goalw [good_map_def] "good_map sysOfAlloc"; |
58 |
by Auto_tac; |
|
59 |
qed "good_map_sysOfAlloc"; |
|
7689 | 60 |
Addsimps [good_map_sysOfAlloc]; |
7399
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
61 |
|
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
62 |
(*MUST BE AUTOMATED: even the statement of such results*) |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
63 |
Goal "!!s. inv sysOfAlloc s = \ |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
64 |
\ ((| allocGiv = allocGiv s, \ |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
65 |
\ allocAsk = allocAsk s, \ |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
66 |
\ allocRel = allocRel s|), \ |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
67 |
\ client s)"; |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
68 |
by (rtac (inj_sysOfAlloc RS inv_f_eq) 1); |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
69 |
by (auto_tac (claset() addSWrapper record_split_wrapper, |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
70 |
simpset() addsimps [sysOfAlloc_def])); |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
71 |
qed "inv_sysOfAlloc_eq"; |
7538 | 72 |
Addsimps [inv_sysOfAlloc_eq]; |
7399
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
73 |
|
7826
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
74 |
|
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
75 |
(*SHOULD NOT BE NECESSARY???????????????? |
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
76 |
Goal "!!z. (| allocGiv = allocGiv z, allocAsk = allocAsk z, \ |
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
77 |
\ allocRel = allocRel z |) = z"; |
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
78 |
by (auto_tac (claset() addSWrapper record_split_wrapper, |
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
79 |
simpset())); |
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
80 |
qed "allocState_eq"; |
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
81 |
Addsimps [allocState_eq]; |
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
82 |
????*) |
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
83 |
|
7365 | 84 |
(**SHOULD NOT BE NECESSARY: The various injections into the system |
85 |
state need to be treated symmetrically or done automatically*) |
|
7347 | 86 |
Goalw [sysOfClient_def] "inj sysOfClient"; |
87 |
by (rtac injI 1); |
|
88 |
by (auto_tac (claset() addSDs [inj_sysOfAlloc RS injD] |
|
89 |
addSWrapper record_split_wrapper, simpset())); |
|
90 |
qed "inj_sysOfClient"; |
|
91 |
||
92 |
Goalw [sysOfClient_def] "surj sysOfClient"; |
|
93 |
by (cut_facts_tac [surj_sysOfAlloc] 1); |
|
94 |
by (rewtac surj_def); |
|
95 |
by Auto_tac; |
|
96 |
by (Blast_tac 1); |
|
97 |
qed "surj_sysOfClient"; |
|
98 |
||
99 |
AddIffs [inj_sysOfClient, surj_sysOfClient]; |
|
100 |
||
7482 | 101 |
Goalw [good_map_def] "good_map sysOfClient"; |
102 |
by Auto_tac; |
|
103 |
qed "good_map_sysOfClient"; |
|
7689 | 104 |
Addsimps [good_map_sysOfClient]; |
6828 | 105 |
|
7347 | 106 |
(*MUST BE AUTOMATED: even the statement of such results*) |
107 |
Goal "!!s. inv sysOfClient s = \ |
|
108 |
\ (client s, \ |
|
109 |
\ (| allocGiv = allocGiv s, \ |
|
110 |
\ allocAsk = allocAsk s, \ |
|
111 |
\ allocRel = allocRel s|) )"; |
|
112 |
by (rtac (inj_sysOfClient RS inv_f_eq) 1); |
|
7399
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
113 |
by (auto_tac (claset() addSWrapper record_split_wrapper, |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
114 |
simpset() addsimps [sysOfAlloc_def, sysOfClient_def])); |
7365 | 115 |
qed "inv_sysOfClient_eq"; |
7689 | 116 |
Addsimps [inv_sysOfClient_eq]; |
6837 | 117 |
|
118 |
||
7365 | 119 |
Open_locale "System"; |
120 |
||
121 |
val Alloc = thm "Alloc"; |
|
122 |
val Client = thm "Client"; |
|
123 |
val Network = thm "Network"; |
|
124 |
val System_def = thm "System_def"; |
|
125 |
||
126 |
AddIffs [finite_lessThan]; |
|
127 |
||
128 |
(*Client : <unfolded specification> *) |
|
129 |
val Client_Spec = |
|
130 |
rewrite_rule [client_spec_def, client_increasing_def, |
|
131 |
client_bounded_def, client_progress_def] Client; |
|
132 |
||
133 |
Goal "Client : UNIV guarantees Increasing ask"; |
|
134 |
by (cut_facts_tac [Client_Spec] 1); |
|
135 |
by (asm_full_simp_tac (simpset() addsimps [guarantees_Int_right]) 1); |
|
136 |
qed "Client_Increasing_ask"; |
|
137 |
||
138 |
Goal "Client : UNIV guarantees Increasing rel"; |
|
139 |
by (cut_facts_tac [Client_Spec] 1); |
|
140 |
by (asm_full_simp_tac (simpset() addsimps [guarantees_Int_right]) 1); |
|
141 |
qed "Client_Increasing_rel"; |
|
142 |
||
143 |
AddIffs [Client_Increasing_ask, Client_Increasing_rel]; |
|
144 |
||
145 |
Goal "Client : UNIV guarantees Always {s. ALL elt : set (ask s). elt <= NbT}"; |
|
146 |
by (cut_facts_tac [Client_Spec] 1); |
|
147 |
by Auto_tac; |
|
148 |
qed "Client_Bounded"; |
|
149 |
||
150 |
(*Client_Progress is cumbersome to state*) |
|
151 |
val Client_Progress = Client_Spec RS IntD2; |
|
6828 | 152 |
|
153 |
||
7365 | 154 |
(*Network : <unfolded specification> *) |
155 |
val Network_Spec = |
|
156 |
rewrite_rule [network_spec_def, network_ask_def, |
|
157 |
network_giv_def, network_rel_def] Network; |
|
158 |
||
159 |
(*CANNOT use bind_thm: it puts the theorem into standard form, in effect |
|
160 |
exporting it from the locale*) |
|
7689 | 161 |
val Network_Ask = Network_Spec RS IntD1 RS IntD1 RS INT_D; |
7540 | 162 |
val Network_Giv = Network_Spec RS IntD1 RS IntD2 RS INT_D; |
7365 | 163 |
val Network_Rel = Network_Spec RS IntD2 RS INT_D; |
164 |
||
165 |
||
166 |
(*Alloc : <unfolded specification> *) |
|
167 |
val Alloc_Spec = |
|
168 |
rewrite_rule [alloc_spec_def, alloc_increasing_def, |
|
169 |
alloc_safety_def, alloc_progress_def] Alloc; |
|
170 |
||
7540 | 171 |
Goal "i < Nclients ==> Alloc : UNIV guarantees Increasing (sub i o allocGiv)"; |
7365 | 172 |
by (cut_facts_tac [Alloc_Spec] 1); |
173 |
by (asm_full_simp_tac (simpset() addsimps [guarantees_INT_right]) 1); |
|
174 |
qed "Alloc_Increasing"; |
|
175 |
||
176 |
val Alloc_Safety = Alloc_Spec RS IntD1 RS IntD2; |
|
177 |
val Alloc_Progress = (Alloc_Spec RS IntD2 |
|
178 |
|> simplify (simpset() addsimps [guarantees_INT_right])) |
|
179 |
RS bspec RS spec; |
|
180 |
||
181 |
||
7347 | 182 |
|
7365 | 183 |
(*Not sure what to say about the other components because they involve |
184 |
extend*) |
|
7399
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
185 |
Goalw [System_def] "Network <= System"; |
7365 | 186 |
by (blast_tac (claset() addIs [componentI]) 1); |
187 |
qed "Network_component_System"; |
|
188 |
||
7399
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
189 |
Goalw [System_def] "(extend sysOfAlloc Alloc) <= System"; |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
190 |
by (blast_tac (claset() addIs [componentI]) 1); |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
191 |
qed "Alloc_component_System"; |
7365 | 192 |
|
7399
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
193 |
AddIffs [Network_component_System, Alloc_component_System]; |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
194 |
|
7365 | 195 |
|
7826
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
196 |
fun alloc_export th = good_map_sysOfAlloc RS export th |> simplify (simpset()); |
7689 | 197 |
|
7826
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
198 |
fun client_export th = good_map_sysOfClient RS export th |> simplify (simpset()); |
7689 | 199 |
|
7365 | 200 |
(* F : UNIV guarantees Increasing func |
201 |
==> extend sysOfClient F : UNIV guarantees Increasing (func o client) *) |
|
7399
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
202 |
val extend_Client_guar_Increasing = |
7826
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
203 |
client_export extend_guar_Increasing; |
7365 | 204 |
|
7540 | 205 |
(*NEED AUTOMATIC PROPAGATION of Alloc_Increasing*) |
206 |
Goal "i < Nclients \ |
|
207 |
\ ==> extend sysOfAlloc Alloc : UNIV guarantees Increasing (sub i o allocGiv)"; |
|
208 |
by (dtac (Alloc_Increasing RS alloc_export extend_guar_Increasing) 1); |
|
209 |
by (auto_tac (claset(), simpset() addsimps [o_def])); |
|
210 |
qed "extend_Alloc_Increasing_allocGiv"; |
|
211 |
||
7365 | 212 |
|
7689 | 213 |
(*** Proof of the safety property (1) ***) |
7365 | 214 |
|
7689 | 215 |
(*safety (1), step 1*) |
7365 | 216 |
Goalw [System_def] |
217 |
"i < Nclients ==> System : Increasing (rel o sub i o client)"; |
|
7689 | 218 |
by (rtac (extend_Client_guar_Increasing RS guarantees_Join_I2 |
219 |
RS guaranteesD) 1); |
|
220 |
by (rtac (lift_prog_guar_Increasing RS guarantees_PLam_I) 1); |
|
221 |
(*gets Client_Increasing_rel from simpset*) |
|
222 |
by Auto_tac; |
|
7347 | 223 |
qed "System_Increasing_rel"; |
6828 | 224 |
|
225 |
||
7689 | 226 |
(*safety (1), step 2*) |
7365 | 227 |
Goal "i < Nclients ==> System : Increasing (sub i o allocRel)"; |
228 |
by (rtac Follows_Increasing1 1); |
|
229 |
by (blast_tac (claset() addIs [Network_Rel RS component_guaranteesD, |
|
7540 | 230 |
System_Increasing_rel]) 1); |
7365 | 231 |
qed "System_Increasing_allocRel"; |
6828 | 232 |
|
7826
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
233 |
|
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
234 |
|
7689 | 235 |
(*safety (1), step 3*) |
7399
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
236 |
Goal "System : Always {s. sum (%i. (tokens o sub i o allocGiv) s) Nclients \ |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
237 |
\ <= NbT + sum (%i. (tokens o sub i o allocRel) s) Nclients}"; |
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
238 |
by (res_inst_tac |
7537 | 239 |
[("X", "(INT i : lessThan Nclients. Increasing (sub i o allocRel))")] |
240 |
component_guaranteesD 1); |
|
7482 | 241 |
by (rtac Alloc_component_System 3); |
7537 | 242 |
by (force_tac (claset(), simpset() addsimps [System_Increasing_allocRel]) 2); |
7538 | 243 |
by (rtac (Alloc_Safety RS project_guarantees) 1); |
7826
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
244 |
(*1: Increasing precondition*) |
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
245 |
br (ballI RS projecting_INT) 1; |
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
246 |
by (rtac (alloc_export projecting_Increasing RS projecting_weaken) 1); |
7537 | 247 |
by Auto_tac; |
7826
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
248 |
by (asm_full_simp_tac (simpset() addsimps [o_def]) 1); |
7538 | 249 |
(*2: Always postcondition*) |
7826
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
250 |
by (rtac ((alloc_export extending_Always RS extending_weaken)) 1); |
c6a8b73b6c2a
working shapshot with "projecting" and "extending"
paulson
parents:
7689
diff
changeset
|
251 |
by Auto_tac; |
7538 | 252 |
by (asm_full_simp_tac |
253 |
(simpset() addsimps [alloc_export Collect_eq_extend_set RS sym]) 1); |
|
254 |
qed "System_sum_bounded"; |
|
7537 | 255 |
|
7689 | 256 |
(*safety (1), step 4*) |
7540 | 257 |
Goal "System : Always (INT i: lessThan Nclients. \ |
258 |
\ {s. (tokens o giv o sub i o client) s \ |
|
259 |
\ <= (tokens o sub i o allocGiv) s})"; |
|
260 |
by (auto_tac (claset(), |
|
261 |
simpset() delsimps [o_apply] |
|
262 |
addsimps [Always_INT_distrib])); |
|
263 |
by (rtac Follows_Bounded 1); |
|
264 |
by (simp_tac (HOL_ss addsimps [o_assoc RS sym]) 1); |
|
265 |
by (rtac (mono_tokens RS mono_Follows_o RS subsetD) 1); |
|
266 |
by (simp_tac (HOL_ss addsimps [o_assoc]) 1); |
|
267 |
by (blast_tac (claset() addIs [Network_Giv RS component_guaranteesD, |
|
268 |
extend_Alloc_Increasing_allocGiv RS component_guaranteesD]) 1); |
|
269 |
qed "System_Always_giv_le_allocGiv"; |
|
270 |
||
271 |
||
7689 | 272 |
(*safety (1), step 5*) |
7540 | 273 |
Goal "System : Always (INT i: lessThan Nclients. \ |
274 |
\ {s. (tokens o sub i o allocRel) s \ |
|
275 |
\ <= (tokens o rel o sub i o client) s})"; |
|
276 |
by (auto_tac (claset(), |
|
277 |
simpset() delsimps [o_apply] |
|
278 |
addsimps [Always_INT_distrib])); |
|
279 |
by (rtac Follows_Bounded 1); |
|
280 |
by (simp_tac (HOL_ss addsimps [o_assoc RS sym]) 1); |
|
281 |
by (rtac (mono_tokens RS mono_Follows_o RS subsetD) 1); |
|
282 |
by (simp_tac (HOL_ss addsimps [o_assoc]) 1); |
|
283 |
by (blast_tac (claset() addIs [Network_Rel RS component_guaranteesD, |
|
284 |
System_Increasing_rel]) 1); |
|
285 |
qed "System_Always_allocRel_le_rel"; |
|
286 |
||
287 |
||
7689 | 288 |
(*safety (1), step 6*) |
7540 | 289 |
Goal "System : Always {s. sum (%i. (tokens o giv o sub i o client)s) Nclients \ |
290 |
\ <= NbT + sum (%i. (tokens o rel o sub i o client)s) Nclients}"; |
|
291 |
by (rtac (Always_Int_rule [System_sum_bounded, System_Always_giv_le_allocGiv, |
|
292 |
System_Always_allocRel_le_rel] RS Always_weaken) 1); |
|
7538 | 293 |
by Auto_tac; |
7540 | 294 |
by (rtac (sum_mono RS order_trans) 1); |
295 |
by (dtac order_trans 2); |
|
296 |
by (rtac ([order_refl, sum_mono] MRS add_le_mono) 2); |
|
297 |
by (assume_tac 3); |
|
7482 | 298 |
by Auto_tac; |
7540 | 299 |
qed "System_safety"; |
7399
cf780c2bcccf
changed "component" infix in HOL/UNITY/Comp.thy to be overloaded <
paulson
parents:
7365
diff
changeset
|
300 |
|
7689 | 301 |
|
302 |
||
303 |
(*** Proof of the progress property (2) ***) |
|
304 |
||
305 |
(*we begin with proofs identical to System_Increasing_rel and |
|
306 |
System_Increasing_allocRel: tactics needed!*) |
|
307 |
||
308 |
(*progress (2), step 1*) |
|
309 |
Goalw [System_def] |
|
310 |
"i < Nclients ==> System : Increasing (ask o sub i o client)"; |
|
311 |
by (rtac (extend_Client_guar_Increasing RS guarantees_Join_I2 |
|
312 |
RS guaranteesD) 1); |
|
313 |
by (rtac (lift_prog_guar_Increasing RS guarantees_PLam_I) 1); |
|
314 |
by Auto_tac; |
|
315 |
qed "System_Increasing_ask"; |
|
316 |
||
317 |
(*progress (2), step 2*) |
|
318 |
Goal "i < Nclients ==> System : Increasing (sub i o allocAsk)"; |
|
319 |
by (rtac Follows_Increasing1 1); |
|
320 |
by (blast_tac (claset() addIs [Network_Ask RS component_guaranteesD, |
|
321 |
System_Increasing_ask]) 1); |
|
322 |
qed "System_Increasing_allocAsk"; |
|
323 |
||
324 |
(*progress (2), step 3*) |
|
325 |
(*All this trouble just to lift "Client_Bounded" through two extemd ops*) |
|
326 |
Goalw [System_def] |
|
327 |
"i < Nclients \ |
|
328 |
\ ==> System : Always \ |
|
329 |
\ {s. ALL elt : set ((ask o sub i o client) s). elt <= NbT}"; |
|
330 |
by (rtac (lift_prog_guar_Always RS |
|
331 |
guarantees_PLam_I RS client_export extend_guar_Always RS |
|
332 |
guarantees_Join_I2 RS guaranteesD RS Always_weaken) 1); |
|
333 |
by (stac Always_UNIV_eq 1 THEN rtac Client_Bounded 1); |
|
334 |
by (auto_tac(claset(), |
|
335 |
simpset() addsimps [Collect_eq_lift_set RS sym, |
|
336 |
client_export Collect_eq_extend_set RS sym])); |
|
337 |
qed "System_Bounded"; |