author  blanchet 
Mon, 15 Sep 2014 10:49:07 +0200  
changeset 58335  a5a3b576fcfb 
parent 55715  bc04f1ab3c3a 
child 58826  2ed2eaabe3df 
permissions  rwrr 
28308  1 
(* Title: Tools/induct_tacs.ML 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

2 
Author: Makarius 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

3 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

4 
Unstructured induction and cases analysis. 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

5 
*) 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

6 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

7 
signature INDUCT_TACS = 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

8 
sig 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

9 
val case_tac: Proof.context > string > int > tactic 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

10 
val case_rule_tac: Proof.context > string > thm > int > tactic 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

11 
val induct_tac: Proof.context > string option list list > int > tactic 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

12 
val induct_rules_tac: Proof.context > string option list list > thm list > int > tactic 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

13 
val setup: theory > theory 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

14 
end 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

15 

45133  16 
structure Induct_Tacs: INDUCT_TACS = 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

17 
struct 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

18 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

19 
(* case analysis *) 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

20 

46836  21 
fun check_type ctxt (t, pos) = 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

22 
let 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

23 
val u = singleton (Variable.polymorphic ctxt) t; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

24 
val U = Term.fastype_of u; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

25 
val _ = Term.is_TVar U andalso 
55715
bc04f1ab3c3a
tuned messages  prefer quote before Position.here, which might be just \<here>;
wenzelm
parents:
55111
diff
changeset

26 
error ("Cannot determine type of " ^ 
bc04f1ab3c3a
tuned messages  prefer quote before Position.here, which might be just \<here>;
wenzelm
parents:
55111
diff
changeset

27 
quote (Syntax.string_of_term ctxt u) ^ Position.here pos); 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

28 
in (u, U) end; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

29 

30541  30 
fun gen_case_tac ctxt0 s opt_rule i st = 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

31 
let 
32863  32 
val (_, ctxt) = Variable.focus_subgoal i st ctxt0; 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

33 
val rule = 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

34 
(case opt_rule of 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

35 
SOME rule => rule 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

36 
 NONE => 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

37 
(case Induct.find_casesT ctxt 
46836  38 
(#2 (check_type ctxt (Proof_Context.read_term_schematic ctxt s, 
46849  39 
Syntax.read_token_pos s))) of 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

40 
rule :: _ => rule 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

41 
 [] => @{thm case_split})); 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

42 
val _ = Method.trace ctxt [rule]; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

43 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

44 
val xi = 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

45 
(case Induct.vars_of (Thm.term_of (Thm.cprem_of rule 1)) of 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

46 
Var (xi, _) :: _ => xi 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

47 
 _ => raise THM ("Malformed cases rule", 0, [rule])); 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

48 
in res_inst_tac ctxt [(xi, s)] rule i st end 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

49 
handle THM _ => Seq.empty; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

50 

30541  51 
fun case_tac ctxt s = gen_case_tac ctxt s NONE; 
52 
fun case_rule_tac ctxt s rule = gen_case_tac ctxt s (SOME rule); 

27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

53 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

54 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

55 
(* induction *) 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

56 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

57 
local 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

58 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

59 
fun prep_var (Var (ixn, _), SOME x) = SOME (ixn, x) 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

60 
 prep_var _ = NONE; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

61 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

62 
fun prep_inst (concl, xs) = 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

63 
let val vs = Induct.vars_of concl 
33957  64 
in map_filter prep_var (drop (length vs  length xs) vs ~~ xs) end; 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

65 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

66 
in 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

67 

30541  68 
fun gen_induct_tac ctxt0 varss opt_rules i st = 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

69 
let 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

70 
val ((_, goal), ctxt) = Variable.focus_subgoal i st ctxt0; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

71 
val (prems, concl) = Logic.strip_horn (Thm.term_of goal); 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

72 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

73 
fun induct_var name = 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

74 
let 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

75 
val t = Syntax.read_term ctxt name; 
46849  76 
val pos = Syntax.read_token_pos name; 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

77 
val (x, _) = Term.dest_Free t handle TERM _ => 
46836  78 
error ("Induction argument not a variable: " ^ 
55715
bc04f1ab3c3a
tuned messages  prefer quote before Position.here, which might be just \<here>;
wenzelm
parents:
55111
diff
changeset

79 
quote (Syntax.string_of_term ctxt t) ^ Position.here pos); 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

