src/HOL/Nominal/nominal_thmdecls.ML
changeset 30986 047fa04a9fe8
parent 30528 7173bf123335
child 30991 c814a34f687e
equal deleted inserted replaced
30983:e54777ab68bd 30986:047fa04a9fe8
     1 (* Authors: Julien Narboux and Christian Urban
     1 (* Authors: Julien Narboux and Christian Urban
     2 
     2 
     3    This file introduces the infrastructure for the lemma
     3    This file introduces the infrastructure for the lemma
     4    declaration "eqvts" "bijs" and "freshs".
     4    collection "eqvts".
     5 
     5 
     6    By attaching [eqvt] [bij] or [fresh] to a lemma, the lemma gets stored
     6    By attaching [eqvt], [eqvt_force] to a lemma, the lemma gets 
     7    in a data-slot in the context. Possible modifiers
     7    stored in a data-slot in the context. Possible modifiers
     8    are [attribute add] and [attribute del] for adding and deleting,
     8    are [... add] and [... del] for adding and deleting, respectively 
     9    respectively the lemma from the data-slot.
     9    the lemma from the data-slot.
    10 *)
    10 *)
    11 
    11 
    12 signature NOMINAL_THMDECLS =
    12 signature NOMINAL_THMDECLS =
    13 sig
    13 sig
    14   val eqvt_add: attribute
    14   val eqvt_add: attribute
    15   val eqvt_del: attribute
    15   val eqvt_del: attribute
    16   val eqvt_force_add: attribute
    16   val eqvt_force_add: attribute
    17   val eqvt_force_del: attribute
    17   val eqvt_force_del: attribute
    18   val setup: theory -> theory
    18   val setup: theory -> theory
    19   val get_eqvt_thms: Proof.context -> thm list
    19   val get_eqvt_thms: Proof.context -> thm list
    20   val get_fresh_thms: Proof.context -> thm list
       
    21   val get_bij_thms: Proof.context -> thm list
       
    22 
       
    23 
    20 
    24   val NOMINAL_EQVT_DEBUG : bool ref
    21   val NOMINAL_EQVT_DEBUG : bool ref
    25 end;
    22 end;
    26 
    23 
    27 structure NominalThmDecls: NOMINAL_THMDECLS =
    24 structure NominalThmDecls: NOMINAL_THMDECLS =
    28 struct
    25 struct
    29 
    26 
    30 structure Data = GenericDataFun
    27 structure Data = GenericDataFun
    31 (
    28 (
    32   type T = {eqvts:thm list, freshs:thm list, bijs:thm list};
    29   type T = thm list
    33   val empty = ({eqvts=[], freshs=[], bijs=[]}:T);
    30   val empty = []:T
    34   val extend = I;
    31   val extend = I
    35   fun merge _ (r1:T,r2:T) = {eqvts  = Thm.merge_thms (#eqvts r1, #eqvts r2),
    32   fun merge _ (r1:T, r2:T) = Thm.merge_thms (r1, r2)
    36                              freshs = Thm.merge_thms (#freshs r1, #freshs r2),
    33 )
    37                              bijs   = Thm.merge_thms (#bijs r1, #bijs r2)}
       
    38 );
       
    39 
    34 
    40 (* Exception for when a theorem does not conform with form of an equivariance lemma. *)
    35 (* Exception for when a theorem does not conform with form of an equivariance lemma. *)
    41 (* There are two forms: one is an implication (for relations) and the other is an    *)
    36 (* There are two forms: one is an implication (for relations) and the other is an    *)
    42 (* equality (for functions). In the implication-case, say P ==> Q, Q must be equal   *)
    37 (* equality (for functions). In the implication-case, say P ==> Q, Q must be equal   *)
    43 (* to P except that every free variable of Q, say x, is replaced by pi o x. In the   *)
    38 (* to P except that every free variable of Q, say x, is replaced by pi o x. In the   *)
    44 (* equality case, say lhs = rhs, the lhs must be of the form pi o t and the rhs must *)
    39 (* equality case, say lhs = rhs, the lhs must be of the form pi o t and the rhs must *)
    45 (* be equal to t except that every free variable, say x, is replaced by pi o x. In   *)
    40 (* be equal to t except that every free variable, say x, is replaced by pi o x. In   *)
    46 (* the implicational case it is also checked that the variables and permutation fit  *)
    41 (* the implicational case it is also checked that the variables and permutation fit  *)
    47 (* together, i.e. are of the right "pt_class", so that a stronger version of the     *)
    42 (* together, i.e. are of the right "pt_class", so that a stronger version of the     *)
    48 (* equality-lemma can be derived. *)
    43 (* equality-lemma can be derived. *)
    49 exception EQVT_FORM of string;
    44 exception EQVT_FORM of string
    50 
       
    51 val get_eqvt_thms = Context.Proof #> Data.get #> #eqvts;
       
    52 val get_fresh_thms = Context.Proof #> Data.get #> #freshs;
       
    53 val get_bij_thms = Context.Proof #> Data.get #> #bijs;
       
    54 
    45 
    55 (* FIXME: should be a function in a library *)
    46 (* FIXME: should be a function in a library *)
    56 fun mk_permT T = HOLogic.listT (HOLogic.mk_prodT (T, T));
    47 fun mk_permT T = HOLogic.listT (HOLogic.mk_prodT (T, T))
    57 
    48 
    58 val NOMINAL_EQVT_DEBUG = ref false;
    49 val NOMINAL_EQVT_DEBUG = ref false
    59 
    50 
    60 fun tactic (msg,tac) =
    51 fun tactic (msg, tac) =
    61     if !NOMINAL_EQVT_DEBUG
    52   if !NOMINAL_EQVT_DEBUG
    62     then tac THEN print_tac ("after "^msg)
    53   then tac THEN' (K (print_tac ("after " ^ msg)))
    63     else tac
    54   else tac
    64 
    55 
    65 fun tactic_eqvt ctx orig_thm pi pi' =
    56 fun tactic_eqvt ctx orig_thm pi pi' =
    66     let
    57 let
    67         val mypi = Thm.cterm_of ctx pi
    58   val mypi = Thm.cterm_of ctx pi
    68         val T = fastype_of pi'
    59   val T = fastype_of pi'
    69         val mypifree = Thm.cterm_of ctx (Const ("List.rev", T --> T) $ pi')
    60   val mypifree = Thm.cterm_of ctx (Const (@{const_name "List.rev"}, T --> T) $ pi')
    70         val perm_pi_simp = PureThy.get_thms ctx "perm_pi_simp"
    61   val perm_pi_simp = PureThy.get_thms ctx "perm_pi_simp"
    71     in
    62 in
    72         EVERY [tactic ("iffI applied",rtac iffI 1),
    63   EVERY1 [tactic ("iffI applied",rtac @{thm iffI}),
    73 	       tactic ("remove pi with perm_boolE", (dtac @{thm perm_boolE} 1)),
    64 	  tactic ("remove pi with perm_boolE", dtac @{thm perm_boolE}),
    74                tactic ("solve with orig_thm", (etac orig_thm 1)),
    65           tactic ("solve with orig_thm", etac orig_thm),
    75                tactic ("applies orig_thm instantiated with rev pi",
    66           tactic ("applies orig_thm instantiated with rev pi",
    76                           dtac (Drule.cterm_instantiate [(mypi,mypifree)] orig_thm) 1),
    67                      dtac (Drule.cterm_instantiate [(mypi,mypifree)] orig_thm)),
    77 	       tactic ("getting rid of the pi on the right",
    68 	  tactic ("getting rid of the pi on the right", rtac @{thm perm_boolI}),
    78                           (rtac @{thm perm_boolI} 1)),
    69           tactic ("getting rid of all remaining perms",
    79                tactic ("getting rid of all remaining perms",
    70                      full_simp_tac (HOL_basic_ss addsimps perm_pi_simp))]
    80                           full_simp_tac (HOL_basic_ss addsimps perm_pi_simp) 1)]
    71 end;
    81     end;
       
    82 
    72 
    83 fun get_derived_thm ctxt hyp concl orig_thm pi typi =
    73 fun get_derived_thm ctxt hyp concl orig_thm pi typi =
    84   let
    74   let
    85     val thy = ProofContext.theory_of ctxt;
    75     val thy = ProofContext.theory_of ctxt;
    86     val pi' = Var (pi, typi);
    76     val pi' = Var (pi, typi);
    87     val lhs = Const ("Nominal.perm", typi --> HOLogic.boolT --> HOLogic.boolT) $ pi' $ hyp;
    77     val lhs = Const (@{const_name "Nominal.perm"}, typi --> HOLogic.boolT --> HOLogic.boolT) $ pi' $ hyp;
    88     val ([goal_term, pi''], ctxt') = Variable.import_terms false
    78     val ([goal_term, pi''], ctxt') = Variable.import_terms false
    89       [HOLogic.mk_Trueprop (HOLogic.mk_eq (lhs, concl)), pi'] ctxt
    79       [HOLogic.mk_Trueprop (HOLogic.mk_eq (lhs, concl)), pi'] ctxt
    90     val _ = Display.print_cterm (cterm_of thy goal_term)
    80     val _ = Display.print_cterm (cterm_of thy goal_term)
    91   in
    81   in
    92     Goal.prove ctxt' [] [] goal_term
    82     Goal.prove ctxt' [] [] goal_term
    93       (fn _ => tactic_eqvt thy orig_thm pi' pi'') |>
    83       (fn _ => tactic_eqvt thy orig_thm pi' pi'') |>
    94     singleton (ProofContext.export ctxt' ctxt)
    84     singleton (ProofContext.export ctxt' ctxt)
    95   end
    85   end
    96 
    86 
    97 (* replaces every variable x in t with pi o x *)
    87 (* replaces every variable x in t with pi o x *)
    98 fun apply_pi trm (pi,typi) =
    88 fun apply_pi trm (pi, typi) =
    99   let
    89 let
   100     fun only_vars t =
    90   fun only_vars t =
   101        (case t of
    91      (case t of
   102           Var (n,ty) => (Const ("Nominal.perm",typi --> ty --> ty) $ (Var (pi,typi)) $ (Var (n,ty)))
    92          Var (n, ty) => 
   103         | _ => t)
    93            (Const (@{const_name "Nominal.perm"}, typi --> ty --> ty) 
   104   in
    94                 $ (Var (pi, typi)) $ (Var (n, ty)))
   105      map_aterms only_vars trm
    95        | _ => t)
   106   end;
    96 in
       
    97     map_aterms only_vars trm
       
    98 end;
   107 
    99 
   108 (* returns *the* pi which is in front of all variables, provided there *)
   100 (* returns *the* pi which is in front of all variables, provided there *)
   109 (* exists such a pi; otherwise raises EQVT_FORM                        *)
   101 (* exists such a pi; otherwise raises EQVT_FORM                        *)
   110 fun get_pi t thy =
   102 fun get_pi t thy =
   111   let fun get_pi_aux s =
   103   let fun get_pi_aux s =
   112         (case s of
   104         (case s of
   113           (Const ("Nominal.perm",typrm) $
   105           (Const (@{const_name "Nominal.perm"} ,typrm) $
   114              (Var (pi,typi as Type("List.list",[Type ("*",[Type (tyatm,[]),_])]))) $
   106              (Var (pi,typi as Type("List.list", [Type ("*", [Type (tyatm,[]),_])]))) $
   115                (Var (n,ty))) =>
   107                (Var (n,ty))) =>
   116              let
   108              let
   117                 (* FIXME: this should be an operation the library *)
   109                 (* FIXME: this should be an operation the library *)
   118                 val class_name = (Long_Name.map_base_name (fn s => "pt_"^s) tyatm)
   110                 val class_name = (Long_Name.map_base_name (fn s => "pt_"^s) tyatm)
   119              in
   111              in
   128   in
   120   in
   129     (* collect first all pi's in front of variables in t and then use distinct *)
   121     (* collect first all pi's in front of variables in t and then use distinct *)
   130     (* to ensure that all pi's must have been the same, i.e. distinct returns  *)
   122     (* to ensure that all pi's must have been the same, i.e. distinct returns  *)
   131     (* a singleton-list  *)
   123     (* a singleton-list  *)
   132     (case (distinct (op =) (get_pi_aux t)) of
   124     (case (distinct (op =) (get_pi_aux t)) of
   133       [(pi,typi)] => (pi,typi)
   125       [(pi,typi)] => (pi, typi)
   134     | _ => raise EQVT_FORM "All permutation should be the same")
   126     | _ => raise EQVT_FORM "All permutation should be the same")
   135   end;
   127   end;
   136 
   128 
   137 (* Either adds a theorem (orig_thm) to or deletes one from the equivariance *)
   129 (* Either adds a theorem (orig_thm) to or deletes one from the equivariance *)
   138 (* lemma list depending on flag. To be added the lemma has to satisfy a     *)
   130 (* lemma list depending on flag. To be added the lemma has to satisfy a     *)
   153                 [orig_thm,
   145                 [orig_thm,
   154                  get_derived_thm (Context.proof_of context) hyp concl orig_thm pi typi])
   146                  get_derived_thm (Context.proof_of context) hyp concl orig_thm pi typi])
   155              else raise EQVT_FORM "Type Implication"
   147              else raise EQVT_FORM "Type Implication"
   156           end
   148           end
   157        (* case: eqvt-lemma is of the equational form *)
   149        (* case: eqvt-lemma is of the equational form *)
   158       | (Const ("Trueprop", _) $ (Const ("op =", _) $
   150       | (Const (@{const_name "Trueprop"}, _) $ (Const (@{const_name "op ="}, _) $
   159             (Const ("Nominal.perm",typrm) $ Var (pi,typi) $ lhs) $ rhs)) =>
   151             (Const (@{const_name "Nominal.perm"},typrm) $ Var (pi,typi) $ lhs) $ rhs)) =>
   160            (if (apply_pi lhs (pi,typi)) = rhs
   152            (if (apply_pi lhs (pi,typi)) = rhs
   161                then [orig_thm]
   153                then [orig_thm]
   162                else raise EQVT_FORM "Type Equality")
   154                else raise EQVT_FORM "Type Equality")
   163       | _ => raise EQVT_FORM "Type unknown")
   155       | _ => raise EQVT_FORM "Type unknown")
   164   in
   156   in
   165       fold (fn thm => Data.map (flag thm)) thms_to_be_added context
   157       fold (fn thm => Data.map (flag thm)) thms_to_be_added context
   166   end
   158   end
   167   handle EQVT_FORM s =>
   159   handle EQVT_FORM s =>
   168       error (Display.string_of_thm orig_thm ^ " does not comply with the form of an equivariance lemma ("^s^").")
   160       error (Display.string_of_thm orig_thm ^ 
       
   161                " does not comply with the form of an equivariance lemma (" ^ s ^").")
   169 
   162 
   170 (* in cases of bij- and freshness, we just add the lemmas to the *)
       
   171 (* data-slot *)
       
   172 
   163 
   173 fun eqvt_map f (r:Data.T)  = {eqvts = f (#eqvts r), freshs = #freshs r, bijs = #bijs r};
   164 fun eqvt_map f (r:Data.T)  = f r;
   174 fun fresh_map f (r:Data.T) = {eqvts = #eqvts r, freshs = f (#freshs r), bijs = #bijs r};
       
   175 fun bij_map f (r:Data.T)   = {eqvts = #eqvts r, freshs = #freshs r, bijs = f (#bijs r)};
       
   176 
   165 
   177 val eqvt_add = Thm.declaration_attribute (eqvt_add_del_aux (eqvt_map o Thm.add_thm));
   166 val eqvt_add = Thm.declaration_attribute (eqvt_add_del_aux (eqvt_map o Thm.add_thm));
   178 val eqvt_del = Thm.declaration_attribute (eqvt_add_del_aux (eqvt_map o Thm.del_thm));
   167 val eqvt_del = Thm.declaration_attribute (eqvt_add_del_aux (eqvt_map o Thm.del_thm));
   179 
   168 
   180 val eqvt_force_add  = Thm.declaration_attribute (Data.map o eqvt_map o Thm.add_thm);
   169 val eqvt_force_add  = Thm.declaration_attribute (Data.map o eqvt_map o Thm.add_thm);
   181 val eqvt_force_del  = Thm.declaration_attribute (Data.map o eqvt_map o Thm.del_thm);
   170 val eqvt_force_del  = Thm.declaration_attribute (Data.map o eqvt_map o Thm.del_thm);
   182 val bij_add   = Thm.declaration_attribute (Data.map o bij_map o Thm.add_thm);
   171 
   183 val bij_del   = Thm.declaration_attribute (Data.map o bij_map o Thm.del_thm);
   172 val get_eqvt_thms = Context.Proof #> Data.get;
   184 val fresh_add = Thm.declaration_attribute (Data.map o fresh_map o Thm.add_thm);
   173 
   185 val fresh_del = Thm.declaration_attribute (Data.map o fresh_map o Thm.del_thm);
   174 val setup =
       
   175     Attrib.setup @{binding eqvt} (Attrib.add_del eqvt_add eqvt_del) 
       
   176      "equivariance theorem declaration" 
       
   177  #> Attrib.setup @{binding eqvt_force} (Attrib.add_del eqvt_force_add eqvt_force_del)
       
   178      "equivariance theorem declaration (without checking the form of the lemma)" 
       
   179  #> PureThy.add_thms_dynamic (Binding.name "eqvts", Data.get) 
   186 
   180 
   187 
   181 
   188 
       
   189 val setup =
       
   190   Attrib.setup @{binding eqvt} (Attrib.add_del eqvt_add eqvt_del)
       
   191     "equivariance theorem declaration" #>
       
   192   Attrib.setup @{binding eqvt_force} (Attrib.add_del eqvt_force_add eqvt_force_del)
       
   193     "equivariance theorem declaration (without checking the form of the lemma)" #>
       
   194   Attrib.setup @{binding fresh} (Attrib.add_del fresh_add fresh_del)
       
   195     "freshness theorem declaration" #>
       
   196   Attrib.setup @{binding "bij"} (Attrib.add_del bij_add bij_del)
       
   197     "bijection theorem declaration" #>
       
   198   PureThy.add_thms_dynamic (Binding.name "eqvts", #eqvts o Data.get) #>
       
   199   PureThy.add_thms_dynamic (Binding.name "freshs", #freshs o Data.get) #>
       
   200   PureThy.add_thms_dynamic (Binding.name "bijs", #bijs o Data.get);
       
   201 
       
   202 end;
   182 end;