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); |