src/HOL/IMP/Live.thy
changeset 28867 3d9873c4c409
parent 28583 9bb9791bdc18
child 32960 69916a850301
     1.1 --- a/src/HOL/IMP/Live.thy	Thu Nov 20 19:43:34 2008 +0100
     1.2 +++ b/src/HOL/IMP/Live.thy	Thu Nov 20 22:39:12 2008 +0100
     1.3 @@ -92,17 +92,80 @@
     1.4        have "b t" using WhileTrue by (simp add: ball_Un)(blast dest:dep_on)
     1.5        then obtain t'' where "\<langle>c,t\<rangle> \<longrightarrow>\<^sub>c t''" and "\<langle>While b c,t''\<rangle> \<longrightarrow>\<^sub>c t'"
     1.6          using WhileTrue(6,7) by auto
     1.7 -      note IH1 = IH(1)[OF _ `\<langle>c,s\<rangle> \<longrightarrow>\<^sub>c s''` `\<langle>c,t\<rangle> \<longrightarrow>\<^sub>c t''`]
     1.8 -      have L1: "\<forall>x\<in>A. s'' x = t'' x" using IH1 WhileTrue(6,8)
     1.9 -	by(simp  add: ball_Un) (metis)
    1.10 -      have L2: "\<forall>x\<in>Dep b. s'' x = t'' x"
    1.11 -	using IH1 WhileTrue(6,8) by (auto simp:L_gen_kill)
    1.12 -      have L3: "\<forall>x\<in>L c A. s'' x = t'' x"
    1.13 -	using IH1 L_idemp[of c A] WhileTrue(6,8) by auto
    1.14 -      have "\<forall>x\<in>L (While b c) A. s'' x = t'' x" using L1 L2 L3 by auto
    1.15 -      then show ?case using WhileTrue(5,6) `\<langle>While b c,t''\<rangle> \<longrightarrow>\<^sub>c t'` by metis
    1.16 +      have "\<forall>x\<in>Dep b \<union> A \<union> L c A. s'' x = t'' x"
    1.17 +	using IH(1)[OF _ `\<langle>c,s\<rangle> \<longrightarrow>\<^sub>c s''` `\<langle>c,t\<rangle> \<longrightarrow>\<^sub>c t''`] WhileTrue(6,8)
    1.18 +	by (auto simp:L_gen_kill)
    1.19 +      moreover then have "\<forall>x\<in>L (While b c) A. s'' x = t'' x" by auto
    1.20 +      ultimately show ?case using WhileTrue(5,6) `\<langle>While b c,t''\<rangle> \<longrightarrow>\<^sub>c t'` by metis
    1.21      qed auto }
    1.22    from this[OF IH(3) _ IH(4,2)] show ?case by metis
    1.23  qed
    1.24  
    1.25 +
    1.26 +primrec bury :: "com \<Rightarrow> loc set \<Rightarrow> com" where
    1.27 +"bury SKIP _ = SKIP" |
    1.28 +"bury (x :== e) A = (if x:A then x:== e else SKIP)" |
    1.29 +"bury (c1; c2) A = (bury c1 (L c2 A); bury c2 A)" |
    1.30 +"bury (IF b THEN c1 ELSE c2) A = (IF b THEN bury c1 A ELSE bury c2 A)" |
    1.31 +"bury (WHILE b DO c) A = (WHILE b DO bury c (Dep b \<union> A \<union> L c A))"
    1.32 +
    1.33 +theorem bury_sound:
    1.34 +  "\<forall> x \<in> L c A. s x = t x \<Longrightarrow> \<langle>c,s\<rangle> \<longrightarrow>\<^sub>c s' \<Longrightarrow> \<langle>bury c A,t\<rangle> \<longrightarrow>\<^sub>c t' \<Longrightarrow>
    1.35 +   \<forall>x\<in>A. s' x = t' x"
    1.36 +proof (induct c arbitrary: A s t s' t')
    1.37 +  case SKIP then show ?case by auto
    1.38 +next
    1.39 +  case (Assign x e) then show ?case
    1.40 +    by (auto simp:update_def ball_Un split:split_if_asm dest!: dep_on)
    1.41 +next
    1.42 +  case (Semi c1 c2)
    1.43 +  from Semi(4) obtain s'' where s1: "\<langle>c1,s\<rangle> \<longrightarrow>\<^sub>c s''" and s2: "\<langle>c2,s''\<rangle> \<longrightarrow>\<^sub>c s'"
    1.44 +    by auto
    1.45 +  from Semi(5) obtain t'' where t1: "\<langle>bury c1 (L c2 A),t\<rangle> \<longrightarrow>\<^sub>c t''" and t2: "\<langle>bury c2 A,t''\<rangle> \<longrightarrow>\<^sub>c t'"
    1.46 +    by auto
    1.47 +  show ?case using Semi(1)[OF _ s1 t1] Semi(2)[OF _ s2 t2] Semi(3) by fastsimp
    1.48 +next
    1.49 +  case (Cond b c1 c2)
    1.50 +  show ?case
    1.51 +  proof cases
    1.52 +    assume "b s"
    1.53 +    hence s: "\<langle>c1,s\<rangle> \<longrightarrow>\<^sub>c s'" using Cond(4) by simp
    1.54 +    have "b t" using `b s` Cond(3) by (simp add: ball_Un)(blast dest: dep_on)
    1.55 +    hence t: "\<langle>bury c1 A,t\<rangle> \<longrightarrow>\<^sub>c t'" using Cond(5) by auto
    1.56 +    show ?thesis using Cond(1)[OF _ s t] Cond(3) by fastsimp
    1.57 +  next
    1.58 +    assume "\<not> b s"
    1.59 +    hence s: "\<langle>c2,s\<rangle> \<longrightarrow>\<^sub>c s'" using Cond(4) by auto
    1.60 +    have "\<not> b t" using `\<not> b s` Cond(3) by (simp add: ball_Un)(blast dest: dep_on)
    1.61 +    hence t: "\<langle>bury c2 A,t\<rangle> \<longrightarrow>\<^sub>c t'" using Cond(5) by auto
    1.62 +    show ?thesis using Cond(2)[OF _ s t] Cond(3) by fastsimp
    1.63 +  qed
    1.64 +next
    1.65 +  case (While b c) note IH = this
    1.66 +  { fix cw
    1.67 +    have "\<langle>cw,s\<rangle> \<longrightarrow>\<^sub>c s' \<Longrightarrow> cw = (While b c) \<Longrightarrow> \<langle>bury cw A,t\<rangle> \<longrightarrow>\<^sub>c t' \<Longrightarrow>
    1.68 +          \<forall> x \<in> L cw A. s x = t x \<Longrightarrow> \<forall>x\<in>A. s' x = t' x"
    1.69 +    proof (induct arbitrary: t A pred:evalc)
    1.70 +      case WhileFalse
    1.71 +      have "\<not> b t" using WhileFalse by (simp add: ball_Un)(blast dest:dep_on)
    1.72 +      then have "t' = t" using WhileFalse by auto
    1.73 +      then show ?case using WhileFalse by auto
    1.74 +    next
    1.75 +      case (WhileTrue _ s _ s'' s')
    1.76 +      have "\<langle>c,s\<rangle> \<longrightarrow>\<^sub>c s''" using WhileTrue(2,6) by simp
    1.77 +      have "b t" using WhileTrue by (simp add: ball_Un)(blast dest:dep_on)
    1.78 +      then obtain t'' where tt'': "\<langle>bury c (Dep b \<union> A \<union> L c A),t\<rangle> \<longrightarrow>\<^sub>c t''"
    1.79 +	and "\<langle>bury (While b c) A,t''\<rangle> \<longrightarrow>\<^sub>c t'"
    1.80 +        using WhileTrue(6,7) by auto
    1.81 +      have "\<forall>x\<in>Dep b \<union> A \<union> L c A. s'' x = t'' x"
    1.82 +	using IH(1)[OF _ `\<langle>c,s\<rangle> \<longrightarrow>\<^sub>c s''` tt''] WhileTrue(6,8)
    1.83 +	by (auto simp:L_gen_kill)
    1.84 +      moreover then have "\<forall>x\<in>L (While b c) A. s'' x = t'' x" by auto
    1.85 +      ultimately show ?case
    1.86 +	using WhileTrue(5,6) `\<langle>bury (While b c) A,t''\<rangle> \<longrightarrow>\<^sub>c t'` by metis
    1.87 +    qed auto }
    1.88 +  from this[OF IH(3) _ IH(4,2)] show ?case by metis
    1.89 +qed
    1.90 +
    1.91 +
    1.92  end
    1.93 \ No newline at end of file