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