author | wenzelm |
Sat, 30 Dec 2023 22:36:41 +0100 | |
changeset 79399 | 11b53e039f6f |
parent 79129 | 2933e71f4e09 |
child 79409 | e1895596e1b9 |
permissions | -rw-r--r-- |
20513 | 1 |
(* Title: Pure/term_subst.ML |
2 |
Author: Makarius |
|
3 |
||
32016 | 4 |
Efficient type/term substitution. |
20513 | 5 |
*) |
6 |
||
7 |
signature TERM_SUBST = |
|
8 |
sig |
|
32016 | 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 |
|
79399 | 12 |
val map_atypsT: typ Same.operation -> typ -> typ |
13 |
val map_types: typ Same.operation -> term -> term |
|
14 |
val map_aterms: term Same.operation -> term -> term |
|
74266 | 15 |
val generalizeT_same: Names.set -> int -> typ Same.operation |
16 |
val generalize_same: Names.set * Names.set -> int -> term Same.operation |
|
17 |
val generalizeT: Names.set -> int -> typ -> typ |
|
18 |
val generalize: Names.set * Names.set -> int -> term -> term |
|
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
19 |
val instantiateT_frees_same: typ TFrees.table -> typ Same.operation |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
20 |
val instantiate_frees_same: typ TFrees.table * term Frees.table -> term Same.operation |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
21 |
val instantiateT_frees: typ TFrees.table -> typ -> typ |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
22 |
val instantiate_frees: typ TFrees.table * term Frees.table -> term -> term |
74576 | 23 |
val instantiateT_maxidx: (typ * int) TVars.table -> typ -> int -> typ * int |
24 |
val instantiate_maxidx: (typ * int) TVars.table * (term * int) Vars.table -> |
|
25 |
term -> int -> term * int |
|
74577
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
26 |
val instantiate_beta_maxidx: (typ * int) TVars.table * (term * int) Vars.table -> |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
27 |
term -> int -> term * int |
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
28 |
val instantiateT_same: typ TVars.table -> typ Same.operation |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
29 |
val instantiate_same: typ TVars.table * term Vars.table -> term Same.operation |
74577
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
30 |
val instantiate_beta_same: typ TVars.table * term Vars.table -> term Same.operation |
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
31 |
val instantiateT: typ TVars.table -> typ -> typ |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
32 |
val instantiate: typ TVars.table * term Vars.table -> term -> term |
74577
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
33 |
val instantiate_beta: typ TVars.table * term Vars.table -> term -> term |
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
34 |
val zero_var_indexes_inst: Name.context -> term list -> typ TVars.table * term Vars.table |
68234 | 35 |
val zero_var_indexes: term -> term |
36 |
val zero_var_indexes_list: term list -> term list |
|
20513 | 37 |
end; |
38 |
||
31977 | 39 |
structure Term_Subst: TERM_SUBST = |
20513 | 40 |
struct |
41 |
||
31980 | 42 |
(* generic mapping *) |
43 |
||
44 |
fun map_atypsT_same f = |
|
45 |
let |
|
32020 | 46 |
fun typ (Type (a, Ts)) = Type (a, Same.map typ Ts) |
47 |
| typ T = f T; |
|
31980 | 48 |
in typ end; |
49 |
||
50 |
fun map_types_same f = |
|
51 |
let |
|
52 |
fun term (Const (a, T)) = Const (a, f T) |
|
53 |
| term (Free (a, T)) = Free (a, f T) |
|
54 |
| term (Var (v, T)) = Var (v, f T) |
|
32020 | 55 |
| term (Bound _) = raise Same.SAME |
31980 | 56 |
| term (Abs (x, T, t)) = |
32016 | 57 |
(Abs (x, f T, Same.commit term t) |
58 |
handle Same.SAME => Abs (x, T, term t)) |
|
59 |
| term (t $ u) = (term t $ Same.commit term u handle Same.SAME => t $ term u); |
|
31980 | 60 |
in term end; |
61 |
||
62 |
fun map_aterms_same f = |
|
63 |
let |
|
64 |
fun term (Abs (x, T, t)) = Abs (x, T, term t) |
|
32016 | 65 |
| term (t $ u) = (term t $ Same.commit term u handle Same.SAME => t $ term u) |
31980 | 66 |
| term a = f a; |
67 |
in term end; |
|
68 |
||
79399 | 69 |
val map_atypsT = Same.commit o map_atypsT_same; |
70 |
val map_types = Same.commit o map_types_same; |
|
71 |
val map_aterms = Same.commit o map_aterms_same; |
|
72 |
||
31980 | 73 |
|
20513 | 74 |
(* generalization of fixed variables *) |
75 |
||
74200
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
76 |
fun generalizeT_same tfrees idx ty = |
74266 | 77 |
if Names.is_empty tfrees then raise Same.SAME |
74200
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
78 |
else |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
79 |
let |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
80 |
fun gen (Type (a, Ts)) = Type (a, Same.map gen Ts) |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
81 |
| gen (TFree (a, S)) = |
74266 | 82 |
if Names.defined tfrees a then TVar ((a, idx), S) |
74200
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
83 |
else raise Same.SAME |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
84 |
| gen _ = raise Same.SAME; |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
85 |
in gen ty end; |
20513 | 86 |
|
74200
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
87 |
fun generalize_same (tfrees, frees) idx tm = |
74266 | 88 |
if Names.is_empty tfrees andalso Names.is_empty frees then raise Same.SAME |
74200
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
89 |
else |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
90 |
let |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
91 |
val genT = generalizeT_same tfrees idx; |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
92 |
fun gen (Free (x, T)) = |
74266 | 93 |
if Names.defined frees x then |
74200
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
94 |
Var (Name.clean_index (x, idx), Same.commit genT T) |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
95 |
else Free (x, genT T) |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
96 |
| gen (Var (xi, T)) = Var (xi, genT T) |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
97 |
| gen (Const (c, T)) = Const (c, genT T) |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
98 |
| gen (Bound _) = raise Same.SAME |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
99 |
| gen (Abs (x, T, t)) = |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
100 |
(Abs (x, genT T, Same.commit gen t) |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
101 |
handle Same.SAME => Abs (x, T, gen t)) |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
102 |
| gen (t $ u) = (gen t $ Same.commit gen u handle Same.SAME => t $ gen u); |
17090e27aae9
more scalable data structure (but: rarely used with > 5 arguments);
wenzelm
parents:
69023
diff
changeset
|
103 |
in gen tm end; |
20513 | 104 |
|
36766 | 105 |
fun generalizeT names i ty = Same.commit (generalizeT_same names i) ty; |
36620
e6bb250402b5
simplified/unified fundamental operations on types/terms/proofterms -- prefer Same.operation over "option" variant;
wenzelm
parents:
35408
diff
changeset
|
106 |
fun generalize names i tm = Same.commit (generalize_same names i) tm; |
20513 | 107 |
|
108 |
||
67698
67caf783b9ee
explicit operations to instantiate frees: typ, term, thm, morphism;
wenzelm
parents:
45395
diff
changeset
|
109 |
(* instantiation of free variables (types before terms) *) |
67caf783b9ee
explicit operations to instantiate frees: typ, term, thm, morphism;
wenzelm
parents:
45395
diff
changeset
|
110 |
|
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
111 |
fun instantiateT_frees_same instT ty = |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
112 |
if TFrees.is_empty instT then raise Same.SAME |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
113 |
else |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
114 |
let |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
115 |
fun subst (Type (a, Ts)) = Type (a, Same.map subst Ts) |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
116 |
| subst (TFree v) = |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
117 |
(case TFrees.lookup instT v of |
74578 | 118 |
SOME T' => T' |
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
119 |
| NONE => raise Same.SAME) |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
120 |
| subst _ = raise Same.SAME; |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
121 |
in subst ty end; |
67698
67caf783b9ee
explicit operations to instantiate frees: typ, term, thm, morphism;
wenzelm
parents:
45395
diff
changeset
|
122 |
|
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
123 |
fun instantiate_frees_same (instT, inst) tm = |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
124 |
if TFrees.is_empty instT andalso Frees.is_empty inst then raise Same.SAME |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
125 |
else |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
126 |
let |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
127 |
val substT = instantiateT_frees_same instT; |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
128 |
fun subst (Const (c, T)) = Const (c, substT T) |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
129 |
| subst (Free (x, T)) = |
79129 | 130 |
let val (T', same) = Same.commit_id substT T in |
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
131 |
(case Frees.lookup inst (x, T') of |
74578 | 132 |
SOME t' => t' |
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
133 |
| NONE => if same then raise Same.SAME else Free (x, T')) |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
134 |
end |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
135 |
| subst (Var (xi, T)) = Var (xi, substT T) |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
136 |
| subst (Bound _) = raise Same.SAME |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
137 |
| subst (Abs (x, T, t)) = |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
138 |
(Abs (x, substT T, Same.commit subst t) |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
139 |
handle Same.SAME => Abs (x, T, subst t)) |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
140 |
| subst (t $ u) = (subst t $ Same.commit subst u handle Same.SAME => t $ subst u); |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
141 |
in subst tm end; |
67698
67caf783b9ee
explicit operations to instantiate frees: typ, term, thm, morphism;
wenzelm
parents:
45395
diff
changeset
|
142 |
|
67caf783b9ee
explicit operations to instantiate frees: typ, term, thm, morphism;
wenzelm
parents:
45395
diff
changeset
|
143 |
fun instantiateT_frees instT ty = Same.commit (instantiateT_frees_same instT) ty; |
67caf783b9ee
explicit operations to instantiate frees: typ, term, thm, morphism;
wenzelm
parents:
45395
diff
changeset
|
144 |
fun instantiate_frees inst tm = Same.commit (instantiate_frees_same inst) tm; |
67caf783b9ee
explicit operations to instantiate frees: typ, term, thm, morphism;
wenzelm
parents:
45395
diff
changeset
|
145 |
|
67caf783b9ee
explicit operations to instantiate frees: typ, term, thm, morphism;
wenzelm
parents:
45395
diff
changeset
|
146 |
|
20513 | 147 |
(* instantiation of schematic variables (types before terms) -- recomputes maxidx *) |
148 |
||
149 |
local |
|
150 |
||
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
151 |
fun no_indexesT instT = TVars.map (fn _ => rpair ~1) instT; |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
152 |
fun no_indexes inst = Vars.map (fn _ => rpair ~1) inst; |
20513 | 153 |
|
36620
e6bb250402b5
simplified/unified fundamental operations on types/terms/proofterms -- prefer Same.operation over "option" variant;
wenzelm
parents:
35408
diff
changeset
|
154 |
fun instT_same maxidx instT ty = |
20513 | 155 |
let |
21184 | 156 |
fun maxify i = if i > ! maxidx then maxidx := i else (); |
157 |
||
20513 | 158 |
fun subst_typ (Type (a, Ts)) = Type (a, subst_typs Ts) |
159 |
| subst_typ (TVar ((a, i), S)) = |
|
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
160 |
(case TVars.lookup instT ((a, i), S) of |
74578 | 161 |
SOME (T', j) => (maxify j; T') |
32016 | 162 |
| NONE => (maxify i; raise Same.SAME)) |
163 |
| subst_typ _ = raise Same.SAME |
|
20513 | 164 |
and subst_typs (T :: Ts) = |
32016 | 165 |
(subst_typ T :: Same.commit subst_typs Ts |
166 |
handle Same.SAME => T :: subst_typs Ts) |
|
167 |
| subst_typs [] = raise Same.SAME; |
|
20513 | 168 |
in subst_typ ty end; |
169 |
||
36620
e6bb250402b5
simplified/unified fundamental operations on types/terms/proofterms -- prefer Same.operation over "option" variant;
wenzelm
parents:
35408
diff
changeset
|
170 |
fun inst_same maxidx (instT, inst) tm = |
20513 | 171 |
let |
21184 | 172 |
fun maxify i = if i > ! maxidx then maxidx := i else (); |
173 |
||
36620
e6bb250402b5
simplified/unified fundamental operations on types/terms/proofterms -- prefer Same.operation over "option" variant;
wenzelm
parents:
35408
diff
changeset
|
174 |
val substT = instT_same maxidx instT; |
20513 | 175 |
fun subst (Const (c, T)) = Const (c, substT T) |
176 |
| subst (Free (x, T)) = Free (x, substT T) |
|
177 |
| subst (Var ((x, i), T)) = |
|
79129 | 178 |
let val (T', same) = Same.commit_id substT T in |
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
179 |
(case Vars.lookup inst ((x, i), T') of |
74578 | 180 |
SOME (t', j) => (maxify j; t') |
32016 | 181 |
| NONE => (maxify i; if same then raise Same.SAME else Var ((x, i), T'))) |
20513 | 182 |
end |
32016 | 183 |
| subst (Bound _) = raise Same.SAME |
20513 | 184 |
| subst (Abs (x, T, t)) = |
74577
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
185 |
(Abs (x, substT T, subst_commit t) |
32016 | 186 |
handle Same.SAME => Abs (x, T, subst t)) |
74577
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
187 |
| subst (t $ u) = (subst t $ subst_commit u handle Same.SAME => t $ subst u) |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
188 |
and subst_commit t = Same.commit subst t; |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
189 |
in subst tm end; |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
190 |
|
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
191 |
(*version with local beta reduction*) |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
192 |
fun inst_beta_same maxidx (instT, inst) tm = |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
193 |
let |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
194 |
fun maxify i = if i > ! maxidx then maxidx := i else (); |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
195 |
|
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
196 |
val substT = instT_same maxidx instT; |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
197 |
|
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
198 |
fun expand_head t = |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
199 |
(case Term.head_of t of |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
200 |
Var ((x, i), T) => |
79129 | 201 |
let val (T', same) = Same.commit_id substT T in |
74577
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
202 |
(case Vars.lookup inst ((x, i), T') of |
74578 | 203 |
SOME (t', j) => (maxify j; SOME t') |
74577
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
204 |
| NONE => (maxify i; if same then NONE else SOME (Var ((x, i), T')))) |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
205 |
end |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
206 |
| _ => NONE); |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
207 |
|
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
208 |
fun subst t = |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
209 |
(case expand_head t of |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
210 |
NONE => |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
211 |
(case t of |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
212 |
Const (c, T) => Const (c, substT T) |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
213 |
| Free (x, T) => Free (x, substT T) |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
214 |
| Var _ => raise Same.SAME |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
215 |
| Bound _ => raise Same.SAME |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
216 |
| Abs (x, T, b) => |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
217 |
(Abs (x, substT T, subst_commit b) |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
218 |
handle Same.SAME => Abs (x, T, subst b)) |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
219 |
| _ $ _ => subst_comb t) |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
220 |
| SOME (u as Abs _) => Term.betapplys (u, map subst_commit (Term.args_of t)) |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
221 |
| SOME u => subst_head u t) |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
222 |
and subst_comb (t $ u) = (subst_comb t $ subst_commit u handle Same.SAME => t $ subst u) |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
223 |
| subst_comb (Var _) = raise Same.SAME |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
224 |
| subst_comb t = subst t |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
225 |
and subst_head h (t $ u) = subst_head h t $ subst_commit u |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
226 |
| subst_head h _ = h |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
227 |
and subst_commit t = Same.commit subst t; |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
228 |
|
20513 | 229 |
in subst tm end; |
230 |
||
231 |
in |
|
232 |
||
233 |
fun instantiateT_maxidx instT ty i = |
|
32738 | 234 |
let val maxidx = Unsynchronized.ref i |
36620
e6bb250402b5
simplified/unified fundamental operations on types/terms/proofterms -- prefer Same.operation over "option" variant;
wenzelm
parents:
35408
diff
changeset
|
235 |
in (Same.commit (instT_same maxidx instT) ty, ! maxidx) end; |
20513 | 236 |
|
237 |
fun instantiate_maxidx insts tm i = |
|
32738 | 238 |
let val maxidx = Unsynchronized.ref i |
36620
e6bb250402b5
simplified/unified fundamental operations on types/terms/proofterms -- prefer Same.operation over "option" variant;
wenzelm
parents:
35408
diff
changeset
|
239 |
in (Same.commit (inst_same maxidx insts) tm, ! maxidx) end; |
20513 | 240 |
|
74577
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
241 |
fun instantiate_beta_maxidx insts tm i = |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
242 |
let val maxidx = Unsynchronized.ref i |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
243 |
in (Same.commit (inst_beta_same maxidx insts) tm, ! maxidx) end; |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
244 |
|
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
245 |
|
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
246 |
fun instantiateT_same instT ty = |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
247 |
if TVars.is_empty instT then raise Same.SAME |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
248 |
else instT_same (Unsynchronized.ref ~1) (no_indexesT instT) ty; |
20513 | 249 |
|
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
250 |
fun instantiate_same (instT, inst) tm = |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
251 |
if TVars.is_empty instT andalso Vars.is_empty inst then raise Same.SAME |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
252 |
else inst_same (Unsynchronized.ref ~1) (no_indexesT instT, no_indexes inst) tm; |
20513 | 253 |
|
74577
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
254 |
fun instantiate_beta_same (instT, inst) tm = |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
255 |
if TVars.is_empty instT andalso Vars.is_empty inst then raise Same.SAME |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
256 |
else inst_beta_same (Unsynchronized.ref ~1) (no_indexesT instT, no_indexes inst) tm; |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
257 |
|
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
258 |
|
36766 | 259 |
fun instantiateT instT ty = Same.commit (instantiateT_same instT) ty; |
74577
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
260 |
|
36766 | 261 |
fun instantiate inst tm = Same.commit (instantiate_same inst) tm; |
262 |
||
74577
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
263 |
fun instantiate_beta inst tm = Same.commit (instantiate_beta_same inst) tm; |
d4829a7333e2
clarified instantiation: local beta reduction after substitution, as for Envir.expand_term_defs;
wenzelm
parents:
74576
diff
changeset
|
264 |
|
20513 | 265 |
end; |
266 |
||
267 |
||
268 |
(* zero var indexes *) |
|
269 |
||
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
270 |
fun zero_var_inst ins mk (v as ((x, i), X)) (inst, used) = |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
271 |
let val (x', used') = Name.variant (if Name.is_bound x then "u" else x) used |
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
272 |
in if x = x' andalso i = 0 then (inst, used') else (ins (v, mk ((x', 0), X)) inst, used') end; |
20513 | 273 |
|
69023
cef000855cf4
clarified standardization of variables, with proper treatment of local variables;
wenzelm
parents:
68234
diff
changeset
|
274 |
fun zero_var_indexes_inst used ts = |
20513 | 275 |
let |
45395
830c9b9b0d66
more scalable zero_var_indexes, depending on canonical order within table;
wenzelm
parents:
43326
diff
changeset
|
276 |
val (instT, _) = |
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
277 |
(TVars.empty, used) |> TVars.fold (zero_var_inst TVars.add TVar o #1) |
74232 | 278 |
(TVars.build (ts |> (fold o fold_types o fold_atyps) |
279 |
(fn TVar v => TVars.add (v, ()) | _ => I))); |
|
45395
830c9b9b0d66
more scalable zero_var_indexes, depending on canonical order within table;
wenzelm
parents:
43326
diff
changeset
|
280 |
val (inst, _) = |
74220
c49134ee16c1
more scalable data structure (but: rarely used many arguments);
wenzelm
parents:
74200
diff
changeset
|
281 |
(Vars.empty, used) |> Vars.fold (zero_var_inst Vars.add Var o #1) |
74232 | 282 |
(Vars.build (ts |> (fold o fold_aterms) |
283 |
(fn Var (xi, T) => Vars.add ((xi, instantiateT instT T), ()) | _ => I))); |
|
20513 | 284 |
in (instT, inst) end; |
285 |
||
69023
cef000855cf4
clarified standardization of variables, with proper treatment of local variables;
wenzelm
parents:
68234
diff
changeset
|
286 |
fun zero_var_indexes_list ts = map (instantiate (zero_var_indexes_inst Name.context ts)) ts; |
68234 | 287 |
val zero_var_indexes = singleton zero_var_indexes_list; |
20513 | 288 |
|
289 |
end; |