20 (* case Abs e *) |
20 (* case Abs e *) |
21 by (asm_full_simp_tac (!simpset addsimps [app_subst_list] |
21 by (asm_full_simp_tac (!simpset addsimps [app_subst_list] |
22 setloop (split_tac [expand_bind])) 1); |
22 setloop (split_tac [expand_bind])) 1); |
23 by (strip_tac 1); |
23 by (strip_tac 1); |
24 by (eres_inst_tac [("x","TVar(n) # a")] allE 1); |
24 by (eres_inst_tac [("x","TVar(n) # a")] allE 1); |
25 by( fast_tac (HOL_cs addss (!simpset addsimps [eq_sym_conv])) 1); |
25 by ( fast_tac (HOL_cs addss (!simpset addsimps [eq_sym_conv])) 1); |
26 (* case App e1 e2 *) |
26 (* case App e1 e2 *) |
27 by (simp_tac (!simpset setloop (split_tac [expand_bind])) 1); |
27 by (simp_tac (!simpset setloop (split_tac [expand_bind])) 1); |
28 by (strip_tac 1); |
28 by (strip_tac 1); |
29 by( rename_tac "sa ta na sb tb nb sc" 1); |
29 by ( rename_tac "sa ta na sb tb nb sc" 1); |
30 by (res_inst_tac [("t2.0","$ sc tb")] has_type.AppI 1); |
30 by (res_inst_tac [("t2.0","$ sc tb")] has_type.AppI 1); |
31 by (res_inst_tac [("s1","sc")] (app_subst_TVar RS subst) 1); |
31 by (res_inst_tac [("s1","sc")] (app_subst_TVar RS subst) 1); |
32 by (rtac (app_subst_Fun RS subst) 1); |
32 by (rtac (app_subst_Fun RS subst) 1); |
33 by (res_inst_tac [("t","$sc(tb -> (TVar nb))"),("s","$sc($sb ta)")] subst 1); |
33 by (res_inst_tac [("t","$sc(tb -> (TVar nb))"),("s","$sc($sb ta)")] subst 1); |
34 by (Asm_full_simp_tac 1); |
34 by (Asm_full_simp_tac 1); |
119 by (asm_full_simp_tac (!simpset addsimps [eq_sym_conv]) 1); |
119 by (asm_full_simp_tac (!simpset addsimps [eq_sym_conv]) 1); |
120 by (eres_inst_tac [("x","$ s a")] allE 1); |
120 by (eres_inst_tac [("x","$ s a")] allE 1); |
121 by (eres_inst_tac [("x","sa")] allE 1); |
121 by (eres_inst_tac [("x","sa")] allE 1); |
122 by (eres_inst_tac [("x","ta")] allE 1); |
122 by (eres_inst_tac [("x","ta")] allE 1); |
123 by (eres_inst_tac [("x","nb")] allE 1); |
123 by (eres_inst_tac [("x","nb")] allE 1); |
124 by( asm_full_simp_tac (!simpset addsimps [o_def,rotate_Ok]) 1); |
124 by ( asm_full_simp_tac (!simpset addsimps [o_def,rotate_Ok]) 1); |
125 by (rtac conjI 1); |
125 by (rtac conjI 1); |
126 by (rtac new_tv_subst_comp_2 1); |
126 by (rtac new_tv_subst_comp_2 1); |
127 by (rtac new_tv_subst_comp_2 1); |
127 by (rtac new_tv_subst_comp_2 1); |
128 by (rtac (lessI RS less_imp_le RS new_tv_subst_le) 1); |
128 by (rtac (lessI RS less_imp_le RS new_tv_subst_le) 1); |
129 by (res_inst_tac [("n","na")] new_tv_subst_le 1); |
129 by (res_inst_tac [("n","na")] new_tv_subst_le 1); |
132 by (fast_tac (HOL_cs addDs [W_var_geD] addIs |
132 by (fast_tac (HOL_cs addDs [W_var_geD] addIs |
133 [new_tv_list_le,new_tv_subst_tel,lessI RS less_imp_le RS new_tv_subst_le]) |
133 [new_tv_list_le,new_tv_subst_tel,lessI RS less_imp_le RS new_tv_subst_le]) |
134 1); |
134 1); |
135 by (etac (sym RS mgu_new) 1); |
135 by (etac (sym RS mgu_new) 1); |
136 by (best_tac (HOL_cs addDs [W_var_geD] |
136 by (best_tac (HOL_cs addDs [W_var_geD] |
137 addIs [new_tv_subst_te,new_tv_list_le, |
137 addIs [new_tv_subst_te,new_tv_list_le, |
138 new_tv_subst_tel, |
138 new_tv_subst_tel, |
139 lessI RS less_imp_le RS new_tv_le, |
139 lessI RS less_imp_le RS new_tv_le, |
140 lessI RS less_imp_le RS new_tv_subst_le, |
140 lessI RS less_imp_le RS new_tv_subst_le, |
141 new_tv_le]) 1); |
141 new_tv_le]) 1); |
142 by (fast_tac (HOL_cs addDs [W_var_geD] |
142 by (fast_tac (HOL_cs addDs [W_var_geD] |
143 addIs [new_tv_list_le,new_tv_subst_tel,new_tv_le] |
143 addIs [new_tv_list_le,new_tv_subst_tel,new_tv_le] |
144 addss (!simpset)) 1); |
144 addss (!simpset)) 1); |
145 by (rtac (lessI RS new_tv_subst_var) 1); |
145 by (rtac (lessI RS new_tv_subst_var) 1); |
146 by (etac (sym RS mgu_new) 1); |
146 by (etac (sym RS mgu_new) 1); |
147 by (best_tac (HOL_cs addSIs [lessI RS less_imp_le RS new_tv_le,new_tv_subst_te] |
147 by (best_tac (HOL_cs addSIs [lessI RS less_imp_le RS new_tv_le,new_tv_subst_te] |
148 addDs [W_var_geD] |
148 addDs [W_var_geD] |
149 addIs [new_tv_list_le, |
149 addIs [new_tv_list_le, |
150 new_tv_subst_tel, |
150 new_tv_subst_tel, |
151 lessI RS less_imp_le RS new_tv_subst_le, |
151 lessI RS less_imp_le RS new_tv_subst_le, |
152 new_tv_le] |
152 new_tv_le] |
153 addss !simpset) 1); |
153 addss !simpset) 1); |
154 by (fast_tac (HOL_cs addDs [W_var_geD] |
154 by (fast_tac (HOL_cs addDs [W_var_geD] |
155 addIs [new_tv_list_le,new_tv_subst_tel,new_tv_le] |
155 addIs [new_tv_list_le,new_tv_subst_tel,new_tv_le] |
156 addss (!simpset)) 1); |
156 addss (!simpset)) 1); |
157 qed_spec_mp "new_tv_W"; |
157 qed_spec_mp "new_tv_W"; |
158 |
158 |
159 |
159 |
160 goal thy |
160 goal thy |
224 \ (? r. $s' a = $r ($s a) & t' = $r t))"; |
224 \ (? r. $s' a = $r ($s a) & t' = $r t))"; |
225 by (expr.induct_tac "e" 1); |
225 by (expr.induct_tac "e" 1); |
226 (* case Var n *) |
226 (* case Var n *) |
227 by (strip_tac 1); |
227 by (strip_tac 1); |
228 by (simp_tac (!simpset addcongs [conj_cong] |
228 by (simp_tac (!simpset addcongs [conj_cong] |
229 setloop (split_tac [expand_if])) 1); |
229 setloop (split_tac [expand_if])) 1); |
230 by (eresolve_tac has_type_casesE 1); |
230 by (eresolve_tac has_type_casesE 1); |
231 by (asm_full_simp_tac (!simpset addsimps [eq_sym_conv,app_subst_list]) 1); |
231 by (asm_full_simp_tac (!simpset addsimps [eq_sym_conv,app_subst_list]) 1); |
232 by (res_inst_tac [("x","id_subst")] exI 1); |
232 by (res_inst_tac [("x","id_subst")] exI 1); |
233 by (res_inst_tac [("x","nth nat a")] exI 1); |
233 by (res_inst_tac [("x","nth nat a")] exI 1); |
234 by (Simp_tac 1); |
234 by (Simp_tac 1); |
241 by (eres_inst_tac [("x","%x.if x=n then t1 else (s' x)")] allE 1); |
241 by (eres_inst_tac [("x","%x.if x=n then t1 else (s' x)")] allE 1); |
242 by (eres_inst_tac [("x","(TVar n)#a")] allE 1); |
242 by (eres_inst_tac [("x","(TVar n)#a")] allE 1); |
243 by (eres_inst_tac [("x","t2")] allE 1); |
243 by (eres_inst_tac [("x","t2")] allE 1); |
244 by (eres_inst_tac [("x","Suc n")] allE 1); |
244 by (eres_inst_tac [("x","Suc n")] allE 1); |
245 by (fast_tac (HOL_cs addss (!simpset addcongs [conj_cong] |
245 by (fast_tac (HOL_cs addss (!simpset addcongs [conj_cong] |
246 setloop (split_tac [expand_bind]))) 1); |
246 setloop (split_tac [expand_bind]))) 1); |
247 |
247 |
248 (* case App e1 e2 *) |
248 (* case App e1 e2 *) |
249 by (strip_tac 1); |
249 by (strip_tac 1); |
250 by (eresolve_tac has_type_casesE 1); |
250 by (eresolve_tac has_type_casesE 1); |
251 by (eres_inst_tac [("x","s'")] allE 1); |
251 by (eres_inst_tac [("x","s'")] allE 1); |
262 by (dtac asm_rl 1); |
262 by (dtac asm_rl 1); |
263 by (Asm_full_simp_tac 1); |
263 by (Asm_full_simp_tac 1); |
264 by (safe_tac HOL_cs); |
264 by (safe_tac HOL_cs); |
265 by (fast_tac HOL_cs 1); |
265 by (fast_tac HOL_cs 1); |
266 by (fast_tac (HOL_cs addIs [sym RS W_var_geD,new_tv_W RS |
266 by (fast_tac (HOL_cs addIs [sym RS W_var_geD,new_tv_W RS |
267 conjunct1,new_tv_list_le,new_tv_subst_tel]) 1); |
267 conjunct1,new_tv_list_le,new_tv_subst_tel]) 1); |
268 |
268 |
269 by (subgoal_tac |
269 by (subgoal_tac |
270 "$ (%x.if x=ma then t' else (if x:(free_tv t - free_tv sa) then r x \ |
270 "$ (%x.if x=ma then t' else (if x:(free_tv t - free_tv sa) then r x \ |
271 \ else ra x)) ($ sa t) = \ |
271 \ else ra x)) ($ sa t) = \ |
272 \ $ (%x.if x=ma then t' else (if x:(free_tv t - free_tv sa) then r x \ |
272 \ $ (%x.if x=ma then t' else (if x:(free_tv t - free_tv sa) then r x \ |
277 by (asm_simp_tac (!simpset addsimps [subst_comp_te]) 2); |
277 by (asm_simp_tac (!simpset addsimps [subst_comp_te]) 2); |
278 by (rtac eq_free_eq_subst_te 2); |
278 by (rtac eq_free_eq_subst_te 2); |
279 by (strip_tac 2); |
279 by (strip_tac 2); |
280 by (subgoal_tac "na ~=ma" 2); |
280 by (subgoal_tac "na ~=ma" 2); |
281 by (fast_tac (HOL_cs addDs [new_tv_W,sym RS W_var_geD, |
281 by (fast_tac (HOL_cs addDs [new_tv_W,sym RS W_var_geD, |
282 new_tv_not_free_tv,new_tv_le]) 3); |
282 new_tv_not_free_tv,new_tv_le]) 3); |
283 by (case_tac "na:free_tv sa" 2); |
283 by (case_tac "na:free_tv sa" 2); |
284 (* na ~: free_tv sa *) |
284 (* na ~: free_tv sa *) |
285 by (asm_simp_tac (!simpset addsimps [not_free_impl_id] |
285 by (asm_simp_tac (!simpset addsimps [not_free_impl_id] |
286 setloop (split_tac [expand_if])) 3); |
286 setloop (split_tac [expand_if])) 3); |
287 (* na : free_tv sa *) |
287 (* na : free_tv sa *) |
288 by (dres_inst_tac [("ts1","$ s a")] (subst_comp_tel RSN (2,trans)) 2); |
288 by (dres_inst_tac [("ts1","$ s a")] (subst_comp_tel RSN (2,trans)) 2); |
289 by (dtac eq_subst_tel_eq_free 2); |
289 by (dtac eq_subst_tel_eq_free 2); |
290 by (fast_tac (HOL_cs addIs [free_tv_W,free_tv_le_new_tv] addDs [new_tv_W]) 2); |
290 by (fast_tac (HOL_cs addIs [free_tv_W,free_tv_le_new_tv] addDs [new_tv_W]) 2); |
291 by (Asm_simp_tac 2); |
291 by (Asm_simp_tac 2); |
292 by (case_tac "na:dom sa" 2); |
292 by (case_tac "na:dom sa" 2); |
293 (* na ~: dom sa *) |
293 (* na ~: dom sa *) |
294 by (asm_full_simp_tac (!simpset addsimps [dom_def] |
294 by (asm_full_simp_tac (!simpset addsimps [dom_def] |
295 setloop (split_tac [expand_if])) 3); |
295 setloop (split_tac [expand_if])) 3); |
296 (* na : dom sa *) |
296 (* na : dom sa *) |
297 by (rtac eq_free_eq_subst_te 2); |
297 by (rtac eq_free_eq_subst_te 2); |
298 by (strip_tac 2); |
298 by (strip_tac 2); |
299 by (subgoal_tac "nb ~= ma" 2); |
299 by (subgoal_tac "nb ~= ma" 2); |
300 by ((forward_tac [new_tv_W] 3) THEN (atac 3)); |
300 by ((forward_tac [new_tv_W] 3) THEN (atac 3)); |
301 by (etac conjE 3); |
301 by (etac conjE 3); |
302 by (dtac new_tv_subst_tel 3); |
302 by (dtac new_tv_subst_tel 3); |
303 by (fast_tac (HOL_cs addIs [new_tv_list_le] addDs [sym RS W_var_geD]) 3); |
303 by (fast_tac (HOL_cs addIs [new_tv_list_le] addDs [sym RS W_var_geD]) 3); |
304 by (fast_tac (set_cs addDs [new_tv_W,new_tv_not_free_tv] addss |
304 by (fast_tac (set_cs addDs [new_tv_W,new_tv_not_free_tv] addss |
305 (!simpset addsimps [cod_def,free_tv_subst])) 3); |
305 (!simpset addsimps [cod_def,free_tv_subst])) 3); |
306 by (fast_tac (set_cs addss (!simpset addsimps [cod_def,free_tv_subst] |
306 by (fast_tac (set_cs addss (!simpset addsimps [cod_def,free_tv_subst] |
307 setloop (split_tac [expand_if]))) 2); |
307 setloop (split_tac [expand_if]))) 2); |
308 |
308 |
309 by (Simp_tac 2); |
309 by (Simp_tac 2); |
310 by (rtac eq_free_eq_subst_te 2); |
310 by (rtac eq_free_eq_subst_te 2); |
311 by (strip_tac 2 ); |
311 by (strip_tac 2 ); |
312 by (subgoal_tac "na ~= ma" 2); |
312 by (subgoal_tac "na ~= ma" 2); |
314 by (etac conjE 3); |
314 by (etac conjE 3); |
315 by (dtac (sym RS W_var_geD) 3); |
315 by (dtac (sym RS W_var_geD) 3); |
316 by (fast_tac (HOL_cs addDs [new_tv_list_le,new_tv_subst_tel,new_tv_W,new_tv_not_free_tv]) 3); |
316 by (fast_tac (HOL_cs addDs [new_tv_list_le,new_tv_subst_tel,new_tv_W,new_tv_not_free_tv]) 3); |
317 by (case_tac "na: free_tv t - free_tv sa" 2); |
317 by (case_tac "na: free_tv t - free_tv sa" 2); |
318 (* case na ~: free_tv t - free_tv sa *) |
318 (* case na ~: free_tv t - free_tv sa *) |
319 by( asm_full_simp_tac (!simpset setloop (split_tac [expand_if])) 3); |
319 by ( asm_full_simp_tac (!simpset setloop (split_tac [expand_if])) 3); |
320 (* case na : free_tv t - free_tv sa *) |
320 (* case na : free_tv t - free_tv sa *) |
321 by( asm_full_simp_tac (!simpset setloop (split_tac [expand_if])) 2); |
321 by ( asm_full_simp_tac (!simpset setloop (split_tac [expand_if])) 2); |
322 by (dres_inst_tac [("ts1","$ s a")] (subst_comp_tel RSN (2,trans)) 2); |
322 by (dres_inst_tac [("ts1","$ s a")] (subst_comp_tel RSN (2,trans)) 2); |
323 by (dtac eq_subst_tel_eq_free 2); |
323 by (dtac eq_subst_tel_eq_free 2); |
324 by (fast_tac (HOL_cs addIs [free_tv_W,free_tv_le_new_tv] addDs [new_tv_W]) 2); |
324 by (fast_tac (HOL_cs addIs [free_tv_W,free_tv_le_new_tv] addDs [new_tv_W]) 2); |
325 by (asm_full_simp_tac (!simpset addsimps [free_tv_subst,dom_def,de_Morgan_disj]) 2); |
325 by (asm_full_simp_tac (!simpset addsimps [free_tv_subst,dom_def,de_Morgan_disj]) 2); |
326 |
326 |
327 by (asm_simp_tac (!simpset setloop (split_tac [expand_bind])) 1); |
327 by (asm_simp_tac (!simpset setloop (split_tac [expand_bind])) 1); |
328 by (safe_tac HOL_cs ); |
328 by (safe_tac HOL_cs ); |
329 by (dtac mgu_Ok 1); |
329 by (dtac mgu_Ok 1); |
330 by( fast_tac (HOL_cs addss !simpset) 1); |
330 by ( fast_tac (HOL_cs addss !simpset) 1); |
331 by (REPEAT (resolve_tac [exI,conjI] 1)); |
331 by (REPEAT (resolve_tac [exI,conjI] 1)); |
332 by (fast_tac HOL_cs 1); |
332 by (fast_tac HOL_cs 1); |
333 by (fast_tac HOL_cs 1); |
333 by (fast_tac HOL_cs 1); |
334 by ((dtac mgu_mg 1) THEN (atac 1)); |
334 by ((dtac mgu_mg 1) THEN (atac 1)); |
335 by (etac exE 1); |
335 by (etac exE 1); |
336 by (res_inst_tac [("x","rb")] exI 1); |
336 by (res_inst_tac [("x","rb")] exI 1); |
337 by (rtac conjI 1); |
337 by (rtac conjI 1); |
338 by (dres_inst_tac [("x","ma")] fun_cong 2); |
338 by (dres_inst_tac [("x","ma")] fun_cong 2); |
339 by( asm_full_simp_tac (!simpset addsimps [eq_sym_conv]) 2); |
339 by ( asm_full_simp_tac (!simpset addsimps [eq_sym_conv]) 2); |
340 by (simp_tac (!simpset addsimps [subst_comp_tel RS sym]) 1); |
340 by (simp_tac (!simpset addsimps [subst_comp_tel RS sym]) 1); |
341 by (res_inst_tac [("ts2","($ sa ($ s a))")] ((subst_comp_tel RS sym) RSN |
341 by (res_inst_tac [("ts2","($ sa ($ s a))")] ((subst_comp_tel RS sym) RSN |
342 (2,trans)) 1); |
342 (2,trans)) 1); |
343 by( asm_full_simp_tac (!simpset addsimps [o_def,eq_sym_conv]) 1); |
343 by ( asm_full_simp_tac (!simpset addsimps [o_def,eq_sym_conv]) 1); |
344 by (rtac eq_free_eq_subst_tel 1); |
344 by (rtac eq_free_eq_subst_tel 1); |
345 by( safe_tac HOL_cs ); |
345 by ( safe_tac HOL_cs ); |
346 by (subgoal_tac "ma ~= na" 1); |
346 by (subgoal_tac "ma ~= na" 1); |
347 by ((forward_tac [new_tv_W] 2) THEN (atac 2)); |
347 by ((forward_tac [new_tv_W] 2) THEN (atac 2)); |
348 by (etac conjE 2); |
348 by (etac conjE 2); |
349 by (dtac new_tv_subst_tel 2); |
349 by (dtac new_tv_subst_tel 2); |
350 by (fast_tac (HOL_cs addIs [new_tv_list_le] addDs [sym RS W_var_geD]) 2); |
350 by (fast_tac (HOL_cs addIs [new_tv_list_le] addDs [sym RS W_var_geD]) 2); |
365 qed_spec_mp "W_complete_lemma"; |
365 qed_spec_mp "W_complete_lemma"; |
366 |
366 |
367 goal W.thy |
367 goal W.thy |
368 "!!e. [] |- e :: t' ==> (? s t. (? m. W e [] n = Ok(s,t,m)) & \ |
368 "!!e. [] |- e :: t' ==> (? s t. (? m. W e [] n = Ok(s,t,m)) & \ |
369 \ (? r. t' = $r t))"; |
369 \ (? r. t' = $r t))"; |
370 by(cut_inst_tac [("a","[]"),("s'","id_subst"),("e","e"),("t'","t'")] |
370 by (cut_inst_tac [("a","[]"),("s'","id_subst"),("e","e"),("t'","t'")] |
371 W_complete_lemma 1); |
371 W_complete_lemma 1); |
372 by(ALLGOALS Asm_full_simp_tac); |
372 by (ALLGOALS Asm_full_simp_tac); |
373 qed "W_complete"; |
373 qed "W_complete"; |