src/HOL/MiniML/W.ML
changeset 2625 69c1b8a493de
parent 2525 477c05586286
child 2637 e9b203f854ae
equal deleted inserted replaced
2624:ab311b6e5e29 2625:69c1b8a493de
    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 -->     \