| 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;; |