src/Pure/term_subst.ML
author wenzelm
Thu Oct 04 20:29:42 2007 +0200 (2007-10-04)
changeset 24850 0cfd722ab579
parent 21607 3698319f6503
child 29269 5c25a2012975
permissions -rw-r--r--
Name.uu, Name.aT;
wenzelm@20513
     1
(*  Title:      Pure/term_subst.ML
wenzelm@20513
     2
    ID:         $Id$
wenzelm@20513
     3
    Author:     Makarius
wenzelm@20513
     4
wenzelm@20513
     5
Efficient term substitution -- avoids copying.
wenzelm@20513
     6
*)
wenzelm@20513
     7
wenzelm@20513
     8
signature TERM_SUBST =
wenzelm@20513
     9
sig
wenzelm@20513
    10
  val generalize: string list * string list -> int -> term -> term
wenzelm@20513
    11
  val generalizeT: string list -> int -> typ -> typ
wenzelm@20513
    12
  val generalize_option: string list * string list -> int -> term -> term option
wenzelm@20513
    13
  val generalizeT_option: string list -> int -> typ -> typ option
wenzelm@20513
    14
  val instantiateT_maxidx: ((indexname * sort) * (typ * int)) list -> typ -> int -> typ * int
wenzelm@20513
    15
  val instantiate_maxidx:
wenzelm@20513
    16
    ((indexname * sort) * (typ * int)) list * ((indexname * typ) * (term * int)) list ->
wenzelm@20513
    17
    term -> int -> term * int
wenzelm@20513
    18
  val instantiate: ((indexname * sort) * typ) list * ((indexname * typ) * term) list ->
wenzelm@20513
    19
    term -> term
wenzelm@20513
    20
  val instantiateT: ((indexname * sort) * typ) list -> typ -> typ
wenzelm@20513
    21
  val instantiate_option: ((indexname * sort) * typ) list * ((indexname * typ) * term) list ->
wenzelm@20513
    22
    term -> term option
wenzelm@20513
    23
  val instantiateT_option: ((indexname * sort) * typ) list -> typ -> typ option
wenzelm@20513
    24
  val zero_var_indexes: term -> term
wenzelm@21607
    25
  val zero_var_indexes_inst: term list ->
wenzelm@20513
    26
    ((indexname * sort) * typ) list * ((indexname * typ) * term) list
wenzelm@20513
    27
end;
wenzelm@20513
    28
wenzelm@20513
    29
structure TermSubst: TERM_SUBST =
wenzelm@20513
    30
struct
wenzelm@20513
    31
wenzelm@20513
    32
(* generalization of fixed variables *)
wenzelm@20513
    33
wenzelm@20513
    34
local
wenzelm@20513
    35
wenzelm@20513
    36
exception SAME;
wenzelm@20513
    37
wenzelm@20513
    38
fun generalizeT_same [] _ _ = raise SAME
wenzelm@20513
    39
  | generalizeT_same tfrees idx ty =
wenzelm@20513
    40
      let
wenzelm@20513
    41
        fun gen_typ (Type (a, Ts)) = Type (a, gen_typs Ts)
wenzelm@20513
    42
          | gen_typ (TFree (a, S)) =
wenzelm@20513
    43
              if member (op =) tfrees a then TVar ((a, idx), S)
wenzelm@20513
    44
              else raise SAME
wenzelm@20513
    45
          | gen_typ _ = raise SAME
wenzelm@20513
    46
        and gen_typs (T :: Ts) =
wenzelm@20513
    47
            (gen_typ T :: (gen_typs Ts handle SAME => Ts)
wenzelm@20513
    48
              handle SAME => T :: gen_typs Ts)
wenzelm@20513
    49
          | gen_typs [] = raise SAME;
wenzelm@20513
    50
      in gen_typ ty end;
wenzelm@20513
    51
wenzelm@20513
    52
fun generalize_same ([], []) _ _ = raise SAME
wenzelm@20513
    53
  | generalize_same (tfrees, frees) idx tm =
wenzelm@20513
    54
      let
wenzelm@20513
    55
        val genT = generalizeT_same tfrees idx;
wenzelm@20513
    56
        fun gen (Free (x, T)) =
wenzelm@20513
    57
              if member (op =) frees x then
