src/HOL/Tools/recdef.ML
author huffman
Fri Mar 30 12:32:35 2012 +0200 (2012-03-30)
changeset 47220 52426c62b5d0
parent 47067 4ef29b0c568f
child 47815 43f677b3ae91
permissions -rw-r--r--
replace lemmas eval_nat_numeral with a simpler reformulation
haftmann@31723
     1
(*  Title:      HOL/Tools/recdef.ML
wenzelm@6429
     2
    Author:     Markus Wenzel, TU Muenchen
wenzelm@6429
     3
wenzelm@6429
     4
Wrapper module for Konrad Slind's TFL package.
wenzelm@6429
     5
*)
wenzelm@6429
     6
haftmann@31723
     7
signature RECDEF =
wenzelm@6429
     8
sig
wenzelm@8657
     9
  val get_recdef: theory -> string
bulwahn@35756
    10
    -> {lhs: term, simps: thm list, rules: thm list list, induct: thm, tcs: term list} option
wenzelm@21505
    11
  val get_hints: Proof.context -> {simps: thm list, congs: (string * thm) list, wfs: thm list}
wenzelm@18728
    12
  val simp_add: attribute
wenzelm@18728
    13
  val simp_del: attribute
wenzelm@18728
    14
  val cong_add: attribute
wenzelm@18728
    15
  val cong_del: attribute
wenzelm@18728
    16
  val wf_add: attribute
wenzelm@18728
    17
  val wf_del: attribute
haftmann@29579
    18
  val add_recdef: bool -> xstring -> string -> ((binding * string) * Attrib.src list) list ->
wenzelm@15703
    19
    Attrib.src option -> theory -> theory
bulwahn@35756
    20
      * {lhs: term, simps: thm list, rules: thm list list, induct: thm, tcs: term list}
haftmann@29579
    21
  val add_recdef_i: bool -> xstring -> term -> ((binding * term) * attribute list) list ->
bulwahn@35756
    22
    theory -> theory * {lhs: term, simps: thm list, rules: thm list list, induct: thm, tcs: term list}
wenzelm@26336
    23
  val defer_recdef: xstring -> string list -> (Facts.ref * Attrib.src list) list
wenzelm@6557
    24
    -> theory -> theory * {induct_rules: thm}
wenzelm@27727
    25
  val defer_recdef_i: xstring -> term list -> thm list -> theory -> theory * {induct_rules: thm}
wenzelm@27727
    26
  val recdef_tc: bstring * Attrib.src list -> xstring -> int option -> bool ->
wenzelm@27727
    27
    local_theory -> Proof.state
wenzelm@27727
    28
  val recdef_tc_i: bstring * Attrib.src list -> string -> int option -> bool ->
wenzelm@27727
    29
    local_theory -> Proof.state
wenzelm@18708
    30
  val setup: theory -> theory
wenzelm@6429
    31
end;
wenzelm@6429
    32
haftmann@31723
    33
structure Recdef: RECDEF =
wenzelm@6429
    34
struct
wenzelm@6429
    35
wenzelm@6429
    36
wenzelm@9859
    37
(** recdef hints **)
wenzelm@6439
    38
wenzelm@9859
    39
(* type hints *)
wenzelm@9859
    40
wenzelm@9859
    41
type hints = {simps: thm list, congs: (string * thm) list, wfs: thm list};
wenzelm@9859
    42
wenzelm@9859
    43
fun mk_hints (simps, congs, wfs) = {simps = simps, congs = congs, wfs = wfs}: hints;
wenzelm@9859
    44
fun map_hints f ({simps, congs, wfs}: hints) = mk_hints (f (simps, congs, wfs));
wenzelm@9859
    45
wenzelm@9859
    46
fun map_simps f = map_hints (fn (simps, congs, wfs) => (f simps, congs, wfs));
wenzelm@9859
    47
fun map_congs f = map_hints (fn (simps, congs, wfs) => (simps, f congs, wfs));
wenzelm@9859
    48
