author | wenzelm |
Tue, 29 Nov 2005 23:00:20 +0100 | |
changeset 18287 | 28efcdae34dc |
parent 18259 | 7b14579c58f2 |
child 18330 | 444f16d232a2 |
permissions | -rw-r--r-- |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
1 |
(* Title: Provers/induct_method.ML |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
2 |
ID: $Id$ |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
3 |
Author: Markus Wenzel, TU Muenchen |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
4 |
|
11735 | 5 |
Proof by cases and induction on sets and types. |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
6 |
*) |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
7 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
8 |
signature INDUCT_METHOD_DATA = |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
9 |
sig |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
10 |
val dest_concls: term -> term list |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
11 |
val cases_default: thm |
11996
b409a8cbe1fb
induct: internalize ``missing'' consumes-facts from goal state
wenzelm
parents:
11984
diff
changeset
|
12 |
val local_impI: thm |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
13 |
val conjI: thm |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
14 |
val atomize: thm list |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
15 |
val rulify1: thm list |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
16 |
val rulify2: thm list |
12240 | 17 |
val localize: thm list |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
18 |
end; |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
19 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
20 |
signature INDUCT_METHOD = |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
21 |
sig |
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
22 |
val fix_tac: Proof.context -> int -> (string * typ) list -> int -> tactic |
18287 | 23 |
val add_defs: (string option * term) option list -> Proof.context -> |
24 |
(term option list * thm list) * Proof.context |
|
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
25 |
val atomize_term: theory -> term -> term |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
26 |
val atomize_tac: int -> tactic |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
27 |
val rulified_term: thm -> theory * term |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
28 |
val rulify_tac: int -> tactic |
18259 | 29 |
val guess_instance: thm -> int -> thm -> thm Seq.seq |
16391 | 30 |
val cases_tac: Proof.context -> bool -> term option list list -> thm option -> |
18224 | 31 |
thm list -> int -> cases_tactic |
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
32 |
val induct_tac: Proof.context -> bool -> (string option * term) option list list -> |
18235 | 33 |
(string * typ) list list -> term option list -> thm option -> thm list -> int -> cases_tactic |
34 |
val coinduct_tac: Proof.context -> bool -> term option list -> term option list -> |
|
35 |
thm option -> thm list -> int -> cases_tactic |
|
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
36 |
val setup: (theory -> theory) list |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
37 |
end; |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
38 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
39 |
functor InductMethodFun(Data: INDUCT_METHOD_DATA): INDUCT_METHOD = |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
40 |
struct |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
41 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
42 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
43 |
(** misc utils **) |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
44 |
|
18287 | 45 |
(* alignment *) |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
46 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
47 |
fun align_left msg xs ys = |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
48 |
let val m = length xs and n = length ys |
11735 | 49 |
in if m < n then raise ERROR_MESSAGE msg else (Library.take (n, xs) ~~ ys) end; |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
50 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
51 |
fun align_right msg xs ys = |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
52 |
let val m = length xs and n = length ys |
11735 | 53 |
in if m < n then raise ERROR_MESSAGE msg else (Library.drop (m - n, xs) ~~ ys) end; |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
54 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
55 |
|
11735 | 56 |
(* prep_inst *) |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
57 |
|
18205 | 58 |
fun prep_inst thy align tune (tm, ts) = |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
59 |
let |
18205 | 60 |
val cert = Thm.cterm_of thy; |
15531 | 61 |
fun prep_var (x, SOME t) = |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
62 |
let |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
63 |
val cx = cert x; |
18147 | 64 |
val {T = xT, thy, ...} = Thm.rep_cterm cx; |
12799
5472afdd3bd3
MetaSimplifier.rewrite_term replaces slow Tactic.rewrite_cterm;
wenzelm
parents:
12305
diff
changeset
|
65 |
val ct = cert (tune t); |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
66 |
in |
18147 | 67 |
if Sign.typ_instance thy (#T (Thm.rep_cterm ct), xT) then SOME (cx, ct) |
11735 | 68 |
else raise ERROR_MESSAGE (Pretty.string_of (Pretty.block |
69 |
[Pretty.str "Ill-typed instantiation:", Pretty.fbrk, |
|
70 |
Display.pretty_cterm ct, Pretty.str " ::", Pretty.brk 1, |
|
71 |
Display.pretty_ctyp (#T (Thm.crep_cterm ct))])) |
|
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
72 |
end |
15531 | 73 |
| prep_var (_, NONE) = NONE; |
11735 | 74 |
val xs = InductAttrib.vars_of tm; |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
75 |
in |
11735 | 76 |
align "Rule has fewer variables than instantiations given" xs ts |
15570 | 77 |
|> List.mapPartial prep_var |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
78 |
end; |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
79 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
80 |
|
18205 | 81 |
(* trace_rules *) |
82 |
||
83 |
fun trace_rules _ kind [] = error ("Unable to figure out " ^ kind ^ " rule") |
|
84 |
| trace_rules ctxt _ rules = Method.trace ctxt rules; |
|
85 |
||
86 |
||
87 |
(* make_cases *) |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
88 |
|
18224 | 89 |
fun make_cases is_open rule = |
90 |
RuleCases.make is_open NONE (Thm.theory_of_thm rule, Thm.prop_of rule); |
|
91 |
||
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
92 |
fun warn_open true = warning "Encountered open rule cases -- deprecated" |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
93 |
| warn_open false = (); |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
94 |
|
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
95 |
|
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
96 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
97 |
(** cases method **) |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
98 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
99 |
(* |
11735 | 100 |
rule selection scheme: |
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
101 |
cases - default case split |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
102 |
`x:A` cases ... - set cases |
11735 | 103 |
cases t - type cases |
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
104 |
... cases ... r - explicit rule |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
105 |
*) |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
106 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
107 |
local |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
108 |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
109 |
fun find_casesT ctxt ((SOME t :: _) :: _) = InductAttrib.find_casesT ctxt (Term.fastype_of t) |
11735 | 110 |
| find_casesT _ _ = []; |
111 |
||
18224 | 112 |
fun find_casesS ctxt (fact :: _) = InductAttrib.find_casesS ctxt (Thm.concl_of fact) |
11735 | 113 |
| find_casesS _ _ = []; |
114 |
||
16391 | 115 |
in |
116 |
||
117 |
fun cases_tac ctxt is_open insts opt_rule facts = |
|
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
118 |
let |
18224 | 119 |
val _ = warn_open is_open; |
18147 | 120 |
val thy = ProofContext.theory_of ctxt; |
121 |
val cert = Thm.cterm_of thy; |
|
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
122 |
|
11735 | 123 |
fun inst_rule r = |
18224 | 124 |
if null insts then `RuleCases.get r |
11735 | 125 |
else (align_left "Rule has fewer premises than arguments given" (Thm.prems_of r) insts |
18205 | 126 |
|> (List.concat o map (prep_inst thy align_left I)) |
18224 | 127 |
|> Drule.cterm_instantiate) r |> pair (RuleCases.get r); |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
128 |
|
11735 | 129 |
val ruleq = |
12852 | 130 |
(case opt_rule of |
18205 | 131 |
SOME r => Seq.single (inst_rule r) |
132 |
| NONE => |
|
133 |
(find_casesS ctxt facts @ find_casesT ctxt insts @ [Data.cases_default]) |
|
134 |
|> tap (trace_rules ctxt InductAttrib.casesN) |
|
18224 | 135 |
|> Seq.of_list |> Seq.maps (Seq.try inst_rule)); |
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
136 |
in |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
137 |
fn i => fn st => |
18224 | 138 |
ruleq |
18235 | 139 |
|> Seq.maps (RuleCases.consume [] facts) |
18224 | 140 |
|> Seq.maps (fn ((cases, (_, more_facts)), rule) => |
141 |
CASES (make_cases is_open rule cases) |
|
142 |
(Method.insert_tac more_facts i THEN Tactic.rtac rule i) st) |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
143 |
end; |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
144 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
145 |
end; |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
146 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
147 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
148 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
149 |
(** induct method **) |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
150 |
|
18235 | 151 |
(* fix_tac *) |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
152 |
|
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
153 |
local |
18240 | 154 |
|
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
155 |
fun goal_prefix k ((c as Const ("all", _)) $ Abs (a, T, B)) = c $ Abs (a, T, goal_prefix k B) |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
156 |
| goal_prefix 0 _ = Term.dummy_pattern propT |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
157 |
| goal_prefix k ((c as Const ("==>", _)) $ A $ B) = c $ A $ goal_prefix (k - 1) B |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
158 |
| goal_prefix _ _ = Term.dummy_pattern propT; |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
159 |
|
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
160 |
fun goal_params k (Const ("all", _) $ Abs (_, _, B)) = goal_params k B + 1 |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
161 |
| goal_params 0 _ = 0 |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
162 |
| goal_params k (Const ("==>", _) $ _ $ B) = goal_params (k - 1) B |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
163 |
| goal_params _ _ = 0; |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
164 |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
165 |
val meta_spec = PureThy.get_thm Pure.thy (Name "meta_spec"); |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
166 |
|
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
167 |
fun meta_spec_tac ctxt n (x, T) = SUBGOAL (fn (goal, i) => |
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
168 |
let |
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
169 |
val thy = ProofContext.theory_of ctxt; |
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
170 |
val cert = Thm.cterm_of thy; |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
171 |
val certT = Thm.ctyp_of thy; |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
172 |
|
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
173 |
val v = Free (x, T); |
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
174 |
fun spec_rule prfx (xs, body) = |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
175 |
meta_spec |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
176 |
|> Thm.rename_params_rule ([ProofContext.revert_skolem ctxt x], 1) |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
177 |
|> Thm.lift_rule (cert prfx) |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
178 |
|> `(Thm.prop_of #> Logic.strip_assums_concl) |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
179 |
|-> (fn pred $ arg => |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
180 |
Drule.cterm_instantiate |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
181 |
[(cert (Term.head_of pred), cert (Unify.rlist_abs (xs, body))), |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
182 |
(cert (Term.head_of arg), cert (Unify.rlist_abs (xs, v)))]); |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
183 |
|
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
184 |
fun goal_concl k xs (Const ("all", _) $ Abs (a, T, B)) = goal_concl k ((a, T) :: xs) B |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
185 |
| goal_concl 0 xs B = |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
186 |
if not (Term.exists_subterm (fn t => t aconv v) B) then NONE |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
187 |
else SOME (xs, Term.absfree (x, T, Term.incr_boundvars 1 B)) |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
188 |
| goal_concl k xs (Const ("==>", _) $ _ $ B) = goal_concl (k - 1) xs B |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
189 |
| goal_concl _ _ _ = NONE; |
18205 | 190 |
in |
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
191 |
(case goal_concl n [] goal of |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
192 |
SOME concl => |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
193 |
(compose_tac (false, spec_rule (goal_prefix n goal) concl, 1) THEN' rtac asm_rl) i |
18259 | 194 |
| NONE => (warning ("Induction: no variable " ^ ProofContext.string_of_term ctxt v ^ |
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
195 |
" to be fixed -- ignored"); all_tac)) |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
196 |
end); |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
197 |
|
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
198 |
fun miniscope_tac n i = PRIMITIVE (Drule.fconv_rule |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
199 |
(Drule.goals_conv (Library.equal i) |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
200 |
(Drule.forall_conv n (Tactic.rewrite true [Thm.symmetric Drule.norm_hhf_eq])))); |
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
201 |
|
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
202 |
in |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
203 |
|
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
204 |
fun fix_tac _ _ [] = K all_tac |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
205 |
| fix_tac ctxt n xs = SUBGOAL (fn (goal, i) => |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
206 |
(EVERY' (map (meta_spec_tac ctxt n) xs) THEN' |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
207 |
(miniscope_tac (goal_params n goal))) i); |
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
208 |
|
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
209 |
end; |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
210 |
|
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
211 |
|
18235 | 212 |
(* add_defs *) |
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
213 |
|
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
214 |
fun add_defs def_insts = |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
215 |
let |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
216 |
fun add (SOME (SOME x, t)) ctxt = |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
217 |
let val ((lhs, def), ctxt') = ProofContext.add_def (x, t) ctxt |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
218 |
in ((SOME (Free lhs), [def]), ctxt') end |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
219 |
| add (SOME (NONE, t)) ctxt = ((SOME t, []), ctxt) |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
220 |
| add NONE ctxt = ((NONE, []), ctxt); |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
221 |
in fold_map add def_insts #> apfst (split_list #> apsnd List.concat) end; |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
222 |
|
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
223 |
|
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
224 |
(* atomize and rulify *) |
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
225 |
|
18147 | 226 |
fun atomize_term thy = |
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
227 |
MetaSimplifier.rewrite_term thy Data.atomize [] |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
228 |
#> ObjectLogic.drop_judgment thy; |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
229 |
|
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
230 |
val atomize_tac = |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
231 |
Tactic.rewrite_goal_tac Data.atomize; |
12799
5472afdd3bd3
MetaSimplifier.rewrite_term replaces slow Tactic.rewrite_cterm;
wenzelm
parents:
12305
diff
changeset
|
232 |
|
5472afdd3bd3
MetaSimplifier.rewrite_term replaces slow Tactic.rewrite_cterm;
wenzelm
parents:
12305
diff
changeset
|
233 |
fun rulified_term thm = |
18147 | 234 |
let val thy = Thm.theory_of_thm thm in |
12799
5472afdd3bd3
MetaSimplifier.rewrite_term replaces slow Tactic.rewrite_cterm;
wenzelm
parents:
12305
diff
changeset
|
235 |
Thm.prop_of thm |
18147 | 236 |
|> MetaSimplifier.rewrite_term thy Data.rulify1 [] |
237 |
|> MetaSimplifier.rewrite_term thy Data.rulify2 [] |
|
238 |
|> pair thy |
|
12799
5472afdd3bd3
MetaSimplifier.rewrite_term replaces slow Tactic.rewrite_cterm;
wenzelm
parents:
12305
diff
changeset
|
239 |
end; |
11756 | 240 |
|
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
241 |
val rulify_tac = |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
242 |
Tactic.rewrite_goal_tac Data.rulify1 THEN' |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
243 |
Tactic.rewrite_goal_tac Data.rulify2 THEN' |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
244 |
Tactic.norm_hhf_tac; |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
245 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
246 |
|
18240 | 247 |
(* internalize/localize rules -- pseudo-elimination *) |
18147 | 248 |
|
249 |
local |
|
11996
b409a8cbe1fb
induct: internalize ``missing'' consumes-facts from goal state
wenzelm
parents:
11984
diff
changeset
|
250 |
|
b409a8cbe1fb
induct: internalize ``missing'' consumes-facts from goal state
wenzelm
parents:
11984
diff
changeset
|
251 |
fun imp_intr i raw_th = |
b409a8cbe1fb
induct: internalize ``missing'' consumes-facts from goal state
wenzelm
parents:
11984
diff
changeset
|
252 |
let |
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
253 |
val cert = Thm.cterm_of (Thm.theory_of_thm raw_th); |
11996
b409a8cbe1fb
induct: internalize ``missing'' consumes-facts from goal state
wenzelm
parents:
11984
diff
changeset
|
254 |
val th = Thm.permute_prems (i - 1) 1 raw_th; |
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
255 |
val prems = Thm.prems_of th; |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
256 |
val As = Library.take (length prems - 1, prems); |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
257 |
val C = Term.dummy_pattern propT; |
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
258 |
in th COMP Thm.lift_rule (cert (Logic.list_implies (As, C))) Data.local_impI end; |
11996
b409a8cbe1fb
induct: internalize ``missing'' consumes-facts from goal state
wenzelm
parents:
11984
diff
changeset
|
259 |
|
18147 | 260 |
in |
261 |
||
262 |
fun internalize k th = if k > 0 then internalize (k - 1) (imp_intr k th) else th; |
|
263 |
||
18240 | 264 |
val localize = Goal.norm_hhf o Tactic.simplify false Data.localize; |
265 |
||
18147 | 266 |
end; |
267 |
||
11996
b409a8cbe1fb
induct: internalize ``missing'' consumes-facts from goal state
wenzelm
parents:
11984
diff
changeset
|
268 |
|
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
269 |
(* join multi-rules *) |
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
270 |
|
11735 | 271 |
val eq_prems = curry (Term.aconvs o pairself Thm.prems_of); |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
272 |
|
11735 | 273 |
fun join_rules [] = [] |
274 |
| join_rules [th] = [th] |
|
275 |
| join_rules (rules as r :: rs) = |
|
276 |
if not (forall (eq_prems r) rs) then [] |
|
277 |
else |
|
278 |
let |
|
279 |
val th :: ths = map Drule.freeze_all rules; |
|
280 |
val cprems = Drule.cprems_of th; |
|
281 |
val asms = map Thm.assume cprems; |
|
282 |
in |
|
283 |
[foldr1 (fn (x, x') => [x, x'] MRS Data.conjI) |
|
284 |
(map (fn x => Drule.implies_elim_list x asms) (th :: ths)) |
|
285 |
|> Drule.implies_intr_list cprems |
|
12305 | 286 |
|> Drule.standard' |
13425
119ae829ad9b
support for split assumptions in cases (hyps vs. prems);
wenzelm
parents:
13197
diff
changeset
|
287 |
|> RuleCases.save r] |
11735 | 288 |
end; |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
289 |
|
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
290 |
|
18259 | 291 |
(* guess rule instantiation -- cannot handle pending goal parameters *) |
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
292 |
|
18205 | 293 |
local |
294 |
||
18147 | 295 |
fun dest_env thy (env as Envir.Envir {iTs, ...}) = |
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
296 |
let |
18147 | 297 |
val cert = Thm.cterm_of thy; |
298 |
val certT = Thm.ctyp_of thy; |
|
15794
5de27a5fc5ed
Adapted to new interface of instantiation and unification / matching functions.
berghofe
parents:
15708
diff
changeset
|
299 |
val pairs = Envir.alist_of env; |
18147 | 300 |
val ts = map (cert o Envir.norm_term env o #2 o #2) pairs; |
301 |
val xs = map2 (cert o Var) (map #1 pairs, map (#T o Thm.rep_cterm) ts); |
|
302 |
in (map (fn (xi, (S, T)) => (certT (TVar (xi, S)), certT T)) (Vartab.dest iTs), xs ~~ ts) end; |
|
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
303 |
|
18205 | 304 |
in |
305 |
||
18259 | 306 |
fun guess_instance rule i st = |
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
307 |
let |
18147 | 308 |
val {thy, maxidx, ...} = Thm.rep_thm st; |
309 |
val goal = Thm.term_of (Thm.cprem_of st i); (*exception Subscript*) |
|
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
310 |
val params = rev (rename_wrt_term goal (Logic.strip_params goal)); (*as they are printed :-*) |
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
311 |
in |
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
312 |
if not (null params) then |
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
313 |
(warning ("Cannot determine rule instantiation due to pending parameter(s): " ^ |
18147 | 314 |
commas (map (Sign.string_of_term thy o Syntax.mark_boundT) params)); |
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
315 |
Seq.single rule) |
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
316 |
else |
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
317 |
let |
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
318 |
val rule' = Thm.incr_indexes (maxidx + 1) rule; |
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
319 |
val concl = Logic.strip_assums_concl goal; |
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
320 |
in |
18147 | 321 |
Unify.smash_unifiers (thy, Envir.empty (#maxidx (Thm.rep_thm rule')), |
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
322 |
[(Thm.concl_of rule', concl)]) |
18147 | 323 |
|> Seq.map (fn env => Drule.instantiate (dest_env thy env) rule') |
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
324 |
end |
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
325 |
end handle Subscript => Seq.empty; |
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
326 |
|
18205 | 327 |
end; |
328 |
||
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
329 |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
330 |
(* special renaming of rule parameters *) |
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
331 |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
332 |
fun special_rename_params ctxt [[SOME (Free (z, Type (T, _)))]] thm = |
18147 | 333 |
let |
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
334 |
val x = ProofContext.revert_skolem ctxt z; |
18147 | 335 |
fun index i [] = [] |
336 |
| index i (y :: ys) = |
|
337 |
if x = y then x ^ string_of_int i :: index (i + 1) ys |
|
338 |
else y :: index i ys; |
|
339 |
fun rename_params [] = [] |
|
340 |
| rename_params ((y, Type (U, _)) :: ys) = |
|
341 |
(if U = T then x else y) :: rename_params ys |
|
342 |
| rename_params ((y, _) :: ys) = y :: rename_params ys; |
|
343 |
fun rename_asm A = |
|
344 |
let |
|
345 |
val xs = rename_params (Logic.strip_params A); |
|
346 |
val xs' = |
|
347 |
(case List.filter (equal x) xs of |
|
348 |
[] => xs | [_] => xs | _ => index 1 xs); |
|
349 |
in Logic.list_rename_params (xs', A) end; |
|
350 |
fun rename_prop p = |
|
351 |
let val (As, C) = Logic.strip_horn p |
|
352 |
in Logic.list_implies (map rename_asm As, C) end; |
|
353 |
val cp' = cterm_fun rename_prop (Thm.cprop_of thm); |
|
354 |
val thm' = Thm.equal_elim (Thm.reflexive cp') thm; |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
355 |
in RuleCases.save thm thm' end |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
356 |
| special_rename_params _ _ thm = thm; |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
357 |
|
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
358 |
|
18205 | 359 |
(* rule_versions *) |
360 |
||
361 |
fun rule_versions rule = Seq.cons (rule, |
|
18235 | 362 |
(Seq.make (fn () => |
18240 | 363 |
SOME (localize rule, Seq.empty))) |
18205 | 364 |
|> Seq.filter (not o curry Thm.eq_thm rule)) |
18224 | 365 |
|> Seq.map (pair (RuleCases.get rule)); |
18205 | 366 |
|
18235 | 367 |
fun rule_instance thy inst rule = |
368 |
Drule.cterm_instantiate (prep_inst thy align_left I (Thm.prop_of rule, inst)) rule; |
|
369 |
||
18205 | 370 |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
371 |
(* induct_tac *) |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
372 |
|
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
373 |
(* |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
374 |
rule selection scheme: |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
375 |
`x:A` induct ... - set induction |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
376 |
induct x - type induction |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
377 |
... induct ... r - explicit rule |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
378 |
*) |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
379 |
|
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
380 |
local |
15235
614a804d7116
Induction now preserves the name of the induction variable.
nipkow
parents:
14981
diff
changeset
|
381 |
|
11735 | 382 |
fun find_inductT ctxt insts = |
18147 | 383 |
fold_rev multiply (insts |> List.mapPartial (fn [] => NONE | ts => List.last ts) |
18205 | 384 |
|> map (InductAttrib.find_inductT ctxt o Term.fastype_of)) [[]] |
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
385 |
|> map join_rules |> List.concat; |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
386 |
|
18224 | 387 |
fun find_inductS ctxt (fact :: _) = InductAttrib.find_inductS ctxt (Thm.concl_of fact) |
11735 | 388 |
| find_inductS _ _ = []; |
389 |
||
16391 | 390 |
in |
11790
42393a11642d
simplified resolveq_cases_tac for cases, separate version for induct;
wenzelm
parents:
11781
diff
changeset
|
391 |
|
18235 | 392 |
fun induct_tac ctxt is_open def_insts fixing taking opt_rule facts = |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
393 |
let |
18224 | 394 |
val _ = warn_open is_open; |
18147 | 395 |
val thy = ProofContext.theory_of ctxt; |
396 |
val cert = Thm.cterm_of thy; |
|
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
397 |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
398 |
val ((insts, defs), defs_ctxt) = fold_map add_defs def_insts ctxt |>> split_list; |
18259 | 399 |
val atomized_defs = map (map ObjectLogic.atomize_thm) defs; |
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
400 |
|
18224 | 401 |
val inst_rule = apsnd (fn r => |
12168
dc93c2e82205
induct: rule_versions produces localized variants;
wenzelm
parents:
12162
diff
changeset
|
402 |
if null insts then r |
11735 | 403 |
else (align_right "Rule has fewer conclusions than arguments given" |
404 |
(Data.dest_concls (Thm.concl_of r)) insts |
|
18205 | 405 |
|> (List.concat o map (prep_inst thy align_right (atomize_term thy))) |
12168
dc93c2e82205
induct: rule_versions produces localized variants;
wenzelm
parents:
12162
diff
changeset
|
406 |
|> Drule.cterm_instantiate) r); |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
407 |
|
11735 | 408 |
val ruleq = |
409 |
(case opt_rule of |
|
18205 | 410 |
SOME r => r |> rule_versions |> Seq.map inst_rule |
411 |
| NONE => |
|
412 |
(find_inductS ctxt facts @ |
|
413 |
map (special_rename_params defs_ctxt insts) (find_inductT ctxt insts)) |
|
414 |
|> tap (trace_rules ctxt InductAttrib.inductN) |
|
18224 | 415 |
|> Seq.of_list |> Seq.maps rule_versions |> Seq.maps (Seq.try inst_rule)); |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
416 |
|
18224 | 417 |
fun rule_cases rule = RuleCases.make is_open (SOME (Thm.prop_of rule)) (rulified_term rule); |
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
418 |
in |
18205 | 419 |
(fn i => fn st => |
18224 | 420 |
ruleq |
18235 | 421 |
|> Seq.maps (RuleCases.consume (List.concat defs) facts) |
18224 | 422 |
|> Seq.maps (fn ((cases, (k, more_facts)), rule) => |
18205 | 423 |
(CONJUNCTS (ALLGOALS (fn j => |
18259 | 424 |
Method.insert_tac (more_facts @ nth_list atomized_defs (j - 1)) j |
18250
dfe5d09514eb
fix_tac: proper treatment of major premises in goal;
wenzelm
parents:
18240
diff
changeset
|
425 |
THEN fix_tac defs_ctxt k (nth_list fixing (j - 1)) j)) |
18205 | 426 |
THEN' atomize_tac) i st |> Seq.maps (fn st' => |
18259 | 427 |
guess_instance (internalize k rule) i st' |
18235 | 428 |
|> Seq.map (rule_instance thy taking) |
429 |
|> Seq.maps (fn rule' => |
|
18224 | 430 |
CASES (rule_cases rule' cases) |
431 |
(Tactic.rtac rule' i THEN |
|
432 |
PRIMSEQ (ProofContext.exports defs_ctxt ctxt)) st')))) |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
433 |
THEN_ALL_NEW_CASES rulify_tac |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
434 |
end; |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
435 |
|
18205 | 436 |
end; |
437 |
||
438 |
||
439 |
||
440 |
(** coinduct method **) |
|
441 |
||
442 |
(* |
|
443 |
rule selection scheme: |
|
18224 | 444 |
goal "x:A" coinduct ... - set coinduction |
445 |
coinduct x - type coinduction |
|
446 |
coinduct ... r - explicit rule |
|
18205 | 447 |
*) |
448 |
||
449 |
local |
|
450 |
||
451 |
fun find_coinductT ctxt (SOME t :: _) = InductAttrib.find_coinductT ctxt (Term.fastype_of t) |
|
452 |
| find_coinductT _ _ = []; |
|
453 |
||
18224 | 454 |
fun find_coinductS ctxt goal = InductAttrib.find_coinductS ctxt (Logic.strip_assums_concl goal); |
18205 | 455 |
|
456 |
in |
|
457 |
||
18235 | 458 |
fun coinduct_tac ctxt is_open inst taking opt_rule facts = |
18205 | 459 |
let |
18224 | 460 |
val _ = warn_open is_open; |
18205 | 461 |
val thy = ProofContext.theory_of ctxt; |
462 |
val cert = Thm.cterm_of thy; |
|
463 |
||
18224 | 464 |
val inst_rule = apsnd (fn r => |
18205 | 465 |
if null inst then r |
466 |
else Drule.cterm_instantiate (prep_inst thy align_left I (Thm.concl_of r, inst)) r); |
|
467 |
||
18224 | 468 |
fun ruleq goal = |
18205 | 469 |
(case opt_rule of |
470 |
SOME r => r |> rule_versions |> Seq.map inst_rule |
|
471 |
| NONE => |
|
18224 | 472 |
(find_coinductS ctxt goal @ find_coinductT ctxt inst) |
18205 | 473 |
|> tap (trace_rules ctxt InductAttrib.coinductN) |
18224 | 474 |
|> Seq.of_list |> Seq.maps rule_versions |> Seq.maps (Seq.try inst_rule)); |
18205 | 475 |
in |
18224 | 476 |
SUBGOAL_CASES (fn (goal, i) => fn st => |
477 |
ruleq goal |
|
18235 | 478 |
|> Seq.maps (RuleCases.consume [] facts) |
18224 | 479 |
|> Seq.maps (fn ((cases, (_, more_facts)), rule) => |
18259 | 480 |
guess_instance rule i st |
18235 | 481 |
|> Seq.map (rule_instance thy taking) |
482 |
|> Seq.maps (fn rule' => |
|
18224 | 483 |
CASES (make_cases is_open rule' cases) |
484 |
(Method.insert_tac more_facts i THEN Tactic.rtac rule' i) st))) |
|
18205 | 485 |
end; |
486 |
||
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
487 |
end; |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
488 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
489 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
490 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
491 |
(** concrete syntax **) |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
492 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
493 |
val openN = "open"; |
18205 | 494 |
val fixingN = "fixing"; |
18235 | 495 |
val takingN = "taking"; |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
496 |
val ruleN = "rule"; |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
497 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
498 |
local |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
499 |
|
15703 | 500 |
fun named_rule k arg get = |
501 |
Scan.lift (Args.$$$ k -- Args.colon) |-- arg :-- (fn name => Scan.peek (fn ctxt => |
|
502 |
(case get ctxt name of SOME x => Scan.succeed x |
|
503 |
| NONE => error ("No rule for " ^ k ^ " " ^ quote name)))) >> #2; |
|
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
504 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
505 |
fun rule get_type get_set = |
15703 | 506 |
named_rule InductAttrib.typeN Args.local_tyname get_type || |
507 |
named_rule InductAttrib.setN Args.local_const get_set || |
|
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
508 |
Scan.lift (Args.$$$ ruleN -- Args.colon) |-- Attrib.local_thm; |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
509 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
510 |
val cases_rule = rule InductAttrib.lookup_casesT InductAttrib.lookup_casesS; |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
511 |
val induct_rule = rule InductAttrib.lookup_inductT InductAttrib.lookup_inductS; |
18205 | 512 |
val coinduct_rule = rule InductAttrib.lookup_coinductT InductAttrib.lookup_coinductS; |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
513 |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
514 |
val inst = Scan.lift (Args.$$$ "_") >> K NONE || Args.local_term >> SOME; |
18147 | 515 |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
516 |
val def_inst = |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
517 |
((Scan.lift (Args.name --| (Args.$$$ "\\<equiv>" || Args.$$$ "==")) >> SOME) |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
518 |
-- Args.local_term) >> SOME || |
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
519 |
inst >> Option.map (pair NONE); |
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
520 |
|
18147 | 521 |
val free = Scan.state -- Args.local_term >> (fn (_, Free v) => v | (ctxt, t) => |
522 |
error ("Bad free variable: " ^ ProofContext.string_of_term ctxt t)); |
|
523 |
||
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
524 |
fun unless_more_args scan = Scan.unless (Scan.lift |
18235 | 525 |
((Args.$$$ fixingN || Args.$$$ takingN || Args.$$$ InductAttrib.typeN || |
526 |
Args.$$$ InductAttrib.setN || Args.$$$ ruleN) -- Args.colon)) scan; |
|
18205 | 527 |
|
528 |
val fixing = Scan.optional (Scan.lift (Args.$$$ fixingN -- Args.colon) |-- |
|
529 |
Args.and_list1 (Scan.repeat (unless_more_args free))) []; |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
530 |
|
18235 | 531 |
val taking = Scan.optional (Scan.lift (Args.$$$ takingN -- Args.colon) |-- |
532 |
Scan.repeat1 (unless_more_args inst)) []; |
|
533 |
||
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
534 |
in |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
535 |
|
18235 | 536 |
fun cases_meth src = |
537 |
Method.syntax (Args.mode openN -- |
|
538 |
(Args.and_list (Scan.repeat (unless_more_args inst)) -- Scan.option cases_rule)) src |
|
539 |
#> (fn (ctxt, (is_open, (insts, opt_rule))) => |
|
540 |
Method.METHOD_CASES (fn facts => |
|
541 |
Seq.DETERM (HEADGOAL (cases_tac ctxt is_open insts opt_rule facts)))); |
|
18178
9e4dfe031525
induct: support local definitions to be passed through the induction;
wenzelm
parents:
18147
diff
changeset
|
542 |
|
18235 | 543 |
fun induct_meth src = |
544 |
Method.syntax (Args.mode openN -- |
|
545 |
(Args.and_list (Scan.repeat (unless_more_args def_inst)) -- |
|
546 |
(fixing -- taking -- Scan.option induct_rule))) src |
|
547 |
#> (fn (ctxt, (is_open, (insts, ((fixing, taking), opt_rule)))) => |
|
548 |
Method.RAW_METHOD_CASES (fn facts => |
|
549 |
Seq.DETERM (HEADGOAL (induct_tac ctxt is_open insts fixing taking opt_rule facts)))); |
|
18205 | 550 |
|
18235 | 551 |
fun coinduct_meth src = |
552 |
Method.syntax (Args.mode openN -- |
|
553 |
(Scan.repeat (unless_more_args inst) -- taking -- Scan.option coinduct_rule)) src |
|
554 |
#> (fn (ctxt, (is_open, ((insts, taking), opt_rule))) => |
|
555 |
Method.RAW_METHOD_CASES (fn facts => |
|
556 |
Seq.DETERM (HEADGOAL (coinduct_tac ctxt is_open insts taking opt_rule facts)))); |
|
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
557 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
558 |
end; |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
559 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
560 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
561 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
562 |
(** theory setup **) |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
563 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
564 |
val setup = |
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
565 |
[Method.add_methods |
18235 | 566 |
[(InductAttrib.casesN, cases_meth, "case analysis on types or sets"), |
567 |
(InductAttrib.inductN, induct_meth, "induction on types or sets"), |
|
568 |
(InductAttrib.coinductN, coinduct_meth, "coinduction on types or sets")]]; |
|
11670
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
569 |
|
59f79df42d1f
proof by cases and induction on types and sets (used to be specific for HOL);
wenzelm
parents:
diff
changeset
|
570 |
end; |