src/HOL/IMP/Transition.ML
changeset 4089 96fba19bcbe2
parent 3439 54785105178c
child 4153 e534c4c32d54
equal deleted inserted replaced
4088:9be9e39fd862 4089:96fba19bcbe2
    32 goal Transition.thy
    32 goal Transition.thy
    33   "!s t u c d. (c,s) -n-> (SKIP,t) --> (d,t) -*-> (SKIP,u) --> \
    33   "!s t u c d. (c,s) -n-> (SKIP,t) --> (d,t) -*-> (SKIP,u) --> \
    34 \              (c;d, s) -*-> (SKIP, u)";
    34 \              (c;d, s) -*-> (SKIP, u)";
    35 by (nat_ind_tac "n" 1);
    35 by (nat_ind_tac "n" 1);
    36  (* case n = 0 *)
    36  (* case n = 0 *)
    37  by (fast_tac (!claset addIs [rtrancl_into_rtrancl2])1);
    37  by (fast_tac (claset() addIs [rtrancl_into_rtrancl2])1);
    38 (* induction step *)
    38 (* induction step *)
    39 by (safe_tac (!claset addSDs [rel_pow_Suc_D2]));
    39 by (safe_tac (claset() addSDs [rel_pow_Suc_D2]));
    40 by (split_all_tac 1);
    40 by (split_all_tac 1);
    41 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1);
    41 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1);
    42 qed_spec_mp "lemma1";
    42 qed_spec_mp "lemma1";
    43 
    43 
    44 
    44 
    45 goal Transition.thy "!!c s s1. <c,s> -c-> s1 ==> (c,s) -*-> (SKIP,s1)";
    45 goal Transition.thy "!!c s s1. <c,s> -c-> s1 ==> (c,s) -*-> (SKIP,s1)";
    46 by (etac evalc.induct 1);
    46 by (etac evalc.induct 1);
    47 
    47 
    48 (* SKIP *)
    48 (* SKIP *)
    49 by (rtac rtrancl_refl 1);
    49 by (rtac rtrancl_refl 1);
    50 
    50 
    51 (* ASSIGN *)
    51 (* ASSIGN *)
    52 by (fast_tac (!claset addSIs [r_into_rtrancl]) 1);
    52 by (fast_tac (claset() addSIs [r_into_rtrancl]) 1);
    53 
    53 
    54 (* SEMI *)
    54 (* SEMI *)
    55 by (fast_tac (!claset addDs [rtrancl_imp_UN_rel_pow] addIs [lemma1]) 1);
    55 by (fast_tac (claset() addDs [rtrancl_imp_UN_rel_pow] addIs [lemma1]) 1);
    56 
    56 
    57 (* IF *)
    57 (* IF *)
    58 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1);
    58 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1);
    59 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1);
    59 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1);
    60 
    60 
    61 (* WHILE *)
    61 (* WHILE *)
    62 by (fast_tac (!claset addSIs [r_into_rtrancl]) 1);
    62 by (fast_tac (claset() addSIs [r_into_rtrancl]) 1);
    63 by (fast_tac (!claset addDs [rtrancl_imp_UN_rel_pow]
    63 by (fast_tac (claset() addDs [rtrancl_imp_UN_rel_pow]
    64                         addIs [rtrancl_into_rtrancl2,lemma1]) 1);
    64                         addIs [rtrancl_into_rtrancl2,lemma1]) 1);
    65 
    65 
    66 qed "evalc_impl_evalc1";
    66 qed "evalc_impl_evalc1";
    67 
    67 
    68 
    68 
    69 goal Transition.thy
    69 goal Transition.thy
    70   "!c d s u. (c;d,s) -n-> (SKIP,u) --> \
    70   "!c d s u. (c;d,s) -n-> (SKIP,u) --> \
    71 \            (? t m. (c,s) -*-> (SKIP,t) & (d,t) -m-> (SKIP,u) & m <= n)";
    71 \            (? t m. (c,s) -*-> (SKIP,t) & (d,t) -m-> (SKIP,u) & m <= n)";
    72 by (nat_ind_tac "n" 1);
    72 by (nat_ind_tac "n" 1);
    73  (* case n = 0 *)
    73  (* case n = 0 *)
    74  by (fast_tac (!claset addss !simpset) 1);
    74  by (fast_tac (claset() addss simpset()) 1);
    75 (* induction step *)
    75 (* induction step *)
    76 by (fast_tac (!claset addSIs [le_SucI,le_refl]
    76 by (fast_tac (claset() addSIs [le_SucI,le_refl]
    77                      addSDs [rel_pow_Suc_D2]
    77                      addSDs [rel_pow_Suc_D2]
    78                      addSEs [rel_pow_imp_rtrancl,rtrancl_into_rtrancl2]) 1);
    78                      addSEs [rel_pow_imp_rtrancl,rtrancl_into_rtrancl2]) 1);
    79 qed_spec_mp "lemma2";
    79 qed_spec_mp "lemma2";
    80 
    80 
    81 goal Transition.thy "!s t. (c,s) -*-> (SKIP,t) --> <c,s> -c-> t";
    81 goal Transition.thy "!s t. (c,s) -*-> (SKIP,t) --> <c,s> -c-> t";
    82 by (com.induct_tac "c" 1);
    82 by (com.induct_tac "c" 1);
    83 by (safe_tac (!claset addSDs [rtrancl_imp_UN_rel_pow]));
    83 by (safe_tac (claset() addSDs [rtrancl_imp_UN_rel_pow]));
    84 
    84 
    85 (* SKIP *)
    85 (* SKIP *)
    86 by (fast_tac (!claset addSEs [rel_pow_E2]) 1);
    86 by (fast_tac (claset() addSEs [rel_pow_E2]) 1);
    87 
    87 
    88 (* ASSIGN *)
    88 (* ASSIGN *)
    89 by (fast_tac (!claset addSDs [hlemma]  addSEs [rel_pow_E2]
    89 by (fast_tac (claset() addSDs [hlemma]  addSEs [rel_pow_E2]
    90                       addss !simpset) 1);
    90                       addss simpset()) 1);
    91 
    91 
    92 (* SEMI *)
    92 (* SEMI *)
    93 by (fast_tac (!claset addSDs [lemma2,rel_pow_imp_rtrancl]) 1);
    93 by (fast_tac (claset() addSDs [lemma2,rel_pow_imp_rtrancl]) 1);
    94 
    94 
    95 (* IF *)
    95 (* IF *)
    96 by (etac rel_pow_E2 1);
    96 by (etac rel_pow_E2 1);
    97 by (Asm_full_simp_tac 1);
    97 by (Asm_full_simp_tac 1);
    98 by (fast_tac (!claset addSDs [rel_pow_imp_rtrancl]) 1);
    98 by (fast_tac (claset() addSDs [rel_pow_imp_rtrancl]) 1);
    99 
    99 
   100 (* WHILE, induction on the length of the computation *)
   100 (* WHILE, induction on the length of the computation *)
   101 by (rotate_tac 1 1);
   101 by (rotate_tac 1 1);
   102 by (etac rev_mp 1);
   102 by (etac rev_mp 1);
   103 by (res_inst_tac [("x","s")] spec 1);
   103 by (res_inst_tac [("x","s")] spec 1);
   106 by (etac rel_pow_E2 1);
   106 by (etac rel_pow_E2 1);
   107  by (Asm_full_simp_tac 1);
   107  by (Asm_full_simp_tac 1);
   108 by (eresolve_tac evalc1_Es 1);
   108 by (eresolve_tac evalc1_Es 1);
   109 
   109 
   110 (* WhileFalse *)
   110 (* WhileFalse *)
   111  by (fast_tac (!claset addSDs [hlemma]) 1);
   111  by (fast_tac (claset() addSDs [hlemma]) 1);
   112 
   112 
   113 (* WhileTrue *)
   113 (* WhileTrue *)
   114 by (fast_tac(!claset addSDs[lemma2,le_imp_less_or_eq,less_Suc_eq RS iffD2])1);
   114 by (fast_tac(claset() addSDs[lemma2,le_imp_less_or_eq,less_Suc_eq RS iffD2])1);
   115 
   115 
   116 qed_spec_mp "evalc1_impl_evalc";
   116 qed_spec_mp "evalc1_impl_evalc";
   117 
   117 
   118 
   118 
   119 (**** proof of the equivalence of evalc and evalc1 ****)
   119 (**** proof of the equivalence of evalc and evalc1 ****)
   127 
   127 
   128 goal Transition.thy
   128 goal Transition.thy
   129  "!!c1. (c1,s1) -*-> (SKIP,s2) ==> \
   129  "!!c1. (c1,s1) -*-> (SKIP,s2) ==> \
   130 \ (c2,s2) -*-> cs3 --> (c1;c2,s1) -*-> cs3";
   130 \ (c2,s2) -*-> cs3 --> (c1;c2,s1) -*-> cs3";
   131 by (etac inverse_rtrancl_induct2 1);
   131 by (etac inverse_rtrancl_induct2 1);
   132 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1);
   132 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1);
   133 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1);
   133 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1);
   134 qed_spec_mp "my_lemma1";
   134 qed_spec_mp "my_lemma1";
   135 
   135 
   136 
   136 
   137 goal Transition.thy "!!c s s1. <c,s> -c-> s1 ==> (c,s) -*-> (SKIP,s1)";
   137 goal Transition.thy "!!c s s1. <c,s> -c-> s1 ==> (c,s) -*-> (SKIP,s1)";
   138 by (etac evalc.induct 1);
   138 by (etac evalc.induct 1);
   139 
   139 
   140 (* SKIP *)
   140 (* SKIP *)
   141 by (rtac rtrancl_refl 1);
   141 by (rtac rtrancl_refl 1);
   142 
   142 
   143 (* ASSIGN *)
   143 (* ASSIGN *)
   144 by (fast_tac (!claset addSIs [r_into_rtrancl]) 1);
   144 by (fast_tac (claset() addSIs [r_into_rtrancl]) 1);
   145 
   145 
   146 (* SEMI *)
   146 (* SEMI *)
   147 by (fast_tac (!claset addIs [my_lemma1]) 1);
   147 by (fast_tac (claset() addIs [my_lemma1]) 1);
   148 
   148 
   149 (* IF *)
   149 (* IF *)
   150 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1);
   150 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1);
   151 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2]) 1);
   151 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2]) 1);
   152 
   152 
   153 (* WHILE *)
   153 (* WHILE *)
   154 by (fast_tac (!claset addSIs [r_into_rtrancl]) 1);
   154 by (fast_tac (claset() addSIs [r_into_rtrancl]) 1);
   155 by (fast_tac (!claset addIs [rtrancl_into_rtrancl2,my_lemma1]) 1);
   155 by (fast_tac (claset() addIs [rtrancl_into_rtrancl2,my_lemma1]) 1);
   156 
   156 
   157 qed "evalc_impl_evalc1";
   157 qed "evalc_impl_evalc1";
   158 
   158 
   159 (* The opposite direction is based on a Coq proof done by Ranan Fraer and
   159 (* The opposite direction is based on a Coq proof done by Ranan Fraer and
   160    Yves Bertot. The following sketch is from an email by Ranan Fraer.
   160    Yves Bertot. The following sketch is from an email by Ranan Fraer.
   199 
   199 
   200 val [major] = goal Transition.thy
   200 val [major] = goal Transition.thy
   201   "(c,s) -*-> (c',s') ==> <c',s'> -c-> t --> <c,s> -c-> t";
   201   "(c,s) -*-> (c',s') ==> <c',s'> -c-> t --> <c,s> -c-> t";
   202 by (rtac (major RS rtrancl_induct2) 1);
   202 by (rtac (major RS rtrancl_induct2) 1);
   203 by (Fast_tac 1);
   203 by (Fast_tac 1);
   204 by (fast_tac (!claset addIs [FB_lemma3] addbefore split_all_tac) 1);
   204 by (fast_tac (claset() addIs [FB_lemma3] addbefore split_all_tac) 1);
   205 qed_spec_mp "FB_lemma2";
   205 qed_spec_mp "FB_lemma2";
   206 
   206 
   207 goal Transition.thy "!!c. (c,s) -*-> (SKIP,t) ==> <c,s> -c-> t";
   207 goal Transition.thy "!!c. (c,s) -*-> (SKIP,t) ==> <c,s> -c-> t";
   208 by (fast_tac (!claset addEs [FB_lemma2]) 1);
   208 by (fast_tac (claset() addEs [FB_lemma2]) 1);
   209 qed "evalc1_impl_evalc";
   209 qed "evalc1_impl_evalc";