85 by (ALLGOALS Fast_tac); (*Blast_tac: proof fails*) |
85 by (ALLGOALS Fast_tac); (*Blast_tac: proof fails*) |
86 qed "com_Unique"; |
86 qed "com_Unique"; |
87 |
87 |
88 |
88 |
89 (*Expression evaluation is functional, or deterministic*) |
89 (*Expression evaluation is functional, or deterministic*) |
90 goalw thy [Function_def] "Function eval"; |
90 Goalw [Function_def] "Function eval"; |
91 by (strip_tac 1); |
91 by (strip_tac 1); |
92 by (split_all_tac 1); |
92 by (split_all_tac 1); |
93 by (etac eval_induct 1); |
93 by (etac eval_induct 1); |
94 by (dtac com_Unique 4); |
94 by (dtac com_Unique 4); |
95 by (ALLGOALS (full_simp_tac (simpset() addsimps [Unique_def]))); |
95 by (ALLGOALS (full_simp_tac (simpset() addsimps [Unique_def]))); |
96 by (ALLGOALS Blast_tac); |
96 by (ALLGOALS Blast_tac); |
97 qed "Function_eval"; |
97 qed "Function_eval"; |
98 |
98 |
99 |
99 |
100 goal thy "!!x. (e,s) -|-> (v,s') ==> (e = N n) --> (v=n & s'=s)"; |
100 Goal "!!x. (e,s) -|-> (v,s') ==> (e = N n) --> (v=n & s'=s)"; |
101 by (etac eval_induct 1); |
101 by (etac eval_induct 1); |
102 by (ALLGOALS Asm_simp_tac); |
102 by (ALLGOALS Asm_simp_tac); |
103 val lemma = result(); |
103 val lemma = result(); |
104 bind_thm ("eval_N_E", refl RSN (2, lemma RS mp)); |
104 bind_thm ("eval_N_E", refl RSN (2, lemma RS mp)); |
105 |
105 |
106 AddSEs [eval_N_E]; |
106 AddSEs [eval_N_E]; |
107 |
107 |
108 |
108 |
109 (*This theorem says that "WHILE TRUE DO c" cannot terminate*) |
109 (*This theorem says that "WHILE TRUE DO c" cannot terminate*) |
110 goal thy "!!x. (c', s) -[eval]-> t ==> (c' = WHILE (N 0) DO c) --> False"; |
110 Goal "!!x. (c', s) -[eval]-> t ==> (c' = WHILE (N 0) DO c) --> False"; |
111 by (etac exec.induct 1); |
111 by (etac exec.induct 1); |
112 by Auto_tac; |
112 by Auto_tac; |
113 bind_thm ("while_true_E", refl RSN (2, result() RS mp)); |
113 bind_thm ("while_true_E", refl RSN (2, result() RS mp)); |
114 |
114 |
115 |
115 |
116 (** Equivalence of IF e THEN c;;(WHILE e DO c) ELSE SKIP and WHILE e DO c **) |
116 (** Equivalence of IF e THEN c;;(WHILE e DO c) ELSE SKIP and WHILE e DO c **) |
117 |
117 |
118 goal thy "!!x. (c',s) -[eval]-> t ==> \ |
118 Goal "!!x. (c',s) -[eval]-> t ==> \ |
119 \ (c' = WHILE e DO c) --> \ |
119 \ (c' = WHILE e DO c) --> \ |
120 \ (IF e THEN c;;c' ELSE SKIP, s) -[eval]-> t"; |
120 \ (IF e THEN c;;c' ELSE SKIP, s) -[eval]-> t"; |
121 by (etac exec.induct 1); |
121 by (etac exec.induct 1); |
122 by (ALLGOALS Asm_simp_tac); |
122 by (ALLGOALS Asm_simp_tac); |
123 by (ALLGOALS Blast_tac); |
123 by (ALLGOALS Blast_tac); |
124 bind_thm ("while_if1", refl RSN (2, result() RS mp)); |
124 bind_thm ("while_if1", refl RSN (2, result() RS mp)); |
125 |
125 |
126 |
126 |
127 goal thy "!!x. (c',s) -[eval]-> t ==> \ |
127 Goal "!!x. (c',s) -[eval]-> t ==> \ |
128 \ (c' = IF e THEN c;;(WHILE e DO c) ELSE SKIP) --> \ |
128 \ (c' = IF e THEN c;;(WHILE e DO c) ELSE SKIP) --> \ |
129 \ (WHILE e DO c, s) -[eval]-> t"; |
129 \ (WHILE e DO c, s) -[eval]-> t"; |
130 by (etac exec.induct 1); |
130 by (etac exec.induct 1); |
131 by (ALLGOALS Asm_simp_tac); |
131 by (ALLGOALS Asm_simp_tac); |
132 by (ALLGOALS Blast_tac); |
132 by (ALLGOALS Blast_tac); |
133 bind_thm ("while_if2", refl RSN (2, result() RS mp)); |
133 bind_thm ("while_if2", refl RSN (2, result() RS mp)); |
134 |
134 |
135 |
135 |
136 goal thy "((IF e THEN c;;(WHILE e DO c) ELSE SKIP, s) -[eval]-> t) = \ |
136 Goal "((IF e THEN c;;(WHILE e DO c) ELSE SKIP, s) -[eval]-> t) = \ |
137 \ ((WHILE e DO c, s) -[eval]-> t)"; |
137 \ ((WHILE e DO c, s) -[eval]-> t)"; |
138 by (blast_tac (claset() addIs [while_if1, while_if2]) 1); |
138 by (blast_tac (claset() addIs [while_if1, while_if2]) 1); |
139 qed "while_if"; |
139 qed "while_if"; |
140 |
140 |
141 |
141 |
142 |
142 |
143 (** Equivalence of (IF e THEN c1 ELSE c2);;c |
143 (** Equivalence of (IF e THEN c1 ELSE c2);;c |
144 and IF e THEN (c1;;c) ELSE (c2;;c) **) |
144 and IF e THEN (c1;;c) ELSE (c2;;c) **) |
145 |
145 |
146 goal thy "!!x. (c',s) -[eval]-> t ==> \ |
146 Goal "!!x. (c',s) -[eval]-> t ==> \ |
147 \ (c' = (IF e THEN c1 ELSE c2);;c) --> \ |
147 \ (c' = (IF e THEN c1 ELSE c2);;c) --> \ |
148 \ (IF e THEN (c1;;c) ELSE (c2;;c), s) -[eval]-> t"; |
148 \ (IF e THEN (c1;;c) ELSE (c2;;c), s) -[eval]-> t"; |
149 by (etac exec.induct 1); |
149 by (etac exec.induct 1); |
150 by (ALLGOALS Asm_simp_tac); |
150 by (ALLGOALS Asm_simp_tac); |
151 by (Blast_tac 1); |
151 by (Blast_tac 1); |
152 bind_thm ("if_semi1", refl RSN (2, result() RS mp)); |
152 bind_thm ("if_semi1", refl RSN (2, result() RS mp)); |
153 |
153 |
154 |
154 |
155 goal thy "!!x. (c',s) -[eval]-> t ==> \ |
155 Goal "!!x. (c',s) -[eval]-> t ==> \ |
156 \ (c' = IF e THEN (c1;;c) ELSE (c2;;c)) --> \ |
156 \ (c' = IF e THEN (c1;;c) ELSE (c2;;c)) --> \ |
157 \ ((IF e THEN c1 ELSE c2);;c, s) -[eval]-> t"; |
157 \ ((IF e THEN c1 ELSE c2);;c, s) -[eval]-> t"; |
158 by (etac exec.induct 1); |
158 by (etac exec.induct 1); |
159 by (ALLGOALS Asm_simp_tac); |
159 by (ALLGOALS Asm_simp_tac); |
160 by (ALLGOALS Blast_tac); |
160 by (ALLGOALS Blast_tac); |
161 bind_thm ("if_semi2", refl RSN (2, result() RS mp)); |
161 bind_thm ("if_semi2", refl RSN (2, result() RS mp)); |
162 |
162 |
163 |
163 |
164 goal thy "(((IF e THEN c1 ELSE c2);;c, s) -[eval]-> t) = \ |
164 Goal "(((IF e THEN c1 ELSE c2);;c, s) -[eval]-> t) = \ |
165 \ ((IF e THEN (c1;;c) ELSE (c2;;c), s) -[eval]-> t)"; |
165 \ ((IF e THEN (c1;;c) ELSE (c2;;c), s) -[eval]-> t)"; |
166 by (blast_tac (claset() addIs [if_semi1, if_semi2]) 1); |
166 by (blast_tac (claset() addIs [if_semi1, if_semi2]) 1); |
167 qed "if_semi"; |
167 qed "if_semi"; |
168 |
168 |
169 |
169 |
170 |
170 |
171 (** Equivalence of VALOF c1 RESULTIS (VALOF c2 RESULTIS e) |
171 (** Equivalence of VALOF c1 RESULTIS (VALOF c2 RESULTIS e) |
172 and VALOF c1;;c2 RESULTIS e |
172 and VALOF c1;;c2 RESULTIS e |
173 **) |
173 **) |
174 |
174 |
175 goal thy "!!x. (e',s) -|-> (v,s') ==> \ |
175 Goal "!!x. (e',s) -|-> (v,s') ==> \ |
176 \ (e' = VALOF c1 RESULTIS (VALOF c2 RESULTIS e)) --> \ |
176 \ (e' = VALOF c1 RESULTIS (VALOF c2 RESULTIS e)) --> \ |
177 \ (VALOF c1;;c2 RESULTIS e, s) -|-> (v,s')"; |
177 \ (VALOF c1;;c2 RESULTIS e, s) -|-> (v,s')"; |
178 by (etac eval_induct 1); |
178 by (etac eval_induct 1); |
179 by (ALLGOALS Asm_simp_tac); |
179 by (ALLGOALS Asm_simp_tac); |
180 by (Blast_tac 1); |
180 by (Blast_tac 1); |
181 bind_thm ("valof_valof1", refl RSN (2, result() RS mp)); |
181 bind_thm ("valof_valof1", refl RSN (2, result() RS mp)); |
182 |
182 |
183 |
183 |
184 goal thy "!!x. (e',s) -|-> (v,s') ==> \ |
184 Goal "!!x. (e',s) -|-> (v,s') ==> \ |
185 \ (e' = VALOF c1;;c2 RESULTIS e) --> \ |
185 \ (e' = VALOF c1;;c2 RESULTIS e) --> \ |
186 \ (VALOF c1 RESULTIS (VALOF c2 RESULTIS e), s) -|-> (v,s')"; |
186 \ (VALOF c1 RESULTIS (VALOF c2 RESULTIS e), s) -|-> (v,s')"; |
187 by (etac eval_induct 1); |
187 by (etac eval_induct 1); |
188 by (ALLGOALS Asm_simp_tac); |
188 by (ALLGOALS Asm_simp_tac); |
189 by (Blast_tac 1); |
189 by (Blast_tac 1); |
190 bind_thm ("valof_valof2", refl RSN (2, result() RS mp)); |
190 bind_thm ("valof_valof2", refl RSN (2, result() RS mp)); |
191 |
191 |
192 |
192 |
193 goal thy "((VALOF c1 RESULTIS (VALOF c2 RESULTIS e), s) -|-> (v,s')) = \ |
193 Goal "((VALOF c1 RESULTIS (VALOF c2 RESULTIS e), s) -|-> (v,s')) = \ |
194 \ ((VALOF c1;;c2 RESULTIS e, s) -|-> (v,s'))"; |
194 \ ((VALOF c1;;c2 RESULTIS e, s) -|-> (v,s'))"; |
195 by (blast_tac (claset() addIs [valof_valof1, valof_valof2]) 1); |
195 by (blast_tac (claset() addIs [valof_valof1, valof_valof2]) 1); |
196 qed "valof_valof"; |
196 qed "valof_valof"; |
197 |
197 |
198 |
198 |
199 (** Equivalence of VALOF SKIP RESULTIS e and e **) |
199 (** Equivalence of VALOF SKIP RESULTIS e and e **) |
200 |
200 |
201 goal thy "!!x. (e',s) -|-> (v,s') ==> \ |
201 Goal "!!x. (e',s) -|-> (v,s') ==> \ |
202 \ (e' = VALOF SKIP RESULTIS e) --> \ |
202 \ (e' = VALOF SKIP RESULTIS e) --> \ |
203 \ (e, s) -|-> (v,s')"; |
203 \ (e, s) -|-> (v,s')"; |
204 by (etac eval_induct 1); |
204 by (etac eval_induct 1); |
205 by (ALLGOALS Asm_simp_tac); |
205 by (ALLGOALS Asm_simp_tac); |
206 by (Blast_tac 1); |
206 by (Blast_tac 1); |
207 bind_thm ("valof_skip1", refl RSN (2, result() RS mp)); |
207 bind_thm ("valof_skip1", refl RSN (2, result() RS mp)); |
208 |
208 |
209 goal thy "!!x. (e,s) -|-> (v,s') ==> (VALOF SKIP RESULTIS e, s) -|-> (v,s')"; |
209 Goal "!!x. (e,s) -|-> (v,s') ==> (VALOF SKIP RESULTIS e, s) -|-> (v,s')"; |
210 by (Blast_tac 1); |
210 by (Blast_tac 1); |
211 qed "valof_skip2"; |
211 qed "valof_skip2"; |
212 |
212 |
213 goal thy "((VALOF SKIP RESULTIS e, s) -|-> (v,s')) = ((e, s) -|-> (v,s'))"; |
213 Goal "((VALOF SKIP RESULTIS e, s) -|-> (v,s')) = ((e, s) -|-> (v,s'))"; |
214 by (blast_tac (claset() addIs [valof_skip1, valof_skip2]) 1); |
214 by (blast_tac (claset() addIs [valof_skip1, valof_skip2]) 1); |
215 qed "valof_skip"; |
215 qed "valof_skip"; |
216 |
216 |
217 |
217 |
218 (** Equivalence of VALOF x:=e RESULTIS x and e **) |
218 (** Equivalence of VALOF x:=e RESULTIS x and e **) |
219 |
219 |
220 goal thy "!!x. (e',s) -|-> (v,s'') ==> \ |
220 Goal "!!x. (e',s) -|-> (v,s'') ==> \ |
221 \ (e' = VALOF x:=e RESULTIS X x) --> \ |
221 \ (e' = VALOF x:=e RESULTIS X x) --> \ |
222 \ (EX s'. (e, s) -|-> (v,s') & (s'' = s'[v/x]))"; |
222 \ (EX s'. (e, s) -|-> (v,s') & (s'' = s'[v/x]))"; |
223 by (etac eval_induct 1); |
223 by (etac eval_induct 1); |
224 by (ALLGOALS Asm_simp_tac); |
224 by (ALLGOALS Asm_simp_tac); |
225 by (thin_tac "?PP-->?QQ" 1); |
225 by (thin_tac "?PP-->?QQ" 1); |