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