src/HOL/Tools/recdef_package.ML
author wenzelm
Wed Jun 25 17:38:32 2008 +0200 (2008-06-25)
changeset 27353 71c4dd53d4cb
parent 26988 742e26213212
child 27727 2397e310b2cc
permissions -rw-r--r--
moved global keywords from OuterSyntax to OuterKeyword, tuned interfaces;
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@8657
    10
  val get_recdef: theory -> string
wenzelm@8657
    11
    -> {simps: thm list, rules: thm list list, induct: thm, tcs: term list} option
wenzelm@21505
    12
  val get_hints: Proof.context -> {simps: thm list, congs: (string * thm) list, wfs: thm list}
wenzelm@18728
    13
  val simp_add: attribute
wenzelm@18728
    14
  val simp_del: attribute
wenzelm@18728
    15
  val cong_add: attribute
wenzelm@18728
    16
  val cong_del: attribute
wenzelm@18728
    17
  val wf_add: attribute
wenzelm@18728
    18
  val wf_del: attribute
wenzelm@15703
    19
  val add_recdef: bool -> xstring -> string -> ((bstring * string) * Attrib.src list) list ->
wenzelm@15703
    20
    Attrib.src option -> theory -> theory
wenzelm@9859
    21
      * {simps: thm list, rules: thm list list, induct: thm, tcs: term list}
wenzelm@18728
    22
  val add_recdef_i: bool -> xstring -> term -> ((bstring * term) * attribute list) list ->
wenzelm@9859
    23
    theory -> theory * {simps: thm list, rules: thm list list, induct: thm, tcs: term list}
wenzelm@26336
    24
  val defer_recdef: xstring -> string list -> (Facts.ref * Attrib.src list) list
wenzelm@6557
    25
    -> theory -> theory * {induct_rules: thm}
wenzelm@18728
    26
  val defer_recdef_i: xstring -> term list -> (thm list * attribute list) list
wenzelm@6557
    27
    -> theory -> theory * {induct_rules: thm}
berghofe@24457
    28
  val recdef_tc: bstring * Attrib.src list -> xstring -> int option -> bool -> local_theory -> Proof.state
berghofe@24457
    29
  val recdef_tc_i: bstring * Attrib.src list -> string -> int option -> bool -> local_theory -> Proof.state
wenzelm@18708
    30
  val setup: theory -> theory
wenzelm@6429
    31
end;
wenzelm@6429
    32
wenzelm@6429
    33
structure RecdefPackage: RECDEF_PACKAGE =
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
fun pretty_hints ({simps, congs, wfs}: hints) =
wenzelm@9859
    51
 [Pretty.big_list "recdef simp hints:" (map Display.pretty_thm simps),
haftmann@21098
    52
  Pretty.big_list "recdef cong hints:" (map Display.pretty_thm (map snd congs)),
wenzelm@9859
    53
  Pretty.big_list "recdef wf hints:" (map Display.pretty_thm wfs)];
wenzelm@9859
    54
wenzelm@9859
    55
wenzelm@9859
    56
(* congruence rules *)
wenzelm@9859
    57
wenzelm@9859
    58
local
wenzelm@9859
    59
wenzelm@9859
    60
val cong_head =
wenzelm@9859
    61
  fst o Term.dest_Const o Term.head_of o fst o Logic.dest_equals o Thm.concl_of;
wenzelm@6439
    62
wenzelm@9859
    63
fun prep_cong raw_thm =
wenzelm@9859
    64
  let val thm = safe_mk_meta_eq raw_thm in (cong_head thm, thm) end;
wenzelm@9859
    65
wenzelm@9859
    66
in
wenzelm@9859
    67
wenzelm@9859
    68
fun add_cong raw_thm congs =
haftmann@21098
    69
  let
haftmann@21098
    70
    val (c, thm) = prep_cong raw_thm;
haftmann@21098
    71
    val _ = if AList.defined (op =) congs c
haftmann@21098
    72
      then warning ("Overwriting recdef congruence rule for " ^ quote c)
haftmann@21098
    73
      else ();
haftmann@21098
    74
  in AList.update (op =) (c, thm) congs end;
wenzelm@9859
    75
wenzelm@9859
    76
fun del_cong raw_thm congs =
wenzelm@9859
    77
  let
wenzelm@9859
    78
    val (c, thm) = prep_cong raw_thm;
haftmann@21098
    79
    val _ = if AList.defined (op =) congs c
