| 1 |
module Ssreflect = struct |
| 2 |
|
| 3 |
(* A special definition for introducing equalities with the construction move eq: a => b *) |
| 4 |
let ssreflect_eq_def = new_definition `!v P. ssreflect_eq (v:A) (P:bool) = P`;; |
| 5 |
|
| 6 |
|
| 7 |
(* Generalizes given variables in a term *) |
| 8 |
let gen_variables binders tm = |
| 9 |
if type_of tm <> bool_ty then |
| 10 |
if length binders = 0 then tm |
| 11 |
else |
| 12 |
failwith "gen_variables: bool term is required" |
| 13 |
else |
| 14 |
let f_vars = map dest_var (frees tm) in |
| 15 |
let find_type name = assoc name f_vars in |
| 16 |
let gen_variable var_name tm = |
| 17 |
let var = |
| 18 |
try mk_var (var_name, find_type var_name) |
| 19 |
with Failure _ -> |
| 20 |
failwith ("gen_variables: variable "^var_name |
| 21 |
^" is not free in the term "^(string_of_term tm)) in |
| 22 |
mk_forall (var, tm) in |
| 23 |
itlist gen_variable binders tm;; |
| 24 |
|
| 25 |
|
| 26 |
(* Combined type of theorems and terms *) |
| 27 |
type arg_type = Arg_theorem of thm | Arg_term of term | Arg_type of hol_type;; |
| 28 |
|
| 29 |
let get_arg_thm arg = |
| 30 |
match arg with |
| 31 |
| Arg_theorem th -> th |
| 32 |
| _ -> failwith "A theorem expected";; |
| 33 |
|
| 34 |
let get_arg_term arg = |
| 35 |
match arg with |
| 36 |
| Arg_term tm -> tm |
| 37 |
| _ -> failwith "A term expected";; |
| 38 |
|
| 39 |
let get_arg_type arg = |
| 40 |
match arg with |
| 41 |
| Arg_type ty -> ty |
| 42 |
| _ -> failwith "A type expected";; |
| 43 |
|
| 44 |
|
| 45 |
(* Converts a theorem tactic into a tactic which accepts thm_term arguments *) |
| 46 |
let thm_tac (ttac : thm_tactic) = ttac o get_arg_thm;; |
| 47 |
let term_tac (ttac : term -> tactic) = ttac o get_arg_term;; |
| 48 |
let type_tac (ttac : hol_type -> tactic) arg = ttac o get_arg_type;; |
| 49 |
|
| 50 |
|
| 51 |
let conv_thm_tac (ttac : thm_tactic->tactic) (arg_tac : arg_type->tactic) = |
| 52 |
ttac (fun th -> arg_tac (Arg_theorem th));; |
| 53 |
|
| 54 |
|
| 55 |
|
| 56 |
(* Based on the code from tactics.ml *) |
| 57 |
(* Applies the second tactic to either the first subgoal or |
| 58 |
the last subgoal *) |
| 59 |
let (THENL_FIRST),(THENL_LAST) = |
| 60 |
let propagate_empty i [] = [] |
| 61 |
and propagate_thm th i [] = INSTANTIATE_ALL i th in |
| 62 |
let compose_justs n just1 just2 i ths = |
| 63 |
let ths1,ths2 = chop_list n ths in |
| 64 |
(just1 i ths1)::(just2 i ths2) in |
| 65 |
let rec seqapply l1 l2 = match (l1,l2) with |
| 66 |
([],[]) -> null_meta,[],propagate_empty |
| 67 |
| ((tac:tactic)::tacs),((goal:goal)::goals) -> |
| 68 |
let ((mvs1,insts1),gls1,just1) = tac goal in |
| 69 |
let goals' = map (inst_goal insts1) goals in |
| 70 |
let ((mvs2,insts2),gls2,just2) = seqapply tacs goals' in |
| 71 |
((union mvs1 mvs2,compose_insts insts1 insts2), |
| 72 |
gls1@gls2,compose_justs (length gls1) just1 just2) |
| 73 |
| _,_ -> failwith "seqapply: Length mismatch" in |
| 74 |
let justsequence just1 just2 insts2 i ths = |
| 75 |
just1 (compose_insts insts2 i) (just2 i ths) in |
| 76 |
let tacsequence ((mvs1,insts1),gls1,just1) tacl = |
| 77 |
let ((mvs2,insts2),gls2,just2) = seqapply tacl gls1 in |
| 78 |
let jst = justsequence just1 just2 insts2 in |
| 79 |
let just = if gls2 = [] then propagate_thm (jst null_inst []) else jst in |
| 80 |
((union mvs1 mvs2,compose_insts insts1 insts2),gls2,just) in |
| 81 |
let (thenl_first: tactic -> tactic -> tactic) = |
| 82 |
fun tac1 tac2 g -> |
| 83 |
let _,gls,_ as gstate = tac1 g in |
| 84 |
if gls = [] then failwith "No subgoals" |
| 85 |
else |
| 86 |
let tac_list = tac2 :: (replicate ALL_TAC (length gls - 1)) in |
| 87 |
tacsequence gstate tac_list |
| 88 |
and (thenl_last: tactic -> tactic -> tactic) = |
| 89 |
fun tac1 tac2 g -> |
| 90 |
let _,gls,_ as gstate = tac1 g in |
| 91 |
if gls = [] then failwith "No subgoals" |
| 92 |
else |
| 93 |
let tac_list = (replicate ALL_TAC (length gls - 1)) @ [tac2] in |
| 94 |
tacsequence gstate tac_list in |
| 95 |
thenl_first, thenl_last;; |
| 96 |
|
| 97 |
|
| 98 |
(* Rotates the goalstack *) |
| 99 |
let (THENL_ROT: int -> tactic -> tactic) = |
| 100 |
fun n tac g -> |
| 101 |
let gstate = tac g in |
| 102 |
rotate n gstate;; |
| 103 |
|
| 104 |
|
| 105 |
(* Repeats the given tactic exactly n times and then repeats the same tactic at most m times *) |
| 106 |
let repeat_tactic n m tac = |
| 107 |
let rec replicate_at_most m tac = |
| 108 |
if m <= 0 then ALL_TAC else (tac THEN replicate_at_most (m - 1) tac) ORELSE ALL_TAC in |
| 109 |
REPLICATE_TAC n tac THEN replicate_at_most m tac;; |
| 110 |
|
| 111 |
|
| 112 |
|
| 113 |
(* Returns all free variables in the goal *) |
| 114 |
let get_context_vars (g : goal) = |
| 115 |
let list, g_tm = g in |
| 116 |
let tms = g_tm :: map (concl o snd) list in |
| 117 |
let f_vars = setify (flat (map frees tms)) in |
| 118 |
map (fun v -> ((fst o dest_var) v, v)) f_vars;; |
| 119 |
|
| 120 |
|
| 121 |
(* Clears the given assumption *) |
| 122 |
let clear_assumption name = |
| 123 |
TRY (REMOVE_THEN name (fun th -> ALL_TAC));; |
| 124 |
|
| 125 |
|
| 126 |
(* DISCH_THEN (LABEL_TAC name) for assumptions and X_GEN_TAC name for variables *) |
| 127 |
let move labels = |
| 128 |
(* Automatically introduces an assumption for a top-level ssreflect_eq *) |
| 129 |
let move_eq (g:goal) = |
| 130 |
let g_tm = snd g in |
| 131 |
let tac = |
| 132 |
try |
| 133 |
let eq_tm = (rator o fst o dest_imp) g_tm in |
| 134 |
if (fst o dest_const o rator) eq_tm = "ssreflect_eq" then |
| 135 |
let label = (fst o dest_var o rand) eq_tm in |
| 136 |
DISCH_THEN (LABEL_TAC label o PURE_ONCE_REWRITE_RULE[ssreflect_eq_def]) |
| 137 |
else |
| 138 |
ALL_TAC |
| 139 |
with Failure _ -> ALL_TAC in |
| 140 |
tac g in |
| 141 |
|
| 142 |
let move1 name (g:goal) = |
| 143 |
let g_tm = snd g in |
| 144 |
let tac = |
| 145 |
if is_forall g_tm then |
| 146 |
let tm0, g_tm1 = dest_forall g_tm in |
| 147 |
let tm = mk_var (name, type_of tm0) in |
| 148 |
if name = "_" then |
| 149 |
GEN_TAC |
| 150 |
else |
| 151 |
X_GEN_TAC tm |
| 152 |
else |
| 153 |
if is_imp g_tm then |
| 154 |
if name = "_" then |
| 155 |
DISCH_THEN (fun th -> ALL_TAC) |
| 156 |
else |
| 157 |
DISCH_THEN (LABEL_TAC name) |
| 158 |
else |
| 159 |
failwith "move: not (!) or (==>)" in |
| 160 |
tac g in |
| 161 |
fun g -> |
| 162 |
let tac = itlist |
| 163 |
(fun name tac -> move_eq THEN move1 name THEN tac) labels ALL_TAC in |
| 164 |
tac g;; |
| 165 |
|
| 166 |
|
| 167 |
(* Localization tactical *) |
| 168 |
let in_tac a_list in_goal tac (g:goal) = |
| 169 |
let goal_tm = snd g in |
| 170 |
let tmp_goal_name = "$_goal_$" in |
| 171 |
let tmp_goal_var = mk_var (tmp_goal_name, bool_ty) in |
| 172 |
let tmp_goal = mk_eq (tmp_goal_var, goal_tm) in |
| 173 |
let tmp_goal_sym = mk_eq (goal_tm, tmp_goal_var) in |
| 174 |
let disch_tac = |
| 175 |
rev_itlist (fun name tac -> REMOVE_THEN name MP_TAC THEN tac) a_list ALL_TAC in |
| 176 |
let intro_tac = move a_list in |
| 177 |
let hide_goal, unfold_goal = |
| 178 |
if in_goal then |
| 179 |
ALL_TAC, ALL_TAC |
| 180 |
else |
| 181 |
ABBREV_TAC tmp_goal, |
| 182 |
EXPAND_TAC tmp_goal_name THEN |
| 183 |
UNDISCH_TAC tmp_goal_sym THEN DISCH_THEN (fun th -> ALL_TAC) |
| 184 |
in |
| 185 |
(hide_goal THEN disch_tac THEN tac THEN TRY intro_tac THEN unfold_goal) g;; |
| 186 |
|
| 187 |
|
| 188 |
|
| 189 |
(* Finds a subterm in the given term which matches against the given |
| 190 |
pattern; local_consts is a list of variable which must be fixed in |
| 191 |
the pattern. |
| 192 |
This function returns the path to the first matched subterm *) |
| 193 |
let match_subterm local_consts pat tm = |
| 194 |
let rec find tm path = |
| 195 |
try |
| 196 |
let inst = term_match local_consts pat tm in |
| 197 |
if instantiate inst pat = tm then path else failwith "Bad instantiation" |
| 198 |
with x -> |
| 199 |
try |
| 200 |
match tm with |
| 201 |
| Abs(_, b_tm) -> find b_tm (path^"b") |
| 202 |
| Comb(l_tm, r_tm) -> |
| 203 |
try find l_tm (path^"l") |
| 204 |
with Failure _ -> find r_tm (path^"r") |
| 205 |
| _ -> failwith "match_subterm: no match" |
| 206 |
with x -> |
| 207 |
failwith ("match_subterm: no match: "^string_of_term pat) in |
| 208 |
find tm "";; |
| 209 |
|
| 210 |
|
| 211 |
|
| 212 |
(* Returns paths to all subterms satisfying p *) |
| 213 |
let find_all_paths p tm = |
| 214 |
let rec find_path p tm path = |
| 215 |
let paths = |
| 216 |
match tm with |
| 217 |
| Abs(_, b_tm) -> |
| 218 |
find_path p b_tm (path ^ "b") |
| 219 |
| Comb(l_tm, r_tm) -> |
| 220 |
(find_path p l_tm (path ^ "l")) @ (find_path p r_tm (path ^ "r")) |
| 221 |
| _ -> [] in |
| 222 |
if p tm then path :: paths else paths in |
| 223 |
find_path p tm "";; |
| 224 |
|
| 225 |
|
| 226 |
(* Instantiates types of the given context variables in the given term.*) |
| 227 |
let inst_context_vars vars tm_vars tm = |
| 228 |
let find_type var = |
| 229 |
let name, ty = dest_var var in |
| 230 |
try |
| 231 |
(ty, type_of (assoc name vars)) |
| 232 |
with Failure _ -> |
| 233 |
failwith (name^" is free in the term `"^(string_of_term tm)^"` and in the context") in |
| 234 |
let ty_src, ty_dst = unzip (map find_type tm_vars) in |
| 235 |
let ty_inst = itlist2 type_match ty_src ty_dst [] in |
| 236 |
inst ty_inst tm;; |
| 237 |
|
| 238 |
|
| 239 |
(* Instantiates types of all free variables in the term using the context *) |
| 240 |
let inst_all_free_vars tm (g : goal) = |
| 241 |
let context_vars = get_context_vars g in |
| 242 |
let f_vars = frees tm in |
| 243 |
inst_context_vars context_vars f_vars tm;; |
| 244 |
|
| 245 |
|
| 246 |
(* Finds a subterm corresponding to the given pattern. |
| 247 |
Before matching, the term types are instantiated in the given context. *) |
| 248 |
let match_subterm_in_context pat tm (g : goal) = |
| 249 |
let context_vars = get_context_vars g in |
| 250 |
let f0_vars = filter (fun tm -> ((fst o dest_var) tm).[0] <> '_') (frees pat) in |
| 251 |
let pattern = inst_context_vars context_vars f0_vars pat in |
| 252 |
let f1_vars = filter (fun tm -> ((fst o dest_var) tm).[0] <> '_') (frees pattern) in |
| 253 |
match_subterm f1_vars pattern tm;; |
| 254 |
|
| 255 |
|
| 256 |
(*************************) |
| 257 |
(* Rewriting *) |
| 258 |
(*************************) |
| 259 |
|
| 260 |
(* Breaks conjunctions and does other misc stuff *) |
| 261 |
let rec break_conjuncts th : thm list = |
| 262 |
(* Convert P ==> (!x. Q x) to !x. P ==> Q x and P ==> Q ==> R to P /\ Q ==> R *) |
| 263 |
let th0 = PURE_REWRITE_RULE[GSYM RIGHT_FORALL_IMP_THM; IMP_IMP] th in |
| 264 |
let th1 = SPEC_ALL th0 in |
| 265 |
(* Break top level conjunctions *) |
| 266 |
let th_list = CONJUNCTS th1 in |
| 267 |
if length th_list > 1 then |
| 268 |
List.concat (map break_conjuncts th_list) |
| 269 |
else |
| 270 |
let th_tm = concl th1 in |
| 271 |
(* Deal with assumptions *) |
| 272 |
if is_imp th_tm then |
| 273 |
let a_tm = lhand th_tm in |
| 274 |
let th_list = break_conjuncts (UNDISCH th1) in |
| 275 |
map (DISCH a_tm) th_list |
| 276 |
else |
| 277 |
if is_eq th_tm then [th1] |
| 278 |
else |
| 279 |
if is_neg th_tm then |
| 280 |
[PURE_ONCE_REWRITE_RULE[TAUT `~P <=> (P <=> F)`] th1] |
| 281 |
else |
| 282 |
[EQT_INTRO th1];; |
| 283 |
|
| 284 |
|
| 285 |
(* Finds an instantination for the given term inside another term *) |
| 286 |
let rec find_term_inst local_consts tm src_tm path = |
| 287 |
try (term_match local_consts tm src_tm, true, path) |
| 288 |
with Failure _ -> |
| 289 |
match src_tm with |
| 290 |
| Comb(l_tm, r_tm) -> |
| 291 |
let r_inst, flag, s = find_term_inst local_consts tm l_tm (path ^ "l") in |
| 292 |
if flag then (r_inst, flag, s) |
| 293 |
else |
| 294 |
find_term_inst local_consts tm r_tm (path ^ "r") |
| 295 |
| Abs(_, b_tm) -> |
| 296 |
find_term_inst local_consts tm b_tm (path ^ "b") |
| 297 |
| _ -> (([],[],[]), false, path);; |
| 298 |
|
| 299 |
|
| 300 |
|
| 301 |
(* Rewrites the subterm at the given path using the given equation theorem *) |
| 302 |
let path_rewrite path th tm = |
| 303 |
let rec build path tm = |
| 304 |
let n = String.length path in |
| 305 |
if n = 0 then |
| 306 |
th |
| 307 |
else |
| 308 |
let ch = path.[0] in |
| 309 |
let path' = String.sub path 1 (n - 1) in |
| 310 |
if ch = 'l' then |
| 311 |
let lhs, rhs = dest_comb tm in |
| 312 |
let th0 = build path' lhs in |
| 313 |
AP_THM th0 rhs |
| 314 |
else if ch = 'r' then |
| 315 |
let lhs, rhs = dest_comb tm in |
| 316 |
let th0 = build path' rhs in |
| 317 |
AP_TERM lhs th0 |
| 318 |
else if ch = 'b' then |
| 319 |
let var, body = dest_abs tm in |
| 320 |
let th0 = build path' body in |
| 321 |
try ABS var th0 |
| 322 |
with Failure _ -> failwith ("ABS failed: (" ^ string_of_term var ^ ", " ^ string_of_thm th0) |
| 323 |
else |
| 324 |
failwith ("Bad path symbol: "^path) in |
| 325 |
let res = build path tm in |
| 326 |
let lhs = (lhand o concl) res in |
| 327 |
if not (aconv lhs tm) then failwith ("path_rewrite: incorrect result [required: "^ |
| 328 |
(string_of_term tm)^"; obtained: "^ |
| 329 |
(string_of_term lhs)) |
| 330 |
else |
| 331 |
res;; |
| 332 |
|
| 333 |
|
| 334 |
let new_rewrite occ pat th g = |
| 335 |
let goal_tm = snd g in |
| 336 |
(* Free variables in the given theorem will not be matched *) |
| 337 |
let local_consts = frees (concl th) in |
| 338 |
(* Apply the pattern *) |
| 339 |
let goal_subterm_path = |
| 340 |
if pat = [] then "" else match_subterm_in_context (hd pat) goal_tm g in |
| 341 |
let goal_subterm = follow_path goal_subterm_path goal_tm in |
| 342 |
|
| 343 |
(* Local rewrite function *) |
| 344 |
let rewrite th = |
| 345 |
let concl_th = concl th in |
| 346 |
let cond_flag = is_imp concl_th in |
| 347 |
let match_fun = lhs o (if cond_flag then rand else I) in |
| 348 |
|
| 349 |
(* Match the theorem *) |
| 350 |
let lhs_tm = match_fun concl_th in |
| 351 |
let ii, flag, path = find_term_inst local_consts lhs_tm goal_subterm goal_subterm_path in |
| 352 |
if not flag then |
| 353 |
failwith (string_of_term lhs_tm ^ " does not match any subterm in the goal") |
| 354 |
else |
| 355 |
let matched_th = INSTANTIATE ii th in |
| 356 |
let matched_tm = (match_fun o concl) matched_th in |
| 357 |
|
| 358 |
(* Find all matched subterms *) |
| 359 |
let paths = find_all_paths (fun x -> aconv x matched_tm) goal_tm in |
| 360 |
let paths = if occ = [] then paths else |
| 361 |
map (fun i -> List.nth paths (i - 1)) occ in |
| 362 |
|
| 363 |
(* Find all free variables in the matched theorem which do not correspond to free variables in |
| 364 |
the matched subterm *) |
| 365 |
let tm_frees = frees matched_tm in |
| 366 |
let mth_frees = frees (concl matched_th) in |
| 367 |
let vars = subtract mth_frees (union local_consts tm_frees) in |
| 368 |
if vars = [] then |
| 369 |
(* Construct the tactic for rewriting *) |
| 370 |
let r_tac = fun th -> MAP_EVERY (fun path -> CONV_TAC (path_rewrite path th)) paths in |
| 371 |
if cond_flag then |
| 372 |
MP_TAC matched_th THEN ANTS_TAC THENL [ALL_TAC; DISCH_THEN r_tac] |
| 373 |
else |
| 374 |
r_tac matched_th |
| 375 |
else |
| 376 |
let rec gen_vars vars th = |
| 377 |
match vars with |
| 378 |
| v :: vs -> gen_vars vs (GEN v th) |
| 379 |
| [] -> th in |
| 380 |
let th2 = gen_vars vars matched_th in |
| 381 |
MP_TAC th2 THEN PURE_REWRITE_TAC[LEFT_IMP_FORALL_THM] in |
| 382 |
|
| 383 |
(* Try to rewrite with all given theorems *) |
| 384 |
let th_list = break_conjuncts th in |
| 385 |
let rec my_first th_list = |
| 386 |
if length th_list = 1 then |
| 387 |
rewrite (hd th_list) g |
| 388 |
else |
| 389 |
try rewrite (hd th_list) g |
| 390 |
with Failure _ -> my_first (tl th_list) in |
| 391 |
my_first th_list;; |
| 392 |
|
| 393 |
|
| 394 |
(* |
| 395 |
let th = ARITH_RULE `!n. n * 0 <= 1`;; |
| 396 |
let tm = `m * 0 <= 1 <=> T`;; |
| 397 |
g tm;; |
| 398 |
e(new_rewrite [] [] th);; |
| 399 |
|
| 400 |
let th = CONJ REAL_MUL_RINV REAL_MUL_LINV;; |
| 401 |
let tm = `inv (x - y) * (x - y) + &1 = &1 + inv (x - y) * (x - y) + x * inv x`;; |
| 402 |
let tm0 = `!x. inv (x - y) * (x - y) = &1`;; |
| 403 |
|
| 404 |
|
| 405 |
g tm0;; |
| 406 |
e(new_rewrite [] [] (th));; |
| 407 |
e(new_rewrite [] [] (GSYM th));; |
| 408 |
e(new_rewrite [] [`_ + &1`] th);; |
| 409 |
|
| 410 |
g(`x < 2`);; |
| 411 |
e(new_rewrite [] [] (ARITH_RULE `!x. x > 2 ==> (!n. n = 2 ==> ~(x < n))`));; |
| 412 |
|
| 413 |
*) |
| 414 |
|
| 415 |
|
| 416 |
(* Rewrite tactic for usual and conditional theorems *) |
| 417 |
let rewrite occ pat th g = |
| 418 |
let rec match_theorem ffun th tm str = |
| 419 |
try (PART_MATCH ffun th tm, true, str) |
| 420 |
with Failure _ -> |
| 421 |
match tm with |
| 422 |
| Comb(l_tm, r_tm) -> |
| 423 |
let r_th, flag, s = match_theorem ffun th l_tm (str ^ "l") in |
| 424 |
if flag then (r_th, flag, s) |
| 425 |
else |
| 426 |
match_theorem ffun th r_tm (str ^ "r") |
| 427 |
| Abs(_, b_tm) -> |
| 428 |
match_theorem ffun th b_tm (str ^ "b") |
| 429 |
| _ -> (th, false, str) in |
| 430 |
(* Initialize auxiliary variables *) |
| 431 |
let goal_tm = snd g in |
| 432 |
let th0 = PURE_REWRITE_RULE[IMP_IMP] th in |
| 433 |
let concl_th = concl (SPEC_ALL th0) in |
| 434 |
let cond_flag = is_imp concl_th in |
| 435 |
let eq_tm = if cond_flag then rand concl_th else concl_th in |
| 436 |
let match_fun = (if is_eq eq_tm then lhand else I) o (if cond_flag then rand else I) in |
| 437 |
|
| 438 |
(* Apply the pattern *) |
| 439 |
let goal_subterm_path = |
| 440 |
if pat = [] then "" else match_subterm_in_context (hd pat) goal_tm g in |
| 441 |
let goal_subterm = follow_path goal_subterm_path goal_tm in |
| 442 |
|
| 443 |
(* Match the theorem *) |
| 444 |
let matched_th, flag, path = match_theorem match_fun th0 goal_subterm goal_subterm_path in |
| 445 |
if not flag then |
| 446 |
failwith "lhs does not match any term in the goal" |
| 447 |
else |
| 448 |
let matched_tm = (match_fun o concl) matched_th in |
| 449 |
(* Find all matched subterms *) |
| 450 |
let paths = find_all_paths (fun x -> x = matched_tm) goal_tm in |
| 451 |
let paths = if occ = [] then paths else |
| 452 |
map (fun i -> List.nth paths (i - 1)) occ in |
| 453 |
(* Find all free variables in the matched theorem which do not correspond to free variables in |
| 454 |
the matched subterm *) |
| 455 |
let tm_frees = frees matched_tm in |
| 456 |
let th_frees = frees (concl th0) in |
| 457 |
let mth_frees = frees (concl matched_th) in |
| 458 |
let vars = subtract mth_frees (union th_frees tm_frees) in |
| 459 |
if vars = [] then |
| 460 |
let r_tac = fun th -> MAP_EVERY (fun path -> GEN_REWRITE_TAC (PATH_CONV path) [th]) paths in |
| 461 |
if cond_flag then |
| 462 |
(MP_TAC matched_th THEN ANTS_TAC THENL [ALL_TAC; DISCH_THEN r_tac]) g |
| 463 |
else |
| 464 |
(r_tac matched_th) g |
| 465 |
else |
| 466 |
let rec gen_vars vars th = |
| 467 |
match vars with |
| 468 |
| v :: vs -> gen_vars vs (GEN v th) |
| 469 |
| [] -> th in |
| 470 |
let th2 = gen_vars vars matched_th in |
| 471 |
(MP_TAC th2 THEN REWRITE_TAC[LEFT_IMP_FORALL_THM]) g;; |
| 472 |
|
| 473 |
|
| 474 |
|
| 475 |
|
| 476 |
(* Analogue of the "done" tactic in SSReflect *) |
| 477 |
let done_tac = ASM_REWRITE_TAC[] THEN FAIL_TAC "done: not all subgoals are proved";; |
| 478 |
|
| 479 |
(* Simplification: /= *) |
| 480 |
let simp_tac = SIMP_TAC[];; |
| 481 |
|
| 482 |
|
| 483 |
(* Linear arithmetic simplification *) |
| 484 |
let arith_tac = FIRST [ARITH_TAC; REAL_ARITH_TAC; INT_ARITH_TAC];; |
| 485 |
|
| 486 |
|
| 487 |
(* split *) |
| 488 |
let split_tac = FIRST [CONJ_TAC; EQ_TAC];; |
| 489 |
|
| 490 |
|
| 491 |
|
| 492 |
(* Creates an abbreviation for the given term with the given name *) |
| 493 |
let set_tac name tm (g : goal) = |
| 494 |
let goal_tm = snd g in |
| 495 |
let tm0 = |
| 496 |
try |
| 497 |
follow_path (match_subterm_in_context tm goal_tm g) goal_tm |
| 498 |
with Failure _ -> tm in |
| 499 |
let tm1 = inst_all_free_vars tm0 g in |
| 500 |
let abbrev_tm = mk_eq (mk_var (name, type_of tm1), tm1) in |
| 501 |
(ABBREV_TAC abbrev_tm THEN POP_ASSUM (LABEL_TAC (name ^ "_def"))) g;; |
| 502 |
|
| 503 |
(* Generates a fresh name for the given term *) |
| 504 |
(* taking into account names of the provided variables *) |
| 505 |
let generate_fresh_name names tm = |
| 506 |
let rec find_name prefix n = |
| 507 |
let name = prefix ^ (if n = 0 then "" else string_of_int n) in |
| 508 |
if can (find (fun str -> str = name)) names then |
| 509 |
find_name prefix (n + 1) |
| 510 |
else |
| 511 |
name in |
| 512 |
let prefix = if is_var tm then (fst o dest_var) tm else "x" in |
| 513 |
find_name prefix 0;; |
| 514 |
|
| 515 |
|
| 516 |
(* Returns a variable which name does not conflict with names of given vars *) |
| 517 |
let get_fresh_var var vars = |
| 518 |
let names = map (fst o dest_var) vars in |
| 519 |
mk_var (generate_fresh_name names var, type_of var);; |
| 520 |
|
| 521 |
|
| 522 |
(* Matches all wild cards in the term and *) |
| 523 |
(* instantinates all type variables in the given context *) |
| 524 |
let prepare_term tm (g : goal) = |
| 525 |
let goal_tm = snd g in |
| 526 |
let tm0 = |
| 527 |
try follow_path (match_subterm_in_context tm goal_tm g) goal_tm |
| 528 |
with Failure _ -> tm in |
| 529 |
inst_all_free_vars tm0 g;; |
| 530 |
|
| 531 |
(* Discharges a term by generalizing all occurences of this term first *) |
| 532 |
let disch_tm_tac occs tm (g : goal) = |
| 533 |
let tm0 = prepare_term tm g in |
| 534 |
let name = generate_fresh_name ((fst o unzip) (get_context_vars g)) tm in |
| 535 |
let new_tm = mk_var (name, type_of tm0) in |
| 536 |
let new_tm1 = |
| 537 |
if occs = [] && is_var tm then |
| 538 |
mk_var ((fst o dest_var) tm, type_of tm0) |
| 539 |
else new_tm in |
| 540 |
let abbrev_tm = mk_eq (new_tm, tm0) in |
| 541 |
(ABBREV_TAC abbrev_tm THEN |
| 542 |
EXPAND_TAC name THEN |
| 543 |
POP_ASSUM (fun th -> TRY (new_rewrite occs [] th)) THEN |
| 544 |
SPEC_TAC (new_tm, new_tm1)) g;; |
| 545 |
|
| 546 |
|
| 547 |
(* Discharges a theorem or a term *) |
| 548 |
let disch_tac occs arg = |
| 549 |
match arg with |
| 550 |
| Arg_theorem th -> MP_TAC th |
| 551 |
| Arg_term tm -> disch_tm_tac occs tm |
| 552 |
| _ -> failwith "disch_tac: a type cannot be discharged";; |
| 553 |
|
| 554 |
|
| 555 |
|
| 556 |
(* process_thm *) |
| 557 |
let process_thm = |
| 558 |
let conj_imp = TAUT `(A /\ B ==> C) ==> (A ==> B ==> C)` in |
| 559 |
let dummy_tm = `F` in |
| 560 |
fun local_consts -> |
| 561 |
let rec process th = |
| 562 |
let ctm = concl th in |
| 563 |
(* forall *) |
| 564 |
if is_forall ctm then |
| 565 |
let (var_tm, _) = dest_forall ctm in |
| 566 |
let var = get_fresh_var var_tm (thm_frees th @ local_consts) in |
| 567 |
let th1 = SPEC var th in |
| 568 |
let list, th0 = process th1 in |
| 569 |
("spec", var) :: list, th0 |
| 570 |
(* P ==> Q *) |
| 571 |
else if is_imp ctm then |
| 572 |
let ant_tm, _ = dest_imp ctm in |
| 573 |
(* P /\ R ==> Q *) |
| 574 |
if is_conj ant_tm then |
| 575 |
let th1 = MATCH_MP conj_imp th in |
| 576 |
let list, th0 = process th1 in |
| 577 |
("conj", dummy_tm) :: list, th0 |
| 578 |
(* P ==> Q *) |
| 579 |
else |
| 580 |
let th1 = UNDISCH th in |
| 581 |
let list, th0 = process th1 in |
| 582 |
("undisch", ant_tm) :: list, th0 |
| 583 |
else |
| 584 |
[], th in |
| 585 |
process;; |
| 586 |
|
| 587 |
|
| 588 |
|
| 589 |
(* reconstruct_thm *) |
| 590 |
let reconstruct_thm = |
| 591 |
let imp_conj = TAUT `(A ==> B ==> C) ==> (A /\ B ==> C)` in |
| 592 |
let triv_ths = TAUT `((T ==> A) <=> A) /\ ((T /\ A) = A) /\ ((A /\ T) = A)` in |
| 593 |
let rec reconstruct list th = |
| 594 |
match list with |
| 595 |
| [] -> th |
| 596 |
| cmd :: t -> |
| 597 |
let th1 = |
| 598 |
match cmd with |
| 599 |
| ("spec", (_ as tm)) -> GEN tm th |
| 600 |
| ("conj", _) -> MATCH_MP imp_conj th |
| 601 |
| ("undisch", (_ as tm)) -> DISCH tm th |
| 602 |
| _ -> failwith ("Unknown command: " ^ fst cmd) in |
| 603 |
reconstruct t th1 in |
| 604 |
|
| 605 |
fun (cmd_list, th) -> |
| 606 |
let th1 = reconstruct (rev cmd_list) th in |
| 607 |
PURE_REWRITE_RULE[triv_ths] th1;; |
| 608 |
|
| 609 |
|
| 610 |
(* spec_var_th *) |
| 611 |
let spec_var_th th n tm = |
| 612 |
let cmd, th0 = process_thm (frees tm) th in |
| 613 |
let ty = type_of tm in |
| 614 |
let rec spec n list head = |
| 615 |
match list with |
| 616 |
| ("spec", (_ as var_tm)) :: t -> |
| 617 |
(try |
| 618 |
let ty_ii = type_match (type_of var_tm) ty [] in |
| 619 |
if n <= 1 then |
| 620 |
let th1 = reconstruct_thm (list, th0) in |
| 621 |
let th2 = ISPEC tm th1 in |
| 622 |
let tail, th0 = process_thm [] th2 in |
| 623 |
let head1 = map (fun s, tm -> s, inst ty_ii tm) head in |
| 624 |
head1 @ tail, th0 |
| 625 |
else |
| 626 |
spec (n - 1) t (head @ [hd list]) |
| 627 |
with Failure _ -> |
| 628 |
spec n t (head @ [hd list])) |
| 629 |
| h :: t -> spec n t (head @ [h]) |
| 630 |
| [] -> failwith ("spec_var_th") in |
| 631 |
reconstruct_thm (spec n cmd []);; |
| 632 |
|
| 633 |
|
| 634 |
(* match_mp_th *) |
| 635 |
let match_mp_th ith n th = |
| 636 |
let lconsts = thm_frees ith in |
| 637 |
let cmd, th0 = process_thm (thm_frees th) ith in |
| 638 |
let tm = concl th in |
| 639 |
let rec rec_match n list head = |
| 640 |
match list with |
| 641 |
| ("undisch", (_ as tm0)) :: t -> |
| 642 |
(try |
| 643 |
let ii = term_match lconsts tm0 tm in |
| 644 |
if n <= 1 then |
| 645 |
let th1 = INSTANTIATE_ALL ii th0 in |
| 646 |
let th2 = PROVE_HYP th th1 in |
| 647 |
let list0 = head @ (("undisch", `T`) :: t) in |
| 648 |
let f_vars = frees tm0 in |
| 649 |
let list1 = filter |
| 650 |
(fun s, tm -> not (s = "spec" && mem tm f_vars)) list0 in |
| 651 |
let list = map (fun s, tm -> s, instantiate ii tm) list1 in |
| 652 |
list, th2 |
| 653 |
else |
| 654 |
rec_match (n - 1) t (head @ [hd list]) |
| 655 |
with Failure _ -> |
| 656 |
rec_match n t (head @ [hd list])) |
| 657 |
| h :: t -> rec_match n t (head @ [h]) |
| 658 |
| [] -> failwith "match_mp_th: no match" in |
| 659 |
let r = rec_match n cmd [] in |
| 660 |
reconstruct_thm r;; |
| 661 |
|
| 662 |
(* Introduces a subgoal *) |
| 663 |
let have_gen_tac binders then_tac tm (g : goal) = |
| 664 |
(* let tm0 = inst_all_free_vars tm g in *) |
| 665 |
let tm1 = gen_variables binders tm in |
| 666 |
let tm2 = prepare_term tm1 g in |
| 667 |
(THENL_FIRST (SUBGOAL_THEN tm2 (fun th -> MP_TAC th THEN then_tac)) |
| 668 |
(move binders)) g;; |
| 669 |
|
| 670 |
|
| 671 |
let have_tac then_tac tm (g : goal) = |
| 672 |
(* let tm0 = inst_all_free_vars tm g in *) |
| 673 |
let tm0 = prepare_term tm g in |
| 674 |
(SUBGOAL_THEN tm0 (fun th -> MP_TAC th THEN then_tac)) g;; |
| 675 |
|
| 676 |
|
| 677 |
|
| 678 |
(* 'wlog' tactic *) |
| 679 |
let wlog_tac then_tac vars tm (g : goal) = |
| 680 |
(* let tm0 = inst_all_free_vars tm g in *) |
| 681 |
let tm0 = prepare_term tm g in |
| 682 |
let vars0 = map (fun tm -> inst_all_free_vars tm g) vars in |
| 683 |
let g_tm = snd g in |
| 684 |
let imp = list_mk_forall (vars0, mk_imp (tm0, g_tm)) in |
| 685 |
(THENL_ROT 1 (SUBGOAL_THEN imp (fun th -> MP_TAC th THEN then_tac) THENL |
| 686 |
[REPLICATE_TAC (length vars) GEN_TAC; ALL_TAC])) g;; |
| 687 |
|
| 688 |
|
| 689 |
(* Provides a witness for an existential goal *) |
| 690 |
let exists_tac tm (g : goal) = |
| 691 |
let tm0 = inst_all_free_vars tm g in |
| 692 |
let target_ty = (type_of o fst o dest_exists o snd) g in |
| 693 |
let inst_ty = type_match (type_of tm0) target_ty [] in |
| 694 |
let tm1 = inst inst_ty tm0 in |
| 695 |
(EXISTS_TAC tm1) g;; |
| 696 |
|
| 697 |
(* Instantiates the first type variable in the given theorem *) |
| 698 |
let inst_first_type th ty = |
| 699 |
let ty_vars = type_vars_in_term (concl th) in |
| 700 |
if ty_vars = [] then |
| 701 |
failwith "inst_first_type: no type variables in the theorem" |
| 702 |
else |
| 703 |
INST_TYPE [(ty, hd ty_vars)] th;; |
| 704 |
|
| 705 |
|
| 706 |
(* The first argument must be a theorem, the second argument is arbitrary *) |
| 707 |
let combine_args arg1 arg2 = |
| 708 |
let th1 = get_arg_thm arg1 in |
| 709 |
let th0 = |
| 710 |
match arg2 with |
| 711 |
| Arg_theorem th2 -> |
| 712 |
(try MATCH_MP th1 th2 with Failure _ -> match_mp_th th1 1 th2) |
| 713 |
| Arg_term tm2 -> |
| 714 |
(try ISPEC tm2 th1 with Failure _ -> spec_var_th th1 1 tm2) |
| 715 |
| Arg_type ty2 -> inst_first_type th1 ty2 in |
| 716 |
Arg_theorem th0;; |
| 717 |
|
| 718 |
|
| 719 |
(* A temporary variable *) |
| 720 |
let use_arg_then_result = ref TRUTH;; |
| 721 |
|
| 722 |
(* |
| 723 |
(* Tests if the given id defines a theorem *) |
| 724 |
let test_id_thm id = |
| 725 |
let lexbuf = |
| 726 |
Lexing.from_string ("use_arg_then_result := " ^ id ^ ";;") in |
| 727 |
let ast = (!Toploop.parse_toplevel_phrase) lexbuf in |
| 728 |
try |
| 729 |
let _ = Toploop.execute_phrase false Format.std_formatter ast in |
| 730 |
true |
| 731 |
with _ -> false;; |
| 732 |
|
| 733 |
|
| 734 |
(* For a given id (string) finds an assumption or an existing theorem with the same name |
| 735 |
and then applies the given tactic *) |
| 736 |
let use_arg_then id (arg_tac:arg_type->tactic) (g:goal) = |
| 737 |
let list = fst g in |
| 738 |
let arg = |
| 739 |
try |
| 740 |
let assumption = assoc id list in |
| 741 |
Arg_theorem assumption |
| 742 |
with Failure _ -> |
| 743 |
try |
| 744 |
let vars = get_context_vars g in |
| 745 |
let var = assoc id vars in |
| 746 |
Arg_term var |
| 747 |
with Failure _ -> |
| 748 |
let lexbuf = |
| 749 |
Lexing.from_string ("use_arg_then_result := " ^ id ^ ";;") in |
| 750 |
let ast = (!Toploop.parse_toplevel_phrase) lexbuf in |
| 751 |
let _ = |
| 752 |
try |
| 753 |
Toploop.execute_phrase false Format.std_formatter ast |
| 754 |
with _ -> failwith ("Bad identifier: " ^ id) in |
| 755 |
Arg_theorem !use_arg_then_result in |
| 756 |
arg_tac arg g;; |
| 757 |
*) |
| 758 |
|
| 759 |
(* The same effect as use_arg_then but the theorem is given explicitly*) |
| 760 |
let use_arg_then2 (id, opt_thm) (arg_tac:arg_type->tactic) (g:goal) = |
| 761 |
let list = fst g in |
| 762 |
let arg = |
| 763 |
try |
| 764 |
let assumption = assoc id list in |
| 765 |
Arg_theorem assumption |
| 766 |
with Failure _ -> |
| 767 |
try |
| 768 |
let vars = get_context_vars g in |
| 769 |
let var = assoc id vars in |
| 770 |
Arg_term var |
| 771 |
with Failure _ -> |
| 772 |
if opt_thm <> [] then |
| 773 |
Arg_theorem (hd opt_thm) |
| 774 |
else |
| 775 |
failwith ("Assumption is not found: " ^ id) in |
| 776 |
arg_tac arg g;; |
| 777 |
|
| 778 |
|
| 779 |
let combine_args_then (tac:arg_type->tactic) arg1 arg2 (g:goal) = |
| 780 |
let th1 = get_arg_thm arg1 in |
| 781 |
let th0 = |
| 782 |
match arg2 with |
| 783 |
| Arg_theorem th2 -> |
| 784 |
(try MATCH_MP th1 th2 with Failure _ -> match_mp_th th1 1 th2) |
| 785 |
| Arg_term tm2 -> |
| 786 |
let tm0 = prepare_term tm2 g in |
| 787 |
(try ISPEC tm0 th1 with Failure _ -> spec_var_th th1 1 tm0) |
| 788 |
| Arg_type ty2 -> inst_first_type th1 ty2 in |
| 789 |
tac (Arg_theorem th0) g;; |
| 790 |
|
| 791 |
|
| 792 |
|
| 793 |
|
| 794 |
(* Specializes a variable and applies the next tactic *) |
| 795 |
let ispec_then tm (tac : thm_tactic) th (g : goal) = |
| 796 |
let tm0 = prepare_term tm g in |
| 797 |
let th0 = try ISPEC tm0 th with Failure _ -> spec_var_th th 1 tm0 in |
| 798 |
tac th0 g;; |
| 799 |
|
| 800 |
|
| 801 |
let ISPEC_THEN tm (tac : thm_tactic) th (g : goal) = |
| 802 |
let tm0 = inst_all_free_vars tm g in |
| 803 |
tac (ISPEC tm0 th) g;; |
| 804 |
|
| 805 |
|
| 806 |
|
| 807 |
let USE_THM_THEN th (tac : thm_tactic) = |
| 808 |
tac th;; |
| 809 |
|
| 810 |
|
| 811 |
let MATCH_MP_THEN th2 (tac : thm_tactic) th1 = |
| 812 |
tac (MATCH_MP th1 th2);; |
| 813 |
|
| 814 |
let match_mp_then th2 (tac : thm_tactic) th1 = |
| 815 |
let th0 = try MATCH_MP th1 th2 with Failure _ -> match_mp_th th1 1 th2 in |
| 816 |
tac th0;; |
| 817 |
|
| 818 |
|
| 819 |
let GSYM_THEN (tac : thm -> tactic) th = |
| 820 |
tac (GSYM th);; |
| 821 |
|
| 822 |
|
| 823 |
let gsym_then (tac:arg_type->tactic) arg = |
| 824 |
tac (Arg_theorem (GSYM (get_arg_thm arg)));; |
| 825 |
|
| 826 |
|
| 827 |
(* The 'apply' tactic *) |
| 828 |
let apply_tac th g = |
| 829 |
let rec try_match th = |
| 830 |
try MATCH_MP_TAC th g with Failure _ -> |
| 831 |
let th0 = PURE_ONCE_REWRITE_RULE[IMP_IMP] th in |
| 832 |
if th = th0 then failwith "apply_tac: no match" |
| 833 |
else |
| 834 |
try_match th0 in |
| 835 |
|
| 836 |
try MATCH_ACCEPT_TAC th g with Failure _ -> |
| 837 |
try_match th;; |
| 838 |
|
| 839 |
(*let apply_tac th = |
| 840 |
FIRST [MATCH_ACCEPT_TAC th; MATCH_MP_TAC th];; *) |
| 841 |
|
| 842 |
|
| 843 |
(* The 'exact' tactic *) |
| 844 |
(* TODO: do [done | by move => top; apply top], here apply top |
| 845 |
works as ACCEPT_TAC with matching (rewriting) in some cases *) |
| 846 |
let exact_tac = FIRST [done_tac; DISCH_THEN (fun th -> apply_tac th) THEN done_tac];; |
| 847 |
|
| 848 |
|
| 849 |
|
| 850 |
(* Specializes the theorem using the given set of variables *) |
| 851 |
let spec0 names vars = |
| 852 |
let find name = |
| 853 |
try (assoc name vars, true) |
| 854 |
with Failure _ -> (parse_term name, false) in |
| 855 |
let find_type var = |
| 856 |
let name, ty = dest_var var in |
| 857 |
let t, flag = find name in |
| 858 |
if flag then |
| 859 |
(ty, type_of t) |
| 860 |
else |
| 861 |
(`:bool`, `:bool`) in |
| 862 |
let inst_term tm = |
| 863 |
let ty_src, ty_dst = unzip (map find_type (frees tm)) in |
| 864 |
let ty_inst = itlist2 type_match ty_src ty_dst [] in |
| 865 |
inst ty_inst tm in |
| 866 |
let list = map find names in |
| 867 |
let tm_list = map (fun tm, flag -> if flag then tm else inst_term tm) list in |
| 868 |
ISPECL tm_list;; |
| 869 |
|
| 870 |
|
| 871 |
let spec names = spec0 names (get_context_vars (top_realgoal()));; |
| 872 |
|
| 873 |
|
| 874 |
let spec_mp names th g = MP_TAC (spec0 names (get_context_vars g) th) g;; |
| 875 |
|
| 876 |
|
| 877 |
(* Case theorems *) |
| 878 |
let bool_cases = ONCE_REWRITE_RULE[CONJ_ACI] bool_INDUCT;; |
| 879 |
let list_cases = prove(`!P. P [] /\ (!(h:A) t. P (CONS h t)) ==> (!l. P l)`, |
| 880 |
REPEAT STRIP_TAC THEN |
| 881 |
MP_TAC (SPEC `l:(A)list` list_CASES) THEN DISCH_THEN DISJ_CASES_TAC THEN ASM_REWRITE_TAC[] THEN |
| 882 |
FIRST_X_ASSUM (CHOOSE_THEN MP_TAC) THEN DISCH_THEN (CHOOSE_THEN MP_TAC) THEN |
| 883 |
DISCH_THEN (fun th -> ASM_REWRITE_TAC[th]));; |
| 884 |
let pair_cases = pair_INDUCT;; |
| 885 |
let num_cases = prove(`!P. P 0 /\ (!n. P (SUC n)) ==> (!m. P m)`, |
| 886 |
REPEAT STRIP_TAC THEN |
| 887 |
MP_TAC (SPEC `m:num` num_CASES) THEN DISCH_THEN DISJ_CASES_TAC THEN ASM_REWRITE_TAC[] THEN |
| 888 |
FIRST_X_ASSUM (CHOOSE_THEN (fun th -> ASM_REWRITE_TAC[th])));; |
| 889 |
let option_cases = option_INDUCT;; |
| 890 |
|
| 891 |
|
| 892 |
let cases_table = Hashtbl.create 10;; |
| 893 |
Hashtbl.add cases_table "bool" bool_cases;; |
| 894 |
Hashtbl.add cases_table "list" list_cases;; |
| 895 |
Hashtbl.add cases_table "prod" pair_cases;; |
| 896 |
Hashtbl.add cases_table "num" num_cases;; |
| 897 |
Hashtbl.add cases_table "option" option_cases;; |
| 898 |
|
| 899 |
|
| 900 |
(* Induction theorems *) |
| 901 |
let bool_elim = bool_cases;; |
| 902 |
let list_elim = list_INDUCT;; |
| 903 |
let pair_elim = pair_INDUCT;; |
| 904 |
let num_elim = num_INDUCTION;; |
| 905 |
let option_elim = option_INDUCT;; |
| 906 |
|
| 907 |
let elim_table = Hashtbl.create 10;; |
| 908 |
Hashtbl.add elim_table "bool" bool_elim;; |
| 909 |
Hashtbl.add elim_table "list" list_elim;; |
| 910 |
Hashtbl.add elim_table "prod" pair_elim;; |
| 911 |
Hashtbl.add elim_table "num" num_elim;; |
| 912 |
Hashtbl.add elim_table "option" option_elim;; |
| 913 |
|
| 914 |
|
| 915 |
|
| 916 |
(* case: works only for (A /\ B) -> C; (A \/ B) -> C; (?x. P) -> Q; !(n:num). P; !(l:list(A)). P *) |
| 917 |
let case (g:goal) = |
| 918 |
let goal_tm = snd g in |
| 919 |
if not (is_imp goal_tm) then |
| 920 |
(* !a. P *) |
| 921 |
if is_forall goal_tm then |
| 922 |
let var, _ = dest_forall goal_tm in |
| 923 |
let ty_name = (fst o dest_type o type_of) var in |
| 924 |
let case_th = Hashtbl.find cases_table ty_name in |
| 925 |
(MATCH_MP_TAC case_th THEN REPEAT CONJ_TAC) g |
| 926 |
else |
| 927 |
failwith "case: not imp or forall" |
| 928 |
else |
| 929 |
let tm = lhand goal_tm in |
| 930 |
(* A /\ B *) |
| 931 |
if is_conj tm then |
| 932 |
(DISCH_THEN (CONJUNCTS_THEN2 ASSUME_TAC MP_TAC) THEN POP_ASSUM MP_TAC) g |
| 933 |
(* A \/ B *) |
| 934 |
else if is_disj tm then |
| 935 |
(DISCH_THEN DISJ_CASES_TAC THEN POP_ASSUM MP_TAC) g |
| 936 |
(* ?x. P *) |
| 937 |
else if is_exists tm then |
| 938 |
(ONCE_REWRITE_TAC[GSYM LEFT_FORALL_IMP_THM]) g |
| 939 |
else |
| 940 |
failwith "case: not implemented";; |
| 941 |
|
| 942 |
|
| 943 |
|
| 944 |
(* elim: works only for num and list *) |
| 945 |
let elim (g:goal) = |
| 946 |
let goal_tm = snd g in |
| 947 |
(* !a. P *) |
| 948 |
if is_forall goal_tm then |
| 949 |
let var, _ = dest_forall goal_tm in |
| 950 |
let ty_name = (fst o dest_type o type_of) var in |
| 951 |
let induct_th = Hashtbl.find elim_table ty_name in |
| 952 |
(MATCH_MP_TAC induct_th THEN REPEAT CONJ_TAC) g |
| 953 |
else |
| 954 |
failwith "elim: not forall";; |
| 955 |
|
| 956 |
|
| 957 |
|
| 958 |
(* Instantiates the first type variable in the given theorem *) |
| 959 |
let INST_FIRST_TYPE_THEN ty (then_tac:thm_tactic) th = |
| 960 |
let ty_vars = type_vars_in_term (concl th) in |
| 961 |
if ty_vars = [] then |
| 962 |
failwith "inst_first_type: no type variables in the theorem" |
| 963 |
else |
| 964 |
then_tac (INST_TYPE [(ty, hd ty_vars)] th);; |
| 965 |
|
| 966 |
|
| 967 |
(* Replaces all occurrences of distinct '_' with unique variables *) |
| 968 |
let transform_pattern pat_tm = |
| 969 |
let names = ref (map (fst o dest_var) (frees pat_tm)) in |
| 970 |
let rec transform tm = |
| 971 |
match tm with |
| 972 |
| Abs(x_tm, b_tm) -> |
| 973 |
let _ = names := (fst o dest_var) x_tm :: !names in |
| 974 |
mk_abs (x_tm, transform b_tm) |
| 975 |
| Comb(l_tm, r_tm) -> |
| 976 |
mk_comb (transform l_tm, transform r_tm) |
| 977 |
| Var ("_", ty) -> |
| 978 |
let name = generate_fresh_name !names tm in |
| 979 |
let _ = names := name :: !names in |
| 980 |
mk_var (name, ty) |
| 981 |
| _ -> tm in |
| 982 |
transform pat_tm;; |
| 983 |
|
| 984 |
|
| 985 |
let wild_frees tm = |
| 986 |
filter (fun tm -> ((fst o dest_var) tm).[0] = '_') (frees tm);; |
| 987 |
|
| 988 |
let nwild_frees tm = |
| 989 |
filter (fun tm -> ((fst o dest_var) tm).[0] <> '_') (frees tm);; |
| 990 |
|
| 991 |
|
| 992 |
(* congr_tac *) |
| 993 |
let congr_tac pat_tm goal = |
| 994 |
let goal_tm = snd goal in |
| 995 |
let context_vars = get_context_vars goal in |
| 996 |
let pat = transform_pattern pat_tm in |
| 997 |
let f0_vars = nwild_frees pat in |
| 998 |
let pattern = inst_context_vars context_vars f0_vars pat in |
| 999 |
let const_pat = nwild_frees pattern in |
| 1000 |
let wild_pat = wild_frees pattern in |
| 1001 |
|
| 1002 |
let lhs, rhs = dest_eq goal_tm in |
| 1003 |
let lm, rm = |
| 1004 |
term_match const_pat pattern lhs, term_match const_pat pattern rhs in |
| 1005 |
let eq_tms = map |
| 1006 |
(fun tm -> mk_eq (instantiate lm tm, instantiate rm tm)) wild_pat in |
| 1007 |
let eq_tm = itlist (curry mk_imp) eq_tms goal_tm in |
| 1008 |
let eq_thm = EQT_ELIM (SIMP_CONV[] eq_tm) in |
| 1009 |
(apply_tac eq_thm THEN REPEAT CONJ_TAC) goal;; |
| 1010 |
|
| 1011 |
|
| 1012 |
(* Eliminates the first antecedent of a goal *) |
| 1013 |
let elim_fst_ants_tac = |
| 1014 |
let gen_elim_thm tm = |
| 1015 |
let vars, tm1 = strip_forall tm in |
| 1016 |
let ants_tm, concl_tm = dest_imp tm1 in |
| 1017 |
let th1 = ASSUME (itlist (curry mk_forall) vars concl_tm) in |
| 1018 |
let th2 = DISCH ants_tm (SPECL vars th1) in |
| 1019 |
DISCH_ALL (itlist GEN vars th2) in |
| 1020 |
fun (g:goal) -> |
| 1021 |
let goal_tm = snd g in |
| 1022 |
let elim_th = gen_elim_thm goal_tm in |
| 1023 |
MATCH_MP_TAC elim_th g;; |
| 1024 |
|
| 1025 |
|
| 1026 |
(* If a goal has the form ssreflect_eq ==> P then the equality is introduced as |
| 1027 |
an assumption. |
| 1028 |
If a goal has the form !x. ssreflect_eq ==> P then the equality is eliminated *) |
| 1029 |
let process_fst_eq_tac (g:goal) = |
| 1030 |
let vars, g_tm = strip_forall (snd g) in |
| 1031 |
let tac = |
| 1032 |
try |
| 1033 |
let eq_tm = (rator o fst o dest_imp) g_tm in |
| 1034 |
let label = (fst o dest_var o rand) eq_tm in |
| 1035 |
if (fst o dest_const o rator) eq_tm = "ssreflect_eq" then |
| 1036 |
if length vars = 0 then |
| 1037 |
DISCH_THEN (LABEL_TAC label o PURE_ONCE_REWRITE_RULE[ssreflect_eq_def]) |
| 1038 |
else |
| 1039 |
elim_fst_ants_tac |
| 1040 |
else |
| 1041 |
ALL_TAC |
| 1042 |
with Failure _ -> ALL_TAC in |
| 1043 |
tac g;; |
| 1044 |
|
| 1045 |
|
| 1046 |
(* Discharges a term by generalizing all occurences of this term first *) |
| 1047 |
let disch_tm_eq_tac eq_name occs tm (g : goal) = |
| 1048 |
let tm0 = prepare_term tm g in |
| 1049 |
let name = generate_fresh_name ((fst o unzip) (get_context_vars g)) tm in |
| 1050 |
let eq_var = mk_var (eq_name, aty) in |
| 1051 |
let new_tm = mk_var (name, type_of tm0) in |
| 1052 |
let abbrev_tm = mk_eq (new_tm, tm0) in |
| 1053 |
(ABBREV_TAC abbrev_tm THEN |
| 1054 |
EXPAND_TAC name THEN |
| 1055 |
FIRST_ASSUM (fun th -> TRY (new_rewrite occs [] th)) THEN |
| 1056 |
POP_ASSUM (MP_TAC o PURE_ONCE_REWRITE_RULE[GSYM (SPEC eq_var ssreflect_eq_def)]) THEN |
| 1057 |
SPEC_TAC (new_tm, new_tm)) g;; |
| 1058 |
|
| 1059 |
|
| 1060 |
(* Discharges a term and generates an equality *) |
| 1061 |
let disch_eq_tac eq_name occs arg = |
| 1062 |
disch_tm_eq_tac eq_name occs (get_arg_term arg);; |
| 1063 |
|
| 1064 |
|
| 1065 |
end;; |