107 |
107 |
108 text {* |
108 text {* |
109 In order to model the general tree structure of a Unix file-system |
109 In order to model the general tree structure of a Unix file-system |
110 we use the arbitrarily branching datatype @{typ "('a, 'b, 'c) env"} |
110 we use the arbitrarily branching datatype @{typ "('a, 'b, 'c) env"} |
111 from the standard library of Isabelle/HOL |
111 from the standard library of Isabelle/HOL |
112 \cite{Bauer-et-al:2001:HOL-Library}. This type provides |
112 \cite{Bauer-et-al:2002:HOL-Library}. This type provides |
113 constructors @{term Val} and @{term Env} as follows: |
113 constructors @{term Val} and @{term Env} as follows: |
114 |
114 |
115 \medskip |
115 \medskip |
116 {\def\isastyleminor{\isastyle} |
116 {\def\isastyleminor{\isastyle} |
117 \begin{tabular}{l} |
117 \begin{tabular}{l} |
147 |
147 |
148 @{thm [display, indent = 2, eta_contract = false] lookup_eq [no_vars]} |
148 @{thm [display, indent = 2, eta_contract = false] lookup_eq [no_vars]} |
149 @{thm [display, indent = 2, eta_contract = false] update_eq [no_vars]} |
149 @{thm [display, indent = 2, eta_contract = false] update_eq [no_vars]} |
150 |
150 |
151 Several further properties of these operations are proven in |
151 Several further properties of these operations are proven in |
152 \cite{Bauer-et-al:2001:HOL-Library}. These will be routinely used |
152 \cite{Bauer-et-al:2002:HOL-Library}. These will be routinely used |
153 later on without further notice. |
153 later on without further notice. |
154 |
154 |
155 \bigskip Apparently, the elements of type @{typ file} contain an |
155 \bigskip Apparently, the elements of type @{typ file} contain an |
156 @{typ att} component in either case. We now define a few auxiliary |
156 @{typ att} component in either case. We now define a few auxiliary |
157 operations to manipulate this field uniformly, following the |
157 operations to manipulate this field uniformly, following the |
332 text {* |
332 text {* |
333 \medskip Note that we have omitted explicit @{text Open} and @{text |
333 \medskip Note that we have omitted explicit @{text Open} and @{text |
334 Close} operations, pretending that @{term Read} and @{term Write} |
334 Close} operations, pretending that @{term Read} and @{term Write} |
335 would already take care of this behind the scenes. Thus we have |
335 would already take care of this behind the scenes. Thus we have |
336 basically treated actual sequences of real system-calls @{text |
336 basically treated actual sequences of real system-calls @{text |
337 open}--@{text read}/@{text write}--@{text close} as atomic. |
337 "open"}--@{text read}/@{text write}--@{text close} as atomic. |
338 |
338 |
339 In principle, this could make big a difference in a model with |
339 In principle, this could make big a difference in a model with |
340 explicit concurrent processes. On the other hand, even on a real |
340 explicit concurrent processes. On the other hand, even on a real |
341 Unix system the exact scheduling of concurrent @{text open} and |
341 Unix system the exact scheduling of concurrent @{text "open"} and |
342 @{text close} operations does \emph{not} directly affect the success |
342 @{text close} operations does \emph{not} directly affect the success |
343 of corresponding @{text read} or @{text write}. Unix allows several |
343 of corresponding @{text read} or @{text write}. Unix allows several |
344 processes to have files opened at the same time, even for writing! |
344 processes to have files opened at the same time, even for writing! |
345 Certainly, the result from reading the contents later may be hard to |
345 Certainly, the result from reading the contents later may be hard to |
346 predict, but the system-calls involved here will succeed in any |
346 predict, but the system-calls involved here will succeed in any |
1116 The main result is now imminent, just by composing the three |
1116 The main result is now imminent, just by composing the three |
1117 invariance lemmas (see \secref{sec:unix-inv-lemmas}) according the the |
1117 invariance lemmas (see \secref{sec:unix-inv-lemmas}) according the the |
1118 overall procedure (see \secref{sec:unix-inv-procedure}). |
1118 overall procedure (see \secref{sec:unix-inv-procedure}). |
1119 *} |
1119 *} |
1120 |
1120 |
1121 corollary (in invariant) (* FIXME in situation!? *) |
1121 corollary result: |
1122 "init users =bogus\<Rightarrow> root \<Longrightarrow> |
1122 includes invariant |
1123 \<not> (\<exists>xs. (\<forall>x \<in> set xs. uid_of x = user1) \<and> |
1123 assumes bogus: "init users =bogus\<Rightarrow> root" |
1124 can_exec root (xs @ [Rmdir user1 [user1, name1]]))" |
1124 shows "\<not> (\<exists>xs. (\<forall>x \<in> set xs. uid_of x = user1) \<and> |
|
1125 can_exec root (xs @ [Rmdir user1 [user1, name1]]))" |
1125 proof - |
1126 proof - |
1126 case rule_context |
1127 from cannot_rmdir init_invariant preserve_invariant |
1127 with cannot_rmdir init_invariant preserve_invariant |
1128 and bogus show ?thesis by (rule general_procedure) |
1128 show ?thesis by (rule general_procedure) |
1129 qed |
1129 qed |
1130 |
|
1131 text {* |
|
1132 So this is our final result: |
|
1133 |
|
1134 @{thm [display] result [OF situation_axioms.intro, no_vars]} |
|
1135 *} |
1130 |
1136 |
1131 end |
1137 end |