src/Pure/more_thm.ML
author wenzelm
Fri Mar 21 20:33:56 2014 +0100 (2014-03-21)
changeset 56245 84fc7dfa3cd4
parent 55633 460f4801b5cb
child 58001 934d85f14d1d
permissions -rw-r--r--
more qualified names;
     1 (*  Title:      Pure/more_thm.ML
     2     Author:     Makarius
     3 
     4 Further operations on type ctyp/cterm/thm, outside the inference kernel.
     5 *)
     6 
     7 infix aconvc;
     8 
     9 signature BASIC_THM =
    10 sig
    11   include BASIC_THM
    12   structure Ctermtab: TABLE
    13   structure Thmtab: TABLE
    14   val aconvc: cterm * cterm -> bool
    15   type attribute = Context.generic * thm -> Context.generic option * thm option
    16 end;
    17 
    18 signature THM =
    19 sig
    20   include THM
    21   structure Ctermtab: TABLE
    22   structure Thmtab: TABLE
    23   val aconvc: cterm * cterm -> bool
    24   val add_cterm_frees: cterm -> cterm list -> cterm list
    25   val all_name: string * cterm -> cterm -> cterm
    26   val all: cterm -> cterm -> cterm
    27   val mk_binop: cterm -> cterm -> cterm -> cterm
    28   val dest_binop: cterm -> cterm * cterm
    29   val dest_implies: cterm -> cterm * cterm
    30   val dest_equals: cterm -> cterm * cterm
    31   val dest_equals_lhs: cterm -> cterm
    32   val dest_equals_rhs: cterm -> cterm
    33   val lhs_of: thm -> cterm
    34   val rhs_of: thm -> cterm
    35   val thm_ord: thm * thm -> order
    36   val cterm_cache: (cterm -> 'a) -> cterm -> 'a
    37   val thm_cache: (thm -> 'a) -> thm -> 'a
    38   val is_reflexive: thm -> bool
    39   val eq_thm: thm * thm -> bool
    40   val eq_thm_prop: thm * thm -> bool
    41   val eq_thm_strict: thm * thm -> bool
    42   val equiv_thm: thm * thm -> bool
    43   val class_triv: theory -> class -> thm
    44   val of_sort: ctyp * sort -> thm list
    45   val check_shyps: sort list -> thm -> thm
    46   val is_dummy: thm -> bool
    47   val plain_prop_of: thm -> term
    48   val add_thm: thm -> thm list -> thm list
    49   val del_thm: thm -> thm list -> thm list
    50   val merge_thms: thm list * thm list -> thm list
    51   val full_rules: thm Item_Net.T
    52   val intro_rules: thm Item_Net.T
    53   val elim_rules: thm Item_Net.T
    54   val declare_hyps: cterm -> Proof.context -> Proof.context
    55   val assume_hyps: cterm -> Proof.context -> thm * Proof.context
    56   val unchecked_hyps: Proof.context -> Proof.context
    57   val restore_hyps: Proof.context -> Proof.context -> Proof.context
    58   val undeclared_hyps: Context.generic -> thm -> term list
    59   val check_hyps: Context.generic -> thm -> thm
    60   val elim_implies: thm -> thm -> thm
    61   val forall_elim_var: int -> thm -> thm
    62   val forall_elim_vars: int -> thm -> thm
    63   val certify_inst: theory ->
    64     ((indexname * sort) * typ) list * ((indexname * typ) * term) list ->
    65     (ctyp * ctyp) list * (cterm * cterm) list
    66   val certify_instantiate:
    67     ((indexname * sort) * typ) list * ((indexname * typ) * term) list -> thm -> thm
    68   val forall_intr_frees: thm -> thm
    69   val unvarify_global: thm -> thm
    70   val close_derivation: thm -> thm
    71   val add_axiom: Proof.context -> binding * term -> theory -> (string * thm) * theory
    72   val add_axiom_global: binding * term -> theory -> (string * thm) * theory
    73   val add_def: Proof.context -> bool -> bool -> binding * term -> theory -> (string * thm) * theory
    74   val add_def_global: bool -> bool -> binding * term -> theory -> (string * thm) * theory
    75   type attribute = Context.generic * thm -> Context.generic option * thm option
    76   type binding = binding * attribute list
    77   val empty_binding: binding
    78   val rule_attribute: (Context.generic -> thm -> thm) -> attribute
    79   val declaration_attribute: (thm -> Context.generic -> Context.generic) -> attribute
    80   val mixed_attribute: (Context.generic * thm -> Context.generic * thm) -> attribute
    81   val apply_attribute: attribute -> thm -> Context.generic -> thm * Context.generic
    82   val attribute_declaration: attribute -> thm -> Context.generic -> Context.generic
    83   val theory_attributes: attribute list -> thm -> theory -> thm * theory
    84   val proof_attributes: attribute list -> thm -> Proof.context -> thm * Proof.context
    85   val no_attributes: 'a -> 'a * 'b list
    86   val simple_fact: 'a -> ('a * 'b list) list
    87   val tag_rule: string * string -> thm -> thm
    88   val untag_rule: string -> thm -> thm
    89   val tag: string * string -> attribute
    90   val untag: string -> attribute
    91   val def_name: string -> string
    92   val def_name_optional: string -> string -> string
    93   val def_binding: Binding.binding -> Binding.binding
    94   val def_binding_optional: Binding.binding -> Binding.binding -> Binding.binding
    95   val has_name_hint: thm -> bool
    96   val get_name_hint: thm -> string
    97   val put_name_hint: string -> thm -> thm
    98   val theoremK: string
    99   val lemmaK: string
   100   val corollaryK: string
   101   val legacy_get_kind: thm -> string
   102   val kind_rule: string -> thm -> thm
   103   val kind: string -> attribute
   104   val register_proofs: thm list -> theory -> theory
   105   val join_theory_proofs: theory -> unit
   106 end;
   107 
   108 structure Thm: THM =
   109 struct
   110 
   111 (** basic operations **)
   112 
   113 (* collecting cterms *)
   114 
   115 val op aconvc = op aconv o pairself Thm.term_of;
   116 
   117 fun add_cterm_frees ct =
   118   let
   119     val cert = Thm.cterm_of (Thm.theory_of_cterm ct);
   120     val t = Thm.term_of ct;
   121   in Term.fold_aterms (fn v as Free _ => insert (op aconvc) (cert v) | _ => I) t end;
   122 
   123 
   124 (* cterm constructors and destructors *)
   125 
   126 fun all_name (x, t) A =
   127   let
   128     val cert = Thm.cterm_of (Thm.theory_of_cterm t);
   129     val T = #T (Thm.rep_cterm t);
   130   in Thm.apply (cert (Const ("Pure.all", (T --> propT) --> propT))) (Thm.lambda_name (x, t) A) end;
   131 
   132 fun all t A = all_name ("", t) A;
   133 
   134 fun mk_binop c a b = Thm.apply (Thm.apply c a) b;
   135 fun dest_binop ct = (Thm.dest_arg1 ct, Thm.dest_arg ct);
   136 
   137 fun dest_implies ct =
   138   (case Thm.term_of ct of
   139     Const ("Pure.imp", _) $ _ $ _ => dest_binop ct
   140   | _ => raise TERM ("dest_implies", [Thm.term_of ct]));
   141 
   142 fun dest_equals ct =
   143   (case Thm.term_of ct of
   144     Const ("Pure.eq", _) $ _ $ _ => dest_binop ct
   145   | _ => raise TERM ("dest_equals", [Thm.term_of ct]));
   146 
   147 fun dest_equals_lhs ct =
   148   (case Thm.term_of ct of
   149     Const ("Pure.eq", _) $ _ $ _ => Thm.dest_arg1 ct
   150   | _ => raise TERM ("dest_equals_lhs", [Thm.term_of ct]));
   151 
   152 fun dest_equals_rhs ct =
   153   (case Thm.term_of ct of
   154     Const ("Pure.eq", _) $ _ $ _ => Thm.dest_arg ct
   155   | _ => raise TERM ("dest_equals_rhs", [Thm.term_of ct]));
   156 
   157 val lhs_of = dest_equals_lhs o Thm.cprop_of;
   158 val rhs_of = dest_equals_rhs o Thm.cprop_of;
   159 
   160 
   161 (* thm order: ignores theory context! *)
   162 
   163 fun thm_ord (th1, th2) =
   164   let
   165     val {shyps = shyps1, hyps = hyps1, tpairs = tpairs1, prop = prop1, ...} = Thm.rep_thm th1;
   166     val {shyps = shyps2, hyps = hyps2, tpairs = tpairs2, prop = prop2, ...} = Thm.rep_thm th2;
   167   in
   168     (case Term_Ord.fast_term_ord (prop1, prop2) of
   169       EQUAL =>
   170         (case list_ord (prod_ord Term_Ord.fast_term_ord Term_Ord.fast_term_ord) (tpairs1, tpairs2) of
   171           EQUAL =>
   172             (case list_ord Term_Ord.fast_term_ord (hyps1, hyps2) of
   173               EQUAL => list_ord Term_Ord.sort_ord (shyps1, shyps2)
   174             | ord => ord)
   175         | ord => ord)
   176     | ord => ord)
   177   end;
   178 
   179 
   180 (* tables and caches *)
   181 
   182 structure Ctermtab = Table(type key = cterm val ord = Term_Ord.fast_term_ord o pairself Thm.term_of);
   183 structure Thmtab = Table(type key = thm val ord = thm_ord);
   184 
   185 fun cterm_cache f = Cache.create Ctermtab.empty Ctermtab.lookup Ctermtab.update f;
   186 fun thm_cache f = Cache.create Thmtab.empty Thmtab.lookup Thmtab.update f;
   187 
   188 
   189 (* equality *)
   190 
   191 fun is_reflexive th = op aconv (Logic.dest_equals (Thm.prop_of th))
   192   handle TERM _ => false;
   193 
   194 val eq_thm = is_equal o thm_ord;
   195 
   196 val eq_thm_prop = op aconv o pairself Thm.full_prop_of;
   197 
   198 fun eq_thm_strict ths =
   199   eq_thm ths andalso
   200     let val (rep1, rep2) = pairself Thm.rep_thm ths in
   201       Theory.eq_thy (#thy rep1, #thy rep2) andalso
   202       #maxidx rep1 = #maxidx rep2 andalso
   203       #tags rep1 = #tags rep2
   204     end;
   205 
   206 
   207 (* pattern equivalence *)
   208 
   209 fun equiv_thm ths =
   210   Pattern.equiv (Theory.merge (pairself Thm.theory_of_thm ths)) (pairself Thm.full_prop_of ths);
   211 
   212 
   213 (* type classes and sorts *)
   214 
   215 fun class_triv thy c =
   216   Thm.of_class (Thm.ctyp_of thy (TVar ((Name.aT, 0), [c])), c);
   217 
   218 fun of_sort (T, S) = map (fn c => Thm.of_class (T, c)) S;
   219 
   220 fun check_shyps sorts raw_th =
   221   let
   222     val th = Thm.strip_shyps raw_th;
   223     val prt_sort = Syntax.pretty_sort_global (Thm.theory_of_thm th);
   224     val pending = Sorts.subtract sorts (Thm.extra_shyps th);
   225   in
   226     if null pending then th
   227     else error (Pretty.string_of (Pretty.block (Pretty.str "Pending sort hypotheses:" ::
   228       Pretty.brk 1 :: Pretty.commas (map prt_sort pending))))
   229   end;
   230 
   231 
   232 (* misc operations *)
   233 
   234 fun is_dummy thm =
   235   (case try Logic.dest_term (Thm.concl_of thm) of
   236     NONE => false
   237   | SOME t => Term.is_dummy_pattern t);
   238 
   239 fun plain_prop_of raw_thm =
   240   let
   241     val thm = Thm.strip_shyps raw_thm;
   242     fun err msg = raise THM ("plain_prop_of: " ^ msg, 0, [thm]);
   243     val {hyps, prop, tpairs, ...} = Thm.rep_thm thm;
   244   in
   245     if not (null hyps) then
   246       err "theorem may not contain hypotheses"
   247     else if not (null (Thm.extra_shyps thm)) then
   248       err "theorem may not contain sort hypotheses"
   249     else if not (null tpairs) then
   250       err "theorem may not contain flex-flex pairs"
   251     else prop
   252   end;
   253 
   254 
   255 (* collections of theorems in canonical order *)
   256 
   257 val add_thm = update eq_thm_prop;
   258 val del_thm = remove eq_thm_prop;
   259 val merge_thms = merge eq_thm_prop;
   260 
   261 val full_rules = Item_Net.init eq_thm_prop (single o Thm.full_prop_of);
   262 val intro_rules = Item_Net.init eq_thm_prop (single o Thm.concl_of);
   263 val elim_rules = Item_Net.init eq_thm_prop (single o Thm.major_prem_of);
   264 
   265 
   266 
   267 (** declared hyps **)
   268 
   269 structure Hyps = Proof_Data
   270 (
   271   type T = Termtab.set * bool;
   272   fun init _ : T = (Termtab.empty, true);
   273 );
   274 
   275 fun declare_hyps ct ctxt =
   276   if Theory.subthy (theory_of_cterm ct, Proof_Context.theory_of ctxt) then
   277     (Hyps.map o apfst) (Termtab.update (term_of ct, ())) ctxt
   278   else raise CTERM ("assume_hyps: bad background theory", [ct]);
   279 
   280 fun assume_hyps ct ctxt = (Thm.assume ct, declare_hyps ct ctxt);
   281 
   282 val unchecked_hyps = (Hyps.map o apsnd) (K false);
   283 fun restore_hyps ctxt = (Hyps.map o apsnd) (K (#2 (Hyps.get ctxt)));
   284 
   285 fun undeclared_hyps context th =
   286   Thm.hyps_of th
   287   |> filter_out
   288     (case context of
   289       Context.Theory _ => K false
   290     | Context.Proof ctxt =>
   291         (case Hyps.get ctxt of
   292           (_, false) => K true
   293         | (hyps, _) => Termtab.defined hyps));
   294 
   295 fun check_hyps context th =
   296   (case undeclared_hyps context th of
   297     [] => th
   298   | undeclared =>
   299       let
   300         val ctxt = Context.cases Syntax.init_pretty_global I context;
   301       in
   302         error (Pretty.string_of (Pretty.big_list "Undeclared hyps:"
   303           (map (Pretty.item o single o Syntax.pretty_term ctxt) undeclared)))
   304       end);
   305 
   306 
   307 
   308 (** basic derived rules **)
   309 
   310 (*Elimination of implication
   311   A    A ==> B
   312   ------------
   313         B
   314 *)
   315 fun elim_implies thA thAB = Thm.implies_elim thAB thA;
   316 
   317 
   318 (* forall_elim_var(s) *)
   319 
   320 local
   321 
   322 fun forall_elim_vars_aux strip_vars i th =
   323   let
   324     val thy = Thm.theory_of_thm th;
   325     val {tpairs, prop, ...} = Thm.rep_thm th;
   326     val add_used = Term.fold_aterms
   327       (fn Var ((x, j), _) => if i = j then insert (op =) x else I | _ => I);
   328     val used = fold (fn (t, u) => add_used t o add_used u) tpairs (add_used prop []);
   329     val vars = strip_vars prop;
   330     val cvars = (Name.variant_list used (map #1 vars), vars)
   331       |> ListPair.map (fn (x, (_, T)) => Thm.cterm_of thy (Var ((x, i), T)));
   332   in fold Thm.forall_elim cvars th end;
   333 
   334 in
   335 
   336 val forall_elim_vars = forall_elim_vars_aux Term.strip_all_vars;
   337 
   338 fun forall_elim_var i th =
   339   forall_elim_vars_aux
   340     (fn Const ("Pure.all", _) $ Abs (a, T, _) => [(a, T)]
   341       | _ => raise THM ("forall_elim_vars", i, [th])) i th;
   342 
   343 end;
   344 
   345 
   346 (* certify_instantiate *)
   347 
   348 fun certify_inst thy (instT, inst) =
   349   (map (fn (v, T) => (Thm.ctyp_of thy (TVar v), Thm.ctyp_of thy T)) instT,
   350     map (fn (v, t) => (Thm.cterm_of thy (Var v), Thm.cterm_of thy t)) inst);
   351 
   352 fun certify_instantiate insts th =
   353   Thm.instantiate (certify_inst (Thm.theory_of_thm th) insts) th;
   354 
   355 
   356 (* forall_intr_frees: generalization over all suitable Free variables *)
   357 
   358 fun forall_intr_frees th =
   359   let
   360     val thy = Thm.theory_of_thm th;
   361     val {prop, hyps, tpairs, ...} = Thm.rep_thm th;
   362     val fixed = fold Term.add_frees (Thm.terms_of_tpairs tpairs @ hyps) [];
   363     val frees = Term.fold_aterms (fn Free v =>
   364       if member (op =) fixed v then I else insert (op =) v | _ => I) prop [];
   365   in fold (Thm.forall_intr o Thm.cterm_of thy o Free) frees th end;
   366 
   367 
   368 (* unvarify_global: global schematic variables *)
   369 
   370 fun unvarify_global th =
   371   let
   372     val prop = Thm.full_prop_of th;
   373     val _ = map Logic.unvarify_global (prop :: Thm.hyps_of th)
   374       handle TERM (msg, _) => raise THM (msg, 0, [th]);
   375 
   376     val instT = rev (Term.add_tvars prop []) |> map (fn v as ((a, _), S) => (v, TFree (a, S)));
   377     val inst = rev (Term.add_vars prop []) |> map (fn ((a, i), T) =>
   378       let val T' = Term_Subst.instantiateT instT T
   379       in (((a, i), T'), Free ((a, T'))) end);
   380   in certify_instantiate (instT, inst) th end;
   381 
   382 
   383 (* close_derivation *)
   384 
   385 fun close_derivation thm =
   386   if Thm.derivation_name thm = "" then Thm.name_derivation "" thm
   387   else thm;
   388 
   389 
   390 
   391 (** specification primitives **)
   392 
   393 (* rules *)
   394 
   395 fun stripped_sorts thy t =
   396   let
   397     val tfrees = rev (map TFree (Term.add_tfrees t []));
   398     val tfrees' = map (fn a => TFree (a, [])) (Name.invent Name.context Name.aT (length tfrees));
   399     val strip = tfrees ~~ tfrees';
   400     val recover = map (pairself (Thm.ctyp_of thy o Logic.varifyT_global) o swap) strip;
   401     val t' = Term.map_types (Term.map_atyps (perhaps (AList.lookup (op =) strip))) t;
   402   in (strip, recover, t') end;
   403 
   404 fun add_axiom ctxt (b, prop) thy =
   405   let
   406     val _ = Sign.no_vars ctxt prop;
   407     val (strip, recover, prop') = stripped_sorts thy prop;
   408     val constraints = map (fn (TFree (_, S), T) => (T, S)) strip;
   409     val of_sorts = maps (fn (T as TFree (_, S), _) => of_sort (Thm.ctyp_of thy T, S)) strip;
   410 
   411     val thy' = thy
   412       |> Theory.add_axiom ctxt (b, Logic.list_implies (maps Logic.mk_of_sort constraints, prop'));
   413     val axm_name = Sign.full_name thy' b;
   414     val axm' = Thm.axiom thy' axm_name;
   415     val thm =
   416       Thm.instantiate (recover, []) axm'
   417       |> unvarify_global
   418       |> fold elim_implies of_sorts;
   419   in ((axm_name, thm), thy') end;
   420 
   421 fun add_axiom_global arg thy = add_axiom (Syntax.init_pretty_global thy) arg thy;
   422 
   423 fun add_def ctxt unchecked overloaded (b, prop) thy =
   424   let
   425     val _ = Sign.no_vars ctxt prop;
   426     val prems = map (Thm.cterm_of thy) (Logic.strip_imp_prems prop);
   427     val (_, recover, concl') = stripped_sorts thy (Logic.strip_imp_concl prop);
   428 
   429     val thy' = Theory.add_def ctxt unchecked overloaded (b, concl') thy;
   430     val axm_name = Sign.full_name thy' b;
   431     val axm' = Thm.axiom thy' axm_name;
   432     val thm =
   433       Thm.instantiate (recover, []) axm'
   434       |> unvarify_global
   435       |> fold_rev Thm.implies_intr prems;
   436   in ((axm_name, thm), thy') end;
   437 
   438 fun add_def_global unchecked overloaded arg thy =
   439   add_def (Syntax.init_pretty_global thy) unchecked overloaded arg thy;
   440 
   441 
   442 
   443 (** attributes **)
   444 
   445 (*attributes subsume any kind of rules or context modifiers*)
   446 type attribute = Context.generic * thm -> Context.generic option * thm option;
   447 
   448 type binding = binding * attribute list;
   449 val empty_binding: binding = (Binding.empty, []);
   450 
   451 fun rule_attribute f (x, th) = (NONE, SOME (f x th));
   452 fun declaration_attribute f (x, th) = (SOME (f th x), NONE);
   453 fun mixed_attribute f (x, th) = let val (x', th') = f (x, th) in (SOME x', SOME th') end;
   454 
   455 fun apply_attribute (att: attribute) th x =
   456   let val (x', th') = att (x, check_hyps x (Thm.transfer (Context.theory_of x) th))
   457   in (the_default th th', the_default x x') end;
   458 
   459 fun attribute_declaration att th x = #2 (apply_attribute att th x);
   460 
   461 fun apply_attributes mk dest =
   462   let
   463     fun app [] th x = (th, x)
   464       | app (att :: atts) th x = apply_attribute att th (mk x) ||> dest |-> app atts;
   465   in app end;
   466 
   467 val theory_attributes = apply_attributes Context.Theory Context.the_theory;
   468 val proof_attributes = apply_attributes Context.Proof Context.the_proof;
   469 
   470 fun no_attributes x = (x, []);
   471 fun simple_fact x = [(x, [])];
   472 
   473 
   474 
   475 (*** theorem tags ***)
   476 
   477 (* add / delete tags *)
   478 
   479 fun tag_rule tg = Thm.map_tags (insert (op =) tg);
   480 fun untag_rule s = Thm.map_tags (filter_out (fn (s', _) => s = s'));
   481 
   482 fun tag tg = rule_attribute (K (tag_rule tg));
   483 fun untag s = rule_attribute (K (untag_rule s));
   484 
   485 
   486 (* def_name *)
   487 
   488 fun def_name c = c ^ "_def";
   489 
   490 fun def_name_optional c "" = def_name c
   491   | def_name_optional _ name = name;
   492 
   493 val def_binding = Binding.map_name def_name;
   494 
   495 fun def_binding_optional b name =
   496   if Binding.is_empty name then def_binding b else name;
   497 
   498 
   499 (* unofficial theorem names *)
   500 
   501 fun the_name_hint thm = the (AList.lookup (op =) (Thm.get_tags thm) Markup.nameN);
   502 
   503 val has_name_hint = can the_name_hint;
   504 val get_name_hint = the_default "??.unknown" o try the_name_hint;
   505 
   506 fun put_name_hint name = untag_rule Markup.nameN #> tag_rule (Markup.nameN, name);
   507 
   508 
   509 (* theorem kinds *)
   510 
   511 val theoremK = "theorem";
   512 val lemmaK = "lemma";
   513 val corollaryK = "corollary";
   514 
   515 fun legacy_get_kind thm = the_default "" (Properties.get (Thm.get_tags thm) Markup.kindN);
   516 
   517 fun kind_rule k = tag_rule (Markup.kindN, k) o untag_rule Markup.kindN;
   518 fun kind k = rule_attribute (K (k <> "" ? kind_rule k));
   519 
   520 
   521 (* forked proofs *)
   522 
   523 structure Proofs = Theory_Data
   524 (
   525   type T = thm list;
   526   val empty = [];
   527   fun extend _ = empty;
   528   fun merge _ = empty;
   529 );
   530 
   531 fun register_proofs more_thms = Proofs.map (fn thms => fold cons more_thms thms);
   532 val join_theory_proofs = Thm.join_proofs o rev o Proofs.get;
   533 
   534 
   535 open Thm;
   536 
   537 end;
   538 
   539 structure Basic_Thm: BASIC_THM = Thm;
   540 open Basic_Thm;
   541