Debian Codegraph @

Formal_ineqs/list/list_conversions.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2012 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* Efficient formal list conversions *)
11 (* -------------------------------------------------------------------------- *)
12
13 needs "Formal_ineqs/arith/arith_nat.hl";;
14 needs "Formal_ineqs/misc/misc_vars.hl";;
15
16 module type List_conversions_sig =
17 sig
18 val eval_hd : term -> thm
19 val hd_conv : term -> thm
20 val eval_el : term -> term -> thm
21 val el_conv : term -> thm
22 val fst_conv : term -> thm
23 val snd_conv : term -> thm
24 val eval_length : term -> thm
25 val length_conv : term -> thm
26 val eval_zip : term -> term -> thm
27 val all_conv_univ : (term -> thm) -> term -> thm
28 val all2_conv_univ : (term -> thm) -> term -> thm
29 val eval_mem_univ : (term -> thm) -> term -> term -> thm
30 val mem_conv_univ : (term -> thm) -> term -> thm
31 val filter_conv_univ : (term -> thm) -> term -> thm
32 val map_conv_univ : (term -> thm) -> term -> thm
33 val get_all : thm -> thm list
34 val select_all : thm -> int list -> thm list
35 val set_of_list_conv : term -> thm
36 end;;
37
38
39 module List_conversions : List_conversions_sig = struct
40
41 open Arith_nat;;
42 open Misc_functions;;
43 open Misc_vars;;
44
45
46 let MY_RULE = UNDISCH_ALL o PURE_REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL;;
47 let MY_RULE_NUM = UNDISCH_ALL o NUMERALS_TO_NUM o PURE_REWRITE_RULE[GSYM IMP_IMP] o SPEC_ALL;;
48
49 (******************************)
50
51 (* HD conversions *)
52
53 let HD_A_CONS = prove(`HD (CONS (h:A) t) = h`, REWRITE_TAC[HD]);;
54
55 (* Takes a term `[a;...]` and returns the theorem |- HD [a;...] = a *)
56 let eval_hd list_tm =
57 let ltm, t_tm = dest_comb list_tm in
58 let h_tm = rand ltm in
59 let list_ty = type_of t_tm and
60 ty = type_of h_tm in
61 let h_var = mk_var("h", ty) and
62 t_var = mk_var("t", list_ty) in
63 (INST[h_tm, h_var; t_tm, t_var] o INST_TYPE[ty, aty]) HD_A_CONS;;
64
65 (* Takes a term `HD [a;...]` and returns the theorem |- HD [a;...] = a *)
66 let hd_conv hd_tm =
67 if (fst o dest_const o rator) hd_tm <> "HD" then failwith "hd_conv"
68 else eval_hd (rand hd_tm);;
69
70
71 (*********************************)
72 (* EL conversion *)
73
74 let EL_0' = (MY_RULE_NUM o prove)(`EL 0 (CONS (h:A) t) = h`, REWRITE_TAC[EL; HD]);;
75 let EL_n' = (MY_RULE_NUM o prove)(`0 < n /\ PRE n = m ==> EL n (CONS (h:A) t) = EL m t`,
76 STRIP_TAC THEN SUBGOAL_THEN `n = SUC m` ASSUME_TAC THENL
77 [ REPEAT (POP_ASSUM MP_TAC) THEN ARITH_TAC; ALL_TAC ] THEN ASM_REWRITE_TAC[EL; TL]);;
78
79
80 (* Takes a raw numeral term and a list term and returns the theorem |- EL n [...] = x *)
81 let eval_el n_tm list_tm =
82 let list_ty = type_of list_tm in
83 let ty = (hd o snd o dest_type) list_ty in
84 let inst_t = INST_TYPE[ty, aty] in
85 let el_0, el_n = inst_t EL_0', inst_t EL_n' in
86 let h_var, t_var = mk_var("h", ty), mk_var("t", list_ty) in
87
88 let rec el_conv_raw = fun n_tm list_tm ->
89 let h_tm, t_tm = dest_cons list_tm in
90 let inst0 = INST[h_tm, h_var; t_tm, t_var] in
91 if n_tm = zero_const then
92 inst0 el_0
93 else
94 let n_gt0 = (EQT_ELIM o raw_gt0_hash_conv) n_tm in
95 let pre_n = raw_pre_hash_conv (mk_comb (pre_op_num, n_tm)) in
96 let m_tm = (rand o concl) pre_n in
97 let th0 = (MY_PROVE_HYP pre_n o MY_PROVE_HYP n_gt0 o
98 INST[n_tm, n_var_num; m_tm, m_var_num] o inst0) el_n in
99 let th1 = el_conv_raw m_tm t_tm in
100 TRANS th0 th1 in
101 el_conv_raw n_tm list_tm;;
102
103
104
105 (* Takes a term `EL n [...]` and returns the theorem |- EL n [...] = x *)
106 (* Note: n must be a raw numeral term Dx (Dy ... _0) *)
107 let el_conv el_tm =
108 let ltm, list_tm = dest_comb el_tm in
109 let el, n_tm = dest_comb ltm in
110 if (fst o dest_const) el <> "EL" then failwith "el_conv"
111 else eval_el n_tm list_tm;;
112
113
114
115 (*******************************)
116 (* FST, SND conversions *)
117
118 let FST' = ISPECL[`x:A`; `y:B`] FST;;
119 let SND' = ISPECL[`x:A`; `y:B`] SND;;
120
121 let fst_conv tm =
122 let x_tm, y_tm = dest_pair (rand tm) in
123 let x_ty, y_ty = type_of x_tm, type_of y_tm in
124 let x_var, y_var = mk_var("x", x_ty), mk_var("y", y_ty) in
125 (INST[x_tm, x_var; y_tm, y_var] o INST_TYPE[x_ty, aty; y_ty, bty]) FST';;
126
127 let snd_conv tm =
128 let x_tm, y_tm = dest_pair (rand tm) in
129 let x_ty, y_ty = type_of x_tm, type_of y_tm in
130 let x_var, y_var = mk_var("x", x_ty), mk_var("y", y_ty) in
131 (INST[x_tm, x_var; y_tm, y_var] o INST_TYPE[x_ty, aty; y_ty, bty]) SND';;
132
133
134
135 (******************************)
136 (* LENGTH conversions *)
137
138 let LENGTH_0' = (MY_RULE_NUM o prove) (`LENGTH ([]:(A)list) = 0`, REWRITE_TAC[LENGTH]) and
139 LENGTH_CONS' = prove(`LENGTH (CONS (h:A) t) = SUC (LENGTH t)`, REWRITE_TAC[LENGTH]);;
140
141 (* Takes a term `[...]` and returns the theorem |- LENGTH [...] = n *)
142 let eval_length list_tm =
143 let list_ty = type_of list_tm in
144 let ty = (hd o snd o dest_type) list_ty in
145 let inst_t = INST_TYPE[ty, aty] in
146 let length_empty, length_cons = inst_t LENGTH_0', inst_t LENGTH_CONS' in
147 let h_var, t_var = mk_var("h", ty), mk_var("t", list_ty) in
148
149 let rec length_conv_raw = fun list_tm ->
150 if (is_comb list_tm) then
151 let ltm, t_tm = dest_comb list_tm in
152 let h_tm = rand ltm in
153 let th0 = INST[h_tm, h_var; t_tm, t_var] length_cons in
154 let th1' = length_conv_raw t_tm in
155 let th1 = AP_TERM suc_op_num th1' in
156 let th2 = raw_suc_conv_hash (rand(concl th1)) in
157 TRANS (TRANS th0 th1) th2
158 else
159 length_empty in
160 length_conv_raw list_tm;;
161
162
163 (* Takes a term `LENGTH [...]` and returns the theorem |- LENGTH [...] = n *)
164 let length_conv length_tm =
165 if (fst o dest_const o rator) length_tm <> "LENGTH" then failwith "length_conv"
166 else eval_length (rand length_tm);;
167
168
169
170 (************************)
171 (* eval_zip *)
172
173 let ZIP_0' = prove(`ZIP ([]:(A)list) ([]:(B)list) = []`, REWRITE_TAC[ZIP]) and
174 ZIP_CONS' = prove(`ZIP (CONS (h1:A) t1) (CONS (h2:B) t2) = CONS (h1, h2) (ZIP t1 t2)`,
175 REWRITE_TAC[ZIP]);;
176
177 let eval_zip list1_tm list2_tm =
178 let list1_ty = type_of list1_tm and
179 list2_ty = type_of list2_tm in
180 let ty1 = (hd o snd o dest_type) list1_ty and
181 ty2 = (hd o snd o dest_type) list2_ty in
182 let inst_t = INST_TYPE[ty1, aty; ty2, bty] in
183 let zip0, zip_cons = inst_t ZIP_0', inst_t ZIP_CONS' in
184 let h1_var, t1_var = mk_var("h1", ty1), mk_var("t1", list1_ty) and
185 h2_var, t2_var = mk_var("h2", ty2), mk_var("t2", list2_ty) in
186
187 let rec zip_conv_rec = fun list1_tm list2_tm ->
188 if (is_comb list1_tm) then
189 let ltm1, t1_tm = dest_comb list1_tm and
190 ltm2, t2_tm = dest_comb list2_tm in
191 let h1_tm, h2_tm = rand ltm1, rand ltm2 in
192 let th0 = INST[h1_tm, h1_var; t1_tm, t1_var; h2_tm, h2_var; t2_tm, t2_var] zip_cons in
193 let cons_tm = (rator o rand o concl) th0 in
194 let th1' = zip_conv_rec t1_tm t2_tm in
195 let th1 = AP_TERM cons_tm th1' in
196 TRANS th0 th1
197 else
198 zip0 in
199 zip_conv_rec list1_tm list2_tm;;
200
201
202 (******************)
203 (* ALL conversion *)
204 (******************)
205
206 let ALL_0' = prove(`ALL P ([]:(A)list) <=> T`, REWRITE_TAC[ALL]) and
207 ALL_CONS_T' = (MY_RULE o prove)(`(P h <=> T) /\ (ALL P t <=> T) ==> (ALL P (CONS (h:A) t) <=> T)`,
208 REWRITE_TAC[ALL]) and
209 ALL_CONS_F2' = (MY_RULE o prove)(`(ALL P t <=> F) ==> (ALL P (CONS (h:A) t) <=> F)`,
210 SIMP_TAC[ALL]) and
211 ALL_CONS_F1' = (MY_RULE o prove)(`(P h <=> F) ==> (ALL P (CONS (h:A) t) <=> F)`,
212 SIMP_TAC[ALL]);;
213
214
215 (* Note: p_conv should return theorems of the form |- P a <=> T *)
216 let all_conv_univ p_conv tm =
217 let ltm, list_tm = dest_comb tm in
218 let p_tm = rand ltm in
219
220 let list_ty = type_of list_tm and
221 p_ty = type_of p_tm in
222 let ty = (hd o snd o dest_type) list_ty in
223 let inst_t = INST_TYPE[ty, aty] in
224
225 let all_0, all_t, all_f1, all_f2 = inst_t ALL_0', inst_t ALL_CONS_T',
226 inst_t ALL_CONS_F1', inst_t ALL_CONS_F2' in
227 let h_var, t_var = mk_var("h", ty), mk_var("t", list_ty) and
228 p_var = mk_var("P", p_ty) in
229
230 let rec all_conv_rec = fun list_tm ->
231 if is_comb list_tm then
232 let ltm, t_tm = dest_comb list_tm in
233 let h_tm = rand ltm in
234 let p_th = p_conv (mk_comb (p_tm, h_tm)) in
235 let inst = INST[h_tm, h_var; t_tm, t_var; p_tm, p_var] in
236 if (rand o concl) p_th = t_const then
237 let all_th = all_conv_rec t_tm in
238 if (rand o concl) all_th = t_const then
239 (MY_PROVE_HYP all_th o MY_PROVE_HYP p_th o inst) all_t
240 else
241 (MY_PROVE_HYP all_th o inst) all_f2
242 else
243 (MY_PROVE_HYP p_th o inst) all_f1
244 else
245 INST[p_tm, p_var] all_0 in
246 all_conv_rec list_tm;;
247
248
249
250 (*******************)
251 (* ALL2 conversion *)
252 (*******************)
253
254 let ALL2_0' = prove(`ALL2 P ([]:(A)list) ([]:(B)list) <=> T`, REWRITE_TAC[ALL2]) and
255 ALL2_CONS_T' = (MY_RULE o prove)(`(P h1 h2 <=> T) /\ (ALL2 P t1 t2 <=> T) ==>
256 (ALL2 P (CONS (h1:A) t1) (CONS (h2:B) t2) <=> T)`,
257 REWRITE_TAC[ALL2]) and
258 ALL2_CONS_F2' = (MY_RULE o prove)(`(ALL2 P t1 t2 <=> F) ==>
259 (ALL2 P (CONS (h1:A) t1) (CONS (h2:B) t2) <=> F)`,
260 SIMP_TAC[ALL2]) and
261 ALL2_CONS_F1' = (MY_RULE o prove)(`(P h1 h2 <=> F) ==>
262 (ALL2 P (CONS (h1:A) t1) (CONS (h2:B) t2) <=> F)`,
263 SIMP_TAC[ALL2]);;
264
265
266 (* Note: p_conv should return theorems of the form |- P a b <=> T *)
267 let all2_conv_univ p_conv tm =
268 let ltm, list2_tm = dest_comb tm in
269 let ltm2, list1_tm = dest_comb ltm in
270 let p_tm = rand ltm2 in
271
272 let list1_ty = type_of list1_tm and
273 list2_ty = type_of list2_tm and
274 p_ty = type_of p_tm in
275 let ty1 = (hd o snd o dest_type) list1_ty and
276 ty2 = (hd o snd o dest_type) list2_ty in
277 let inst_t = INST_TYPE[ty1, aty; ty2, bty] in
278
279 let all2_0, all2_t, all2_f1, all2_f2 = inst_t ALL2_0', inst_t ALL2_CONS_T',
280 inst_t ALL2_CONS_F1', inst_t ALL2_CONS_F2' in
281 let h1_var, t1_var = mk_var("h1", ty1), mk_var("t1", list1_ty) and
282 h2_var, t2_var = mk_var("h2", ty2), mk_var("t2", list2_ty) and
283 p_var = mk_var("P", p_ty) in
284
285 let rec all2_conv_rec = fun list1_tm list2_tm ->
286 if is_comb list1_tm then
287 let ltm1, t1_tm = dest_comb list1_tm and
288 ltm2, t2_tm = dest_comb list2_tm in
289 let h1_tm, h2_tm = rand ltm1, rand ltm2 in
290 let p_th = p_conv (mk_binop p_tm h1_tm h2_tm) in
291 let inst = INST[h1_tm, h1_var; t1_tm, t1_var; h2_tm, h2_var; t2_tm, t2_var; p_tm, p_var] in
292 if (rand o concl) p_th = t_const then
293 let all2_th = all2_conv_rec t1_tm t2_tm in
294 if (rand o concl) all2_th = t_const then
295 (MY_PROVE_HYP all2_th o MY_PROVE_HYP p_th o inst) all2_t
296 else
297 (MY_PROVE_HYP all2_th o inst) all2_f2
298 else
299 (MY_PROVE_HYP p_th o inst) all2_f1
300 else
301 if is_comb list2_tm then failwith ("all2_conv_univ: l1 = []; l2 = "^string_of_term list2_tm) else
302 INST[p_tm, p_var] all2_0 in
303 all2_conv_rec list1_tm list2_tm;;
304
305
306
307 (******************************)
308 (* MEM conversions *)
309
310 let MEM_A_EMPTY = prove(`MEM (x:A) [] <=> F`, REWRITE_TAC[MEM]) and
311 MEM_A_HD = MY_RULE (prove(`(x = h <=> T) ==> (MEM (x:A) (CONS h t) <=> T)`,SIMP_TAC[MEM])) and
312 MEM_A_TL = MY_RULE (prove(`(x = h <=> F) ==> (MEM (x:A) (CONS h t) <=> MEM x t)`, SIMP_TAC[MEM]));;
313
314
315 let rec eval_mem_univ eq_conv x_tm list_tm =
316 let ty = type_of x_tm in
317 let inst_t = INST_TYPE[ty, aty] in
318 let mem_empty, mem_hd, mem_tl = inst_t MEM_A_EMPTY, inst_t MEM_A_HD, inst_t MEM_A_TL in
319 let x_var, h_var = mk_var("x", ty), mk_var("h", ty) and
320 t_var = mk_var("t", mk_type("list", [ty])) in
321
322 let rec mem_conv_raw list_tm =
323 if (is_comb list_tm) then
324 let h_tm', t_tm = dest_comb list_tm in
325 let h_tm = rand h_tm' in
326 let eq_th = eq_conv (mk_eq(x_tm, h_tm)) in
327 if (rand(concl eq_th) = t_const) then
328 let th0' = INST[x_tm, x_var; h_tm, h_var; t_tm, t_var] mem_hd in
329 MY_PROVE_HYP eq_th th0'
330 else
331 let th0' = INST[x_tm, x_var; h_tm, h_var; t_tm, t_var] mem_tl in
332 let th0 = MY_PROVE_HYP eq_th th0' in
333 let th1 = mem_conv_raw t_tm in
334 TRANS th0 th1
335 else
336 INST[x_tm, x_var] mem_empty in
337
338 mem_conv_raw list_tm;;
339
340
341 let mem_conv_univ eq_conv mem_tm =
342 let ltm, list_tm = dest_comb mem_tm in
343 let c_tm, x_tm = dest_comb ltm in
344 if (fst o dest_const) c_tm <> "MEM" then failwith "mem_conv_univ" else
345 eval_mem_univ eq_conv x_tm list_tm;;
346
347
348
349 (**********************************)
350 (* FILTER conversions *)
351
352 let FILTER_A_EMPTY = prove(`FILTER (P:A->bool) [] = []`, REWRITE_TAC[FILTER]) and
353 FILTER_A_HD = (MY_RULE o prove)(`(P h <=> T) ==> FILTER (P:A->bool) (CONS h t) = CONS h (FILTER P t)`,
354 SIMP_TAC[FILTER]) and
355 FILTER_A_TL = (MY_RULE o prove)(`(P h <=> F) ==> FILTER (P:A->bool) (CONS h t) = FILTER P t`,
356 SIMP_TAC[FILTER]);;
357
358
359 let filter_conv_univ p_conv tm =
360 let ltm, list_tm = dest_comb tm in
361 let p_tm = rand ltm in
362 let p_ty = type_of p_tm in
363 let ty = (hd o snd o dest_type) p_ty in
364 let inst_t = INST_TYPE[ty, aty] in
365 let filter_empty, filter_hd, filter_tl =
366 inst_t FILTER_A_EMPTY, inst_t FILTER_A_HD, inst_t FILTER_A_TL in
367 let p_var = mk_var("P", p_ty) in
368 let h_var = mk_var("h", ty) in
369 let t_var = mk_var("t", mk_type("list",[ty])) in
370
371 let rec filter_conv_raw = fun list_tm ->
372 if (is_comb list_tm) then
373 let ltm, t_tm = dest_comb list_tm in
374 let h_tm = rand ltm in
375 let p_th = p_conv (mk_comb(p_tm, h_tm)) in
376 if (rand(concl p_th) = t_const) then
377 let th0' = INST[p_tm, p_var; h_tm, h_var; t_tm, t_var] filter_hd in
378 let th0 = MY_PROVE_HYP p_th th0' in
379 let ltm = rator(rand(concl th0)) in
380 let th1 = filter_conv_raw t_tm in
381 TRANS th0 (AP_TERM ltm th1)
382 else
383 let th0' = INST[p_tm, p_var; h_tm, h_var; t_tm, t_var] filter_tl in
384 let th0 = MY_PROVE_HYP p_th th0' in
385 let th1 = filter_conv_raw t_tm in
386 TRANS th0 th1
387 else
388 INST[p_tm, p_var] filter_empty in
389 filter_conv_raw list_tm;;
390
391
392
393 (***************************)
394 (* MAP conversions *)
395
396 let MAP_AB_EMPTY = prove(`MAP (f:A->B) [] = []`, REWRITE_TAC[MAP]) and
397 MAP_AB_CONS = prove(`MAP (f:A->B) (CONS h t) = CONS (f h) (MAP f t)`, REWRITE_TAC[MAP]);;
398
399
400 let map_conv_univ f_conv tm =
401 let ltm, list_tm = dest_comb tm in
402 let ftm = rand ltm in
403 let ftm_ty = type_of ftm in
404 let f_var = mk_var("f", ftm_ty) in
405 let a_type, b_type = pair_of_list (snd (dest_type ftm_ty)) in
406 let h_var = mk_var("h", a_type) in
407 let t_var = mk_var("t", mk_type("list", [a_type])) in
408 let inst_t = INST[ftm, f_var] o INST_TYPE[a_type, aty; b_type, bty] in
409 let map_empty, map_cons =
410 inst_t MAP_AB_EMPTY, inst_t MAP_AB_CONS in
411
412 let rec map_conv_raw list_tm =
413 if (is_comb list_tm) then
414 let h_tm', t_tm = dest_comb list_tm in
415 let h_tm = rand h_tm' in
416 let th0 = INST[h_tm, h_var; t_tm, t_var] map_cons in
417 let ltm, rtm = dest_comb (rand(concl th0)) in
418 let cons_tm, f_h_tm = dest_comb ltm in
419 let f_h_th = f_conv f_h_tm in
420 let map_t_th = map_conv_raw t_tm in
421 TRANS th0 (MK_COMB (AP_TERM cons_tm f_h_th, map_t_th))
422 else
423 map_empty in
424
425 map_conv_raw list_tm;;
426
427
428 (*****************************************)
429 (* ALL rules *)
430
431 let ALL_A_HD = UNDISCH_ALL(prove(`ALL (P:A->bool) (CONS h t) ==> P h`, SIMP_TAC[ALL])) and
432 ALL_A_TL = UNDISCH_ALL(prove(`ALL (P:A->bool) (CONS h t) ==> ALL P t`, SIMP_TAC[ALL]));;
433
434
435 (* Given a theorem `ALL P list` returns the list of theorems (P x1),...,(P xn) *)
436 let get_all th =
437 let ltm, list_tm = dest_comb (concl th) in
438 let p_tm = rand ltm in
439 let list_ty = type_of list_tm in
440 let p_ty = type_of p_tm in
441 let ty = (hd o snd o dest_type) list_ty in
442 let p_var = mk_var("P", p_ty) in
443 let h_var = mk_var("h", ty) in
444 let t_var = mk_var("t", list_ty) in
445
446 let inst_t = INST[p_tm, p_var] o INST_TYPE[ty, aty] in
447 let all_hd, all_tl = inst_t ALL_A_HD, inst_t ALL_A_TL in
448
449 let rec get_all_raw all_th list_tm =
450 if (is_comb list_tm) then
451 let h_tm', t_tm = dest_comb list_tm in
452 let h_tm = rand h_tm' in
453 let inst_t = INST[h_tm, h_var; t_tm, t_var] in
454 let th_tl = MY_PROVE_HYP all_th (inst_t all_tl) in
455 let th_hd = MY_PROVE_HYP all_th (inst_t all_hd) in
456 th_hd :: get_all_raw th_tl t_tm
457 else
458 [] in
459 get_all_raw th list_tm;;
460
461
462
463 (* Given a theorem `ALL P list`, returns (P x_i1),..., (P x_in)
464 where i1,...,in are given indices.
465 The list of indices should be sorted *)
466 let select_all th indices =
467 let ltm, list_tm = dest_comb (concl th) in
468 let p_tm = rand ltm in
469 let list_ty = type_of list_tm in
470 let p_ty = type_of p_tm in
471 let ty = (hd o snd o dest_type) list_ty in
472 let p_var = mk_var("P", p_ty) in
473 let h_var = mk_var("h", ty) in
474 let t_var = mk_var("t", list_ty) in
475
476 let inst_t = INST[p_tm, p_var] o INST_TYPE[ty, aty] in
477 let all_hd, all_tl = inst_t ALL_A_HD, inst_t ALL_A_TL in
478
479 let rec get_all_raw all_th list_tm indices n =
480 match indices with
481 [] -> []
482 | i::is ->
483 let h_tm', t_tm = dest_comb list_tm in
484 let h_tm = rand h_tm' in
485 let inst_t = INST[h_tm, h_var; t_tm, t_var] in
486 let th_tl = MY_PROVE_HYP all_th (inst_t all_tl) in
487
488 if (i - n = 0) then
489 let th_hd = MY_PROVE_HYP all_th (inst_t all_hd) in
490 th_hd :: get_all_raw th_tl t_tm is (n + 1)
491 else
492 get_all_raw th_tl t_tm (i::is) (n + 1) in
493 get_all_raw th list_tm indices 0;;
494
495
496 (*****************************************)
497 (* set_of_list conversions *)
498
499 let SET_OF_LIST_A_EMPTY = prove(`set_of_list ([]:(A)list) = {}`, REWRITE_TAC[set_of_list]) and
500 SET_OF_LIST_A_H = prove(`set_of_list [h:A] = {h}`, REWRITE_TAC[set_of_list]) and
501 SET_OF_LIST_A_CONS = prove(`set_of_list (CONS (h:A) t) = h INSERT set_of_list t`, REWRITE_TAC[set_of_list]);;
502
503
504 let set_of_list_conv tm =
505 let list_tm = rand tm in
506 let list_ty = type_of list_tm in
507 let ty = (hd o snd o dest_type) list_ty in
508 let h_var = mk_var("h", ty) in
509 let t_var = mk_var("t", list_ty) in
510 let inst_t = INST_TYPE[ty, aty] in
511 let set_of_list_h, set_of_list_cons = inst_t SET_OF_LIST_A_H, inst_t SET_OF_LIST_A_CONS in
512
513 let rec set_of_list_conv_raw = fun h_tm t_tm ->
514 if (is_comb t_tm) then
515 let h_tm', t_tm' = dest_comb t_tm in
516 let th0 = INST[h_tm, h_var; t_tm, t_var] set_of_list_cons in
517 let ltm, rtm = dest_comb(rand(concl th0)) in
518 TRANS th0 (AP_TERM ltm (set_of_list_conv_raw (rand h_tm') t_tm'))
519 else
520 INST[h_tm, h_var] set_of_list_h in
521
522 if (is_comb list_tm) then
523 let h_tm, t_tm = dest_comb list_tm in
524 set_of_list_conv_raw (rand h_tm) t_tm
525 else
526 inst_t SET_OF_LIST_A_EMPTY;;
527
528
529 end;;