80 
val eq_x = fn Free (y, _) => x = y  _ => false; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

81 
val _ = 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

82 
if Term.exists_subterm eq_x concl then () 
46836  83 
else 
84 
error ("No such variable in subgoal: " ^ 

55715
bc04f1ab3c3a
tuned messages  prefer quote before Position.here, which might be just \<here>;
wenzelm
parents:
55111
diff
changeset

85 
quote (Syntax.string_of_term ctxt t) ^ Position.here pos); 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

86 
val _ = 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

87 
if (exists o Term.exists_subterm) eq_x prems then 
46836  88 
warning ("Induction variable occurs also among premises: " ^ 
55715
bc04f1ab3c3a
tuned messages  prefer quote before Position.here, which might be just \<here>;
wenzelm
parents:
55111
diff
changeset

89 
quote (Syntax.string_of_term ctxt t) ^ Position.here pos) 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

90 
else (); 
46836  91 
in #1 (check_type ctxt (t, pos)) end; 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

92 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

93 
val argss = map (map (Option.map induct_var)) varss; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

94 
val rule = 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

95 
(case opt_rules of 
33368  96 
SOME rules => #2 (Rule_Cases.strict_mutual_rule ctxt rules) 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

97 
 NONE => 
33368  98 
(case map_filter (Rule_Cases.mutual_rule ctxt) (Induct.get_inductT ctxt argss) of 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

99 
(_, rule) :: _ => rule 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

100 
 [] => raise THM ("No induction rules", 0, []))); 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

101 

54742
7a86358a3c0b
proper context for basic Simplifier operations: rewrite_rule, rewrite_goals_rule, rewrite_goals_tac etc.;
wenzelm
parents:
48992
diff
changeset

102 
val rule' = rule > Conv.fconv_rule (Conv.concl_conv ~1 (Object_Logic.atomize ctxt)); 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

103 
val _ = Method.trace ctxt [rule']; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

104 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

105 
val concls = Logic.dest_conjunctions (Thm.concl_of rule); 
40722
441260986b63
make two copies (!) of Library.UnequalLengths coincide with ListPair.UnequalLengths;
wenzelm
parents:
36960
diff
changeset

106 
val insts = maps prep_inst (concls ~~ varss) handle ListPair.UnequalLengths => 
27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

107 
error "Induction rule has different numbers of variables"; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

108 
in res_inst_tac ctxt insts rule' i st end 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

109 
handle THM _ => Seq.empty; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

110 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

111 
end; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

112 

30541  113 
fun induct_tac ctxt args = gen_induct_tac ctxt args NONE; 
114 
fun induct_rules_tac ctxt args rules = gen_induct_tac ctxt args (SOME rules); 

27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

115 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

116 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

117 
(* method syntax *) 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

118 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

119 
local 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

120 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

121 
val rule_spec = Scan.lift (Args.$$$ "rule"  Args.$$$ ":"); 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

122 
val opt_rule = Scan.option (rule_spec  Attrib.thm); 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

123 
val opt_rules = Scan.option (rule_spec  Attrib.thms); 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

124 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

125 
val varss = 
55111  126 
Parse.and_list' 
127 
(Scan.repeat (Scan.unless rule_spec (Scan.lift (Args.maybe Args.name_inner_syntax)))); 

27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

128 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

129 
in 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

130 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

131 
val setup = 
30541  132 
Method.setup @{binding case_tac} 
55111  133 
(Args.goal_spec  Scan.lift Args.name_inner_syntax  opt_rule >> 
30541  134 
(fn ((quant, s), r) => fn ctxt => SIMPLE_METHOD'' quant (gen_case_tac ctxt s r))) 
135 
"unstructured case analysis on types" #> 

136 
Method.setup @{binding induct_tac} 

137 
(Args.goal_spec  varss  opt_rules >> 

138 
(fn ((quant, vs), rs) => fn ctxt => SIMPLE_METHOD'' quant (gen_induct_tac ctxt vs rs))) 

139 
"unstructured induction on types"; 

27326
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

140 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

141 
end; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

142 

d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

143 
end; 
d3beec370964
moved src/HOL/Tools/induct_tacs.ML to src/Tools/induct_tacs.ML;
wenzelm
parents:
diff
changeset

144 