src/Pure/term_subst.ML
author haftmann
Tue Oct 20 16:13:01 2009 +0200 (2009-10-20)
changeset 33037 b22e44496dc2
parent 32738 15bb09ca0378
child 35408 b48ab741683b
permissions -rw-r--r--
replaced old_style infixes eq_set, subset, union, inter and variants by generic versions
wenzelm@20513
     1
(*  Title:      Pure/term_subst.ML
wenzelm@20513
     2
    Author:     Makarius
wenzelm@20513
     3
wenzelm@32016
     4
Efficient type/term substitution.
wenzelm@20513
     5
*)
wenzelm@20513
     6
wenzelm@20513
     7
signature TERM_SUBST =
wenzelm@20513
     8
sig
wenzelm@32016
     9
  val map_atypsT_same: typ Same.operation -> typ Same.operation
wenzelm@32016
    10
  val map_types_same: typ Same.operation -> term Same.operation
wenzelm@32016
    11
  val map_aterms_same: term Same.operation -> term Same.operation
wenzelm@31980
    12
  val map_atypsT_option: (typ -> typ option) -> typ -> typ option
wenzelm@31980
    13
  val map_atyps_option: (typ -> typ option) -> term -> term option
wenzelm@31980
    14
  val map_types_option: (typ -> typ option) -> term -> term option
wenzelm@31980
    15
  val map_aterms_option: (term -> term option) -> term -> term option
wenzelm@20513
    16
  val generalize: string list * string list -> int -> term -> term
wenzelm@20513
    17
  val generalizeT: string list -> int -> typ -> typ
wenzelm@20513
    18
  val generalize_option: string list * string list -> int -> term -> term option
wenzelm@20513
    19
  val generalizeT_option: string list -> int -> typ -> typ option
wenzelm@20513
    20
  val instantiateT_maxidx: ((indexname * sort) * (typ * int)) list -> typ -> int -> typ * int
wenzelm@20513
    21
  val instantiate_maxidx:
wenzelm@20513
    22
    ((indexname * sort) * (typ * int)) list * ((indexname * typ) * (term * int)) list ->
wenzelm@20513
    23
    term -> int -> term * int
wenzelm@20513
    24
  val instantiate: ((indexname * sort) * typ) list * ((indexname * typ) * term) list ->
wenzelm@20513
    25
    term -> term
wenzelm@20513
    26
  val instantiateT: ((indexname * sort) * typ) list -> typ -> typ
wenzelm@20513
    27
  val instantiate_option: ((indexname * sort) * typ) list * ((indexname * typ) * term) list ->
wenzelm@20513
    28
    term -> term option
wenzelm@20513
    29
  val instantiateT_option: ((indexname * sort) * typ) list -> typ -> typ option
wenzelm@20513
    30
  val zero_var_indexes: term -> term
wenzelm@21607
    31
  val zero_var_indexes_inst: term list ->
wenzelm@20513
    32
    ((indexname * sort) * typ) list * ((indexname * typ) * term) list
wenzelm@20513
    33
end;
wenzelm@20513
    34
wenzelm@31977
    35
structure Term_Subst: TERM_SUBST =
wenzelm@20513
    36
struct
wenzelm@20513
    37
wenzelm@31980
    38
(* generic mapping *)
wenzelm@31980
    39
wenzelm@31980
    40
fun map_atypsT_same f =
wenzelm@31980
    41
  let
wenzelm@32020
    42
    fun typ (Type (a, Ts)) = Type (a, Same.map typ Ts)
wenzelm@32020
    43
      | typ T = f T;
wenzelm@31980
    44
  in typ end;
wenzelm@31980
    45
wenzelm@31980
    46
fun map_types_same f =
wenzelm@31980
    47
  let
wenzelm@31980
    48
    fun term (Const (a, T)) = Const (a, f T)
wenzelm@31980
    49
      | term (Free (a, T)) = Free (a, f T)