wenzelm@20513
    58
                Var (Name.clean_index (x, idx), genT T handle SAME => T)
wenzelm@20513
    59
              else Free (x, genT T)
wenzelm@20513
    60
          | gen (Var (xi, T)) = Var (xi, genT T)
wenzelm@20513
    61
          | gen (Const (c, T)) = Const (c, genT T)
wenzelm@20513
    62
          | gen (Bound _) = raise SAME
wenzelm@20513
    63
          | gen (Abs (x, T, t)) =
wenzelm@20513
    64
              (Abs (x, genT T, gen t handle SAME => t)
wenzelm@20513
    65
                handle SAME => Abs (x, T, gen t))
wenzelm@20513
    66
          | gen (t $ u) = (gen t $ (gen u handle SAME => u) handle SAME => t $ gen u);
wenzelm@20513
    67
      in gen tm end;
wenzelm@20513
    68
wenzelm@20513
    69
in
wenzelm@20513
    70
wenzelm@20513
    71
fun generalize names i tm = generalize_same names i tm handle SAME => tm;
wenzelm@20513
    72
fun generalizeT names i ty = generalizeT_same names i ty handle SAME => ty;
wenzelm@20513
    73
wenzelm@20513
    74
fun generalize_option names i tm = SOME (generalize_same names i tm) handle SAME => NONE;
wenzelm@20513
    75
fun generalizeT_option names i ty = SOME (generalizeT_same names i ty) handle SAME => NONE;
wenzelm@20513
    76
wenzelm@20513
    77
end;
wenzelm@20513
    78
wenzelm@20513
    79
wenzelm@20513
    80
(* instantiation of schematic variables (types before terms) -- recomputes maxidx *)
wenzelm@20513
    81
wenzelm@20513
    82
local
wenzelm@20513
    83
wenzelm@20513
    84
fun no_index (x, y) = (x, (y, ~1));
wenzelm@20513
    85
fun no_indexes1 inst = map no_index inst;
wenzelm@20513
    86
fun no_indexes2 (inst1, inst2) = (map no_index inst1, map no_index inst2);
wenzelm@20513
    87
wenzelm@20513
    88
exception SAME;
wenzelm@20513
    89
wenzelm@21184
    90
fun instantiateT_same maxidx instT ty =
wenzelm@20513
    91
  let
wenzelm@21184
    92
    fun maxify i = if i > ! maxidx then maxidx := i else ();
wenzelm@21184
    93
wenzelm@20513
    94
    fun subst_typ (Type (a, Ts)) = Type (a, subst_typs Ts)
wenzelm@20513
    95
      | subst_typ (TVar ((a, i), S)) =
wenzelm@20513
    96
          (case AList.lookup Term.eq_tvar instT ((a, i), S) of
wenzelm@20513
    97
            SOME (T, j) => (maxify j; T)
wenzelm@20513
    98
          | NONE => (maxify i; raise SAME))
wenzelm@20513
    99
      | subst_typ _ = raise SAME
wenzelm@20513
   100
    and subst_typs (T :: Ts) =
wenzelm@20513
   101
        (subst_typ T :: (subst_typs Ts handle SAME => Ts)
wenzelm@20513
   102
          handle SAME => T :: subst_typs Ts)
wenzelm@20513
   103
      | subst_typs [] = raise SAME;
wenzelm@20513
   104
  in subst_typ ty end;
wenzelm@20513
   105
wenzelm@21184
   106
fun instantiate_same maxidx (instT, inst) tm =
wenzelm@20513
   107
  let
wenzelm@21184
   108
    fun maxify i = if i > ! maxidx then maxidx := i else ();
wenzelm@21184
   109
wenzelm@21184
   110
    val substT = instantiateT_same maxidx instT;
wenzelm@20513
   111
    fun subst (Const (c, T)) = Const (c, substT T)
wenzelm@20513
   112
      | subst (Free (x, T)) = Free (x, substT T)
wenzelm@20513
   113
      | subst (Var ((x, i), T)) =
