author | blanchet |
Mon, 01 Sep 2014 16:17:46 +0200 | |
changeset 58111 | 82db9ad610b9 |
parent 55236 | 8d61b0aa7a0d |
child 58112 | 8081087096ad |
permissions | -rw-r--r-- |
23150 | 1 |
(* Title: HOL/Tools/TFL/casesplit.ML |
2 |
Author: Lucas Dixon, University of Edinburgh |
|
3 |
||
41840
f69045fdc836
removed dead code/unused exports/speculative generality
krauss
parents:
41228
diff
changeset
|
4 |
Extra case splitting for TFL. |
23150 | 5 |
*) |
6 |
||
7 |
signature CASE_SPLIT = |
|
8 |
sig |
|
9 |
(* try to recursively split conjectured thm to given list of thms *) |
|
49340
25fc6e0da459
observe context more carefully when producing "fresh" variables -- for increased chances that method "subst" works in local context (including that of forked proofs);
wenzelm
parents:
46489
diff
changeset
|
10 |
val splitto : Proof.context -> thm list -> thm -> thm |
23150 | 11 |
end; |
12 |
||
41840
f69045fdc836
removed dead code/unused exports/speculative generality
krauss
parents:
41228
diff
changeset
|
13 |
structure CaseSplit: CASE_SPLIT = |
23150 | 14 |
struct |
15 |
||
16 |
(* make a casethm from an induction thm *) |
|
17 |
val cases_thm_of_induct_thm = |
|
18 |
Seq.hd o (ALLGOALS (fn i => REPEAT (etac Drule.thin_rl i))); |
|
19 |
||
20 |
(* get the case_thm (my version) from a type *) |
|
31784 | 21 |
fun case_thm_of_ty thy ty = |
23150 | 22 |
let |
23 |
val ty_str = case ty of |
|
24 |
Type(ty_str, _) => ty_str |
|
25 |
| TFree(s,_) => error ("Free type: " ^ s) |
|
26 |
| TVar((s,i),_) => error ("Free variable: " ^ s) |
|
58111 | 27 |
val {induct, ...} = Datatype_Data.the_info thy ty_str |
23150 | 28 |
in |
45701 | 29 |
cases_thm_of_induct_thm induct |
23150 | 30 |
end; |
31 |
||
32 |
||
33 |
(* for use when there are no prems to the subgoal *) |
|
34 |
(* does a case split on the given variable *) |
|
35 |
fun mk_casesplit_goal_thm sgn (vstr,ty) gt = |
|
36 |
let |
|
37 |
val x = Free(vstr,ty) |
|
38 |
val abst = Abs(vstr, ty, Term.abstract_over (x, gt)); |
|
39 |
||
40 |
val ctermify = Thm.cterm_of sgn; |
|
41 |
val ctypify = Thm.ctyp_of sgn; |
|
42 |
val case_thm = case_thm_of_ty sgn ty; |
|
43 |
||
44 |
val abs_ct = ctermify abst; |
|
45 |
val free_ct = ctermify x; |
|
46 |
||
47 |
val (Pv, Dv, type_insts) = |
|
48 |
case (Thm.concl_of case_thm) of |
|
49 |
(_ $ ((Pv as Var(P,Pty)) $ (Dv as Var(D, Dty)))) => |
|
50 |
(Pv, Dv, |
|
51 |
Sign.typ_match sgn (Dty, ty) Vartab.empty) |
|
52 |
| _ => error "not a valid case thm"; |
|
53 |
val type_cinsts = map (fn (ixn, (S, T)) => (ctypify (TVar (ixn, S)), ctypify T)) |
|
54 |
(Vartab.dest type_insts); |
|
32035 | 55 |
val cPv = ctermify (Envir.subst_term_types type_insts Pv); |
56 |
val cDv = ctermify (Envir.subst_term_types type_insts Dv); |
|
23150 | 57 |
in |
52243 | 58 |
Conv.fconv_rule Drule.beta_eta_conversion |
23150 | 59 |
(case_thm |
60 |
|> Thm.instantiate (type_cinsts, []) |
|
52243 | 61 |
|> Thm.instantiate ([], [(cPv, abs_ct), (cDv, free_ct)])) |
23150 | 62 |
end; |
63 |
||
64 |
||
65 |
(* the find_XXX_split functions are simply doing a lightwieght (I |
|
66 |
think) term matching equivalent to find where to do the next split *) |
|
67 |
||
68 |
(* assuming two twems are identical except for a free in one at a |
|
69 |
subterm, or constant in another, ie assume that one term is a plit of |
|
70 |
another, then gives back the free variable that has been split. *) |
|
71 |
exception find_split_exp of string |
|
72 |
fun find_term_split (Free v, _ $ _) = SOME v |
|
73 |
| find_term_split (Free v, Const _) = SOME v |
|
74 |
| find_term_split (Free v, Abs _) = SOME v (* do we really want this case? *) |
|
75 |
| find_term_split (Free v, Var _) = NONE (* keep searching *) |
|
76 |
| find_term_split (a $ b, a2 $ b2) = |
|
77 |
(case find_term_split (a, a2) of |
|
78 |
NONE => find_term_split (b,b2) |
|
79 |
| vopt => vopt) |
|
80 |
| find_term_split (Abs(_,ty,t1), Abs(_,ty2,t2)) = |
|
81 |
find_term_split (t1, t2) |
|
82 |
| find_term_split (Const (x,ty), Const(x2,ty2)) = |
|
83 |
if x = x2 then NONE else (* keep searching *) |
|
84 |
raise find_split_exp (* stop now *) |
|
85 |
"Terms are not identical upto a free varaible! (Consts)" |
|
86 |
| find_term_split (Bound i, Bound j) = |
|
87 |
if i = j then NONE else (* keep searching *) |
|
88 |
raise find_split_exp (* stop now *) |
|
89 |
"Terms are not identical upto a free varaible! (Bound)" |
|
46489 | 90 |
| find_term_split _ = |
23150 | 91 |
raise find_split_exp (* stop now *) |
92 |
"Terms are not identical upto a free varaible! (Other)"; |
|
93 |
||
94 |
(* assume that "splitth" is a case split form of subgoal i of "genth", |
|
95 |
then look for a free variable to split, breaking the subgoal closer to |
|
96 |
splitth. *) |
|
97 |
fun find_thm_split splitth i genth = |
|
98 |
find_term_split (Logic.get_goal (Thm.prop_of genth) i, |
|
99 |
Thm.concl_of splitth) handle find_split_exp _ => NONE; |
|
100 |
||
101 |
(* as above but searches "splitths" for a theorem that suggest a case split *) |
|
102 |
fun find_thms_split splitths i genth = |
|
103 |
Library.get_first (fn sth => find_thm_split sth i genth) splitths; |
|
104 |
||
105 |
||
106 |
(* split the subgoal i of "genth" until we get to a member of |
|
107 |
splitths. Assumes that genth will be a general form of splitths, that |
|
108 |
can be case-split, as needed. Otherwise fails. Note: We assume that |
|
109 |
all of "splitths" are split to the same level, and thus it doesn't |
|
110 |
matter which one we choose to look for the next split. Simply add |
|
111 |
search on splitthms and split variable, to change this. *) |
|
112 |
(* Note: possible efficiency measure: when a case theorem is no longer |
|
113 |
useful, drop it? *) |
|
114 |
(* Note: This should not be a separate tactic but integrated into the |
|
115 |
case split done during recdef's case analysis, this would avoid us |
|
116 |
having to (re)search for variables to split. *) |
|
49340
25fc6e0da459
observe context more carefully when producing "fresh" variables -- for increased chances that method "subst" works in local context (including that of forked proofs);
wenzelm
parents:
46489
diff
changeset
|
117 |
fun splitto ctxt splitths genth = |
23150 | 118 |
let |
119 |
val _ = not (null splitths) orelse error "splitto: no given splitths"; |
|
42364 | 120 |
val thy = Thm.theory_of_thm genth; |
23150 | 121 |
|
122 |
(* check if we are a member of splitths - FIXME: quicker and |
|
123 |
more flexible with discrim net. *) |
|
124 |
fun solve_by_splitth th split = |
|
42364 | 125 |
Thm.biresolution false [(false,split)] 1 th; |
23150 | 126 |
|
127 |
fun split th = |
|
42364 | 128 |
(case find_thms_split splitths 1 th of |
129 |
NONE => |
|
130 |
(writeln (cat_lines |
|
55236 | 131 |
(["th:", Display.string_of_thm ctxt th, "split ths:"] @ |
132 |
map (Display.string_of_thm ctxt) splitths @ ["\n--"])); |
|
42364 | 133 |
error "splitto: cannot find variable to split on") |
134 |
| SOME v => |
|
135 |
let |
|
42365
bfd28ba57859
more direct Logic.dest_implies (with exception TERM instead of Subscript);
wenzelm
parents:
42364
diff
changeset
|
136 |
val gt = HOLogic.dest_Trueprop (#1 (Logic.dest_implies (Thm.prop_of th))); |
42364 | 137 |
val split_thm = mk_casesplit_goal_thm thy v gt; |
49340
25fc6e0da459
observe context more carefully when producing "fresh" variables -- for increased chances that method "subst" works in local context (including that of forked proofs);
wenzelm
parents:
46489
diff
changeset
|
138 |
val (subthms, expf) = IsaND.fixed_subgoal_thms ctxt split_thm; |
42364 | 139 |
in |
140 |
expf (map recsplitf subthms) |
|
141 |
end) |
|
23150 | 142 |
|
143 |
and recsplitf th = |
|
42364 | 144 |
(* note: multiple unifiers! we only take the first element, |
145 |
probably fine -- there is probably only one anyway. *) |
|
146 |
(case get_first (Seq.pull o solve_by_splitth th) splitths of |
|
147 |
NONE => split th |
|
46489 | 148 |
| SOME (solved_th, _) => solved_th); |
23150 | 149 |
in |
150 |
recsplitf genth |
|
151 |
end; |
|
152 |
||
153 |
end; |