75 Not if it resembles x=t[x], since substitution does not eliminate x. |
77 Not if it resembles x=t[x], since substitution does not eliminate x. |
76 Not if it resembles ?x=0; consider ?x=0 ==> ?x=1 or even ?x=0 ==> P |
78 Not if it resembles ?x=0; consider ?x=0 ==> ?x=1 or even ?x=0 ==> P |
77 Not if it involves a variable free in the premises, |
79 Not if it involves a variable free in the premises, |
78 but we can't check for this -- hence bnd and bound_hyp_subst_tac |
80 but we can't check for this -- hence bnd and bound_hyp_subst_tac |
79 Prefer to eliminate Bound variables if possible. |
81 Prefer to eliminate Bound variables if possible. |
80 Result: true = use as is, false = reorient first *) |
82 Result: true = use as is, false = reorient first |
|
83 also returns var to substitute, relevant if it is Free *) |
81 fun inspect_pair bnd novars (t, u) = |
84 fun inspect_pair bnd novars (t, u) = |
82 if novars andalso (has_tvars t orelse has_tvars u) |
85 if novars andalso (has_tvars t orelse has_tvars u) |
83 then raise Match (*variables in the type!*) |
86 then raise Match (*variables in the type!*) |
84 else |
87 else |
85 (case (contract t, contract u) of |
88 (case (contract t, contract u) of |
86 (Bound i, _) => |
89 (Bound i, _) => |
87 if loose_bvar1 (u, i) orelse novars andalso has_vars u |
90 if loose_bvar1 (u, i) orelse novars andalso has_vars u |
88 then raise Match |
91 then raise Match |
89 else true (*eliminates t*) |
92 else (true, Bound i) (*eliminates t*) |
90 | (_, Bound i) => |
93 | (_, Bound i) => |
91 if loose_bvar1 (t, i) orelse novars andalso has_vars t |
94 if loose_bvar1 (t, i) orelse novars andalso has_vars t |
92 then raise Match |
95 then raise Match |
93 else false (*eliminates u*) |
96 else (false, Bound i) (*eliminates u*) |
94 | (t' as Free _, _) => |
97 | (t' as Free _, _) => |
95 if bnd orelse Logic.occs (t', u) orelse novars andalso has_vars u |
98 if bnd orelse Logic.occs (t', u) orelse novars andalso has_vars u |
96 then raise Match |
99 then raise Match |
97 else true (*eliminates t*) |
100 else (true, t') (*eliminates t*) |
98 | (_, u' as Free _) => |
101 | (_, u' as Free _) => |
99 if bnd orelse Logic.occs (u', t) orelse novars andalso has_vars t |
102 if bnd orelse Logic.occs (u', t) orelse novars andalso has_vars t |
100 then raise Match |
103 then raise Match |
101 else false (*eliminates u*) |
104 else (false, u') (*eliminates u*) |
102 | _ => raise Match); |
105 | _ => raise Match); |
103 |
106 |
104 (*Locates a substitutable variable on the left (resp. right) of an equality |
107 (*Locates a substitutable variable on the left (resp. right) of an equality |
105 assumption. Returns the number of intervening assumptions. *) |
108 assumption. Returns the number of intervening assumptions. *) |
106 fun eq_var bnd novars = |
109 fun eq_var bnd novars check_frees t = |
107 let fun eq_var_aux k (Const(@{const_name Pure.all},_) $ Abs(_,_,t)) = eq_var_aux k t |
110 let |
108 | eq_var_aux k (Const(@{const_name Pure.imp},_) $ A $ B) = |
111 fun check_free ts (orient, Free f) |
109 ((k, inspect_pair bnd novars |
112 = if not check_frees orelse not orient |
110 (Data.dest_eq (Data.dest_Trueprop A))) |
113 orelse exists (curry Logic.occs (Free f)) ts |
111 handle TERM _ => eq_var_aux (k+1) B |
114 then (orient, true) else raise Match |
112 | Match => eq_var_aux (k+1) B) |
115 | check_free ts (orient, _) = (orient, false) |
113 | eq_var_aux k _ = raise EQ_VAR |
116 fun eq_var_aux k (Const(@{const_name Pure.all},_) $ Abs(_,_,t)) hs = eq_var_aux k t hs |
114 in eq_var_aux 0 end; |
117 | eq_var_aux k (Const(@{const_name Pure.imp},_) $ A $ B) hs = |
|
118 ((k, check_free (B :: hs) (inspect_pair bnd novars |
|
119 (Data.dest_eq (Data.dest_Trueprop A)))) |
|
120 handle TERM _ => eq_var_aux (k+1) B (A :: hs) |
|
121 | Match => eq_var_aux (k+1) B (A :: hs)) |
|
122 | eq_var_aux k _ _ = raise EQ_VAR |
|
123 |
|
124 in eq_var_aux 0 t [] end; |
|
125 |
|
126 val thin_free_eq_tac = SUBGOAL (fn (t, i) => let |
|
127 val (k, _) = eq_var false false false t |
|
128 val ok = (eq_var false false true t |> fst) > k |
|
129 handle EQ_VAR => true |
|
130 in if ok then EVERY [rotate_tac k i, etac thin_rl i, rotate_tac (~k) i] |
|
131 else no_tac |
|
132 end handle EQ_VAR => no_tac) |
115 |
133 |
116 (*For the simpset. Adds ALL suitable equalities, even if not first! |
134 (*For the simpset. Adds ALL suitable equalities, even if not first! |
117 No vars are allowed here, as simpsets are built from meta-assumptions*) |
135 No vars are allowed here, as simpsets are built from meta-assumptions*) |
118 fun mk_eqs bnd th = |
136 fun mk_eqs bnd th = |
119 [ if inspect_pair bnd false (Data.dest_eq (Data.dest_Trueprop (Thm.prop_of th))) |
137 [ if inspect_pair bnd false (Data.dest_eq (Data.dest_Trueprop (Thm.prop_of th))) |> fst |
120 then th RS Data.eq_reflection |
138 then th RS Data.eq_reflection |
121 else Thm.symmetric(th RS Data.eq_reflection) (*reorient*) ] |
139 else Thm.symmetric(th RS Data.eq_reflection) (*reorient*) ] |
122 handle TERM _ => [] | Match => []; |
140 handle TERM _ => [] | Match => []; |
123 |
141 |
|
142 fun bool2s true = "true" | bool2s false = "false" |
|
143 |
124 local |
144 local |
125 in |
145 in |
126 |
146 |
127 (*Select a suitable equality assumption; substitute throughout the subgoal |
147 (*Select a suitable equality assumption; substitute throughout the subgoal |
128 If bnd is true, then it replaces Bound variables only. *) |
148 If bnd is true, then it replaces Bound variables only. *) |
129 fun gen_hyp_subst_tac ctxt bnd = |
149 fun gen_hyp_subst_tac ctxt bnd = |
130 let fun tac i st = SUBGOAL (fn (Bi, _) => |
150 SUBGOAL (fn (Bi, i) => |
131 let |
151 let |
132 val (k, _) = eq_var bnd true Bi |
152 val (k, (orient, is_free)) = eq_var bnd true true Bi |
133 val hyp_subst_ctxt = empty_simpset ctxt |> Simplifier.set_mksimps (K (mk_eqs bnd)) |
153 val hyp_subst_ctxt = empty_simpset ctxt |> Simplifier.set_mksimps (K (mk_eqs bnd)) |
134 in EVERY [rotate_tac k i, asm_lr_simp_tac hyp_subst_ctxt i, |
154 in EVERY [rotate_tac k i, asm_lr_simp_tac hyp_subst_ctxt i, |
135 etac thin_rl i, rotate_tac (~k) i] |
155 if not is_free then etac thin_rl i |
136 end handle THM _ => no_tac | EQ_VAR => no_tac) i st |
156 else if orient then etac Data.rev_mp i |
137 in REPEAT_DETERM1 o tac end; |
157 else etac (Data.sym RS Data.rev_mp) i, |
|
158 rotate_tac (~k) i, |
|
159 if is_free then rtac Data.imp_intr i else all_tac] |
|
160 end handle THM _ => no_tac | EQ_VAR => no_tac) |
138 |
161 |
139 end; |
162 end; |
140 |
163 |
141 val ssubst = Drule.zero_var_indexes (Data.sym RS Data.subst); |
164 val ssubst = Drule.zero_var_indexes (Data.sym RS Data.subst); |
142 |
165 |
172 end |
195 end |
173 | NONE => no_tac); |
196 | NONE => no_tac); |
174 |
197 |
175 val imp_intr_tac = rtac Data.imp_intr; |
198 val imp_intr_tac = rtac Data.imp_intr; |
176 |
199 |
|
200 fun rev_dup_elim th = (th RSN (2, revcut_rl)) |> Thm.assumption 2 |> Seq.hd; |
|
201 val dup_subst = rev_dup_elim ssubst |
|
202 |
177 (* FIXME: "etac Data.rev_mp i" will not behave as expected if goal has *) |
203 (* FIXME: "etac Data.rev_mp i" will not behave as expected if goal has *) |
178 (* premises containing meta-implications or quantifiers *) |
204 (* premises containing meta-implications or quantifiers *) |
179 |
205 |
180 (*Old version of the tactic above -- slower but the only way |
206 (*Old version of the tactic above -- slower but the only way |
181 to handle equalities containing Vars.*) |
207 to handle equalities containing Vars.*) |
182 fun vars_gen_hyp_subst_tac bnd = SUBGOAL(fn (Bi,i) => |
208 fun vars_gen_hyp_subst_tac bnd = SUBGOAL(fn (Bi,i) => |
183 let val n = length(Logic.strip_assums_hyp Bi) - 1 |
209 let val n = length(Logic.strip_assums_hyp Bi) - 1 |
184 val (k,symopt) = eq_var bnd false Bi |
210 val (k, (orient, is_free)) = eq_var bnd false true Bi |
|
211 val rl = if is_free then dup_subst else ssubst |
|
212 val rl = if orient then rl else Data.sym RS rl |
185 in |
213 in |
186 DETERM |
214 DETERM |
187 (EVERY [REPEAT_DETERM_N k (etac Data.rev_mp i), |
215 (EVERY [REPEAT_DETERM_N k (etac Data.rev_mp i), |
188 rotate_tac 1 i, |
216 rotate_tac 1 i, |
189 REPEAT_DETERM_N (n-k) (etac Data.rev_mp i), |
217 REPEAT_DETERM_N (n-k) (etac Data.rev_mp i), |
190 inst_subst_tac symopt (if symopt then ssubst else Data.subst) i, |
218 inst_subst_tac orient rl i, |
191 REPEAT_DETERM_N n (imp_intr_tac i THEN rotate_tac ~1 i)]) |
219 REPEAT_DETERM_N n (imp_intr_tac i THEN rotate_tac ~1 i)]) |
192 end |
220 end |
193 handle THM _ => no_tac | EQ_VAR => no_tac); |
221 handle THM _ => no_tac | EQ_VAR => no_tac); |
194 |
222 |
195 (*Substitutes for Free or Bound variables*) |
223 (*Substitutes for Free or Bound variables, |
196 fun hyp_subst_tac ctxt = |
224 discarding equalities on Bound variables |
197 FIRST' [ematch_tac [Data.thin_refl], |
225 and on Free variables if thin=true*) |
198 gen_hyp_subst_tac ctxt false, vars_gen_hyp_subst_tac false]; |
226 fun hyp_subst_tac_thin thin ctxt = |
|
227 REPEAT_DETERM1 o FIRST' [ematch_tac [Data.thin_refl], |
|
228 gen_hyp_subst_tac ctxt false, vars_gen_hyp_subst_tac false, |
|
229 if thin then thin_free_eq_tac else K no_tac]; |
|
230 |
|
231 val (hyp_subst_thins, hyp_subst_thins_setup) = Attrib.config_bool |
|
232 @{binding hypsubst_thin} (K false); |
|
233 |
|
234 fun hyp_subst_tac ctxt = hyp_subst_tac_thin |
|
235 (Config.get ctxt hyp_subst_thins) ctxt |
199 |
236 |
200 (*Substitutes for Bound variables only -- this is always safe*) |
237 (*Substitutes for Bound variables only -- this is always safe*) |
201 fun bound_hyp_subst_tac ctxt = |
238 fun bound_hyp_subst_tac ctxt = |
202 gen_hyp_subst_tac ctxt true ORELSE' vars_gen_hyp_subst_tac true; |
239 REPEAT_DETERM1 o (gen_hyp_subst_tac ctxt true |
203 |
240 ORELSE' vars_gen_hyp_subst_tac true); |
204 |
241 |
205 (** Version for Blast_tac. Hyps that are affected by the substitution are |
242 (** Version for Blast_tac. Hyps that are affected by the substitution are |
206 moved to the front. Defect: even trivial changes are noticed, such as |
243 moved to the front. Defect: even trivial changes are noticed, such as |
207 substitutions in the arguments of a function Var. **) |
244 substitutions in the arguments of a function Var. **) |
208 |
245 |