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