src/HOLCF/FOCUS/Buffer_adm.ML
changeset 17293 ecf182ccc3ca
parent 15188 9d57263faf9e
child 18365 0839b1ddc29b
equal deleted inserted replaced
17292:5c613b64bf0a 17293:ecf182ccc3ca
     1 (*  Title: 	HOLCF/FOCUS/Buffer_adm.ML
     1 (*  Title:      HOLCF/FOCUS/Buffer_adm.ML
     2     ID:         $Id$
     2     ID:         $Id$
     3     Author: 	David von Oheimb, TU Muenchen
     3     Author:     David von Oheimb, TU Muenchen
     4 *)
     4 *)
     5 
     5 
     6 infixr 0 y;
     6 infixr 0 y;
     7 fun _ y t = by t;
     7 fun _ y t = by t;
     8 val b=9999;
     8 val b=9999;
     9 
     9 
    10 Addsimps [thm "Fin_0"];
    10 Addsimps [thm "Fin_0"];
    11 
    11 
    12 val BufAC_Asm_d2 = prove_forw "a\\<leadsto>s:BufAC_Asm ==> ? d. a=Md d" BufAC_Asm_unfold;
    12 val BufAC_Asm_d2 = prove_forw "a\\<leadsto>s:BufAC_Asm ==> ? d. a=Md d" BufAC_Asm_unfold;
    13 val BufAC_Asm_d3 = prove_forw 
    13 val BufAC_Asm_d3 = prove_forw
    14     "a\\<leadsto>b\\<leadsto>s:BufAC_Asm ==> ? d. a=Md d & b=\\<bullet> & s:BufAC_Asm" BufAC_Asm_unfold;
    14     "a\\<leadsto>b\\<leadsto>s:BufAC_Asm ==> ? d. a=Md d & b=\\<bullet> & s:BufAC_Asm" BufAC_Asm_unfold;
    15 
    15 
    16 val BufAC_Asm_F_def3 = prove_goalw thy [BufAC_Asm_F_def] 
    16 val BufAC_Asm_F_def3 = prove_goalw (the_context ()) [BufAC_Asm_F_def]
    17  "(s:BufAC_Asm_F A) = (s=<> | \
    17  "(s:BufAC_Asm_F A) = (s=<> | \
    18 \ (? d. ft\\<cdot>s=Def(Md d)) & (rt\\<cdot>s=<> | ft\\<cdot>(rt\\<cdot>s)=Def \\<bullet> & rt\\<cdot>(rt\\<cdot>s):A))" (K [
    18 \ (? d. ft\\<cdot>s=Def(Md d)) & (rt\\<cdot>s=<> | ft\\<cdot>(rt\\<cdot>s)=Def \\<bullet> & rt\\<cdot>(rt\\<cdot>s):A))" (K [
    19 	Auto_tac]);
    19         Auto_tac]);
    20 
    20 
    21 Goal "down_cont BufAC_Asm_F";
    21 Goal "down_cont BufAC_Asm_F";
    22 by (auto_tac (claset(),simpset() addsimps [down_cont_def,BufAC_Asm_F_def3]));
    22 by (auto_tac (claset(),simpset() addsimps [down_cont_def,BufAC_Asm_F_def3]));
    23 qed "cont_BufAC_Asm_F";
    23 qed "cont_BufAC_Asm_F";
    24 
    24 
    25 val BufAC_Cmt_F_def3 = prove_goalw thy [BufAC_Cmt_F_def] 
    25 val BufAC_Cmt_F_def3 = prove_goalw (the_context ()) [BufAC_Cmt_F_def]
    26  "((s,t):BufAC_Cmt_F C) = (!d x.\
    26  "((s,t):BufAC_Cmt_F C) = (!d x.\
    27 \   (s = <>       --> t = <>                   ) & \
    27 \   (s = <>       --> t = <>                   ) & \
    28 \   (s = Md d\\<leadsto><>  --> t = <>                   ) & \
    28 \   (s = Md d\\<leadsto><>  --> t = <>                   ) & \
    29 \   (s = Md d\\<leadsto>\\<bullet>\\<leadsto>x --> ft\\<cdot>t = Def d & (x,rt\\<cdot>t):C))" (fn _=> [
    29 \   (s = Md d\\<leadsto>\\<bullet>\\<leadsto>x --> ft\\<cdot>t = Def d & (x,rt\\<cdot>t):C))" (fn _=> [
    30 	subgoal_tac "!d x. (s = Md d\\<leadsto>\\<bullet>\\<leadsto>x --> (? y. t = d\\<leadsto>y & (x,y):C)) = \
    30         subgoal_tac "!d x. (s = Md d\\<leadsto>\\<bullet>\\<leadsto>x --> (? y. t = d\\<leadsto>y & (x,y):C)) = \
    31 		   \ (s = Md d\\<leadsto>\\<bullet>\\<leadsto>x --> ft\\<cdot>t = Def d & (x,rt\\<cdot>t):C)"  1,
    31                    \ (s = Md d\\<leadsto>\\<bullet>\\<leadsto>x --> ft\\<cdot>t = Def d & (x,rt\\<cdot>t):C)"  1,
    32 	Asm_simp_tac 1,
    32         Asm_simp_tac 1,
    33 	auto_tac (claset() addIs [thm "surjectiv_scons" RS sym], simpset())]);
    33         auto_tac (claset() addIs [thm "surjectiv_scons" RS sym], simpset())]);
    34 
    34 
    35 val cont_BufAC_Cmt_F = prove_goal thy "down_cont BufAC_Cmt_F" (K [
    35 val cont_BufAC_Cmt_F = prove_goal (the_context ()) "down_cont BufAC_Cmt_F" (K [
    36 	auto_tac (claset(),simpset() addsimps [down_cont_def,BufAC_Cmt_F_def3])]);
    36         auto_tac (claset(),simpset() addsimps [down_cont_def,BufAC_Cmt_F_def3])]);
    37 
    37 
    38 
    38 
    39 (**** adm_BufAC_Asm ***********************************************************)
    39 (**** adm_BufAC_Asm ***********************************************************)
    40 
    40 
    41 Goalw [BufAC_Asm_F_def, stream_monoP_def] "stream_monoP BufAC_Asm_F";
    41 Goalw [BufAC_Asm_F_def, stream_monoP_def] "stream_monoP BufAC_Asm_F";
    42 by (res_inst_tac [("x","{x. (? d. x = Md d\\<leadsto>\\<bullet>\\<leadsto><>)}")] exI 1);
    42 by (res_inst_tac [("x","{x. (? d. x = Md d\\<leadsto>\\<bullet>\\<leadsto><>)}")] exI 1);
    43 by (res_inst_tac [("x","Suc (Suc 0)")] exI 1);
    43 by (res_inst_tac [("x","Suc (Suc 0)")] exI 1);
    44 by (Clarsimp_tac 1);
    44 by (Clarsimp_tac 1);
    45 qed "BufAC_Asm_F_stream_monoP";
    45 qed "BufAC_Asm_F_stream_monoP";
    46 
    46 
    47 val adm_BufAC_Asm = prove_goalw thy [BufAC_Asm_def] "adm (%x. x:BufAC_Asm)" (K [
    47 val adm_BufAC_Asm = prove_goalw (the_context ()) [BufAC_Asm_def] "adm (%x. x:BufAC_Asm)" (K [
    48 rtac (cont_BufAC_Asm_F RS (BufAC_Asm_F_stream_monoP RS fstream_gfp_admI))1]);
    48 rtac (cont_BufAC_Asm_F RS (BufAC_Asm_F_stream_monoP RS fstream_gfp_admI))1]);
    49 
    49 
    50 
    50 
    51 (**** adm_non_BufAC_Asm *******************************************************)
    51 (**** adm_non_BufAC_Asm *******************************************************)
    52 
    52 
    70 (*adm_non_BufAC_Asm*)
    70 (*adm_non_BufAC_Asm*)
    71 Goal "!f ff. f:BufEq --> ff:BufEq --> s:BufAC_Asm --> f\\<cdot>s = ff\\<cdot>s";
    71 Goal "!f ff. f:BufEq --> ff:BufEq --> s:BufAC_Asm --> f\\<cdot>s = ff\\<cdot>s";
    72 by (rtac fstream_ind2 1);
    72 by (rtac fstream_ind2 1);
    73 by (simp_tac (simpset() addsimps [adm_non_BufAC_Asm]) 1);
    73 by (simp_tac (simpset() addsimps [adm_non_BufAC_Asm]) 1);
    74 by   (force_tac (claset() addDs [Buf_f_empty], simpset()) 1);
    74 by   (force_tac (claset() addDs [Buf_f_empty], simpset()) 1);
    75 by  (force_tac (claset() addSDs [BufAC_Asm_d2] 
    75 by  (force_tac (claset() addSDs [BufAC_Asm_d2]
    76 		addDs [Buf_f_d] addEs [ssubst], simpset()) 1);
    76                 addDs [Buf_f_d] addEs [ssubst], simpset()) 1);
    77 by (safe_tac (claset() addSDs [BufAC_Asm_d3]));
    77 by (safe_tac (claset() addSDs [BufAC_Asm_d3]));
    78 by (REPEAT(dtac Buf_f_d_req 1));
    78 by (REPEAT(dtac Buf_f_d_req 1));
    79 by (fast_tac (claset() addEs [ssubst]) 1);
    79 by (fast_tac (claset() addEs [ssubst]) 1);
    80 qed_spec_mp "BufAC_Asm_cong";
    80 qed_spec_mp "BufAC_Asm_cong";
    81 
    81 
    82 (*adm_non_BufAC_Asm,BufAC_Asm_cong*)
    82 (*adm_non_BufAC_Asm,BufAC_Asm_cong*)
    83 val BufAC_Cmt_d_req = prove_goal thy 
    83 val BufAC_Cmt_d_req = prove_goal (the_context ())
    84 "!!X. [|f:BufEq; s:BufAC_Asm; (s, f\\<cdot>s):BufAC_Cmt|] ==> (a\\<leadsto>b\\<leadsto>s, f\\<cdot>(a\\<leadsto>b\\<leadsto>s)):BufAC_Cmt"
    84 "!!X. [|f:BufEq; s:BufAC_Asm; (s, f\\<cdot>s):BufAC_Cmt|] ==> (a\\<leadsto>b\\<leadsto>s, f\\<cdot>(a\\<leadsto>b\\<leadsto>s)):BufAC_Cmt"
    85  (K [
    85  (K [
    86 	rtac (BufAC_Cmt_unfold RS iffD2) 1,
    86         rtac (BufAC_Cmt_unfold RS iffD2) 1,
    87 	strip_tac 1,
    87         strip_tac 1,
    88 	ftac Buf_f_d_req 1,
    88         ftac Buf_f_d_req 1,
    89 	auto_tac (claset() addEs [BufAC_Asm_cong RS subst],simpset())]);
    89         auto_tac (claset() addEs [BufAC_Asm_cong RS subst],simpset())]);
    90 
    90 
    91 (*adm_BufAC_Asm*)
    91 (*adm_BufAC_Asm*)
    92 Goal "antitonP BufAC_Asm";
    92 Goal "antitonP BufAC_Asm";
    93 b y rtac antitonPI 1;
    93 b y rtac antitonPI 1;
    94 b y rtac allI 1;
    94 b y rtac allI 1;
    97 b y    rtac cont_id 1;
    97 b y    rtac cont_id 1;
    98 b y    rtac adm_BufAC_Asm 1;
    98 b y    rtac adm_BufAC_Asm 1;
    99 b y   safe_tac HOL_cs;
    99 b y   safe_tac HOL_cs;
   100 b y   rtac BufAC_Asm_empty 1;
   100 b y   rtac BufAC_Asm_empty 1;
   101 b y  force_tac (claset() addSDs [fstream_prefix]
   101 b y  force_tac (claset() addSDs [fstream_prefix]
   102 		addDs [BufAC_Asm_d2] addIs [BufAC_Asm_d],simpset()) 1;
   102                 addDs [BufAC_Asm_d2] addIs [BufAC_Asm_d],simpset()) 1;
   103 b y  force_tac (claset() addSDs [fstream_prefix]
   103 b y  force_tac (claset() addSDs [fstream_prefix]
   104 		addDs [] addIs []
   104                 addDs [] addIs []
   105 		addDs [BufAC_Asm_d3] addSIs [BufAC_Asm_d_req],simpset()) 1;
   105                 addDs [BufAC_Asm_d3] addSIs [BufAC_Asm_d_req],simpset()) 1;
   106 qed "BufAC_Asm_antiton";
   106 qed "BufAC_Asm_antiton";
   107 
   107 
   108 (*adm_BufAC_Asm,BufAC_Asm_antiton,adm_non_BufAC_Asm,BufAC_Asm_cong*)
   108 (*adm_BufAC_Asm,BufAC_Asm_antiton,adm_non_BufAC_Asm,BufAC_Asm_cong*)
   109 Goal "f:BufEq ==> ? l. !i x s. s:BufAC_Asm --> x << s --> Fin (l i) < #x --> \
   109 Goal "f:BufEq ==> ? l. !i x s. s:BufAC_Asm --> x << s --> Fin (l i) < #x --> \
   110 		\    (x,f\\<cdot>x):down_iterate BufAC_Cmt_F i --> \
   110                 \    (x,f\\<cdot>x):down_iterate BufAC_Cmt_F i --> \
   111 		\    (s,f\\<cdot>s):down_iterate BufAC_Cmt_F i";
   111                 \    (s,f\\<cdot>s):down_iterate BufAC_Cmt_F i";
   112 by (res_inst_tac [("x","%i. 2*i")] exI 1);
   112 by (res_inst_tac [("x","%i. 2*i")] exI 1);
   113 by (rtac allI 1);
   113 by (rtac allI 1);
   114 by (induct_tac "i" 1);
   114 by (induct_tac "i" 1);
   115 by ( Simp_tac 1);
   115 by ( Simp_tac 1);
   116 by (simp_tac (simpset() addsimps [add_commute]) 1);
   116 by (simp_tac (simpset() addsimps [add_commute]) 1);
   135           (ya, t) \\<in> down_iterate BufAC_Cmt_F i; ya \\<sqsubseteq> xa\\<rbrakk>
   135           (ya, t) \\<in> down_iterate BufAC_Cmt_F i; ya \\<sqsubseteq> xa\\<rbrakk>
   136        \\<Longrightarrow> (xa, rt\\<cdot>(f\\<cdot>(Md d\\<leadsto>\\<bullet>\\<leadsto>xa))) \\<in> down_iterate BufAC_Cmt_F i
   136        \\<Longrightarrow> (xa, rt\\<cdot>(f\\<cdot>(Md d\\<leadsto>\\<bullet>\\<leadsto>xa))) \\<in> down_iterate BufAC_Cmt_F i
   137 *)
   137 *)
   138 by (rotate_tac 2 1);
   138 by (rotate_tac 2 1);
   139 by (dtac BufAC_Asm_prefix2 1);
   139 by (dtac BufAC_Asm_prefix2 1);
   140 by (EVERY[ftac Buf_f_d_req 1, etac exE 1, etac conjE 1, rotate_tac ~1 1,etac ssubst 1]); 
   140 by (EVERY[ftac Buf_f_d_req 1, etac exE 1, etac conjE 1, rotate_tac ~1 1,etac ssubst 1]);
   141 by (EVERY[ftac Buf_f_d_req 1, etac exE 1, etac conjE 1]);
   141 by (EVERY[ftac Buf_f_d_req 1, etac exE 1, etac conjE 1]);
   142 by (		subgoal_tac "f\\<cdot>(Md d\\<leadsto>\\<bullet>\\<leadsto>ya) = d\\<leadsto>ffa\\<cdot>ya" 1);
   142 by (            subgoal_tac "f\\<cdot>(Md d\\<leadsto>\\<bullet>\\<leadsto>ya) = d\\<leadsto>ffa\\<cdot>ya" 1);
   143 by ( atac 2);
   143 by ( atac 2);
   144 by (		rotate_tac ~1 1);
   144 by (            rotate_tac ~1 1);
   145 by (		Asm_full_simp_tac 1);
   145 by (            Asm_full_simp_tac 1);
   146 by (hyp_subst_tac 1);
   146 by (hyp_subst_tac 1);
   147 (*
   147 (*
   148  1. \\<And>i d xa ya t ff ffa.
   148  1. \\<And>i d xa ya t ff ffa.
   149        \\<lbrakk>f\\<cdot>(Md d\\<leadsto>\\<bullet>\\<leadsto>ya) = d\\<leadsto>ffa\\<cdot>ya; Fin (2 * i) < #ya;
   149        \\<lbrakk>f\\<cdot>(Md d\\<leadsto>\\<bullet>\\<leadsto>ya) = d\\<leadsto>ffa\\<cdot>ya; Fin (2 * i) < #ya;
   150           (ya, ffa\\<cdot>ya) \\<in> down_iterate BufAC_Cmt_F i; ya \\<sqsubseteq> xa; f \\<in> BufEq;
   150           (ya, ffa\\<cdot>ya) \\<in> down_iterate BufAC_Cmt_F i; ya \\<sqsubseteq> xa; f \\<in> BufEq;
   270 qed "adm_non_BufAC_Asm'";
   270 qed "adm_non_BufAC_Asm'";
   271 
   271 
   272 Goal "f \\<in> BufEq \\<Longrightarrow> adm (\\<lambda>u. u \\<in> BufAC_Asm \\<longrightarrow> (u, f\\<cdot>u) \\<in> BufAC_Cmt)";
   272 Goal "f \\<in> BufEq \\<Longrightarrow> adm (\\<lambda>u. u \\<in> BufAC_Asm \\<longrightarrow> (u, f\\<cdot>u) \\<in> BufAC_Cmt)";
   273 by (rtac triv_admI 1);
   273 by (rtac triv_admI 1);
   274 by (Clarify_tac 1);
   274 by (Clarify_tac 1);
   275 by (eatac Buf_Eq_imp_AC_lemma 1 1); 
   275 by (eatac Buf_Eq_imp_AC_lemma 1 1);
   276       (* this is what we originally aimed to show, using admissibilty :-( *)
   276       (* this is what we originally aimed to show, using admissibilty :-( *)
   277 qed "adm_BufAC'";
   277 qed "adm_BufAC'";