src/HOL/UNITY/Token.ML
changeset 5069 3ea049f7979d
parent 4776 1f9362e769c1
child 5111 8f4b72f0c15d
equal deleted inserted replaced
5068:fb28eaa07e01 5069:3ea049f7979d
    14 
    14 
    15 val Token_defs = [WellTyped_def, Token_def, HasTok_def, H_def, E_def, T_def];
    15 val Token_defs = [WellTyped_def, Token_def, HasTok_def, H_def, E_def, T_def];
    16 
    16 
    17 AddIffs [N_positive, skip];
    17 AddIffs [N_positive, skip];
    18 
    18 
    19 goalw thy [HasTok_def] "!!i. [| s: HasTok i; s: HasTok j |] ==> i=j";
    19 Goalw [HasTok_def] "!!i. [| s: HasTok i; s: HasTok j |] ==> i=j";
    20 by Auto_tac;
    20 by Auto_tac;
    21 qed "HasToK_partition";
    21 qed "HasToK_partition";
    22 
    22 
    23 goalw thy Token_defs "!!s. s : WellTyped ==> (s ~: E i) = (s : H i | s : T i)";
    23 Goalw Token_defs "!!s. s : WellTyped ==> (s ~: E i) = (s : H i | s : T i)";
    24 by (Simp_tac 1);
    24 by (Simp_tac 1);
    25 by (exhaust_tac "s (Suc i)" 1);
    25 by (exhaust_tac "s (Suc i)" 1);
    26 by Auto_tac;
    26 by Auto_tac;
    27 qed "not_E_eq";
    27 qed "not_E_eq";
    28 
    28 
    30     the Invariant rule should let us assume that the initial
    30     the Invariant rule should let us assume that the initial
    31     state is reachable, and therefore contained in any Invariant.  Then
    31     state is reachable, and therefore contained in any Invariant.  Then
    32     we'd not have to mention WellTyped in the statement of this theorem.
    32     we'd not have to mention WellTyped in the statement of this theorem.
    33 **)
    33 **)
    34 
    34 
    35 goalw thy [stable_def]
    35 Goalw [stable_def]
    36     "stable Acts (WellTyped Int {s. s : E i --> s : HasTok i})";
    36     "stable Acts (WellTyped Int {s. s : E i --> s : HasTok i})";
    37 by (rtac (stable_WT RS stable_constrains_Int) 1);
    37 by (rtac (stable_WT RS stable_constrains_Int) 1);
    38 by (cut_facts_tac [TR2,TR4,TR5] 1);
    38 by (cut_facts_tac [TR2,TR4,TR5] 1);
    39 by (asm_full_simp_tac (simpset() addsimps [constrains_def]) 1);
    39 by (asm_full_simp_tac (simpset() addsimps [constrains_def]) 1);
    40 by (REPEAT_FIRST (rtac ballI ORELSE' (dtac bspec THEN' assume_tac)));
    40 by (REPEAT_FIRST (rtac ballI ORELSE' (dtac bspec THEN' assume_tac)));
    42 by (case_tac "xa : HasTok i" 1);
    42 by (case_tac "xa : HasTok i" 1);
    43 by (auto_tac (claset(), simpset() addsimps [H_def, E_def, T_def]));
    43 by (auto_tac (claset(), simpset() addsimps [H_def, E_def, T_def]));
    44 qed "token_stable";
    44 qed "token_stable";
    45 
    45 
    46 (*This proof is in the "massaging" style and is much faster! *)
    46 (*This proof is in the "massaging" style and is much faster! *)
    47 goalw thy [stable_def]
    47 Goalw [stable_def]
    48     "stable Acts (WellTyped Int (Compl(E i) Un (HasTok i)))";
    48     "stable Acts (WellTyped Int (Compl(E i) Un (HasTok i)))";
    49 by (rtac (stable_WT RS stable_constrains_Int) 1);
    49 by (rtac (stable_WT RS stable_constrains_Int) 1);
    50 by (rtac constrains_weaken 1);
    50 by (rtac constrains_weaken 1);
    51 by (rtac ([[TR2, TR4] MRS constrains_Un, TR5] MRS constrains_Un) 1);
    51 by (rtac ([[TR2, TR4] MRS constrains_Un, TR5] MRS constrains_Un) 1);
    52 by (auto_tac (claset(), simpset() addsimps [not_E_eq]));
    52 by (auto_tac (claset(), simpset() addsimps [not_E_eq]));
    54 qed "token_stable";
    54 qed "token_stable";
    55 
    55 
    56 
    56 
    57 (*** Progress under weak fairness ***)
    57 (*** Progress under weak fairness ***)
    58 
    58 
    59 goalw thy [nodeOrder_def] "wf(nodeOrder j)";
    59 Goalw [nodeOrder_def] "wf(nodeOrder j)";
    60 by (rtac (wf_less_than RS wf_inv_image RS wf_subset) 1);
    60 by (rtac (wf_less_than RS wf_inv_image RS wf_subset) 1);
    61 by (Blast_tac 1);
    61 by (Blast_tac 1);
    62 qed"wf_nodeOrder";
    62 qed"wf_nodeOrder";
    63 
    63 
    64     goal thy "!!m. [| m<n; Suc m ~= n |] ==> Suc(m) < n";
    64 Goal "!!m. [| m<n; Suc m ~= n |] ==> Suc(m) < n";
    65     by (full_simp_tac (simpset() addsimps [nat_neq_iff]) 1);
    65     by (full_simp_tac (simpset() addsimps [nat_neq_iff]) 1);
    66     by (blast_tac (claset() addEs [less_asym, less_SucE]) 1);
    66     by (blast_tac (claset() addEs [less_asym, less_SucE]) 1);
    67     qed "Suc_lessI";
    67     qed "Suc_lessI";
    68 
    68 
    69 goalw thy [nodeOrder_def, next_def, inv_image_def]
    69 Goalw [nodeOrder_def, next_def, inv_image_def]
    70     "!!x. [| i<N; j<N |] ==> ((next i, i) : nodeOrder j) = (i ~= j)";
    70     "!!x. [| i<N; j<N |] ==> ((next i, i) : nodeOrder j) = (i ~= j)";
    71 by (auto_tac (claset(),
    71 by (auto_tac (claset(),
    72 	      simpset() addsimps [Suc_lessI, mod_Suc, mod_less, mod_geq]));
    72 	      simpset() addsimps [Suc_lessI, mod_Suc, mod_less, mod_geq]));
    73 by (dtac sym 1);
    73 by (dtac sym 1);
    74 (*The next two lines...**)
    74 (*The next two lines...**)
    97 qed "nodeOrder_eq";
    97 qed "nodeOrder_eq";
    98 
    98 
    99 
    99 
   100 (*From "A Logic for Concurrent Programming", but not used in Chapter 4.
   100 (*From "A Logic for Concurrent Programming", but not used in Chapter 4.
   101   Note the use of case_tac.  Reasoning about leadsTo takes practice!*)
   101   Note the use of case_tac.  Reasoning about leadsTo takes practice!*)
   102 goal thy
   102 Goal
   103  "!!i. [| i<N; j<N |] ==> \
   103  "!!i. [| i<N; j<N |] ==> \
   104 \      leadsTo Acts (HasTok i) ({s. (Token s, i) : nodeOrder j} Un HasTok j)";
   104 \      leadsTo Acts (HasTok i) ({s. (Token s, i) : nodeOrder j} Un HasTok j)";
   105 by (case_tac "i=j" 1);
   105 by (case_tac "i=j" 1);
   106 by (blast_tac (claset() addIs [subset_imp_leadsTo]) 1);
   106 by (blast_tac (claset() addIs [subset_imp_leadsTo]) 1);
   107 by (rtac (TR7 RS leadsTo_weaken_R) 1);
   107 by (rtac (TR7 RS leadsTo_weaken_R) 1);
   109 by (asm_full_simp_tac (simpset() addsimps [HasTok_def, nodeOrder_eq]) 1);
   109 by (asm_full_simp_tac (simpset() addsimps [HasTok_def, nodeOrder_eq]) 1);
   110 qed "TR7_nodeOrder";
   110 qed "TR7_nodeOrder";
   111 
   111 
   112 
   112 
   113 (*Chapter 4 variant, the one actually used below.*)
   113 (*Chapter 4 variant, the one actually used below.*)
   114 goal thy
   114 Goal
   115  "!!i. [| i<N; j<N; i~=j |] ==> \
   115  "!!i. [| i<N; j<N; i~=j |] ==> \
   116 \      leadsTo Acts (HasTok i) {s. (Token s, i) : nodeOrder j}";
   116 \      leadsTo Acts (HasTok i) {s. (Token s, i) : nodeOrder j}";
   117 by (rtac (TR7 RS leadsTo_weaken_R) 1);
   117 by (rtac (TR7 RS leadsTo_weaken_R) 1);
   118 by (Clarify_tac 1);
   118 by (Clarify_tac 1);
   119 by (asm_full_simp_tac (simpset() addsimps [HasTok_def, nodeOrder_eq]) 1);
   119 by (asm_full_simp_tac (simpset() addsimps [HasTok_def, nodeOrder_eq]) 1);
   120 qed "TR7_aux";
   120 qed "TR7_aux";
   121 
   121 
   122 goal thy "({s. Token s < N} Int Token -`` {m}) = \
   122 Goal "({s. Token s < N} Int Token -`` {m}) = \
   123 \         (if m<N then Token -`` {m} else {})";
   123 \         (if m<N then Token -`` {m} else {})";
   124 by Auto_tac;
   124 by Auto_tac;
   125 val Token_lemma = result();
   125 val Token_lemma = result();
   126 
   126 
   127 
   127 
   128 (*Misra's TR9: the token reaches an arbitrary node*)
   128 (*Misra's TR9: the token reaches an arbitrary node*)
   129 goal thy
   129 Goal
   130  "!!i. j<N ==> leadsTo Acts {s. Token s < N} (HasTok j)";
   130  "!!i. j<N ==> leadsTo Acts {s. Token s < N} (HasTok j)";
   131 by (rtac leadsTo_weaken_R 1);
   131 by (rtac leadsTo_weaken_R 1);
   132 by (res_inst_tac [("I", "Compl{j}"), ("f", "Token"), ("B", "{}")]
   132 by (res_inst_tac [("I", "Compl{j}"), ("f", "Token"), ("B", "{}")]
   133      (wf_nodeOrder RS bounded_induct) 1);
   133      (wf_nodeOrder RS bounded_induct) 1);
   134 by (ALLGOALS (asm_simp_tac (simpset() addsimps [Token_lemma, vimage_Diff,
   134 by (ALLGOALS (asm_simp_tac (simpset() addsimps [Token_lemma, vimage_Diff,
   139 by (ALLGOALS (asm_simp_tac (simpset() addsimps [nodeOrder_def, HasTok_def])));
   139 by (ALLGOALS (asm_simp_tac (simpset() addsimps [nodeOrder_def, HasTok_def])));
   140 by (ALLGOALS Blast_tac);
   140 by (ALLGOALS Blast_tac);
   141 qed "leadsTo_j";
   141 qed "leadsTo_j";
   142 
   142 
   143 (*Misra's TR8: a hungry process eventually eats*)
   143 (*Misra's TR8: a hungry process eventually eats*)
   144 goal thy "!!i. j<N ==> leadsTo Acts ({s. Token s < N} Int H j) (E j)";
   144 Goal "!!i. j<N ==> leadsTo Acts ({s. Token s < N} Int H j) (E j)";
   145 by (rtac (leadsTo_cancel1 RS leadsTo_Un_duplicate) 1);
   145 by (rtac (leadsTo_cancel1 RS leadsTo_Un_duplicate) 1);
   146 by (rtac TR6 2);
   146 by (rtac TR6 2);
   147 by (rtac leadsTo_weaken_R 1);
   147 by (rtac leadsTo_weaken_R 1);
   148 by (rtac ([leadsTo_j, TR3] MRS PSP) 1);
   148 by (rtac ([leadsTo_j, TR3] MRS PSP) 1);
   149 by (ALLGOALS Blast_tac);
   149 by (ALLGOALS Blast_tac);