src/Pure/more_thm.ML
author bulwahn
Sat May 16 20:17:59 2009 +0200 (2009-05-16)
changeset 31174 f1f1e9b53c81
parent 30564 deddb8a1516f
child 31177 c39994cb152a
permissions -rw-r--r--
added new kind generated_theorem for theorems which are generated by packages to distinguish between theorems from users and packages
     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 THM =
    10 sig
    11   include THM
    12   val aconvc: cterm * cterm -> bool
    13   val add_cterm_frees: cterm -> cterm list -> cterm list
    14   val mk_binop: cterm -> cterm -> cterm -> cterm
    15   val dest_binop: cterm -> cterm * cterm
    16   val dest_implies: cterm -> cterm * cterm
    17   val dest_equals: cterm -> cterm * cterm
    18   val dest_equals_lhs: cterm -> cterm
    19   val dest_equals_rhs: cterm -> cterm
    20   val lhs_of: thm -> cterm
    21   val rhs_of: thm -> cterm
    22   val thm_ord: thm * thm -> order
    23   val is_reflexive: thm -> bool
    24   val eq_thm: thm * thm -> bool
    25   val eq_thms: thm list * thm list -> bool
    26   val eq_thm_thy: thm * thm -> bool
    27   val eq_thm_prop: thm * thm -> bool
    28   val equiv_thm: thm * thm -> bool
    29   val check_shyps: sort list -> thm -> thm
    30   val is_dummy: thm -> bool
    31   val plain_prop_of: thm -> term
    32   val fold_terms: (term -> 'a -> 'a) -> thm -> 'a -> 'a
    33   val add_thm: thm -> thm list -> thm list
    34   val del_thm: thm -> thm list -> thm list
    35   val merge_thms: thm list * thm list -> thm list
    36   val intro_rules: thm Item_Net.T
    37   val elim_rules: thm Item_Net.T
    38   val elim_implies: thm -> thm -> thm
    39   val forall_elim_var: int -> thm -> thm
    40   val forall_elim_vars: int -> thm -> thm
    41   val unvarify: thm -> thm
    42   val close_derivation: thm -> thm
    43   val add_axiom: binding * term -> theory -> thm * theory
    44   val add_def: bool -> bool -> binding * term -> theory -> thm * theory
    45   type binding = binding * attribute list
    46   val empty_binding: binding
    47   val rule_attribute: (Context.generic -> thm -> thm) -> attribute
    48   val declaration_attribute: (thm -> Context.generic -> Context.generic) -> attribute
    49   val theory_attributes: attribute list -> theory * thm -> theory * thm
    50   val proof_attributes: attribute list -> Proof.context * thm -> Proof.context * thm
    51   val no_attributes: 'a -> 'a * 'b list
    52   val simple_fact: 'a -> ('a * 'b list) list
    53   val tag_rule: Properties.property -> thm -> thm
    54   val untag_rule: string -> thm -> thm
    55   val tag: Properties.property -> attribute
    56   val untag: string -> attribute
    57   val position_of: thm -> Position.T
    58   val default_position: Position.T -> thm -> thm
    59   val default_position_of: thm -> thm -> thm
    60   val def_name: string -> string
    61   val def_name_optional: string -> string -> string
    62   val def_binding_optional: Binding.binding -> Binding.binding -> Binding.binding
    63   val has_name_hint: thm -> bool
    64   val get_name_hint: thm -> string
    65   val put_name_hint: string -> thm -> thm
    66   val get_group: thm -> string option
    67   val put_group: string -> thm -> thm
    68   val group: string -> attribute
    69   val axiomK: string
    70   val assumptionK: string
    71   val definitionK: string
    72   val theoremK: string
    73   val generated_theoremK : string
    74   val lemmaK: string
    75   val corollaryK: string
    76   val internalK: string
    77   val has_kind: thm -> bool
    78   val get_kind: thm -> string
    79   val kind_rule: string -> thm -> thm
    80   val kind: string -> attribute
    81   val kind_internal: attribute
    82   val has_internal: Properties.property list -> bool
    83   val is_internal: thm -> bool
    84 end;
    85 
    86 structure Thm: THM =
    87 struct
    88 
    89 (** basic operations **)
    90 
    91 (* collecting cterms *)
    92 
    93 val op aconvc = op aconv o pairself Thm.term_of;
    94 
    95 fun add_cterm_frees ct =
    96   let
    97     val cert = Thm.cterm_of (Thm.theory_of_cterm ct);
    98     val t = Thm.term_of ct;
    99   in Term.fold_aterms (fn v as Free _ => insert (op aconvc) (cert v) | _ => I) t end;
   100 
   101 
   102 (* cterm constructors and destructors *)
   103 
   104 fun mk_binop c a b = Thm.capply (Thm.capply c a) b;
   105 fun dest_binop ct = (Thm.dest_arg1 ct, Thm.dest_arg ct);
   106 
   107 fun dest_implies ct =
   108   (case Thm.term_of ct of
   109     Const ("==>", _) $ _ $ _ => dest_binop ct
   110   | _ => raise TERM ("dest_implies", [Thm.term_of ct]));
   111 
   112 fun dest_equals ct =
   113   (case Thm.term_of ct of
   114     Const ("==", _) $ _ $ _ => dest_binop ct
   115   | _ => raise TERM ("dest_equals", [Thm.term_of ct]));
   116 
   117 fun dest_equals_lhs ct =
   118   (case Thm.term_of ct of
   119     Const ("==", _) $ _ $ _ => Thm.dest_arg1 ct
   120   | _ => raise TERM ("dest_equals_lhs", [Thm.term_of ct]));
   121 
   122 fun dest_equals_rhs ct =
   123   (case Thm.term_of ct of
   124     Const ("==", _) $ _ $ _ => Thm.dest_arg ct
   125   | _ => raise TERM ("dest_equals_rhs", [Thm.term_of ct]));
   126 
   127 val lhs_of = dest_equals_lhs o Thm.cprop_of;
   128 val rhs_of = dest_equals_rhs o Thm.cprop_of;
   129 
   130 
   131 (* thm order: ignores theory context! *)
   132 
   133 fun thm_ord (th1, th2) =
   134   let
   135     val {shyps = shyps1, hyps = hyps1, tpairs = tpairs1, prop = prop1, ...} = Thm.rep_thm th1;
   136     val {shyps = shyps2, hyps = hyps2, tpairs = tpairs2, prop = prop2, ...} = Thm.rep_thm th2;
   137   in
   138     (case TermOrd.fast_term_ord (prop1, prop2) of
   139       EQUAL =>
   140         (case list_ord (prod_ord TermOrd.fast_term_ord TermOrd.fast_term_ord) (tpairs1, tpairs2) of
   141           EQUAL =>
   142             (case list_ord TermOrd.fast_term_ord (hyps1, hyps2) of
   143               EQUAL => list_ord TermOrd.sort_ord (shyps1, shyps2)
   144             | ord => ord)
   145         | ord => ord)
   146     | ord => ord)
   147   end;
   148 
   149 
   150 (* equality *)
   151 
   152 fun is_reflexive th = op aconv (Logic.dest_equals (Thm.prop_of th))
   153   handle TERM _ => false;
   154 
   155 fun eq_thm ths =
   156   Context.joinable (pairself Thm.theory_of_thm ths) andalso
   157   is_equal (thm_ord ths);
   158 
   159 val eq_thms = eq_list eq_thm;
   160 
   161 val eq_thm_thy = Theory.eq_thy o pairself Thm.theory_of_thm;
   162 val eq_thm_prop = op aconv o pairself Thm.full_prop_of;
   163 
   164 
   165 (* pattern equivalence *)
   166 
   167 fun equiv_thm ths =
   168   Pattern.equiv (Theory.merge (pairself Thm.theory_of_thm ths)) (pairself Thm.full_prop_of ths);
   169 
   170 
   171 (* sort hypotheses *)
   172 
   173 fun check_shyps sorts raw_th =
   174   let
   175     val th = Thm.strip_shyps raw_th;
   176     val prt_sort = Syntax.pretty_sort_global (Thm.theory_of_thm th);
   177     val pending = Sorts.subtract sorts (Thm.extra_shyps th);
   178   in
   179     if null pending then th
   180     else error (Pretty.string_of (Pretty.block (Pretty.str "Pending sort hypotheses:" ::
   181       Pretty.brk 1 :: Pretty.commas (map prt_sort pending))))
   182   end;
   183 
   184 
   185 (* misc operations *)
   186 
   187 fun is_dummy thm =
   188   (case try Logic.dest_term (Thm.concl_of thm) of
   189     NONE => false
   190   | SOME t => Term.is_dummy_pattern t);
   191 
   192 fun plain_prop_of raw_thm =
   193   let
   194     val thm = Thm.strip_shyps raw_thm;
   195     fun err msg = raise THM ("plain_prop_of: " ^ msg, 0, [thm]);
   196     val {hyps, prop, tpairs, ...} = Thm.rep_thm thm;
   197   in
   198     if not (null hyps) then
   199       err "theorem may not contain hypotheses"
   200     else if not (null (Thm.extra_shyps thm)) then
   201       err "theorem may not contain sort hypotheses"
   202     else if not (null tpairs) then
   203       err "theorem may not contain flex-flex pairs"
   204     else prop
   205   end;
   206 
   207 fun fold_terms f th =
   208   let val {tpairs, prop, hyps, ...} = Thm.rep_thm th
   209   in fold (fn (t, u) => f t #> f u) tpairs #> f prop #> fold f hyps end;
   210 
   211 
   212 (* collections of theorems in canonical order *)
   213 
   214 val add_thm = update eq_thm_prop;
   215 val del_thm = remove eq_thm_prop;
   216 val merge_thms = merge eq_thm_prop;
   217 
   218 val intro_rules = Item_Net.init eq_thm_prop Thm.concl_of;
   219 val elim_rules = Item_Net.init eq_thm_prop Thm.major_prem_of;
   220 
   221 
   222 
   223 (** basic derived rules **)
   224 
   225 (*Elimination of implication
   226   A    A ==> B
   227   ------------
   228         B
   229 *)
   230 fun elim_implies thA thAB = Thm.implies_elim thAB thA;
   231 
   232 
   233 (* forall_elim_var(s) *)
   234 
   235 local
   236 
   237 fun forall_elim_vars_aux strip_vars i th =
   238   let
   239     val thy = Thm.theory_of_thm th;
   240     val {tpairs, prop, ...} = Thm.rep_thm th;
   241     val add_used = Term.fold_aterms
   242       (fn Var ((x, j), _) => if i = j then insert (op =) x else I | _ => I);
   243     val used = fold (fn (t, u) => add_used t o add_used u) tpairs (add_used prop []);
   244     val vars = strip_vars prop;
   245     val cvars = (Name.variant_list used (map #1 vars), vars)
   246       |> ListPair.map (fn (x, (_, T)) => Thm.cterm_of thy (Var ((x, i), T)));
   247   in fold Thm.forall_elim cvars th end;
   248 
   249 in
   250 
   251 val forall_elim_vars = forall_elim_vars_aux Term.strip_all_vars;
   252 
   253 fun forall_elim_var i th = forall_elim_vars_aux
   254   (fn Const ("all", _) $ Abs (a, T, _) => [(a, T)]
   255   | _ => raise THM ("forall_elim_vars", i, [th])) i th;
   256 
   257 end;
   258 
   259 
   260 (* unvarify: global schematic variables *)
   261 
   262 fun unvarify th =
   263   let
   264     val thy = Thm.theory_of_thm th;
   265     val cert = Thm.cterm_of thy;
   266     val certT = Thm.ctyp_of thy;
   267 
   268     val prop = Thm.full_prop_of th;
   269     val _ = map Logic.unvarify (prop :: Thm.hyps_of th)
   270       handle TERM (msg, _) => raise THM (msg, 0, [th]);
   271 
   272     val instT0 = rev (Term.add_tvars prop []) |> map (fn v as ((a, _), S) => (v, TFree (a, S)));
   273     val instT = map (fn (v, T) => (certT (TVar v), certT T)) instT0;
   274     val inst = rev (Term.add_vars prop []) |> map (fn ((a, i), T) =>
   275       let val T' = TermSubst.instantiateT instT0 T
   276       in (cert (Var ((a, i), T')), cert (Free ((a, T')))) end);
   277   in Thm.instantiate (instT, inst) th end;
   278 
   279 
   280 (* close_derivation *)
   281 
   282 fun close_derivation thm =
   283   if Thm.get_name thm = "" then Thm.put_name "" thm
   284   else thm;
   285 
   286 
   287 
   288 (** specification primitives **)
   289 
   290 (* rules *)
   291 
   292 fun add_axiom (b, prop) thy =
   293   let
   294     val b' = if Binding.is_empty b
   295       then Binding.name ("axiom_" ^ serial_string ()) else b;
   296     val thy' = thy |> Theory.add_axioms_i [(b', prop)];
   297     val axm = unvarify (Thm.axiom thy' (Sign.full_name thy' b'));
   298   in (axm, thy') end;
   299 
   300 fun add_def unchecked overloaded (b, prop) thy =
   301   let
   302     val tfrees = rev (map TFree (Term.add_tfrees prop []));
   303     val tfrees' = map (fn a => TFree (a, [])) (Name.invents Name.context Name.aT (length tfrees));
   304     val strip_sorts = tfrees ~~ tfrees';
   305     val recover_sorts = map (pairself (Thm.ctyp_of thy o Logic.varifyT)) (tfrees' ~~ tfrees);
   306 
   307     val prop' = Term.map_types (Term.map_atyps (perhaps (AList.lookup (op =) strip_sorts))) prop;
   308     val thy' = Theory.add_defs_i unchecked overloaded [(b, prop')] thy;
   309     val axm' = Thm.axiom thy' (Sign.full_name thy' b);
   310     val thm = unvarify (Thm.instantiate (recover_sorts, []) axm');
   311   in (thm, thy') end;
   312 
   313 
   314 
   315 (** attributes **)
   316 
   317 type binding = binding * attribute list;
   318 val empty_binding: binding = (Binding.empty, []);
   319 
   320 fun rule_attribute f (x, th) = (x, f x th);
   321 fun declaration_attribute f (x, th) = (f th x, th);
   322 
   323 fun apply_attributes mk dest =
   324   let
   325     fun app [] = I
   326       | app ((f: attribute) :: fs) = fn (x, th) => f (mk x, th) |>> dest |> app fs;
   327   in app end;
   328 
   329 val theory_attributes = apply_attributes Context.Theory Context.the_theory;
   330 val proof_attributes = apply_attributes Context.Proof Context.the_proof;
   331 
   332 fun no_attributes x = (x, []);
   333 fun simple_fact x = [(x, [])];
   334 
   335 
   336 
   337 (*** theorem tags ***)
   338 
   339 (* add / delete tags *)
   340 
   341 fun tag_rule tg = Thm.map_tags (insert (op =) tg);
   342 fun untag_rule s = Thm.map_tags (filter_out (fn (s', _) => s = s'));
   343 
   344 fun tag tg x = rule_attribute (K (tag_rule tg)) x;
   345 fun untag s x = rule_attribute (K (untag_rule s)) x;
   346 
   347 
   348 (* position *)
   349 
   350 val position_of = Position.of_properties o Thm.get_tags;
   351 
   352 fun default_position pos = Thm.map_tags (Position.default_properties pos);
   353 val default_position_of = default_position o position_of;
   354 
   355 
   356 (* def_name *)
   357 
   358 fun def_name c = c ^ "_def";
   359 
   360 fun def_name_optional c "" = def_name c
   361   | def_name_optional _ name = name;
   362 
   363 fun def_binding_optional b name =
   364   if Binding.is_empty name then Binding.map_name def_name b else name;
   365 
   366 
   367 (* unofficial theorem names *)
   368 
   369 fun the_name_hint thm = the (AList.lookup (op =) (Thm.get_tags thm) Markup.nameN);
   370 
   371 val has_name_hint = can the_name_hint;
   372 val get_name_hint = the_default "??.unknown" o try the_name_hint;
   373 
   374 fun put_name_hint name = untag_rule Markup.nameN #> tag_rule (Markup.nameN, name);
   375 
   376 
   377 (* theorem groups *)
   378 
   379 fun get_group thm = Properties.get (Thm.get_tags thm) Markup.groupN;
   380 
   381 fun put_group name = if name = "" then I else Thm.map_tags (Properties.put (Markup.groupN, name));
   382 
   383 fun group name = rule_attribute (K (put_group name));
   384 
   385 
   386 (* theorem kinds *)
   387 
   388 val axiomK = "axiom";
   389 val assumptionK = "assumption";
   390 val definitionK = "definition";
   391 val theoremK = "theorem";
   392 val generated_theoremK = "generated_theoremK"
   393 val lemmaK = "lemma";
   394 val corollaryK = "corollary";
   395 val internalK = Markup.internalK;
   396 
   397 fun the_kind thm = the (Properties.get (Thm.get_tags thm) Markup.kindN);
   398 
   399 val has_kind = can the_kind;
   400 val get_kind = the_default "" o try the_kind;
   401 
   402 fun kind_rule k = tag_rule (Markup.kindN, k) o untag_rule Markup.kindN;
   403 fun kind k x = if k = "" then x else rule_attribute (K (kind_rule k)) x;
   404 fun kind_internal x = kind internalK x;
   405 fun has_internal tags = exists (fn tg => tg = (Markup.kindN, internalK)) tags;
   406 val is_internal = has_internal o Thm.get_tags;
   407 
   408 
   409 open Thm;
   410 
   411 end;
   412 
   413 val op aconvc = Thm.aconvc;
   414 
   415 structure Thmtab = TableFun(type key = thm val ord = Thm.thm_ord);