theory Atomicity_Lib

lemma shuttle_gets_interferences[simplified K_bind_def]:
  "equivp sr \<Longrightarrow> \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t
    \<Longrightarrow> (\<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t)
    \<Longrightarrow> \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t
    \<Longrightarrow> rel_tr_refinement sr P R C
        (do interferences; x \<leftarrow> gets f; g x od) (do x \<leftarrow> gets f; interferences; g x od)" apply (rule rel_tr_refinement_trans) apply (metis equivpE) apply (simp only: bind_assoc[symmetric] K_bind_def) apply (rule rel_tr_refinement_bind_left_general) apply (metis equivpE) apply simp apply (rule rel_tr_refinement_comm_repeat, assumption) apply (rule shuttle_gets_interference; simp) apply simp apply wpsimp apply (simp add: bind_assoc) apply (rule rel_tr_refinement_refl) apply (metis equivpE) done

(* Proof state trace *)
proof (prove)
goal (1 subgoal):
 1. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (do interferences;
gets f >>= g
od) (do x <- gets f;
interferences;
g x
od) proof (prove)
goal (3 subgoals):
 1. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> transp sr
 2. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (do interferences;
gets f >>= g
od) ?g
 3. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C ?g (do x <- gets f;
interferences;
g x
od) proof (prove)
goal (2 subgoals):
 1. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (do interferences;
gets f >>= g
od) ?g
 2. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C ?g (do x <- gets f;
interferences;
g x
od) proof (prove)
goal (2 subgoals):
 1. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (do y <- interferences;
gets f
od >>= g) ?g
 2. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C ?g (do x <- gets f;
interferences;
g x
od) proof (prove)
goal (4 subgoals):
 1. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> reflp sr
 2. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> (\<forall>x. not_env_steps_first (g x)) \<or> (\<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t)
 3. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (do y <- interferences;
gets f
od) ?g8
 4. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (?g8 >>= g) (do x <- gets f;
interferences;
g x
od) proof (prove)
goal (3 subgoals):
 1. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> (\<forall>x. not_env_steps_first (g x)) \<or> (\<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t)
 2. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (do y <- interferences;
gets f
od) ?g8
 3. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (?g8 >>= g) (do x <- gets f;
interferences;
g x
od) proof (prove)
goal (2 subgoals):
 1. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (do y <- interferences;
gets f
od) ?g8
 2. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (?g8 >>= g) (do x <- gets f;
interferences;
g x
od) proof (prove)
goal (4 subgoals):
 1. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (do y <- interference;
gets f
od) (do x <- gets f;
y <- interference;
return x
od)
 2. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> not_env_steps_first interference \<or> (\<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t)
 3. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> \<lbrace>\<lambda>s0 s. (C \<longrightarrow> s0 = s) \<and> P s\<rbrace>, \<lbrace>R\<rbrace> interference -, \<lbrace>\<lambda>_ s0 s. (C \<longrightarrow> s0 = s) \<and> P s\<rbrace>
 4. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (do x <- gets f;
y <- interferences;
return x
od >>= g) (do x <- gets f;
interferences;
g x
od) proof (prove)
goal (3 subgoals):
 1. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> not_env_steps_first interference \<or> (\<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t)
 2. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> \<lbrace>\<lambda>s0 s. (C \<longrightarrow> s0 = s) \<and> P s\<rbrace>, \<lbrace>R\<rbrace> interference -, \<lbrace>\<lambda>_ s0 s. (C \<longrightarrow> s0 = s) \<and> P s\<rbrace>
 3. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (do x <- gets f;
y <- interferences;
return x
od >>= g) (do x <- gets f;
interferences;
g x
od) proof (prove)
goal (2 subgoals):
 1. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> \<lbrace>\<lambda>s0 s. (C \<longrightarrow> s0 = s) \<and> P s\<rbrace>, \<lbrace>R\<rbrace> interference -, \<lbrace>\<lambda>_ s0 s. (C \<longrightarrow> s0 = s) \<and> P s\<rbrace>
 2. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (do x <- gets f;
y <- interferences;
return x
od >>= g) (do x <- gets f;
interferences;
g x
od) proof (prove)
goal (1 subgoal):
 1. \<lbrakk>equivp sr; \<forall>s t. P s \<longrightarrow> R s t \<longrightarrow> f s = f t; \<forall>s s' t. sr s s' \<longrightarrow> R s t = R s' t; \<forall>s t. P s \<longrightarrow> R\<^sup>*\<^sup>* s t \<longrightarrow> P t\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (do x <- gets f;
y <- interferences;
return x
od >>= g) (do x <- gets f;
interferences;
g x
od) proof (prove)
goal (1 subgoal):
 1. \<lbrakk>equivp sr; \<forall>s. P s \<longrightarrow> (\<forall>t. R s t \<longrightarrow> f s = f t); \<forall>s s'. sr s s' \<longrightarrow> (\<forall>t. R s t = R s' t); \<forall>s. P s \<longrightarrow> (\<forall>t. R\<^sup>*\<^sup>* s t \<longrightarrow> P t)\<rbrakk> \<Longrightarrow> rel_tr_refinement sr P R C (do x <- gets f;
y <- interferences;
g x
od) (do x <- gets f;
y <- interferences;
g x
od) proof (prove)
goal (1 subgoal):
 1. \<lbrakk>equivp sr; \<forall>s. P s \<longrightarrow> (\<forall>t. R s t \<longrightarrow> f s = f t); \<forall>s s'. sr s s' \<longrightarrow> (\<forall>t. R s t = R s' t); \<forall>s. P s \<longrightarrow> (\<forall>t. R\<^sup>*\<^sup>* s t \<longrightarrow> P t)\<rbrakk> \<Longrightarrow> reflp sr proof (prove)
goal:
No subgoals!