19 by (hyp_subst_tac 1); |
19 by (hyp_subst_tac 1); |
20 by (bound_hyp_subst_tac 1); |
20 by (bound_hyp_subst_tac 1); |
21 |
21 |
22 Here hyp_subst_tac goes wrong; harder still to prove P(f(f(a))) & P(f(a)) |
22 Here hyp_subst_tac goes wrong; harder still to prove P(f(f(a))) & P(f(a)) |
23 goal thy "P(a) --> (EX y. a=y --> P(f(a)))"; |
23 goal thy "P(a) --> (EX y. a=y --> P(f(a)))"; |
|
24 |
|
25 goal thy "!!x. [| Q(x,h1); P(a,h2); R(x,y,h3); R(y,z,h4); x=f(y); \ |
|
26 \ P(x,h5); P(y,h6); K(x,h7) |] ==> Q(x,c)"; |
|
27 by (blast_hyp_subst_tac (ref true) 1); |
24 *) |
28 *) |
25 |
29 |
26 signature HYPSUBST_DATA = |
30 signature HYPSUBST_DATA = |
27 sig |
31 sig |
28 structure Simplifier : SIMPLIFIER |
32 structure Simplifier : SIMPLIFIER |
|
33 val dest_Trueprop : term -> term |
29 val dest_eq : term -> term*term*typ |
34 val dest_eq : term -> term*term*typ |
|
35 val dest_imp : term -> term*term |
30 val eq_reflection : thm (* a=b ==> a==b *) |
36 val eq_reflection : thm (* a=b ==> a==b *) |
31 val imp_intr : thm (* (P ==> Q) ==> P-->Q *) |
37 val imp_intr : thm (* (P ==> Q) ==> P-->Q *) |
32 val rev_mp : thm (* [| P; P-->Q |] ==> Q *) |
38 val rev_mp : thm (* [| P; P-->Q |] ==> Q *) |
33 val subst : thm (* [| a=b; P(a) |] ==> P(b) *) |
39 val subst : thm (* [| a=b; P(a) |] ==> P(b) *) |
34 val sym : thm (* a=b ==> b=a *) |
40 val sym : thm (* a=b ==> b=a *) |
35 val thin_refl : thm (* [|x=x; PROP W|] ==> PROP W *) |
41 val thin_refl : thm (* [|x=x; PROP W|] ==> PROP W *) |
36 end; |
42 end; |
37 |
43 |
38 |
44 |
39 signature HYPSUBST = |
45 signature HYPSUBST = |
40 sig |
46 sig |
41 val bound_hyp_subst_tac : int -> tactic |
47 val bound_hyp_subst_tac : int -> tactic |
42 val hyp_subst_tac : int -> tactic |
48 val hyp_subst_tac : int -> tactic |
|
49 val blast_hyp_subst_tac : bool ref -> int -> tactic |
43 (*exported purely for debugging purposes*) |
50 (*exported purely for debugging purposes*) |
44 val gen_hyp_subst_tac : bool -> int -> tactic |
51 val gen_hyp_subst_tac : bool -> int -> tactic |
45 val vars_gen_hyp_subst_tac : bool -> int -> tactic |
52 val vars_gen_hyp_subst_tac : bool -> int -> tactic |
46 val eq_var : bool -> bool -> term -> int * bool |
53 val eq_var : bool -> bool -> term -> int * bool |
47 val inspect_pair : bool -> bool -> term * term * typ -> bool |
54 val inspect_pair : bool -> bool -> term * term * typ -> bool |
107 (*Locates a substitutable variable on the left (resp. right) of an equality |
112 (*Locates a substitutable variable on the left (resp. right) of an equality |
108 assumption. Returns the number of intervening assumptions. *) |
113 assumption. Returns the number of intervening assumptions. *) |
109 fun eq_var bnd novars = |
114 fun eq_var bnd novars = |
110 let fun eq_var_aux k (Const("all",_) $ Abs(_,_,t)) = eq_var_aux k t |
115 let fun eq_var_aux k (Const("all",_) $ Abs(_,_,t)) = eq_var_aux k t |
111 | eq_var_aux k (Const("==>",_) $ A $ B) = |
116 | eq_var_aux k (Const("==>",_) $ A $ B) = |
112 ((k, inspect_pair bnd novars (dest_eq A)) |
117 ((k, inspect_pair bnd novars |
|
118 (Data.dest_eq (Data.dest_Trueprop A))) |
113 (*Exception comes from inspect_pair or dest_eq*) |
119 (*Exception comes from inspect_pair or dest_eq*) |
114 handle Match => eq_var_aux (k+1) B) |
120 handle _ => eq_var_aux (k+1) B) |
115 | eq_var_aux k _ = raise EQ_VAR |
121 | eq_var_aux k _ = raise EQ_VAR |
116 in eq_var_aux 0 end; |
122 in eq_var_aux 0 end; |
117 |
123 |
118 (*We do not try to delete ALL equality assumptions at once. But |
124 (*We do not try to delete ALL equality assumptions at once. But |
119 it is easy to handle several consecutive equality assumptions in a row. |
125 it is easy to handle several consecutive equality assumptions in a row. |
121 since e.g. z=f(x); x=z changes to z=f(x); x=f(x) and the second equality |
127 since e.g. z=f(x); x=z changes to z=f(x); x=f(x) and the second equality |
122 must NOT be deleted. Tactic must rotate or delete m assumptions. |
128 must NOT be deleted. Tactic must rotate or delete m assumptions. |
123 *) |
129 *) |
124 fun thin_leading_eqs_tac bnd m = SUBGOAL (fn (Bi,i) => |
130 fun thin_leading_eqs_tac bnd m = SUBGOAL (fn (Bi,i) => |
125 let fun count [] = 0 |
131 let fun count [] = 0 |
126 | count (A::Bs) = ((inspect_pair bnd true (dest_eq A); |
132 | count (A::Bs) = ((inspect_pair bnd true |
|
133 (Data.dest_eq (Data.dest_Trueprop A)); |
127 1 + count Bs) |
134 1 + count Bs) |
128 handle Match => 0) |
135 handle _ => 0) |
129 val j = Int.min(m, count (Logic.strip_assums_hyp Bi)) |
136 val j = Int.min(m, count (Logic.strip_assums_hyp Bi)) |
130 in REPEAT_DETERM_N j (etac thin_rl i) THEN rotate_tac (m-j) i |
137 in REPEAT_DETERM_N j (etac thin_rl i) THEN rotate_tac (m-j) i |
131 end); |
138 end); |
132 |
139 |
133 (*For the simpset. Adds ALL suitable equalities, even if not first! |
140 (*For the simpset. Adds ALL suitable equalities, even if not first! |
134 No vars are allowed here, as simpsets are built from meta-assumptions*) |
141 No vars are allowed here, as simpsets are built from meta-assumptions*) |
135 fun mk_eqs th = |
142 fun mk_eqs th = |
136 [ if inspect_pair false false (Data.dest_eq (#prop (rep_thm th))) |
143 [ if inspect_pair false false (Data.dest_eq |
|
144 (Data.dest_Trueprop (#prop (rep_thm th)))) |
137 then th RS Data.eq_reflection |
145 then th RS Data.eq_reflection |
138 else symmetric(th RS Data.eq_reflection) (*reorient*) ] |
146 else symmetric(th RS Data.eq_reflection) (*reorient*) ] |
139 handle Match => []; (*Exception comes from inspect_pair or dest_eq*) |
147 handle _ => []; (*Exception comes from inspect_pair or dest_eq*) |
140 |
148 |
141 local open Simplifier |
149 local open Simplifier |
142 in |
150 in |
143 |
151 |
144 val hyp_subst_ss = empty_ss setmksimps mk_eqs |
152 val hyp_subst_ss = empty_ss setmksimps mk_eqs |
156 end |
164 end |
157 handle THM _ => no_tac | EQ_VAR => no_tac); |
165 handle THM _ => no_tac | EQ_VAR => no_tac); |
158 |
166 |
159 end; |
167 end; |
160 |
168 |
161 val ssubst = standard (sym RS subst); |
169 val ssubst = standard (Data.sym RS Data.subst); |
|
170 |
|
171 val imp_intr_tac = rtac Data.imp_intr; |
162 |
172 |
163 (*Old version of the tactic above -- slower but the only way |
173 (*Old version of the tactic above -- slower but the only way |
164 to handle equalities containing Vars.*) |
174 to handle equalities containing Vars.*) |
165 fun vars_gen_hyp_subst_tac bnd = SUBGOAL(fn (Bi,i) => |
175 fun vars_gen_hyp_subst_tac bnd = SUBGOAL(fn (Bi,i) => |
166 let val n = length(Logic.strip_assums_hyp Bi) - 1 |
176 let val n = length(Logic.strip_assums_hyp Bi) - 1 |
167 val (k,symopt) = eq_var bnd false Bi |
177 val (k,symopt) = eq_var bnd false Bi |
168 in |
178 in |
169 DETERM |
179 DETERM |
170 (EVERY [REPEAT_DETERM_N k (etac rev_mp i), |
180 (EVERY [REPEAT_DETERM_N k (etac Data.rev_mp i), |
171 etac revcut_rl i, |
181 rotate_tac 1 i, |
172 REPEAT_DETERM_N (n-k) (etac rev_mp i), |
182 REPEAT_DETERM_N (n-k) (etac Data.rev_mp i), |
173 etac (if symopt then ssubst else subst) i, |
183 etac (if symopt then ssubst else Data.subst) i, |
174 REPEAT_DETERM_N n (rtac imp_intr i THEN rotate_tac ~1 i)]) |
184 REPEAT_DETERM_N n (imp_intr_tac i THEN rotate_tac ~1 i)]) |
175 end |
185 end |
176 handle THM _ => no_tac | EQ_VAR => no_tac); |
186 handle THM _ => no_tac | EQ_VAR => no_tac); |
177 |
187 |
178 (*Substitutes for Free or Bound variables*) |
188 (*Substitutes for Free or Bound variables*) |
179 val hyp_subst_tac = FIRST' [ematch_tac [thin_refl], |
189 val hyp_subst_tac = FIRST' [ematch_tac [Data.thin_refl], |
180 gen_hyp_subst_tac false, vars_gen_hyp_subst_tac false]; |
190 gen_hyp_subst_tac false, vars_gen_hyp_subst_tac false]; |
181 |
191 |
182 (*Substitutes for Bound variables only -- this is always safe*) |
192 (*Substitutes for Bound variables only -- this is always safe*) |
183 val bound_hyp_subst_tac = |
193 val bound_hyp_subst_tac = |
184 gen_hyp_subst_tac true ORELSE' vars_gen_hyp_subst_tac true; |
194 gen_hyp_subst_tac true ORELSE' vars_gen_hyp_subst_tac true; |
185 |
195 |
186 end |
196 |
|
197 (** Version for Blast_tac. Hyps that are affected by the substitution are |
|
198 moved to the front. Defect: even trivial changes are noticed, such as |
|
199 substitutions in the arguments of a function Var. **) |
|
200 |
|
201 (*final re-reversal of the changed assumptions*) |
|
202 fun reverse_n_tac 0 i = all_tac |
|
203 | reverse_n_tac 1 i = rotate_tac ~1 i |
|
204 | reverse_n_tac n i = |
|
205 REPEAT_DETERM_N n (rotate_tac ~1 i THEN etac Data.rev_mp i) THEN |
|
206 REPEAT_DETERM_N n (imp_intr_tac i THEN rotate_tac ~1 i); |
|
207 |
|
208 (*Use imp_intr, comparing the old hyps with the new ones as they come out.*) |
|
209 fun all_imp_intr_tac hyps i = |
|
210 let fun imptac (r, []) st = reverse_n_tac r i st |
|
211 | imptac (r, hyp::hyps) st = |
|
212 let val (hyp',_) = List.nth (prems_of st, i-1) |> |
|
213 Logic.strip_assums_concl |> |
|
214 Data.dest_Trueprop |> Data.dest_imp |
|
215 val (r',tac) = if Pattern.aeconv (hyp,hyp') |
|
216 then (r, imp_intr_tac i THEN rotate_tac ~1 i) |
|
217 else (*leave affected hyps at end*) |
|
218 (r+1, imp_intr_tac i) |
|
219 in |
|
220 case Seq.pull(tac st) of |
|
221 None => Seq.single(st) |
|
222 | Some(st',_) => imptac (r',hyps) st' |
|
223 end handle _ => error "?? in blast_hyp_subst_tac" |
|
224 in imptac (0, rev hyps) end; |
|
225 |
|
226 |
|
227 fun blast_hyp_subst_tac trace = SUBGOAL(fn (Bi,i) => |
|
228 let val (k,symopt) = eq_var false false Bi |
|
229 val hyps0 = map Data.dest_Trueprop (Logic.strip_assums_hyp Bi) |
|
230 (*omit selected equality, returning other hyps*) |
|
231 val hyps = List.take(hyps0, k) @ List.drop(hyps0, k+1) |
|
232 val n = length hyps |
|
233 in |
|
234 if !trace then writeln "Substituting an equality" else (); |
|
235 DETERM |
|
236 (EVERY [REPEAT_DETERM_N k (etac Data.rev_mp i), |
|
237 rotate_tac 1 i, |
|
238 REPEAT_DETERM_N (n-k) (etac Data.rev_mp i), |
|
239 etac (if symopt then ssubst else Data.subst) i, |
|
240 all_imp_intr_tac hyps i]) |
|
241 end |
|
242 handle THM _ => no_tac | EQ_VAR => no_tac); |
|
243 |
187 end; |
244 end; |
188 |
245 |