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