src/HOLCF/IOA/meta_theory/SimCorrectness.ML
changeset 6161 bc2a76ce1ea3
parent 5132 24f992a25adc
child 7229 6773ba0c36d5
equal deleted inserted replaced
6160:32c0b8f57bb7 6161:bc2a76ce1ea3
    67 section"properties of move";
    67 section"properties of move";
    68 
    68 
    69 Delsimps [Let_def];
    69 Delsimps [Let_def];
    70 
    70 
    71 Goalw [is_simulation_def]
    71 Goalw [is_simulation_def]
    72    "!!f. [|is_simulation R C A; reachable C s; s -a--C-> t; (s,s'):R|] ==>\
    72    "[|is_simulation R C A; reachable C s; s -a--C-> t; (s,s'):R|] ==>\
    73 \     let T' = @t'. ? ex1. (t,t'):R & move A ex1 s' a t' in \
    73 \     let T' = @t'. ? ex1. (t,t'):R & move A ex1 s' a t' in \
    74 \     (t,T'): R & move A (@ex2. move A ex2 s' a T') s' a T'";
    74 \     (t,T'): R & move A (@ex2. move A ex2 s' a T') s' a T'";
    75 
    75 
    76 (* Does not perform conditional rewriting on assumptions automatically as
    76 (* Does not perform conditional rewriting on assumptions automatically as
    77    usual. Instantiate all variables per hand. Ask Tobias?? *)
    77    usual. Instantiate all variables per hand. Ask Tobias?? *)
    97 
    97 
    98 
    98 
    99 Addsimps [Let_def];
    99 Addsimps [Let_def];
   100 
   100 
   101 Goal
   101 Goal
   102    "!!f. [|is_simulation R C A; reachable C s; s-a--C-> t; (s,s'):R|] ==>\
   102    "[|is_simulation R C A; reachable C s; s-a--C-> t; (s,s'):R|] ==>\
   103 \   let T' = @t'. ? ex1. (t,t'):R & move A ex1 s' a t' in \
   103 \   let T' = @t'. ? ex1. (t,t'):R & move A ex1 s' a t' in \
   104 \    is_exec_frag A (s',@x. move A x s' a T')";
   104 \    is_exec_frag A (s',@x. move A x s' a T')";
   105 by (cut_inst_tac [] move_is_move_sim 1);
   105 by (cut_inst_tac [] move_is_move_sim 1);
   106 by (REPEAT (assume_tac 1));
   106 by (REPEAT (assume_tac 1));
   107 by (asm_full_simp_tac (simpset() addsimps [move_def,Let_def]) 1);
   107 by (asm_full_simp_tac (simpset() addsimps [move_def,Let_def]) 1);
   108 qed"move_subprop1_sim";
   108 qed"move_subprop1_sim";
   109 
   109 
   110 Goal
   110 Goal
   111    "!!f. [|is_simulation R C A; reachable C s; s-a--C-> t; (s,s'):R|] ==>\
   111    "[|is_simulation R C A; reachable C s; s-a--C-> t; (s,s'):R|] ==>\
   112 \   let T' = @t'. ? ex1. (t,t'):R & move A ex1 s' a t' in \
   112 \   let T' = @t'. ? ex1. (t,t'):R & move A ex1 s' a t' in \
   113 \   Finite (@x. move A x s' a T')";
   113 \   Finite (@x. move A x s' a T')";
   114 by (cut_inst_tac [] move_is_move_sim 1);
   114 by (cut_inst_tac [] move_is_move_sim 1);
   115 by (REPEAT (assume_tac 1));
   115 by (REPEAT (assume_tac 1));
   116 by (asm_full_simp_tac (simpset() addsimps [move_def,Let_def]) 1);
   116 by (asm_full_simp_tac (simpset() addsimps [move_def,Let_def]) 1);
   117 qed"move_subprop2_sim";
   117 qed"move_subprop2_sim";
   118 
   118 
   119 Goal
   119 Goal
   120    "!!f. [|is_simulation R C A; reachable C s; s-a--C-> t; (s,s'):R|] ==>\
   120    "[|is_simulation R C A; reachable C s; s-a--C-> t; (s,s'):R|] ==>\
   121 \   let T' = @t'. ? ex1. (t,t'):R & move A ex1 s' a t' in \
   121 \   let T' = @t'. ? ex1. (t,t'):R & move A ex1 s' a t' in \
   122 \    laststate (s',@x. move A x s' a T') = T'";
   122 \    laststate (s',@x. move A x s' a T') = T'";
   123 by (cut_inst_tac [] move_is_move_sim 1);
   123 by (cut_inst_tac [] move_is_move_sim 1);
   124 by (REPEAT (assume_tac 1));
   124 by (REPEAT (assume_tac 1));
   125 by (asm_full_simp_tac (simpset() addsimps [move_def,Let_def]) 1);
   125 by (asm_full_simp_tac (simpset() addsimps [move_def,Let_def]) 1);
   126 qed"move_subprop3_sim";
   126 qed"move_subprop3_sim";
   127 
   127 
   128 Goal
   128 Goal
   129    "!!f. [|is_simulation R C A; reachable C s; s-a--C-> t; (s,s'):R|] ==>\
   129    "[|is_simulation R C A; reachable C s; s-a--C-> t; (s,s'):R|] ==>\
   130 \   let T' = @t'. ? ex1. (t,t'):R & move A ex1 s' a t' in \
   130 \   let T' = @t'. ? ex1. (t,t'):R & move A ex1 s' a t' in \
   131 \     mk_trace A`((@x. move A x s' a T')) = \
   131 \     mk_trace A`((@x. move A x s' a T')) = \
   132 \       (if a:ext A then a>>nil else nil)";
   132 \       (if a:ext A then a>>nil else nil)";
   133 by (cut_inst_tac [] move_is_move_sim 1);
   133 by (cut_inst_tac [] move_is_move_sim 1);
   134 by (REPEAT (assume_tac 1));
   134 by (REPEAT (assume_tac 1));
   135 by (asm_full_simp_tac (simpset() addsimps [move_def,Let_def]) 1);
   135 by (asm_full_simp_tac (simpset() addsimps [move_def,Let_def]) 1);
   136 qed"move_subprop4_sim";
   136 qed"move_subprop4_sim";
   137 
   137 
   138 Goal
   138 Goal
   139    "!!f. [|is_simulation R C A; reachable C s; s-a--C-> t; (s,s'):R|] ==>\
   139    "[|is_simulation R C A; reachable C s; s-a--C-> t; (s,s'):R|] ==>\
   140 \   let T' = @t'. ? ex1. (t,t'):R & move A ex1 s' a t' in \
   140 \   let T' = @t'. ? ex1. (t,t'):R & move A ex1 s' a t' in \
   141 \     (t,T'):R";
   141 \     (t,T'):R";
   142 by (cut_inst_tac [] move_is_move_sim 1);
   142 by (cut_inst_tac [] move_is_move_sim 1);
   143 by (REPEAT (assume_tac 1));
   143 by (REPEAT (assume_tac 1));
   144 by (asm_full_simp_tac (simpset() addsimps [move_def,Let_def]) 1);
   144 by (asm_full_simp_tac (simpset() addsimps [move_def,Let_def]) 1);
   156                  Lemma 1 :Traces coincide  
   156                  Lemma 1 :Traces coincide  
   157    ------------------------------------------------------- *)
   157    ------------------------------------------------------- *)
   158 
   158 
   159 Delsplits[split_if];
   159 Delsplits[split_if];
   160 Goal 
   160 Goal 
   161   "!!f.[|is_simulation R C A; ext C = ext A|] ==>  \     
   161   "[|is_simulation R C A; ext C = ext A|] ==>  \     
   162 \        !s s'. reachable C s & is_exec_frag C (s,ex) & (s,s'): R --> \
   162 \        !s s'. reachable C s & is_exec_frag C (s,ex) & (s,s'): R --> \
   163 \            mk_trace C`ex = mk_trace A`((corresp_ex_simC A R`ex) s')";
   163 \            mk_trace C`ex = mk_trace A`((corresp_ex_simC A R`ex) s')";
   164 
   164 
   165 by (pair_induct_tac "ex" [is_exec_frag_def] 1);
   165 by (pair_induct_tac "ex" [is_exec_frag_def] 1);
   166 (* cons case *) 
   166 (* cons case *) 
   186 (*               Lemma 2 : corresp_ex_sim is execution             *)
   186 (*               Lemma 2 : corresp_ex_sim is execution             *)
   187 (* ----------------------------------------------------------- *)
   187 (* ----------------------------------------------------------- *)
   188 
   188 
   189 
   189 
   190 Goal 
   190 Goal 
   191  "!!f.[| is_simulation R C A |] ==>\
   191  "[| is_simulation R C A |] ==>\
   192 \ !s s'. reachable C s & is_exec_frag C (s,ex) & (s,s'):R  \
   192 \ !s s'. reachable C s & is_exec_frag C (s,ex) & (s,s'):R  \
   193 \ --> is_exec_frag A (s',(corresp_ex_simC A R`ex) s')"; 
   193 \ --> is_exec_frag A (s',(corresp_ex_simC A R`ex) s')"; 
   194 
   194 
   195 by (Asm_full_simp_tac 1);
   195 by (Asm_full_simp_tac 1);
   196 by (pair_induct_tac "ex" [is_exec_frag_def] 1);
   196 by (pair_induct_tac "ex" [is_exec_frag_def] 1);
   238      for the induction cases concerning the two lemmas correpsim_is_execution and 
   238      for the induction cases concerning the two lemmas correpsim_is_execution and 
   239      traces_coincide_sim, the second for the start state case. 
   239      traces_coincide_sim, the second for the start state case. 
   240      S':= @s'. (s,s'):R & s':starts_of A, where s:starts_of C  *)
   240      S':= @s'. (s,s'):R & s':starts_of A, where s:starts_of C  *)
   241 
   241 
   242 Goal 
   242 Goal 
   243 "!!C. [| is_simulation R C A; s:starts_of C |] \
   243 "[| is_simulation R C A; s:starts_of C |] \
   244 \ ==> let S' = @s'. (s,s'):R & s':starts_of A in \
   244 \ ==> let S' = @s'. (s,s'):R & s':starts_of A in \
   245 \     (s,S'):R & S':starts_of A";
   245 \     (s,S'):R & S':starts_of A";
   246   by (asm_full_simp_tac (simpset() addsimps [is_simulation_def,
   246   by (asm_full_simp_tac (simpset() addsimps [is_simulation_def,
   247          corresp_ex_sim_def, Int_non_empty,Image_def]) 1);
   247          corresp_ex_sim_def, Int_non_empty,Image_def]) 1);
   248   by (REPEAT (etac conjE 1));
   248   by (REPEAT (etac conjE 1));
   257 bind_thm("sim_starts1",(rewrite_rule [Let_def] simulation_starts) RS conjunct1);
   257 bind_thm("sim_starts1",(rewrite_rule [Let_def] simulation_starts) RS conjunct1);
   258 bind_thm("sim_starts2",(rewrite_rule [Let_def] simulation_starts) RS conjunct2);
   258 bind_thm("sim_starts2",(rewrite_rule [Let_def] simulation_starts) RS conjunct2);
   259 
   259 
   260 
   260 
   261 Goalw [traces_def]
   261 Goalw [traces_def]
   262   "!!f. [| ext C = ext A; is_simulation R C A |] \
   262   "[| ext C = ext A; is_simulation R C A |] \
   263 \          ==> traces C <= traces A"; 
   263 \          ==> traces C <= traces A"; 
   264 
   264 
   265   by (simp_tac(simpset() addsimps [has_trace_def2])1);
   265   by (simp_tac(simpset() addsimps [has_trace_def2])1);
   266   by (safe_tac set_cs);
   266   by (safe_tac set_cs);
   267 
   267