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