# HG changeset patch # User wenzelm # Date 1377641930 -7200 # Node ID effd8fcabca29cb61698c6797b696e4842040472 # Parent 07593a0a27f471b5bb6ee19fcb27ee6fedf73e61 more symbols; diff -r 07593a0a27f4 -r effd8fcabca2 src/HOL/Hoare_Parallel/Gar_Coll.thy --- a/src/HOL/Hoare_Parallel/Gar_Coll.thy Tue Aug 27 23:54:23 2013 +0200 +++ b/src/HOL/Hoare_Parallel/Gar_Coll.thy Wed Aug 28 00:18:50 2013 +0200 @@ -40,15 +40,15 @@ edge but has not yet colored the new target. *} definition Redirect_Edge :: "gar_coll_state ann_com" where - "Redirect_Edge \ .{\Mut_init \ \z}. \\E:=\E[R:=(fst(\E!R), T)],, \z:= (\\z)\" + "Redirect_Edge \ \\Mut_init \ \z\ \\E:=\E[R:=(fst(\E!R), T)],, \z:= (\\z)\" definition Color_Target :: "gar_coll_state ann_com" where - "Color_Target \ .{\Mut_init \ \\z}. \\M:=\M[T:=Black],, \z:= (\\z)\" + "Color_Target \ \\Mut_init \ \\z\ \\M:=\M[T:=Black],, \z:= (\\z)\" definition Mutator :: "gar_coll_state ann_com" where "Mutator \ - .{\Mut_init \ \z}. - WHILE True INV .{\Mut_init \ \z}. + \\Mut_init \ \z\ + WHILE True INV \\Mut_init \ \z\ DO Redirect_Edge ;; Color_Target OD" subsubsection {* Correctness of the mutator *} @@ -64,14 +64,14 @@ done lemma Color_Target: - "\ Color_Target .{\Mut_init \ \z}." + "\ Color_Target \\Mut_init \ \z\" apply (unfold mutator_defs) apply annhoare apply(simp_all) done lemma Mutator: - "\ Mutator .{False}." + "\ Mutator \False\" apply(unfold Mutator_def) apply annhoare apply(simp_all add:Redirect_Edge Color_Target) @@ -101,21 +101,21 @@ definition Blacken_Roots :: " gar_coll_state ann_com" where "Blacken_Roots \ - .{\Proper}. + \\Proper\ \ind:=0;; - .{\Proper \ \ind=0}. + \\Proper \ \ind=0\ WHILE \indM - INV .{\Proper \ (\i<\ind. i \ Roots \ \M!i=Black) \ \ind\length \M}. - DO .{\Proper \ (\i<\ind. i \ Roots \ \M!i=Black) \ \indM}. + INV \\Proper \ (\i<\ind. i \ Roots \ \M!i=Black) \ \ind\length \M\ + DO \\Proper \ (\i<\ind. i \ Roots \ \M!i=Black) \ \indM\ IF \ind\Roots THEN - .{\Proper \ (\i<\ind. i \ Roots \ \M!i=Black) \ \indM \ \ind\Roots}. + \\Proper \ (\i<\ind. i \ Roots \ \M!i=Black) \ \indM \ \ind\Roots\ \M:=\M[\ind:=Black] FI;; - .{\Proper \ (\i<\ind+1. i \ Roots \ \M!i=Black) \ \indM}. + \\Proper \ (\i<\ind+1. i \ Roots \ \M!i=Black) \ \indM\ \ind:=\ind+1 OD" lemma Blacken_Roots: - "\ Blacken_Roots .{\Proper \ Roots\Blacks \M}." + "\ Blacken_Roots \\Proper \ Roots\Blacks \M\" apply (unfold Blacken_Roots_def) apply annhoare apply(simp_all add:collector_defs Graph_defs) @@ -135,28 +135,28 @@ definition Propagate_Black_aux :: "gar_coll_state ann_com" where "Propagate_Black_aux \ - .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M}. + \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M\ \ind:=0;; - .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M \ \ind=0}. + \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M \ \ind=0\ WHILE \indE - INV .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ \PBInv \ind \ \ind\length \E}. - DO .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ \PBInv \ind \ \indE}. + INV \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \ \PBInv \ind \ \ind\length \E\ + DO \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \ \PBInv \ind \ \indE\ IF \M!(fst (\E!\ind)) = Black THEN - .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ \PBInv \ind \ \indE \ \M!fst(\E!\ind)=Black}. + \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \ \PBInv \ind \ \indE \ \M!fst(\E!\ind)=Black\ \M:=\M[snd(\E!\ind):=Black];; - .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ \PBInv (\ind + 1) \ \indE}. + \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \ \PBInv (\ind + 1) \ \indE\ \ind:=\ind+1 FI OD" lemma Propagate_Black_aux: "\ Propagate_Black_aux - .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ ( \obc < Blacks \M \ \Safe)}." + \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \ ( \obc < Blacks \M \ \Safe)\" apply (unfold Propagate_Black_aux_def PBInv_def collector_defs) apply annhoare apply(simp_all add:Graph6 Graph7 Graph8 Graph12) @@ -215,32 +215,32 @@ definition Propagate_Black :: " gar_coll_state ann_com" where "Propagate_Black \ - .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M}. + \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M\ \ind:=0;; - .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M \ \ind=0}. + \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M \ \ind=0\ WHILE \indE - INV .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ \PBInv \ind \ \ind\length \E}. - DO .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ \PBInv \ind \ \indE}. + INV \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \ \PBInv \ind \ \ind\length \E\ + DO \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \ \PBInv \ind \ \indE\ IF (\M!(fst (\E!\ind)))=Black THEN - .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ \PBInv \ind \ \indE \ (\M!fst(\E!\ind))=Black}. + \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \ \PBInv \ind \ \indE \ (\M!fst(\E!\ind))=Black\ \k:=(snd(\E!\ind));; - .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M \ \PBInv \ind \ \indE \ (\M!fst(\E!\ind))=Black - \ \Auxk}. + \ \Auxk\ \\M:=\M[\k:=Black],, \ind:=\ind+1\ - ELSE .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ \PBInv \ind \ \indE}. + ELSE \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \ \PBInv \ind \ \indE\ \IF (\M!(fst (\E!\ind)))\Black THEN \ind:=\ind+1 FI\ FI OD" lemma Propagate_Black: "\ Propagate_Black - .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ ( \obc < Blacks \M \ \Safe)}." + \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \ ( \obc < Blacks \M \ \Safe)\" apply (unfold Propagate_Black_def PBInv_def Auxk_def collector_defs) apply annhoare apply(simp_all add: Graph6 Graph7 Graph8 Graph12) @@ -325,42 +325,42 @@ definition Count :: " gar_coll_state ann_com" where "Count \ - .{\Proper \ Roots\Blacks \M + \\Proper \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M - \ length \Ma=length \M \ (\obc < Blacks \Ma \ \Safe) \ \bc={}}. + \ length \Ma=length \M \ (\obc < Blacks \Ma \ \Safe) \ \bc={}\ \ind:=0;; - .{\Proper \ Roots\Blacks \M + \\Proper \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ (\obc < Blacks \Ma \ \Safe) \ \bc={} - \ \ind=0}. + \ \ind=0\ WHILE \indM - INV .{\Proper \ Roots\Blacks \M + INV \\Proper \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ \CountInv \ind - \ ( \obc < Blacks \Ma \ \Safe) \ \ind\length \M}. - DO .{\Proper \ Roots\Blacks \M + \ ( \obc < Blacks \Ma \ \Safe) \ \ind\length \M\ + DO \\Proper \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ \CountInv \ind - \ ( \obc < Blacks \Ma \ \Safe) \ \indM}. + \ ( \obc < Blacks \Ma \ \Safe) \ \indM\ IF \M!\ind=Black - THEN .{\Proper \ Roots\Blacks \M + THEN \\Proper \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ \CountInv \ind - \ ( \obc < Blacks \Ma \ \Safe) \ \indM \ \M!\ind=Black}. + \ ( \obc < Blacks \Ma \ \Safe) \ \indM \ \M!\ind=Black\ \bc:=insert \ind \bc FI;; - .{\Proper \ Roots\Blacks \M + \\Proper \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ \CountInv (\ind+1) - \ ( \obc < Blacks \Ma \ \Safe) \ \indM}. + \ ( \obc < Blacks \Ma \ \Safe) \ \indM\ \ind:=\ind+1 OD" lemma Count: "\ Count - .{\Proper \ Roots\Blacks \M + \\Proper \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\\bc \ \bc\Blacks \M \ length \Ma=length \M - \ (\obc < Blacks \Ma \ \Safe)}." + \ (\obc < Blacks \Ma \ \Safe)\" apply(unfold Count_def) apply annhoare apply(simp_all add:CountInv_def Graph6 Graph7 Graph8 Graph12 Blacks_def collector_defs) @@ -392,24 +392,24 @@ definition Append :: "gar_coll_state ann_com" where "Append \ - .{\Proper \ Roots\Blacks \M \ \Safe}. + \\Proper \ Roots\Blacks \M \ \Safe\ \ind:=0;; - .{\Proper \ Roots\Blacks \M \ \Safe \ \ind=0}. + \\Proper \ Roots\Blacks \M \ \Safe \ \ind=0\ WHILE \indM - INV .{\Proper \ \AppendInv \ind \ \ind\length \M}. - DO .{\Proper \ \AppendInv \ind \ \indM}. + INV \\Proper \ \AppendInv \ind \ \ind\length \M\ + DO \\Proper \ \AppendInv \ind \ \indM\ IF \M!\ind=Black THEN - .{\Proper \ \AppendInv \ind \ \indM \ \M!\ind=Black}. + \\Proper \ \AppendInv \ind \ \indM \ \M!\ind=Black\ \M:=\M[\ind:=White] - ELSE .{\Proper \ \AppendInv \ind \ \indM \ \ind\Reach \E}. + ELSE \\Proper \ \AppendInv \ind \ \indM \ \ind\Reach \E\ \E:=Append_to_free(\ind,\E) FI;; - .{\Proper \ \AppendInv (\ind+1) \ \indM}. + \\Proper \ \AppendInv (\ind+1) \ \indM\ \ind:=\ind+1 OD" lemma Append: - "\ Append .{\Proper}." + "\ Append \\Proper\" apply(unfold Append_def AppendInv_def) apply annhoare apply(simp_all add:collector_defs Graph6 Graph7 Graph8 Append_to_free0 Append_to_free1 Graph12) @@ -433,30 +433,30 @@ definition Collector :: " gar_coll_state ann_com" where "Collector \ -.{\Proper}. - WHILE True INV .{\Proper}. +\\Proper\ + WHILE True INV \\Proper\ DO Blacken_Roots;; - .{\Proper \ Roots\Blacks \M}. + \\Proper \ Roots\Blacks \M\ \obc:={};; - .{\Proper \ Roots\Blacks \M \ \obc={}}. + \\Proper \ Roots\Blacks \M \ \obc={}\ \bc:=Roots;; - .{\Proper \ Roots\Blacks \M \ \obc={} \ \bc=Roots}. + \\Proper \ Roots\Blacks \M \ \obc={} \ \bc=Roots\ \Ma:=M_init;; - .{\Proper \ Roots\Blacks \M \ \obc={} \ \bc=Roots \ \Ma=M_init}. + \\Proper \ Roots\Blacks \M \ \obc={} \ \bc=Roots \ \Ma=M_init\ WHILE \obc\\bc - INV .{\Proper \ Roots\Blacks \M + INV \\Proper \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\\bc \ \bc\Blacks \M - \ length \Ma=length \M \ (\obc < Blacks \Ma \ \Safe)}. - DO .{\Proper \ Roots\Blacks \M \ \bc\Blacks \M}. + \ length \Ma=length \M \ (\obc < Blacks \Ma \ \Safe)\ + DO \\Proper \ Roots\Blacks \M \ \bc\Blacks \M\ \obc:=\bc;; Propagate_Black;; - .{\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ (\obc < Blacks \M \ \Safe)}. + \\Proper \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \ (\obc < Blacks \M \ \Safe)\ \Ma:=\M;; - .{\Proper \ Roots\Blacks \M \ \obc\Blacks \Ma + \\Proper \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M - \ ( \obc < Blacks \Ma \ \Safe)}. + \ ( \obc < Blacks \Ma \ \Safe)\ \bc:={};; Count OD;; @@ -464,7 +464,7 @@ OD" lemma Collector: - "\ Collector .{False}." + "\ Collector \False\" apply(unfold Collector_def) apply annhoare apply(simp_all add: Blacken_Roots Propagate_Black Count Append) @@ -806,15 +806,15 @@ text {* In total there are 289 verification conditions. *} lemma Gar_Coll: - "\- .{\Proper \ \Mut_init \ \z}. + "\- \\Proper \ \Mut_init \ \z\ COBEGIN Collector - .{False}. + \False\ \ Mutator - .{False}. + \False\ COEND - .{False}." + \False\" apply oghoare apply(force simp add: Mutator_def Collector_def modules) apply(rule Collector) diff -r 07593a0a27f4 -r effd8fcabca2 src/HOL/Hoare_Parallel/Mul_Gar_Coll.thy --- a/src/HOL/Hoare_Parallel/Mul_Gar_Coll.thy Tue Aug 27 23:54:23 2013 +0200 +++ b/src/HOL/Hoare_Parallel/Mul_Gar_Coll.thy Wed Aug 28 00:18:50 2013 +0200 @@ -32,21 +32,21 @@ definition Mul_Redirect_Edge :: "nat \ nat \ mul_gar_coll_state ann_com" where "Mul_Redirect_Edge j n \ - .{\Mul_mut_init n \ Z (\Muts!j)}. + \\Mul_mut_init n \ Z (\Muts!j)\ \IF T(\Muts!j) \ Reach \E THEN \E:= \E[R (\Muts!j):= (fst (\E!R(\Muts!j)), T (\Muts!j))] FI,, \Muts:= \Muts[j:= (\Muts!j) \Z:=False\]\" definition Mul_Color_Target :: "nat \ nat \ mul_gar_coll_state ann_com" where "Mul_Color_Target j n \ - .{\Mul_mut_init n \ \ Z (\Muts!j)}. + \\Mul_mut_init n \ \ Z (\Muts!j)\ \\M:=\M[T (\Muts!j):=Black],, \Muts:=\Muts[j:= (\Muts!j) \Z:=True\]\" definition Mul_Mutator :: "nat \ nat \ mul_gar_coll_state ann_com" where "Mul_Mutator j n \ - .{\Mul_mut_init n \ Z (\Muts!j)}. + \\Mul_mut_init n \ Z (\Muts!j)\ WHILE True - INV .{\Mul_mut_init n \ Z (\Muts!j)}. + INV \\Mul_mut_init n \ Z (\Muts!j)\ DO Mul_Redirect_Edge j n ;; Mul_Color_Target j n OD" @@ -67,7 +67,7 @@ lemma Mul_Color_Target: "0\j \ j \ Mul_Color_Target j n - .{\Mul_mut_init n \ Z (\Muts!j)}." + \\Mul_mut_init n \ Z (\Muts!j)\" apply (unfold mul_mutator_defs) apply annhoare apply(simp_all) @@ -76,7 +76,7 @@ done lemma Mul_Mutator: "0\j \ j - \ Mul_Mutator j n .{False}." + \ Mul_Mutator j n \False\" apply(unfold Mul_Mutator_def) apply annhoare apply(simp_all add:Mul_Redirect_Edge Mul_Color_Target) @@ -139,13 +139,13 @@ subsubsection {* Modular Parameterized Mutators *} lemma Mul_Parameterized_Mutators: "0 - \- .{\Mul_mut_init n \ (\iMuts!i))}. + \- \\Mul_mut_init n \ (\iMuts!i))\ COBEGIN SCHEME [0\ j< n] Mul_Mutator j n - .{False}. + \False\ COEND - .{False}." + \False\" apply oghoare apply(force simp add:Mul_Mutator_def mul_mutator_defs nth_list_update) apply(erule Mul_Mutator) @@ -175,22 +175,22 @@ definition Mul_Blacken_Roots :: "nat \ mul_gar_coll_state ann_com" where "Mul_Blacken_Roots n \ - .{\Mul_Proper n}. + \\Mul_Proper n\ \ind:=0;; - .{\Mul_Proper n \ \ind=0}. + \\Mul_Proper n \ \ind=0\ WHILE \indM - INV .{\Mul_Proper n \ (\i<\ind. i\Roots \ \M!i=Black) \ \ind\length \M}. - DO .{\Mul_Proper n \ (\i<\ind. i\Roots \ \M!i=Black) \ \indM}. + INV \\Mul_Proper n \ (\i<\ind. i\Roots \ \M!i=Black) \ \ind\length \M\ + DO \\Mul_Proper n \ (\i<\ind. i\Roots \ \M!i=Black) \ \indM\ IF \ind\Roots THEN - .{\Mul_Proper n \ (\i<\ind. i\Roots \ \M!i=Black) \ \indM \ \ind\Roots}. + \\Mul_Proper n \ (\i<\ind. i\Roots \ \M!i=Black) \ \indM \ \ind\Roots\ \M:=\M[\ind:=Black] FI;; - .{\Mul_Proper n \ (\i<\ind+1. i\Roots \ \M!i=Black) \ \indM}. + \\Mul_Proper n \ (\i<\ind+1. i\Roots \ \M!i=Black) \ \indM\ \ind:=\ind+1 OD" lemma Mul_Blacken_Roots: "\ Mul_Blacken_Roots n - .{\Mul_Proper n \ Roots \ Blacks \M}." + \\Mul_Proper n \ Roots \ Blacks \M\" apply (unfold Mul_Blacken_Roots_def) apply annhoare apply(simp_all add:mul_collector_defs Graph_defs) @@ -213,40 +213,40 @@ definition Mul_Propagate_Black :: "nat \ mul_gar_coll_state ann_com" where "Mul_Propagate_Black n \ - .{\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ (\Safe \ \l\\Queue \ \obc\Blacks \M)}. + \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \ (\Safe \ \l\\Queue \ \obc\Blacks \M)\ \ind:=0;; - .{\Mul_Proper n \ Roots\Blacks \M + \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \M \ Blacks \M\Blacks \M \ \bc\Blacks \M - \ (\Safe \ \l\\Queue \ \obc\Blacks \M) \ \ind=0}. + \ (\Safe \ \l\\Queue \ \obc\Blacks \M) \ \ind=0\ WHILE \indE - INV .{\Mul_Proper n \ Roots\Blacks \M + INV \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ \Mul_PBInv \ \ind\length \E}. - DO .{\Mul_Proper n \ Roots\Blacks \M + \ \Mul_PBInv \ \ind\length \E\ + DO \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ \Mul_PBInv \ \indE}. + \ \Mul_PBInv \ \indE\ IF \M!(fst (\E!\ind))=Black THEN - .{\Mul_Proper n \ Roots\Blacks \M + \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ \Mul_PBInv \ (\M!fst(\E!\ind))=Black \ \indE}. + \ \Mul_PBInv \ (\M!fst(\E!\ind))=Black \ \indE\ \k:=snd(\E!\ind);; - .{\Mul_Proper n \ Roots\Blacks \M + \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M \ (\Safe \ \obc\Blacks \M \ \l<\Queue \ (\i<\ind. \BtoW(\E!i,\M)) \ \l\\Queue \ \Mul_Auxk ) \ \kM \ \M!fst(\E!\ind)=Black - \ \indE}. + \ \indE\ \\M:=\M[\k:=Black],,\ind:=\ind+1\ - ELSE .{\Mul_Proper n \ Roots\Blacks \M + ELSE \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ \Mul_PBInv \ \indE}. + \ \Mul_PBInv \ \indE\ \IF \M!(fst (\E!\ind))\Black THEN \ind:=\ind+1 FI\ FI OD" lemma Mul_Propagate_Black: "\ Mul_Propagate_Black n - .{\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M - \ (\Safe \ \obc\Blacks \M \ \l<\Queue \ (\l\\Queue \ \obc\Blacks \M))}." + \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M + \ (\Safe \ \obc\Blacks \M \ \l<\Queue \ (\l\\Queue \ \obc\Blacks \M))\" apply(unfold Mul_Propagate_Black_def) apply annhoare apply(simp_all add:Mul_PBInv_def mul_collector_defs Mul_Auxk_def Graph6 Graph7 Graph8 Graph12 mul_collector_defs Queue_def) @@ -295,51 +295,51 @@ definition Mul_Count :: "nat \ mul_gar_coll_state ann_com" where "Mul_Count n \ - .{\Mul_Proper n \ Roots\Blacks \M + \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ (\Safe \ \obc\Blacks \Ma \ \l<\q \ (\q\\Queue \ \obc\Blacks \M) ) - \ \q \bc={}}. + \ \q \bc={}\ \ind:=0;; - .{\Mul_Proper n \ Roots\Blacks \M + \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ (\Safe \ \obc\Blacks \Ma \ \l<\q \ (\q\\Queue \ \obc\Blacks \M) ) - \ \q \bc={} \ \ind=0}. + \ \q \bc={} \ \ind=0\ WHILE \indM - INV .{\Mul_Proper n \ Roots\Blacks \M + INV \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ \Mul_CountInv \ind \ (\Safe \ \obc\Blacks \Ma \ \l<\q \ (\q\\Queue \ \obc\Blacks \M)) - \ \q \ind\length \M}. - DO .{\Mul_Proper n \ Roots\Blacks \M + \ \q \ind\length \M\ + DO \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ \Mul_CountInv \ind \ (\Safe \ \obc\Blacks \Ma \ \l<\q \ (\q\\Queue \ \obc\Blacks \M)) - \ \q \indM}. + \ \q \indM\ IF \M!\ind=Black - THEN .{\Mul_Proper n \ Roots\Blacks \M + THEN \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ \Mul_CountInv \ind \ (\Safe \ \obc\Blacks \Ma \ \l<\q \ (\q\\Queue \ \obc\Blacks \M)) - \ \q \indM \ \M!\ind=Black}. + \ \q \indM \ \M!\ind=Black\ \bc:=insert \ind \bc FI;; - .{\Mul_Proper n \ Roots\Blacks \M + \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ \Mul_CountInv (\ind+1) \ (\Safe \ \obc\Blacks \Ma \ \l<\q \ (\q\\Queue \ \obc\Blacks \M)) - \ \q \indM}. + \ \q \indM\ \ind:=\ind+1 OD" lemma Mul_Count: "\ Mul_Count n - .{\Mul_Proper n \ Roots\Blacks \M + \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ Blacks \Ma\\bc \ (\Safe \ \obc\Blacks \Ma \ \l<\q \ (\q\\Queue \ \obc\Blacks \M)) - \ \q \q" apply (unfold Mul_Count_def) apply annhoare apply(simp_all add:Mul_CountInv_def mul_collector_defs Mul_Auxk_def Graph6 Graph7 Graph8 Graph12 mul_collector_defs Queue_def) @@ -393,26 +393,26 @@ definition Mul_Append :: "nat \ mul_gar_coll_state ann_com" where "Mul_Append n \ - .{\Mul_Proper n \ Roots\Blacks \M \ \Safe}. + \\Mul_Proper n \ Roots\Blacks \M \ \Safe\ \ind:=0;; - .{\Mul_Proper n \ Roots\Blacks \M \ \Safe \ \ind=0}. + \\Mul_Proper n \ Roots\Blacks \M \ \Safe \ \ind=0\ WHILE \indM - INV .{\Mul_Proper n \ \Mul_AppendInv \ind \ \ind\length \M}. - DO .{\Mul_Proper n \ \Mul_AppendInv \ind \ \indM}. + INV \\Mul_Proper n \ \Mul_AppendInv \ind \ \ind\length \M\ + DO \\Mul_Proper n \ \Mul_AppendInv \ind \ \indM\ IF \M!\ind=Black THEN - .{\Mul_Proper n \ \Mul_AppendInv \ind \ \indM \ \M!\ind=Black}. + \\Mul_Proper n \ \Mul_AppendInv \ind \ \indM \ \M!\ind=Black\ \M:=\M[\ind:=White] ELSE - .{\Mul_Proper n \ \Mul_AppendInv \ind \ \indM \ \ind\Reach \E}. + \\Mul_Proper n \ \Mul_AppendInv \ind \ \indM \ \ind\Reach \E\ \E:=Append_to_free(\ind,\E) FI;; - .{\Mul_Proper n \ \Mul_AppendInv (\ind+1) \ \indM}. + \\Mul_Proper n \ \Mul_AppendInv (\ind+1) \ \indM\ \ind:=\ind+1 OD" lemma Mul_Append: "\ Mul_Append n - .{\Mul_Proper n}." + \\Mul_Proper n\" apply(unfold Mul_Append_def) apply annhoare apply(simp_all add: mul_collector_defs Mul_AppendInv_def @@ -431,52 +431,52 @@ definition Mul_Collector :: "nat \ mul_gar_coll_state ann_com" where "Mul_Collector n \ -.{\Mul_Proper n}. -WHILE True INV .{\Mul_Proper n}. +\\Mul_Proper n\ +WHILE True INV \\Mul_Proper n\ DO Mul_Blacken_Roots n ;; -.{\Mul_Proper n \ Roots\Blacks \M}. +\\Mul_Proper n \ Roots\Blacks \M\ \obc:={};; -.{\Mul_Proper n \ Roots\Blacks \M \ \obc={}}. +\\Mul_Proper n \ Roots\Blacks \M \ \obc={}\ \bc:=Roots;; -.{\Mul_Proper n \ Roots\Blacks \M \ \obc={} \ \bc=Roots}. +\\Mul_Proper n \ Roots\Blacks \M \ \obc={} \ \bc=Roots\ \l:=0;; -.{\Mul_Proper n \ Roots\Blacks \M \ \obc={} \ \bc=Roots \ \l=0}. +\\Mul_Proper n \ Roots\Blacks \M \ \obc={} \ \bc=Roots \ \l=0\ WHILE \lMul_Proper n \ Roots\Blacks \M \ \bc\Blacks \M \ - (\Safe \ (\l\\Queue \ \bc\Blacks \M) \ \lMul_Proper n \ Roots\Blacks \M \ \bc\Blacks \M - \ (\Safe \ \l\\Queue \ \bc\Blacks \M)}. + INV \\Mul_Proper n \ Roots\Blacks \M \ \bc\Blacks \M \ + (\Safe \ (\l\\Queue \ \bc\Blacks \M) \ \l + DO \\Mul_Proper n \ Roots\Blacks \M \ \bc\Blacks \M + \ (\Safe \ \l\\Queue \ \bc\Blacks \M)\ \obc:=\bc;; Mul_Propagate_Black n;; - .{\Mul_Proper n \ Roots\Blacks \M + \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M \ (\Safe \ \obc\Blacks \M \ \l<\Queue - \ (\l\\Queue \ \obc\Blacks \M))}. + \ (\l\\Queue \ \obc\Blacks \M))\ \bc:={};; - .{\Mul_Proper n \ Roots\Blacks \M + \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \M \ \bc\Blacks \M \ (\Safe \ \obc\Blacks \M \ \l<\Queue - \ (\l\\Queue \ \obc\Blacks \M)) \ \bc={}}. + \ (\l\\Queue \ \obc\Blacks \M)) \ \bc={}\ \ \Ma:=\M,, \q:=\Queue \;; Mul_Count n;; - .{\Mul_Proper n \ Roots\Blacks \M + \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ Blacks \Ma\\bc \ (\Safe \ \obc\Blacks \Ma \ \l<\q \ (\q\\Queue \ \obc\Blacks \M)) - \ \q \q IF \obc=\bc THEN - .{\Mul_Proper n \ Roots\Blacks \M + \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ Blacks \Ma\\bc \ (\Safe \ \obc\Blacks \Ma \ \l<\q \ (\q\\Queue \ \obc\Blacks \M)) - \ \q \obc=\bc}. + \ \q \obc=\bc\ \l:=\l+1 - ELSE .{\Mul_Proper n \ Roots\Blacks \M + ELSE \\Mul_Proper n \ Roots\Blacks \M \ \obc\Blacks \Ma \ Blacks \Ma\Blacks \M \ \bc\Blacks \M \ length \Ma=length \M \ Blacks \Ma\\bc \ (\Safe \ \obc\Blacks \Ma \ \l<\q \ (\q\\Queue \ \obc\Blacks \M)) - \ \q \obc\\bc}. + \ \q \obc\\bc\ \l:=0 FI OD;; Mul_Append n @@ -488,7 +488,7 @@ lemma Mul_Collector: "\ Mul_Collector n - .{False}." + \False\" apply(unfold Mul_Collector_def) apply annhoare apply(simp_all only:pre.simps Mul_Blacken_Roots @@ -1237,16 +1237,16 @@ text {* The total number of verification conditions is 328 *} lemma Mul_Gar_Coll: - "\- .{\Mul_Proper n \ \Mul_mut_init n \ (\iMuts!i))}. + "\- \\Mul_Proper n \ \Mul_mut_init n \ (\iMuts!i))\ COBEGIN Mul_Collector n - .{False}. + \False\ \ SCHEME [0\ j< n] Mul_Mutator j n - .{False}. + \False\ COEND - .{False}." + \False\" apply oghoare --{* Strengthening the precondition *} apply(rule Int_greatest) diff -r 07593a0a27f4 -r effd8fcabca2 src/HOL/Hoare_Parallel/OG_Examples.thy --- a/src/HOL/Hoare_Parallel/OG_Examples.thy Tue Aug 27 23:54:23 2013 +0200 +++ b/src/HOL/Hoare_Parallel/OG_Examples.thy Wed Aug 28 00:18:50 2013 +0200 @@ -16,30 +16,30 @@ hold :: nat lemma Petersons_mutex_1: - "\- .{\pr1=0 \ \\in1 \ \pr2=0 \ \\in2 }. - COBEGIN .{\pr1=0 \ \\in1}. - WHILE True INV .{\pr1=0 \ \\in1}. + "\- \\pr1=0 \ \\in1 \ \pr2=0 \ \\in2 \ + COBEGIN \\pr1=0 \ \\in1\ + WHILE True INV \\pr1=0 \ \\in1\ DO - .{\pr1=0 \ \\in1}. \ \in1:=True,,\pr1:=1 \;; - .{\pr1=1 \ \in1}. \ \hold:=1,,\pr1:=2 \;; - .{\pr1=2 \ \in1 \ (\hold=1 \ \hold=2 \ \pr2=2)}. + \\pr1=0 \ \\in1\ \ \in1:=True,,\pr1:=1 \;; + \\pr1=1 \ \in1\ \ \hold:=1,,\pr1:=2 \;; + \\pr1=2 \ \in1 \ (\hold=1 \ \hold=2 \ \pr2=2)\ AWAIT (\\in2 \ \(\hold=1)) THEN \pr1:=3 END;; - .{\pr1=3 \ \in1 \ (\hold=1 \ \hold=2 \ \pr2=2)}. + \\pr1=3 \ \in1 \ (\hold=1 \ \hold=2 \ \pr2=2)\ \\in1:=False,,\pr1:=0\ - OD .{\pr1=0 \ \\in1}. + OD \\pr1=0 \ \\in1\ \ - .{\pr2=0 \ \\in2}. - WHILE True INV .{\pr2=0 \ \\in2}. + \\pr2=0 \ \\in2\ + WHILE True INV \\pr2=0 \ \\in2\ DO - .{\pr2=0 \ \\in2}. \ \in2:=True,,\pr2:=1 \;; - .{\pr2=1 \ \in2}. \ \hold:=2,,\pr2:=2 \;; - .{\pr2=2 \ \in2 \ (\hold=2 \ (\hold=1 \ \pr1=2))}. + \\pr2=0 \ \\in2\ \ \in2:=True,,\pr2:=1 \;; + \\pr2=1 \ \in2\ \ \hold:=2,,\pr2:=2 \;; + \\pr2=2 \ \in2 \ (\hold=2 \ (\hold=1 \ \pr1=2))\ AWAIT (\\in1 \ \(\hold=2)) THEN \pr2:=3 END;; - .{\pr2=3 \ \in2 \ (\hold=2 \ (\hold=1 \ \pr1=2))}. + \\pr2=3 \ \in2 \ (\hold=2 \ (\hold=1 \ \pr1=2))\ \\in2:=False,,\pr2:=0\ - OD .{\pr2=0 \ \\in2}. + OD \\pr2=0 \ \\in2\ COEND - .{\pr1=0 \ \\in1 \ \pr2=0 \ \\in2}." + \\pr1=0 \ \\in1 \ \pr2=0 \ \\in2\" apply oghoare --{* 104 verification conditions. *} apply auto @@ -57,37 +57,37 @@ after2 :: bool lemma Busy_wait_mutex: - "\- .{True}. + "\- \True\ \flag1:=False,, \flag2:=False,, - COBEGIN .{\\flag1}. + COBEGIN \\\flag1\ WHILE True - INV .{\\flag1}. - DO .{\\flag1}. \ \flag1:=True,,\after1:=False \;; - .{\flag1 \ \\after1}. \ \turn:=1,,\after1:=True \;; - .{\flag1 \ \after1 \ (\turn=1 \ \turn=2)}. + INV \\\flag1\ + DO \\\flag1\ \ \flag1:=True,,\after1:=False \;; + \\flag1 \ \\after1\ \ \turn:=1,,\after1:=True \;; + \\flag1 \ \after1 \ (\turn=1 \ \turn=2)\ WHILE \(\flag2 \ \turn=2) - INV .{\flag1 \ \after1 \ (\turn=1 \ \turn=2)}. - DO .{\flag1 \ \after1 \ (\turn=1 \ \turn=2)}. SKIP OD;; - .{\flag1 \ \after1 \ (\flag2 \ \after2 \ \turn=2)}. + INV \\flag1 \ \after1 \ (\turn=1 \ \turn=2)\ + DO \\flag1 \ \after1 \ (\turn=1 \ \turn=2)\ SKIP OD;; + \\flag1 \ \after1 \ (\flag2 \ \after2 \ \turn=2)\ \flag1:=False OD - .{False}. + \False\ \ - .{\\flag2}. + \\\flag2\ WHILE True - INV .{\\flag2}. - DO .{\\flag2}. \ \flag2:=True,,\after2:=False \;; - .{\flag2 \ \\after2}. \ \turn:=2,,\after2:=True \;; - .{\flag2 \ \after2 \ (\turn=1 \ \turn=2)}. + INV \\\flag2\ + DO \\\flag2\ \ \flag2:=True,,\after2:=False \;; + \\flag2 \ \\after2\ \ \turn:=2,,\after2:=True \;; + \\flag2 \ \after2 \ (\turn=1 \ \turn=2)\ WHILE \(\flag1 \ \turn=1) - INV .{\flag2 \ \after2 \ (\turn=1 \ \turn=2)}. - DO .{\flag2 \ \after2 \ (\turn=1 \ \turn=2)}. SKIP OD;; - .{\flag2 \ \after2 \ (\flag1 \ \after1 \ \turn=1)}. + INV \\flag2 \ \after2 \ (\turn=1 \ \turn=2)\ + DO \\flag2 \ \after2 \ (\turn=1 \ \turn=2)\ SKIP OD;; + \\flag2 \ \after2 \ (\flag1 \ \after1 \ \turn=1)\ \flag2:=False OD - .{False}. + \False\ COEND - .{False}." + \False\" apply oghoare --{* 122 vc *} apply auto @@ -100,21 +100,21 @@ who :: nat lemma Semaphores_mutex: - "\- .{i\j}. + "\- \i\j\ \out:=True ,, - COBEGIN .{i\j}. - WHILE True INV .{i\j}. - DO .{i\j}. AWAIT \out THEN \out:=False,, \who:=i END;; - .{\\out \ \who=i \ i\j}. \out:=True OD - .{False}. + COBEGIN \i\j\ + WHILE True INV \i\j\ + DO \i\j\ AWAIT \out THEN \out:=False,, \who:=i END;; + \\\out \ \who=i \ i\j\ \out:=True OD + \False\ \ - .{i\j}. - WHILE True INV .{i\j}. - DO .{i\j}. AWAIT \out THEN \out:=False,,\who:=j END;; - .{\\out \ \who=j \ i\j}. \out:=True OD - .{False}. + \i\j\ + WHILE True INV \i\j\ + DO \i\j\ AWAIT \out THEN \out:=False,,\who:=j END;; + \\\out \ \who=j \ i\j\ \out:=True OD + \False\ COEND - .{False}." + \False\" apply oghoare --{* 38 vc *} apply auto @@ -123,17 +123,17 @@ subsubsection {* Peterson's Algorithm III: Parameterized version: *} lemma Semaphores_parameterized_mutex: - "0 \- .{True}. + "0 \- \True\ \out:=True ,, COBEGIN SCHEME [0\ i< n] - .{True}. - WHILE True INV .{True}. - DO .{True}. AWAIT \out THEN \out:=False,, \who:=i END;; - .{\\out \ \who=i}. \out:=True OD - .{False}. + \True\ + WHILE True INV \True\ + DO \True\ AWAIT \out THEN \out:=False,, \who:=i END;; + \\\out \ \who=i\ \out:=True OD + \False\ COEND - .{False}." + \False\" apply oghoare --{* 20 vc *} apply auto @@ -150,22 +150,22 @@ lemma Ticket_mutex: "\ 0n=length \turn \ 0<\nextv \ (\k l. k l k\l \ \turn!k < \num \ (\turn!k =0 \ \turn!k\\turn!l))\ \ - \ \- .{n=length \turn}. + \ \- \n=length \turn\ \index:= 0,, - WHILE \index < n INV .{n=length \turn \ (\i<\index. \turn!i=0)}. + WHILE \index < n INV \n=length \turn \ (\i<\index. \turn!i=0)\ DO \turn:= \turn[\index:=0],, \index:=\index +1 OD,, \num:=1 ,, \nextv:=1 ,, COBEGIN SCHEME [0\ i< n] - .{\I}. - WHILE True INV .{\I}. - DO .{\I}. \ \turn :=\turn[i:=\num],, \num:=\num+1 \;; - .{\I}. WAIT \turn!i=\nextv END;; - .{\I \ \turn!i=\nextv}. \nextv:=\nextv+1 + \\I\ + WHILE True INV \\I\ + DO \\I\ \ \turn :=\turn[i:=\num],, \num:=\num+1 \;; + \\I\ WAIT \turn!i=\nextv END;; + \\I \ \turn!i=\nextv\ \nextv:=\nextv+1 OD - .{False}. + \False\ COEND - .{False}." + \False\" apply oghoare --{* 35 vc *} apply simp_all @@ -259,40 +259,40 @@ \ (\\found \ a<\ x \ f(\x)\0) \ ; I2= \\y\a+1 \ (\found \ (a<\x \ f(\x)=0) \ (\y\a \ f(\y)=0)) \ (\\found \ \y\a \ f(\y)\0) \ \ \ - \- .{\ u. f(u)=0}. + \- \\ u. f(u)=0\ \turn:=1,, \found:= False,, \x:=a,, \y:=a+1 ,, - COBEGIN .{\I1}. + COBEGIN \\I1\ WHILE \\found - INV .{\I1}. - DO .{a\\x \ (\found \ \y\a \ f(\y)=0) \ (a<\x \ f(\x)\0)}. + INV \\I1\ + DO \a\\x \ (\found \ \y\a \ f(\y)=0) \ (a<\x \ f(\x)\0)\ WAIT \turn=1 END;; - .{a\\x \ (\found \ \y\a \ f(\y)=0) \ (a<\x \ f(\x)\0)}. + \a\\x \ (\found \ \y\a \ f(\y)=0) \ (a<\x \ f(\x)\0)\ \turn:=2;; - .{a\\x \ (\found \ \y\a \ f(\y)=0) \ (a<\x \ f(\x)\0)}. + \a\\x \ (\found \ \y\a \ f(\y)=0) \ (a<\x \ f(\x)\0)\ \ \x:=\x+1,, IF f(\x)=0 THEN \found:=True ELSE SKIP FI\ OD;; - .{\I1 \ \found}. + \\I1 \ \found\ \turn:=2 - .{\I1 \ \found}. + \\I1 \ \found\ \ - .{\I2}. + \\I2\ WHILE \\found - INV .{\I2}. - DO .{\y\a+1 \ (\found \ a<\x \ f(\x)=0) \ (\y\a \ f(\y)\0)}. + INV \\I2\ + DO \\y\a+1 \ (\found \ a<\x \ f(\x)=0) \ (\y\a \ f(\y)\0)\ WAIT \turn=2 END;; - .{\y\a+1 \ (\found \ a<\x \ f(\x)=0) \ (\y\a \ f(\y)\0)}. + \\y\a+1 \ (\found \ a<\x \ f(\x)=0) \ (\y\a \ f(\y)\0)\ \turn:=1;; - .{\y\a+1 \ (\found \ a<\x \ f(\x)=0) \ (\y\a \ f(\y)\0)}. + \\y\a+1 \ (\found \ a<\x \ f(\x)=0) \ (\y\a \ f(\y)\0)\ \ \y:=(\y - 1),, IF f(\y)=0 THEN \found:=True ELSE SKIP FI\ OD;; - .{\I2 \ \found}. + \\I2 \ \found\ \turn:=1 - .{\I2 \ \found}. + \\I2 \ \found\ COEND - .{f(\x)=0 \ f(\y)=0}." + \f(\x)=0 \ f(\y)=0\" apply oghoare --{* 98 verification conditions *} apply auto @@ -306,26 +306,26 @@ \ (\\found \ a<\x \ f(\x)\0)\; I2= \\y\a+1 \ (\found \ (a<\x \ f(\x)=0) \ (\y\a \ f(\y)=0)) \ (\\found \ \y\a \ f(\y)\0)\\ \ - \- .{\u. f(u)=0}. + \- \\u. f(u)=0\ \found:= False,, \x:=a,, \y:=a+1,, - COBEGIN .{\I1}. + COBEGIN \\I1\ WHILE \\found - INV .{\I1}. - DO .{a\\x \ (\found \ \y\a \ f(\y)=0) \ (a<\x \ f(\x)\0)}. + INV \\I1\ + DO \a\\x \ (\found \ \y\a \ f(\y)=0) \ (a<\x \ f(\x)\0)\ \ \x:=\x+1,,IF f(\x)=0 THEN \found:=True ELSE SKIP FI\ OD - .{\I1 \ \found}. + \\I1 \ \found\ \ - .{\I2}. + \\I2\ WHILE \\found - INV .{\I2}. - DO .{\y\a+1 \ (\found \ a<\x \ f(\x)=0) \ (\y\a \ f(\y)\0)}. + INV \\I2\ + DO \\y\a+1 \ (\found \ a<\x \ f(\x)=0) \ (\y\a \ f(\y)\0)\ \ \y:=(\y - 1),,IF f(\y)=0 THEN \found:=True ELSE SKIP FI\ OD - .{\I2 \ \found}. + \\I2 \ \found\ COEND - .{f(\x)=0 \ f(\y)=0}." + \f(\x)=0 \ f(\y)=0\" apply oghoare --{* 20 vc *} apply auto @@ -390,44 +390,44 @@ p1= \\I1 \ \li=\ins\ ; I2 = \\I \ (\k<\lj. (a ! k)=(\b ! k)) \ \lj\length a\ ; p2 = \\I2 \ \lj=\outs\ \ \ - \- .{\INIT}. + \- \\INIT\ \ins:=0,, \outs:=0,, \li:=0,, \lj:=0,, - COBEGIN .{\p1 \ \INIT}. + COBEGIN \\p1 \ \INIT\ WHILE \li p1 \ \INIT}. - DO .{\p1 \ \INIT \ \li\p1 \ \INIT\ + DO \\p1 \ \INIT \ \li \vx:= (a ! \li);; - .{\p1 \ \INIT \ \li \vx=(a ! \li)}. + \\p1 \ \INIT \ \li \vx=(a ! \li)\ WAIT \ins-\outs < length \buffer END;; - .{\p1 \ \INIT \ \li \vx=(a ! \li) - \ \ins-\outs < length \buffer}. + \\p1 \ \INIT \ \li \vx=(a ! \li) + \ \ins-\outs < length \buffer\ \buffer:=(list_update \buffer (\ins mod (length \buffer)) \vx);; - .{\p1 \ \INIT \ \li\p1 \ \INIT \ \li (a ! \li)=(\buffer ! (\ins mod (length \buffer))) - \ \ins-\outs buffer}. + \ \ins-\outs buffer\ \ins:=\ins+1;; - .{\I1 \ \INIT \ (\li+1)=\ins \ \li\I1 \ \INIT \ (\li+1)=\ins \ \li \li:=\li+1 OD - .{\p1 \ \INIT \ \li=length a}. + \\p1 \ \INIT \ \li=length a\ \ - .{\p2 \ \INIT}. + \\p2 \ \INIT\ WHILE \lj < length a - INV .{\p2 \ \INIT}. - DO .{\p2 \ \lj \INIT}. + INV \\p2 \ \INIT\ + DO \\p2 \ \lj \INIT\ WAIT \outs<\ins END;; - .{\p2 \ \lj \outs<\ins \ \INIT}. + \\p2 \ \lj \outs<\ins \ \INIT\ \vy:=(\buffer ! (\outs mod (length \buffer)));; - .{\p2 \ \lj \outs<\ins \ \vy=(a ! \lj) \ \INIT}. + \\p2 \ \lj \outs<\ins \ \vy=(a ! \lj) \ \INIT\ \outs:=\outs+1;; - .{\I2 \ (\lj+1)=\outs \ \lj \vy=(a ! \lj) \ \INIT}. + \\I2 \ (\lj+1)=\outs \ \lj \vy=(a ! \lj) \ \INIT\ \b:=(list_update \b \lj \vy);; - .{\I2 \ (\lj+1)=\outs \ \lj (a ! \lj)=(\b ! \lj) \ \INIT}. + \\I2 \ (\lj+1)=\outs \ \lj (a ! \lj)=(\b ! \lj) \ \INIT\ \lj:=\lj+1 OD - .{\p2 \ \lj=length a \ \INIT}. + \\p2 \ \lj=length a \ \INIT\ COEND - .{ \kb ! k)}." + \ \kb ! k)\" apply oghoare --{* 138 vc *} apply(tactic {* ALLGOALS (clarify_tac @{context}) *}) @@ -455,9 +455,9 @@ a :: "nat \ nat" lemma Example1: - "\- .{True}. - COBEGIN SCHEME [0\ia:=\a (i:=0) .{\a i=0}. COEND - .{\i < n. \a i = 0}." + "\- \True\ + COBEGIN SCHEME [0\iTrue\ \a:=\a (i:=0) \\a i=0\ COEND + \\i < n. \a i = 0\" apply oghoare apply simp_all done @@ -466,11 +466,11 @@ record Example1_list = A :: "nat list" lemma Example1_list: - "\- .{n < length \A}. + "\- \n < length \A\ COBEGIN - SCHEME [0\iA}. \A:=\A[i:=0] .{\A!i=0}. + SCHEME [0\in < length \A\ \A:=\A[i:=0] \\A!i=0\ COEND - .{\i < n. \A!i = 0}." + \\i < n. \A!i = 0\" apply oghoare apply force+ done @@ -525,14 +525,14 @@ x :: nat lemma Example_2: "0 - \- .{\x=0 \ (\i=0..c i)=0}. + \- \\x=0 \ (\i=0..c i)=0\ COBEGIN SCHEME [0\ix=(\i=0..c i) \ \c i=0}. + \\x=(\i=0..c i) \ \c i=0\ \ \x:=\x+(Suc 0),, \c:=\c (i:=(Suc 0)) \ - .{\x=(\i=0..c i) \ \c i=(Suc 0)}. + \\x=(\i=0..c i) \ \c i=(Suc 0)\ COEND - .{\x=n}." + \\x=n\" apply oghoare apply (simp_all cong del: strong_setsum_cong) apply (tactic {* ALLGOALS (clarify_tac @{context}) *}) diff -r 07593a0a27f4 -r effd8fcabca2 src/HOL/Hoare_Parallel/OG_Syntax.thy --- a/src/HOL/Hoare_Parallel/OG_Syntax.thy Tue Aug 27 23:54:23 2013 +0200 +++ b/src/HOL/Hoare_Parallel/OG_Syntax.thy Wed Aug 28 00:18:50 2013 +0200 @@ -44,15 +44,15 @@ ("(0WHILE _ //DO _ /OD)" [0, 0] 61) translations - "IF b THEN c1 ELSE c2 FI" \ "CONST Cond .{b}. c1 c2" + "IF b THEN c1 ELSE c2 FI" \ "CONST Cond \b\ c1 c2" "IF b THEN c FI" \ "IF b THEN c ELSE SKIP FI" - "WHILE b INV i DO c OD" \ "CONST While .{b}. i c" + "WHILE b INV i DO c OD" \ "CONST While \b\ i c" "WHILE b DO c OD" \ "WHILE b INV CONST undefined DO c OD" - "r IF b THEN c1 ELSE c2 FI" \ "CONST AnnCond1 r .{b}. c1 c2" - "r IF b THEN c FI" \ "CONST AnnCond2 r .{b}. c" - "r WHILE b INV i DO c OD" \ "CONST AnnWhile r .{b}. i c" - "r AWAIT b THEN c END" \ "CONST AnnAwait r .{b}. c" + "r IF b THEN c1 ELSE c2 FI" \ "CONST AnnCond1 r \b\ c1 c2" + "r IF b THEN c FI" \ "CONST AnnCond2 r \b\ c" + "r WHILE b INV i DO c OD" \ "CONST AnnWhile r \b\ i c" + "r AWAIT b THEN c END" \ "CONST AnnAwait r \b\ c" "r \c\" \ "r AWAIT CONST True THEN c END" "r WAIT b END" \ "r AWAIT b THEN SKIP END" diff -r 07593a0a27f4 -r effd8fcabca2 src/HOL/Hoare_Parallel/Quote_Antiquote.thy --- a/src/HOL/Hoare_Parallel/Quote_Antiquote.thy Tue Aug 27 23:54:23 2013 +0200 +++ b/src/HOL/Hoare_Parallel/Quote_Antiquote.thy Wed Aug 28 00:18:50 2013 +0200 @@ -6,13 +6,10 @@ syntax "_quote" :: "'b \ ('a \ 'b)" ("(\_\)" [0] 1000) "_antiquote" :: "('a \ 'b) \ 'b" ("\_" [1000] 1000) - "_Assert" :: "'a \ 'a set" ("(.{_}.)" [0] 1000) - -syntax (xsymbols) - "_Assert" :: "'a \ 'a set" ("(\_\)" [0] 1000) + "_Assert" :: "'a \ 'a set" ("(\_\)" [0] 1000) translations - ".{b}." \ "CONST Collect \b\" + "\b\" \ "CONST Collect \b\" parse_translation {* let diff -r 07593a0a27f4 -r effd8fcabca2 src/HOL/Hoare_Parallel/RG_Syntax.thy --- a/src/HOL/Hoare_Parallel/RG_Syntax.thy Tue Aug 27 23:54:23 2013 +0200 +++ b/src/HOL/Hoare_Parallel/RG_Syntax.thy Wed Aug 28 00:18:50 2013 +0200 @@ -20,10 +20,10 @@ translations "\x := a" \ "CONST Basic \\(_update_name x (\_. a))\" - "IF b THEN c1 ELSE c2 FI" \ "CONST Cond .{b}. c1 c2" + "IF b THEN c1 ELSE c2 FI" \ "CONST Cond \b\ c1 c2" "IF b THEN c FI" \ "IF b THEN c ELSE SKIP FI" - "WHILE b DO c OD" \ "CONST While .{b}. c" - "AWAIT b THEN c END" \ "CONST Await .{b}. c" + "WHILE b DO c OD" \ "CONST While \b\ c" + "AWAIT b THEN c END" \ "CONST Await \b\ c" "\c\" \ "AWAIT CONST True THEN c END" "WAIT b END" \ "AWAIT b THEN SKIP END"