wenzelm@31980
    50
      | term (Var (v, T)) = Var (v, f T)
wenzelm@32020
    51
      | term (Bound _) = raise Same.SAME
wenzelm@31980
    52
      | term (Abs (x, T, t)) =
wenzelm@32016
    53
          (Abs (x, f T, Same.commit term t)
wenzelm@32016
    54
            handle Same.SAME => Abs (x, T, term t))
wenzelm@32016
    55
      | term (t $ u) = (term t $ Same.commit term u handle Same.SAME => t $ term u);
wenzelm@31980
    56
  in term end;
wenzelm@31980
    57
wenzelm@31980
    58
fun map_aterms_same f =
wenzelm@31980
    59
  let
wenzelm@31980
    60
    fun term (Abs (x, T, t)) = Abs (x, T, term t)
wenzelm@32016
    61
      | term (t $ u) = (term t $ Same.commit term u handle Same.SAME => t $ term u)
wenzelm@31980
    62
      | term a = f a;
wenzelm@31980
    63
  in term end;
wenzelm@31980
    64
wenzelm@32016
    65
val map_atypsT_option = Same.capture o map_atypsT_same o Same.function;
wenzelm@32016
    66
val map_atyps_option = Same.capture o map_types_same o map_atypsT_same o Same.function;
wenzelm@32016
    67
val map_types_option = Same.capture o map_types_same o Same.function;
wenzelm@32016
    68
val map_aterms_option = Same.capture o map_aterms_same o Same.function;
wenzelm@31980
    69
wenzelm@31980
    70
wenzelm@20513
    71
(* generalization of fixed variables *)
wenzelm@20513
    72
wenzelm@20513
    73
local
wenzelm@20513
    74
wenzelm@32016
    75
fun generalizeT_same [] _ _ = raise Same.SAME
wenzelm@20513
    76
  | generalizeT_same tfrees idx ty =
wenzelm@20513
    77
      let
wenzelm@32020
    78
        fun gen (Type (a, Ts)) = Type (a, Same.map gen Ts)
wenzelm@32020
    79
          | gen (TFree (a, S)) =
wenzelm@20513
    80
              if member (op =) tfrees a then TVar ((a, idx), S)
wenzelm@32016
    81
              else raise Same.SAME
wenzelm@32020
    82
          | gen _ = raise Same.SAME;
wenzelm@32020
    83
      in gen ty end;
wenzelm@20513
    84
wenzelm@32016
    85
fun generalize_same ([], []) _ _ = raise Same.SAME
wenzelm@20513
    86
  | generalize_same (tfrees, frees) idx tm =
wenzelm@20513
    87
      let
wenzelm@20513
    88
        val genT = generalizeT_same tfrees idx;
wenzelm@20513
    89
        fun gen (Free (x, T)) =
wenzelm@20513
    90
              if member (op =) frees x then
wenzelm@32016
    91
                Var (Name.clean_index (x, idx), Same.commit genT T)
wenzelm@20513
    92
              else Free (x, genT T)
wenzelm@20513
    93
          | gen (Var (xi, T)) = Var (xi, genT T)
wenzelm@20513
    94
          | gen (Const (c, T)) = Const (c, genT T)
wenzelm@32016
    95
          | gen (Bound _) = raise Same.SAME
wenzelm@20513
    96
          | gen (Abs (x, T, t)) =
wenzelm@32016
    97
              (Abs (x, genT T, Same.commit gen t)
wenzelm@32016
    98
                handle Same.SAME => Abs (x, T, gen t))
wenzelm@32016
    99
          | gen (t $ u) = (gen t $ Same.commit gen u handle Same.SAME => t $ gen u);
wenzelm@20513
   100
      in gen tm end;
wenzelm@20513
   101
wenzelm@20513
   102
in
wenzelm@20513
   103
wenzelm@32016
   104
