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