src/HOL/Tools/recdef_package.ML
author wenzelm
Thu Jan 19 21:22:08 2006 +0100 (2006-01-19)
changeset 18708 4b3dadb4fe33
parent 18688 abf0f018b5ec
child 18728 6790126ab5f6
permissions -rw-r--r--
setup: theory -> theory;
wenzelm@6429
     1
(*  Title:      HOL/Tools/recdef_package.ML
wenzelm@6429
     2
    ID:         $Id$
wenzelm@6429
     3
    Author:     Markus Wenzel, TU Muenchen
wenzelm@6429
     4
wenzelm@6429
     5
Wrapper module for Konrad Slind's TFL package.
wenzelm@6429
     6
*)
wenzelm@6429
     7
wenzelm@6429
     8
signature RECDEF_PACKAGE =
wenzelm@6429
     9
sig
wenzelm@6429
    10
  val quiet_mode: bool ref
wenzelm@6439
    11
  val print_recdefs: theory -> unit
wenzelm@8657
    12
  val get_recdef: theory -> string
wenzelm@8657
    13
    -> {simps: thm list, rules: thm list list, induct: thm, tcs: term list} option
wenzelm@18688
    14
  val simp_add: Context.generic attribute
wenzelm@18688
    15
  val simp_del: Context.generic attribute
wenzelm@18688
    16
  val cong_add: Context.generic attribute
wenzelm@18688
    17
  val cong_del: Context.generic attribute
wenzelm@18688
    18
  val wf_add: Context.generic attribute
wenzelm@18688
    19
  val wf_del: Context.generic attribute
wenzelm@15703
    20
  val add_recdef: bool -> xstring -> string -> ((bstring * string) * Attrib.src list) list ->
wenzelm@15703
    21
    Attrib.src option -> theory -> theory
wenzelm@9859
    22
      * {simps: thm list, rules: thm list list, induct: thm, tcs: term list}
wenzelm@11629
    23
  val add_recdef_i: bool -> xstring -> term -> ((bstring * term) * theory attribute list) list ->
wenzelm@9859
    24
    theory -> theory * {simps: thm list, rules: thm list list, induct: thm, tcs: term list}
wenzelm@15703
    25
  val defer_recdef: xstring -> string list -> (thmref * Attrib.src list) list
wenzelm@6557
    26
    -> theory -> theory * {induct_rules: thm}
wenzelm@12708
    27
  val defer_recdef_i: xstring -> term list -> (thm list * theory attribute list) list
wenzelm@6557
    28
    -> theory -> theory * {induct_rules: thm}
wenzelm@17336
    29
  val recdef_tc: bstring * Attrib.src list -> xstring -> int option -> theory -> Proof.state
wenzelm@10775
    30
  val recdef_tc_i: bstring * theory attribute list -> string -> int option
wenzelm@17336
    31
    -> theory -> Proof.state
wenzelm@18708
    32
  val setup: theory -> theory
wenzelm@6429
    33
end;
wenzelm@6429
    34
wenzelm@6429
    35
structure RecdefPackage: RECDEF_PACKAGE =
wenzelm@6429
    36
struct
wenzelm@6429
    37
wenzelm@6429
    38
val quiet_mode = Tfl.quiet_mode;
wenzelm@6429
    39
val message = Tfl.message;
wenzelm@6429
    40
wenzelm@6429
    41
wenzelm@9859
    42
(** recdef hints **)
wenzelm@6439
    43
wenzelm@9859
    44
(* type hints *)
wenzelm@9859
    45
wenzelm@9859
    46
type hints = {simps: thm list, congs: (string * thm) list, wfs: thm list};
wenzelm@9859
    47
wenzelm@9859
    48
fun mk_hints (simps, congs, wfs) = {simps = simps, congs = congs, wfs = wfs}: hints;
wenzelm@9859
    49
fun map_hints f ({simps, congs, wfs}: hints) = mk_hints (f (simps, congs, wfs));
wenzelm@9859
    50
wenzelm@9859
    51
fun map_simps f = map_hints (fn (simps, congs, wfs) => (f simps, congs, wfs));
wenzelm@9859
    52
fun map_congs f = map_hints (fn (simps, congs, wfs) => (simps, f congs, wfs));
wenzelm@9859
    53
