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