12 (* correctness of W with respect to has_type *) |
12 (* correctness of W with respect to has_type *) |
13 goal W.thy |
13 goal W.thy |
14 "!a s t m n . Ok (s,t,m) = W e a n --> $s a |- e :: t"; |
14 "!a s t m n . Ok (s,t,m) = W e a n --> $s a |- e :: t"; |
15 by (expr.induct_tac "e" 1); |
15 by (expr.induct_tac "e" 1); |
16 (* case Var n *) |
16 (* case Var n *) |
17 by (asm_simp_tac (simpset() addsplits [expand_if]) 1); |
17 by (Asm_simp_tac 1); |
18 (* case Abs e *) |
18 (* case Abs e *) |
19 by (asm_full_simp_tac (simpset() addsimps [app_subst_list] |
19 by (asm_full_simp_tac (simpset() addsimps [app_subst_list] |
20 addsplits [expand_bind]) 1); |
20 addsplits [expand_bind]) 1); |
21 by (strip_tac 1); |
21 by (strip_tac 1); |
22 by (dtac sym 1); |
22 by (dtac sym 1); |
43 (* the resulting type variable is always greater or equal than the given one *) |
43 (* the resulting type variable is always greater or equal than the given one *) |
44 goal thy |
44 goal thy |
45 "!a n s t m. W e a n = Ok (s,t,m) --> n<=m"; |
45 "!a n s t m. W e a n = Ok (s,t,m) --> n<=m"; |
46 by (expr.induct_tac "e" 1); |
46 by (expr.induct_tac "e" 1); |
47 (* case Var(n) *) |
47 (* case Var(n) *) |
48 by (fast_tac (HOL_cs addss(simpset() addsplits [expand_if])) 1); |
48 by (fast_tac (HOL_cs addss simpset()) 1); |
49 (* case Abs e *) |
49 (* case Abs e *) |
50 by (simp_tac (simpset() addsplits [expand_bind]) 1); |
50 by (simp_tac (simpset() addsplits [expand_bind]) 1); |
51 by (fast_tac (HOL_cs addDs [Suc_leD]) 1); |
51 by (fast_tac (HOL_cs addDs [Suc_leD]) 1); |
52 (* case App e1 e2 *) |
52 (* case App e1 e2 *) |
53 by (simp_tac (simpset() addsplits [expand_bind]) 1); |
53 by (simp_tac (simpset() addsplits [expand_bind]) 1); |
89 "!n a s t m. new_tv n a --> W e a n = Ok (s,t,m) --> \ |
89 "!n a s t m. new_tv n a --> W e a n = Ok (s,t,m) --> \ |
90 \ new_tv m s & new_tv m t"; |
90 \ new_tv m s & new_tv m t"; |
91 by (expr.induct_tac "e" 1); |
91 by (expr.induct_tac "e" 1); |
92 (* case Var n *) |
92 (* case Var n *) |
93 by (fast_tac (HOL_cs addDs [list_all_nth] addss (simpset() |
93 by (fast_tac (HOL_cs addDs [list_all_nth] addss (simpset() |
94 addsimps [id_subst_def,new_tv_list,new_tv_subst] |
94 addsimps [id_subst_def,new_tv_list,new_tv_subst])) 1); |
95 addsplits [expand_if])) 1); |
|
96 (* case Abs e *) |
95 (* case Abs e *) |
97 by (simp_tac (simpset() addsimps [new_tv_subst,new_tv_Suc_list] |
96 by (simp_tac (simpset() addsimps [new_tv_subst,new_tv_Suc_list] |
98 addsplits [expand_bind]) 1); |
97 addsplits [expand_bind]) 1); |
99 by (strip_tac 1); |
98 by (strip_tac 1); |
100 by (eres_inst_tac [("x","Suc n")] allE 1); |
99 by (eres_inst_tac [("x","Suc n")] allE 1); |
157 "!n a s t m v. W e a n = Ok (s,t,m) --> \ |
156 "!n a s t m v. W e a n = Ok (s,t,m) --> \ |
158 \ (v:free_tv s | v:free_tv t) --> v<n --> v:free_tv a"; |
157 \ (v:free_tv s | v:free_tv t) --> v<n --> v:free_tv a"; |
159 by (expr.induct_tac "e" 1); |
158 by (expr.induct_tac "e" 1); |
160 (* case Var n *) |
159 (* case Var n *) |
161 by (fast_tac (HOL_cs addIs [nth_mem,subsetD,ftv_mem_sub_ftv_list] |
160 by (fast_tac (HOL_cs addIs [nth_mem,subsetD,ftv_mem_sub_ftv_list] |
162 addss (simpset() addsplits [expand_if])) 1); |
161 addss simpset()) 1); |
163 |
162 |
164 (* case Abs e *) |
163 (* case Abs e *) |
165 by (asm_full_simp_tac (simpset() addsimps |
164 by (asm_full_simp_tac (simpset() addsimps |
166 [free_tv_subst] addsplits [expand_bind]) 1); |
165 [free_tv_subst] addsplits [expand_bind]) 1); |
167 by (strip_tac 1); |
166 by (strip_tac 1); |
223 \ (? s t. (? m. W e a n = Ok (s,t,m)) & \ |
222 \ (? s t. (? m. W e a n = Ok (s,t,m)) & \ |
224 \ (? r. $s' a = $r ($s a) & t' = $r t))"; |
223 \ (? r. $s' a = $r ($s a) & t' = $r t))"; |
225 by (expr.induct_tac "e" 1); |
224 by (expr.induct_tac "e" 1); |
226 (* case Var n *) |
225 (* case Var n *) |
227 by (strip_tac 1); |
226 by (strip_tac 1); |
228 by (simp_tac (simpset() addcongs [conj_cong] |
227 by (simp_tac (simpset() addcongs [conj_cong]) 1); |
229 addsplits [expand_if]) 1); |
|
230 by (eresolve_tac has_type_casesE 1); |
228 by (eresolve_tac has_type_casesE 1); |
231 by (asm_full_simp_tac (simpset() addsimps [eq_sym_conv,app_subst_list]) 1); |
229 by (asm_full_simp_tac (simpset() addsimps [eq_sym_conv,app_subst_list]) 1); |
232 by (res_inst_tac [("x","s'")] exI 1); |
230 by (res_inst_tac [("x","s'")] exI 1); |
233 by (Asm_simp_tac 1); |
231 by (Asm_simp_tac 1); |
234 |
232 |
282 new_tv_not_free_tv,new_tv_le]) 3); |
280 new_tv_not_free_tv,new_tv_le]) 3); |
283 (** LEVEL 42 **) |
281 (** LEVEL 42 **) |
284 by (case_tac "na:free_tv sa" 2); |
282 by (case_tac "na:free_tv sa" 2); |
285 (* na ~: free_tv sa *) |
283 (* na ~: free_tv sa *) |
286 by (forward_tac [not_free_impl_id] 3); |
284 by (forward_tac [not_free_impl_id] 3); |
287 by (asm_simp_tac (simpset() addsplits [expand_if]) 3); |
285 by (Asm_simp_tac 3); |
288 (* na : free_tv sa *) |
286 (* na : free_tv sa *) |
289 by (dres_inst_tac [("ts1","$ s a")] (subst_comp_tel RSN (2,trans)) 2); |
287 by (dres_inst_tac [("ts1","$ s a")] (subst_comp_tel RSN (2,trans)) 2); |
290 by (dtac eq_subst_tel_eq_free 2); |
288 by (dtac eq_subst_tel_eq_free 2); |
291 by (fast_tac (HOL_cs addIs [free_tv_W,free_tv_le_new_tv] addDs [new_tv_W]) 2); |
289 by (fast_tac (HOL_cs addIs [free_tv_W,free_tv_le_new_tv] addDs [new_tv_W]) 2); |
292 by (Asm_simp_tac 2); |
290 by (Asm_simp_tac 2); |
293 by (case_tac "na:dom sa" 2); |
291 by (case_tac "na:dom sa" 2); |
294 (* na ~: dom sa *) |
292 (* na ~: dom sa *) |
295 (** LEVEL 50 **) |
293 (** LEVEL 50 **) |
296 by (asm_full_simp_tac (simpset() addsimps [dom_def] |
294 by (asm_full_simp_tac (simpset() addsimps [dom_def]) 3); |
297 addsplits [expand_if]) 3); |
|
298 (* na : dom sa *) |
295 (* na : dom sa *) |
299 by (rtac eq_free_eq_subst_te 2); |
296 by (rtac eq_free_eq_subst_te 2); |
300 by (strip_tac 2); |
297 by (strip_tac 2); |
301 by (subgoal_tac "nb ~= ma" 2); |
298 by (subgoal_tac "nb ~= ma" 2); |
302 by ((forward_tac [new_tv_W] 3) THEN (atac 3)); |
299 by ((forward_tac [new_tv_W] 3) THEN (atac 3)); |
303 by (etac conjE 3); |
300 by (etac conjE 3); |
304 by (dtac new_tv_subst_tel 3); |
301 by (dtac new_tv_subst_tel 3); |
305 by (fast_tac (HOL_cs addIs [new_tv_list_le] addDs [sym RS W_var_geD]) 3); |
302 by (fast_tac (HOL_cs addIs [new_tv_list_le] addDs [sym RS W_var_geD]) 3); |
306 by (fast_tac (set_cs addDs [new_tv_W,new_tv_not_free_tv] addss |
303 by (fast_tac (set_cs addDs [new_tv_W,new_tv_not_free_tv] addss |
307 (simpset() addsimps [cod_def,free_tv_subst])) 3); |
304 (simpset() addsimps [cod_def,free_tv_subst])) 3); |
308 by (fast_tac (set_cs addss (simpset() addsimps [cod_def,free_tv_subst] |
305 by (fast_tac (set_cs addss (simpset() addsimps [cod_def,free_tv_subst])) 2); |
309 addsplits [expand_if])) 2); |
|
310 |
306 |
311 (** LEVEL 60 **) |
307 (** LEVEL 60 **) |
312 by (Simp_tac 2); |
308 by (Simp_tac 2); |
313 by (rtac eq_free_eq_subst_te 2); |
309 by (rtac eq_free_eq_subst_te 2); |
314 by (strip_tac 2 ); |
310 by (strip_tac 2 ); |
318 by (dtac (sym RS W_var_geD) 3); |
314 by (dtac (sym RS W_var_geD) 3); |
319 by (fast_tac (HOL_cs addDs [new_tv_list_le,new_tv_subst_tel,new_tv_W,new_tv_not_free_tv]) 3); |
315 by (fast_tac (HOL_cs addDs [new_tv_list_le,new_tv_subst_tel,new_tv_W,new_tv_not_free_tv]) 3); |
320 by (case_tac "na: free_tv t - free_tv sa" 2); |
316 by (case_tac "na: free_tv t - free_tv sa" 2); |
321 (** LEVEL 69 **) |
317 (** LEVEL 69 **) |
322 (* case na ~: free_tv t - free_tv sa *) |
318 (* case na ~: free_tv t - free_tv sa *) |
323 by ( asm_full_simp_tac (simpset() addsplits [expand_if]) 3); |
319 by (Asm_full_simp_tac 3); |
324 (* case na : free_tv t - free_tv sa *) |
320 (* case na : free_tv t - free_tv sa *) |
325 by ( asm_full_simp_tac (simpset() addsplits [expand_if]) 2); |
321 by (Asm_full_simp_tac 2); |
326 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); |
327 by (dtac eq_subst_tel_eq_free 2); |
323 by (dtac eq_subst_tel_eq_free 2); |
328 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); |
329 by (asm_full_simp_tac (simpset() addsimps [free_tv_subst,dom_def]) 2); |
325 by (asm_full_simp_tac (simpset() addsimps [free_tv_subst,dom_def]) 2); |
330 by (Fast_tac 2); |
326 by (Fast_tac 2); |
356 by (dtac (free_tv_app_subst_tel RS subsetD) 2); |
352 by (dtac (free_tv_app_subst_tel RS subsetD) 2); |
357 by (fast_tac (set_cs addDs [sym RS W_var_geD,new_tv_list_le,codD, |
353 by (fast_tac (set_cs addDs [sym RS W_var_geD,new_tv_list_le,codD, |
358 new_tv_not_free_tv]) 2); |
354 new_tv_not_free_tv]) 2); |
359 by (case_tac "na: free_tv t - free_tv sa" 1); |
355 by (case_tac "na: free_tv t - free_tv sa" 1); |
360 (* case na ~: free_tv t - free_tv sa *) |
356 (* case na ~: free_tv t - free_tv sa *) |
361 by (asm_full_simp_tac (simpset() addsplits [expand_if]) 2); |
357 by (Asm_full_simp_tac 2); |
362 (* case na : free_tv t - free_tv sa *) |
358 (* case na : free_tv t - free_tv sa *) |
363 by (asm_full_simp_tac (simpset() addsplits [expand_if]) 1); |
359 by (Asm_full_simp_tac 1); |
364 by (dtac (free_tv_app_subst_tel RS subsetD) 1); |
360 by (dtac (free_tv_app_subst_tel RS subsetD) 1); |
365 by (fast_tac (set_cs addDs [codD,subst_comp_tel RSN (2,trans), |
361 by (fast_tac (set_cs addDs [codD,subst_comp_tel RSN (2,trans), |
366 eq_subst_tel_eq_free] |
362 eq_subst_tel_eq_free] |
367 addss ((simpset() addsimps [free_tv_subst,dom_def]))) 1); |
363 addss ((simpset() addsimps [free_tv_subst,dom_def]))) 1); |
368 (** LEVEL 106 **) |
364 (** LEVEL 106 **) |