71 by (dtac W_var_geD 1); |
71 by (dtac W_var_geD 1); |
72 by (rtac new_scheme_list_le 1); |
72 by (rtac new_scheme_list_le 1); |
73 ba 1; |
73 ba 1; |
74 ba 1; |
74 ba 1; |
75 qed "new_tv_compatible_W"; |
75 qed "new_tv_compatible_W"; |
76 |
|
77 (* auxiliary lemma *) |
|
78 goal Maybe.thy "(y = Some x) = (Some x = y)"; |
|
79 by( simp_tac (!simpset addsimps [eq_sym_conv]) 1); |
|
80 qed "rotate_Some"; |
|
81 |
76 |
82 goal thy "!!sch. new_tv n sch --> new_tv (n + (min_new_bound_tv sch)) (bound_typ_inst (%b. TVar (b + n)) sch)"; |
77 goal thy "!!sch. new_tv n sch --> new_tv (n + (min_new_bound_tv sch)) (bound_typ_inst (%b. TVar (b + n)) sch)"; |
83 by (type_scheme.induct_tac "sch" 1); |
78 by (type_scheme.induct_tac "sch" 1); |
84 by (Asm_full_simp_tac 1); |
79 by (Asm_full_simp_tac 1); |
85 by (asm_full_simp_tac (!simpset addsimps [add_commute]) 1); |
80 by (asm_full_simp_tac (!simpset addsimps [add_commute]) 1); |
333 addDs [less_le_trans]) 1); |
328 addDs [less_le_trans]) 1); |
334 qed_spec_mp "free_tv_W"; |
329 qed_spec_mp "free_tv_W"; |
335 |
330 |
336 goal thy "!!A. (!x. x : A --> x ~: B) ==> A Int B = {}"; |
331 goal thy "!!A. (!x. x : A --> x ~: B) ==> A Int B = {}"; |
337 by (Fast_tac 1); |
332 by (Fast_tac 1); |
338 qed "weaken_A_Int_B_eq_empty"; |
333 val weaken_A_Int_B_eq_empty = result(); |
339 |
334 |
340 goal thy "!!A. x ~: A | x : B ==> x ~: A - B"; |
335 goal thy "!!A. x ~: A | x : B ==> x ~: A - B"; |
341 by (Fast_tac 1); |
336 by (Fast_tac 1); |
342 qed "weaken_not_elem_A_minus_B"; |
337 val weaken_not_elem_A_minus_B = result(); |
343 |
338 |
344 (* correctness of W with respect to has_type *) |
339 (* correctness of W with respect to has_type *) |
345 goal W.thy |
340 goal W.thy |
346 "!A S t m n . new_tv n A --> Some (S,t,m) = W e A n --> $S A |- e :: t"; |
341 "!A S t m n . new_tv n A --> Some (S,t,m) = W e A n --> $S A |- e :: t"; |
347 by (expr.induct_tac "e" 1); |
342 by (expr.induct_tac "e" 1); |
460 by (rtac new_tv_le 1); |
455 by (rtac new_tv_le 1); |
461 ba 2; |
456 ba 2; |
462 by (asm_full_simp_tac (!simpset addsimps [not_less_iff_le]) 1); |
457 by (asm_full_simp_tac (!simpset addsimps [not_less_iff_le]) 1); |
463 qed_spec_mp "W_correct_lemma"; |
458 qed_spec_mp "W_correct_lemma"; |
464 |
459 |
465 goal Type.thy "new_tv n (sch::type_scheme) --> \ |
|
466 \ $(%k.if k<n then S k else S' k) sch = $S sch"; |
|
467 by (type_scheme.induct_tac "sch" 1); |
|
468 by(ALLGOALS Asm_simp_tac); |
|
469 qed "new_if_subst_type_scheme"; |
|
470 Addsimps [new_if_subst_type_scheme]; |
|
471 |
|
472 goal Type.thy "new_tv n (A::type_scheme list) --> \ |
|
473 \ $(%k.if k<n then S k else S' k) A = $S A"; |
|
474 by (list.induct_tac "A" 1); |
|
475 by(ALLGOALS Asm_simp_tac); |
|
476 qed "new_if_subst_type_scheme_list"; |
|
477 Addsimps [new_if_subst_type_scheme_list]; |
|
478 |
|
479 goal Arith.thy "!!n::nat. ~ k+n < n"; |
460 goal Arith.thy "!!n::nat. ~ k+n < n"; |
480 by (nat_ind_tac "k" 1); |
461 by (nat_ind_tac "k" 1); |
481 by(ALLGOALS Asm_simp_tac); |
462 by(ALLGOALS Asm_simp_tac); |
482 by(trans_tac 1); |
463 by(trans_tac 1); |
483 qed "not_add_less1"; |
464 val not_add_less1 = result(); |
484 Addsimps [not_add_less1]; |
465 Addsimps [not_add_less1]; |
485 |
466 |
486 (* Completeness of W w.r.t. has_type *) |
467 (* Completeness of W w.r.t. has_type *) |
487 goal thy |
468 goal thy |
488 "!S' A t' n. $S' A |- e :: t' --> new_tv n A --> \ |
469 "!S' A t' n. $S' A |- e :: t' --> new_tv n A --> \ |