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