11 type unfold_thms |
11 type unfold_thms |
12 val empty_unfold: unfold_thms |
12 val empty_unfold: unfold_thms |
13 val map_unfolds_of: unfold_thms -> thm list |
13 val map_unfolds_of: unfold_thms -> thm list |
14 val set_unfoldss_of: unfold_thms -> thm list list |
14 val set_unfoldss_of: unfold_thms -> thm list list |
15 val rel_unfolds_of: unfold_thms -> thm list |
15 val rel_unfolds_of: unfold_thms -> thm list |
16 val pred_unfolds_of: unfold_thms -> thm list |
|
17 |
16 |
18 val bnf_of_typ: BNF_Def.const_policy -> (binding -> binding) -> |
17 val bnf_of_typ: BNF_Def.const_policy -> (binding -> binding) -> |
19 ((string * sort) list list -> (string * sort) list) -> typ -> unfold_thms * Proof.context -> |
18 ((string * sort) list list -> (string * sort) list) -> typ -> unfold_thms * Proof.context -> |
20 (BNF_Def.BNF * (typ list * typ list)) * (unfold_thms * Proof.context) |
19 (BNF_Def.BNF * (typ list * typ list)) * (unfold_thms * Proof.context) |
21 val default_comp_sort: (string * sort) list list -> (string * sort) list |
20 val default_comp_sort: (string * sort) list list -> (string * sort) list |
35 open BNF_Comp_Tactics |
34 open BNF_Comp_Tactics |
36 |
35 |
37 type unfold_thms = { |
36 type unfold_thms = { |
38 map_unfolds: thm list, |
37 map_unfolds: thm list, |
39 set_unfoldss: thm list list, |
38 set_unfoldss: thm list list, |
40 rel_unfolds: thm list, |
39 rel_unfolds: thm list |
41 pred_unfolds: thm list |
|
42 }; |
40 }; |
43 |
41 |
44 fun add_to_thms thms NONE = thms |
42 fun add_to_thms thms NONE = thms |
45 | add_to_thms thms (SOME new) = if Thm.is_reflexive new then thms else insert Thm.eq_thm new thms; |
43 | add_to_thms thms (SOME new) = if Thm.is_reflexive new then thms else insert Thm.eq_thm new thms; |
46 fun adds_to_thms thms NONE = thms |
44 fun adds_to_thms thms NONE = thms |
47 | adds_to_thms thms (SOME news) = insert (eq_set Thm.eq_thm) (filter_refl news) thms; |
45 | adds_to_thms thms (SOME news) = insert (eq_set Thm.eq_thm) (filter_out_refl news) thms; |
48 |
46 |
49 fun mk_unfold_thms maps setss rels preds = |
47 fun mk_unfold_thms maps setss rels = {map_unfolds = maps, set_unfoldss = setss, rel_unfolds = rels}; |
50 {map_unfolds = maps, set_unfoldss = setss, rel_unfolds = rels, pred_unfolds = preds}; |
48 |
51 |
49 val empty_unfold = mk_unfold_thms [] [] []; |
52 val empty_unfold = mk_unfold_thms [] [] [] []; |
50 |
53 |
51 fun add_to_unfold_opt map_opt sets_opt rel_opt |
54 fun add_to_unfold_opt map_opt sets_opt rel_opt pred_opt |
52 {map_unfolds = maps, set_unfoldss = setss, rel_unfolds = rels} = { |
55 {map_unfolds = maps, set_unfoldss = setss, rel_unfolds = rels, pred_unfolds = preds} = { |
|
56 map_unfolds = add_to_thms maps map_opt, |
53 map_unfolds = add_to_thms maps map_opt, |
57 set_unfoldss = adds_to_thms setss sets_opt, |
54 set_unfoldss = adds_to_thms setss sets_opt, |
58 rel_unfolds = add_to_thms rels rel_opt, |
55 rel_unfolds = add_to_thms rels rel_opt}; |
59 pred_unfolds = add_to_thms preds pred_opt}; |
56 |
60 |
57 fun add_to_unfold map sets rel = add_to_unfold_opt (SOME map) (SOME sets) (SOME rel); |
61 fun add_to_unfold map sets rel pred = |
|
62 add_to_unfold_opt (SOME map) (SOME sets) (SOME rel) (SOME pred); |
|
63 |
58 |
64 val map_unfolds_of = #map_unfolds; |
59 val map_unfolds_of = #map_unfolds; |
65 val set_unfoldss_of = #set_unfoldss; |
60 val set_unfoldss_of = #set_unfoldss; |
66 val rel_unfolds_of = #rel_unfolds; |
61 val rel_unfolds_of = #rel_unfolds; |
67 val pred_unfolds_of = #pred_unfolds; |
|
68 |
62 |
69 val bdTN = "bdT"; |
63 val bdTN = "bdT"; |
70 |
64 |
71 fun mk_killN n = "_kill" ^ string_of_int n; |
65 fun mk_killN n = "_kill" ^ string_of_int n; |
72 fun mk_liftN n = "_lift" ^ string_of_int n; |
66 fun mk_liftN n = "_lift" ^ string_of_int n; |
73 fun mk_permuteN src dest = |
67 fun mk_permuteN src dest = |
74 "_permute_" ^ implode (map string_of_int src) ^ "_" ^ implode (map string_of_int dest); |
68 "_permute_" ^ implode (map string_of_int src) ^ "_" ^ implode (map string_of_int dest); |
75 |
69 |
76 val no_thm = refl; |
70 val subst_rel_def = @{thm subst_rel_def}; |
77 val Collect_split_box_equals = box_equals RS @{thm Collect_split_cong}; |
|
78 val abs_pred_sym = sym RS @{thm abs_pred_def}; |
|
79 val abs_pred_sym_pred_abs = abs_pred_sym RS @{thm pred_def_abs}; |
|
80 |
71 |
81 (*copied from Envir.expand_term_free*) |
72 (*copied from Envir.expand_term_free*) |
82 fun expand_term_const defs = |
73 fun expand_term_const defs = |
83 let |
74 let |
84 val eqs = map ((fn ((x, U), u) => (x, (U, u))) o apfst dest_Const) defs; |
75 val eqs = map ((fn ((x, U), u) => (x, (U, u))) o apfst dest_Const) defs; |
109 val Ass_repl = replicate olive As; |
100 val Ass_repl = replicate olive As; |
110 val (Bs, _(*lthy4*)) = apfst (map TFree) |
101 val (Bs, _(*lthy4*)) = apfst (map TFree) |
111 (Variable.invent_types (replicate ilive HOLogic.typeS) lthy3); |
102 (Variable.invent_types (replicate ilive HOLogic.typeS) lthy3); |
112 val Bss_repl = replicate olive Bs; |
103 val Bss_repl = replicate olive Bs; |
113 |
104 |
114 val (((fs', Asets), xs), _(*names_lthy*)) = lthy |
105 val ((((fs', Rs'), Asets), xs), _(*names_lthy*)) = lthy |
115 |> apfst snd o mk_Frees' "f" (map2 (curry (op -->)) As Bs) |
106 |> apfst snd o mk_Frees' "f" (map2 (curry (op -->)) As Bs) |
116 ||>> mk_Frees "A" (map (HOLogic.mk_setT) As) |
107 ||>> apfst snd o mk_Frees' "R" (map2 (curry mk_relT) As Bs) |
|
108 ||>> mk_Frees "A" (map HOLogic.mk_setT As) |
117 ||>> mk_Frees "x" As; |
109 ||>> mk_Frees "x" As; |
118 |
110 |
119 val CAs = map3 mk_T_of_bnf Dss Ass_repl inners; |
111 val CAs = map3 mk_T_of_bnf Dss Ass_repl inners; |
120 val CCA = mk_T_of_bnf oDs CAs outer; |
112 val CCA = mk_T_of_bnf oDs CAs outer; |
121 val CBs = map3 mk_T_of_bnf Dss Bss_repl inners; |
113 val CBs = map3 mk_T_of_bnf Dss Bss_repl inners; |
127 (*%f1 ... fn. outer.map (inner_1.map f1 ... fn) ... (inner_m.map f1 ... fn)*) |
119 (*%f1 ... fn. outer.map (inner_1.map f1 ... fn) ... (inner_m.map f1 ... fn)*) |
128 val mapx = fold_rev Term.abs fs' |
120 val mapx = fold_rev Term.abs fs' |
129 (Term.list_comb (mk_map_of_bnf oDs CAs CBs outer, |
121 (Term.list_comb (mk_map_of_bnf oDs CAs CBs outer, |
130 map2 (fn Ds => (fn f => Term.list_comb (f, map Bound ((ilive - 1) downto 0))) o |
122 map2 (fn Ds => (fn f => Term.list_comb (f, map Bound ((ilive - 1) downto 0))) o |
131 mk_map_of_bnf Ds As Bs) Dss inners)); |
123 mk_map_of_bnf Ds As Bs) Dss inners)); |
|
124 (*%R1 ... Rn. outer.rel (inner_1.rel R1 ... Rn) ... (inner_m.rel R1 ... Rn)*) |
|
125 val rel = fold_rev Term.abs Rs' |
|
126 (Term.list_comb (mk_rel_of_bnf oDs CAs CBs outer, |
|
127 map2 (fn Ds => (fn f => Term.list_comb (f, map Bound ((ilive - 1) downto 0))) o |
|
128 mk_rel_of_bnf Ds As Bs) Dss inners)); |
132 |
129 |
133 (*Union o collect {outer.set_1 ... outer.set_m} o outer.map inner_1.set_i ... inner_m.set_i*) |
130 (*Union o collect {outer.set_1 ... outer.set_m} o outer.map inner_1.set_i ... inner_m.set_i*) |
134 (*Union o collect {image inner_1.set_i o outer.set_1 ... image inner_m.set_i o outer.set_m}*) |
131 (*Union o collect {image inner_1.set_i o outer.set_1 ... image inner_m.set_i o outer.set_m}*) |
135 fun mk_set i = |
132 fun mk_set i = |
136 let |
133 let |
231 (map bd_Cinfinite_of_bnf inners) (bd_Card_order_of_bnf outer); |
228 (map bd_Cinfinite_of_bnf inners) (bd_Card_order_of_bnf outer); |
232 |
229 |
233 fun map_wpull_tac _ = |
230 fun map_wpull_tac _ = |
234 mk_map_wpull_tac in_alt_thm (map map_wpull_of_bnf inners) (map_wpull_of_bnf outer); |
231 mk_map_wpull_tac in_alt_thm (map map_wpull_of_bnf inners) (map_wpull_of_bnf outer); |
235 |
232 |
236 val tacs = [map_id_tac, map_comp_tac, map_cong_tac] @ set_natural_tacs @ [bd_card_order_tac, |
233 fun rel_O_Gr_tac _ = |
237 bd_cinfinite_tac] @ set_bd_tacs @ [in_bd_tac, map_wpull_tac]; |
234 let |
|
235 val outer_rel_Gr = rel_Gr_of_bnf outer RS sym; |
|
236 val outer_rel_cong = rel_cong_of_bnf outer; |
|
237 in |
|
238 rtac (trans OF [in_alt_thm RS subst_rel_def, |
|
239 trans OF [@{thm arg_cong2[of _ _ _ _ relcomp]} OF |
|
240 [trans OF [outer_rel_Gr RS @{thm arg_cong[of _ _ converse]}, |
|
241 rel_converse_of_bnf outer RS sym], outer_rel_Gr], |
|
242 trans OF [rel_O_of_bnf outer RS sym, outer_rel_cong OF |
|
243 (map (fn bnf => rel_O_Gr_of_bnf bnf RS sym) inners)]]] RS sym) 1 |
|
244 end |
|
245 |
|
246 val tacs = zip_goals map_id_tac map_comp_tac map_cong_tac set_natural_tacs bd_card_order_tac |
|
247 bd_cinfinite_tac set_bd_tacs in_bd_tac map_wpull_tac rel_O_Gr_tac; |
238 |
248 |
239 val outer_wits = mk_wits_of_bnf (replicate onwits oDs) (replicate onwits CAs) outer; |
249 val outer_wits = mk_wits_of_bnf (replicate onwits oDs) (replicate onwits CAs) outer; |
240 |
250 |
241 val inner_witss = map (map (fn (I, wit) => Term.list_comb (wit, map (nth xs) I))) |
251 val inner_witss = map (map (fn (I, wit) => Term.list_comb (wit, map (nth xs) I))) |
242 (map3 (fn Ds => fn n => mk_wits_of_bnf (replicate n Ds) (replicate n As)) |
252 (map3 (fn Ds => fn n => mk_wits_of_bnf (replicate n Ds) (replicate n As)) |
257 |
267 |
258 val (bnf', lthy') = |
268 val (bnf', lthy') = |
259 bnf_def const_policy (K Derive_Some_Facts) qualify tacs wit_tac (SOME (oDs @ flat Dss)) |
269 bnf_def const_policy (K Derive_Some_Facts) qualify tacs wit_tac (SOME (oDs @ flat Dss)) |
260 (((((b, mapx), sets), bd), wits), rel) lthy; |
270 (((((b, mapx), sets), bd), wits), rel) lthy; |
261 |
271 |
262 val outer_rel_Gr = rel_Gr_of_bnf outer RS sym; |
272 val unfold' = add_to_unfold (map_def_of_bnf bnf') (set_defs_of_bnf bnf') (rel_def_of_bnf bnf') |
263 val outer_rel_cong = rel_cong_of_bnf outer; |
273 unfold; |
264 |
|
265 val rel_unfold_thm = |
|
266 trans OF [rel_O_Gr_of_bnf bnf', |
|
267 trans OF [in_alt_thm RS @{thm subst_rel_def}, |
|
268 trans OF [@{thm arg_cong2[of _ _ _ _ relcomp]} OF |
|
269 [trans OF [outer_rel_Gr RS @{thm arg_cong[of _ _ converse]}, |
|
270 rel_converse_of_bnf outer RS sym], outer_rel_Gr], |
|
271 trans OF [rel_O_of_bnf outer RS sym, outer_rel_cong OF |
|
272 (map (fn bnf => rel_O_Gr_of_bnf bnf RS sym) inners)]]]]; |
|
273 |
|
274 val pred_unfold_thm = Collect_split_box_equals OF [rel_unfold_thm, |
|
275 pred_def_of_bnf bnf' RS abs_pred_sym, |
|
276 trans OF [outer_rel_cong OF (map (fn bnf => pred_def_of_bnf bnf RS abs_pred_sym) inners), |
|
277 pred_def_of_bnf outer RS abs_pred_sym]]; |
|
278 |
|
279 val unfold' = add_to_unfold (map_def_of_bnf bnf') (set_defs_of_bnf bnf') rel_unfold_thm |
|
280 pred_unfold_thm unfold; |
|
281 in |
274 in |
282 (bnf', (unfold', lthy')) |
275 (bnf', (unfold', lthy')) |
283 end; |
276 end; |
284 |
277 |
285 (* Killing live variables *) |
278 (* Killing live variables *) |
299 (Variable.invent_types (replicate live HOLogic.typeS) lthy1); |
292 (Variable.invent_types (replicate live HOLogic.typeS) lthy1); |
300 val (Bs, _(*lthy3*)) = apfst (append killedAs o map TFree) |
293 val (Bs, _(*lthy3*)) = apfst (append killedAs o map TFree) |
301 (Variable.invent_types (replicate (live - n) HOLogic.typeS) lthy2); |
294 (Variable.invent_types (replicate (live - n) HOLogic.typeS) lthy2); |
302 |
295 |
303 val ((Asets, lives), _(*names_lthy*)) = lthy |
296 val ((Asets, lives), _(*names_lthy*)) = lthy |
304 |> mk_Frees "A" (map (HOLogic.mk_setT) (drop n As)) |
297 |> mk_Frees "A" (map HOLogic.mk_setT (drop n As)) |
305 ||>> mk_Frees "x" (drop n As); |
298 ||>> mk_Frees "x" (drop n As); |
306 val xs = map (fn T => HOLogic.choice_const T $ absdummy T @{term True}) killedAs @ lives; |
299 val xs = map (fn T => HOLogic.choice_const T $ absdummy T @{term True}) killedAs @ lives; |
307 |
300 |
308 val T = mk_T_of_bnf Ds As bnf; |
301 val T = mk_T_of_bnf Ds As bnf; |
309 |
302 |
310 (*bnf.map id ... id*) |
303 (*bnf.map id ... id*) |
311 val mapx = Term.list_comb (mk_map_of_bnf Ds As Bs bnf, map HOLogic.id_const killedAs); |
304 val mapx = Term.list_comb (mk_map_of_bnf Ds As Bs bnf, map HOLogic.id_const killedAs); |
|
305 (*bnf.rel Id ... Id*) |
|
306 val rel = Term.list_comb (mk_rel_of_bnf Ds As Bs bnf, map Id_const killedAs); |
312 |
307 |
313 val bnf_sets = mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf; |
308 val bnf_sets = mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf; |
314 val sets = drop n bnf_sets; |
309 val sets = drop n bnf_sets; |
315 |
310 |
316 (*(|UNIV :: A1 set| +c ... +c |UNIV :: An set|) *c bnf.bd*) |
311 (*(|UNIV :: A1 set| +c ... +c |UNIV :: An set|) *c bnf.bd*) |
343 fun in_bd_tac _ = |
338 fun in_bd_tac _ = |
344 mk_kill_in_bd_tac n (live > n) in_alt_thm (in_bd_of_bnf bnf) (bd_Card_order_of_bnf bnf) |
339 mk_kill_in_bd_tac n (live > n) in_alt_thm (in_bd_of_bnf bnf) (bd_Card_order_of_bnf bnf) |
345 (bd_Cinfinite_of_bnf bnf) (bd_Cnotzero_of_bnf bnf); |
340 (bd_Cinfinite_of_bnf bnf) (bd_Cnotzero_of_bnf bnf); |
346 fun map_wpull_tac _ = mk_map_wpull_tac in_alt_thm [] (map_wpull_of_bnf bnf); |
341 fun map_wpull_tac _ = mk_map_wpull_tac in_alt_thm [] (map_wpull_of_bnf bnf); |
347 |
342 |
348 val tacs = [map_id_tac, map_comp_tac, map_cong_tac] @ set_natural_tacs @ [bd_card_order_tac, |
343 fun rel_O_Gr_tac _ = |
349 bd_cinfinite_tac] @ set_bd_tacs @ [in_bd_tac, map_wpull_tac]; |
344 let |
|
345 val rel_Gr = rel_Gr_of_bnf bnf RS sym |
|
346 in |
|
347 rtac (trans OF [in_alt_thm RS subst_rel_def, |
|
348 trans OF [@{thm arg_cong2[of _ _ _ _ relcomp]} OF |
|
349 [trans OF [rel_Gr RS @{thm arg_cong[of _ _ converse]}, |
|
350 rel_converse_of_bnf bnf RS sym], rel_Gr], |
|
351 trans OF [rel_O_of_bnf bnf RS sym, rel_cong_of_bnf bnf OF |
|
352 (replicate n @{thm trans[OF Gr_UNIV_id[OF refl] Id_alt[symmetric]]} @ |
|
353 replicate (live - n) @{thm Gr_fst_snd})]]] RS sym) 1 |
|
354 end; |
|
355 |
|
356 val tacs = zip_goals map_id_tac map_comp_tac map_cong_tac set_natural_tacs bd_card_order_tac |
|
357 bd_cinfinite_tac set_bd_tacs in_bd_tac map_wpull_tac rel_O_Gr_tac; |
350 |
358 |
351 val bnf_wits = mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf; |
359 val bnf_wits = mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf; |
352 |
360 |
353 val wits = map (fn t => fold absfree (Term.add_frees t []) t) |
361 val wits = map (fn t => fold absfree (Term.add_frees t []) t) |
354 (map (fn (I, wit) => Term.list_comb (wit, map (nth xs) I)) bnf_wits); |
362 (map (fn (I, wit) => Term.list_comb (wit, map (nth xs) I)) bnf_wits); |
355 |
363 |
356 fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf); |
364 fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf); |
357 |
365 |
358 val (bnf', lthy') = |
366 val (bnf', lthy') = |
359 bnf_def Smart_Inline (K Derive_Some_Facts) qualify tacs wit_tac (SOME (killedAs @ Ds)) |
367 bnf_def Smart_Inline (K Derive_Some_Facts) qualify tacs wit_tac (SOME (killedAs @ Ds)) |
360 ((((b, mapx), sets), Term.absdummy T bd), wits) lthy; |
368 (((((b, mapx), sets), Term.absdummy T bd), wits), rel) lthy; |
361 |
369 |
362 val rel_Gr = rel_Gr_of_bnf bnf RS sym; |
370 val unfold' = add_to_unfold (map_def_of_bnf bnf') (set_defs_of_bnf bnf') (rel_def_of_bnf bnf') |
363 |
371 unfold; |
364 val rel_unfold_thm = |
|
365 trans OF [rel_O_Gr_of_bnf bnf', |
|
366 trans OF [in_alt_thm RS @{thm subst_rel_def}, |
|
367 trans OF [@{thm arg_cong2[of _ _ _ _ relcomp]} OF |
|
368 [trans OF [rel_Gr RS @{thm arg_cong[of _ _ converse]}, rel_converse_of_bnf bnf RS sym], |
|
369 rel_Gr], |
|
370 trans OF [rel_O_of_bnf bnf RS sym, rel_cong_of_bnf bnf OF |
|
371 (replicate n @{thm trans[OF Gr_UNIV_id[OF refl] Id_alt[symmetric]]} @ |
|
372 replicate (live - n) @{thm Gr_fst_snd})]]]]; |
|
373 |
|
374 val pred_unfold_thm = Collect_split_box_equals OF |
|
375 [Local_Defs.unfold lthy' @{thms Id_def'} rel_unfold_thm, pred_def_of_bnf bnf' RS abs_pred_sym, |
|
376 pred_def_of_bnf bnf RS abs_pred_sym]; |
|
377 |
|
378 val unfold' = add_to_unfold (map_def_of_bnf bnf') (set_defs_of_bnf bnf') rel_unfold_thm |
|
379 pred_unfold_thm unfold; |
|
380 in |
372 in |
381 (bnf', (unfold', lthy')) |
373 (bnf', (unfold', lthy')) |
382 end; |
374 end; |
383 |
375 |
384 (* Adding dummy live variables *) |
376 (* Adding dummy live variables *) |
398 (Variable.invent_types (replicate (n + live) HOLogic.typeS) lthy1); |
390 (Variable.invent_types (replicate (n + live) HOLogic.typeS) lthy1); |
399 val ((newBs, Bs), _(*lthy3*)) = apfst (chop n o map TFree) |
391 val ((newBs, Bs), _(*lthy3*)) = apfst (chop n o map TFree) |
400 (Variable.invent_types (replicate (n + live) HOLogic.typeS) lthy2); |
392 (Variable.invent_types (replicate (n + live) HOLogic.typeS) lthy2); |
401 |
393 |
402 val (Asets, _(*names_lthy*)) = lthy |
394 val (Asets, _(*names_lthy*)) = lthy |
403 |> mk_Frees "A" (map (HOLogic.mk_setT) (newAs @ As)); |
395 |> mk_Frees "A" (map HOLogic.mk_setT (newAs @ As)); |
404 |
396 |
405 val T = mk_T_of_bnf Ds As bnf; |
397 val T = mk_T_of_bnf Ds As bnf; |
406 |
398 |
407 (*%f1 ... fn. bnf.map*) |
399 (*%f1 ... fn. bnf.map*) |
408 val mapx = |
400 val mapx = |
409 fold_rev Term.absdummy (map2 (curry (op -->)) newAs newBs) (mk_map_of_bnf Ds As Bs bnf); |
401 fold_rev Term.absdummy (map2 (curry (op -->)) newAs newBs) (mk_map_of_bnf Ds As Bs bnf); |
|
402 (*%R1 ... Rn. bnf.rel*) |
|
403 val rel = |
|
404 fold_rev Term.absdummy (map2 (curry mk_relT) newAs newBs) (mk_rel_of_bnf Ds As Bs bnf); |
410 |
405 |
411 val bnf_sets = mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf; |
406 val bnf_sets = mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf; |
412 val sets = map (fn A => absdummy T (HOLogic.mk_set A [])) newAs @ bnf_sets; |
407 val sets = map (fn A => absdummy T (HOLogic.mk_set A [])) newAs @ bnf_sets; |
413 |
408 |
414 val bd = mk_bd_of_bnf Ds As bnf; |
409 val bd = mk_bd_of_bnf Ds As bnf; |
444 end; |
439 end; |
445 |
440 |
446 fun in_bd_tac _ = mk_lift_in_bd_tac n in_alt_thm (in_bd_of_bnf bnf) (bd_Card_order_of_bnf bnf); |
441 fun in_bd_tac _ = mk_lift_in_bd_tac n in_alt_thm (in_bd_of_bnf bnf) (bd_Card_order_of_bnf bnf); |
447 fun map_wpull_tac _ = mk_map_wpull_tac in_alt_thm [] (map_wpull_of_bnf bnf); |
442 fun map_wpull_tac _ = mk_map_wpull_tac in_alt_thm [] (map_wpull_of_bnf bnf); |
448 |
443 |
449 val tacs = [map_id_tac, map_comp_tac, map_cong_tac] @ set_natural_tacs @ [bd_card_order_tac, |
444 fun rel_O_Gr_tac _ = |
450 bd_cinfinite_tac] @ set_bd_tacs @ [in_bd_tac, map_wpull_tac]; |
445 rtac (trans OF [rel_O_Gr_of_bnf bnf, in_alt_thm RS subst_rel_def RS sym]) 1; |
|
446 |
|
447 val tacs = zip_goals map_id_tac map_comp_tac map_cong_tac set_natural_tacs bd_card_order_tac |
|
448 bd_cinfinite_tac set_bd_tacs in_bd_tac map_wpull_tac rel_O_Gr_tac; |
451 |
449 |
452 val wits = map snd (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf); |
450 val wits = map snd (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf); |
453 |
451 |
454 fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf); |
452 fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf); |
455 |
453 |
456 val (bnf', lthy') = |
454 val (bnf', lthy') = |
457 bnf_def Smart_Inline (K Derive_Some_Facts) qualify tacs wit_tac (SOME Ds) |
455 bnf_def Smart_Inline (K Derive_Some_Facts) qualify tacs wit_tac (SOME Ds) |
458 ((((b, mapx), sets), Term.absdummy T bd), wits) lthy; |
456 (((((b, mapx), sets), Term.absdummy T bd), wits), rel) lthy; |
459 |
457 |
460 val rel_unfold_thm = |
458 val unfold' = add_to_unfold (map_def_of_bnf bnf') (set_defs_of_bnf bnf') (rel_def_of_bnf bnf') |
461 trans OF [rel_O_Gr_of_bnf bnf', |
459 unfold; |
462 trans OF [in_alt_thm RS @{thm subst_rel_def}, rel_O_Gr_of_bnf bnf RS sym]]; |
|
463 |
|
464 val pred_unfold_thm = Collect_split_box_equals OF [rel_unfold_thm, |
|
465 pred_def_of_bnf bnf' RS abs_pred_sym, pred_def_of_bnf bnf RS abs_pred_sym]; |
|
466 |
|
467 val unfold' = add_to_unfold (map_def_of_bnf bnf') (set_defs_of_bnf bnf') rel_unfold_thm |
|
468 pred_unfold_thm unfold; |
|
469 in |
460 in |
470 (bnf', (unfold', lthy')) |
461 (bnf', (unfold', lthy')) |
471 end; |
462 end; |
472 |
463 |
473 (* Changing the order of live variables *) |
464 (* Changing the order of live variables *) |
487 (Variable.invent_types (replicate live HOLogic.typeS) lthy1); |
478 (Variable.invent_types (replicate live HOLogic.typeS) lthy1); |
488 val (Bs, _(*lthy3*)) = apfst (map TFree) |
479 val (Bs, _(*lthy3*)) = apfst (map TFree) |
489 (Variable.invent_types (replicate live HOLogic.typeS) lthy2); |
480 (Variable.invent_types (replicate live HOLogic.typeS) lthy2); |
490 |
481 |
491 val (Asets, _(*names_lthy*)) = lthy |
482 val (Asets, _(*names_lthy*)) = lthy |
492 |> mk_Frees "A" (map (HOLogic.mk_setT) (permute As)); |
483 |> mk_Frees "A" (map HOLogic.mk_setT (permute As)); |
493 |
484 |
494 val T = mk_T_of_bnf Ds As bnf; |
485 val T = mk_T_of_bnf Ds As bnf; |
495 |
486 |
496 (*%f(1) ... f(n). bnf.map f\<sigma>(1) ... f\<sigma>(n)*) |
487 (*%f(1) ... f(n). bnf.map f\<sigma>(1) ... f\<sigma>(n)*) |
497 val mapx = fold_rev Term.absdummy (permute (map2 (curry op -->) As Bs)) |
488 val mapx = fold_rev Term.absdummy (permute (map2 (curry op -->) As Bs)) |
498 (Term.list_comb (mk_map_of_bnf Ds As Bs bnf, |
489 (Term.list_comb (mk_map_of_bnf Ds As Bs bnf, permute_rev (map Bound ((live - 1) downto 0)))); |
499 permute_rev (map Bound ((live - 1) downto 0)))); |
490 (*%R(1) ... R(n). bnf.rel R\<sigma>(1) ... R\<sigma>(n)*) |
|
491 val rel = fold_rev Term.absdummy (permute (map2 (curry mk_relT) As Bs)) |
|
492 (Term.list_comb (mk_rel_of_bnf Ds As Bs bnf, permute_rev (map Bound ((live - 1) downto 0)))); |
500 |
493 |
501 val bnf_sets = mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf; |
494 val bnf_sets = mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf; |
502 val sets = permute bnf_sets; |
495 val sets = permute bnf_sets; |
503 |
496 |
504 val bd = mk_bd_of_bnf Ds As bnf; |
497 val bd = mk_bd_of_bnf Ds As bnf; |
524 |
517 |
525 fun in_bd_tac _ = |
518 fun in_bd_tac _ = |
526 mk_permute_in_bd_tac src dest in_alt_thm (in_bd_of_bnf bnf) (bd_Card_order_of_bnf bnf); |
519 mk_permute_in_bd_tac src dest in_alt_thm (in_bd_of_bnf bnf) (bd_Card_order_of_bnf bnf); |
527 fun map_wpull_tac _ = mk_map_wpull_tac in_alt_thm [] (map_wpull_of_bnf bnf); |
520 fun map_wpull_tac _ = mk_map_wpull_tac in_alt_thm [] (map_wpull_of_bnf bnf); |
528 |
521 |
529 val tacs = [map_id_tac, map_comp_tac, map_cong_tac] @ set_natural_tacs @ [bd_card_order_tac, |
522 fun rel_O_Gr_tac _ = |
530 bd_cinfinite_tac] @ set_bd_tacs @ [in_bd_tac, map_wpull_tac]; |
523 rtac (trans OF [rel_O_Gr_of_bnf bnf, in_alt_thm RS subst_rel_def RS sym]) 1; |
|
524 |
|
525 val tacs = zip_goals map_id_tac map_comp_tac map_cong_tac set_natural_tacs bd_card_order_tac |
|
526 bd_cinfinite_tac set_bd_tacs in_bd_tac map_wpull_tac rel_O_Gr_tac; |
531 |
527 |
532 val wits = map snd (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf); |
528 val wits = map snd (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf); |
533 |
529 |
534 fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf); |
530 fun wit_tac _ = mk_simple_wit_tac (wit_thms_of_bnf bnf); |
535 |
531 |
536 val (bnf', lthy') = |
532 val (bnf', lthy') = |
537 bnf_def Smart_Inline (K Derive_Some_Facts) qualify tacs wit_tac (SOME Ds) |
533 bnf_def Smart_Inline (K Derive_Some_Facts) qualify tacs wit_tac (SOME Ds) |
538 ((((b, mapx), sets), Term.absdummy T bd), wits) lthy; |
534 (((((b, mapx), sets), Term.absdummy T bd), wits), rel) lthy; |
539 |
535 |
540 val rel_unfold_thm = |
536 val unfold' = add_to_unfold (map_def_of_bnf bnf') (set_defs_of_bnf bnf') (rel_def_of_bnf bnf') |
541 trans OF [rel_O_Gr_of_bnf bnf', |
537 unfold; |
542 trans OF [in_alt_thm RS @{thm subst_rel_def}, rel_O_Gr_of_bnf bnf RS sym]]; |
|
543 |
|
544 val pred_unfold_thm = Collect_split_box_equals OF [rel_unfold_thm, |
|
545 pred_def_of_bnf bnf' RS abs_pred_sym, pred_def_of_bnf bnf RS abs_pred_sym]; |
|
546 |
|
547 val unfold' = add_to_unfold (map_def_of_bnf bnf') (set_defs_of_bnf bnf') rel_unfold_thm |
|
548 pred_unfold_thm unfold; |
|
549 in |
538 in |
550 (bnf', (unfold', lthy')) |
539 (bnf', (unfold', lthy')) |
551 end; |
540 end; |
552 |
541 |
553 (* Composition pipeline *) |
542 (* Composition pipeline *) |
617 val (As, lthy1) = apfst (map TFree) |
606 val (As, lthy1) = apfst (map TFree) |
618 (Variable.invent_types (replicate live HOLogic.typeS) (fold Variable.declare_typ Ds lthy)); |
607 (Variable.invent_types (replicate live HOLogic.typeS) (fold Variable.declare_typ Ds lthy)); |
619 val (Bs, _) = apfst (map TFree) |
608 val (Bs, _) = apfst (map TFree) |
620 (Variable.invent_types (replicate live HOLogic.typeS) lthy1); |
609 (Variable.invent_types (replicate live HOLogic.typeS) lthy1); |
621 |
610 |
622 val map_unfolds = filter_refl (map_unfolds_of unfold); |
611 val map_unfolds = filter_out_refl (map_unfolds_of unfold); |
623 val set_unfoldss = map filter_refl (set_unfoldss_of unfold); |
612 val set_unfoldss = map filter_out_refl (set_unfoldss_of unfold); |
|
613 val rel_unfolds = filter_out_refl (rel_unfolds_of unfold); |
624 |
614 |
625 val expand_maps = fold expand_term_const (map (single o Logic.dest_equals o Thm.prop_of) |
615 val expand_maps = fold expand_term_const (map (single o Logic.dest_equals o Thm.prop_of) |
626 map_unfolds); |
616 map_unfolds); |
627 val expand_sets = fold expand_term_const (map (map (Logic.dest_equals o Thm.prop_of)) |
617 val expand_sets = fold expand_term_const (map (map (Logic.dest_equals o Thm.prop_of)) |
628 set_unfoldss); |
618 set_unfoldss); |
|
619 val expand_rels = fold expand_term_const (map (single o Logic.dest_equals o Thm.prop_of) |
|
620 rel_unfolds); |
629 val unfold_maps = fold (Local_Defs.unfold lthy o single) map_unfolds; |
621 val unfold_maps = fold (Local_Defs.unfold lthy o single) map_unfolds; |
630 val unfold_sets = fold (Local_Defs.unfold lthy) set_unfoldss; |
622 val unfold_sets = fold (Local_Defs.unfold lthy) set_unfoldss; |
631 val unfold_defs = unfold_sets o unfold_maps; |
623 val unfold_defs = unfold_sets o unfold_maps; |
632 val bnf_map = expand_maps (mk_map_of_bnf Ds As Bs bnf); |
624 val bnf_map = expand_maps (mk_map_of_bnf Ds As Bs bnf); |
633 val bnf_sets = map (expand_maps o expand_sets) |
625 val bnf_sets = map (expand_maps o expand_sets) |
634 (mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf); |
626 (mk_sets_of_bnf (replicate live Ds) (replicate live As) bnf); |
635 val bnf_bd = mk_bd_of_bnf Ds As bnf; |
627 val bnf_bd = mk_bd_of_bnf Ds As bnf; |
|
628 val bnf_rel = expand_rels (mk_rel_of_bnf Ds As Bs bnf); |
636 val T = mk_T_of_bnf Ds As bnf; |
629 val T = mk_T_of_bnf Ds As bnf; |
637 |
630 |
638 (*bd should only depend on dead type variables!*) |
631 (*bd should only depend on dead type variables!*) |
639 val bd_repT = fst (dest_relT (fastype_of bnf_bd)); |
632 val bd_repT = fst (dest_relT (fastype_of bnf_bd)); |
640 val bdT_bind = Binding.suffix_name ("_" ^ bdTN) b; |
633 val bdT_bind = Binding.suffix_name ("_" ^ bdTN) b; |
665 @{thm ctwo_Cnotzero} else @{thm ctwo_Cnotzero} RS @{thm csum_Cnotzero2}, |
658 @{thm ctwo_Cnotzero} else @{thm ctwo_Cnotzero} RS @{thm csum_Cnotzero2}, |
666 bd_Card_order_of_bnf bnf]]; |
659 bd_Card_order_of_bnf bnf]]; |
667 |
660 |
668 fun mk_tac thm {context = ctxt, prems = _} = (rtac (unfold_defs thm) THEN' |
661 fun mk_tac thm {context = ctxt, prems = _} = (rtac (unfold_defs thm) THEN' |
669 SOLVE o REPEAT_DETERM o (atac ORELSE' Goal.assume_rule_tac ctxt)) 1; |
662 SOLVE o REPEAT_DETERM o (atac ORELSE' Goal.assume_rule_tac ctxt)) 1; |
670 val tacs = |
663 |
671 map mk_tac ([map_id_of_bnf bnf, map_comp_of_bnf bnf, map_cong_of_bnf bnf] @ |
664 val tacs = zip_goals (mk_tac (map_id_of_bnf bnf)) (mk_tac (map_comp_of_bnf bnf)) |
672 set_natural_of_bnf bnf) @ |
665 (mk_tac (map_cong_of_bnf bnf)) (map mk_tac (set_natural_of_bnf bnf)) |
673 map K [rtac bd_card_order 1, rtac bd_cinfinite 1] @ |
666 (K (rtac bd_card_order 1)) (K (rtac bd_cinfinite 1)) (map mk_tac set_bds) (mk_tac in_bd) |
674 map mk_tac (set_bds @ [in_bd, map_wpull_of_bnf bnf]); |
667 (mk_tac (map_wpull_of_bnf bnf)) (mk_tac (rel_O_Gr_of_bnf bnf)); |
675 |
668 |
676 val bnf_wits = map snd (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf); |
669 val bnf_wits = map snd (mk_wits_of_bnf (replicate nwits Ds) (replicate nwits As) bnf); |
677 |
670 |
678 fun wit_tac _ = mk_simple_wit_tac (map unfold_defs (wit_thms_of_bnf bnf)); |
671 fun wit_tac _ = mk_simple_wit_tac (map unfold_defs (wit_thms_of_bnf bnf)); |
679 |
672 |
680 val policy = user_policy Derive_All_Facts; |
673 val policy = user_policy Derive_All_Facts; |
681 |
674 |
682 val (bnf', lthy') = bnf_def Hardly_Inline policy I tacs wit_tac (SOME deads) |
675 val (bnf', lthy') = bnf_def Hardly_Inline policy I tacs wit_tac (SOME deads) |
683 ((((b, bnf_map), bnf_sets), Term.absdummy T bnf_bd'), bnf_wits) lthy; |
676 (((((b, bnf_map), bnf_sets), Term.absdummy T bnf_bd'), bnf_wits), bnf_rel) lthy; |
684 |
|
685 val defs' = filter_refl (map_def_of_bnf bnf' :: set_defs_of_bnf bnf'); |
|
686 val unfold_defs' = unfold_defs o Local_Defs.unfold lthy' defs'; |
|
687 |
|
688 val rel_O_Gr = unfold_defs' (rel_O_Gr_of_bnf bnf'); |
|
689 val rel_unfold = Local_Defs.unfold lthy' |
|
690 (map unfold_defs (filter_refl (rel_unfolds_of unfold))) rel_O_Gr; |
|
691 |
|
692 val unfold_defs'' = unfold_defs' o Local_Defs.unfold lthy' (filter_refl [rel_O_Gr_of_bnf bnf']); |
|
693 |
|
694 val pred_def = unfold_defs'' (pred_def_of_bnf bnf' RS abs_pred_sym_pred_abs); |
|
695 val pred_unfold = Local_Defs.unfold lthy' |
|
696 (map unfold_defs (filter_refl (pred_unfolds_of unfold))) pred_def; |
|
697 |
|
698 val notes = |
|
699 [(rel_unfoldN, [rel_unfold]), |
|
700 (pred_unfoldN, [pred_unfold])] |
|
701 |> map (fn (thmN, thms) => |
|
702 ((Binding.qualify true (Binding.name_of b) (Binding.name thmN), []), [(thms, [])])); |
|
703 in |
677 in |
704 ((bnf', deads), lthy' |> Local_Theory.notes notes |> snd) |
678 ((bnf', deads), lthy') |
705 end; |
679 end; |
706 |
680 |
707 val ID_bnf = the (bnf_of @{context} "Basic_BNFs.ID"); |
681 val ID_bnf = the (bnf_of @{context} "Basic_BNFs.ID"); |
708 val DEADID_bnf = the (bnf_of @{context} "Basic_BNFs.DEADID"); |
682 val DEADID_bnf = the (bnf_of @{context} "Basic_BNFs.DEADID"); |
709 |
683 |
710 val ID_rel_O_Gr = rel_O_Gr_of_bnf ID_bnf; |
684 fun bnf_of_typ _ _ _ (T as TFree _) accum = ((ID_bnf, ([], [T])), accum) |
711 val ID_rel_O_Gr' = ID_rel_O_Gr RS sym; |
|
712 val ID_pred_def' = Local_Defs.unfold @{context} [ID_rel_O_Gr] (pred_def_of_bnf ID_bnf) RS sym; |
|
713 |
|
714 fun bnf_of_typ _ _ _ (T as TFree _) (unfold, lthy) = |
|
715 ((ID_bnf, ([], [T])), |
|
716 (add_to_unfold_opt NONE NONE (SOME ID_rel_O_Gr') (SOME ID_pred_def') unfold, lthy)) |
|
717 | bnf_of_typ _ _ _ (TVar _) _ = error "Unexpected schematic variable" |
685 | bnf_of_typ _ _ _ (TVar _) _ = error "Unexpected schematic variable" |
718 | bnf_of_typ const_policy qualify' sort (T as Type (C, Ts)) (unfold, lthy) = |
686 | bnf_of_typ const_policy qualify' sort (T as Type (C, Ts)) (unfold, lthy) = |
719 let |
687 let |
720 val tfrees = Term.add_tfreesT T []; |
688 val tfrees = Term.add_tfreesT T []; |
721 val bnf_opt = if null tfrees then NONE else bnf_of lthy C; |
689 val bnf_opt = if null tfrees then NONE else bnf_of lthy C; |
730 val lives = lives_of_bnf bnf; |
698 val lives = lives_of_bnf bnf; |
731 val tvars' = Term.add_tvarsT T' []; |
699 val tvars' = Term.add_tvarsT T' []; |
732 val deads_lives = |
700 val deads_lives = |
733 pairself (map (Term.typ_subst_TVars (map fst tvars' ~~ map TFree tfrees))) |
701 pairself (map (Term.typ_subst_TVars (map fst tvars' ~~ map TFree tfrees))) |
734 (deads, lives); |
702 (deads, lives); |
735 val rel_O_Gr = rel_O_Gr_of_bnf bnf; |
703 in ((bnf, deads_lives), (unfold, lthy)) end |
736 val unfold' = add_to_unfold_opt NONE NONE (SOME (rel_O_Gr RS sym)) |
|
737 (SOME (Local_Defs.unfold lthy [rel_O_Gr] (pred_def_of_bnf bnf) RS sym)) unfold; |
|
738 in ((bnf, deads_lives), (unfold', lthy)) end |
|
739 else |
704 else |
740 let |
705 let |
741 val name = Long_Name.base_name C; |
706 val name = Long_Name.base_name C; |
742 fun qualify i = |
707 fun qualify i = |
743 let val namei = name ^ nonzero_string_of_int i; |
708 let val namei = name ^ nonzero_string_of_int i; |