diff -r e99f706aeab9 -r ad8e0a789af6 src/HOL/Hoare_Parallel/RG_Examples.thy --- a/src/HOL/Hoare_Parallel/RG_Examples.thy Sat Dec 27 19:51:55 2014 +0100 +++ b/src/HOL/Hoare_Parallel/RG_Examples.thy Sat Dec 27 20:32:06 2014 +0100 @@ -1,12 +1,12 @@ -section {* Examples *} +section \Examples\ theory RG_Examples imports RG_Syntax begin -lemmas definitions [simp]= stable_def Pre_def Rely_def Guar_def Post_def Com_def +lemmas definitions [simp]= stable_def Pre_def Rely_def Guar_def Post_def Com_def -subsection {* Set Elements of an Array to Zero *} +subsection \Set Elements of an Array to Zero\ lemma le_less_trans2: "\(j::nat) j\ \ i COBEGIN SCHEME [0 \ i < n] - (\A := \A [i := 0], - \ n < length \A \, - \ length \A = length \A \ \A ! i = \A ! i \, - \ length \A = length \A \ (\j j \ \A ! j = \A ! j) \, - \ \A ! i = 0 \) + (\A := \A [i := 0], + \ n < length \A \, + \ length \A = length \A \ \A ! i = \A ! i \, + \ length \A = length \A \ (\j j \ \A ! j = \A ! j) \, + \ \A ! i = 0 \) COEND SAT [\ n < length \A \, \ \A = \A \, \ True \, \ \i < n. \A ! i = 0 \]" apply(rule Parallel) -apply (auto intro!: Basic) +apply (auto intro!: Basic) done -lemma Example1_parameterized: +lemma Example1_parameterized: "k < t \ - \ COBEGIN - SCHEME [k*n\i<(Suc k)*n] (\A:=\A[i:=0], - \t*n < length \A\, - \t*n < length \A \ length \A=length \A \ \A!i = \A!i\, - \t*n < length \A \ length \A=length \A \ (\jA . i\j \ \A!j = \A!j)\, - \\A!i=0\) - COEND - SAT [\t*n < length \A\, - \t*n < length \A \ length \A=length \A \ (\iA!(k*n+i)=\A!(k*n+i))\, - \t*n < length \A \ length \A=length \A \ - (\iA . (i \A!i = \A!i) \ ((Suc k)*n \ i\ \A!i = \A!i))\, + \ COBEGIN + SCHEME [k*n\i<(Suc k)*n] (\A:=\A[i:=0], + \t*n < length \A\, + \t*n < length \A \ length \A=length \A \ \A!i = \A!i\, + \t*n < length \A \ length \A=length \A \ (\jA . i\j \ \A!j = \A!j)\, + \\A!i=0\) + COEND + SAT [\t*n < length \A\, + \t*n < length \A \ length \A=length \A \ (\iA!(k*n+i)=\A!(k*n+i))\, + \t*n < length \A \ length \A=length \A \ + (\iA . (i \A!i = \A!i) \ ((Suc k)*n \ i\ \A!i = \A!i))\, \\iA!(k*n+i) = 0\]" apply(rule Parallel) apply auto apply(erule_tac x="k*n +i" in allE) apply(subgoal_tac "k*n+i Increment a Variable in Parallel\ -subsubsection {* Two components *} +subsubsection \Two components\ record Example2 = x :: nat c_0 :: nat c_1 :: nat -lemma Example2: +lemma Example2: "\ COBEGIN - (\ \x:=\x+1;; \c_0:=\c_0 + 1 \, - \\x=\c_0 + \c_1 \ \c_0=0\, - \\c_0 = \c_0 \ - (\x=\c_0 + \c_1 - \ \x = \c_0 + \c_1)\, - \\c_1 = \c_1 \ - (\x=\c_0 + \c_1 + (\ \x:=\x+1;; \c_0:=\c_0 + 1 \, + \\x=\c_0 + \c_1 \ \c_0=0\, + \\c_0 = \c_0 \ + (\x=\c_0 + \c_1 + \ \x = \c_0 + \c_1)\, + \\c_1 = \c_1 \ + (\x=\c_0 + \c_1 \ \x =\c_0 + \c_1)\, \\x=\c_0 + \c_1 \ \c_0=1 \) \ - (\ \x:=\x+1;; \c_1:=\c_1+1 \, - \\x=\c_0 + \c_1 \ \c_1=0 \, - \\c_1 = \c_1 \ - (\x=\c_0 + \c_1 - \ \x = \c_0 + \c_1)\, - \\c_0 = \c_0 \ - (\x=\c_0 + \c_1 + (\ \x:=\x+1;; \c_1:=\c_1+1 \, + \\x=\c_0 + \c_1 \ \c_1=0 \, + \\c_1 = \c_1 \ + (\x=\c_0 + \c_1 + \ \x = \c_0 + \c_1)\, + \\c_0 = \c_0 \ + (\x=\c_0 + \c_1 \ \x =\c_0 + \c_1)\, \\x=\c_0 + \c_1 \ \c_1=1\) COEND - SAT [\\x=0 \ \c_0=0 \ \c_1=0\, + SAT [\\x=0 \ \c_0=0 \ \c_1=0\, \\x=\x \ \c_0= \c_0 \ \c_1=\c_1\, \True\, \\x=2\]" @@ -151,9 +151,9 @@ apply(auto intro!: Basic) done -subsubsection {* Parameterized *} +subsubsection \Parameterized\ -lemma Example2_lemma2_aux: "j +lemma Example2_lemma2_aux: "j (\i=0..i=0..i=0.. s \ (\i::nat=0..i=0..j \ Suc (\i::nat=0..i=0..i::nat=0..< n. b i)=(\i=0..< n. (b (j:=Suc 0)) i)" by(simp add:Example2_lemma2) -record Example2_parameterized = +record Example2_parameterized = C :: "nat \ nat" y :: nat -lemma Example2_parameterized: "0 +lemma Example2_parameterized: "0 \ COBEGIN SCHEME [0\i \y:=\y+1;; \C:=\C (i:=1) \, - \\y=(\i=0..C i) \ \C i=0\, - \\C i = \C i \ - (\y=(\i=0..C i) \ \y =(\i=0..C i))\, - \(\jj \ \C j = \C j) \ + (\ \y:=\y+1;; \C:=\C (i:=1) \, + \\y=(\i=0..C i) \ \C i=0\, + \\C i = \C i \ + (\y=(\i=0..C i) \ \y =(\i=0..C i))\, + \(\jj \ \C j = \C j) \ (\y=(\i=0..C i) \ \y =(\i=0..C i))\, - \\y=(\i=0..C i) \ \C i=1\) + \\y=(\i=0..C i) \ \C i=1\) COEND SAT [\\y=0 \ (\i=0..C i)=0 \, \\C=\C \ \y=\y\, \True\, \\y=n\]" apply(rule Parallel) @@ -229,9 +229,9 @@ apply simp_all done -subsection {* Find Least Element *} +subsection \Find Least Element\ -text {* A previous lemma: *} +text \A previous lemma:\ lemma mod_aux :"\i < (n::nat); a mod n = i; j < a + n; j mod n = i; a < j\ \ False" apply(subgoal_tac "a=a div n*n + a mod n" ) @@ -251,25 +251,25 @@ X :: "nat \ nat" Y :: "nat \ nat" -lemma Example3: "m mod n=0 \ - \ COBEGIN +lemma Example3: "m mod n=0 \ + \ COBEGIN SCHEME [0\ijX i < \Y j) DO - IF P(B!(\X i)) THEN \Y:=\Y (i:=\X i) - ELSE \X:= \X (i:=(\X i)+ n) FI + (WHILE (\jX i < \Y j) DO + IF P(B!(\X i)) THEN \Y:=\Y (i:=\X i) + ELSE \X:= \X (i:=(\X i)+ n) FI OD, \(\X i) mod n=i \ (\j<\X i. j mod n=i \ \P(B!j)) \ (\Y i P(B!(\Y i)) \ \Y i\ m+i)\, - \(\jj \ \Y j \ \Y j) \ \X i = \X i \ + \(\jj \ \Y j \ \Y j) \ \X i = \X i \ \Y i = \Y i\, - \(\jj \ \X j = \X j \ \Y j = \Y j) \ + \(\jj \ \X j = \X j \ \Y j = \Y j) \ \Y i \ \Y i\, - \(\X i) mod n=i \ (\j<\X i. j mod n=i \ \P(B!j)) \ (\Y i P(B!(\Y i)) \ \Y i\ m+i) \ (\jY j \ \X i) \) + \(\X i) mod n=i \ (\j<\X i. j mod n=i \ \P(B!j)) \ (\Y i P(B!(\Y i)) \ \Y i\ m+i) \ (\jY j \ \X i) \) COEND SAT [\ \iX i=i \ \Y i=m+i \,\\X=\X \ \Y=\Y\,\True\, - \\iX i) mod n=i \ (\j<\X i. j mod n=i \ \P(B!j)) \ + \\iX i) mod n=i \ (\j<\X i. j mod n=i \ \P(B!j)) \ (\Y i P(B!(\Y i)) \ \Y i\ m+i) \ (\jY j \ \X i)\]" apply(rule Parallel) ---{*5 subgoals left *} +--\5 subgoals left\ apply force+ apply clarify apply simp @@ -298,29 +298,29 @@ apply auto done -text {* Same but with a list as auxiliary variable: *} +text \Same but with a list as auxiliary variable:\ record Example3_list = X :: "nat list" Y :: "nat list" lemma Example3_list: "m mod n=0 \ \ (COBEGIN SCHEME [0\ijX!i < \Y!j) DO - IF P(B!(\X!i)) THEN \Y:=\Y[i:=\X!i] ELSE \X:= \X[i:=(\X!i)+ n] FI + (WHILE (\jX!i < \Y!j) DO + IF P(B!(\X!i)) THEN \Y:=\Y[i:=\X!i] ELSE \X:= \X[i:=(\X!i)+ n] FI OD, \nX \ nY \ (\X!i) mod n=i \ (\j<\X!i. j mod n=i \ \P(B!j)) \ (\Y!i P(B!(\Y!i)) \ \Y!i\ m+i)\, - \(\jj \ \Y!j \ \Y!j) \ \X!i = \X!i \ + \(\jj \ \Y!j \ \Y!j) \ \X!i = \X!i \ \Y!i = \Y!i \ length \X = length \X \ length \Y = length \Y\, - \(\jj \ \X!j = \X!j \ \Y!j = \Y!j) \ + \(\jj \ \X!j = \X!j \ \Y!j = \Y!j) \ \Y!i \ \Y!i \ length \X = length \X \ length \Y = length \Y\, \(\X!i) mod n=i \ (\j<\X!i. j mod n=i \ \P(B!j)) \ (\Y!i P(B!(\Y!i)) \ \Y!i\ m+i) \ (\jY!j \ \X!i) \) COEND) SAT [\nX \ nY \ (\iX!i=i \ \Y!i=m+i) \, \\X=\X \ \Y=\Y\, \True\, - \\iX!i) mod n=i \ (\j<\X!i. j mod n=i \ \P(B!j)) \ + \\iX!i) mod n=i \ (\j<\X!i. j mod n=i \ \P(B!j)) \ (\Y!i P(B!(\Y!i)) \ \Y!i\ m+i) \ (\jY!j \ \X!i)\]" apply (rule Parallel) -apply (auto cong del: strong_INF_cong strong_SUP_cong) +apply (auto cong del: strong_INF_cong strong_SUP_cong) apply force apply (rule While) apply force