src/HOL/MiniML/W.ML
changeset 5118 6b995dad8a9d
parent 5069 3ea049f7979d
child 5184 9b8547a9496a
equal deleted inserted replaced
5117:7b5efef2ca74 5118:6b995dad8a9d
    31 qed_spec_mp "W_var_ge";
    31 qed_spec_mp "W_var_ge";
    32 
    32 
    33 Addsimps [W_var_ge];
    33 Addsimps [W_var_ge];
    34 
    34 
    35 Goal
    35 Goal
    36         "!! s. Some (S,t,m) = W e A n ==> n<=m";
    36         "Some (S,t,m) = W e A n ==> n<=m";
    37 by (asm_full_simp_tac (simpset() addsimps [eq_sym_conv]) 1);
    37 by (asm_full_simp_tac (simpset() addsimps [eq_sym_conv]) 1);
    38 qed "W_var_geD";
    38 qed "W_var_geD";
    39 
    39 
    40 Goal "!! s. new_tv n A ==> Some (S,t,m) = W e A n ==> new_tv m A";
    40 Goal "new_tv n A ==> Some (S,t,m) = W e A n ==> new_tv m A";
    41 by (dtac W_var_geD 1);
    41 by (dtac W_var_geD 1);
    42 by (rtac new_scheme_list_le 1);
    42 by (rtac new_scheme_list_le 1);
    43 by (assume_tac 1);
    43 by (assume_tac 1);
    44 by (assume_tac 1);
    44 by (assume_tac 1);
    45 qed "new_tv_compatible_W";
    45 qed "new_tv_compatible_W";
    46 
    46 
    47 Goal "!!sch. new_tv n sch --> new_tv (n + (min_new_bound_tv sch)) (bound_typ_inst (%b. TVar (b + n)) sch)";
    47 Goal "new_tv n sch --> new_tv (n + (min_new_bound_tv sch)) (bound_typ_inst (%b. TVar (b + n)) sch)";
    48 by (type_scheme.induct_tac "sch" 1);
    48 by (type_scheme.induct_tac "sch" 1);
    49   by (Asm_full_simp_tac 1);
    49   by (Asm_full_simp_tac 1);
    50  by (asm_full_simp_tac (simpset() addsimps [add_commute]) 1);
    50  by (asm_full_simp_tac (simpset() addsimps [add_commute]) 1);
    51 by (strip_tac 1);
    51 by (strip_tac 1);
    52 by (Asm_full_simp_tac 1);
    52 by (Asm_full_simp_tac 1);
   153 by (assume_tac 1);
   153 by (assume_tac 1);
   154 by (assume_tac 1);
   154 by (assume_tac 1);
   155 by (assume_tac 1);
   155 by (assume_tac 1);
   156 qed_spec_mp "new_tv_W";
   156 qed_spec_mp "new_tv_W";
   157 
   157 
   158 Goal "!!sch. (v ~: free_tv sch) --> (v : free_tv (bound_typ_inst (TVar o S) sch)) --> (? x. v = S x)";
   158 Goal "(v ~: free_tv sch) --> (v : free_tv (bound_typ_inst (TVar o S) sch)) --> (? x. v = S x)";
   159 by (type_scheme.induct_tac "sch" 1);
   159 by (type_scheme.induct_tac "sch" 1);
   160 by (Asm_full_simp_tac 1);
   160 by (Asm_full_simp_tac 1);
   161 by (Asm_full_simp_tac 1);
   161 by (Asm_full_simp_tac 1);
   162 by (strip_tac 1);
   162 by (strip_tac 1);
   163 by (rtac exI 1);
   163 by (rtac exI 1);
   252               addDs [less_le_trans]) 1);
   252               addDs [less_le_trans]) 1);
   253 by (fast_tac (claset() addSDs [codD,free_tv_app_subst_scheme_list RS subsetD,W_var_ge] 
   253 by (fast_tac (claset() addSDs [codD,free_tv_app_subst_scheme_list RS subsetD,W_var_ge] 
   254               addDs [less_le_trans]) 1);
   254               addDs [less_le_trans]) 1);
   255 qed_spec_mp "free_tv_W"; 
   255 qed_spec_mp "free_tv_W"; 
   256 
   256 
   257 Goal "!!A. (!x. x : A --> x ~: B) ==> A Int B = {}";
   257 Goal "(!x. x : A --> x ~: B) ==> A Int B = {}";
   258 by (Fast_tac 1);
   258 by (Fast_tac 1);
   259 val weaken_A_Int_B_eq_empty = result();
   259 val weaken_A_Int_B_eq_empty = result();
   260 
   260 
   261 Goal "!!A. x ~: A | x : B ==> x ~: A - B";
   261 Goal "x ~: A | x : B ==> x ~: A - B";
   262 by (Fast_tac 1);
   262 by (Fast_tac 1);
   263 val weaken_not_elem_A_minus_B = result();
   263 val weaken_not_elem_A_minus_B = result();
   264 
   264 
   265 (* correctness of W with respect to has_type *)
   265 (* correctness of W with respect to has_type *)
   266 Goal
   266 Goal
   557 by (res_inst_tac [("x","Ra")] exI 1);
   557 by (res_inst_tac [("x","Ra")] exI 1);
   558 by (simp_tac (simpset() addsimps [o_def,subst_comp_scheme_list RS sym]) 1);
   558 by (simp_tac (simpset() addsimps [o_def,subst_comp_scheme_list RS sym]) 1);
   559 qed_spec_mp "W_complete_lemma";
   559 qed_spec_mp "W_complete_lemma";
   560 
   560 
   561 Goal
   561 Goal
   562  "!!e. [] |- e :: t' ==>  (? S t. (? m. W e [] n = Some(S,t,m)) &  \
   562  "[] |- e :: t' ==>  (? S t. (? m. W e [] n = Some(S,t,m)) &  \
   563 \                                 (? R. t' = $ R t))";
   563 \                                 (? R. t' = $ R t))";
   564 by (cut_inst_tac [("A","[]"),("S'","id_subst"),("e","e"),("t'","t'")]
   564 by (cut_inst_tac [("A","[]"),("S'","id_subst"),("e","e"),("t'","t'")]
   565                 W_complete_lemma 1);
   565                 W_complete_lemma 1);
   566 by (ALLGOALS Asm_full_simp_tac);
   566 by (ALLGOALS Asm_full_simp_tac);
   567 qed "W_complete";
   567 qed "W_complete";