author | paulson |
Thu, 22 Jun 2000 11:35:28 +0200 | |
changeset 9105 | d9257992b845 |
parent 9027 | daeccd9f885f |
child 9403 | aad13b59b8d9 |
permissions | -rw-r--r-- |
9027 | 1 |
(* Title: HOL/UNITY/AllocImpl |
2 |
ID: $Id$ |
|
3 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
|
4 |
Copyright 1998 University of Cambridge |
|
5 |
||
6 |
Implementation of a multiple-client allocator from a single-client allocator |
|
7 |
||
8 |
add_path "../Induct"; |
|
9 |
with_path "../Induct" time_use_thy "AllocImpl"; |
|
10 |
*) |
|
11 |
||
12 |
AllocImpl = AllocBase + Follows + PPROD + |
|
13 |
||
14 |
||
15 |
(** State definitions. OUTPUT variables are locals **) |
|
16 |
||
17 |
(*Type variable 'b is the type of items being merged*) |
|
18 |
record 'b merge = |
|
19 |
In :: nat => 'b list (*merge's INPUT histories: streams to merge*) |
|
20 |
Out :: 'b list (*merge's OUTPUT history: merged items*) |
|
21 |
iOut :: nat list (*merge's OUTPUT history: origins of merged items*) |
|
22 |
||
23 |
record ('a,'b) merge_u = |
|
24 |
'b merge + |
|
25 |
extra :: 'a (*dummy field for new variables*) |
|
26 |
||
27 |
constdefs |
|
28 |
non_extra :: ('a,'b) merge_u => 'b merge |
|
29 |
"non_extra s == (|In = In s, Out = Out s, iOut = iOut s|)" |
|
30 |
||
31 |
record 'b distr = |
|
32 |
In :: 'b list (*items to distribute*) |
|
33 |
iIn :: nat list (*destinations of items to distribute*) |
|
34 |
Out :: nat => 'b list (*distributed items*) |
|
35 |
||
36 |
record ('a,'b) distr_u = |
|
37 |
'b distr + |
|
38 |
extra :: 'a (*dummy field for new variables*) |
|
39 |
||
40 |
record allocState = |
|
41 |
giv :: nat list (*OUTPUT history: source of tokens*) |
|
42 |
ask :: nat list (*INPUT: tokens requested from allocator*) |
|
43 |
rel :: nat list (*INPUT: tokens released to allocator*) |
|
44 |
||
45 |
record 'a allocState_u = |
|
46 |
allocState + |
|
47 |
extra :: 'a (*dummy field for new variables*) |
|
48 |
||
49 |
record 'a systemState = |
|
50 |
allocState + |
|
51 |
mergeRel :: nat merge |
|
52 |
mergeAsk :: nat merge |
|
53 |
distr :: nat distr |
|
54 |
extra :: 'a (*dummy field for new variables*) |
|
55 |
||
56 |
||
57 |
constdefs |
|
58 |
||
9105
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
59 |
(** Merge specification (the number of inputs is Nclients) ***) |
9027 | 60 |
|
61 |
(*spec (10)*) |
|
62 |
merge_increasing :: ('a,'b) merge_u program set |
|
63 |
"merge_increasing == |
|
64 |
UNIV guarantees[funPair merge.Out merge.iOut] |
|
65 |
(Increasing merge.Out) Int (Increasing merge.iOut)" |
|
66 |
||
67 |
(*spec (11)*) |
|
68 |
merge_eqOut :: ('a,'b) merge_u program set |
|
69 |
"merge_eqOut == |
|
70 |
UNIV guarantees[funPair merge.Out merge.iOut] |
|
71 |
Always {s. length (merge.Out s) = length (merge.iOut s)}" |
|
72 |
||
73 |
(*spec (12)*) |
|
74 |
merge_bounded :: ('a,'b) merge_u program set |
|
75 |
"merge_bounded == |
|
76 |
UNIV guarantees[merge.iOut] |
|
9105
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
77 |
Always {s. ALL elt : set (merge.iOut s). elt < Nclients}" |
9027 | 78 |
|
79 |
(*spec (13)*) |
|
80 |
merge_follows :: ('a,'b) merge_u program set |
|
81 |
"merge_follows == |
|
82 |
(INT i : lessThan Nclients. Increasing (sub i o merge.In)) |
|
83 |
guarantees[funPair merge.Out merge.iOut] |
|
84 |
(INT i : lessThan Nclients. |
|
85 |
(%s. sublist (merge.Out s) |
|
9105
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
86 |
{k. k < size(merge.iOut s) & merge.iOut s! k = i}) |
9027 | 87 |
Fols (sub i o merge.In))" |
88 |
||
89 |
(*spec: preserves part*) |
|
90 |
merge_preserves :: ('a,'b) merge_u program set |
|
91 |
"merge_preserves == preserves (funPair merge.In merge_u.extra)" |
|
92 |
||
93 |
merge_spec :: ('a,'b) merge_u program set |
|
94 |
"merge_spec == merge_increasing Int merge_eqOut Int merge_bounded Int |
|
95 |
merge_follows Int merge_preserves" |
|
96 |
||
9105
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
97 |
(** Distributor specification (the number of outputs is Nclients) ***) |
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
98 |
|
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
99 |
(*spec (14)*) |
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
100 |
distr_follows :: ('a,'b) distr_u program set |
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
101 |
"distr_follows == |
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
102 |
Increasing distr.In Int Increasing distr.iIn Int |
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
103 |
Always {s. ALL elt : set (distr.iIn s). elt < Nclients} |
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
104 |
guarantees[distr.Out] |
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
105 |
(INT i : lessThan Nclients. |
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
106 |
(sub i o distr.Out) Fols |
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
107 |
(%s. sublist (distr.In s) |
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
108 |
{k. k < size(distr.iIn s) & distr.iIn s ! k = i}))" |
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
109 |
|
d9257992b845
fixed the merge spec (NbT -> Nclients) and added the distributor spec
paulson
parents:
9027
diff
changeset
|
110 |
|
9027 | 111 |
(** Single-client allocator specification (required) ***) |
112 |
||
113 |
(*spec (18)*) |
|
114 |
alloc_increasing :: 'a allocState_u program set |
|
115 |
"alloc_increasing == UNIV guarantees[giv] Increasing giv" |
|
116 |
||
117 |
(*spec (19)*) |
|
118 |
alloc_safety :: 'a allocState_u program set |
|
119 |
"alloc_safety == |
|
120 |
Increasing rel |
|
121 |
guarantees[giv] Always {s. tokens (giv s) <= NbT + tokens (rel s)}" |
|
122 |
||
123 |
(*spec (20)*) |
|
124 |
alloc_progress :: 'a allocState_u program set |
|
125 |
"alloc_progress == |
|
126 |
Increasing ask Int Increasing rel Int |
|
127 |
Always {s. ALL elt : set (ask s). elt <= NbT} |
|
128 |
Int |
|
129 |
(INT h. {s. h <= giv s & h pfixGe (ask s)} |
|
130 |
LeadsTo |
|
131 |
{s. tokens h <= tokens (rel s)}) |
|
132 |
guarantees[giv] |
|
133 |
(INT h. {s. h <= ask s} LeadsTo {s. h pfixLe giv s})" |
|
134 |
||
135 |
(*spec: preserves part*) |
|
136 |
alloc_preserves :: 'a allocState_u program set |
|
137 |
"alloc_preserves == preserves (funPair rel |
|
138 |
(funPair ask allocState_u.extra))" |
|
139 |
||
140 |
alloc_spec :: 'a allocState_u program set |
|
141 |
"alloc_spec == alloc_increasing Int alloc_safety Int alloc_progress Int |
|
142 |
alloc_preserves" |
|
143 |
||
144 |
(**** |
|
145 |
(** Network specification ***) |
|
146 |
||
147 |
(*spec (9.1)*) |
|
148 |
network_ask :: 'a systemState program set |
|
149 |
"network_ask == INT i : lessThan Nclients. |
|
150 |
Increasing (ask o sub i o client) |
|
151 |
guarantees[ask] |
|
152 |
(ask Fols (ask o sub i o client))" |
|
153 |
||
154 |
(*spec (9.2)*) |
|
155 |
network_giv :: 'a systemState program set |
|
156 |
"network_giv == INT i : lessThan Nclients. |
|
157 |
Increasing giv |
|
158 |
guarantees[giv o sub i o client] |
|
159 |
((giv o sub i o client) Fols giv )" |
|
160 |
||
161 |
(*spec (9.3)*) |
|
162 |
network_rel :: 'a systemState program set |
|
163 |
"network_rel == INT i : lessThan Nclients. |
|
164 |
Increasing (rel o sub i o client) |
|
165 |
guarantees[rel] |
|
166 |
(rel Fols (rel o sub i o client))" |
|
167 |
||
168 |
(*spec: preserves part*) |
|
169 |
network_preserves :: 'a systemState program set |
|
170 |
"network_preserves == preserves giv Int |
|
171 |
(INT i : lessThan Nclients. |
|
172 |
preserves (funPair rel ask o sub i o client))" |
|
173 |
||
174 |
network_spec :: 'a systemState program set |
|
175 |
"network_spec == network_ask Int network_giv Int |
|
176 |
network_rel Int network_preserves" |
|
177 |
||
178 |
||
179 |
(** State mappings **) |
|
180 |
sysOfAlloc :: "((nat => merge) * 'a) allocState_u => 'a systemState" |
|
181 |
"sysOfAlloc == %s. let (cl,xtr) = allocState_u.extra s |
|
182 |
in (| giv = giv s, |
|
183 |
ask = ask s, |
|
184 |
rel = rel s, |
|
185 |
client = cl, |
|
186 |
extra = xtr|)" |
|
187 |
||
188 |
||
189 |
sysOfClient :: "(nat => merge) * 'a allocState_u => 'a systemState" |
|
190 |
"sysOfClient == %(cl,al). (| giv = giv al, |
|
191 |
ask = ask al, |
|
192 |
rel = rel al, |
|
193 |
client = cl, |
|
194 |
systemState.extra = allocState_u.extra al|)" |
|
195 |
****) |
|
196 |
||
197 |
consts |
|
198 |
Alloc :: 'a allocState_u program |
|
199 |
Merge :: ('a,'b) merge_u program |
|
200 |
(* |
|
201 |
Network :: 'a systemState program |
|
202 |
System :: 'a systemState program |
|
203 |
*) |
|
204 |
||
205 |
rules |
|
206 |
Alloc "Alloc : alloc_spec" |
|
207 |
Merge "Merge : merge_spec" |
|
208 |
(** Network "Network : network_spec"**) |
|
209 |
||
210 |
||
211 |
||
212 |
(** |
|
213 |
defs |
|
214 |
System_def |
|
215 |
"System == rename sysOfAlloc Alloc Join Network Join |
|
216 |
(rename sysOfMerge |
|
217 |
(plam x: lessThan Nclients. rename merge_map Merge))" |
|
218 |
**) |
|
219 |
||
220 |
||
221 |
end |