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