# HG changeset patch # User wenzelm # Date 1158056177 -7200 # Node ID 4294eb25228341966953331619680f389af92f08 # Parent a041c2afb52e3029360b8697e17c0b853e10a9de Efficient term substitution -- avoids copying. moved here from term.ML; added instantiate_maxidx; diff -r a041c2afb52e -r 4294eb252283 src/Pure/term_subst.ML --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/Pure/term_subst.ML Tue Sep 12 12:16:17 2006 +0200 @@ -0,0 +1,164 @@ +(* Title: Pure/term_subst.ML + ID: $Id$ + Author: Makarius + +Efficient term substitution -- avoids copying. +*) + +signature TERM_SUBST = +sig + val generalize: string list * string list -> int -> term -> term + val generalizeT: string list -> int -> typ -> typ + val generalize_option: string list * string list -> int -> term -> term option + val generalizeT_option: string list -> int -> typ -> typ option + val instantiateT_maxidx: ((indexname * sort) * (typ * int)) list -> typ -> int -> typ * int + val instantiate_maxidx: + ((indexname * sort) * (typ * int)) list * ((indexname * typ) * (term * int)) list -> + term -> int -> term * int + val instantiate: ((indexname * sort) * typ) list * ((indexname * typ) * term) list -> + term -> term + val instantiateT: ((indexname * sort) * typ) list -> typ -> typ + val instantiate_option: ((indexname * sort) * typ) list * ((indexname * typ) * term) list -> + term -> term option + val instantiateT_option: ((indexname * sort) * typ) list -> typ -> typ option + val zero_var_indexes: term -> term + val zero_var_indexes_inst: term -> + ((indexname * sort) * typ) list * ((indexname * typ) * term) list +end; + +structure TermSubst: TERM_SUBST = +struct + +(* generalization of fixed variables *) + +local + +exception SAME; + +fun generalizeT_same [] _ _ = raise SAME + | generalizeT_same tfrees idx ty = + let + fun gen_typ (Type (a, Ts)) = Type (a, gen_typs Ts) + | gen_typ (TFree (a, S)) = + if member (op =) tfrees a then TVar ((a, idx), S) + else raise SAME + | gen_typ _ = raise SAME + and gen_typs (T :: Ts) = + (gen_typ T :: (gen_typs Ts handle SAME => Ts) + handle SAME => T :: gen_typs Ts) + | gen_typs [] = raise SAME; + in gen_typ ty end; + +fun generalize_same ([], []) _ _ = raise SAME + | generalize_same (tfrees, frees) idx tm = + let + val genT = generalizeT_same tfrees idx; + fun gen (Free (x, T)) = + if member (op =) frees x then + Var (Name.clean_index (x, idx), genT T handle SAME => T) + else Free (x, genT T) + | gen (Var (xi, T)) = Var (xi, genT T) + | gen (Const (c, T)) = Const (c, genT T) + | gen (Bound _) = raise SAME + | gen (Abs (x, T, t)) = + (Abs (x, genT T, gen t handle SAME => t) + handle SAME => Abs (x, T, gen t)) + | gen (t $ u) = (gen t $ (gen u handle SAME => u) handle SAME => t $ gen u); + in gen tm end; + +in + +fun generalize names i tm = generalize_same names i tm handle SAME => tm; +fun generalizeT names i ty = generalizeT_same names i ty handle SAME => ty; + +fun generalize_option names i tm = SOME (generalize_same names i tm) handle SAME => NONE; +fun generalizeT_option names i ty = SOME (generalizeT_same names i ty) handle SAME => NONE; + +end; + + +(* instantiation of schematic variables (types before terms) -- recomputes maxidx *) + +local + +val maxidx = ref ~1; +fun maxify i = if i > ! maxidx then maxidx := i else (); + +fun no_index (x, y) = (x, (y, ~1)); +fun no_indexes1 inst = map no_index inst; +fun no_indexes2 (inst1, inst2) = (map no_index inst1, map no_index inst2); + +exception SAME; + +fun instantiateT_same instT ty = + let + fun subst_typ (Type (a, Ts)) = Type (a, subst_typs Ts) + | subst_typ (TVar ((a, i), S)) = + (case AList.lookup Term.eq_tvar instT ((a, i), S) of + SOME (T, j) => (maxify j; T) + | NONE => (maxify i; raise SAME)) + | subst_typ _ = raise SAME + and subst_typs (T :: Ts) = + (subst_typ T :: (subst_typs Ts handle SAME => Ts) + handle SAME => T :: subst_typs Ts) + | subst_typs [] = raise SAME; + in subst_typ ty end; + +fun instantiate_same (instT, inst) tm = + let + val substT = instantiateT_same instT; + fun subst (Const (c, T)) = Const (c, substT T) + | subst (Free (x, T)) = Free (x, substT T) + | subst (Var ((x, i), T)) = + let val (T', same) = (substT T, false) handle SAME => (T, true) in + (case AList.lookup Term.eq_var inst ((x, i), T') of + SOME (t, j) => (maxify j; t) + | NONE => (maxify i; if same then raise SAME else Var ((x, i), T'))) + end + | subst (Bound _) = raise SAME + | subst (Abs (x, T, t)) = + (Abs (x, substT T, subst t handle SAME => t) + handle SAME => Abs (x, T, subst t)) + | subst (t $ u) = (subst t $ (subst u handle SAME => u) handle SAME => t $ subst u); + in subst tm end; + +in + +fun instantiateT_maxidx instT ty i = + (maxidx := i; (instantiateT_same instT ty handle SAME => ty, ! maxidx)); + +fun instantiate_maxidx insts tm i = + (maxidx := i; (instantiate_same insts tm handle SAME => tm, ! maxidx)); + +fun instantiateT instT ty = instantiateT_same (no_indexes1 instT) ty handle SAME => ty; +fun instantiate insts tm = instantiate_same (no_indexes2 insts) tm handle SAME => tm; + +fun instantiateT_option instT ty = + SOME (instantiateT_same (no_indexes1 instT) ty) handle SAME => NONE; + +fun instantiate_option insts tm = + SOME (instantiate_same (no_indexes2 insts) tm) handle SAME => NONE; + +end; + + +(* zero var indexes *) + +fun zero_var_inst vars = + fold (fn v as ((x, i), X) => fn (inst, used) => + let + val ([x'], used') = Name.variants [if Name.is_bound x then "u" else x] used; + in if x = x' andalso i = 0 then (inst, used') else ((v, ((x', 0), X)) :: inst, used') end) + vars ([], Name.context) |> #1; + +fun zero_var_indexes_inst tm = + let + val instT = zero_var_inst (sort Term.tvar_ord (Term.add_tvars tm [])) |> map (apsnd TVar); + val inst = + zero_var_inst (sort Term.var_ord (map (apsnd (instantiateT instT)) (Term.add_vars tm []))) + |> map (apsnd Var); + in (instT, inst) end; + +fun zero_var_indexes tm = instantiate (zero_var_indexes_inst tm) tm; + +end;