Debian Codegraph @

Formal_ineqs/lib/ssreflect/ssreflect.hl

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