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