src/HOL/Tools/transfer.ML
author haftmann
Tue Oct 20 16:13:01 2009 +0200 (2009-10-20)
changeset 33037 b22e44496dc2
parent 32813 dac196e23093
child 33038 8f9594c31de4
permissions -rw-r--r--
replaced old_style infixes eq_set, subset, union, inter and variants by generic versions
haftmann@32557
     1
(*  Author:     Amine Chaieb, University of Cambridge, 2009
wenzelm@32813
     2
    Author:     Jeremy Avigad, Carnegie Mellon University
huffman@31706
     3
*)
huffman@31706
     4
haftmann@32557
     5
signature TRANSFER =
huffman@31706
     6
sig
huffman@31706
     7
  type data
huffman@31706
     8
  type entry
huffman@31706
     9
  val get: Proof.context -> data
huffman@31706
    10
  val del: attribute
huffman@31706
    11
  val setup: theory -> theory
huffman@31706
    12
end;
huffman@31706
    13
haftmann@32557
    14
structure Transfer : TRANSFER =
huffman@31706
    15
struct
haftmann@32557
    16
haftmann@32557
    17
type entry = {inj : thm list, emb : thm list, ret : thm list, cong : thm list,
wenzelm@32813
    18
  guess : bool, hints : string list};
huffman@31706
    19
type data = simpset * (thm * entry) list;
huffman@31706
    20
huffman@31706
    21
structure Data = GenericDataFun
huffman@31706
    22
(
huffman@31706
    23
  type T = data;
huffman@31706
    24
  val empty = (HOL_ss, []);
huffman@31706
    25
  val extend  = I;
haftmann@32557
    26
  fun merge _ ((ss1, e1), (ss2, e2)) =
wenzelm@32813
    27
    (merge_ss (ss1, ss2), AList.merge Thm.eq_thm (K true) (e1, e2));
huffman@31706
    28
);
huffman@31706
    29
huffman@31706
    30
val get = Data.get o Context.Proof;
huffman@31706
    31
wenzelm@32813
    32
fun del_data key = apsnd (remove (eq_fst Thm.eq_thm) (key, []));
huffman@31706
    33
huffman@31706
    34
val del = Thm.declaration_attribute (Data.map o del_data);
wenzelm@32813
    35
val add_ss = Thm.declaration_attribute
huffman@31706
    36
   (fn th => Data.map (fn (ss,data) => (ss addsimps [th], data)));
huffman@31706
    37
wenzelm@32813
    38
val del_ss = Thm.declaration_attribute
huffman@31706
    39
   (fn th => Data.map (fn (ss,data) => (ss delsimps [th], data)));
huffman@31706
    40
huffman@31706
    41
val transM_pat = (Thm.dest_arg1 o Thm.dest_arg o cprop_of) @{thm TransferMorphism_def};
huffman@31706
    42
huffman@31706
    43
fun merge_update eq m (k,v) [] = [(k,v)]
wenzelm@32813
    44
  | merge_update eq m (k,v) ((k',v')::al) =