fun map_wfs f = map_hints (fn (simps, congs, wfs) => (simps, congs, f wfs));
wenzelm@9859
    49
wenzelm@9859
    50
wenzelm@9859
    51
(* congruence rules *)
wenzelm@9859
    52
wenzelm@9859
    53
local
wenzelm@9859
    54
wenzelm@9859
    55
val cong_head =
wenzelm@9859
    56
  fst o Term.dest_Const o Term.head_of o fst o Logic.dest_equals o Thm.concl_of;
wenzelm@6439
    57
wenzelm@9859
    58
fun prep_cong raw_thm =
wenzelm@9859
    59
  let val thm = safe_mk_meta_eq raw_thm in (cong_head thm, thm) end;
wenzelm@9859
    60
wenzelm@9859
    61
in
wenzelm@9859
    62
wenzelm@9859
    63
fun add_cong raw_thm congs =
haftmann@21098
    64
  let
haftmann@21098
    65
    val (c, thm) = prep_cong raw_thm;
haftmann@21098
    66
    val _ = if AList.defined (op =) congs c
haftmann@21098
    67
      then warning ("Overwriting recdef congruence rule for " ^ quote c)
haftmann@21098
    68
      else ();
haftmann@21098
    69
  in AList.update (op =) (c, thm) congs end;
wenzelm@9859
    70
wenzelm@9859
    71
fun del_cong raw_thm congs =
wenzelm@9859
    72
  let
wenzelm@9859
    73
    val (c, thm) = prep_cong raw_thm;
haftmann@21098
    74
    val _ = if AList.defined (op =) congs c
haftmann@21098
    75
      then ()
haftmann@21098
    76
      else warning ("No recdef congruence rule for " ^ quote c);
haftmann@21098
    77
  in AList.delete (op =) c congs end;
wenzelm@9859
    78
wenzelm@9859
    79
end;
wenzelm@9859
    80
wenzelm@9859
    81
wenzelm@9859
    82
wenzelm@9859
    83
(** global and local recdef data **)
wenzelm@9859
    84
wenzelm@17920
    85
(* theory data *)
wenzelm@6439
    86
bulwahn@35756
    87
type recdef_info = {lhs: term, simps: thm list, rules: thm list list, induct: thm, tcs: term list};
wenzelm@6439
    88
wenzelm@33522
    89
structure GlobalRecdefData = Theory_Data
wenzelm@22846
    90
(
wenzelm@9859
    91
  type T = recdef_info Symtab.table * hints;
wenzelm@9879
    92
  val empty = (Symtab.empty, mk_hints ([], [], [])): T;
wenzelm@16458
    93
  val extend = I;
wenzelm@33522
    94
  fun merge
wenzelm@9859
    95
   ((tab1, {simps = simps1, congs = congs1, wfs = wfs1}),
wenzelm@16458
    96
    (tab2, {simps = simps2, congs = congs2, wfs = wfs2})) : T =
wenzelm@9859
    97
      (Symtab.merge (K true) (tab1, tab2),
wenzelm@24039
    98
        mk_hints (Thm.merge_thms (simps1, simps2),
wenzelm@33699
    99
          AList.merge (op =) (K true) (congs1, congs2),
wenzelm@24039
   100
          Thm.merge_thms (wfs1, wfs2)));
wenzelm@22846
   101
);
wenzelm@6439
   102
wenzelm@17412
   103
val get_recdef = Symtab.lookup o #1 o GlobalRecdefData.get;
wenzelm@6439
   104
wenzelm@6439
   105
fun put_recdef name info thy =
wenzelm@6429
   106
  let
wenzelm@9859
   107
    val (tab, hints) = GlobalRecdefData.get thy;
wenzelm@17412
   108
    val tab' = Symtab.update_new (name, info) tab
wenzelm@6439
   109
      handle Symtab.DUP _ => error ("Duplicate recursive function definition " ^ quote name);