haftmann@21098
    80
      then ()
haftmann@21098
    81
      else warning ("No recdef congruence rule for " ^ quote c);
haftmann@21098
    82
  in AList.delete (op =) c congs end;
wenzelm@9859
    83
wenzelm@9859
    84
end;
wenzelm@9859
    85
wenzelm@9859
    86
wenzelm@9859
    87
wenzelm@9859
    88
(** global and local recdef data **)
wenzelm@9859
    89
wenzelm@17920
    90
(* theory data *)
wenzelm@6439
    91
wenzelm@8657
    92
type recdef_info = {simps: thm list, rules: thm list list, induct: thm, tcs: term list};
wenzelm@6439
    93
wenzelm@16458
    94
structure GlobalRecdefData = TheoryDataFun
wenzelm@22846
    95
(
wenzelm@9859
    96
  type T = recdef_info Symtab.table * hints;
wenzelm@9879
    97
  val empty = (Symtab.empty, mk_hints ([], [], [])): T;
wenzelm@6557
    98
  val copy = I;
wenzelm@16458
    99
  val extend = I;
wenzelm@16458
   100
  fun merge _
wenzelm@9859
   101
   ((tab1, {simps = simps1, congs = congs1, wfs = wfs1}),
wenzelm@16458
   102
    (tab2, {simps = simps2, congs = congs2, wfs = wfs2})) : T =
wenzelm@9859
   103
      (Symtab.merge (K true) (tab1, tab2),
wenzelm@24039
   104
        mk_hints (Thm.merge_thms (simps1, simps2),
wenzelm@22360
   105
          AList.merge (op =) Thm.eq_thm (congs1, congs2),
wenzelm@24039
   106
          Thm.merge_thms (wfs1, wfs2)));
wenzelm@22846
   107
);
wenzelm@6439
   108
wenzelm@17412
   109
val get_recdef = Symtab.lookup o #1 o GlobalRecdefData.get;
wenzelm@6439
   110
wenzelm@6439
   111
fun put_recdef name info thy =
wenzelm@6429
   112
  let
wenzelm@9859
   113
    val (tab, hints) = GlobalRecdefData.get thy;
wenzelm@17412
   114
    val tab' = Symtab.update_new (name, info) tab
wenzelm@6439
   115
      handle Symtab.DUP _ => error ("Duplicate recursive function definition " ^ quote name);
