src/HOL/MiniML/W.ML
changeset 2031 03a843f0f447
parent 1950 97f1c6bf3ace
child 2058 ff04984186e9
equal deleted inserted replaced
2030:474b3f208789 2031:03a843f0f447
    20 (* case Abs e *)
    20 (* case Abs e *)
    21 by (asm_full_simp_tac (!simpset addsimps [app_subst_list]
    21 by (asm_full_simp_tac (!simpset addsimps [app_subst_list]
    22                         setloop (split_tac [expand_bind])) 1);
    22                         setloop (split_tac [expand_bind])) 1);
    23 by (strip_tac 1);
    23 by (strip_tac 1);
    24 by (eres_inst_tac [("x","TVar(n) # a")] allE 1);
    24 by (eres_inst_tac [("x","TVar(n) # a")] allE 1);
    25 by( fast_tac (HOL_cs addss (!simpset addsimps [eq_sym_conv])) 1);
    25 by ( fast_tac (HOL_cs addss (!simpset addsimps [eq_sym_conv])) 1);
    26 (* case App e1 e2 *)
    26 (* case App e1 e2 *)
    27 by (simp_tac (!simpset setloop (split_tac [expand_bind])) 1);
    27 by (simp_tac (!simpset setloop (split_tac [expand_bind])) 1);
    28 by (strip_tac 1);
    28 by (strip_tac 1);
    29 by( rename_tac "sa ta na sb tb nb sc" 1);
    29 by ( rename_tac "sa ta na sb tb nb sc" 1);
    30 by (res_inst_tac [("t2.0","$ sc tb")] has_type.AppI 1);
    30 by (res_inst_tac [("t2.0","$ sc tb")] has_type.AppI 1);
    31 by (res_inst_tac [("s1","sc")] (app_subst_TVar RS subst) 1);
    31 by (res_inst_tac [("s1","sc")] (app_subst_TVar RS subst) 1);
    32 by (rtac (app_subst_Fun RS subst) 1);
    32 by (rtac (app_subst_Fun RS subst) 1);
    33 by (res_inst_tac [("t","$sc(tb -> (TVar nb))"),("s","$sc($sb ta)")] subst 1);
    33 by (res_inst_tac [("t","$sc(tb -> (TVar nb))"),("s","$sc($sb ta)")] subst 1);
    34 by (Asm_full_simp_tac 1);
    34 by (Asm_full_simp_tac 1);
    81 qed "W_var_geD";
    81 qed "W_var_geD";
    82 
    82 
    83 
    83 
    84 (* auxiliary lemma *)
    84 (* auxiliary lemma *)
    85 goal Maybe.thy "(y = Ok x) = (Ok x = y)";
    85 goal Maybe.thy "(y = Ok x) = (Ok x = y)";
    86 by( simp_tac (!simpset addsimps [eq_sym_conv]) 1);
    86 by ( simp_tac (!simpset addsimps [eq_sym_conv]) 1);
    87 qed "rotate_Ok";
    87 qed "rotate_Ok";
    88 
    88 
    89 
    89 
    90 (* resulting type variable is new *)
    90 (* resulting type variable is new *)
    91 goal thy
    91 goal thy
   119 by (asm_full_simp_tac (!simpset addsimps [eq_sym_conv]) 1);
   119 by (asm_full_simp_tac (!simpset addsimps [eq_sym_conv]) 1);
   120 by (eres_inst_tac [("x","$ s a")] allE 1);
   120 by (eres_inst_tac [("x","$ s a")] allE 1);
   121 by (eres_inst_tac [("x","sa")] allE 1);
   121 by (eres_inst_tac [("x","sa")] allE 1);
   122 by (eres_inst_tac [("x","ta")] allE 1);
   122 by (eres_inst_tac [("x","ta")] allE 1);
   123 by (eres_inst_tac [("x","nb")] allE 1);
   123 by (eres_inst_tac [("x","nb")] allE 1);
   124 by( asm_full_simp_tac (!simpset addsimps [o_def,rotate_Ok]) 1);
   124 by ( asm_full_simp_tac (!simpset addsimps [o_def,rotate_Ok]) 1);
   125 by (rtac conjI 1);
   125 by (rtac conjI 1);
   126 by (rtac new_tv_subst_comp_2 1);
   126 by (rtac new_tv_subst_comp_2 1);
   127 by (rtac new_tv_subst_comp_2 1);
   127 by (rtac new_tv_subst_comp_2 1);
   128 by (rtac (lessI RS less_imp_le RS new_tv_subst_le) 1);
   128 by (rtac (lessI RS less_imp_le RS new_tv_subst_le) 1);
   129 by (res_inst_tac [("n","na")] new_tv_subst_le 1); 
   129 by (res_inst_tac [("n","na")] new_tv_subst_le 1); 
   132 by (fast_tac (HOL_cs addDs [W_var_geD] addIs
   132 by (fast_tac (HOL_cs addDs [W_var_geD] addIs
   133      [new_tv_list_le,new_tv_subst_tel,lessI RS less_imp_le RS new_tv_subst_le])
   133      [new_tv_list_le,new_tv_subst_tel,lessI RS less_imp_le RS new_tv_subst_le])
   134     1);
   134     1);
   135 by (etac (sym RS mgu_new) 1);
   135 by (etac (sym RS mgu_new) 1);
   136 by (best_tac (HOL_cs addDs [W_var_geD] 
   136 by (best_tac (HOL_cs addDs [W_var_geD] 
   137 	             addIs [new_tv_subst_te,new_tv_list_le,
   137                      addIs [new_tv_subst_te,new_tv_list_le,
   138 			    new_tv_subst_tel,
   138                             new_tv_subst_tel,
   139 			    lessI RS less_imp_le RS new_tv_le,
   139                             lessI RS less_imp_le RS new_tv_le,
   140 			    lessI RS less_imp_le RS new_tv_subst_le,
   140                             lessI RS less_imp_le RS new_tv_subst_le,
   141 			    new_tv_le]) 1);
   141                             new_tv_le]) 1);
   142 by (fast_tac (HOL_cs addDs [W_var_geD] 
   142 by (fast_tac (HOL_cs addDs [W_var_geD] 
   143 	             addIs [new_tv_list_le,new_tv_subst_tel,new_tv_le] 
   143                      addIs [new_tv_list_le,new_tv_subst_tel,new_tv_le] 
   144 		     addss (!simpset)) 1);
   144                      addss (!simpset)) 1);
   145 by (rtac (lessI RS new_tv_subst_var) 1);
   145 by (rtac (lessI RS new_tv_subst_var) 1);
   146 by (etac (sym RS mgu_new) 1);
   146 by (etac (sym RS mgu_new) 1);
   147 by (best_tac (HOL_cs addSIs [lessI RS less_imp_le RS new_tv_le,new_tv_subst_te]
   147 by (best_tac (HOL_cs addSIs [lessI RS less_imp_le RS new_tv_le,new_tv_subst_te]
   148                      addDs [W_var_geD]
   148                      addDs [W_var_geD]
   149 		     addIs [new_tv_list_le,
   149                      addIs [new_tv_list_le,
   150 			    new_tv_subst_tel,
   150                             new_tv_subst_tel,
   151 			    lessI RS less_imp_le RS new_tv_subst_le,
   151                             lessI RS less_imp_le RS new_tv_subst_le,
   152 			    new_tv_le] 
   152                             new_tv_le] 
   153 		     addss !simpset) 1);
   153                      addss !simpset) 1);
   154 by (fast_tac (HOL_cs addDs [W_var_geD] 
   154 by (fast_tac (HOL_cs addDs [W_var_geD] 
   155 	             addIs [new_tv_list_le,new_tv_subst_tel,new_tv_le]
   155                      addIs [new_tv_list_le,new_tv_subst_tel,new_tv_le]
   156                      addss (!simpset)) 1);
   156                      addss (!simpset)) 1);
   157 qed_spec_mp "new_tv_W";
   157 qed_spec_mp "new_tv_W";
   158 
   158 
   159 
   159 
   160 goal thy
   160 goal thy
   224 \                     (? r. $s' a = $r ($s a) & t' = $r t))";
   224 \                     (? r. $s' a = $r ($s a) & t' = $r t))";
   225 by (expr.induct_tac "e" 1);
   225 by (expr.induct_tac "e" 1);
   226 (* case Var n *)
   226 (* case Var n *)
   227 by (strip_tac 1);
   227 by (strip_tac 1);
   228 by (simp_tac (!simpset addcongs [conj_cong] 
   228 by (simp_tac (!simpset addcongs [conj_cong] 
   229 	      setloop (split_tac [expand_if])) 1);
   229               setloop (split_tac [expand_if])) 1);
   230 by (eresolve_tac has_type_casesE 1); 
   230 by (eresolve_tac has_type_casesE 1); 
   231 by (asm_full_simp_tac (!simpset addsimps [eq_sym_conv,app_subst_list]) 1);
   231 by (asm_full_simp_tac (!simpset addsimps [eq_sym_conv,app_subst_list]) 1);
   232 by (res_inst_tac [("x","id_subst")] exI 1);
   232 by (res_inst_tac [("x","id_subst")] exI 1);
   233 by (res_inst_tac [("x","nth nat a")] exI 1);
   233 by (res_inst_tac [("x","nth nat a")] exI 1);
   234 by (Simp_tac 1);
   234 by (Simp_tac 1);
   241 by (eres_inst_tac [("x","%x.if x=n then t1 else (s' x)")] allE 1);
   241 by (eres_inst_tac [("x","%x.if x=n then t1 else (s' x)")] allE 1);
   242 by (eres_inst_tac [("x","(TVar n)#a")] allE 1);
   242 by (eres_inst_tac [("x","(TVar n)#a")] allE 1);
   243 by (eres_inst_tac [("x","t2")] allE 1);
   243 by (eres_inst_tac [("x","t2")] allE 1);
   244 by (eres_inst_tac [("x","Suc n")] allE 1);
   244 by (eres_inst_tac [("x","Suc n")] allE 1);
   245 by (fast_tac (HOL_cs addss (!simpset addcongs [conj_cong]
   245 by (fast_tac (HOL_cs addss (!simpset addcongs [conj_cong]
   246 			    setloop (split_tac [expand_bind]))) 1);
   246                             setloop (split_tac [expand_bind]))) 1);
   247 
   247 
   248 (* case App e1 e2 *)
   248 (* case App e1 e2 *)
   249 by (strip_tac 1);
   249 by (strip_tac 1);
   250 by (eresolve_tac has_type_casesE 1);
   250 by (eresolve_tac has_type_casesE 1);
   251 by (eres_inst_tac [("x","s'")] allE 1);
   251 by (eres_inst_tac [("x","s'")] allE 1);
   262 by (dtac asm_rl 1);
   262 by (dtac asm_rl 1);
   263 by (Asm_full_simp_tac 1);
   263 by (Asm_full_simp_tac 1);
   264 by (safe_tac HOL_cs);
   264 by (safe_tac HOL_cs);
   265 by (fast_tac HOL_cs 1);
   265 by (fast_tac HOL_cs 1);
   266 by (fast_tac (HOL_cs addIs [sym RS W_var_geD,new_tv_W RS
   266 by (fast_tac (HOL_cs addIs [sym RS W_var_geD,new_tv_W RS
   267 			    conjunct1,new_tv_list_le,new_tv_subst_tel]) 1);
   267                             conjunct1,new_tv_list_le,new_tv_subst_tel]) 1);
   268 
   268 
   269 by (subgoal_tac
   269 by (subgoal_tac
   270   "$ (%x.if x=ma then t' else (if x:(free_tv t - free_tv sa) then r x \
   270   "$ (%x.if x=ma then t' else (if x:(free_tv t - free_tv sa) then r x \
   271 \        else ra x)) ($ sa t) = \
   271 \        else ra x)) ($ sa t) = \
   272 \  $ (%x.if x=ma then t' else (if x:(free_tv t - free_tv sa) then r x \
   272 \  $ (%x.if x=ma then t' else (if x:(free_tv t - free_tv sa) then r x \
   277 by (asm_simp_tac (!simpset addsimps [subst_comp_te]) 2);
   277 by (asm_simp_tac (!simpset addsimps [subst_comp_te]) 2);
   278 by (rtac eq_free_eq_subst_te 2);  
   278 by (rtac eq_free_eq_subst_te 2);  
   279 by (strip_tac 2);
   279 by (strip_tac 2);
   280 by (subgoal_tac "na ~=ma" 2);
   280 by (subgoal_tac "na ~=ma" 2);
   281 by (fast_tac (HOL_cs addDs [new_tv_W,sym RS W_var_geD,
   281 by (fast_tac (HOL_cs addDs [new_tv_W,sym RS W_var_geD,
   282 			    new_tv_not_free_tv,new_tv_le]) 3);
   282                             new_tv_not_free_tv,new_tv_le]) 3);
   283 by (case_tac "na:free_tv sa" 2);
   283 by (case_tac "na:free_tv sa" 2);
   284 (* na ~: free_tv sa *)
   284 (* na ~: free_tv sa *)
   285 by (asm_simp_tac (!simpset addsimps [not_free_impl_id]
   285 by (asm_simp_tac (!simpset addsimps [not_free_impl_id]
   286 		  setloop (split_tac [expand_if])) 3);
   286                   setloop (split_tac [expand_if])) 3);
   287 (* na : free_tv sa *)
   287 (* na : free_tv sa *)
   288 by (dres_inst_tac [("ts1","$ s a")] (subst_comp_tel RSN (2,trans)) 2);
   288 by (dres_inst_tac [("ts1","$ s a")] (subst_comp_tel RSN (2,trans)) 2);
   289 by (dtac eq_subst_tel_eq_free 2);
   289 by (dtac eq_subst_tel_eq_free 2);
   290 by (fast_tac (HOL_cs addIs [free_tv_W,free_tv_le_new_tv] addDs [new_tv_W]) 2);
   290 by (fast_tac (HOL_cs addIs [free_tv_W,free_tv_le_new_tv] addDs [new_tv_W]) 2);
   291 by (Asm_simp_tac 2); 
   291 by (Asm_simp_tac 2); 
   292 by (case_tac "na:dom sa" 2);
   292 by (case_tac "na:dom sa" 2);
   293 (* na ~: dom sa *)
   293 (* na ~: dom sa *)
   294 by (asm_full_simp_tac (!simpset addsimps [dom_def] 
   294 by (asm_full_simp_tac (!simpset addsimps [dom_def] 
   295 		       setloop (split_tac [expand_if])) 3);
   295                        setloop (split_tac [expand_if])) 3);
   296 (* na : dom sa *)
   296 (* na : dom sa *)
   297 by (rtac eq_free_eq_subst_te 2);
   297 by (rtac eq_free_eq_subst_te 2);
   298 by (strip_tac 2);
   298 by (strip_tac 2);
   299 by (subgoal_tac "nb ~= ma" 2);
   299 by (subgoal_tac "nb ~= ma" 2);
   300 by ((forward_tac [new_tv_W] 3) THEN (atac 3));
   300 by ((forward_tac [new_tv_W] 3) THEN (atac 3));
   301 by (etac conjE 3);
   301 by (etac conjE 3);
   302 by (dtac new_tv_subst_tel 3);
   302 by (dtac new_tv_subst_tel 3);
   303 by (fast_tac (HOL_cs addIs [new_tv_list_le] addDs [sym RS W_var_geD]) 3);
   303 by (fast_tac (HOL_cs addIs [new_tv_list_le] addDs [sym RS W_var_geD]) 3);
   304 by (fast_tac (set_cs addDs [new_tv_W,new_tv_not_free_tv] addss 
   304 by (fast_tac (set_cs addDs [new_tv_W,new_tv_not_free_tv] addss 
   305 	      (!simpset addsimps [cod_def,free_tv_subst])) 3);
   305               (!simpset addsimps [cod_def,free_tv_subst])) 3);
   306 by (fast_tac (set_cs addss (!simpset addsimps [cod_def,free_tv_subst] 
   306 by (fast_tac (set_cs addss (!simpset addsimps [cod_def,free_tv_subst] 
   307 			    setloop (split_tac [expand_if]))) 2);
   307                             setloop (split_tac [expand_if]))) 2);
   308 
   308 
   309 by (Simp_tac 2);  
   309 by (Simp_tac 2);  
   310 by (rtac eq_free_eq_subst_te 2);
   310 by (rtac eq_free_eq_subst_te 2);
   311 by (strip_tac 2 );
   311 by (strip_tac 2 );
   312 by (subgoal_tac "na ~= ma" 2);
   312 by (subgoal_tac "na ~= ma" 2);
   314 by (etac conjE 3);
   314 by (etac conjE 3);
   315 by (dtac (sym RS W_var_geD) 3);
   315 by (dtac (sym RS W_var_geD) 3);
   316 by (fast_tac (HOL_cs addDs [new_tv_list_le,new_tv_subst_tel,new_tv_W,new_tv_not_free_tv]) 3);
   316 by (fast_tac (HOL_cs addDs [new_tv_list_le,new_tv_subst_tel,new_tv_W,new_tv_not_free_tv]) 3);
   317 by (case_tac "na: free_tv t - free_tv sa" 2);
   317 by (case_tac "na: free_tv t - free_tv sa" 2);
   318 (* case na ~: free_tv t - free_tv sa *)
   318 (* case na ~: free_tv t - free_tv sa *)
   319 by( asm_full_simp_tac (!simpset setloop (split_tac [expand_if])) 3);
   319 by ( asm_full_simp_tac (!simpset setloop (split_tac [expand_if])) 3);
   320 (* case na : free_tv t - free_tv sa *)
   320 (* case na : free_tv t - free_tv sa *)
   321 by( asm_full_simp_tac (!simpset setloop (split_tac [expand_if])) 2);
   321 by ( asm_full_simp_tac (!simpset setloop (split_tac [expand_if])) 2);
   322 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);
   323 by (dtac eq_subst_tel_eq_free 2);
   323 by (dtac eq_subst_tel_eq_free 2);
   324 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);
   325 by (asm_full_simp_tac (!simpset addsimps [free_tv_subst,dom_def,de_Morgan_disj]) 2);
   325 by (asm_full_simp_tac (!simpset addsimps [free_tv_subst,dom_def,de_Morgan_disj]) 2);
   326 
   326 
   327 by (asm_simp_tac (!simpset setloop (split_tac [expand_bind])) 1); 
   327 by (asm_simp_tac (!simpset setloop (split_tac [expand_bind])) 1); 
   328 by (safe_tac HOL_cs );
   328 by (safe_tac HOL_cs );
   329 by (dtac mgu_Ok 1);
   329 by (dtac mgu_Ok 1);
   330 by( fast_tac (HOL_cs addss !simpset) 1);
   330 by ( fast_tac (HOL_cs addss !simpset) 1);
   331 by (REPEAT (resolve_tac [exI,conjI] 1));
   331 by (REPEAT (resolve_tac [exI,conjI] 1));
   332 by (fast_tac HOL_cs 1);
   332 by (fast_tac HOL_cs 1);
   333 by (fast_tac HOL_cs 1);
   333 by (fast_tac HOL_cs 1);
   334 by ((dtac mgu_mg 1) THEN (atac 1));
   334 by ((dtac mgu_mg 1) THEN (atac 1));
   335 by (etac exE 1);
   335 by (etac exE 1);
   336 by (res_inst_tac [("x","rb")] exI 1);
   336 by (res_inst_tac [("x","rb")] exI 1);
   337 by (rtac conjI 1);
   337 by (rtac conjI 1);
   338 by (dres_inst_tac [("x","ma")] fun_cong 2);
   338 by (dres_inst_tac [("x","ma")] fun_cong 2);
   339 by( asm_full_simp_tac (!simpset addsimps [eq_sym_conv]) 2);
   339 by ( asm_full_simp_tac (!simpset addsimps [eq_sym_conv]) 2);
   340 by (simp_tac (!simpset addsimps [subst_comp_tel RS sym]) 1);
   340 by (simp_tac (!simpset addsimps [subst_comp_tel RS sym]) 1);
   341 by (res_inst_tac [("ts2","($ sa ($ s a))")] ((subst_comp_tel RS sym) RSN 
   341 by (res_inst_tac [("ts2","($ sa ($ s a))")] ((subst_comp_tel RS sym) RSN 
   342     (2,trans)) 1);
   342     (2,trans)) 1);
   343 by( asm_full_simp_tac (!simpset addsimps [o_def,eq_sym_conv]) 1);
   343 by ( asm_full_simp_tac (!simpset addsimps [o_def,eq_sym_conv]) 1);
   344 by (rtac eq_free_eq_subst_tel 1);
   344 by (rtac eq_free_eq_subst_tel 1);
   345 by( safe_tac HOL_cs );
   345 by ( safe_tac HOL_cs );
   346 by (subgoal_tac "ma ~= na" 1);
   346 by (subgoal_tac "ma ~= na" 1);
   347 by ((forward_tac [new_tv_W] 2) THEN (atac 2));
   347 by ((forward_tac [new_tv_W] 2) THEN (atac 2));
   348 by (etac conjE 2);
   348 by (etac conjE 2);
   349 by (dtac new_tv_subst_tel 2);
   349 by (dtac new_tv_subst_tel 2);
   350 by (fast_tac (HOL_cs addIs [new_tv_list_le] addDs [sym RS W_var_geD]) 2);
   350 by (fast_tac (HOL_cs addIs [new_tv_list_le] addDs [sym RS W_var_geD]) 2);
   365 qed_spec_mp "W_complete_lemma";
   365 qed_spec_mp "W_complete_lemma";
   366 
   366 
   367 goal W.thy
   367 goal W.thy
   368  "!!e. [] |- e :: t' ==>  (? s t. (? m. W e [] n = Ok(s,t,m)) &  \
   368  "!!e. [] |- e :: t' ==>  (? s t. (? m. W e [] n = Ok(s,t,m)) &  \
   369 \                                 (? r. t' = $r t))";
   369 \                                 (? r. t' = $r t))";
   370 by(cut_inst_tac [("a","[]"),("s'","id_subst"),("e","e"),("t'","t'")]
   370 by (cut_inst_tac [("a","[]"),("s'","id_subst"),("e","e"),("t'","t'")]
   371                 W_complete_lemma 1);
   371                 W_complete_lemma 1);
   372 by(ALLGOALS Asm_full_simp_tac);
   372 by (ALLGOALS Asm_full_simp_tac);
   373 qed "W_complete";
   373 qed "W_complete";