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