wenzelm@9859
   116
  in GlobalRecdefData.put (tab', hints) thy end;
wenzelm@9859
   117
wenzelm@9859
   118
val get_global_hints = #2 o GlobalRecdefData.get;
wenzelm@9859
   119
wenzelm@9859
   120
wenzelm@17920
   121
(* proof data *)
wenzelm@9859
   122
wenzelm@16458
   123
structure LocalRecdefData = ProofDataFun
wenzelm@22846
   124
(
wenzelm@9859
   125
  type T = hints;
wenzelm@9859
   126
  val init = get_global_hints;
wenzelm@22846
   127
);
wenzelm@9859
   128
wenzelm@21505
   129
val get_hints = LocalRecdefData.get;
wenzelm@21505
   130
fun map_hints f = Context.mapping (GlobalRecdefData.map (apsnd f)) (LocalRecdefData.map f);
wenzelm@9859
   131
wenzelm@20291
   132
wenzelm@20291
   133
(* attributes *)
wenzelm@20291
   134
wenzelm@18728
   135
fun attrib f = Thm.declaration_attribute (map_hints o f);
wenzelm@9859
   136
wenzelm@24039
   137
val simp_add = attrib (map_simps o Thm.add_thm);
wenzelm@24039
   138
val simp_del = attrib (map_simps o Thm.del_thm);
wenzelm@18688
   139
val cong_add = attrib (map_congs o add_cong);
wenzelm@18688
   140
val cong_del = attrib (map_congs o del_cong);
wenzelm@24039
   141
val wf_add = attrib (map_wfs o Thm.add_thm);
wenzelm@24039
   142
val wf_del = attrib (map_wfs o Thm.del_thm);
wenzelm@9859
   143
wenzelm@9859
   144
wenzelm@9949
   145
(* modifiers *)
wenzelm@9859
   146
wenzelm@9949
   147
val recdef_simpN = "recdef_simp";
wenzelm@9949
   148
val recdef_congN = "recdef_cong";
wenzelm@9949
   149
val recdef_wfN = "recdef_wf";
wenzelm@9859
   150
wenzelm@9859
   151
val recdef_modifiers =
wenzelm@18728
   152
 [Args.$$$ recdef_simpN -- Args.colon >> K ((I, simp_add): Method.modifier),
wenzelm@18728
   153
  Args.$$$ recdef_simpN -- Args.add -- Args.colon >> K (I, simp_add),
wenzelm@18728
   154
  Args.$$$ recdef_simpN -- Args.del -- Args.colon >> K (I, simp_del),
wenzelm@18728
   155
  Args.$$$ recdef_congN -- Args.colon >> K (I, cong_add),
wenzelm@18728
   156
  Args.$$$ recdef_congN -- Args.add -- Args.colon >> K (I, cong_add),
wenzelm@18728
   157
  Args.$$$ recdef_congN -- Args.del -- Args.colon >> K (I, cong_del),
wenzelm@18728
   158
  Args.$$$ recdef_wfN -- Args.colon >> K (I, wf_add),
wenzelm@18728
   159
  Args.$$$ recdef_wfN -- Args.add -- Args.colon >> K (I, wf_add),
wenzelm@18728
   160
  Args.$$$ recdef_wfN -- Args.del -- Args.colon >> K (I, wf_del)] @
wenzelm@9949
   161
  Clasimp.clasimp_modifiers;
wenzelm@9859
   162
wenzelm@9949
   163
wenzelm@9859
   164
wenzelm@9949
   165
(** prepare_hints(_i) **)
wenzelm@9859
   166
wenzelm@9859
   167
fun prepare_hints thy opt_src =
wenzelm@9859
   168
  let
wenzelm@9859
   169
    val ctxt0 = ProofContext.init thy;
wenzelm@9859
   170
    val ctxt =
wenzelm@9859
   171
      (case opt_src of
skalberg@15531
   172
        NONE => ctxt0
skalberg@15531
   173
      | SOME src => Method.only_sectioned_args recdef_modifiers I src ctxt0);
wenzelm@21505
   174
    val {simps, congs, wfs} = get_hints ctxt;
wenzelm@15032
   175
    val cs = local_claset_of ctxt;
wenzelm@15032
   176
    val ss = local_simpset_of ctxt addsimps simps;
haftmann@21098
   177
  in (cs, ss, rev (map snd congs), wfs) end;
wenzelm@9859
   178
wenzelm@9859
   179
fun prepare_hints_i thy () =
wenzelm@15032
   180
  let
wenzelm@15032
   181
    val ctxt0 = ProofContext.init thy;
wenzelm@15032
   182
    val {simps, congs, wfs} = get_global_hints thy;
haftmann@21098
   183
  in (local_claset_of ctxt0, local_simpset_of ctxt0 addsimps simps, rev (map snd congs), wfs) end;
wenzelm@9859
   184
wenzelm@6439
   185
wenzelm@6439
   186
wenzelm@6439
   187
(** add_recdef(_i) **)
wenzelm@6439
   188
wenzelm@6557
   189
fun requires_recdef thy = Theory.requires thy "Recdef" "recursive functions";
wenzelm@6557
   190
wenzelm@17920
   191
fun gen_add_recdef tfl_fn prep_att prep_hints not_permissive raw_name R eq_srcs hints thy =
wenzelm@6439
   192
  let
wenzelm@9859
   193
    val _ = requires_recdef thy;
wenzelm@9859
   194
wenzelm@16458
   195
    val name = Sign.intern_const thy raw_name;
wenzelm@6439
   196
    val bname = Sign.base_name name;
wenzelm@26478
   197
    val _ = writeln ("Defining recursive function " ^ quote name ^ " ...");
wenzelm@6429
   198
wenzelm@8657
   199
    val ((eq_names, eqs), raw_eq_atts) = apfst split_list (split_list eq_srcs);
wenzelm@8657
   200
    val eq_atts = map (map (prep_att thy)) raw_eq_atts;
wenzelm@8657
   201
wenzelm@9859
   202
    val (cs, ss, congs, wfs) = prep_hints thy hints;
paulson@14241
   203
    (*We must remove imp_cong to prevent looping when the induction rule
paulson@14241
   204
      is simplified. Many induction rules have nested implications that would
paulson@14241
   205
      give rise to looping conditional rewriting.*)
paulson@14241
   206
    val (thy, {rules = rules_idx, induct, tcs}) =
wenzelm@17920
   207
        tfl_fn not_permissive thy cs (ss delcongs [imp_cong])
paulson@14241
   208
               congs wfs name R eqs;
haftmann@21098
   209
    val rules = (map o map) fst (partition_eq (eq_snd (op = : int * int -> bool)) rules_idx);
haftmann@24624
   210
    val simp_att = if null tcs then [Simplifier.simp_add, RecfunCodegen.add_default] else [];
wenzelm@8657
   211
haftmann@18377
   212
    val ((simps' :: rules', [induct']), thy) =
wenzelm@7798
   213
      thy
wenzelm@24712
   214
      |> Sign.add_path bname
wenzelm@18688
   215
      |> PureThy.add_thmss
wenzelm@18688
   216
        ((("simps", List.concat rules), simp_att) :: ((eq_names ~~ rules) ~~ eq_atts))
haftmann@18377
   217
      ||>> PureThy.add_thms [(("induct", induct), [])];
wenzelm@8657
   218
    val result = {simps = simps', rules = rules', induct = induct', tcs = tcs};
wenzelm@7798
   219
    val thy =
wenzelm@7798
   220
      thy
wenzelm@6439
   221
      |> put_recdef name result
wenzelm@24712
   222
      |> Sign.parent_path;
wenzelm@7798
   223
  in (thy, result) end;
wenzelm@6429
   224
wenzelm@18728
   225
val add_recdef = gen_add_recdef Tfl.define Attrib.attribute prepare_hints;
wenzelm@11629
   226
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
   227
wenzelm@9859
   228
wenzelm@6557
   229
wenzelm@6557
   230
(** defer_recdef(_i) **)
wenzelm@6557
   231
wenzelm@6557
   232
fun gen_defer_recdef tfl_fn app_thms raw_name eqs raw_congs thy =
wenzelm@6557
   233
  let
wenzelm@16458
   234
    val name = Sign.intern_const thy raw_name;
wenzelm@6557
   235
    val bname = Sign.base_name name;
wenzelm@6557
   236
wenzelm@6557
   237
    val _ = requires_recdef thy;
wenzelm@26478
   238
    val _ = writeln ("Deferred recursive function " ^ quote name ^ " ...");
wenzelm@6557
   239
haftmann@18418
   240
    val (congs, thy1) = thy |> app_thms raw_congs;
wenzelm@9859
   241
    val (thy2, induct_rules) = tfl_fn thy1 congs name eqs;
haftmann@18377
   242
    val ([induct_rules'], thy3) =
wenzelm@6557
   243
      thy2
wenzelm@24712
   244
      |> Sign.add_path bname
wenzelm@6557
   245
      |> PureThy.add_thms [(("induct_rules", induct_rules), [])]
wenzelm@24712
   246
      ||> Sign.parent_path;
wenzelm@8430
   247
  in (thy3, {induct_rules = induct_rules'}) end;
wenzelm@6557
   248
wenzelm@21351
   249
val defer_recdef = gen_defer_recdef Tfl.defer IsarCmd.apply_theorems;
wenzelm@21351
   250
val defer_recdef_i = gen_defer_recdef Tfl.defer_i IsarCmd.apply_theorems_i;
wenzelm@6557
   251
wenzelm@6557
   252
wenzelm@6557
   253
wenzelm@10775
   254
(** recdef_tc(_i) **)
wenzelm@10775
   255
berghofe@24457
   256
fun gen_recdef_tc prep_att prep_name (bname, raw_atts) raw_name opt_i int lthy =
wenzelm@10775
   257
  let
wenzelm@21351
   258
    val thy = ProofContext.theory_of lthy;
wenzelm@16458
   259
    val name = prep_name thy raw_name;
wenzelm@10775
   260
    val atts = map (prep_att thy) raw_atts;
wenzelm@10775
   261
    val tcs =
wenzelm@10775
   262
      (case get_recdef thy name of
skalberg@15531
   263
        NONE => error ("No recdef definition of constant: " ^ quote name)
skalberg@15531
   264
      | SOME {tcs, ...} => tcs);
wenzelm@21351
   265
    val i = the_default 1 opt_i;
wenzelm@21351
   266
    val tc = nth tcs (i - 1) handle Subscript =>
wenzelm@10775
   267
      error ("No termination condition #" ^ string_of_int i ^
wenzelm@10775
   268
        " in recdef definition of " ^ quote name);
wenzelm@21351
   269
  in
wenzelm@24927
   270
    Specification.theorem Thm.internalK NONE (K I) (bname, atts)
berghofe@24457
   271
      [] (Element.Shows [(("", []), [(HOLogic.mk_Trueprop tc, [])])]) int lthy
wenzelm@21351
   272
  end;
wenzelm@10775
   273
wenzelm@21351
   274
val recdef_tc = gen_recdef_tc Attrib.intern_src Sign.intern_const;
wenzelm@10775
   275
val recdef_tc_i = gen_recdef_tc (K I) (K I);
wenzelm@10775
   276
wenzelm@10775
   277
wenzelm@10775
   278
wenzelm@6439
   279
(** package setup **)
wenzelm@6439
   280
wenzelm@6439
   281
(* setup theory *)
wenzelm@6439
   282
wenzelm@9859
   283
val setup =
wenzelm@9859
   284
  Attrib.add_attributes
wenzelm@18728
   285
   [(recdef_simpN, Attrib.add_del_args simp_add simp_del, "declaration of recdef simp rule"),
krauss@19770
   286
    (recdef_congN, Attrib.add_del_args cong_add cong_del, "declaration of recdef cong rule"),
wenzelm@18728
   287
    (recdef_wfN, Attrib.add_del_args wf_add wf_del, "declaration of recdef wf rule")];
wenzelm@6439
   288
wenzelm@6439
   289
wenzelm@6429
   290
(* outer syntax *)
wenzelm@6429
   291
wenzelm@17057
   292
local structure P = OuterParse and K = OuterKeyword in
wenzelm@6429
   293
wenzelm@27353
   294
val _ = List.app OuterKeyword.keyword ["permissive", "congs", "hints"];
wenzelm@24867
   295
wenzelm@9859
   296
val hints =
wenzelm@9859
   297
  P.$$$ "(" |-- P.!!! (P.position (P.$$$ "hints" -- P.arguments) --| P.$$$ ")") >> Args.src;
wenzelm@9859
   298
wenzelm@6429
   299
val recdef_decl =
wenzelm@11629
   300
  Scan.optional (P.$$$ "(" -- P.!!! (P.$$$ "permissive" -- P.$$$ ")") >> K false) true --
wenzelm@22101
   301
  P.name -- P.term -- Scan.repeat1 (SpecParse.opt_thm_name ":" -- P.prop) -- Scan.option hints
wenzelm@11629
   302
  >> (fn ((((p, f), R), eqs), src) => #1 o add_recdef p f R (map P.triple_swap eqs) src);
wenzelm@6429
   303
wenzelm@24867
   304
val _ =
wenzelm@6723
   305
  OuterSyntax.command "recdef" "define general recursive functions (TFL)" K.thy_decl
wenzelm@6429
   306
    (recdef_decl >> Toplevel.theory);
wenzelm@6429
   307
wenzelm@6557
   308
wenzelm@6557
   309
val defer_recdef_decl =
wenzelm@8657
   310
  P.name -- Scan.repeat1 P.prop --
wenzelm@22101
   311
  Scan.optional (P.$$$ "(" |-- P.$$$ "congs" |-- P.!!! (SpecParse.xthms1 --| P.$$$ ")")) []
wenzelm@6557
   312
  >> (fn ((f, eqs), congs) => #1 o defer_recdef f eqs congs);
wenzelm@6557
   313
wenzelm@24867
   314
val _ =
wenzelm@6723
   315
  OuterSyntax.command "defer_recdef" "defer general recursive functions (TFL)" K.thy_decl
wenzelm@6557
   316
    (defer_recdef_decl >> Toplevel.theory);
wenzelm@6557
   317
wenzelm@24867
   318
val _ =
wenzelm@26988
   319
  OuterSyntax.local_theory_to_proof' "recdef_tc" "recommence proof of termination condition (TFL)"
wenzelm@26988
   320
    K.thy_goal
wenzelm@26988
   321
    (SpecParse.opt_thm_name ":" -- P.xname -- Scan.option (P.$$$ "(" |-- P.nat --| P.$$$ ")")
wenzelm@26988
   322
      >> (fn ((thm_name, name), i) => recdef_tc thm_name name i));
wenzelm@10775
   323
wenzelm@6429
   324
end;
wenzelm@6429
   325
wenzelm@6429
   326
end;