78 [rtrancl_beta_AppL,rtrancl_beta_AppR,rtrancl_trans]) 1); |
78 [rtrancl_beta_AppL,rtrancl_beta_AppR,rtrancl_trans]) 1); |
79 qed "rtrancl_beta_App"; |
79 qed "rtrancl_beta_App"; |
80 |
80 |
81 (*** subst and lift ***) |
81 (*** subst and lift ***) |
82 |
82 |
83 val split_ss = !simpset delsimps [less_Suc_eq,subst_Var] |
83 fun addsplit ss = ss addsimps [subst_Var] setloop (split_tac [expand_if]); |
84 addsimps [subst_Var] |
|
85 setloop (split_tac [expand_if]); |
|
86 |
84 |
87 goal Lambda.thy "(Var k)[u/k] = u"; |
85 goal Lambda.thy "(Var k)[u/k] = u"; |
88 by (asm_full_simp_tac split_ss 1); |
86 by (asm_full_simp_tac(addsplit(!simpset)) 1); |
89 qed "subst_eq"; |
87 qed "subst_eq"; |
90 |
88 |
91 goal Lambda.thy "!!s. i<j ==> (Var j)[u/i] = Var(pred j)"; |
89 goal Lambda.thy "!!s. i<j ==> (Var j)[u/i] = Var(pred j)"; |
92 by (asm_full_simp_tac split_ss 1); |
90 by (asm_full_simp_tac(addsplit(!simpset)) 1); |
93 qed "subst_gt"; |
91 qed "subst_gt"; |
94 |
92 |
95 goal Lambda.thy "!!s. j<i ==> (Var j)[u/i] = Var(j)"; |
93 goal Lambda.thy "!!s. j<i ==> (Var j)[u/i] = Var(j)"; |
96 by (asm_full_simp_tac (split_ss addsimps |
94 by (asm_full_simp_tac (addsplit(!simpset) addsimps |
97 [less_not_refl2 RS not_sym,less_SucI]) 1); |
95 [less_not_refl2 RS not_sym,less_SucI]) 1); |
98 qed "subst_lt"; |
96 qed "subst_lt"; |
99 |
97 |
100 Addsimps [subst_eq,subst_gt,subst_lt]; |
98 Addsimps [subst_eq,subst_gt,subst_lt]; |
101 val ss = !simpset delsimps [less_Suc_eq, subst_Var]; |
|
102 |
99 |
103 goal Lambda.thy |
100 goal Lambda.thy |
104 "!i k. i < Suc k --> lift (lift t i) (Suc k) = lift (lift t k) i"; |
101 "!i k. i < Suc k --> lift (lift t i) (Suc k) = lift (lift t k) i"; |
105 by(db.induct_tac "t" 1); |
102 by(db.induct_tac "t" 1); |
106 by(ALLGOALS (asm_simp_tac ss)); |
103 by(ALLGOALS Asm_simp_tac); |
107 by(strip_tac 1); |
104 by(strip_tac 1); |
108 by (excluded_middle_tac "nat < i" 1); |
105 by (excluded_middle_tac "nat < i" 1); |
109 by ((forward_tac [lt_trans2] 2) THEN (assume_tac 2)); |
106 by ((forward_tac [lt_trans2] 2) THEN (assume_tac 2)); |
110 by (ALLGOALS(asm_full_simp_tac (split_ss addsimps [less_SucI]))); |
107 by (ALLGOALS(asm_full_simp_tac (addsplit(!simpset) addsimps [less_SucI]))); |
111 qed"lift_lift"; |
108 qed"lift_lift"; |
112 |
109 |
113 goal Lambda.thy "!i j s. j < Suc i --> \ |
110 goal Lambda.thy "!i j s. j < Suc i --> \ |
114 \ lift (t[s/j]) i = (lift t (Suc i)) [lift s i / j]"; |
111 \ lift (t[s/j]) i = (lift t (Suc i)) [lift s i / j]"; |
115 by(db.induct_tac "t" 1); |
112 by(db.induct_tac "t" 1); |
116 by(ALLGOALS(asm_simp_tac (ss addsimps [lift_lift]))); |
113 by(ALLGOALS(asm_simp_tac (!simpset addsimps [lift_lift]))); |
117 by(strip_tac 1); |
114 by(strip_tac 1); |
118 by (excluded_middle_tac "nat < j" 1); |
115 by (excluded_middle_tac "nat < j" 1); |
119 by (asm_full_simp_tac ss 1); |
116 by (Asm_full_simp_tac 1); |
120 by (eres_inst_tac [("j","nat")] leqE 1); |
117 by (eres_inst_tac [("j","nat")] leqE 1); |
121 by (asm_full_simp_tac (split_ss addsimps [less_SucI,gt_pred,Suc_pred]) 1); |
118 by (asm_full_simp_tac (addsplit(!simpset) |
|
119 addsimps [less_SucI,gt_pred,Suc_pred]) 1); |
122 by (hyp_subst_tac 1); |
120 by (hyp_subst_tac 1); |
123 by (Asm_simp_tac 1); |
121 by (Asm_simp_tac 1); |
124 by (forw_inst_tac [("j","j")] lt_trans2 1); |
122 by (forw_inst_tac [("j","j")] lt_trans2 1); |
125 by (assume_tac 1); |
123 by (assume_tac 1); |
126 by (asm_full_simp_tac (split_ss addsimps [less_SucI]) 1); |
124 by (asm_full_simp_tac (addsplit(!simpset) addsimps [less_SucI]) 1); |
127 qed "lift_subst"; |
125 qed "lift_subst"; |
128 Addsimps [lift_subst]; |
126 Addsimps [lift_subst]; |
129 |
127 |
130 goal Lambda.thy |
128 goal Lambda.thy |
131 "!i j s. i < Suc j -->\ |
129 "!i j s. i < Suc j -->\ |
132 \ lift (t[s/j]) i = (lift t i) [lift s i / Suc j]"; |
130 \ lift (t[s/j]) i = (lift t i) [lift s i / Suc j]"; |
133 by(db.induct_tac "t" 1); |
131 by(db.induct_tac "t" 1); |
134 by(ALLGOALS(asm_simp_tac (ss addsimps [lift_lift]))); |
132 by(ALLGOALS(asm_simp_tac (!simpset addsimps [lift_lift]))); |
135 by(strip_tac 1); |
133 by(strip_tac 1); |
136 by (excluded_middle_tac "nat < j" 1); |
134 by (excluded_middle_tac "nat < j" 1); |
137 by (asm_full_simp_tac ss 1); |
135 by (Asm_full_simp_tac 1); |
138 by (eres_inst_tac [("i","j")] leqE 1); |
136 by (eres_inst_tac [("i","j")] leqE 1); |
139 by (forward_tac [lt_trans1] 1 THEN assume_tac 1); |
137 by (forward_tac [lt_trans1] 1 THEN assume_tac 1); |
140 by (ALLGOALS(asm_full_simp_tac (ss addsimps [Suc_pred,less_SucI,gt_pred]))); |
138 by (ALLGOALS(asm_full_simp_tac |
|
139 (!simpset addsimps [Suc_pred,less_SucI,gt_pred]))); |
141 by (hyp_subst_tac 1); |
140 by (hyp_subst_tac 1); |
142 by (asm_full_simp_tac (ss addsimps [less_SucI]) 1); |
141 by (asm_full_simp_tac (!simpset addsimps [less_SucI]) 1); |
143 by(split_tac [expand_if] 1); |
142 by(split_tac [expand_if] 1); |
144 by (asm_full_simp_tac (!simpset addsimps [less_SucI]) 1); |
143 by (asm_full_simp_tac (!simpset addsimps [less_SucI]) 1); |
145 qed "lift_subst_lt"; |
144 qed "lift_subst_lt"; |
146 |
145 |
147 goal Lambda.thy "!k s. (lift t k)[s/k] = t"; |
146 goal Lambda.thy "!k s. (lift t k)[s/k] = t"; |
154 |
153 |
155 |
154 |
156 goal Lambda.thy "!i j u v. i < Suc j --> \ |
155 goal Lambda.thy "!i j u v. i < Suc j --> \ |
157 \ t[lift v i / Suc j][u[v/j]/i] = t[u/i][v/j]"; |
156 \ t[lift v i / Suc j][u[v/j]/i] = t[u/i][v/j]"; |
158 by(db.induct_tac "t" 1); |
157 by(db.induct_tac "t" 1); |
159 by (ALLGOALS(asm_simp_tac (ss addsimps |
158 by (ALLGOALS(asm_simp_tac (!simpset addsimps |
160 [lift_lift RS spec RS spec RS mp RS sym,lift_subst_lt]))); |
159 [lift_lift RS spec RS spec RS mp RS sym,lift_subst_lt]))); |
161 by(strip_tac 1); |
160 by(strip_tac 1); |
162 by (excluded_middle_tac "nat < Suc(Suc j)" 1); |
161 by (excluded_middle_tac "nat < Suc(Suc j)" 1); |
163 by(asm_full_simp_tac ss 1); |
162 by(Asm_full_simp_tac 1); |
164 by (forward_tac [lessI RS less_trans] 1); |
163 by (forward_tac [lessI RS less_trans] 1); |
165 by (eresolve_tac [leqE] 1); |
164 by (eresolve_tac [leqE] 1); |
166 by (asm_simp_tac (ss addsimps [Suc_pred,lt_pred]) 2); |
165 by (asm_simp_tac (!simpset addsimps [Suc_pred,lt_pred]) 2); |
167 by (forward_tac [Suc_mono RS less_trans] 1 THEN assume_tac 1); |
166 by (forward_tac [Suc_mono RS less_trans] 1 THEN assume_tac 1); |
168 by (forw_inst_tac [("i","i")] (lessI RS less_trans) 1); |
167 by (forw_inst_tac [("i","i")] (lessI RS less_trans) 1); |
169 by (asm_simp_tac (ss addsimps [Suc_pred,lt_pred]) 1); |
168 by (asm_simp_tac (!simpset addsimps [Suc_pred,lt_pred]) 1); |
170 by (eres_inst_tac [("i","nat")] leqE 1); |
169 by (eres_inst_tac [("i","nat")] leqE 1); |
171 by (asm_full_simp_tac (!simpset delsimps [less_Suc_eq] |
170 by (asm_full_simp_tac (!simpset addsimps [Suc_pred,less_SucI]) 2); |
172 addsimps [Suc_pred,less_SucI]) 2); |
|
173 by (excluded_middle_tac "nat < i" 1); |
171 by (excluded_middle_tac "nat < i" 1); |
174 by (asm_full_simp_tac ss 1); |
172 by (Asm_full_simp_tac 1); |
175 by (eres_inst_tac [("j","nat")] leqE 1); |
173 by (eres_inst_tac [("j","nat")] leqE 1); |
176 by (asm_simp_tac (!simpset addsimps [gt_pred]) 1); |
174 by (asm_simp_tac (!simpset addsimps [gt_pred]) 1); |
177 by (Asm_simp_tac 1); |
175 by (Asm_simp_tac 1); |
178 by (forward_tac [lt_trans2] 1 THEN assume_tac 1); |
176 by (forward_tac [lt_trans2] 1 THEN assume_tac 1); |
179 by (asm_simp_tac (!simpset addsimps [gt_pred]) 1); |
177 by (asm_simp_tac (!simpset addsimps [gt_pred]) 1); |
182 |
180 |
183 (*** Equivalence proof for optimized substitution ***) |
181 (*** Equivalence proof for optimized substitution ***) |
184 |
182 |
185 goal Lambda.thy "!k. liftn 0 t k = t"; |
183 goal Lambda.thy "!k. liftn 0 t k = t"; |
186 by(db.induct_tac "t" 1); |
184 by(db.induct_tac "t" 1); |
187 by(ALLGOALS(asm_simp_tac split_ss)); |
185 by(ALLGOALS(asm_simp_tac(addsplit(!simpset)))); |
188 qed "liftn_0"; |
186 qed "liftn_0"; |
189 Addsimps [liftn_0]; |
187 Addsimps [liftn_0]; |
190 |
188 |
191 goal Lambda.thy "!k. liftn (Suc n) t k = lift (liftn n t k) k"; |
189 goal Lambda.thy "!k. liftn (Suc n) t k = lift (liftn n t k) k"; |
192 by(db.induct_tac "t" 1); |
190 by(db.induct_tac "t" 1); |
193 by(ALLGOALS(asm_simp_tac split_ss)); |
191 by(ALLGOALS(asm_simp_tac(addsplit(!simpset)))); |
194 by(fast_tac (HOL_cs addDs [add_lessD1]) 1); |
192 by(fast_tac (HOL_cs addDs [add_lessD1]) 1); |
195 qed "liftn_lift"; |
193 qed "liftn_lift"; |
196 Addsimps [liftn_lift]; |
194 Addsimps [liftn_lift]; |
197 |
195 |
198 goal Lambda.thy "!n. substn t s n = t[liftn n s 0 / n]"; |
196 goal Lambda.thy "!n. substn t s n = t[liftn n s 0 / n]"; |
199 by(db.induct_tac "t" 1); |
197 by(db.induct_tac "t" 1); |
200 by(ALLGOALS(asm_simp_tac (!simpset setloop (split_tac [expand_if])))); |
198 by(ALLGOALS(asm_simp_tac(addsplit(!simpset)))); |
201 qed "substn_subst_n"; |
199 qed "substn_subst_n"; |
202 Addsimps [substn_subst_n]; |
200 Addsimps [substn_subst_n]; |
203 |
201 |
204 goal Lambda.thy "substn t s 0 = t[s/0]"; |
202 goal Lambda.thy "substn t s 0 = t[s/0]"; |
205 by(Simp_tac 1); |
203 by(Simp_tac 1); |