38 |
38 |
39 fun mk_perm_bool ctxt pi th = |
39 fun mk_perm_bool ctxt pi th = |
40 th RS infer_instantiate ctxt [(#1 (dest_Var (Thm.term_of perm_boolI_pi)), pi)] perm_boolI; |
40 th RS infer_instantiate ctxt [(#1 (dest_Var (Thm.term_of perm_boolI_pi)), pi)] perm_boolI; |
41 |
41 |
42 fun mk_perm_bool_simproc names = |
42 fun mk_perm_bool_simproc names = |
43 Simplifier.make_simproc @{context} "perm_bool" |
43 Simplifier.make_simproc \<^context> "perm_bool" |
44 {lhss = [@{term "perm pi x"}], |
44 {lhss = [\<^term>\<open>perm pi x\<close>], |
45 proc = fn _ => fn _ => fn ct => |
45 proc = fn _ => fn _ => fn ct => |
46 (case Thm.term_of ct of |
46 (case Thm.term_of ct of |
47 Const (@{const_name Nominal.perm}, _) $ _ $ t => |
47 Const (\<^const_name>\<open>Nominal.perm\<close>, _) $ _ $ t => |
48 if member (op =) names (the_default "" (try (head_of #> dest_Const #> fst) t)) |
48 if member (op =) names (the_default "" (try (head_of #> dest_Const #> fst) t)) |
49 then SOME perm_bool else NONE |
49 then SOME perm_bool else NONE |
50 | _ => NONE)}; |
50 | _ => NONE)}; |
51 |
51 |
52 fun transp ([] :: _) = [] |
52 fun transp ([] :: _) = [] |
71 | _ => fold (add_binders thy i) ts bs) |
71 | _ => fold (add_binders thy i) ts bs) |
72 | (u, ts) => add_binders thy i u (fold (add_binders thy i) ts bs)) |
72 | (u, ts) => add_binders thy i u (fold (add_binders thy i) ts bs)) |
73 | add_binders thy i (Abs (_, _, t)) bs = add_binders thy (i + 1) t bs |
73 | add_binders thy i (Abs (_, _, t)) bs = add_binders thy (i + 1) t bs |
74 | add_binders thy i _ bs = bs; |
74 | add_binders thy i _ bs = bs; |
75 |
75 |
76 fun split_conj f names (Const (@{const_name HOL.conj}, _) $ p $ q) _ = (case head_of p of |
76 fun split_conj f names (Const (\<^const_name>\<open>HOL.conj\<close>, _) $ p $ q) _ = (case head_of p of |
77 Const (name, _) => |
77 Const (name, _) => |
78 if member (op =) names name then SOME (f p q) else NONE |
78 if member (op =) names name then SOME (f p q) else NONE |
79 | _ => NONE) |
79 | _ => NONE) |
80 | split_conj _ _ _ _ = NONE; |
80 | split_conj _ _ _ _ = NONE; |
81 |
81 |
82 fun strip_all [] t = t |
82 fun strip_all [] t = t |
83 | strip_all (_ :: xs) (Const (@{const_name All}, _) $ Abs (s, T, t)) = strip_all xs t; |
83 | strip_all (_ :: xs) (Const (\<^const_name>\<open>All\<close>, _) $ Abs (s, T, t)) = strip_all xs t; |
84 |
84 |
85 (*********************************************************************) |
85 (*********************************************************************) |
86 (* maps R ... & (ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t)) *) |
86 (* maps R ... & (ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t)) *) |
87 (* or ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t) *) |
87 (* or ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t) *) |
88 (* to R ... & id (ALL z. P z (pi_1 o ... o pi_n o t)) *) |
88 (* to R ... & id (ALL z. P z (pi_1 o ... o pi_n o t)) *) |
89 (* or id (ALL z. P z (pi_1 o ... o pi_n o t)) *) |
89 (* or id (ALL z. P z (pi_1 o ... o pi_n o t)) *) |
90 (* *) |
90 (* *) |
91 (* where "id" protects the subformula from simplification *) |
91 (* where "id" protects the subformula from simplification *) |
92 (*********************************************************************) |
92 (*********************************************************************) |
93 |
93 |
94 fun inst_conj_all names ps pis (Const (@{const_name HOL.conj}, _) $ p $ q) _ = |
94 fun inst_conj_all names ps pis (Const (\<^const_name>\<open>HOL.conj\<close>, _) $ p $ q) _ = |
95 (case head_of p of |
95 (case head_of p of |
96 Const (name, _) => |
96 Const (name, _) => |
97 if member (op =) names name then SOME (HOLogic.mk_conj (p, |
97 if member (op =) names name then SOME (HOLogic.mk_conj (p, |
98 Const (@{const_name Fun.id}, HOLogic.boolT --> HOLogic.boolT) $ |
98 Const (\<^const_name>\<open>Fun.id\<close>, HOLogic.boolT --> HOLogic.boolT) $ |
99 (subst_bounds (pis, strip_all pis q)))) |
99 (subst_bounds (pis, strip_all pis q)))) |
100 else NONE |
100 else NONE |
101 | _ => NONE) |
101 | _ => NONE) |
102 | inst_conj_all names ps pis t u = |
102 | inst_conj_all names ps pis t u = |
103 if member (op aconv) ps (head_of u) then |
103 if member (op aconv) ps (head_of u) then |
104 SOME (Const (@{const_name Fun.id}, HOLogic.boolT --> HOLogic.boolT) $ |
104 SOME (Const (\<^const_name>\<open>Fun.id\<close>, HOLogic.boolT --> HOLogic.boolT) $ |
105 (subst_bounds (pis, strip_all pis t))) |
105 (subst_bounds (pis, strip_all pis t))) |
106 else NONE |
106 else NONE |
107 | inst_conj_all _ _ _ _ _ = NONE; |
107 | inst_conj_all _ _ _ _ _ = NONE; |
108 |
108 |
109 fun inst_conj_all_tac ctxt k = EVERY |
109 fun inst_conj_all_tac ctxt k = EVERY |
197 map (apfst (incr_boundvars 1)) (mk_avoids params avoid), |
197 map (apfst (incr_boundvars 1)) (mk_avoids params avoid), |
198 prems, strip_comb (HOLogic.dest_Trueprop concl)) |
198 prems, strip_comb (HOLogic.dest_Trueprop concl)) |
199 end) (Logic.strip_imp_prems raw_induct' ~~ avoids'); |
199 end) (Logic.strip_imp_prems raw_induct' ~~ avoids'); |
200 |
200 |
201 val atomTs = distinct op = (maps (map snd o #2) prems); |
201 val atomTs = distinct op = (maps (map snd o #2) prems); |
202 val ind_sort = if null atomTs then @{sort type} |
202 val ind_sort = if null atomTs then \<^sort>\<open>type\<close> |
203 else Sign.minimize_sort thy (Sign.certify_sort thy (map (fn T => Sign.intern_class thy |
203 else Sign.minimize_sort thy (Sign.certify_sort thy (map (fn T => Sign.intern_class thy |
204 ("fs_" ^ Long_Name.base_name (fst (dest_Type T)))) atomTs)); |
204 ("fs_" ^ Long_Name.base_name (fst (dest_Type T)))) atomTs)); |
205 val (fs_ctxt_tyname, _) = Name.variant "'n" (Variable.names_of ctxt'); |
205 val (fs_ctxt_tyname, _) = Name.variant "'n" (Variable.names_of ctxt'); |
206 val ([fs_ctxt_name], ctxt'') = Variable.variant_fixes ["z"] ctxt'; |
206 val ([fs_ctxt_name], ctxt'') = Variable.variant_fixes ["z"] ctxt'; |
207 val fsT = TFree (fs_ctxt_tyname, ind_sort); |
207 val fsT = TFree (fs_ctxt_tyname, ind_sort); |
274 val perm_pi_simp = Global_Theory.get_thms thy "perm_pi_simp"; |
274 val perm_pi_simp = Global_Theory.get_thms thy "perm_pi_simp"; |
275 val pt2_atoms = map (fn aT => Global_Theory.get_thm thy |
275 val pt2_atoms = map (fn aT => Global_Theory.get_thm thy |
276 ("pt_" ^ Long_Name.base_name (fst (dest_Type aT)) ^ "2")) atomTs; |
276 ("pt_" ^ Long_Name.base_name (fst (dest_Type aT)) ^ "2")) atomTs; |
277 val eqvt_ss = simpset_of (put_simpset HOL_basic_ss (Proof_Context.init_global thy) |
277 val eqvt_ss = simpset_of (put_simpset HOL_basic_ss (Proof_Context.init_global thy) |
278 addsimps (eqvt_thms @ perm_pi_simp @ pt2_atoms) |
278 addsimps (eqvt_thms @ perm_pi_simp @ pt2_atoms) |
279 addsimprocs [mk_perm_bool_simproc [@{const_name Fun.id}], |
279 addsimprocs [mk_perm_bool_simproc [\<^const_name>\<open>Fun.id\<close>], |
280 NominalPermeq.perm_simproc_app, NominalPermeq.perm_simproc_fun]); |
280 NominalPermeq.perm_simproc_app, NominalPermeq.perm_simproc_fun]); |
281 val fresh_bij = Global_Theory.get_thms thy "fresh_bij"; |
281 val fresh_bij = Global_Theory.get_thms thy "fresh_bij"; |
282 val perm_bij = Global_Theory.get_thms thy "perm_bij"; |
282 val perm_bij = Global_Theory.get_thms thy "perm_bij"; |
283 val fs_atoms = map (fn aT => Global_Theory.get_thm thy |
283 val fs_atoms = map (fn aT => Global_Theory.get_thm thy |
284 ("fs_" ^ Long_Name.base_name (fst (dest_Type aT)) ^ "1")) atomTs; |
284 ("fs_" ^ Long_Name.base_name (fst (dest_Type aT)) ^ "1")) atomTs; |
290 fun obtain_fresh_name ts T (freshs1, freshs2, ctxt) = |
290 fun obtain_fresh_name ts T (freshs1, freshs2, ctxt) = |
291 let |
291 let |
292 (** protect terms to avoid that fresh_prod interferes with **) |
292 (** protect terms to avoid that fresh_prod interferes with **) |
293 (** pairs used in introduction rules of inductive predicate **) |
293 (** pairs used in introduction rules of inductive predicate **) |
294 fun protect t = |
294 fun protect t = |
295 let val T = fastype_of t in Const (@{const_name Fun.id}, T --> T) $ t end; |
295 let val T = fastype_of t in Const (\<^const_name>\<open>Fun.id\<close>, T --> T) $ t end; |
296 val p = foldr1 HOLogic.mk_prod (map protect ts @ freshs1); |
296 val p = foldr1 HOLogic.mk_prod (map protect ts @ freshs1); |
297 val ex = Goal.prove ctxt [] [] (HOLogic.mk_Trueprop |
297 val ex = Goal.prove ctxt [] [] (HOLogic.mk_Trueprop |
298 (HOLogic.exists_const T $ Abs ("x", T, |
298 (HOLogic.exists_const T $ Abs ("x", T, |
299 NominalDatatype.fresh_const T (fastype_of p) $ |
299 NominalDatatype.fresh_const T (fastype_of p) $ |
300 Bound 0 $ p))) |
300 Bound 0 $ p))) |
334 val freshs2' = NominalDatatype.mk_not_sym freshs2; |
334 val freshs2' = NominalDatatype.mk_not_sym freshs2; |
335 val pis' = map NominalDatatype.perm_of_pair (pi_bvars ~~ freshs1); |
335 val pis' = map NominalDatatype.perm_of_pair (pi_bvars ~~ freshs1); |
336 fun concat_perm pi1 pi2 = |
336 fun concat_perm pi1 pi2 = |
337 let val T = fastype_of pi1 |
337 let val T = fastype_of pi1 |
338 in if T = fastype_of pi2 then |
338 in if T = fastype_of pi2 then |
339 Const (@{const_name append}, T --> T --> T) $ pi1 $ pi2 |
339 Const (\<^const_name>\<open>append\<close>, T --> T --> T) $ pi1 $ pi2 |
340 else pi2 |
340 else pi2 |
341 end; |
341 end; |
342 val pis'' = fold (concat_perm #> map) pis' pis; |
342 val pis'' = fold (concat_perm #> map) pis' pis; |
343 val env = Pattern.first_order_match thy (ihypt, Thm.prop_of ihyp) |
343 val env = Pattern.first_order_match thy (ihypt, Thm.prop_of ihyp) |
344 (Vartab.empty, Vartab.empty); |
344 (Vartab.empty, Vartab.empty); |
676 |
676 |
677 |
677 |
678 (* outer syntax *) |
678 (* outer syntax *) |
679 |
679 |
680 val _ = |
680 val _ = |
681 Outer_Syntax.local_theory_to_proof @{command_keyword nominal_inductive} |
681 Outer_Syntax.local_theory_to_proof \<^command_keyword>\<open>nominal_inductive\<close> |
682 "prove equivariance and strong induction theorem for inductive predicate involving nominal datatypes" |
682 "prove equivariance and strong induction theorem for inductive predicate involving nominal datatypes" |
683 (Parse.name -- Scan.optional (@{keyword "avoids"} |-- Parse.and_list1 (Parse.name -- |
683 (Parse.name -- Scan.optional (\<^keyword>\<open>avoids\<close> |-- Parse.and_list1 (Parse.name -- |
684 (@{keyword ":"} |-- Scan.repeat1 Parse.name))) [] >> (fn (name, avoids) => |
684 (\<^keyword>\<open>:\<close> |-- Scan.repeat1 Parse.name))) [] >> (fn (name, avoids) => |
685 prove_strong_ind name avoids)); |
685 prove_strong_ind name avoids)); |
686 |
686 |
687 val _ = |
687 val _ = |
688 Outer_Syntax.local_theory @{command_keyword equivariance} |
688 Outer_Syntax.local_theory \<^command_keyword>\<open>equivariance\<close> |
689 "prove equivariance for inductive predicate involving nominal datatypes" |
689 "prove equivariance for inductive predicate involving nominal datatypes" |
690 (Parse.name -- Scan.optional (@{keyword "["} |-- Parse.list1 Parse.name --| @{keyword "]"}) [] >> |
690 (Parse.name -- Scan.optional (\<^keyword>\<open>[\<close> |-- Parse.list1 Parse.name --| \<^keyword>\<open>]\<close>) [] >> |
691 (fn (name, atoms) => prove_eqvt name atoms)); |
691 (fn (name, atoms) => prove_eqvt name atoms)); |
692 |
692 |
693 end |
693 end |