wenzelm@20513
   114
          let val (T', same) = (substT T, false) handle SAME => (T, true) in
wenzelm@20513
   115
            (case AList.lookup Term.eq_var inst ((x, i), T') of
wenzelm@20513
   116
               SOME (t, j) => (maxify j; t)
wenzelm@20513
   117
             | NONE => (maxify i; if same then raise SAME else Var ((x, i), T')))
wenzelm@20513
   118
          end
wenzelm@20513
   119
      | subst (Bound _) = raise SAME
wenzelm@20513
   120
      | subst (Abs (x, T, t)) =
wenzelm@20513
   121
          (Abs (x, substT T, subst t handle SAME => t)
wenzelm@20513
   122
            handle SAME => Abs (x, T, subst t))
wenzelm@20513
   123
      | subst (t $ u) = (subst t $ (subst u handle SAME => u) handle SAME => t $ subst u);
wenzelm@20513
   124
  in subst tm end;
wenzelm@20513
   125
wenzelm@20513
   126
in
wenzelm@20513
   127
wenzelm@20513
   128
fun instantiateT_maxidx instT ty i =
wenzelm@21184
   129
  let val maxidx = ref i
wenzelm@21184
   130
  in (instantiateT_same maxidx instT ty handle SAME => ty, ! maxidx) end;
wenzelm@20513
   131
wenzelm@20513
   132
fun instantiate_maxidx insts tm i =
wenzelm@21184
   133
  let val maxidx = ref i
wenzelm@21184
   134
  in (instantiate_same maxidx insts tm handle SAME => tm, ! maxidx) end;
wenzelm@20513
   135
wenzelm@21315
   136
fun instantiateT [] ty = ty
wenzelm@21315
   137
  | instantiateT instT ty =
wenzelm@21315
   138
      (instantiateT_same (ref ~1) (no_indexes1 instT) ty handle SAME => ty);
wenzelm@21184
   139
wenzelm@21315
   140
fun instantiate ([], []) tm = tm
wenzelm@21315
   141
  | instantiate insts tm =
wenzelm@21315
   142
      (instantiate_same (ref ~1) (no_indexes2 insts) tm handle SAME => tm);
wenzelm@20513
   143
wenzelm@21315
   144
fun instantiateT_option [] _ = NONE
wenzelm@21315
   145
  | instantiateT_option instT ty =
wenzelm@21315
   146
      (SOME (instantiateT_same (ref ~1) (no_indexes1 instT) ty) handle SAME => NONE);
wenzelm@20513
   147
wenzelm@21315
   148
fun instantiate_option ([], []) _ = NONE
wenzelm@21315
   149
  | instantiate_option insts tm =
wenzelm@21315
   150
      (SOME (instantiate_same (ref ~1) (no_indexes2 insts) tm) handle SAME => NONE);
wenzelm@20513
   151
wenzelm@20513
   152
end;
wenzelm@20513
   153
wenzelm@20513
   154
wenzelm@20513
   155
(* zero var indexes *)
wenzelm@20513
   156
wenzelm@20513
   157
fun zero_var_inst vars =
wenzelm@20513
   158
  fold (fn v as ((x, i), X) => fn (inst, used) =>
wenzelm@20513
   159
    let
wenzelm@20513
   160
      val ([x'], used') = Name.variants [if Name.is_bound x then "u" else x] used;
wenzelm@20513
   161
    in if x = x' andalso i = 0 then (inst, used') else ((v, ((x', 0), X)) :: inst, used') end)
wenzelm@20513
   162
  vars ([], Name.context) |> #1;
wenzelm@20513
   163
wenzelm@21607
   164
fun zero_var_indexes_inst ts =
wenzelm@20513
   165
  let
wenzelm@21607
   166
    val tvars = sort Term.tvar_ord (fold Term.add_tvars ts []);
wenzelm@21607
   167
    val instT = map (apsnd TVar) (zero_var_inst tvars);
wenzelm@21607
   168
    val vars = sort Term.var_ord (map (apsnd (instantiateT instT)) (fold Term.add_vars ts []));
wenzelm@21607
   169
    val inst = map (apsnd Var) (zero_var_inst vars);
wenzelm@20513
   170
  in (instT, inst) end;
wenzelm@20513
   171
wenzelm@21607
   172
fun zero_var_indexes t = instantiate (zero_var_indexes_inst [t]) t;
wenzelm@20513
   173
wenzelm@20513
   174
end;