author | wenzelm |
Sun, 02 Nov 2014 18:21:45 +0100 | |
changeset 58889 | 5b7a9633cfa8 |
parent 51717 | 9e7d1c139569 |
child 60587 | 0318b43ee95c |
permissions | -rw-r--r-- |
41589 | 1 |
(* Title: HOL/TLA/Buffer/DBuffer.thy |
2 |
Author: Stephan Merz, University of Munich |
|
3807 | 3 |
*) |
4 |
||
58889 | 5 |
section {* Two FIFO buffers in a row, with interleaving assumption *} |
17309 | 6 |
|
7 |
theory DBuffer |
|
8 |
imports Buffer |
|
9 |
begin |
|
3807 | 10 |
|
47968 | 11 |
axiomatization |
3807 | 12 |
(* implementation variables *) |
47968 | 13 |
inp :: "nat stfun" and |
14 |
mid :: "nat stfun" and |
|
15 |
out :: "nat stfun" and |
|
16 |
q1 :: "nat list stfun" and |
|
17 |
q2 :: "nat list stfun" and |
|
18 |
qc :: "nat list stfun" and |
|
3807 | 19 |
|
47968 | 20 |
DBInit :: stpred and |
21 |
DBEnq :: action and |
|
22 |
DBDeq :: action and |
|
23 |
DBPass :: action and |
|
24 |
DBNext :: action and |
|
17309 | 25 |
DBuffer :: temporal |
47968 | 26 |
where |
27 |
DB_base: "basevars (inp,mid,out,q1,q2)" and |
|
3807 | 28 |
|
29 |
(* the concatenation of the two buffers *) |
|
47968 | 30 |
qc_def: "PRED qc == PRED (q2 @ q1)" and |
3807 | 31 |
|
47968 | 32 |
DBInit_def: "DBInit == PRED (BInit inp q1 mid & BInit mid q2 out)" and |
33 |
DBEnq_def: "DBEnq == ACT Enq inp q1 mid & unchanged (q2,out)" and |
|
34 |
DBDeq_def: "DBDeq == ACT Deq mid q2 out & unchanged (inp,q1)" and |
|
17309 | 35 |
DBPass_def: "DBPass == ACT Deq inp q1 mid |
6255 | 36 |
& (q2$ = $q2 @ [ mid$ ]) |
47968 | 37 |
& (out$ = $out)" and |
38 |
DBNext_def: "DBNext == ACT (DBEnq | DBDeq | DBPass)" and |
|
17309 | 39 |
DBuffer_def: "DBuffer == TEMP Init DBInit |
6255 | 40 |
& [][DBNext]_(inp,mid,out,q1,q2) |
41 |
& WF(DBDeq)_(inp,mid,out,q1,q2) |
|
42 |
& WF(DBPass)_(inp,mid,out,q1,q2)" |
|
3807 | 43 |
|
21624 | 44 |
|
45 |
declare qc_def [simp] |
|
46 |
||
47 |
lemmas db_defs = |
|
48 |
BInit_def Enq_def Deq_def Next_def IBuffer_def Buffer_def |
|
49 |
DBInit_def DBEnq_def DBDeq_def DBPass_def DBNext_def DBuffer_def |
|
50 |
||
51 |
||
52 |
(*** Proper initialization ***) |
|
53 |
lemma DBInit: "|- Init DBInit --> Init (BInit inp qc out)" |
|
54 |
by (auto simp: Init_def DBInit_def BInit_def) |
|
55 |
||
56 |
||
57 |
(*** Step simulation ***) |
|
58 |
lemma DB_step_simulation: "|- [DBNext]_(inp,mid,out,q1,q2) --> [Next inp qc out]_(inp,qc,out)" |
|
59 |
apply (rule square_simulation) |
|
60 |
apply clarsimp |
|
61 |
apply (tactic |
|
51717
9e7d1c139569
simplifier uses proper Proof.context instead of historic type simpset;
wenzelm
parents:
47968
diff
changeset
|
62 |
{* action_simp_tac (@{context} addsimps (@{thm hd_append} :: @{thms db_defs})) [] [] 1 *}) |
21624 | 63 |
done |
64 |
||
65 |
||
66 |
(*** Simulation of fairness ***) |
|
67 |
||
68 |
(* Compute enabledness predicates for DBDeq and DBPass actions *) |
|
69 |
lemma DBDeq_visible: "|- <DBDeq>_(inp,mid,out,q1,q2) = DBDeq" |
|
70 |
apply (unfold angle_def DBDeq_def Deq_def) |
|
71 |
apply (safe, simp (asm_lr))+ |
|
72 |
done |
|
73 |
||
74 |
lemma DBDeq_enabled: |
|
75 |
"|- Enabled (<DBDeq>_(inp,mid,out,q1,q2)) = (q2 ~= #[])" |
|
76 |
apply (unfold DBDeq_visible [action_rewrite]) |
|
77 |
apply (force intro!: DB_base [THEN base_enabled, temp_use] |
|
78 |
elim!: enabledE simp: angle_def DBDeq_def Deq_def) |
|
79 |
done |
|
80 |
||
81 |
lemma DBPass_visible: "|- <DBPass>_(inp,mid,out,q1,q2) = DBPass" |
|
82 |
by (auto simp: angle_def DBPass_def Deq_def) |
|
83 |
||
84 |
lemma DBPass_enabled: |
|
85 |
"|- Enabled (<DBPass>_(inp,mid,out,q1,q2)) = (q1 ~= #[])" |
|
86 |
apply (unfold DBPass_visible [action_rewrite]) |
|
87 |
apply (force intro!: DB_base [THEN base_enabled, temp_use] |
|
88 |
elim!: enabledE simp: angle_def DBPass_def Deq_def) |
|
89 |
done |
|
90 |
||
91 |
||
92 |
(* The plan for proving weak fairness at the higher level is to prove |
|
93 |
(0) DBuffer => (Enabled (Deq inp qc out) ~> (Deq inp qc out)) |
|
94 |
which is in turn reduced to the two leadsto conditions |
|
95 |
(1) DBuffer => (Enabled (Deq inp qc out) ~> q2 ~= []) |
|
96 |
(2) DBuffer => (q2 ~= [] ~> DBDeq) |
|
97 |
and the fact that DBDeq implies <Deq inp qc out>_(inp,qc,out) |
|
98 |
(and therefore DBDeq ~> <Deq inp qc out>_(inp,qc,out) trivially holds). |
|
17309 | 99 |
|
21624 | 100 |
Condition (1) is reduced to |
101 |
(1a) DBuffer => (qc ~= [] /\ q2 = [] ~> q2 ~= []) |
|
102 |
by standard leadsto rules (leadsto_classical) and rule Deq_enabledE. |
|
103 |
||
104 |
Both (1a) and (2) are proved from DBuffer's WF conditions by standard |
|
105 |
WF reasoning (Lamport's WF1 and WF_leadsto). |
|
106 |
The condition WF(Deq inp qc out) follows from (0) by rule leadsto_WF. |
|
107 |
||
108 |
One could use Lamport's WF2 instead. |
|
109 |
*) |
|
110 |
||
111 |
(* Condition (1a) *) |
|
112 |
lemma DBFair_1a: "|- [][DBNext]_(inp,mid,out,q1,q2) & WF(DBPass)_(inp,mid,out,q1,q2) |
|
113 |
--> (qc ~= #[] & q2 = #[] ~> q2 ~= #[])" |
|
114 |
apply (rule WF1) |
|
115 |
apply (force simp: db_defs) |
|
116 |
apply (force simp: angle_def DBPass_def) |
|
117 |
apply (force simp: DBPass_enabled [temp_use]) |
|
118 |
done |
|
119 |
||
120 |
(* Condition (1) *) |
|
121 |
lemma DBFair_1: "|- [][DBNext]_(inp,mid,out,q1,q2) & WF(DBPass)_(inp,mid,out,q1,q2) |
|
122 |
--> (Enabled (<Deq inp qc out>_(inp,qc,out)) ~> q2 ~= #[])" |
|
123 |
apply clarsimp |
|
124 |
apply (rule leadsto_classical [temp_use]) |
|
125 |
apply (rule DBFair_1a [temp_use, THEN LatticeTransitivity [temp_use]]) |
|
126 |
apply assumption+ |
|
127 |
apply (rule ImplLeadsto_gen [temp_use]) |
|
128 |
apply (force intro!: necT [temp_use] dest!: STL2_gen [temp_use] Deq_enabledE [temp_use] |
|
129 |
simp add: Init_defs) |
|
130 |
done |
|
131 |
||
132 |
(* Condition (2) *) |
|
133 |
lemma DBFair_2: "|- [][DBNext]_(inp,mid,out,q1,q2) & WF(DBDeq)_(inp,mid,out,q1,q2) |
|
134 |
--> (q2 ~= #[] ~> DBDeq)" |
|
135 |
apply (rule WF_leadsto) |
|
136 |
apply (force simp: DBDeq_enabled [temp_use]) |
|
137 |
apply (force simp: angle_def) |
|
138 |
apply (force simp: db_defs elim!: Stable [temp_use]) |
|
139 |
done |
|
140 |
||
141 |
(* High-level fairness *) |
|
142 |
lemma DBFair: "|- [][DBNext]_(inp,mid,out,q1,q2) & WF(DBPass)_(inp,mid,out,q1,q2) |
|
143 |
& WF(DBDeq)_(inp,mid,out,q1,q2) |
|
144 |
--> WF(Deq inp qc out)_(inp,qc,out)" |
|
145 |
apply (auto simp del: qc_def intro!: leadsto_WF [temp_use] |
|
146 |
DBFair_1 [temp_use, THEN [2] LatticeTransitivity [temp_use]] |
|
147 |
DBFair_2 [temp_use, THEN [2] LatticeTransitivity [temp_use]]) |
|
148 |
apply (auto intro!: ImplLeadsto_simple [temp_use] |
|
149 |
simp: angle_def DBDeq_def Deq_def hd_append [try_rewrite]) |
|
150 |
done |
|
151 |
||
152 |
(*** Main theorem ***) |
|
153 |
lemma DBuffer_impl_Buffer: "|- DBuffer --> Buffer inp out" |
|
154 |
apply (unfold DBuffer_def Buffer_def IBuffer_def) |
|
155 |
apply (force intro!: eexI [temp_use] DBInit [temp_use] |
|
156 |
DB_step_simulation [THEN STL4, temp_use] DBFair [temp_use]) |
|
157 |
done |
|
158 |
||
159 |
end |