fun map_wfs f = map_hints (fn (simps, congs, wfs) => (simps, congs, f wfs));
wenzelm@9859
    54
wenzelm@9859
    55
fun pretty_hints ({simps, congs, wfs}: hints) =
wenzelm@9859
    56
 [Pretty.big_list "recdef simp hints:" (map Display.pretty_thm simps),
wenzelm@9859
    57
  Pretty.big_list "recdef cong hints:" (map Display.pretty_thm (map #2 congs)),
wenzelm@9859
    58
  Pretty.big_list "recdef wf hints:" (map Display.pretty_thm wfs)];
wenzelm@9859
    59
wenzelm@9859
    60
wenzelm@9859
    61
(* congruence rules *)
wenzelm@9859
    62
wenzelm@9859
    63
local
wenzelm@9859
    64
wenzelm@9859
    65
val cong_head =
wenzelm@9859
    66
  fst o Term.dest_Const o Term.head_of o fst o Logic.dest_equals o Thm.concl_of;
wenzelm@6439
    67
wenzelm@9859
    68
fun prep_cong raw_thm =
wenzelm@9859
    69
  let val thm = safe_mk_meta_eq raw_thm in (cong_head thm, thm) end;
wenzelm@9859
    70
wenzelm@9859
    71
in
wenzelm@9859
    72
wenzelm@9859
    73
fun add_cong raw_thm congs =
wenzelm@9859
    74
  let val (c, thm) = prep_cong raw_thm
haftmann@17593
    75
  in overwrite_warn (congs, (c, thm)) ("Overwriting recdef congruence rule for " ^ quote c) end;
wenzelm@9859
    76
wenzelm@9859
    77
fun del_cong raw_thm congs =
wenzelm@9859
    78
  let
wenzelm@9859
    79
    val (c, thm) = prep_cong raw_thm;
wenzelm@9859
    80
    val (del, rest) = Library.partition (Library.equal c o fst) congs;
wenzelm@9859
    81
  in if null del then (warning ("No recdef congruence rule for " ^ quote c); congs) else rest end;
wenzelm@9859
    82
skalberg@15574
    83
val add_congs = foldr (uncurry add_cong);
wenzelm@9859
    84
wenzelm@9859
    85
end;
wenzelm@9859
    86
wenzelm@9859
    87
wenzelm@9859
    88
wenzelm@9859
    89
(** global and local recdef data **)
wenzelm@9859
    90
wenzelm@17920
    91
(* theory data *)
wenzelm@6439
    92
wenzelm@8657
    93
type recdef_info = {simps: thm list, rules: thm list list, induct: thm, tcs: term list};
wenzelm@6439
    94
wenzelm@16458
    95
structure GlobalRecdefData = TheoryDataFun
wenzelm@16458
    96
(struct
wenzelm@6439
    97
  val name = "HOL/recdef";
wenzelm@9859
    98
  type T = recdef_info Symtab.table * hints;
wenzelm@6439
    99
wenzelm@9879
   100
  val empty = (Symtab.empty, mk_hints ([], [], [])): T;
wenzelm@6557
   101
  val copy = I;
wenzelm@16458
   102
  val extend = I;
wenzelm@16458
   103
  fun merge _
wenzelm@9859
   104
   ((tab1, {simps = simps1, congs = congs1, wfs = wfs1}),
wenzelm@16458
   105
    (tab2, {simps = simps2, congs = congs2, wfs = wfs2})) : T =
wenzelm@9859
   106
      (Symtab.merge (K true) (tab1, tab2),
wenzelm@9859
   107
        mk_hints (Drule.merge_rules (simps1, simps2),
wenzelm@9859
   108
          Library.merge_alists congs1 congs2,
wenzelm@9859
   109
          Drule.merge_rules (wfs1, wfs2)));
wenzelm@6439
   110
wenzelm@16458
   111
  fun print thy (tab, hints) =
wenzelm@16458
   112
    (Pretty.strs ("recdefs:" :: map #1 (NameSpace.extern_table (Sign.const_space thy, tab))) ::
wenzelm@16364
   113
      pretty_hints hints) |> Pretty.chunks |> Pretty.writeln;
wenzelm@16458
   114
end);
wenzelm@6439
   115
wenzelm@9859
   116
val print_recdefs = GlobalRecdefData.print;
wenzelm@6429
   117
wenzelm@6439
   118
wenzelm@17412
   119
val get_recdef = Symtab.lookup o #1 o GlobalRecdefData.get;
wenzelm@6439
   120
wenzelm@6439
   121
fun put_recdef name info thy =
wenzelm@6429
   122
  let
wenzelm@9859
   123
    val (tab, hints) = GlobalRecdefData.get thy;
wenzelm@17412
   124
    val tab' = Symtab.update_new (name, info) tab
wenzelm@6439
   125
      handle Symtab.DUP _ => error ("Duplicate recursive function definition " ^ quote name);
wenzelm@9859
   126
  in GlobalRecdefData.put (tab', hints) thy end;
wenzelm@9859
   127
wenzelm@9859
   128
val get_global_hints = #2 o GlobalRecdefData.get;
wenzelm@9859
   129
val map_global_hints = GlobalRecdefData.map o apsnd;
wenzelm@9859
   130
wenzelm@9859
   131
wenzelm@17920
   132
(* proof data *)
wenzelm@9859
   133
wenzelm@16458
   134
structure LocalRecdefData = ProofDataFun
wenzelm@16458
   135
(struct
wenzelm@9859
   136
  val name = "HOL/recdef";
wenzelm@9859
   137
  type T = hints;
wenzelm@9859
   138
  val init = get_global_hints;
wenzelm@9859
   139
  fun print _ hints = pretty_hints hints |> Pretty.chunks |> Pretty.writeln;
wenzelm@16458
   140
end);
wenzelm@9859
   141
wenzelm@9859
   142
val get_local_hints = LocalRecdefData.get;
wenzelm@9859
   143
val map_local_hints = LocalRecdefData.map;
wenzelm@9859
   144
wenzelm@9859
   145
wenzelm@9859
   146
(* attributes *)
wenzelm@9859
   147
wenzelm@18688
   148
fun map_hints f (Context.Theory thy) = Context.Theory (map_global_hints f thy)
wenzelm@18688
   149
  | map_hints f (Context.Proof ctxt) = Context.Proof (map_local_hints f ctxt);
wenzelm@9859
   150
wenzelm@18688
   151
fun attrib f = Attrib.declaration (map_hints o f);
wenzelm@9859
   152
wenzelm@18688
   153
val simp_add = attrib (map_simps o Drule.add_rule);
wenzelm@18688
   154
val simp_del = attrib (map_simps o Drule.del_rule);
wenzelm@18688
   155
val cong_add = attrib (map_congs o add_cong);
wenzelm@18688
   156
val cong_del = attrib (map_congs o del_cong);
wenzelm@18688
   157
val wf_add = attrib (map_wfs o Drule.add_rule);
wenzelm@18688
   158
val wf_del = attrib (map_wfs o Drule.del_rule);
wenzelm@9859
   159
wenzelm@9859
   160
wenzelm@9949
   161
(* modifiers *)
wenzelm@9859
   162
wenzelm@9949
   163
val recdef_simpN = "recdef_simp";
wenzelm@9949
   164
val recdef_congN = "recdef_cong";
wenzelm@9949
   165
val recdef_wfN = "recdef_wf";
wenzelm@9859
   166
wenzelm@9859
   167
val recdef_modifiers =
wenzelm@18688
   168
 [Args.$$$ recdef_simpN -- Args.colon >> K ((I, Attrib.context simp_add): Method.modifier),
wenzelm@18688
   169
  Args.$$$ recdef_simpN -- Args.add -- Args.colon >> K (I, Attrib.context simp_add),
wenzelm@18688
   170
  Args.$$$ recdef_simpN -- Args.del -- Args.colon >> K (I, Attrib.context simp_del),
wenzelm@18688
   171
  Args.$$$ recdef_congN -- Args.colon >> K (I, Attrib.context cong_add),
wenzelm@18688
   172
  Args.$$$ recdef_congN -- Args.add -- Args.colon >> K (I, Attrib.context cong_add),
wenzelm@18688
   173
  Args.$$$ recdef_congN -- Args.del -- Args.colon >> K (I, Attrib.context cong_del),
wenzelm@18688
   174
  Args.$$$ recdef_wfN -- Args.colon >> K (I, Attrib.context wf_add),
wenzelm@18688
   175
  Args.$$$ recdef_wfN -- Args.add -- Args.colon >> K (I, Attrib.context wf_add),
wenzelm@18688
   176
  Args.$$$ recdef_wfN -- Args.del -- Args.colon >> K (I, Attrib.context wf_del)] @
wenzelm@9949
   177
  Clasimp.clasimp_modifiers;
wenzelm@9859
   178
wenzelm@9949
   179
wenzelm@9859
   180
wenzelm@9949
   181
(** prepare_hints(_i) **)
wenzelm@9859
   182
wenzelm@9859
   183
fun prepare_hints thy opt_src =
wenzelm@9859
   184
  let
wenzelm@9859
   185
    val ctxt0 = ProofContext.init thy;
wenzelm@9859
   186
    val ctxt =
wenzelm@9859
   187
      (case opt_src of
skalberg@15531
   188
        NONE => ctxt0
skalberg@15531
   189
      | SOME src => Method.only_sectioned_args recdef_modifiers I src ctxt0);
wenzelm@9859
   190
    val {simps, congs, wfs} = get_local_hints ctxt;
wenzelm@15032
   191
    val cs = local_claset_of ctxt;
wenzelm@15032
   192
    val ss = local_simpset_of ctxt addsimps simps;
wenzelm@9859
   193
  in (cs, ss, map #2 congs, wfs) end;
wenzelm@9859
   194
wenzelm@9859
   195
fun prepare_hints_i thy () =
wenzelm@15032
   196
  let
wenzelm@15032
   197
    val ctxt0 = ProofContext.init thy;
wenzelm@15032
   198
    val {simps, congs, wfs} = get_global_hints thy;
wenzelm@15032
   199
  in (local_claset_of ctxt0, local_simpset_of ctxt0 addsimps simps, map #2 congs, wfs) end;
wenzelm@9859
   200
wenzelm@6439
   201
wenzelm@6439
   202
wenzelm@6439
   203
(** add_recdef(_i) **)
wenzelm@6439
   204
wenzelm@6557
   205
fun requires_recdef thy = Theory.requires thy "Recdef" "recursive functions";
wenzelm@6557
   206
wenzelm@17920
   207
fun gen_add_recdef tfl_fn prep_att prep_hints not_permissive raw_name R eq_srcs hints thy =
wenzelm@6439
   208
  let
wenzelm@9859
   209
    val _ = requires_recdef thy;
wenzelm@9859
   210
wenzelm@16458
   211
    val name = Sign.intern_const thy raw_name;
wenzelm@6439
   212
    val bname = Sign.base_name name;
wenzelm@6429
   213
    val _ = message ("Defining recursive function " ^ quote name ^ " ...");
wenzelm@6429
   214
wenzelm@8657
   215
    val ((eq_names, eqs), raw_eq_atts) = apfst split_list (split_list eq_srcs);
wenzelm@8657
   216
    val eq_atts = map (map (prep_att thy)) raw_eq_atts;
wenzelm@8657
   217
wenzelm@9859
   218
    val (cs, ss, congs, wfs) = prep_hints thy hints;
paulson@14241
   219
    (*We must remove imp_cong to prevent looping when the induction rule
paulson@14241
   220
      is simplified. Many induction rules have nested implications that would
paulson@14241
   221
      give rise to looping conditional rewriting.*)
paulson@14241
   222
    val (thy, {rules = rules_idx, induct, tcs}) =
wenzelm@17920
   223
        tfl_fn not_permissive thy cs (ss delcongs [imp_cong])
paulson@14241
   224
               congs wfs name R eqs;
haftmann@17496
   225
    val rules = map (map #1) (Library.partition_eq (Library.eq_snd (op =)) rules_idx);
berghofe@12448
   226
    val simp_att = if null tcs then
wenzelm@18688
   227
      [Attrib.theory Simplifier.simp_add, RecfunCodegen.add NONE] else [];
wenzelm@8657
   228
haftmann@18377
   229
    val ((simps' :: rules', [induct']), thy) =
wenzelm@7798
   230
      thy
wenzelm@6439
   231
      |> Theory.add_path bname
wenzelm@18688
   232
      |> PureThy.add_thmss
wenzelm@18688
   233
        ((("simps", List.concat rules), simp_att) :: ((eq_names ~~ rules) ~~ eq_atts))
haftmann@18377
   234
      ||>> PureThy.add_thms [(("induct", induct), [])];
wenzelm@8657
   235
    val result = {simps = simps', rules = rules', induct = induct', tcs = tcs};
wenzelm@7798
   236
    val thy =
wenzelm@7798
   237
      thy
wenzelm@6439
   238
      |> put_recdef name result
wenzelm@6429
   239
      |> Theory.parent_path;
wenzelm@7798
   240
  in (thy, result) end;
wenzelm@6429
   241
wenzelm@9859
   242
val add_recdef = gen_add_recdef Tfl.define Attrib.global_attribute prepare_hints;
wenzelm@11629
   243
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
   244
wenzelm@9859
   245
wenzelm@6557
   246
wenzelm@6557
   247
(** defer_recdef(_i) **)
wenzelm@6557
   248
wenzelm@6557
   249
fun gen_defer_recdef tfl_fn app_thms raw_name eqs raw_congs thy =
wenzelm@6557
   250
  let
wenzelm@16458
   251
    val name = Sign.intern_const thy raw_name;
wenzelm@6557
   252
    val bname = Sign.base_name name;
wenzelm@6557
   253
wenzelm@6557
   254
    val _ = requires_recdef thy;
wenzelm@6557
   255
    val _ = message ("Deferred recursive function " ^ quote name ^ " ...");
wenzelm@6557
   256
haftmann@18418
   257
    val (congs, thy1) = thy |> app_thms raw_congs;
wenzelm@9859
   258
    val (thy2, induct_rules) = tfl_fn thy1 congs name eqs;
haftmann@18377
   259
    val ([induct_rules'], thy3) =
wenzelm@6557
   260
      thy2
wenzelm@6557
   261
      |> Theory.add_path bname
wenzelm@6557
   262
      |> PureThy.add_thms [(("induct_rules", induct_rules), [])]
haftmann@18377
   263
      ||> Theory.parent_path;
wenzelm@8430
   264
  in (thy3, {induct_rules = induct_rules'}) end;
wenzelm@6557
   265
wenzelm@6557
   266
val defer_recdef = gen_defer_recdef Tfl.defer IsarThy.apply_theorems;
wenzelm@6557
   267
val defer_recdef_i = gen_defer_recdef Tfl.defer_i IsarThy.apply_theorems_i;
wenzelm@6557
   268
wenzelm@6557
   269
wenzelm@6557
   270
wenzelm@10775
   271
(** recdef_tc(_i) **)
wenzelm@10775
   272
wenzelm@17336
   273
fun gen_recdef_tc prep_att prep_name (bname, raw_atts) raw_name opt_i thy =
wenzelm@10775
   274
  let
wenzelm@16458
   275
    val name = prep_name thy raw_name;
wenzelm@10775
   276
    val atts = map (prep_att thy) raw_atts;
wenzelm@10775
   277
    val tcs =
wenzelm@10775
   278
      (case get_recdef thy name of
skalberg@15531
   279
        NONE => error ("No recdef definition of constant: " ^ quote name)
skalberg@15531
   280
      | SOME {tcs, ...} => tcs);
skalberg@15570
   281
    val i = getOpt (opt_i, 1);
skalberg@15570
   282
    val tc = List.nth (tcs, i - 1) handle Subscript =>
wenzelm@10775
   283
      error ("No termination condition #" ^ string_of_int i ^
wenzelm@10775
   284
        " in recdef definition of " ^ quote name);
wenzelm@17336
   285
  in IsarThy.theorem_i Drule.internalK (bname, atts) (HOLogic.mk_Trueprop tc, ([], [])) thy end;
wenzelm@10775
   286
wenzelm@10775
   287
val recdef_tc = gen_recdef_tc Attrib.global_attribute Sign.intern_const;
wenzelm@10775
   288
val recdef_tc_i = gen_recdef_tc (K I) (K I);
wenzelm@10775
   289
wenzelm@10775
   290
wenzelm@10775
   291
wenzelm@6439
   292
(** package setup **)
wenzelm@6439
   293
wenzelm@6439
   294
(* setup theory *)
wenzelm@6439
   295
wenzelm@9859
   296
val setup =
wenzelm@18708
   297
  GlobalRecdefData.init #>
wenzelm@18708
   298
  LocalRecdefData.init #>
wenzelm@9859
   299
  Attrib.add_attributes
wenzelm@18688
   300
   [(recdef_simpN, Attrib.common (Attrib.add_del_args simp_add simp_del),
wenzelm@18688
   301
      "declaration of recdef simp rule"),
wenzelm@18688
   302
    (recdef_congN, Attrib.common (Attrib.add_del_args cong_add cong_del),
wenzelm@18688
   303
      "declaration of recdef cong rule"),
wenzelm@18688
   304
    (recdef_wfN, Attrib.common (Attrib.add_del_args wf_add wf_del),
wenzelm@18708
   305
      "declaration of recdef wf rule")];
wenzelm@6439
   306
wenzelm@6439
   307
wenzelm@6429
   308
(* outer syntax *)
wenzelm@6429
   309
wenzelm@17057
   310
local structure P = OuterParse and K = OuterKeyword in
wenzelm@6429
   311
wenzelm@9859
   312
val hints =
wenzelm@9859
   313
  P.$$$ "(" |-- P.!!! (P.position (P.$$$ "hints" -- P.arguments) --| P.$$$ ")") >> Args.src;
wenzelm@9859
   314
wenzelm@6429
   315
val recdef_decl =
wenzelm@11629
   316
  Scan.optional (P.$$$ "(" -- P.!!! (P.$$$ "permissive" -- P.$$$ ")") >> K false) true --
wenzelm@12876
   317
  P.name -- P.term -- Scan.repeat1 (P.opt_thm_name ":" -- P.prop) -- Scan.option hints
wenzelm@11629
   318
  >> (fn ((((p, f), R), eqs), src) => #1 o add_recdef p f R (map P.triple_swap eqs) src);
wenzelm@6429
   319
wenzelm@6429
   320
val recdefP =
wenzelm@6723
   321
  OuterSyntax.command "recdef" "define general recursive functions (TFL)" K.thy_decl
wenzelm@6429
   322
    (recdef_decl >> Toplevel.theory);
wenzelm@6429
   323
wenzelm@6557
   324
wenzelm@6557
   325
val defer_recdef_decl =
wenzelm@8657
   326
  P.name -- Scan.repeat1 P.prop --
wenzelm@6723
   327
  Scan.optional (P.$$$ "(" |-- P.$$$ "congs" |-- P.!!! (P.xthms1 --| P.$$$ ")")) []
wenzelm@6557
   328
  >> (fn ((f, eqs), congs) => #1 o defer_recdef f eqs congs);
wenzelm@6557
   329
wenzelm@6557
   330
val defer_recdefP =
wenzelm@6723
   331
  OuterSyntax.command "defer_recdef" "defer general recursive functions (TFL)" K.thy_decl
wenzelm@6557
   332
    (defer_recdef_decl >> Toplevel.theory);
wenzelm@6557
   333
wenzelm@10775
   334
val recdef_tcP =
wenzelm@10775
   335
  OuterSyntax.command "recdef_tc" "recommence proof of termination condition (TFL)" K.thy_goal
wenzelm@17336
   336
    (P.opt_thm_name ":" -- P.xname -- Scan.option (P.$$$ "(" |-- P.nat --| P.$$$ ")")
wenzelm@17336
   337
      >> (fn ((thm_name, name), i) =>
wenzelm@17336
   338
        Toplevel.print o Toplevel.theory_to_proof (recdef_tc thm_name name i)));
wenzelm@10775
   339
wenzelm@10775
   340
wenzelm@11629
   341
val _ = OuterSyntax.add_keywords ["permissive", "congs", "hints"];
wenzelm@10775
   342
val _ = OuterSyntax.add_parsers [recdefP, defer_recdefP, recdef_tcP];
wenzelm@6429
   343
wenzelm@6429
   344
end;
wenzelm@6429
   345
wenzelm@6429
   346
end;