huffman@31706
    45
           if eq (k,k') then (k',m (v,v')):: al else (k',v') :: merge_update eq m (k,v) al
huffman@31706
    46
wenzelm@32813
    47
fun simpset_of_entry injonly {inj = inj, emb = emb, ret = ret, cong = cg, guess = g, hints = hints} =
huffman@31706
    48
 HOL_ss addsimps inj addsimps (if injonly then [] else emb@ret) addcongs cg;
huffman@31706
    49
wenzelm@32813
    50
fun basic_transfer_rule injonly a0 D0 e leave ctxt0 th =
wenzelm@32813
    51
 let
wenzelm@31794
    52
  val ([a,D], ctxt) = apfst (map Drule.dest_term o snd) (Variable.import true (map Drule.mk_term [a0, D0]) ctxt0)
wenzelm@32813
    53
  val (aT,bT) =
wenzelm@32813
    54
     let val T = typ_of (ctyp_of_term a)
huffman@31706
    55
     in (Term.range_type T, Term.domain_type T)
huffman@31706
    56
     end
huffman@31706
    57
  val ctxt' = (Variable.declare_term (term_of a) o Variable.declare_term (term_of D) o Variable.declare_thm th) ctxt
huffman@31706
    58
  val ns = filter (fn i => Type.could_unify (snd i, aT) andalso not (fst (fst i) mem_string leave)) (Term.add_vars (prop_of th) [])
huffman@31706
    59
  val (ins, ctxt'') = Variable.variant_fixes (map (fst o fst) ns) ctxt'
huffman@31706
    60
  val cns = map ((cterm_of o ProofContext.theory_of) ctxt'' o Var) ns
huffman@31706
    61
  val cfis = map ((cterm_of o ProofContext.theory_of) ctxt'' o (fn n => Free (n, bT))) ins
huffman@31706
    62
  val cis = map (Thm.capply a) cfis
huffman@31706
    63
  val (hs,ctxt''') = Assumption.add_assumes (map (fn ct => Thm.capply @{cterm "Trueprop"} (Thm.capply D ct)) cfis) ctxt''
wenzelm@32813
    64
  val th1 = Drule.cterm_instantiate (cns ~~ cis) th
wenzelm@32813
    65
  val th2 = fold Thm.elim_implies hs (fold_rev implies_intr (map cprop_of hs) th1)
wenzelm@32813
    66
  val th3 = Simplifier.asm_full_simplify (Simplifier.context ctxt''' (simpset_of_entry injonly e))
huffman@31706
    67
                                         (fold_rev implies_intr (map cprop_of hs) th2)
huffman@31706
    68
in hd (Variable.export ctxt''' ctxt0 [th3]) end;
huffman@31706
    69
huffman@31706
    70
local
wenzelm@32813
    71
fun transfer_ruleh a D leave ctxt th =
huffman@31706
    72
 let val (ss,al) = get ctxt
huffman@31706
    73
     val a0 = cterm_of (ProofContext.theory_of ctxt) a
huffman@31706
    74
     val D0 = cterm_of (ProofContext.theory_of ctxt) D
wenzelm@32813
    75
     fun h (th', e) = let val (a',D') = (Thm.dest_binop o Thm.dest_arg o cprop_of) th'
huffman@31706
    76
                 in if a0 aconvc a' andalso D0 aconvc D' then SOME e else NONE
huffman@31706
    77
                 end
huffman@31706
    78
 in case get_first h al of
huffman@31706
    79
      SOME e => basic_transfer_rule false a0 D0 e leave ctxt th
huffman@31706
    80
    | NONE => error "Transfer: corresponding instance not found in context-data"
huffman@31706
    81
 end
wenzelm@32813
    82
in fun transfer_rule (a,D) leave (gctxt,th) =
huffman@31706
    83
   (gctxt, transfer_ruleh a D leave (Context.proof_of gctxt) th)
huffman@31706
    84
end;
huffman@31706
    85
huffman@31706
    86
fun  splits P [] = []
wenzelm@32813
    87
   | splits P (xxs as (x::xs)) =
huffman@31706
    88
    let val pss = filter (P x) xxs
huffman@31706
    89
        val qss = filter_out (P x) xxs
huffman@31706
    90
    in if null pss then [qss] else if null qss then [pss] else pss:: splits P qss
huffman@31706
    91
    end
huffman@31706
    92
wenzelm@32813
    93
fun all_transfers leave (gctxt,th) =
wenzelm@32813
    94
 let
huffman@31706
    95
  val ctxt = Context.proof_of gctxt
huffman@31706
    96
  val tys = map snd (Term.add_vars (prop_of th) [])
huffman@31706
    97
  val _ = if null tys then error "transfer: Unable to guess instance" else ()
wenzelm@32813
    98
  val tyss = splits (curry Type.could_unify) tys
huffman@31706
    99
  val get_ty = typ_of o ctyp_of_term o fst o Thm.dest_binop o Thm.dest_arg o cprop_of
huffman@31706
   100
  val get_aD = Thm.dest_binop o Thm.dest_arg o cprop_of
wenzelm@32813
   101
  val insts =
wenzelm@32813
   102
    map_filter (fn tys =>
wenzelm@32813
   103
      get_first (fn (k,ss) =>
wenzelm@32813
   104
        if Type.could_unify (hd tys, range_type (get_ty k))
wenzelm@32813
   105
        then SOME (get_aD k, ss)
wenzelm@32813
   106
        else NONE) (snd (get ctxt))) tyss
wenzelm@32813
   107
  val _ =
wenzelm@32813
   108
    if null insts then
wenzelm@32813
   109
      error "Transfer guesser: there were no possible instances, use direction: in order to provide a direction"
wenzelm@32813
   110
    else ()
huffman@31706
   111
  val ths = map  (fn ((a,D),e) => basic_transfer_rule false a D e leave ctxt th) insts
huffman@31706
   112
  val cth = Conjunction.intr_balanced ths
huffman@31706
   113
 in (gctxt, cth)
huffman@31706
   114
 end;
huffman@31706
   115
wenzelm@32813
   116
fun transfer_rule_by_hint ls leave (gctxt,th) =
wenzelm@32813
   117
 let
huffman@31706
   118
  val ctxt = Context.proof_of gctxt
huffman@31706
   119
  val get_aD = Thm.dest_binop o Thm.dest_arg o cprop_of
wenzelm@32813
   120
  val insts =
wenzelm@32813
   121
    map_filter (fn (k,e) => if exists (member (op =) (#hints e)) ls
haftmann@32557
   122
          then SOME (get_aD k, e) else NONE)
huffman@31706
   123
        (snd (get ctxt))
huffman@31706
   124
  val _ = if null insts then error "Transfer: No labels provided are stored in the context" else ()
huffman@31706
   125
  val ths = map  (fn ((a,D),e) => basic_transfer_rule false a D e leave ctxt th) insts
huffman@31706
   126
  val cth = Conjunction.intr_balanced ths
huffman@31706
   127
 in (gctxt, cth)
huffman@31706
   128
 end;
huffman@31706
   129
huffman@31706
   130
wenzelm@32813
   131
fun transferred_attribute ls NONE leave =
huffman@31706
   132
         if null ls then all_transfers leave else transfer_rule_by_hint ls leave
huffman@31706
   133
  | transferred_attribute _ (SOME (a,D)) leave = transfer_rule (a,D) leave
huffman@31706
   134
wenzelm@32813
   135
wenzelm@32813
   136
(* Add data to the context *)
wenzelm@32813
   137
huffman@31706
   138
fun gen_merge_entries {inj = inj0, emb = emb0, ret = ret0, cong = cg0, guess = g0, hints = hints0}
wenzelm@32813
   139
                      ({inj = inj1, emb = emb1, ret = ret1, cong = cg1, guess = g1, hints = hints1},
huffman@31706
   140
                       {inj = inj2, emb = emb2, ret = ret2, cong = cg2, guess = g2, hints = hints2})
wenzelm@32813
   141
 =
huffman@31706
   142
 let fun h xs0 xs ys = subtract Thm.eq_thm xs0 (merge Thm.eq_thm (xs,ys)) in
wenzelm@32813
   143
 {inj = h inj0 inj1 inj2, emb = h emb0 emb1 emb2,
huffman@31706
   144
  ret = h ret0 ret1 ret2, cong = h cg0 cg1 cg2, guess = g1 andalso g2,
wenzelm@32813
   145
  hints = subtract (op = : string*string -> bool) hints0
haftmann@33037
   146
            (gen_union (op =) (hints1, hints2))}
huffman@31706
   147
 end;
huffman@31706
   148
huffman@31706
   149
local
huffman@31706
   150
 val h = curry (merge Thm.eq_thm)
huffman@31706
   151
in
wenzelm@32813
   152
fun merge_entries ({inj = inj1, emb = emb1, ret = ret1, cong = cg1, guess = g1, hints = hints1},
wenzelm@32813
   153
                   {inj = inj2, emb = emb2, ret = ret2, cong = cg2, guess = g2, hints = hints2}) =
haftmann@33037
   154
    {inj = h inj1 inj2, emb = h emb1 emb2, ret = h ret1 ret2, cong = h cg1 cg2, guess = g1 andalso g2, hints = gen_union (op =) (hints1, hints2)}
wenzelm@32813
   155
end;
huffman@31706
   156
huffman@31706
   157
fun add ((inja,injd), (emba,embd), (reta,retd), (cga,cgd), g, (hintsa, hintsd)) =
huffman@31706
   158
  Thm.declaration_attribute (fn key => fn context => context |> Data.map
wenzelm@32813
   159
   (fn (ss, al) =>
huffman@31706
   160
     let
wenzelm@32813
   161
      val _ = Thm.match (transM_pat, Thm.dest_arg (Thm.cprop_of key))
wenzelm@32813
   162
        handle Pattern.MATCH =>
wenzelm@32813
   163
          error "Attribute expected Theorem of the form : TransferMorphism A a B b"
huffman@31706
   164
      val e0 = {inj = inja, emb = emba, ret = reta, cong = cga, guess = g, hints = hintsa}
huffman@31706
   165
      val ed = {inj = injd, emb = embd, ret = retd, cong = cgd, guess = g, hints = hintsd}
wenzelm@32813
   166
      val entry =
wenzelm@32813
   167
        if g then
huffman@31706
   168
         let val (a0,D0) = (Thm.dest_binop o Thm.dest_arg o cprop_of) key
huffman@31706
   169
             val ctxt0 = ProofContext.init (Thm.theory_of_thm key)
wenzelm@32813
   170
             val inj' =
wenzelm@32813
   171
               if null inja then
wenzelm@32813
   172
                #inj
wenzelm@32813
   173
                  (case AList.lookup Thm.eq_thm al key of SOME e => e
wenzelm@32813
   174
                  | NONE => error "Transfer: can not generate return rules on the fly, either add injectivity axiom or force manual mode with mode: manual")
wenzelm@32813
   175
               else inja
huffman@31706
   176
             val ret' = merge Thm.eq_thm (reta,  map (fn th => basic_transfer_rule true a0 D0 {inj = inj', emb = [], ret = [], cong = cga, guess = g, hints = hintsa} [] ctxt0 th RS sym) emba)
wenzelm@32813
   177
         in {inj = inja, emb = emba, ret = ret', cong = cga, guess = g, hints = hintsa} end
huffman@31706
   178
        else e0
wenzelm@32813
   179
    in (ss, merge_update Thm.eq_thm (gen_merge_entries ed) (key, entry) al)
huffman@31706
   180
    end));
huffman@31706
   181
huffman@31706
   182
huffman@31706
   183
(* concrete syntax *)
huffman@31706
   184
huffman@31706
   185
local
huffman@31706
   186
huffman@31706
   187
fun keyword k = Scan.lift (Args.$$$ k) >> K ()
huffman@31706
   188
fun keywordC k = Scan.lift (Args.$$$ k -- Args.colon) >> K ()
huffman@31706
   189
huffman@31706
   190
val congN = "cong"
huffman@31706
   191
val injN = "inj"
huffman@31706
   192
val embedN = "embed"
huffman@31706
   193
val returnN = "return"
huffman@31706
   194
val addN = "add"
huffman@31706
   195
val delN = "del"
huffman@31706
   196
val modeN = "mode"
huffman@31706
   197
val automaticN = "automatic"
huffman@31706
   198
val manualN = "manual"
huffman@31706
   199
val directionN = "direction"
huffman@31706
   200
val labelsN = "labels"
huffman@31706
   201
val leavingN = "leaving"
huffman@31706
   202
huffman@31706
   203
val any_keyword = keywordC congN || keywordC injN || keywordC embedN || keywordC returnN || keywordC directionN || keywordC modeN || keywordC delN || keywordC labelsN || keywordC leavingN
huffman@31706
   204
huffman@31706
   205
val thms = Scan.repeat (Scan.unless any_keyword Attrib.multi_thm) >> flat
huffman@31706
   206
val terms = thms >> map Drule.dest_term
wenzelm@32813
   207
val types = thms >> (Logic.dest_type o HOLogic.dest_Trueprop o prop_of o hd)
huffman@31706
   208
val name = Scan.lift Args.name
huffman@31706
   209
val names = Scan.repeat (Scan.unless any_keyword name)
huffman@31706
   210
fun optional scan = Scan.optional scan []
huffman@31706
   211
fun optional2 scan = Scan.optional scan ([],[])
huffman@31706
   212
huffman@31706
   213
val mode = keywordC modeN |-- ((Scan.lift (Args.$$$ manualN) >> K false) || (Scan.lift (Args.$$$ automaticN) >> K true))
huffman@31706
   214
val inj = (keywordC injN |-- thms) -- optional (keywordC delN |-- thms)
huffman@31706
   215
val embed = (keywordC embedN |-- thms) -- optional (keywordC delN |-- thms)
huffman@31706
   216
val return = (keywordC returnN |-- thms) -- optional (keywordC delN |-- thms)
huffman@31706
   217
val cong = (keywordC congN |-- thms) -- optional (keywordC delN |-- thms)
huffman@31706
   218
val addscan = Scan.unless any_keyword (keyword addN)
huffman@31706
   219
val labels = (keywordC labelsN |-- names) -- optional (keywordC delN |-- names)
huffman@31706
   220
val entry = Scan.optional mode true -- optional2 inj -- optional2 embed -- optional2 return -- optional2 cong -- optional2 labels
huffman@31706
   221
huffman@31706
   222
val transf_add = addscan |-- entry
huffman@31706
   223
in
huffman@31706
   224
huffman@31706
   225
val install_att_syntax =
huffman@31706
   226
  (Scan.lift (Args.$$$ delN >> K del) ||
huffman@31706
   227
    transf_add
huffman@31706
   228
    >> (fn (((((g, inj), embed), ret), cg), hints) => add (inj, embed, ret, cg, g, hints)))
huffman@31706
   229
haftmann@32476
   230
val transferred_att_syntax = (optional names -- Scan.option (keywordC directionN |-- (Args.term -- Args.term))
haftmann@32476
   231
  -- optional (keywordC leavingN |-- names) >> (fn ((hints, aD),leave) => transferred_attribute hints aD leave));
huffman@31706
   232
huffman@31706
   233
end;
huffman@31706
   234
huffman@31706
   235
huffman@31706
   236
(* theory setup *)
huffman@31706
   237
huffman@31706
   238
val setup =
huffman@31706
   239
  Attrib.setup @{binding transfer} install_att_syntax
huffman@31706
   240
    "Installs transfer data" #>
huffman@31706
   241
  Attrib.setup @{binding transfer_simps} (Attrib.add_del add_ss del_ss)
huffman@31706
   242
    "simp rules for transfer" #>
huffman@31706
   243
  Attrib.setup @{binding transferred} transferred_att_syntax
huffman@31706
   244
    "Transfers theorems";
huffman@31706
   245
huffman@31706
   246
end;