15481
|
1 |
(* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- *)
|
|
2 |
(* Title: sys/rw_inst.ML
|
|
3 |
Author: Lucas Dixon, University of Edinburgh
|
|
4 |
lucas.dixon@ed.ac.uk
|
|
5 |
Created: 25 Aug 2004
|
|
6 |
*)
|
|
7 |
(* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- *)
|
|
8 |
(* DESCRIPTION:
|
|
9 |
|
|
10 |
rewriting using a conditional meta-equality theorem which supports
|
|
11 |
schematic variable instantiation.
|
|
12 |
|
|
13 |
*)
|
|
14 |
(* -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- *)
|
|
15 |
signature RW_INST =
|
|
16 |
sig
|
|
17 |
|
|
18 |
(* Rewrite: give it instantiation infromation, a rule, and the
|
|
19 |
target thm, and it will return the rewritten target thm *)
|
|
20 |
val rw :
|
|
21 |
((Term.indexname * Term.typ) list * (* type var instantiations *)
|
|
22 |
(Term.indexname * Term.term) list) (* schematic var instantiations *)
|
|
23 |
* (string * Term.typ) list * (* bound types *)
|
|
24 |
Term.term -> (* outer term for instantiation *)
|
|
25 |
Thm.thm -> (* rule with indexies lifted *)
|
|
26 |
Thm.thm -> (* target thm *)
|
|
27 |
Thm.thm (* rewritten theorem possibly
|
|
28 |
with additional premises for
|
|
29 |
rule conditions *)
|
|
30 |
|
|
31 |
(* used tools *)
|
|
32 |
val mk_abstractedrule :
|
|
33 |
(string * Term.typ) list -> Thm.thm -> Thm.cterm list * Thm.thm
|
|
34 |
val mk_fixtvar_tyinsts :
|
|
35 |
Term.indexname list ->
|
|
36 |
Term.term list -> ((string * int) * Term.typ) list * string list
|
|
37 |
val mk_renamings :
|
|
38 |
Term.term -> Thm.thm -> (((string * int) * Term.typ) * Term.term) list
|
|
39 |
val new_tfree :
|
|
40 |
((string * int) * Term.sort) *
|
|
41 |
(((string * int) * Term.typ) list * string list) ->
|
|
42 |
((string * int) * Term.typ) list * string list
|
|
43 |
val cross_inst : (Term.indexname * Term.term) list
|
|
44 |
-> (Term.indexname * Term.term) list
|
|
45 |
|
|
46 |
val beta_contract_tac : Thm.thm -> Thm.thm
|
|
47 |
val beta_eta_contract_tac : Thm.thm -> Thm.thm
|
|
48 |
|
|
49 |
end;
|
|
50 |
|
|
51 |
structure RWInst : RW_INST=
|
|
52 |
struct
|
|
53 |
|
|
54 |
|
|
55 |
(* beta contract the theorem *)
|
|
56 |
fun beta_contract_tac thm =
|
|
57 |
equal_elim (Thm.beta_conversion true (Thm.cprop_of thm)) thm;
|
|
58 |
|
|
59 |
(* beta-eta contract the theorem *)
|
|
60 |
fun beta_eta_contract_tac thm =
|
|
61 |
let
|
|
62 |
val thm2 = equal_elim (Thm.beta_conversion true (Thm.cprop_of thm)) thm
|
|
63 |
val thm3 = equal_elim (Thm.eta_conversion (Thm.cprop_of thm2)) thm2
|
|
64 |
in thm3 end;
|
|
65 |
|
|
66 |
(* Given a list of variables that were bound, and a that has been
|
|
67 |
instantiated with free variable placeholders for the bound vars, it
|
|
68 |
creates an abstracted version of the theorem, with local bound vars as
|
|
69 |
lambda-params:
|
|
70 |
|
|
71 |
Ts:
|
|
72 |
("x", ty)
|
|
73 |
|
|
74 |
rule::
|
|
75 |
C :x ==> P :x = Q :x
|
|
76 |
|
|
77 |
results in:
|
|
78 |
("!! x. C x", (%x. p x = %y. p y) [!! x. C x])
|
|
79 |
|
|
80 |
note: assumes rule is instantiated
|
|
81 |
*)
|
|
82 |
(* Note, we take abstraction in the order of last abstraction first *)
|
|
83 |
fun mk_abstractedrule Ts rule =
|
|
84 |
let
|
|
85 |
val ctermify = Thm.cterm_of (Thm.sign_of_thm rule);
|
|
86 |
|
|
87 |
(* now we change the names the temporary free vars that represent
|
|
88 |
bound vars with binders outside the redex *)
|
|
89 |
val prop = Thm.prop_of rule;
|
|
90 |
val names = Term.add_term_names (prop, []);
|
|
91 |
val (fromnames,tonames,names2) =
|
|
92 |
foldl (fn ((rnf,rnt,names),(n,ty)) =>
|
|
93 |
let val n2 = Term.variant names n in
|
|
94 |
(ctermify (Free(RWTools.mk_fake_bound_name n,
|
|
95 |
ty)) :: rnf,
|
|
96 |
ctermify (Free(n2,ty)) :: rnt,
|
|
97 |
n2 :: names)
|
|
98 |
end)
|
|
99 |
(([],[],names), Ts);
|
|
100 |
val rule' = rule |> Drule.forall_intr_list fromnames
|
|
101 |
|> Drule.forall_elim_list tonames;
|
|
102 |
|
|
103 |
(* make unconditional rule and prems *)
|
|
104 |
val (uncond_rule, cprems) = IsaND.allify_conditions ctermify Ts rule';
|
|
105 |
|
|
106 |
(* using these names create lambda-abstracted version of the rule *)
|
|
107 |
val abstractions = Ts ~~ (rev tonames);
|
|
108 |
val abstract_rule = foldl (fn (th,((n,ty),ct)) =>
|
|
109 |
Thm.abstract_rule n ct th)
|
|
110 |
(uncond_rule, abstractions);
|
|
111 |
in (cprems, abstract_rule) end;
|
|
112 |
|
|
113 |
|
|
114 |
(* given names to avoid, and vars that need to be fixed, it gives
|
|
115 |
unique new names to the vars so that they can be fixed as free
|
|
116 |
variables *)
|
|
117 |
(* make fixed unique free variable instantiations for non-ground vars *)
|
|
118 |
(* Create a table of vars to be renamed after instantiation - ie
|
|
119 |
other uninstantiated vars in the hyps of the rule
|
|
120 |
ie ?z in C ?z ?x ==> A ?x ?y = B ?x ?y *)
|
|
121 |
fun mk_renamings tgt rule_inst =
|
|
122 |
let
|
|
123 |
val rule_conds = Thm.prems_of rule_inst
|
|
124 |
val names = foldr Term.add_term_names (tgt :: rule_conds, []);
|
|
125 |
val (conds_tyvs,cond_vs) =
|
|
126 |
foldl (fn ((tyvs, vs), t) =>
|
|
127 |
(Library.union
|
|
128 |
(Term.term_tvars t, tyvs),
|
|
129 |
Library.union
|
|
130 |
(map Term.dest_Var (Term.term_vars t), vs)))
|
|
131 |
(([],[]), rule_conds);
|
|
132 |
val termvars = map Term.dest_Var (Term.term_vars tgt);
|
|
133 |
val vars_to_fix = Library.union (termvars, cond_vs);
|
|
134 |
val (renamings, names2) =
|
|
135 |
foldr (fn (((n,i),ty), (vs, names')) =>
|
|
136 |
let val n' = Term.variant names' n in
|
|
137 |
((((n,i),ty), Free (n', ty)) :: vs, n'::names')
|
|
138 |
end)
|
|
139 |
(vars_to_fix, ([], names));
|
|
140 |
in renamings end;
|
|
141 |
|
|
142 |
(* make a new fresh typefree instantiation for the given tvar *)
|
|
143 |
fun new_tfree (tv as (ix,sort), (pairs,used)) =
|
|
144 |
let val v = variant used (string_of_indexname ix)
|
|
145 |
in ((ix,TFree(v,sort))::pairs, v::used) end;
|
|
146 |
|
|
147 |
|
|
148 |
(* make instantiations to fix type variables that are not
|
|
149 |
already instantiated (in ignore_ixs) from the list of terms. *)
|
|
150 |
fun mk_fixtvar_tyinsts ignore_ixs ts =
|
|
151 |
let val (tvars, tfreenames) =
|
|
152 |
foldr (fn (t, (varixs, tfreenames)) =>
|
|
153 |
(Term.add_term_tvars (t,varixs),
|
|
154 |
Term.add_term_tfree_names (t,tfreenames)))
|
|
155 |
(ts, ([],[]));
|
|
156 |
val unfixed_tvars = filter (fn (ix,s) => not (ix mem ignore_ixs)) tvars;
|
|
157 |
val (fixtyinsts, _) = foldr new_tfree (unfixed_tvars, ([], tfreenames))
|
|
158 |
in (fixtyinsts, tfreenames) end;
|
|
159 |
|
|
160 |
|
|
161 |
(* cross-instantiate the instantiations - ie for each instantiation
|
|
162 |
replace all occurances in other instantiations - no loops are possible
|
|
163 |
and thus only one-parsing of the instantiations is necessary. *)
|
|
164 |
fun cross_inst insts =
|
|
165 |
let
|
|
166 |
fun instL (ix, t) =
|
|
167 |
map (fn (ix2,t2) => (ix2, Term.subst_vars ([], [(ix, t)]) t2));
|
|
168 |
|
|
169 |
fun cross_instL ([], l) = rev l
|
|
170 |
| cross_instL ((ix, t) :: insts, l) =
|
|
171 |
cross_instL (instL (ix, t) insts, (ix, t) :: (instL (ix, t) l));
|
|
172 |
|
|
173 |
in cross_instL (insts, []) end;
|
|
174 |
(* as above but for types -- I don't know if this is needed, will we ever incur mixed up types? *)
|
|
175 |
fun cross_inst_typs insts =
|
|
176 |
let
|
|
177 |
fun instL (ix, ty) =
|
|
178 |
map (fn (ix2,ty2) => (ix2, Term.typ_subst_TVars [(ix, ty)] ty2));
|
|
179 |
|
|
180 |
fun cross_instL ([], l) = rev l
|
|
181 |
| cross_instL ((ix, t) :: insts, l) =
|
|
182 |
cross_instL (instL (ix, t) insts, (ix, t) :: (instL (ix, t) l));
|
|
183 |
|
|
184 |
in cross_instL (insts, []) end;
|
|
185 |
|
|
186 |
|
|
187 |
(* assume that rule and target_thm have distinct var names *)
|
|
188 |
(* THINK: efficient version with tables for vars for: target vars,
|
|
189 |
introduced vars, and rule vars, for quicker instantiation? *)
|
|
190 |
(* The outerterm defines which part of the target_thm was modified *)
|
|
191 |
(* Note: we take Ts in the upterm order, ie last abstraction first.,
|
|
192 |
and with an outeterm where the abstracted subterm has the arguments in
|
|
193 |
the revered order, ie first abstraction first. *)
|
|
194 |
fun rw ((nonfixed_typinsts, unprepinsts), Ts, outerterm) rule target_thm =
|
|
195 |
let
|
|
196 |
(* general signature info *)
|
|
197 |
val target_sign = (Thm.sign_of_thm target_thm);
|
|
198 |
val ctermify = Thm.cterm_of target_sign;
|
|
199 |
val ctypeify = Thm.ctyp_of target_sign;
|
|
200 |
|
|
201 |
(* fix all non-instantiated tvars *)
|
|
202 |
val (fixtyinsts, othertfrees) =
|
|
203 |
mk_fixtvar_tyinsts (map fst nonfixed_typinsts)
|
|
204 |
[Thm.prop_of rule, Thm.prop_of target_thm];
|
|
205 |
|
|
206 |
val typinsts = cross_inst_typs (nonfixed_typinsts @ fixtyinsts);
|
|
207 |
|
|
208 |
(* certified instantiations for types *)
|
|
209 |
val ctyp_insts = map (apsnd ctypeify) typinsts;
|
|
210 |
|
|
211 |
(* type instantiated versions *)
|
|
212 |
val tgt_th_tyinst =
|
|
213 |
Thm.instantiate (ctyp_insts, []) target_thm;
|
|
214 |
val rule_tyinst =
|
|
215 |
Thm.instantiate (ctyp_insts, []) rule;
|
|
216 |
|
|
217 |
(* type instanitated outer term *)
|
|
218 |
val outerterm_tyinst =
|
|
219 |
Term.subst_vars (typinsts,[]) outerterm;
|
|
220 |
|
|
221 |
(* type-instantiate the var instantiations *)
|
|
222 |
val insts_tyinst = foldr (fn ((ix,t),insts_tyinst) =>
|
|
223 |
(ix, Term.subst_vars (typinsts,[]) t)
|
|
224 |
:: insts_tyinst)
|
|
225 |
(unprepinsts,[]);
|
|
226 |
|
|
227 |
(* cross-instantiate *)
|
|
228 |
val insts_tyinst_inst = cross_inst insts_tyinst;
|
|
229 |
|
|
230 |
(* create certms of instantiations *)
|
|
231 |
val cinsts_tyinst =
|
|
232 |
map (fn (ix,t) => (ctermify (Var (ix, Term.type_of t)),
|
|
233 |
ctermify t)) insts_tyinst_inst;
|
|
234 |
|
|
235 |
(* The instantiated rule *)
|
|
236 |
val rule_inst = rule_tyinst |> Thm.instantiate ([], cinsts_tyinst);
|
|
237 |
|
|
238 |
(* Create a table of vars to be renamed after instantiation - ie
|
|
239 |
other uninstantiated vars in the hyps the *instantiated* rule
|
|
240 |
ie ?z in C ?z ?x ==> A ?x ?y = B ?x ?y *)
|
|
241 |
val renamings = mk_renamings (Thm.prop_of tgt_th_tyinst)
|
|
242 |
rule_inst;
|
|
243 |
val cterm_renamings =
|
|
244 |
map (fn (x,y) => (ctermify (Var x), ctermify y)) renamings;
|
|
245 |
|
|
246 |
(* Create the specific version of the rule for this target application *)
|
|
247 |
val outerterm_inst =
|
|
248 |
outerterm_tyinst
|
|
249 |
|> Term.subst_vars ([], insts_tyinst_inst)
|
|
250 |
|> Term.subst_vars ([], map (fn ((ix,ty),t) => (ix,t))
|
|
251 |
renamings);
|
|
252 |
val couter_inst = Thm.reflexive (ctermify outerterm_inst);
|
|
253 |
val (cprems, abstract_rule_inst) =
|
|
254 |
rule_inst |> Thm.instantiate ([], cterm_renamings)
|
|
255 |
|> mk_abstractedrule Ts;
|
|
256 |
val specific_tgt_rule =
|
|
257 |
beta_eta_contract_tac
|
|
258 |
(Thm.combination couter_inst abstract_rule_inst);
|
|
259 |
|
|
260 |
(* create an instantiated version of the target thm *)
|
|
261 |
val tgt_th_inst =
|
|
262 |
tgt_th_tyinst |> Thm.instantiate ([], cinsts_tyinst)
|
|
263 |
|> Thm.instantiate ([], cterm_renamings);
|
|
264 |
|
|
265 |
val (vars,frees_of_fixed_vars) = Library.split_list cterm_renamings;
|
|
266 |
|
|
267 |
in
|
|
268 |
(beta_eta_contract_tac tgt_th_inst)
|
|
269 |
|> Thm.equal_elim specific_tgt_rule
|
|
270 |
|> Drule.implies_intr_list cprems
|
|
271 |
|> Drule.forall_intr_list frees_of_fixed_vars
|
|
272 |
|> Drule.forall_elim_list vars
|
|
273 |
|> fst o Thm.varifyT' othertfrees
|
|
274 |
|> Drule.zero_var_indexes
|
|
275 |
end;
|
|
276 |
|
|
277 |
|
|
278 |
end; (* struct *)
|