src/HOL/W0/W.ML
changeset 4686 74a12e86b20b
parent 4089 96fba19bcbe2
child 4724 3d2375efb80e
equal deleted inserted replaced
4685:9259feeeb2c8 4686:74a12e86b20b
    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 **)