wenzelm@9859
   110
  in GlobalRecdefData.put (tab', hints) thy end;
wenzelm@9859
   111
wenzelm@9859
   112
val get_global_hints = #2 o GlobalRecdefData.get;
wenzelm@9859
   113
wenzelm@9859
   114
wenzelm@17920
   115
(* proof data *)
wenzelm@9859
   116
wenzelm@33519
   117
structure LocalRecdefData = Proof_Data
wenzelm@22846
   118
(
wenzelm@9859
   119
  type T = hints;
wenzelm@9859
   120
  val init = get_global_hints;
wenzelm@22846
   121
);
wenzelm@9859
   122
wenzelm@21505
   123
val get_hints = LocalRecdefData.get;
wenzelm@21505
   124
fun map_hints f = Context.mapping (GlobalRecdefData.map (apsnd f)) (LocalRecdefData.map f);
wenzelm@9859
   125
wenzelm@20291
   126
wenzelm@20291
   127
(* attributes *)
wenzelm@20291
   128
wenzelm@18728
   129
fun attrib f = Thm.declaration_attribute (map_hints o f);
wenzelm@9859
   130
wenzelm@24039
   131
val simp_add = attrib (map_simps o Thm.add_thm);
wenzelm@24039
   132
val simp_del = attrib (map_simps o Thm.del_thm);
wenzelm@18688
   133
val cong_add = attrib (map_congs o add_cong);
wenzelm@18688
   134
val cong_del = attrib (map_congs o del_cong);
wenzelm@24039
   135
val wf_add = attrib (map_wfs o Thm.add_thm);
wenzelm@24039
   136
val wf_del = attrib (map_wfs o Thm.del_thm);
wenzelm@9859
   137
wenzelm@9859
   138
wenzelm@9949
   139
(* modifiers *)
wenzelm@9859
   140
wenzelm@9949
   141
val recdef_simpN = "recdef_simp";
wenzelm@9949
   142
val recdef_congN = "recdef_cong";
wenzelm@9949
   143
val recdef_wfN = "recdef_wf";
wenzelm@9859
   144
wenzelm@9859
   145
val recdef_modifiers =
wenzelm@18728
   146
 [Args.$$$ recdef_simpN -- Args.colon >> K ((I, simp_add): Method.modifier),
wenzelm@18728
   147
  Args.$$$ recdef_simpN -- Args.add -- Args.colon >> K (I, simp_add),
wenzelm@18728
   148
  Args.$$$ recdef_simpN -- Args.del -- Args.colon >> K (I, simp_del),
wenzelm@18728
   149
  Args.$$$ recdef_congN -- Args.colon >> K (I, cong_add),
wenzelm@18728
   150
  Args.$$$ recdef_congN -- Args.add -- Args.colon >> K (I, cong_add),
wenzelm@18728
   151
  Args.$$$ recdef_congN -- Args.del -- Args.colon >> K (I, cong_del),
wenzelm@18728
   152
  Args.$$$ recdef_wfN -- Args.colon >> K (I, wf_add),
wenzelm@18728
   153
  Args.$$$ recdef_wfN -- Args.add -- Args.colon >> K (I, wf_add),
wenzelm@18728
   154
  Args.$$$ recdef_wfN -- Args.del -- Args.colon >> K (I, wf_del)] @
wenzelm@9949
   155
  Clasimp.clasimp_modifiers;
wenzelm@9859
   156
wenzelm@9949
   157
wenzelm@9859
   158
wenzelm@9949
   159
(** prepare_hints(_i) **)
wenzelm@9859
   160
wenzelm@9859
   161
fun prepare_hints thy opt_src =
wenzelm@9859
   162
  let
wenzelm@42361
   163
    val ctxt0 = Proof_Context.init_global thy;
wenzelm@9859
   164
    val ctxt =
wenzelm@9859
   165
      (case opt_src of
skalberg@15531
   166
        NONE => ctxt0
wenzelm@31243
   167
      | SOME src => #2 (Method.syntax (Method.sections recdef_modifiers) src ctxt0));
wenzelm@21505
   168
    val {simps, congs, wfs} = get_hints ctxt;
wenzelm@42775
   169
    val ctxt' = ctxt
wenzelm@46185
   170
      |> Simplifier.map_simpset (fn ss => ss addsimps simps |> Simplifier.del_cong @{thm imp_cong});
wenzelm@42775
   171
  in (ctxt', rev (map snd congs), wfs) end;
wenzelm@9859
   172
wenzelm@9859
   173
fun prepare_hints_i thy () =
wenzelm@15032
   174
  let
wenzelm@42775
   175
    val ctxt = Proof_Context.init_global thy;
wenzelm@15032
   176
    val {simps, congs, wfs} = get_global_hints thy;
wenzelm@42775
   177
    val ctxt' = ctxt
wenzelm@46185
   178
      |> Simplifier.map_simpset (fn ss => ss addsimps simps |> Simplifier.del_cong @{thm imp_cong});
wenzelm@42775
   179
  in (ctxt', rev (map snd congs), wfs) end;
wenzelm@9859
   180
wenzelm@6439
   181
wenzelm@6439
   182
wenzelm@6439
   183
(** add_recdef(_i) **)
wenzelm@6439
   184
krauss@44013
   185
fun requires_recdef thy = Theory.requires thy "Old_Recdef" "recursive functions";
wenzelm@6557
   186
wenzelm@17920
   187
fun gen_add_recdef tfl_fn prep_att prep_hints not_permissive raw_name R eq_srcs hints thy =
wenzelm@6439
   188
  let
wenzelm@36865
   189
    val _ = legacy_feature "Old 'recdef' command -- use 'fun' or 'function' instead";
wenzelm@9859
   190
    val _ = requires_recdef thy;
wenzelm@9859
   191
wenzelm@16458
   192
    val name = Sign.intern_const thy raw_name;
wenzelm@30364
   193
    val bname = Long_Name.base_name name;
wenzelm@26478
   194
    val _ = writeln ("Defining recursive function " ^ quote name ^ " ...");
wenzelm@6429
   195
wenzelm@8657
   196
    val ((eq_names, eqs), raw_eq_atts) = apfst split_list (split_list eq_srcs);
wenzelm@8657
   197
    val eq_atts = map (map (prep_att thy)) raw_eq_atts;
wenzelm@8657
   198
wenzelm@42775
   199
    val (ctxt, congs, wfs) = prep_hints thy hints;
paulson@14241
   200
    (*We must remove imp_cong to prevent looping when the induction rule
paulson@14241
   201
      is simplified. Many induction rules have nested implications that would
paulson@14241
   202
      give rise to looping conditional rewriting.*)
wenzelm@42775
   203
    val ({lhs, rules = rules_idx, induct, tcs}, thy) =
wenzelm@42775
   204
      tfl_fn not_permissive ctxt congs wfs name R eqs thy;
haftmann@21098
   205
    val rules = (map o map) fst (partition_eq (eq_snd (op = : int * int -> bool)) rules_idx);
wenzelm@33552
   206
    val simp_att =
wenzelm@33552
   207
      if null tcs then [Simplifier.simp_add, Nitpick_Simps.add, Code.add_default_eqn_attribute]
wenzelm@33552
   208
      else [];
haftmann@18377
   209
    val ((simps' :: rules', [induct']), thy) =
wenzelm@7798
   210
      thy
wenzelm@24712
   211
      |> Sign.add_path bname
wenzelm@39557
   212
      |> Global_Theory.add_thmss
wenzelm@32952
   213
        (((Binding.name "simps", flat rules), simp_att) :: ((eq_names ~~ rules) ~~ eq_atts))
wenzelm@39557
   214
      ||>> Global_Theory.add_thms [((Binding.name "induct", induct), [])]
bulwahn@35756
   215
      ||> Spec_Rules.add_global Spec_Rules.Equational ([lhs], flat rules);
bulwahn@35756
   216
    val result = {lhs = lhs, simps = simps', rules = rules', induct = induct', tcs = tcs};
wenzelm@7798
   217
    val thy =
wenzelm@7798
   218
      thy
wenzelm@6439
   219
      |> put_recdef name result
wenzelm@24712
   220
      |> Sign.parent_path;
wenzelm@7798
   221
  in (thy, result) end;
wenzelm@6429
   222
wenzelm@18728
   223
val add_recdef = gen_add_recdef Tfl.define Attrib.attribute prepare_hints;
wenzelm@11629
   224
fun add_recdef_i x y z w = gen_add_recdef Tfl.define_i (K I) prepare_hints_i x y z w ();
wenzelm@9859
   225
wenzelm@9859
   226
wenzelm@6557
   227
wenzelm@6557
   228
(** defer_recdef(_i) **)
wenzelm@6557
   229
wenzelm@27727
   230
fun gen_defer_recdef tfl_fn eval_thms raw_name eqs raw_congs thy =
wenzelm@6557
   231
  let
wenzelm@16458
   232
    val name = Sign.intern_const thy raw_name;
wenzelm@30364
   233
    val bname = Long_Name.base_name name;
wenzelm@6557
   234
wenzelm@6557
   235
    val _ = requires_recdef thy;
wenzelm@26478
   236
    val _ = writeln ("Deferred recursive function " ^ quote name ^ " ...");
wenzelm@6557
   237
wenzelm@42361
   238
    val congs = eval_thms (Proof_Context.init_global thy) raw_congs;
wenzelm@42775
   239
    val (induct_rules, thy2) = tfl_fn congs name eqs thy;
haftmann@18377
   240
    val ([induct_rules'], thy3) =
wenzelm@6557
   241
      thy2
wenzelm@24712
   242
      |> Sign.add_path bname
wenzelm@39557
   243
      |> Global_Theory.add_thms [((Binding.name "induct_rules", induct_rules), [])]
wenzelm@24712
   244
      ||> Sign.parent_path;
wenzelm@8430
   245
  in (thy3, {induct_rules = induct_rules'}) end;
wenzelm@6557
   246
wenzelm@27727
   247
val defer_recdef = gen_defer_recdef Tfl.defer Attrib.eval_thms;
wenzelm@27727
   248
val defer_recdef_i = gen_defer_recdef Tfl.defer_i (K I);
wenzelm@6557
   249
wenzelm@6557
   250
wenzelm@6557
   251
wenzelm@10775
   252
(** recdef_tc(_i) **)
wenzelm@10775
   253
berghofe@24457
   254
fun gen_recdef_tc prep_att prep_name (bname, raw_atts) raw_name opt_i int lthy =
wenzelm@10775
   255
  let
wenzelm@42361
   256
    val thy = Proof_Context.theory_of lthy;
wenzelm@16458
   257
    val name = prep_name thy raw_name;
wenzelm@10775
   258
    val atts = map (prep_att thy) raw_atts;
wenzelm@10775
   259
    val tcs =
wenzelm@10775
   260
      (case get_recdef thy name of
skalberg@15531
   261
        NONE => error ("No recdef definition of constant: " ^ quote name)
skalberg@15531
   262
      | SOME {tcs, ...} => tcs);
wenzelm@21351
   263
    val i = the_default 1 opt_i;
wenzelm@43278
   264
    val tc = nth tcs (i - 1) handle General.Subscript =>
wenzelm@10775
   265
      error ("No termination condition #" ^ string_of_int i ^
wenzelm@10775
   266
        " in recdef definition of " ^ quote name);
wenzelm@21351
   267
  in
wenzelm@33643
   268
    Specification.theorem "" NONE (K I)
wenzelm@47067
   269
      (Binding.conceal (Binding.name bname), atts) [] []
wenzelm@33278
   270
      (Element.Shows [(Attrib.empty_binding, [(HOLogic.mk_Trueprop tc, [])])]) int lthy
wenzelm@21351
   271
  end;
wenzelm@10775
   272
wenzelm@21351
   273
val recdef_tc = gen_recdef_tc Attrib.intern_src Sign.intern_const;
wenzelm@10775
   274
val recdef_tc_i = gen_recdef_tc (K I) (K I);
wenzelm@10775
   275
wenzelm@10775
   276
wenzelm@10775
   277
wenzelm@6439
   278
(** package setup **)
wenzelm@6439
   279
wenzelm@6439
   280
(* setup theory *)
wenzelm@6439
   281
wenzelm@9859
   282
val setup =
wenzelm@30528
   283
  Attrib.setup @{binding recdef_simp} (Attrib.add_del simp_add simp_del)
wenzelm@30528
   284
    "declaration of recdef simp rule" #>
wenzelm@30528
   285
  Attrib.setup @{binding recdef_cong} (Attrib.add_del cong_add cong_del)
wenzelm@30528
   286
    "declaration of recdef cong rule" #>
wenzelm@30528
   287
  Attrib.setup @{binding recdef_wf} (Attrib.add_del wf_add wf_del)
wenzelm@30528
   288
    "declaration of recdef wf rule";
wenzelm@6439
   289
wenzelm@6439
   290
wenzelm@6429
   291
(* outer syntax *)
wenzelm@6429
   292
wenzelm@9859
   293
val hints =
wenzelm@46949
   294
  @{keyword "("} |--
wenzelm@46949
   295
    Parse.!!! (Parse.position (@{keyword "hints"} -- Args.parse) --| @{keyword ")"}) >> Args.src;
wenzelm@9859
   296
wenzelm@6429
   297
val recdef_decl =
wenzelm@36960
   298
  Scan.optional
wenzelm@46949
   299
    (@{keyword "("} -- Parse.!!! (@{keyword "permissive"} -- @{keyword ")"}) >> K false) true --
wenzelm@36960
   300
  Parse.name -- Parse.term -- Scan.repeat1 (Parse_Spec.opt_thm_name ":" -- Parse.prop)
wenzelm@28083
   301
    -- Scan.option hints
wenzelm@36960
   302
  >> (fn ((((p, f), R), eqs), src) => #1 o add_recdef p f R (map Parse.triple_swap eqs) src);
wenzelm@6429
   303
wenzelm@24867
   304
val _ =
wenzelm@46961
   305
  Outer_Syntax.command @{command_spec "recdef"} "define general recursive functions (TFL)"
wenzelm@6429
   306
    (recdef_decl >> Toplevel.theory);
wenzelm@6429
   307
wenzelm@6557
   308
wenzelm@6557
   309
val defer_recdef_decl =
wenzelm@36960
   310
  Parse.name -- Scan.repeat1 Parse.prop --
wenzelm@36960
   311
  Scan.optional
wenzelm@46949
   312
    (@{keyword "("} |-- @{keyword "congs"} |-- Parse.!!! (Parse_Spec.xthms1 --| @{keyword ")"})) []
wenzelm@6557
   313
  >> (fn ((f, eqs), congs) => #1 o defer_recdef f eqs congs);
wenzelm@6557
   314
wenzelm@24867
   315
val _ =
wenzelm@46961
   316
  Outer_Syntax.command @{command_spec "defer_recdef"}
wenzelm@46961
   317
    "defer general recursive functions (TFL)"
wenzelm@6557
   318
    (defer_recdef_decl >> Toplevel.theory);
wenzelm@6557
   319
wenzelm@24867
   320
val _ =
wenzelm@46961
   321
  Outer_Syntax.local_theory_to_proof' @{command_spec "recdef_tc"}
wenzelm@46961
   322
    "recommence proof of termination condition (TFL)"
wenzelm@36960
   323
    ((Parse_Spec.opt_thm_name ":" >> apfst Binding.name_of) -- Parse.xname --
wenzelm@46949
   324
        Scan.option (@{keyword "("} |-- Parse.nat --| @{keyword ")"})
wenzelm@26988
   325
      >> (fn ((thm_name, name), i) => recdef_tc thm_name name i));
wenzelm@10775
   326
wenzelm@6429
   327
end;