fun generalize names i tm = generalize_same names i tm handle Same.SAME => tm;
wenzelm@32016
   105
fun generalizeT names i ty = generalizeT_same names i ty handle Same.SAME => ty;
wenzelm@20513
   106
wenzelm@32016
   107
fun generalize_option names i tm = SOME (generalize_same names i tm) handle Same.SAME => NONE;
wenzelm@32016
   108
fun generalizeT_option names i ty = SOME (generalizeT_same names i ty) handle Same.SAME => NONE;
wenzelm@20513
   109
wenzelm@20513
   110
end;
wenzelm@20513
   111
wenzelm@20513
   112
wenzelm@20513
   113
(* instantiation of schematic variables (types before terms) -- recomputes maxidx *)
wenzelm@20513
   114
wenzelm@20513
   115
local
wenzelm@20513
   116
wenzelm@20513
   117
fun no_index (x, y) = (x, (y, ~1));
wenzelm@20513
   118
fun no_indexes1 inst = map no_index inst;
wenzelm@20513
   119
fun no_indexes2 (inst1, inst2) = (map no_index inst1, map no_index inst2);
wenzelm@20513
   120
wenzelm@21184
   121
fun instantiateT_same maxidx instT ty =
wenzelm@20513
   122
  let
wenzelm@21184
   123
    fun maxify i = if i > ! maxidx then maxidx := i else ();
wenzelm@21184
   124
wenzelm@20513
   125
    fun subst_typ (Type (a, Ts)) = Type (a, subst_typs Ts)
wenzelm@20513
   126
      | subst_typ (TVar ((a, i), S)) =
wenzelm@20513
   127
          (case AList.lookup Term.eq_tvar instT ((a, i), S) of
wenzelm@20513
   128
            SOME (T, j) => (maxify j; T)
wenzelm@32016
   129
          | NONE => (maxify i; raise Same.SAME))
wenzelm@32016
   130
      | subst_typ _ = raise Same.SAME
wenzelm@20513
   131
    and subst_typs (T :: Ts) =
wenzelm@32016
   132
        (subst_typ T :: Same.commit subst_typs Ts
wenzelm@32016
   133
          handle Same.SAME => T :: subst_typs Ts)
wenzelm@32016
   134
      | subst_typs [] = raise Same.SAME;
wenzelm@20513
   135
  in subst_typ ty end;
wenzelm@20513
   136
wenzelm@21184
   137
fun instantiate_same maxidx (instT, inst) tm =
wenzelm@20513
   138
  let
wenzelm@21184
   139
    fun maxify i = if i > ! maxidx then maxidx := i else ();
wenzelm@21184
   140
wenzelm@21184
   141
    val substT = instantiateT_same maxidx instT;
wenzelm@20513
   142
    fun subst (Const (c, T)) = Const (c, substT T)
wenzelm@20513
   143
      | subst (Free (x, T)) = Free (x, substT T)
wenzelm@20513
   144
      | subst (Var ((x, i), T)) =
