16 stop :: "bool" --{*whether the lift is stopped at floor*} |
16 stop :: "bool" --{*whether the lift is stopped at floor*} |
17 req :: "int set" --{*for each floor, whether the lift is requested*} |
17 req :: "int set" --{*for each floor, whether the lift is requested*} |
18 up :: "bool" --{*current direction of movement*} |
18 up :: "bool" --{*current direction of movement*} |
19 move :: "bool" --{*whether moving takes precedence over opening*} |
19 move :: "bool" --{*whether moving takes precedence over opening*} |
20 |
20 |
21 consts |
21 axiomatization |
22 Min :: "int" --{*least and greatest floors*} |
22 Min :: "int" and --{*least and greatest floors*} |
23 Max :: "int" --{*least and greatest floors*} |
23 Max :: "int" --{*least and greatest floors*} |
24 |
24 where |
25 axioms |
|
26 Min_le_Max [iff]: "Min \<le> Max" |
25 Min_le_Max [iff]: "Min \<le> Max" |
27 |
26 |
28 constdefs |
|
29 |
27 |
30 --{*Abbreviations: the "always" part*} |
28 --{*Abbreviations: the "always" part*} |
31 |
29 |
|
30 definition |
32 above :: "state set" |
31 above :: "state set" |
33 "above == {s. \<exists>i. floor s < i & i \<le> Max & i \<in> req s}" |
32 where "above = {s. \<exists>i. floor s < i & i \<le> Max & i \<in> req s}" |
34 |
33 |
|
34 definition |
35 below :: "state set" |
35 below :: "state set" |
36 "below == {s. \<exists>i. Min \<le> i & i < floor s & i \<in> req s}" |
36 where "below = {s. \<exists>i. Min \<le> i & i < floor s & i \<in> req s}" |
37 |
37 |
|
38 definition |
38 queueing :: "state set" |
39 queueing :: "state set" |
39 "queueing == above \<union> below" |
40 where "queueing = above \<union> below" |
40 |
41 |
|
42 definition |
41 goingup :: "state set" |
43 goingup :: "state set" |
42 "goingup == above \<inter> ({s. up s} \<union> -below)" |
44 where "goingup = above \<inter> ({s. up s} \<union> -below)" |
43 |
45 |
|
46 definition |
44 goingdown :: "state set" |
47 goingdown :: "state set" |
45 "goingdown == below \<inter> ({s. ~ up s} \<union> -above)" |
48 where "goingdown = below \<inter> ({s. ~ up s} \<union> -above)" |
46 |
49 |
|
50 definition |
47 ready :: "state set" |
51 ready :: "state set" |
48 "ready == {s. stop s & ~ open s & move s}" |
52 where "ready = {s. stop s & ~ open s & move s}" |
49 |
53 |
50 --{*Further abbreviations*} |
54 --{*Further abbreviations*} |
51 |
55 |
|
56 definition |
52 moving :: "state set" |
57 moving :: "state set" |
53 "moving == {s. ~ stop s & ~ open s}" |
58 where "moving = {s. ~ stop s & ~ open s}" |
54 |
59 |
|
60 definition |
55 stopped :: "state set" |
61 stopped :: "state set" |
56 "stopped == {s. stop s & ~ open s & ~ move s}" |
62 where "stopped = {s. stop s & ~ open s & ~ move s}" |
57 |
63 |
|
64 definition |
58 opened :: "state set" |
65 opened :: "state set" |
59 "opened == {s. stop s & open s & move s}" |
66 where "opened = {s. stop s & open s & move s}" |
60 |
67 |
|
68 definition |
61 closed :: "state set" --{*but this is the same as ready!!*} |
69 closed :: "state set" --{*but this is the same as ready!!*} |
62 "closed == {s. stop s & ~ open s & move s}" |
70 where "closed = {s. stop s & ~ open s & move s}" |
63 |
71 |
|
72 definition |
64 atFloor :: "int => state set" |
73 atFloor :: "int => state set" |
65 "atFloor n == {s. floor s = n}" |
74 where "atFloor n = {s. floor s = n}" |
66 |
75 |
|
76 definition |
67 Req :: "int => state set" |
77 Req :: "int => state set" |
68 "Req n == {s. n \<in> req s}" |
78 where "Req n = {s. n \<in> req s}" |
69 |
79 |
70 |
80 |
71 |
81 |
72 --{*The program*} |
82 --{*The program*} |
73 |
83 |
|
84 definition |
74 request_act :: "(state*state) set" |
85 request_act :: "(state*state) set" |
75 "request_act == {(s,s'). s' = s (|stop:=True, move:=False|) |
86 where "request_act = {(s,s'). s' = s (|stop:=True, move:=False|) |
76 & ~ stop s & floor s \<in> req s}" |
87 & ~ stop s & floor s \<in> req s}" |
77 |
88 |
|
89 definition |
78 open_act :: "(state*state) set" |
90 open_act :: "(state*state) set" |
79 "open_act == |
91 where "open_act = |
80 {(s,s'). s' = s (|open :=True, |
92 {(s,s'). s' = s (|open :=True, |
81 req := req s - {floor s}, |
93 req := req s - {floor s}, |
82 move := True|) |
94 move := True|) |
83 & stop s & ~ open s & floor s \<in> req s |
95 & stop s & ~ open s & floor s \<in> req s |
84 & ~(move s & s \<in> queueing)}" |
96 & ~(move s & s \<in> queueing)}" |
85 |
97 |
|
98 definition |
86 close_act :: "(state*state) set" |
99 close_act :: "(state*state) set" |
87 "close_act == {(s,s'). s' = s (|open := False|) & open s}" |
100 where "close_act = {(s,s'). s' = s (|open := False|) & open s}" |
88 |
101 |
|
102 definition |
89 req_up :: "(state*state) set" |
103 req_up :: "(state*state) set" |
90 "req_up == |
104 where "req_up = |
91 {(s,s'). s' = s (|stop :=False, |
105 {(s,s'). s' = s (|stop :=False, |
92 floor := floor s + 1, |
106 floor := floor s + 1, |
93 up := True|) |
107 up := True|) |
94 & s \<in> (ready \<inter> goingup)}" |
108 & s \<in> (ready \<inter> goingup)}" |
95 |
109 |
|
110 definition |
96 req_down :: "(state*state) set" |
111 req_down :: "(state*state) set" |
97 "req_down == |
112 where "req_down = |
98 {(s,s'). s' = s (|stop :=False, |
113 {(s,s'). s' = s (|stop :=False, |
99 floor := floor s - 1, |
114 floor := floor s - 1, |
100 up := False|) |
115 up := False|) |
101 & s \<in> (ready \<inter> goingdown)}" |
116 & s \<in> (ready \<inter> goingdown)}" |
102 |
117 |
|
118 definition |
103 move_up :: "(state*state) set" |
119 move_up :: "(state*state) set" |
104 "move_up == |
120 where "move_up = |
105 {(s,s'). s' = s (|floor := floor s + 1|) |
121 {(s,s'). s' = s (|floor := floor s + 1|) |
106 & ~ stop s & up s & floor s \<notin> req s}" |
122 & ~ stop s & up s & floor s \<notin> req s}" |
107 |
123 |
|
124 definition |
108 move_down :: "(state*state) set" |
125 move_down :: "(state*state) set" |
109 "move_down == |
126 where "move_down = |
110 {(s,s'). s' = s (|floor := floor s - 1|) |
127 {(s,s'). s' = s (|floor := floor s - 1|) |
111 & ~ stop s & ~ up s & floor s \<notin> req s}" |
128 & ~ stop s & ~ up s & floor s \<notin> req s}" |
112 |
129 |
|
130 definition |
113 button_press :: "(state*state) set" |
131 button_press :: "(state*state) set" |
114 --{*This action is omitted from prior treatments, which therefore are |
132 --{*This action is omitted from prior treatments, which therefore are |
115 unrealistic: nobody asks the lift to do anything! But adding this |
133 unrealistic: nobody asks the lift to do anything! But adding this |
116 action invalidates many of the existing progress arguments: various |
134 action invalidates many of the existing progress arguments: various |
117 "ensures" properties fail. Maybe it should be constrained to only |
135 "ensures" properties fail. Maybe it should be constrained to only |
118 allow button presses in the current direction of travel, like in a |
136 allow button presses in the current direction of travel, like in a |
119 real lift.*} |
137 real lift.*} |
120 "button_press == |
138 where "button_press = |
121 {(s,s'). \<exists>n. s' = s (|req := insert n (req s)|) |
139 {(s,s'). \<exists>n. s' = s (|req := insert n (req s)|) |
122 & Min \<le> n & n \<le> Max}" |
140 & Min \<le> n & n \<le> Max}" |
123 |
141 |
124 |
142 |
|
143 definition |
125 Lift :: "state program" |
144 Lift :: "state program" |
126 --{*for the moment, we OMIT @{text button_press}*} |
145 --{*for the moment, we OMIT @{text button_press}*} |
127 "Lift == mk_total_program |
146 where "Lift = mk_total_program |
128 ({s. floor s = Min & ~ up s & move s & stop s & |
147 ({s. floor s = Min & ~ up s & move s & stop s & |
129 ~ open s & req s = {}}, |
148 ~ open s & req s = {}}, |
130 {request_act, open_act, close_act, |
149 {request_act, open_act, close_act, |
131 req_up, req_down, move_up, move_down}, |
150 req_up, req_down, move_up, move_down}, |
132 UNIV)" |
151 UNIV)" |
133 |
152 |
134 |
153 |
135 --{*Invariants*} |
154 --{*Invariants*} |
136 |
155 |
|
156 definition |
137 bounded :: "state set" |
157 bounded :: "state set" |
138 "bounded == {s. Min \<le> floor s & floor s \<le> Max}" |
158 where "bounded = {s. Min \<le> floor s & floor s \<le> Max}" |
139 |
159 |
|
160 definition |
140 open_stop :: "state set" |
161 open_stop :: "state set" |
141 "open_stop == {s. open s --> stop s}" |
162 where "open_stop = {s. open s --> stop s}" |
142 |
163 |
|
164 definition |
143 open_move :: "state set" |
165 open_move :: "state set" |
144 "open_move == {s. open s --> move s}" |
166 where "open_move = {s. open s --> move s}" |
145 |
167 |
|
168 definition |
146 stop_floor :: "state set" |
169 stop_floor :: "state set" |
147 "stop_floor == {s. stop s & ~ move s --> floor s \<in> req s}" |
170 where "stop_floor = {s. stop s & ~ move s --> floor s \<in> req s}" |
148 |
171 |
|
172 definition |
149 moving_up :: "state set" |
173 moving_up :: "state set" |
150 "moving_up == {s. ~ stop s & up s --> |
174 where "moving_up = {s. ~ stop s & up s --> |
151 (\<exists>f. floor s \<le> f & f \<le> Max & f \<in> req s)}" |
175 (\<exists>f. floor s \<le> f & f \<le> Max & f \<in> req s)}" |
152 |
176 |
|
177 definition |
153 moving_down :: "state set" |
178 moving_down :: "state set" |
154 "moving_down == {s. ~ stop s & ~ up s --> |
179 where "moving_down = {s. ~ stop s & ~ up s --> |
155 (\<exists>f. Min \<le> f & f \<le> floor s & f \<in> req s)}" |
180 (\<exists>f. Min \<le> f & f \<le> floor s & f \<in> req s)}" |
156 |
181 |
|
182 definition |
157 metric :: "[int,state] => int" |
183 metric :: "[int,state] => int" |
158 "metric == |
184 where "metric = |
159 %n s. if floor s < n then (if up s then n - floor s |
185 (%n s. if floor s < n then (if up s then n - floor s |
160 else (floor s - Min) + (n-Min)) |
186 else (floor s - Min) + (n-Min)) |
161 else |
187 else |
162 if n < floor s then (if up s then (Max - floor s) + (Max-n) |
188 if n < floor s then (if up s then (Max - floor s) + (Max-n) |
163 else floor s - n) |
189 else floor s - n) |
164 else 0" |
190 else 0)" |
165 |
191 |
166 locale Floor = |
192 locale Floor = |
167 fixes n |
193 fixes n |
168 assumes Min_le_n [iff]: "Min \<le> n" |
194 assumes Min_le_n [iff]: "Min \<le> n" |
169 and n_le_Max [iff]: "n \<le> Max" |
195 and n_le_Max [iff]: "n \<le> Max" |