src/HOL/UNITY/Token.ML
changeset 5648 fe887910e32e
parent 5625 77e9ab9cd7b1
child 5782 7559f116cb10
equal deleted inserted replaced
5647:4e8837255b87 5648:fe887910e32e
    30 val TR6   = forall_elim_vars 0 (thm "TR6");
    30 val TR6   = forall_elim_vars 0 (thm "TR6");
    31 val TR7   = forall_elim_vars 0 (thm "TR7");
    31 val TR7   = forall_elim_vars 0 (thm "TR7");
    32 val nodeOrder_def   = (thm "nodeOrder_def");
    32 val nodeOrder_def   = (thm "nodeOrder_def");
    33 val next_def   = (thm "next_def");
    33 val next_def   = (thm "next_def");
    34 
    34 
    35 AddIffs [thm "N_positive", thm"skip"];
    35 AddIffs [thm "N_positive"];
    36 
    36 
    37 Goalw [stable_def] "stable acts (-(E i) Un (HasTok i))";
    37 Goalw [stable_def] "F : stable (-(E i) Un (HasTok i))";
    38 by (rtac constrains_weaken 1);
    38 by (rtac constrains_weaken 1);
    39 by (rtac ([[TR2, TR4] MRS constrains_Un, TR5] MRS constrains_Un) 1);
    39 by (rtac ([[TR2, TR4] MRS constrains_Un, TR5] MRS constrains_Un) 1);
    40 by (auto_tac (claset(), simpset() addsimps [not_E_eq]));
    40 by (auto_tac (claset(), simpset() addsimps [not_E_eq]));
    41 by (ALLGOALS (asm_full_simp_tac (simpset() addsimps [H_def, E_def, T_def])));
    41 by (ALLGOALS (asm_full_simp_tac (simpset() addsimps [H_def, E_def, T_def])));
    42 qed "token_stable";
    42 qed "token_stable";
    68 
    68 
    69 
    69 
    70 (*From "A Logic for Concurrent Programming", but not used in Chapter 4.
    70 (*From "A Logic for Concurrent Programming", but not used in Chapter 4.
    71   Note the use of case_tac.  Reasoning about leadsTo takes practice!*)
    71   Note the use of case_tac.  Reasoning about leadsTo takes practice!*)
    72 Goal "[| i<N; j<N |] ==>   \
    72 Goal "[| i<N; j<N |] ==>   \
    73 \     leadsTo acts (HasTok i) ({s. (token s, i) : nodeOrder j} Un HasTok j)";
    73 \     F : leadsTo (HasTok i) ({s. (token s, i) : nodeOrder j} Un HasTok j)";
    74 by (case_tac "i=j" 1);
    74 by (case_tac "i=j" 1);
    75 by (blast_tac (claset() addIs [subset_imp_leadsTo]) 1);
    75 by (blast_tac (claset() addIs [subset_imp_leadsTo]) 1);
    76 by (rtac (TR7 RS leadsTo_weaken_R) 1);
    76 by (rtac (TR7 RS leadsTo_weaken_R) 1);
    77 by (Clarify_tac 1);
    77 by (Clarify_tac 1);
    78 by (asm_full_simp_tac (simpset() addsimps [HasTok_def, nodeOrder_eq]) 1);
    78 by (asm_full_simp_tac (simpset() addsimps [HasTok_def, nodeOrder_eq]) 1);
    79 qed "TR7_nodeOrder";
    79 qed "TR7_nodeOrder";
    80 
    80 
    81 
    81 
    82 (*Chapter 4 variant, the one actually used below.*)
    82 (*Chapter 4 variant, the one actually used below.*)
    83 Goal "[| i<N; j<N; i~=j |]    \
    83 Goal "[| i<N; j<N; i~=j |]    \
    84 \     ==> leadsTo acts (HasTok i) {s. (token s, i) : nodeOrder j}";
    84 \     ==> F : leadsTo (HasTok i) {s. (token s, i) : nodeOrder j}";
    85 by (rtac (TR7 RS leadsTo_weaken_R) 1);
    85 by (rtac (TR7 RS leadsTo_weaken_R) 1);
    86 by (Clarify_tac 1);
    86 by (Clarify_tac 1);
    87 by (asm_full_simp_tac (simpset() addsimps [HasTok_def, nodeOrder_eq]) 1);
    87 by (asm_full_simp_tac (simpset() addsimps [HasTok_def, nodeOrder_eq]) 1);
    88 qed "TR7_aux";
    88 qed "TR7_aux";
    89 
    89 
    92 by Auto_tac;
    92 by Auto_tac;
    93 val token_lemma = result();
    93 val token_lemma = result();
    94 
    94 
    95 
    95 
    96 (*Misra's TR9: the token reaches an arbitrary node*)
    96 (*Misra's TR9: the token reaches an arbitrary node*)
    97 Goal "j<N ==> leadsTo acts {s. token s < N} (HasTok j)";
    97 Goal "j<N ==> F : leadsTo {s. token s < N} (HasTok j)";
    98 by (rtac leadsTo_weaken_R 1);
    98 by (rtac leadsTo_weaken_R 1);
    99 by (res_inst_tac [("I", "-{j}"), ("f", "token"), ("B", "{}")]
    99 by (res_inst_tac [("I", "-{j}"), ("f", "token"), ("B", "{}")]
   100      (wf_nodeOrder RS bounded_induct) 1);
   100      (wf_nodeOrder RS bounded_induct) 1);
   101 by (ALLGOALS (asm_simp_tac (simpset() addsimps [token_lemma, vimage_Diff,
   101 by (ALLGOALS (asm_simp_tac (simpset() addsimps [token_lemma, vimage_Diff,
   102 						HasTok_def])));
   102 						HasTok_def])));
   106 by (ALLGOALS (asm_simp_tac (simpset() addsimps [nodeOrder_def, HasTok_def])));
   106 by (ALLGOALS (asm_simp_tac (simpset() addsimps [nodeOrder_def, HasTok_def])));
   107 by (ALLGOALS Blast_tac);
   107 by (ALLGOALS Blast_tac);
   108 qed "leadsTo_j";
   108 qed "leadsTo_j";
   109 
   109 
   110 (*Misra's TR8: a hungry process eventually eats*)
   110 (*Misra's TR8: a hungry process eventually eats*)
   111 Goal "j<N ==> leadsTo acts ({s. token s < N} Int H j) (E j)";
   111 Goal "j<N ==> F : leadsTo ({s. token s < N} Int H j) (E j)";
   112 by (rtac (leadsTo_cancel1 RS leadsTo_Un_duplicate) 1);
   112 by (rtac (leadsTo_cancel1 RS leadsTo_Un_duplicate) 1);
   113 by (rtac TR6 2);
   113 by (rtac TR6 2);
   114 by (rtac leadsTo_weaken_R 1);
   114 by (rtac leadsTo_weaken_R 1);
   115 by (rtac ([leadsTo_j, TR3] MRS psp) 1);
   115 by (rtac ([leadsTo_j, TR3] MRS psp) 1);
   116 by (ALLGOALS Blast_tac);
   116 by (ALLGOALS Blast_tac);