6442
|
1 |
(* Title: HOL/Tools/induct_method.ML
|
|
2 |
ID: $Id$
|
|
3 |
Author: Markus Wenzel, TU Muenchen
|
|
4 |
|
8376
|
5 |
Proof by cases and induction on types and sets.
|
6442
|
6 |
*)
|
|
7 |
|
|
8 |
signature INDUCT_METHOD =
|
|
9 |
sig
|
8376
|
10 |
val dest_global_rules: theory ->
|
|
11 |
{type_cases: (string * thm) list, set_cases: (string * thm) list,
|
|
12 |
type_induct: (string * thm) list, set_induct: (string * thm) list}
|
8308
|
13 |
val print_global_rules: theory -> unit
|
8376
|
14 |
val dest_local_rules: Proof.context ->
|
|
15 |
{type_cases: (string * thm) list, set_cases: (string * thm) list,
|
|
16 |
type_induct: (string * thm) list, set_induct: (string * thm) list}
|
8308
|
17 |
val print_local_rules: Proof.context -> unit
|
8431
|
18 |
val vars_of: term -> term list
|
8695
|
19 |
val concls_of: thm -> term list
|
8308
|
20 |
val cases_type_global: string -> theory attribute
|
|
21 |
val cases_set_global: string -> theory attribute
|
|
22 |
val cases_type_local: string -> Proof.context attribute
|
|
23 |
val cases_set_local: string -> Proof.context attribute
|
|
24 |
val induct_type_global: string -> theory attribute
|
|
25 |
val induct_set_global: string -> theory attribute
|
|
26 |
val induct_type_local: string -> Proof.context attribute
|
|
27 |
val induct_set_local: string -> Proof.context attribute
|
8337
|
28 |
val con_elim_tac: simpset -> tactic
|
|
29 |
val con_elim_solved_tac: simpset -> tactic
|
6442
|
30 |
val setup: (theory -> theory) list
|
|
31 |
end;
|
|
32 |
|
|
33 |
structure InductMethod: INDUCT_METHOD =
|
|
34 |
struct
|
|
35 |
|
8337
|
36 |
|
8308
|
37 |
(** global and local induct data **)
|
6442
|
38 |
|
8308
|
39 |
(* rules *)
|
|
40 |
|
|
41 |
type rules = (string * thm) NetRules.T;
|
|
42 |
|
|
43 |
fun eq_rule ((s1:string, th1), (s2, th2)) = s1 = s2 andalso Thm.eq_thm (th1, th2);
|
|
44 |
|
|
45 |
val type_rules = NetRules.init eq_rule (Thm.concl_of o #2);
|
|
46 |
val set_rules = NetRules.init eq_rule (Thm.major_prem_of o #2);
|
|
47 |
|
|
48 |
fun lookup_rule (rs:rules) name = Library.assoc (NetRules.rules rs, name);
|
|
49 |
|
|
50 |
fun print_rules kind rs =
|
|
51 |
let val thms = map snd (NetRules.rules rs)
|
8315
|
52 |
in Pretty.writeln (Pretty.big_list kind (map Display.pretty_thm thms)) end;
|
8308
|
53 |
|
|
54 |
|
|
55 |
(* theory data kind 'HOL/induct_method' *)
|
|
56 |
|
|
57 |
structure GlobalInductArgs =
|
|
58 |
struct
|
|
59 |
val name = "HOL/induct_method";
|
|
60 |
type T = (rules * rules) * (rules * rules);
|
|
61 |
|
|
62 |
val empty = ((type_rules, set_rules), (type_rules, set_rules));
|
|
63 |
val copy = I;
|
|
64 |
val prep_ext = I;
|
|
65 |
fun merge (((casesT1, casesS1), (inductT1, inductS1)),
|
|
66 |
((casesT2, casesS2), (inductT2, inductS2))) =
|
|
67 |
((NetRules.merge (casesT1, casesT2), NetRules.merge (casesS1, casesS2)),
|
|
68 |
(NetRules.merge (inductT1, inductT2), NetRules.merge (inductS1, inductS2)));
|
|
69 |
|
|
70 |
fun print _ ((casesT, casesS), (inductT, inductS)) =
|
8315
|
71 |
(print_rules "type cases:" casesT;
|
|
72 |
print_rules "set cases:" casesS;
|
|
73 |
print_rules "type induct:" inductT;
|
|
74 |
print_rules "set induct:" inductS);
|
8376
|
75 |
|
|
76 |
fun dest ((casesT, casesS), (inductT, inductS)) =
|
|
77 |
{type_cases = NetRules.rules casesT,
|
|
78 |
set_cases = NetRules.rules casesS,
|
|
79 |
type_induct = NetRules.rules inductT,
|
|
80 |
set_induct = NetRules.rules inductS};
|
8308
|
81 |
end;
|
|
82 |
|
|
83 |
structure GlobalInduct = TheoryDataFun(GlobalInductArgs);
|
|
84 |
val print_global_rules = GlobalInduct.print;
|
8376
|
85 |
val dest_global_rules = GlobalInductArgs.dest o GlobalInduct.get;
|
8308
|
86 |
|
|
87 |
|
|
88 |
(* proof data kind 'HOL/induct_method' *)
|
|
89 |
|
|
90 |
structure LocalInductArgs =
|
|
91 |
struct
|
|
92 |
val name = "HOL/induct_method";
|
|
93 |
type T = GlobalInductArgs.T;
|
8278
|
94 |
|
8308
|
95 |
fun init thy = GlobalInduct.get thy;
|
|
96 |
fun print x = GlobalInductArgs.print x;
|
|
97 |
end;
|
|
98 |
|
|
99 |
structure LocalInduct = ProofDataFun(LocalInductArgs);
|
|
100 |
val print_local_rules = LocalInduct.print;
|
8376
|
101 |
val dest_local_rules = GlobalInductArgs.dest o LocalInduct.get;
|
8308
|
102 |
|
|
103 |
|
|
104 |
(* access rules *)
|
|
105 |
|
|
106 |
val get_cases = #1 o LocalInduct.get;
|
|
107 |
val get_induct = #2 o LocalInduct.get;
|
|
108 |
|
|
109 |
val lookup_casesT = lookup_rule o #1 o get_cases;
|
|
110 |
val lookup_casesS = lookup_rule o #2 o get_cases;
|
|
111 |
val lookup_inductT = lookup_rule o #1 o get_induct;
|
|
112 |
val lookup_inductS = lookup_rule o #2 o get_induct;
|
|
113 |
|
|
114 |
|
|
115 |
|
|
116 |
(** attributes **)
|
|
117 |
|
|
118 |
local
|
|
119 |
|
|
120 |
fun mk_att f g name (x, thm) = (f (g (name, thm)) x, thm);
|
|
121 |
|
|
122 |
fun add_casesT rule x = apfst (apfst (NetRules.insert rule)) x;
|
|
123 |
fun add_casesS rule x = apfst (apsnd (NetRules.insert rule)) x;
|
|
124 |
fun add_inductT rule x = apsnd (apfst (NetRules.insert rule)) x;
|
|
125 |
fun add_inductS rule x = apsnd (apsnd (NetRules.insert rule)) x;
|
|
126 |
|
|
127 |
in
|
|
128 |
|
|
129 |
val cases_type_global = mk_att GlobalInduct.map add_casesT;
|
|
130 |
val cases_set_global = mk_att GlobalInduct.map add_casesS;
|
|
131 |
val induct_type_global = mk_att GlobalInduct.map add_inductT;
|
|
132 |
val induct_set_global = mk_att GlobalInduct.map add_inductS;
|
|
133 |
|
|
134 |
val cases_type_local = mk_att LocalInduct.map add_casesT;
|
|
135 |
val cases_set_local = mk_att LocalInduct.map add_casesS;
|
|
136 |
val induct_type_local = mk_att LocalInduct.map add_inductT;
|
|
137 |
val induct_set_local = mk_att LocalInduct.map add_inductS;
|
|
138 |
|
|
139 |
end;
|
|
140 |
|
|
141 |
|
|
142 |
|
|
143 |
(** misc utils **)
|
8278
|
144 |
|
8695
|
145 |
(* thms and terms *)
|
|
146 |
|
|
147 |
val concls_of = HOLogic.dest_conj o HOLogic.dest_Trueprop o Thm.concl_of;
|
8344
|
148 |
|
8278
|
149 |
fun vars_of tm = (*ordered left-to-right, preferring right!*)
|
8308
|
150 |
Term.foldl_aterms (fn (ts, t as Var _) => t :: ts | (ts, _) => ts) ([], tm)
|
8278
|
151 |
|> Library.distinct |> rev;
|
|
152 |
|
8308
|
153 |
fun type_name t =
|
|
154 |
#1 (Term.dest_Type (Term.type_of t))
|
|
155 |
handle TYPE _ => raise TERM ("Bad type of term argument", [t]);
|
8278
|
156 |
|
|
157 |
|
8337
|
158 |
(* simplifying cases rules *)
|
|
159 |
|
|
160 |
local
|
|
161 |
|
|
162 |
(*delete needless equality assumptions*)
|
|
163 |
val refl_thin = prove_goal HOL.thy "!!P. [| a=a; P |] ==> P"
|
|
164 |
(fn _ => [assume_tac 1]);
|
|
165 |
|
|
166 |
val elim_rls = [asm_rl, FalseE, refl_thin, conjE, exE, Pair_inject];
|
|
167 |
|
|
168 |
val elim_tac = REPEAT o Tactic.eresolve_tac elim_rls;
|
|
169 |
|
|
170 |
fun simp_case_tac ss =
|
|
171 |
EVERY' [elim_tac, asm_full_simp_tac ss, elim_tac, REPEAT o bound_hyp_subst_tac];
|
|
172 |
|
|
173 |
in
|
|
174 |
|
|
175 |
fun con_elim_tac ss = ALLGOALS (simp_case_tac ss) THEN prune_params_tac;
|
|
176 |
|
|
177 |
fun con_elim_solved_tac ss =
|
|
178 |
ALLGOALS (fn i => TRY (simp_case_tac ss i THEN_MAYBE no_tac)) THEN prune_params_tac;
|
|
179 |
|
|
180 |
end;
|
|
181 |
|
|
182 |
|
8278
|
183 |
|
|
184 |
(** cases method **)
|
|
185 |
|
8308
|
186 |
(*
|
|
187 |
rule selection:
|
|
188 |
cases - classical case split
|
8376
|
189 |
cases t - datatype exhaustion
|
|
190 |
<x:A> cases ... - set elimination
|
8451
|
191 |
... cases ... R - explicit rule
|
8308
|
192 |
*)
|
8278
|
193 |
|
8344
|
194 |
local
|
|
195 |
|
8308
|
196 |
fun cases_var thm =
|
|
197 |
(case try (hd o vars_of o hd o Logic.strip_assums_hyp o Library.last_elem o Thm.prems_of) thm of
|
|
198 |
None => raise THM ("Malformed cases rule", 0, [thm])
|
|
199 |
| Some x => x);
|
|
200 |
|
8337
|
201 |
fun simplify_cases ctxt =
|
|
202 |
Tactic.rule_by_tactic (con_elim_solved_tac (Simplifier.get_local_simpset ctxt));
|
|
203 |
|
8344
|
204 |
fun cases_tac (ctxt, (simplified, args)) facts =
|
8308
|
205 |
let
|
|
206 |
val sg = ProofContext.sign_of ctxt;
|
|
207 |
val cert = Thm.cterm_of sg;
|
8278
|
208 |
|
8308
|
209 |
fun inst_rule t thm =
|
|
210 |
Drule.cterm_instantiate [(cert (cases_var thm), cert t)] thm;
|
6442
|
211 |
|
8376
|
212 |
val cond_simp = if simplified then simplify_cases ctxt else I;
|
|
213 |
|
|
214 |
fun find_cases th =
|
|
215 |
NetRules.may_unify (#2 (get_cases ctxt))
|
|
216 |
(Logic.strip_assums_concl (#prop (Thm.rep_thm th)));
|
|
217 |
|
|
218 |
val rules =
|
8344
|
219 |
(case (args, facts) of
|
8540
|
220 |
((None, None), []) => [(case_split_thm, ["True", "False"])]
|
8376
|
221 |
| ((Some t, None), []) =>
|
8308
|
222 |
let val name = type_name t in
|
|
223 |
(case lookup_casesT ctxt name of
|
|
224 |
None => error ("No cases rule for type: " ^ quote name)
|
8376
|
225 |
| Some thm => [(inst_rule t thm, RuleCases.get thm)])
|
8308
|
226 |
end
|
8376
|
227 |
| ((None, None), th :: _) => map (RuleCases.add o #2) (find_cases th)
|
|
228 |
| ((Some t, None), th :: _) =>
|
|
229 |
(case find_cases th of (*may instantiate first rule only!*)
|
|
230 |
(_, thm) :: _ => [(inst_rule t thm, RuleCases.get thm)]
|
|
231 |
| [] => [])
|
|
232 |
| ((None, Some thm), _) => [RuleCases.add thm]
|
|
233 |
| ((Some t, Some thm), _) => [(inst_rule t thm, RuleCases.get thm)]);
|
|
234 |
|
|
235 |
fun prep_rule (thm, cases) =
|
|
236 |
Seq.map (rpair cases o cond_simp) (Method.multi_resolves facts [thm]);
|
|
237 |
in Method.resolveq_cases_tac (Seq.flat (Seq.map prep_rule (Seq.of_list rules))) end;
|
8278
|
238 |
|
8344
|
239 |
in
|
|
240 |
|
8671
|
241 |
val cases_meth = Method.METHOD_CASES o (HEADGOAL oo cases_tac);
|
8278
|
242 |
|
8344
|
243 |
end;
|
|
244 |
|
8278
|
245 |
|
|
246 |
|
|
247 |
(** induct method **)
|
|
248 |
|
8308
|
249 |
(*
|
|
250 |
rule selection:
|
|
251 |
induct - mathematical induction
|
8376
|
252 |
induct x - datatype induction
|
|
253 |
<x:A> induct ... - set induction
|
8451
|
254 |
... induct ... R - explicit rule
|
8308
|
255 |
*)
|
8278
|
256 |
|
8344
|
257 |
local
|
|
258 |
|
8376
|
259 |
infix 1 THEN_ALL_NEW_CASES;
|
|
260 |
|
|
261 |
fun (tac1 THEN_ALL_NEW_CASES tac2) i st =
|
|
262 |
st |> Seq.THEN (tac1 i, (fn (st', cases) =>
|
8540
|
263 |
Seq.map (rpair cases) (Seq.INTERVAL tac2 i (i + nprems_of st' - nprems_of st) st')));
|
8376
|
264 |
|
|
265 |
|
8330
|
266 |
fun induct_rule ctxt t =
|
|
267 |
let val name = type_name t in
|
|
268 |
(case lookup_inductT ctxt name of
|
|
269 |
None => error ("No induct rule for type: " ^ quote name)
|
8332
|
270 |
| Some thm => (name, thm))
|
8330
|
271 |
end;
|
|
272 |
|
8332
|
273 |
fun join_rules [(_, thm)] = thm
|
8330
|
274 |
| join_rules raw_thms =
|
|
275 |
let
|
8332
|
276 |
val thms = (map (apsnd Drule.freeze_all) raw_thms);
|
|
277 |
fun eq_prems ((_, th1), (_, th2)) =
|
|
278 |
Term.aconvs (Thm.prems_of th1, Thm.prems_of th2);
|
8330
|
279 |
in
|
8332
|
280 |
(case Library.gen_distinct eq_prems thms of
|
|
281 |
[(_, thm)] =>
|
|
282 |
let
|
|
283 |
val cprems = Drule.cprems_of thm;
|
|
284 |
val asms = map Thm.assume cprems;
|
|
285 |
fun strip (_, th) = Drule.implies_elim_list th asms;
|
|
286 |
in
|
|
287 |
foldr1 (fn (th, th') => [th, th'] MRS conjI) (map strip thms)
|
|
288 |
|> Drule.implies_intr_list cprems
|
|
289 |
|> Drule.standard
|
|
290 |
end
|
|
291 |
| [] => error "No rule given"
|
|
292 |
| bads => error ("Incompatible rules for " ^ commas_quote (map #1 bads)))
|
8330
|
293 |
end;
|
|
294 |
|
8376
|
295 |
|
8344
|
296 |
fun induct_tac (ctxt, (stripped, args)) facts =
|
8308
|
297 |
let
|
|
298 |
val sg = ProofContext.sign_of ctxt;
|
|
299 |
val cert = Thm.cterm_of sg;
|
|
300 |
|
8695
|
301 |
fun prep_var (x, Some t) = Some (cert x, cert t)
|
|
302 |
| prep_var (_, None) = None;
|
|
303 |
|
8308
|
304 |
fun prep_inst (concl, ts) =
|
|
305 |
let val xs = vars_of concl; val n = length xs - length ts in
|
8695
|
306 |
if n < 0 then error "More variables than given than in induction rule"
|
|
307 |
else mapfilter prep_var (Library.drop (n, xs) ~~ ts)
|
8308
|
308 |
end;
|
8278
|
309 |
|
8308
|
310 |
fun inst_rule insts thm =
|
8695
|
311 |
let val concls = concls_of thm in
|
|
312 |
if length concls < length insts then
|
|
313 |
error "More arguments than given than in induction rule"
|
|
314 |
else Drule.cterm_instantiate (flat (map prep_inst (concls ~~ insts))) thm
|
|
315 |
end;
|
8278
|
316 |
|
8376
|
317 |
fun find_induct th =
|
|
318 |
NetRules.may_unify (#2 (get_induct ctxt))
|
|
319 |
(Logic.strip_assums_concl (#prop (Thm.rep_thm th)));
|
|
320 |
|
|
321 |
val rules =
|
8308
|
322 |
(case (args, facts) of
|
8540
|
323 |
(([], None), []) => []
|
8376
|
324 |
| ((insts, None), []) =>
|
8695
|
325 |
let val thms = map (induct_rule ctxt o last_elem o mapfilter I) insts
|
|
326 |
handle Library.LIST _ => error "Unable to figure out type induction rule"
|
8376
|
327 |
in [(inst_rule insts (join_rules thms), RuleCases.get (#2 (hd thms)))] end
|
|
328 |
| (([], None), th :: _) => map (RuleCases.add o #2) (find_induct th)
|
|
329 |
| ((insts, None), th :: _) =>
|
|
330 |
(case find_induct th of (*may instantiate first rule only!*)
|
|
331 |
(_, thm) :: _ => [(inst_rule insts thm, RuleCases.get thm)]
|
|
332 |
| [] => [])
|
|
333 |
| (([], Some thm), _) => [RuleCases.add thm]
|
|
334 |
| ((insts, Some thm), _) => [(inst_rule insts thm, RuleCases.get thm)]);
|
|
335 |
|
|
336 |
fun prep_rule (thm, cases) =
|
|
337 |
Seq.map (rpair cases) (Method.multi_resolves facts [thm]);
|
|
338 |
val tac = Method.resolveq_cases_tac (Seq.flat (Seq.map prep_rule (Seq.of_list rules)));
|
8344
|
339 |
in
|
8688
|
340 |
if stripped then tac THEN_ALL_NEW_CASES (REPEAT o Tactic.match_tac [impI, allI, ballI])
|
8376
|
341 |
else tac
|
8344
|
342 |
end;
|
|
343 |
|
|
344 |
in
|
8278
|
345 |
|
8671
|
346 |
val induct_meth = Method.METHOD_CASES o (HEADGOAL oo induct_tac);
|
8278
|
347 |
|
8344
|
348 |
end;
|
|
349 |
|
8278
|
350 |
|
|
351 |
|
|
352 |
(** concrete syntax **)
|
|
353 |
|
8308
|
354 |
val casesN = "cases";
|
|
355 |
val inductN = "induct";
|
8344
|
356 |
|
8337
|
357 |
val simplifiedN = "simplified";
|
8344
|
358 |
val strippedN = "stripped";
|
|
359 |
|
8308
|
360 |
val typeN = "type";
|
|
361 |
val setN = "set";
|
|
362 |
val ruleN = "rule";
|
|
363 |
|
|
364 |
|
|
365 |
(* attributes *)
|
|
366 |
|
|
367 |
fun spec k = (Args.$$$ k -- Args.$$$ ":") |-- Args.!!! Args.name;
|
|
368 |
|
|
369 |
fun attrib sign_of add_type add_set = Scan.depend (fn x =>
|
|
370 |
let val sg = sign_of x in
|
|
371 |
spec typeN >> (add_type o Sign.intern_tycon sg) ||
|
|
372 |
spec setN >> (add_set o Sign.intern_const sg)
|
|
373 |
end >> pair x);
|
|
374 |
|
|
375 |
val cases_attr =
|
|
376 |
(Attrib.syntax (attrib Theory.sign_of cases_type_global cases_set_global),
|
|
377 |
Attrib.syntax (attrib ProofContext.sign_of cases_type_local cases_set_local));
|
|
378 |
|
|
379 |
val induct_attr =
|
|
380 |
(Attrib.syntax (attrib Theory.sign_of induct_type_global induct_set_global),
|
|
381 |
Attrib.syntax (attrib ProofContext.sign_of induct_type_local induct_set_local));
|
|
382 |
|
|
383 |
|
|
384 |
(* methods *)
|
|
385 |
|
8278
|
386 |
local
|
6442
|
387 |
|
8308
|
388 |
fun err k get name =
|
|
389 |
(case get name of Some x => x
|
|
390 |
| None => error ("No rule for " ^ k ^ " " ^ quote name));
|
6442
|
391 |
|
8308
|
392 |
fun rule get_type get_set =
|
|
393 |
Scan.depend (fn ctxt =>
|
|
394 |
let val sg = ProofContext.sign_of ctxt in
|
|
395 |
spec typeN >> (err typeN (get_type ctxt) o Sign.intern_tycon sg) ||
|
|
396 |
spec setN >> (err setN (get_set ctxt) o Sign.intern_const sg)
|
|
397 |
end >> pair ctxt) ||
|
|
398 |
Scan.lift (Args.$$$ ruleN -- Args.$$$ ":") |-- Attrib.local_thm;
|
6442
|
399 |
|
8308
|
400 |
val cases_rule = rule lookup_casesT lookup_casesS;
|
|
401 |
val induct_rule = rule lookup_inductT lookup_inductS;
|
6442
|
402 |
|
8308
|
403 |
val kind = (Args.$$$ typeN || Args.$$$ setN || Args.$$$ ruleN) -- Args.$$$ ":";
|
|
404 |
val term = Scan.unless (Scan.lift kind) Args.local_term;
|
8695
|
405 |
val term_dummy = Scan.unless (Scan.lift kind)
|
|
406 |
(Scan.lift (Args.$$$ "_") >> K None || Args.local_term >> Some);
|
6446
|
407 |
|
8344
|
408 |
fun mode name =
|
|
409 |
Scan.lift (Scan.optional (Args.$$$ name -- Args.$$$ ":" >> K true) false);
|
8337
|
410 |
|
8278
|
411 |
in
|
|
412 |
|
8695
|
413 |
val cases_args = Method.syntax (mode simplifiedN -- (Scan.option term -- Scan.option cases_rule));
|
|
414 |
val induct_args = Method.syntax
|
|
415 |
(mode strippedN -- (Args.and_list (Scan.repeat term_dummy) -- Scan.option induct_rule));
|
8278
|
416 |
|
|
417 |
end;
|
6446
|
418 |
|
|
419 |
|
6442
|
420 |
|
8278
|
421 |
(** theory setup **)
|
6446
|
422 |
|
8278
|
423 |
val setup =
|
8308
|
424 |
[GlobalInduct.init, LocalInduct.init,
|
|
425 |
Attrib.add_attributes
|
|
426 |
[(casesN, cases_attr, "cases rule for type or set"),
|
|
427 |
(inductN, induct_attr, "induction rule for type or set")],
|
|
428 |
Method.add_methods
|
|
429 |
[("cases", cases_meth oo cases_args, "case analysis on types or sets"),
|
|
430 |
("induct", induct_meth oo induct_args, "induction on types or sets")]];
|
6442
|
431 |
|
|
432 |
end;
|