wenzelm@32016
   145
          let val (T', same) = (substT T, false) handle Same.SAME => (T, true) in
wenzelm@20513
   146
            (case AList.lookup Term.eq_var inst ((x, i), T') of
wenzelm@20513
   147
               SOME (t, j) => (maxify j; t)
wenzelm@32016
   148
             | NONE => (maxify i; if same then raise Same.SAME else Var ((x, i), T')))
wenzelm@20513
   149
          end
wenzelm@32016
   150
      | subst (Bound _) = raise Same.SAME
wenzelm@20513
   151
      | subst (Abs (x, T, t)) =
wenzelm@32016
   152
          (Abs (x, substT T, Same.commit subst t)
wenzelm@32016
   153
            handle Same.SAME => Abs (x, T, subst t))
wenzelm@32016
   154
      | subst (t $ u) = (subst t $ Same.commit subst u handle Same.SAME => t $ subst u);
wenzelm@20513
   155
  in subst tm end;
wenzelm@20513
   156
wenzelm@20513
   157
in
wenzelm@20513
   158
wenzelm@20513
   159
fun instantiateT_maxidx instT ty i =
wenzelm@32738
   160
  let val maxidx = Unsynchronized.ref i
wenzelm@32016
   161
  in (instantiateT_same maxidx instT ty handle Same.SAME => ty, ! maxidx) end;
wenzelm@20513
   162
wenzelm@20513
   163
fun instantiate_maxidx insts tm i =
wenzelm@32738
   164
  let val maxidx = Unsynchronized.ref i
wenzelm@32016
   165
  in (instantiate_same maxidx insts tm handle Same.SAME => tm, ! maxidx) end;
wenzelm@20513
   166
wenzelm@21315
   167
fun instantiateT [] ty = ty
wenzelm@21315
   168
  | instantiateT instT ty =
wenzelm@32738
   169
      (instantiateT_same (Unsynchronized.ref ~1) (no_indexes1 instT) ty
wenzelm@32738
   170
        handle Same.SAME => ty);
wenzelm@21184
   171
wenzelm@21315
   172
fun instantiate ([], []) tm = tm
wenzelm@21315
   173
  | instantiate insts tm =
wenzelm@32738
   174
      (instantiate_same (Unsynchronized.ref ~1) (no_indexes2 insts) tm
wenzelm@32738
   175
        handle Same.SAME => tm);
wenzelm@20513
   176
wenzelm@21315
   177
fun instantiateT_option [] _ = NONE
wenzelm@21315
   178
  | instantiateT_option instT ty =
wenzelm@32738
   179
      (SOME (instantiateT_same (Unsynchronized.ref ~1) (no_indexes1 instT) ty)
wenzelm@32738
   180
        handle Same.SAME => NONE);
wenzelm@20513
   181
wenzelm@21315
   182
fun instantiate_option ([], []) _ = NONE
wenzelm@21315
   183
  | instantiate_option insts tm =
wenzelm@32738
   184
      (SOME (instantiate_same (Unsynchronized.ref ~1) (no_indexes2 insts) tm)
wenzelm@32738
   185
        handle Same.SAME => NONE);
wenzelm@20513
   186
wenzelm@20513
   187
end;
wenzelm@20513
   188
wenzelm@20513
   189
wenzelm@20513
   190
(* zero var indexes *)
wenzelm@20513
   191
wenzelm@20513
   192
fun zero_var_inst vars =
wenzelm@20513
   193
  fold (fn v as ((x, i), X) => fn (inst, used) =>
wenzelm@20513
   194
    let
wenzelm@20513
   195
      val ([x'], used') = Name.variants [if Name.is_bound x then "u" else x] used;
wenzelm@20513
   196
    in if x = x' andalso i = 0 then (inst, used') else ((v, ((x', 0), X)) :: inst, used') end)
wenzelm@20513
   197
  vars ([], Name.context) |> #1;
wenzelm@20513
   198
wenzelm@21607
   199
fun zero_var_indexes_inst ts =
wenzelm@20513
   200
  let
wenzelm@29269
   201
    val tvars = sort TermOrd.tvar_ord (fold Term.add_tvars ts []);
wenzelm@21607
   202
    val instT = map (apsnd TVar) (zero_var_inst tvars);
wenzelm@29269
   203
    val vars = sort TermOrd.var_ord (map (apsnd (instantiateT instT)) (fold Term.add_vars ts []));
wenzelm@21607
   204
    val inst = map (apsnd Var) (zero_var_inst vars);
wenzelm@20513
   205
  in (instT, inst) end;
wenzelm@20513
   206
wenzelm@21607
   207
fun zero_var_indexes t = instantiate (zero_var_indexes_inst [t]) t;
wenzelm@20513
   208
wenzelm@20513
   209
end;