src/HOL/Tools/transfer.ML
author huffman
Fri Mar 30 12:32:35 2012 +0200 (2012-03-30)
changeset 47220 52426c62b5d0
parent 46497 89ccf66aa73d
permissions -rw-r--r--
replace lemmas eval_nat_numeral with a simpler reformulation
     1 (*  Title:      HOL/Tools/transfer.ML
     2     Author:     Amine Chaieb, University of Cambridge, 2009
     3                 Jeremy Avigad, Carnegie Mellon University
     4                 Florian Haftmann, TU Muenchen
     5 
     6 Simple transfer principle on theorems.
     7 *)
     8 
     9 signature TRANSFER =
    10 sig
    11   datatype selection = Direction of term * term | Hints of string list | Prop
    12   val transfer: Context.generic -> selection -> string list -> thm -> thm list
    13   type entry
    14   val add: thm -> bool -> entry -> Context.generic -> Context.generic
    15   val del: thm -> entry -> Context.generic -> Context.generic
    16   val drop: thm -> Context.generic -> Context.generic
    17   val setup: theory -> theory
    18 end;
    19 
    20 structure Transfer : TRANSFER =
    21 struct
    22 
    23 (* data administration *)
    24 
    25 val direction_of = Thm.dest_binop o Thm.dest_arg o cprop_of;
    26 
    27 val transfer_morphism_key = Drule.strip_imp_concl (Thm.cprop_of @{thm transfer_morphismI});
    28 
    29 fun check_morphism_key ctxt key =
    30   let
    31     val _ = Thm.match (transfer_morphism_key, Thm.cprop_of key)
    32       handle Pattern.MATCH => error ("Transfer: expected theorem of the form "
    33         ^ quote (Syntax.string_of_term ctxt (Thm.term_of transfer_morphism_key)));
    34   in direction_of key end;
    35 
    36 type entry = { inj : thm list, embed : thm list, return : thm list, cong : thm list,
    37   hints : string list };
    38 
    39 val empty_entry = { inj = [], embed = [], return = [], cong = [], hints = [] };
    40 fun merge_entry ({ inj = inj1, embed = embed1, return = return1, cong = cong1, hints = hints1 } : entry,
    41   { inj = inj2, embed = embed2, return = return2, cong = cong2, hints = hints2 } : entry) =
    42     { inj = merge Thm.eq_thm (inj1, inj2), embed = merge Thm.eq_thm (embed1, embed2),
    43       return = merge Thm.eq_thm (return1, return2), cong = merge Thm.eq_thm (cong1, cong2),
    44       hints = merge (op =) (hints1, hints2) };
    45 
    46 structure Data = Generic_Data
    47 (
    48   type T = (thm * entry) list;
    49   val empty = [];
    50   val extend = I;
    51   val merge = AList.join Thm.eq_thm (K merge_entry);
    52 );
    53 
    54 
    55 (* data lookup *)
    56 
    57 fun transfer_rules_of ({ inj, embed, return, cong, ... } : entry) =
    58   (inj, embed, return, cong);
    59 
    60 fun get_by_direction context (a, D) =
    61   let
    62     val ctxt = Context.proof_of context;
    63     val certify = Thm.cterm_of (Context.theory_of context);
    64     val a0 = certify a;
    65     val D0 = certify D;
    66     fun eq_direction ((a, D), thm') =
    67       let
    68         val (a', D') = direction_of thm';
    69       in a aconvc a' andalso D aconvc D' end;
    70   in case AList.lookup eq_direction (Data.get context) (a0, D0) of
    71       SOME e => ((a0, D0), transfer_rules_of e)
    72     | NONE => error ("Transfer: no such instance: ("
    73         ^ Syntax.string_of_term ctxt a ^ ", " ^ Syntax.string_of_term ctxt D ^ ")")
    74   end;
    75 
    76 fun get_by_hints context hints =
    77   let
    78     val insts = map_filter (fn (k, e) => if exists (member (op =) (#hints e)) hints
    79       then SOME (direction_of k, transfer_rules_of e) else NONE) (Data.get context);
    80     val _ = if null insts then error ("Transfer: no such labels: " ^ commas_quote hints) else ();
    81   in insts end;
    82 
    83 fun splits P [] = []
    84   | splits P (xs as (x :: _)) =
    85       let
    86         val (pss, qss) = List.partition (P x) xs;
    87       in if null pss then [qss] else if null qss then [pss] else pss :: splits P qss end;
    88 
    89 fun get_by_prop context t =
    90   let
    91     val tys = map snd (Term.add_vars t []);
    92     val _ = if null tys then error "Transfer: unable to guess instance" else ();
    93     val tyss = splits (curry Type.could_unify) tys;
    94     val get_ty = typ_of o ctyp_of_term o fst o direction_of;
    95     val insts = map_filter (fn tys => get_first (fn (k, e) =>
    96       if Type.could_unify (hd tys, range_type (get_ty k))
    97       then SOME (direction_of k, transfer_rules_of e)
    98       else NONE) (Data.get context)) tyss;
    99     val _ = if null insts then
   100       error "Transfer: no instances, provide direction or hints explicitly" else ();
   101   in insts end;
   102 
   103 
   104 (* applying transfer data *)
   105 
   106 fun transfer_thm ((raw_a, raw_D), (inj, embed, return, cong)) leave ctxt1 thm =
   107   let
   108     (* identify morphism function *)
   109     val ([a, D], ctxt2) = ctxt1
   110       |> Variable.import true (map Drule.mk_term [raw_a, raw_D])
   111       |>> map Drule.dest_term o snd;
   112     val transform = Thm.apply @{cterm "Trueprop"} o Thm.apply D;
   113     val T = Thm.typ_of (Thm.ctyp_of_term a);
   114     val (aT, bT) = (Term.range_type T, Term.domain_type T);
   115     
   116     (* determine variables to transfer *)
   117     val ctxt3 = ctxt2
   118       |> Variable.declare_thm thm
   119       |> Variable.declare_term (term_of a)
   120       |> Variable.declare_term (term_of D);
   121     val certify = Thm.cterm_of (Proof_Context.theory_of ctxt3);
   122     val vars = filter (fn ((v, _), T) => Type.could_unify (T, aT) andalso
   123       not (member (op =) leave v)) (Term.add_vars (Thm.prop_of thm) []);
   124     val c_vars = map (certify o Var) vars;
   125     val (vs', ctxt4) = Variable.variant_fixes (map (fst o fst) vars) ctxt3;
   126     val c_vars' = map (certify o (fn v => Free (v, bT))) vs';
   127     val c_exprs' = map (Thm.apply a) c_vars';
   128 
   129     (* transfer *)
   130     val (hyps, ctxt5) = ctxt4
   131       |> Assumption.add_assumes (map transform c_vars');
   132     val simpset =
   133       Simplifier.context ctxt5 HOL_ss addsimps (inj @ embed @ return)
   134       |> fold Simplifier.add_cong cong;
   135     val thm' = thm
   136       |> Drule.cterm_instantiate (c_vars ~~ c_exprs')
   137       |> fold_rev Thm.implies_intr (map cprop_of hyps)
   138       |> Simplifier.asm_full_simplify simpset
   139   in singleton (Variable.export ctxt5 ctxt1) thm' end;
   140 
   141 fun transfer_thm_multiple insts leave ctxt thm =
   142   map (fn inst => transfer_thm inst leave ctxt thm) insts;
   143 
   144 datatype selection = Direction of term * term | Hints of string list | Prop;
   145 
   146 fun insts_for context thm (Direction direction) = [get_by_direction context direction]
   147   | insts_for context thm (Hints hints) = get_by_hints context hints
   148   | insts_for context thm Prop = get_by_prop context (Thm.prop_of thm);
   149 
   150 fun transfer context selection leave thm =
   151   transfer_thm_multiple (insts_for context thm selection) leave (Context.proof_of context) thm;
   152 
   153 
   154 (* maintaining transfer data *)
   155 
   156 fun extend_entry ctxt (a, D) guess
   157     { inj = inj1, embed = embed1, return = return1, cong = cong1, hints = hints1 }
   158     { inj = inj2, embed = embed2, return = return2, cong = cong2, hints = hints2 } =
   159   let
   160     fun add_del eq del add = union eq add #> subtract eq del;
   161     val guessed = if guess
   162       then map (fn thm => transfer_thm
   163         ((a, D), (if null inj1 then inj2 else inj1, [], [], cong1)) [] ctxt thm RS sym) embed1
   164       else [];
   165   in
   166     { inj = union Thm.eq_thm inj1 inj2, embed = union Thm.eq_thm embed1 embed2,
   167       return = union Thm.eq_thm guessed (union Thm.eq_thm return1 return2),
   168       cong = union Thm.eq_thm cong1 cong2, hints = union (op =) hints1 hints2 }
   169   end;
   170 
   171 fun diminish_entry 
   172     { inj = inj0, embed = embed0, return = return0, cong = cong0, hints = hints0 }
   173     { inj = inj2, embed = embed2, return = return2, cong = cong2, hints = hints2 } =
   174   { inj = subtract Thm.eq_thm inj0 inj2, embed = subtract Thm.eq_thm embed0 embed2,
   175     return = subtract Thm.eq_thm return0 return2, cong = subtract Thm.eq_thm cong0 cong2,
   176     hints = subtract (op =) hints0 hints2 };
   177 
   178 fun add key guess entry context =
   179   let
   180     val ctxt = Context.proof_of context;
   181     val a_D = check_morphism_key ctxt key;
   182   in
   183     context
   184     |> Data.map (AList.map_default Thm.eq_thm
   185          (key, empty_entry) (extend_entry ctxt a_D guess entry))
   186   end;
   187 
   188 fun del key entry = Data.map (AList.map_entry Thm.eq_thm key (diminish_entry entry));
   189 
   190 fun drop key = Data.map (AList.delete Thm.eq_thm key);
   191 
   192 
   193 (* syntax *)
   194 
   195 local
   196 
   197 fun these scan = Scan.optional scan [];
   198 fun these_pair scan = Scan.optional scan ([], []);
   199 
   200 fun keyword k = Scan.lift (Args.$$$ k) >> K ();
   201 fun keyword_colon k = Scan.lift (Args.$$$ k -- Args.colon) >> K ();
   202 
   203 val addN = "add";
   204 val delN = "del";
   205 val keyN = "key";
   206 val modeN = "mode";
   207 val automaticN = "automatic";
   208 val manualN = "manual";
   209 val injN = "inj";
   210 val embedN = "embed";
   211 val returnN = "return";
   212 val congN = "cong";
   213 val labelsN = "labels";
   214 
   215 val leavingN = "leaving";
   216 val directionN = "direction";
   217 
   218 val any_keyword = keyword_colon addN || keyword_colon delN || keyword_colon keyN
   219   || keyword_colon modeN || keyword_colon injN || keyword_colon embedN || keyword_colon returnN
   220   || keyword_colon congN || keyword_colon labelsN
   221   || keyword_colon leavingN || keyword_colon directionN;
   222 
   223 val thms = Scan.repeat (Scan.unless any_keyword Attrib.multi_thm) >> flat;
   224 val names = Scan.repeat (Scan.unless any_keyword (Scan.lift Args.name))
   225 
   226 val mode = keyword_colon modeN |-- ((Scan.lift (Args.$$$ manualN) >> K false)
   227   || (Scan.lift (Args.$$$ automaticN) >> K true));
   228 val inj = (keyword_colon injN |-- thms) -- these (keyword_colon delN |-- thms);
   229 val embed = (keyword_colon embedN |-- thms) -- these (keyword_colon delN |-- thms);
   230 val return = (keyword_colon returnN |-- thms) -- these (keyword_colon delN |-- thms);
   231 val cong = (keyword_colon congN |-- thms) -- these (keyword_colon delN |-- thms);
   232 val labels = (keyword_colon labelsN |-- names) -- these (keyword_colon delN |-- names);
   233 
   234 val entry_pair = these_pair inj -- these_pair embed
   235   -- these_pair return -- these_pair cong -- these_pair labels
   236   >> (fn (((((inja, injd), (embeda, embedd)), (returna, returnd)), (conga, congd)),
   237        (hintsa, hintsd)) =>
   238       ({ inj = inja, embed = embeda, return = returna, cong = conga, hints = hintsa },
   239         { inj = injd, embed = embedd, return = returnd, cong = congd, hints = hintsd }));
   240 
   241 val selection = (keyword_colon directionN |-- (Args.term -- Args.term) >> Direction)
   242   || these names >> (fn hints => if null hints then Prop else Hints hints);
   243 
   244 in
   245 
   246 val transfer_attribute = keyword delN >> K (Thm.declaration_attribute drop)
   247   || keyword addN |-- Scan.optional mode true -- entry_pair
   248     >> (fn (guess, (entry_add, entry_del)) => Thm.declaration_attribute
   249       (fn thm => add thm guess entry_add #> del thm entry_del))
   250   || keyword_colon keyN |-- Attrib.thm
   251     >> (fn key => Thm.declaration_attribute
   252       (fn thm => add key false
   253         { inj = [], embed = [], return = [thm], cong = [], hints = [] }));
   254 
   255 val transferred_attribute = selection -- these (keyword_colon leavingN |-- names)
   256   >> (fn (selection, leave) => Thm.rule_attribute (fn context =>
   257       Conjunction.intr_balanced o transfer context selection leave));
   258 
   259 end;
   260 
   261 
   262 (* theory setup *)
   263 
   264 val setup =
   265   Attrib.setup @{binding transfer} transfer_attribute
   266     "Installs transfer data" #>
   267   Attrib.setup @{binding transferred} transferred_attribute
   268     "Transfers theorems";
   269 
   270 end;