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