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