src/Pure/more_thm.ML
author wenzelm
Fri Jun 13 21:04:42 2008 +0200 (2008-06-13)
changeset 27195 bbf4cbc69243
parent 26665 2e363edf7578
child 27255 0ea8e825a1b3
permissions -rw-r--r--
map_const: soft version, no failure here;
     1 (*  Title:      Pure/more_thm.ML
     2     ID:         $Id$
     3     Author:     Makarius
     4 
     5 Further operations on type ctyp/cterm/thm, outside the inference kernel.
     6 *)
     7 
     8 infix aconvc;
     9 
    10 signature THM =
    11 sig
    12   include THM
    13   val aconvc: cterm * cterm -> bool
    14   val add_cterm_frees: cterm -> cterm list -> cterm list
    15   val mk_binop: cterm -> cterm -> cterm -> cterm
    16   val dest_binop: cterm -> cterm * cterm
    17   val dest_implies: cterm -> cterm * cterm
    18   val dest_equals: cterm -> cterm * cterm
    19   val dest_equals_lhs: cterm -> cterm
    20   val dest_equals_rhs: cterm -> cterm
    21   val lhs_of: thm -> cterm
    22   val rhs_of: thm -> cterm
    23   val thm_ord: thm * thm -> order
    24   val is_reflexive: thm -> bool
    25   val eq_thm: thm * thm -> bool
    26   val eq_thms: thm list * thm list -> bool
    27   val eq_thm_thy: thm * thm -> bool
    28   val eq_thm_prop: thm * thm -> bool
    29   val equiv_thm: thm * thm -> bool
    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 axiomK: string
    37   val assumptionK: string
    38   val definitionK: string
    39   val theoremK: string
    40   val lemmaK: string
    41   val corollaryK: string
    42   val internalK: string
    43   val rule_attribute: (Context.generic -> thm -> thm) -> attribute
    44   val declaration_attribute: (thm -> Context.generic -> Context.generic) -> attribute
    45   val theory_attributes: attribute list -> theory * thm -> theory * thm
    46   val proof_attributes: attribute list -> Proof.context * thm -> Proof.context * thm
    47   val no_attributes: 'a -> 'a * 'b list
    48   val simple_fact: 'a -> ('a * 'b list) list
    49   val read_def_cterms:
    50     theory * (indexname -> typ option) * (indexname -> sort option) ->
    51     string list -> bool -> (string * typ)list
    52     -> cterm list * (indexname * typ)list
    53   val read_cterm: theory -> string * typ -> cterm
    54   val elim_implies: thm -> thm -> thm
    55   val forall_elim_var: int -> thm -> thm
    56   val forall_elim_vars: int -> thm -> thm
    57   val unvarify: thm -> thm
    58   val close_derivation: thm -> thm
    59   val add_axiom: term list -> bstring * term -> theory -> thm * theory
    60   val add_def: bool -> bool -> bstring * term -> theory -> thm * theory
    61 end;
    62 
    63 structure Thm: THM =
    64 struct
    65 
    66 (** basic operations **)
    67 
    68 (* collecting cterms *)
    69 
    70 val op aconvc = op aconv o pairself Thm.term_of;
    71 
    72 fun add_cterm_frees ct =
    73   let
    74     val cert = Thm.cterm_of (Thm.theory_of_cterm ct);
    75     val t = Thm.term_of ct;
    76   in Term.fold_aterms (fn v as Free _ => insert (op aconvc) (cert v) | _ => I) t end;
    77 
    78 
    79 (* cterm constructors and destructors *)
    80 
    81 fun mk_binop c a b = Thm.capply (Thm.capply c a) b;
    82 fun dest_binop ct = (Thm.dest_arg1 ct, Thm.dest_arg ct);
    83 
    84 fun dest_implies ct =
    85   (case Thm.term_of ct of
    86     Const ("==>", _) $ _ $ _ => dest_binop ct
    87   | _ => raise TERM ("dest_implies", [Thm.term_of ct]));
    88 
    89 fun dest_equals ct =
    90   (case Thm.term_of ct of
    91     Const ("==", _) $ _ $ _ => dest_binop ct
    92   | _ => raise TERM ("dest_equals", [Thm.term_of ct]));
    93 
    94 fun dest_equals_lhs ct =
    95   (case Thm.term_of ct of
    96     Const ("==", _) $ _ $ _ => Thm.dest_arg1 ct
    97   | _ => raise TERM ("dest_equals_lhs", [Thm.term_of ct]));
    98 
    99 fun dest_equals_rhs ct =
   100   (case Thm.term_of ct of
   101     Const ("==", _) $ _ $ _ => Thm.dest_arg ct
   102   | _ => raise TERM ("dest_equals_rhs", [Thm.term_of ct]));
   103 
   104 val lhs_of = dest_equals_lhs o Thm.cprop_of;
   105 val rhs_of = dest_equals_rhs o Thm.cprop_of;
   106 
   107 
   108 (* thm order: ignores theory context! *)
   109 
   110 fun thm_ord (th1, th2) =
   111   let
   112     val {shyps = shyps1, hyps = hyps1, tpairs = tpairs1, prop = prop1, ...} = Thm.rep_thm th1;
   113     val {shyps = shyps2, hyps = hyps2, tpairs = tpairs2, prop = prop2, ...} = Thm.rep_thm th2;
   114   in
   115     (case Term.fast_term_ord (prop1, prop2) of
   116       EQUAL =>
   117         (case list_ord (prod_ord Term.fast_term_ord Term.fast_term_ord) (tpairs1, tpairs2) of
   118           EQUAL =>
   119             (case list_ord Term.fast_term_ord (hyps1, hyps2) of
   120               EQUAL => list_ord Term.sort_ord (shyps1, shyps2)
   121             | ord => ord)
   122         | ord => ord)
   123     | ord => ord)
   124   end;
   125 
   126 
   127 (* equality *)
   128 
   129 fun is_reflexive th = op aconv (Logic.dest_equals (Thm.prop_of th))
   130   handle TERM _ => false;
   131 
   132 fun eq_thm ths =
   133   Context.joinable (pairself Thm.theory_of_thm ths) andalso
   134   is_equal (thm_ord ths);
   135 
   136 val eq_thms = eq_list eq_thm;
   137 
   138 val eq_thm_thy = Theory.eq_thy o pairself Thm.theory_of_thm;
   139 val eq_thm_prop = op aconv o pairself Thm.full_prop_of;
   140 
   141 
   142 (* pattern equivalence *)
   143 
   144 fun equiv_thm ths =
   145   Pattern.equiv (Theory.merge (pairself Thm.theory_of_thm ths)) (pairself Thm.full_prop_of ths);
   146 
   147 
   148 (* misc operations *)
   149 
   150 fun is_dummy thm =
   151   (case try Logic.dest_term (Thm.concl_of thm) of
   152     NONE => false
   153   | SOME t => Term.is_dummy_pattern t);
   154 
   155 fun plain_prop_of raw_thm =
   156   let
   157     val thm = Thm.strip_shyps raw_thm;
   158     fun err msg = raise THM ("plain_prop_of: " ^ msg, 0, [thm]);
   159     val {hyps, prop, tpairs, ...} = Thm.rep_thm thm;
   160   in
   161     if not (null hyps) then
   162       err "theorem may not contain hypotheses"
   163     else if not (null (Thm.extra_shyps thm)) then
   164       err "theorem may not contain sort hypotheses"
   165     else if not (null tpairs) then
   166       err "theorem may not contain flex-flex pairs"
   167     else prop
   168   end;
   169 
   170 fun fold_terms f th =
   171   let val {tpairs, prop, hyps, ...} = Thm.rep_thm th
   172   in fold (fn (t, u) => f t #> f u) tpairs #> f prop #> fold f hyps end;
   173 
   174 
   175 (* lists of theorems in canonical order *)
   176 
   177 val add_thm = update eq_thm_prop;
   178 val del_thm = remove eq_thm_prop;
   179 val merge_thms = merge eq_thm_prop;
   180 
   181 
   182 
   183 (** theorem kinds **)
   184 
   185 val axiomK = "axiom";
   186 val assumptionK = "assumption";
   187 val definitionK = "definition";
   188 val theoremK = "theorem";
   189 val lemmaK = "lemma";
   190 val corollaryK = "corollary";
   191 val internalK = Markup.internalK;
   192 
   193 
   194 
   195 (** attributes **)
   196 
   197 fun rule_attribute f (x, th) = (x, f x th);
   198 fun declaration_attribute f (x, th) = (f th x, th);
   199 
   200 fun apply_attributes mk dest =
   201   let
   202     fun app [] = I
   203       | app ((f: attribute) :: fs) = fn (x, th) => f (mk x, th) |>> dest |> app fs;
   204   in app end;
   205 
   206 val theory_attributes = apply_attributes Context.Theory Context.the_theory;
   207 val proof_attributes = apply_attributes Context.Proof Context.the_proof;
   208 
   209 fun no_attributes x = (x, []);
   210 fun simple_fact x = [(x, [])];
   211 
   212 
   213 (** read/certify terms (obsolete) **)    (*exception ERROR*)
   214 
   215 fun read_def_cterms (thy, types, sorts) used freeze sTs =
   216   let
   217     val (ts', tye) = Sign.read_def_terms (thy, types, sorts) used freeze sTs;
   218     val cts = map (Thm.cterm_of thy) ts'
   219       handle TYPE (msg, _, _) => error msg
   220            | TERM (msg, _) => error msg;
   221   in (cts, tye) end;
   222 
   223 fun read_cterm thy sT =
   224   let val ([ct], _) = read_def_cterms (thy, K NONE, K NONE) [] true [sT]
   225   in ct end;
   226 
   227 
   228 
   229 (** basic derived rules **)
   230 
   231 (*Elimination of implication
   232   A    A ==> B
   233   ------------
   234         B
   235 *)
   236 fun elim_implies thA thAB = Thm.implies_elim thAB thA;
   237 
   238 
   239 (* forall_elim_var(s) *)
   240 
   241 local
   242 
   243 fun forall_elim_vars_aux strip_vars i th =
   244   let
   245     val thy = Thm.theory_of_thm th;
   246     val {tpairs, prop, ...} = Thm.rep_thm th;
   247     val add_used = Term.fold_aterms
   248       (fn Var ((x, j), _) => if i = j then insert (op =) x else I | _ => I);
   249     val used = fold (fn (t, u) => add_used t o add_used u) tpairs (add_used prop []);
   250     val vars = strip_vars prop;
   251     val cvars = (Name.variant_list used (map #1 vars), vars)
   252       |> ListPair.map (fn (x, (_, T)) => Thm.cterm_of thy (Var ((x, i), T)));
   253   in fold Thm.forall_elim cvars th end;
   254 
   255 in
   256 
   257 val forall_elim_vars = forall_elim_vars_aux Term.strip_all_vars;
   258 
   259 fun forall_elim_var i th = forall_elim_vars_aux
   260   (fn Const ("all", _) $ Abs (a, T, _) => [(a, T)]
   261   | _ => raise THM ("forall_elim_vars", i, [th])) i th;
   262 
   263 end;
   264 
   265 
   266 (* unvarify: global schematic variables *)
   267 
   268 fun unvarify th =
   269   let
   270     val thy = Thm.theory_of_thm th;
   271     val cert = Thm.cterm_of thy;
   272     val certT = Thm.ctyp_of thy;
   273 
   274     val prop = Thm.full_prop_of th;
   275     val _ = map Logic.unvarify (prop :: Thm.hyps_of th)
   276       handle TERM (msg, _) => raise THM (msg, 0, [th]);
   277 
   278     val instT0 = rev (Term.add_tvars prop []) |> map (fn v as ((a, _), S) => (v, TFree (a, S)));
   279     val instT = map (fn (v, T) => (certT (TVar v), certT T)) instT0;
   280     val inst = rev (Term.add_vars prop []) |> map (fn ((a, i), T) =>
   281       let val T' = TermSubst.instantiateT instT0 T
   282       in (cert (Var ((a, i), T')), cert (Free ((a, T')))) end);
   283   in Thm.instantiate (instT, inst) th end;
   284 
   285 
   286 (* close_derivation *)
   287 
   288 fun close_derivation thm =
   289   if Thm.get_name thm = "" then Thm.put_name "" thm
   290   else thm;
   291 
   292 
   293 
   294 (** specification primitives **)
   295 
   296 fun add_axiom hyps (name, prop) thy =
   297   let
   298     val name' = if name = "" then "axiom_" ^ serial_string () else name;
   299     val prop' = Logic.list_implies (hyps, prop);
   300     val thy' = thy |> Theory.add_axioms_i [(name', prop')];
   301     val axm = unvarify (Thm.get_axiom_i thy' (Sign.full_name thy' name'));
   302     val prems = map (Thm.assume o Thm.cterm_of thy') hyps;
   303     val thm = fold elim_implies prems axm;
   304   in (thm, thy') end;
   305 
   306 fun add_def unchecked overloaded (name, prop) thy =
   307   let
   308     val tfrees = rev (map TFree (Term.add_tfrees prop []));
   309     val tfrees' = map (fn a => TFree (a, [])) (Name.invents Name.context Name.aT (length tfrees));
   310     val strip_sorts = tfrees ~~ tfrees';
   311     val recover_sorts = map (pairself (Thm.ctyp_of thy o Logic.varifyT)) (tfrees' ~~ tfrees);
   312 
   313     val prop' = Term.map_types (Term.map_atyps (perhaps (AList.lookup (op =) strip_sorts))) prop;
   314     val thy' = Theory.add_defs_i unchecked overloaded [(name, prop')] thy;
   315     val axm' = Thm.get_axiom_i thy' (Sign.full_name thy' name);
   316     val thm = unvarify (Thm.instantiate (recover_sorts, []) axm');
   317   in (thm, thy') end;
   318 
   319 open Thm;
   320 
   321 end;
   322 
   323 val op aconvc = Thm.aconvc;
   324 
   325 structure Thmtab = TableFun(type key = thm val ord = Thm.thm_ord);