src/HOLCF/IOA/ABP/Correctness.ML
changeset 5068 fb28eaa07e01
parent 4833 2e53109d4bc8
child 5192 704dd3a6d47d
equal deleted inserted replaced
5067:62b6288e6005 5068:fb28eaa07e01
    40 (* auxiliary function *)
    40 (* auxiliary function *)
    41 fun rotate n i = EVERY(replicate n (etac revcut_rl i));
    41 fun rotate n i = EVERY(replicate n (etac revcut_rl i));
    42 
    42 
    43 (* lemmas about reduce *)
    43 (* lemmas about reduce *)
    44 
    44 
    45 goal Correctness.thy "(reduce(l)=[]) = (l=[])";  
    45 Goal "(reduce(l)=[]) = (l=[])";  
    46  by (rtac iffI 1);
    46  by (rtac iffI 1);
    47  by (subgoal_tac "(l~=[]) --> (reduce(l)~=[])" 1);
    47  by (subgoal_tac "(l~=[]) --> (reduce(l)~=[])" 1);
    48  by (Fast_tac 1); 
    48  by (Fast_tac 1); 
    49  by (List.list.induct_tac "l" 1);
    49  by (List.list.induct_tac "l" 1);
    50  by (Simp_tac 1);
    50  by (Simp_tac 1);
    57  by (stac split_if 1);
    57  by (stac split_if 1);
    58  by (Asm_full_simp_tac 1);
    58  by (Asm_full_simp_tac 1);
    59  by (Asm_full_simp_tac 1);
    59  by (Asm_full_simp_tac 1);
    60 val l_iff_red_nil = result();
    60 val l_iff_red_nil = result();
    61 
    61 
    62 goal Correctness.thy "s~=[] --> hd(s)=hd(reduce(s))";
    62 Goal "s~=[] --> hd(s)=hd(reduce(s))";
    63 by (List.list.induct_tac "s" 1);
    63 by (List.list.induct_tac "s" 1);
    64 by (Simp_tac 1);
    64 by (Simp_tac 1);
    65 by (case_tac "list =[]" 1);
    65 by (case_tac "list =[]" 1);
    66 by (Asm_full_simp_tac 1);
    66 by (Asm_full_simp_tac 1);
    67 (* main case *)
    67 (* main case *)
    77 by (etac subst 1);
    77 by (etac subst 1);
    78 by (Simp_tac 1);
    78 by (Simp_tac 1);
    79 qed"hd_is_reduce_hd";
    79 qed"hd_is_reduce_hd";
    80 
    80 
    81 (* to be used in the following Lemma *)
    81 (* to be used in the following Lemma *)
    82 goal Correctness.thy "l~=[] --> reverse(reduce(l))~=[]";
    82 Goal "l~=[] --> reverse(reduce(l))~=[]";
    83 by (List.list.induct_tac "l" 1);
    83 by (List.list.induct_tac "l" 1);
    84 by (Simp_tac 1);
    84 by (Simp_tac 1);
    85 by (case_tac "list =[]" 1);
    85 by (case_tac "list =[]" 1);
    86 by (asm_full_simp_tac (simpset() addsimps [reverse_Cons]) 1);
    86 by (asm_full_simp_tac (simpset() addsimps [reverse_Cons]) 1);
    87 (* main case *)
    87 (* main case *)
    95 by (hyp_subst_tac 1);
    95 by (hyp_subst_tac 1);
    96 by (asm_full_simp_tac (simpset() addsimps [reverse_Cons]) 1); 
    96 by (asm_full_simp_tac (simpset() addsimps [reverse_Cons]) 1); 
    97 qed"rev_red_not_nil";
    97 qed"rev_red_not_nil";
    98 
    98 
    99 (* shows applicability of the induction hypothesis of the following Lemma 1 *)
    99 (* shows applicability of the induction hypothesis of the following Lemma 1 *)
   100 goal Correctness.thy "!!l.[| l~=[] |] ==>   \
   100 Goal "!!l.[| l~=[] |] ==>   \
   101 \   hd(reverse(reduce(a#l))) = hd(reverse(reduce(l)))";
   101 \   hd(reverse(reduce(a#l))) = hd(reverse(reduce(l)))";
   102  by (Simp_tac 1);
   102  by (Simp_tac 1);
   103  by (rtac (split_list_case RS iffD2) 1);
   103  by (rtac (split_list_case RS iffD2) 1);
   104  by (asm_full_simp_tac list_ss 1);
   104  by (asm_full_simp_tac list_ss 1);
   105  by (REPEAT (rtac allI 1)); 
   105  by (REPEAT (rtac allI 1)); 
   110 qed"last_ind_on_first";
   110 qed"last_ind_on_first";
   111 
   111 
   112 val impl_ss = simpset() delsimps [reduce_Cons];
   112 val impl_ss = simpset() delsimps [reduce_Cons];
   113 
   113 
   114 (* Main Lemma 1 for S_pkt in showing that reduce is refinement  *) 
   114 (* Main Lemma 1 for S_pkt in showing that reduce is refinement  *) 
   115 goal Correctness.thy 
   115 Goal 
   116    "if x=hd(reverse(reduce(l))) & reduce(l)~=[] then   \
   116    "if x=hd(reverse(reduce(l))) & reduce(l)~=[] then   \
   117 \      reduce(l@[x])=reduce(l) else                  \
   117 \      reduce(l@[x])=reduce(l) else                  \
   118 \      reduce(l@[x])=reduce(l)@[x]"; 
   118 \      reduce(l@[x])=reduce(l)@[x]"; 
   119 by (stac split_if 1);
   119 by (stac split_if 1);
   120 by (rtac conjI 1);
   120 by (rtac conjI 1);
   143 by (Asm_full_simp_tac 1);
   143 by (Asm_full_simp_tac 1);
   144 qed"reduce_hd";
   144 qed"reduce_hd";
   145 
   145 
   146 
   146 
   147 (* Main Lemma 2 for R_pkt in showing that reduce is refinement *)
   147 (* Main Lemma 2 for R_pkt in showing that reduce is refinement *)
   148 goal Correctness.thy 
   148 Goal 
   149   "!! s. [| s~=[] |] ==>  \
   149   "!! s. [| s~=[] |] ==>  \
   150 \    if hd(s)=hd(tl(s)) & tl(s)~=[] then    \
   150 \    if hd(s)=hd(tl(s)) & tl(s)~=[] then    \
   151 \      reduce(tl(s))=reduce(s) else      \
   151 \      reduce(tl(s))=reduce(s) else      \
   152 \      reduce(tl(s))=tl(reduce(s))"; 
   152 \      reduce(tl(s))=tl(reduce(s))"; 
   153 by (cut_inst_tac [("l","s")] cons_not_nil 1);
   153 by (cut_inst_tac [("l","s")] cons_not_nil 1);
   166 (*******************************************************************
   166 (*******************************************************************
   167           C h a n n e l   A b s t r a c t i o n
   167           C h a n n e l   A b s t r a c t i o n
   168  *******************************************************************)
   168  *******************************************************************)
   169 
   169 
   170 Delsplits [split_if];
   170 Delsplits [split_if];
   171 goal Correctness.thy 
   171 Goal 
   172       "is_weak_ref_map reduce ch_ioa ch_fin_ioa";
   172       "is_weak_ref_map reduce ch_ioa ch_fin_ioa";
   173 by (simp_tac (simpset() addsimps [is_weak_ref_map_def]) 1);
   173 by (simp_tac (simpset() addsimps [is_weak_ref_map_def]) 1);
   174 (* ---------------- main-part ------------------- *)
   174 (* ---------------- main-part ------------------- *)
   175 by (REPEAT (rtac allI 1));
   175 by (REPEAT (rtac allI 1));
   176 by (rtac imp_conj_lemma 1);
   176 by (rtac imp_conj_lemma 1);
   192 by (etac (hd_is_reduce_hd RS mp) 1); 
   192 by (etac (hd_is_reduce_hd RS mp) 1); 
   193 by (rtac (bool_if_impl_or RS mp) 1);
   193 by (rtac (bool_if_impl_or RS mp) 1);
   194 by (etac reduce_tl 1);
   194 by (etac reduce_tl 1);
   195 qed"channel_abstraction";
   195 qed"channel_abstraction";
   196 
   196 
   197 goal Correctness.thy 
   197 Goal 
   198       "is_weak_ref_map reduce srch_ioa srch_fin_ioa";
   198       "is_weak_ref_map reduce srch_ioa srch_fin_ioa";
   199 by (simp_tac (list_ss addsimps [srch_fin_ioa_def,rsch_fin_ioa_def,
   199 by (simp_tac (list_ss addsimps [srch_fin_ioa_def,rsch_fin_ioa_def,
   200  srch_ioa_def,rsch_ioa_def,rename_through_pmap,channel_abstraction]) 1);
   200  srch_ioa_def,rsch_ioa_def,rename_through_pmap,channel_abstraction]) 1);
   201 qed"sender_abstraction";
   201 qed"sender_abstraction";
   202 
   202 
   203 goal Correctness.thy 
   203 Goal 
   204       "is_weak_ref_map reduce rsch_ioa rsch_fin_ioa";
   204       "is_weak_ref_map reduce rsch_ioa rsch_fin_ioa";
   205 by (simp_tac (list_ss addsimps [srch_fin_ioa_def,rsch_fin_ioa_def,
   205 by (simp_tac (list_ss addsimps [srch_fin_ioa_def,rsch_fin_ioa_def,
   206  srch_ioa_def,rsch_ioa_def,rename_through_pmap,channel_abstraction]) 1);
   206  srch_ioa_def,rsch_ioa_def,rename_through_pmap,channel_abstraction]) 1);
   207 qed"receiver_abstraction";
   207 qed"receiver_abstraction";
   208 
   208 
   209 
   209 
   210 (* 3 thms that do not hold generally! The lucky restriction here is 
   210 (* 3 thms that do not hold generally! The lucky restriction here is 
   211    the absence of internal actions. *)
   211    the absence of internal actions. *)
   212 goal Correctness.thy 
   212 Goal 
   213       "is_weak_ref_map (%id. id) sender_ioa sender_ioa";
   213       "is_weak_ref_map (%id. id) sender_ioa sender_ioa";
   214 by (simp_tac (simpset() addsimps [is_weak_ref_map_def]) 1);
   214 by (simp_tac (simpset() addsimps [is_weak_ref_map_def]) 1);
   215 by (TRY(
   215 by (TRY(
   216    (rtac conjI 1) THEN
   216    (rtac conjI 1) THEN
   217 (* start states *)
   217 (* start states *)
   223 (* 7 cases *)
   223 (* 7 cases *)
   224 by (ALLGOALS (simp_tac (simpset() addsimps [externals_def] addsplits [split_if])));
   224 by (ALLGOALS (simp_tac (simpset() addsimps [externals_def] addsplits [split_if])));
   225 qed"sender_unchanged";
   225 qed"sender_unchanged";
   226 
   226 
   227 (* 2 copies of before *)
   227 (* 2 copies of before *)
   228 goal Correctness.thy 
   228 Goal 
   229       "is_weak_ref_map (%id. id) receiver_ioa receiver_ioa";
   229       "is_weak_ref_map (%id. id) receiver_ioa receiver_ioa";
   230 by (simp_tac (simpset() addsimps [is_weak_ref_map_def]) 1);
   230 by (simp_tac (simpset() addsimps [is_weak_ref_map_def]) 1);
   231 by (TRY(
   231 by (TRY(
   232    (rtac conjI 1) THEN
   232    (rtac conjI 1) THEN
   233  (* start states *)
   233  (* start states *)
   238 by (Action.action.induct_tac "a" 1);
   238 by (Action.action.induct_tac "a" 1);
   239 (* 7 cases *)
   239 (* 7 cases *)
   240 by (ALLGOALS(simp_tac (simpset() addsimps [externals_def] addsplits [split_if])));
   240 by (ALLGOALS(simp_tac (simpset() addsimps [externals_def] addsplits [split_if])));
   241 qed"receiver_unchanged";
   241 qed"receiver_unchanged";
   242 
   242 
   243 goal Correctness.thy 
   243 Goal 
   244       "is_weak_ref_map (%id. id) env_ioa env_ioa";
   244       "is_weak_ref_map (%id. id) env_ioa env_ioa";
   245 by (simp_tac (simpset() addsimps [is_weak_ref_map_def]) 1);
   245 by (simp_tac (simpset() addsimps [is_weak_ref_map_def]) 1);
   246 by (TRY(
   246 by (TRY(
   247    (rtac conjI 1) THEN
   247    (rtac conjI 1) THEN
   248 (* start states *)
   248 (* start states *)
   254 (* 7 cases *)
   254 (* 7 cases *)
   255 by (ALLGOALS(simp_tac (simpset() addsimps [externals_def] addsplits [split_if])));
   255 by (ALLGOALS(simp_tac (simpset() addsimps [externals_def] addsplits [split_if])));
   256 qed"env_unchanged";
   256 qed"env_unchanged";
   257 Addsplits [split_if];
   257 Addsplits [split_if];
   258 
   258 
   259 goal Correctness.thy "compatible srch_ioa rsch_ioa"; 
   259 Goal "compatible srch_ioa rsch_ioa"; 
   260 by (simp_tac (simpset() addsimps [compatible_def,Int_def,empty_def]) 1);
   260 by (simp_tac (simpset() addsimps [compatible_def,Int_def,empty_def]) 1);
   261 by (rtac set_ext 1);
   261 by (rtac set_ext 1);
   262 by (Action.action.induct_tac "x" 1);
   262 by (Action.action.induct_tac "x" 1);
   263 by (ALLGOALS(Simp_tac));
   263 by (ALLGOALS(Simp_tac));
   264 val compat_single_ch = result();
   264 val compat_single_ch = result();
   265 
   265 
   266 (* totally the same as before *)
   266 (* totally the same as before *)
   267 goal Correctness.thy "compatible srch_fin_ioa rsch_fin_ioa"; 
   267 Goal "compatible srch_fin_ioa rsch_fin_ioa"; 
   268 by (simp_tac (simpset() addsimps [compatible_def,Int_def,empty_def]) 1);
   268 by (simp_tac (simpset() addsimps [compatible_def,Int_def,empty_def]) 1);
   269 by (rtac set_ext 1);
   269 by (rtac set_ext 1);
   270 by (Action.action.induct_tac "x" 1);
   270 by (Action.action.induct_tac "x" 1);
   271 by (ALLGOALS(Simp_tac));
   271 by (ALLGOALS(Simp_tac));
   272 val compat_single_fin_ch = result();
   272 val compat_single_fin_ch = result();
   276                       asig_of_def, actions_def, srch_trans_def, rsch_trans_def,
   276                       asig_of_def, actions_def, srch_trans_def, rsch_trans_def,
   277                       srch_ioa_def, srch_fin_ioa_def, rsch_fin_ioa_def, 
   277                       srch_ioa_def, srch_fin_ioa_def, rsch_fin_ioa_def, 
   278                       rsch_ioa_def, Sender.sender_trans_def,
   278                       rsch_ioa_def, Sender.sender_trans_def,
   279                       Receiver.receiver_trans_def] @ set_lemmas);
   279                       Receiver.receiver_trans_def] @ set_lemmas);
   280 
   280 
   281 goal Correctness.thy "compatible receiver_ioa (srch_ioa || rsch_ioa)";
   281 Goal "compatible receiver_ioa (srch_ioa || rsch_ioa)";
   282 by (simp_tac (ss addsimps [empty_def,compatible_def,
   282 by (simp_tac (ss addsimps [empty_def,compatible_def,
   283                            asig_of_par,asig_comp_def,actions_def,
   283                            asig_of_par,asig_comp_def,actions_def,
   284                            Int_def]) 1);
   284                            Int_def]) 1);
   285 by (Simp_tac 1);
   285 by (Simp_tac 1);
   286 by (rtac set_ext 1);
   286 by (rtac set_ext 1);
   287 by (Action.action.induct_tac "x" 1);
   287 by (Action.action.induct_tac "x" 1);
   288 by (ALLGOALS Simp_tac);
   288 by (ALLGOALS Simp_tac);
   289 val compat_rec = result();
   289 val compat_rec = result();
   290 
   290 
   291 (* 5 proofs totally the same as before *)
   291 (* 5 proofs totally the same as before *)
   292 goal Correctness.thy "compatible receiver_ioa (srch_fin_ioa || rsch_fin_ioa)";
   292 Goal "compatible receiver_ioa (srch_fin_ioa || rsch_fin_ioa)";
   293 by (simp_tac (ss addsimps [empty_def,compatible_def,asig_of_par,asig_comp_def,actions_def,Int_def]) 1);
   293 by (simp_tac (ss addsimps [empty_def,compatible_def,asig_of_par,asig_comp_def,actions_def,Int_def]) 1);
   294 by (Simp_tac 1);
   294 by (Simp_tac 1);
   295 by (rtac set_ext 1);
   295 by (rtac set_ext 1);
   296 by (Action.action.induct_tac "x" 1);
   296 by (Action.action.induct_tac "x" 1);
   297 by (ALLGOALS Simp_tac);
   297 by (ALLGOALS Simp_tac);
   298 val compat_rec_fin =result();
   298 val compat_rec_fin =result();
   299 
   299 
   300 goal Correctness.thy "compatible sender_ioa \
   300 Goal "compatible sender_ioa \
   301 \      (receiver_ioa || srch_ioa || rsch_ioa)";
   301 \      (receiver_ioa || srch_ioa || rsch_ioa)";
   302 by (simp_tac (ss addsimps [empty_def,compatible_def,asig_of_par,asig_comp_def,actions_def,Int_def]) 1);
   302 by (simp_tac (ss addsimps [empty_def,compatible_def,asig_of_par,asig_comp_def,actions_def,Int_def]) 1);
   303 by (Simp_tac 1);
   303 by (Simp_tac 1);
   304 by (rtac set_ext 1);
   304 by (rtac set_ext 1);
   305 by (Action.action.induct_tac "x" 1);
   305 by (Action.action.induct_tac "x" 1);
   306 by (ALLGOALS(Simp_tac));
   306 by (ALLGOALS(Simp_tac));
   307 val compat_sen=result();
   307 val compat_sen=result();
   308 
   308 
   309 goal Correctness.thy "compatible sender_ioa\
   309 Goal "compatible sender_ioa\
   310 \      (receiver_ioa || srch_fin_ioa || rsch_fin_ioa)";
   310 \      (receiver_ioa || srch_fin_ioa || rsch_fin_ioa)";
   311 by (simp_tac (ss addsimps [empty_def,  compatible_def,asig_of_par,asig_comp_def,actions_def,Int_def]) 1);
   311 by (simp_tac (ss addsimps [empty_def,  compatible_def,asig_of_par,asig_comp_def,actions_def,Int_def]) 1);
   312 by (Simp_tac 1);
   312 by (Simp_tac 1);
   313 by (rtac set_ext 1);
   313 by (rtac set_ext 1);
   314 by (Action.action.induct_tac "x" 1);
   314 by (Action.action.induct_tac "x" 1);
   315 by (ALLGOALS(Simp_tac));
   315 by (ALLGOALS(Simp_tac));
   316 val compat_sen_fin =result();
   316 val compat_sen_fin =result();
   317 
   317 
   318 goal Correctness.thy "compatible env_ioa\
   318 Goal "compatible env_ioa\
   319 \      (sender_ioa || receiver_ioa || srch_ioa || rsch_ioa)";
   319 \      (sender_ioa || receiver_ioa || srch_ioa || rsch_ioa)";
   320 by (simp_tac (ss addsimps [empty_def,compatible_def,asig_of_par,asig_comp_def,actions_def,Int_def]) 1);
   320 by (simp_tac (ss addsimps [empty_def,compatible_def,asig_of_par,asig_comp_def,actions_def,Int_def]) 1);
   321 by (Simp_tac 1);
   321 by (Simp_tac 1);
   322 by (rtac set_ext 1);
   322 by (rtac set_ext 1);
   323 by (Action.action.induct_tac "x" 1);
   323 by (Action.action.induct_tac "x" 1);
   324 by (ALLGOALS(Simp_tac));
   324 by (ALLGOALS(Simp_tac));
   325 val compat_env=result();
   325 val compat_env=result();
   326 
   326 
   327 goal Correctness.thy "compatible env_ioa\
   327 Goal "compatible env_ioa\
   328 \      (sender_ioa || receiver_ioa || srch_fin_ioa || rsch_fin_ioa)";
   328 \      (sender_ioa || receiver_ioa || srch_fin_ioa || rsch_fin_ioa)";
   329 by (simp_tac (ss addsimps [empty_def,compatible_def,asig_of_par,asig_comp_def,actions_def,Int_def]) 1);
   329 by (simp_tac (ss addsimps [empty_def,compatible_def,asig_of_par,asig_comp_def,actions_def,Int_def]) 1);
   330 by (Simp_tac 1);
   330 by (Simp_tac 1);
   331 by (rtac set_ext 1);
   331 by (rtac set_ext 1);
   332 by (Action.action.induct_tac "x" 1);
   332 by (Action.action.induct_tac "x" 1);
   333 by (ALLGOALS Simp_tac);
   333 by (ALLGOALS Simp_tac);
   334 val compat_env_fin=result();
   334 val compat_env_fin=result();
   335 
   335 
   336 
   336 
   337 (* lemmata about externals of channels *)
   337 (* lemmata about externals of channels *)
   338 goal Correctness.thy 
   338 Goal 
   339  "externals(asig_of(srch_fin_ioa)) = externals(asig_of(srch_ioa)) &  \
   339  "externals(asig_of(srch_fin_ioa)) = externals(asig_of(srch_ioa)) &  \
   340 \ externals(asig_of(rsch_fin_ioa)) = externals(asig_of(rsch_ioa))";
   340 \ externals(asig_of(rsch_fin_ioa)) = externals(asig_of(rsch_ioa))";
   341    by (simp_tac (simpset() addsimps [externals_def]) 1);
   341    by (simp_tac (simpset() addsimps [externals_def]) 1);
   342 val ext_single_ch = result();
   342 val ext_single_ch = result();
   343 
   343 
   361                             impl_ioas @ env_ioas);
   361                             impl_ioas @ env_ioas);
   362 
   362 
   363 (* FIX: this proof should be done with compositionality on trace level, not on 
   363 (* FIX: this proof should be done with compositionality on trace level, not on 
   364         weak_ref_map level, as done here with fxg_is_weak_ref_map_of_product_IOA 
   364         weak_ref_map level, as done here with fxg_is_weak_ref_map_of_product_IOA 
   365 
   365 
   366 goal Correctness.thy 
   366 Goal 
   367      "is_weak_ref_map  abs  system_ioa  system_fin_ioa";
   367      "is_weak_ref_map  abs  system_ioa  system_fin_ioa";
   368 
   368 
   369 by (simp_tac (impl_ss delsimps ([srch_ioa_def, rsch_ioa_def, srch_fin_ioa_def,
   369 by (simp_tac (impl_ss delsimps ([srch_ioa_def, rsch_ioa_def, srch_fin_ioa_def,
   370                                  rsch_fin_ioa_def] @ env_ioas @ impl_ioas)
   370                                  rsch_fin_ioa_def] @ env_ioas @ impl_ioas)
   371                       addsimps [system_def, system_fin_def, abs_def,
   371                       addsimps [system_def, system_fin_def, abs_def,