src/HOL/Nominal/nominal_inductive.ML
changeset 69597 ff784d5a5bfb
parent 67405 e9ab4ad7bd15
child 70326 aa7c49651f4e
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
    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