22 'a com = Basic "'a \<Rightarrow> 'a" |
22 'a com = Basic "'a \<Rightarrow> 'a" |
23 | Seq "'a com" "'a com" ("(_;/ _)" [61,60] 60) |
23 | Seq "'a com" "'a com" ("(_;/ _)" [61,60] 60) |
24 | Cond "'a bexp" "'a com" "'a com" ("(1IF _/ THEN _ / ELSE _/ FI)" [0,0,0] 61) |
24 | Cond "'a bexp" "'a com" "'a com" ("(1IF _/ THEN _ / ELSE _/ FI)" [0,0,0] 61) |
25 | While "'a bexp" "'a assn" "'a com" ("(1WHILE _/ INV {_} //DO _ /OD)" [0,0,0] 61) |
25 | While "'a bexp" "'a assn" "'a com" ("(1WHILE _/ INV {_} //DO _ /OD)" [0,0,0] 61) |
26 |
26 |
27 syntax |
27 abbreviation annskip ("SKIP") where "SKIP == Basic id" |
28 "@assign" :: "id => 'b => 'a com" ("(2_ :=/ _)" [70,65] 61) |
|
29 "@annskip" :: "'a com" ("SKIP") |
|
30 |
|
31 translations |
|
32 "SKIP" == "Basic id" |
|
33 |
28 |
34 types 'a sem = "'a => 'a => bool" |
29 types 'a sem = "'a => 'a => bool" |
35 |
30 |
36 consts iter :: "nat => 'a bexp => 'a sem => 'a sem" |
31 consts iter :: "nat => 'a bexp => 'a sem => 'a sem" |
37 primrec |
32 primrec |
48 |
43 |
49 constdefs Valid :: "'a bexp \<Rightarrow> 'a com \<Rightarrow> 'a bexp \<Rightarrow> bool" |
44 constdefs Valid :: "'a bexp \<Rightarrow> 'a com \<Rightarrow> 'a bexp \<Rightarrow> bool" |
50 "Valid p c q == !s s'. Sem c s s' --> s : p --> s' : q" |
45 "Valid p c q == !s s'. Sem c s s' --> s : p --> s' : q" |
51 |
46 |
52 |
47 |
|
48 |
|
49 (** parse translations **) |
|
50 |
53 syntax |
51 syntax |
54 "@hoare_vars" :: "[idts, 'a assn,'a com,'a assn] => bool" |
52 "_assign" :: "id => 'b => 'a com" ("(2_ :=/ _)" [70,65] 61) |
|
53 |
|
54 syntax |
|
55 "_hoare_vars" :: "[idts, 'a assn,'a com,'a assn] => bool" |
55 ("VARS _// {_} // _ // {_}" [0,0,55,0] 50) |
56 ("VARS _// {_} // _ // {_}" [0,0,55,0] 50) |
56 syntax ("" output) |
57 syntax ("" output) |
57 "@hoare" :: "['a assn,'a com,'a assn] => bool" |
58 "_hoare" :: "['a assn,'a com,'a assn] => bool" |
58 ("{_} // _ // {_}" [0,55,0] 50) |
59 ("{_} // _ // {_}" [0,55,0] 50) |
59 |
60 ML {* |
60 (** parse translations **) |
|
61 |
|
62 ML{* |
|
63 |
61 |
64 local |
62 local |
65 |
63 |
66 fun abs((a,T),body) = |
64 fun abs((a,T),body) = |
67 let val a = absfree(a, dummyT, body) |
65 let val a = absfree(a, dummyT, body) |
89 |
87 |
90 fun assn_tr r xs = Syntax.const "Collect" $ mk_abstuple xs r; |
88 fun assn_tr r xs = Syntax.const "Collect" $ mk_abstuple xs r; |
91 *} |
89 *} |
92 (* com_tr *) |
90 (* com_tr *) |
93 ML{* |
91 ML{* |
94 fun com_tr (Const("@assign",_) $ Free (a,_) $ e) xs = |
92 fun com_tr (Const("_assign",_) $ Free (a,_) $ e) xs = |
95 Syntax.const "Basic" $ mk_fexp a e xs |
93 Syntax.const "Basic" $ mk_fexp a e xs |
96 | com_tr (Const ("Basic",_) $ f) xs = Syntax.const "Basic" $ f |
94 | com_tr (Const ("Basic",_) $ f) xs = Syntax.const "Basic" $ f |
97 | com_tr (Const ("Seq",_) $ c1 $ c2) xs = |
95 | com_tr (Const ("Seq",_) $ c1 $ c2) xs = |
98 Syntax.const "Seq" $ com_tr c1 xs $ com_tr c2 xs |
96 Syntax.const "Seq" $ com_tr c1 xs $ com_tr c2 xs |
99 | com_tr (Const ("Cond",_) $ b $ c1 $ c2) xs = |
97 | com_tr (Const ("Cond",_) $ b $ c1 $ c2) xs = |
121 end |
119 end |
122 | hoare_vars_tr ts = raise TERM ("hoare_vars_tr", ts); |
120 | hoare_vars_tr ts = raise TERM ("hoare_vars_tr", ts); |
123 end |
121 end |
124 *} |
122 *} |
125 |
123 |
126 parse_translation {* [("@hoare_vars", hoare_vars_tr)] *} |
124 parse_translation {* [("_hoare_vars", hoare_vars_tr)] *} |
127 |
125 |
128 |
126 |
129 (*****************************************************************************) |
127 (*****************************************************************************) |
130 |
128 |
131 (*** print translations ***) |
129 (*** print translations ***) |
173 (*com_tr' *) |
171 (*com_tr' *) |
174 ML{* |
172 ML{* |
175 fun mk_assign f = |
173 fun mk_assign f = |
176 let val (vs, ts) = mk_vts f; |
174 let val (vs, ts) = mk_vts f; |
177 val (ch, which) = find_ch (vs~~ts) ((length vs)-1) (rev vs) |
175 val (ch, which) = find_ch (vs~~ts) ((length vs)-1) (rev vs) |
178 in if ch then Syntax.const "@assign" $ fst(which) $ snd(which) |
176 in if ch then Syntax.const "_assign" $ fst(which) $ snd(which) |
179 else Syntax.const "@skip" end; |
177 else Syntax.const @{const_syntax annskip} end; |
180 |
178 |
181 fun com_tr' (Const ("Basic",_) $ f) = if is_f f then mk_assign f |
179 fun com_tr' (Const ("Basic",_) $ f) = if is_f f then mk_assign f |
182 else Syntax.const "Basic" $ f |
180 else Syntax.const "Basic" $ f |
183 | com_tr' (Const ("Seq",_) $ c1 $ c2) = Syntax.const "Seq" $ |
181 | com_tr' (Const ("Seq",_) $ c1 $ c2) = Syntax.const "Seq" $ |
184 com_tr' c1 $ com_tr' c2 |
182 com_tr' c1 $ com_tr' c2 |
188 bexp_tr' b $ assn_tr' I $ com_tr' c |
186 bexp_tr' b $ assn_tr' I $ com_tr' c |
189 | com_tr' t = t; |
187 | com_tr' t = t; |
190 |
188 |
191 |
189 |
192 fun spec_tr' [p, c, q] = |
190 fun spec_tr' [p, c, q] = |
193 Syntax.const "@hoare" $ assn_tr' p $ com_tr' c $ assn_tr' q |
191 Syntax.const "_hoare" $ assn_tr' p $ com_tr' c $ assn_tr' q |
194 *} |
192 *} |
195 |
193 |
196 print_translation {* [("Valid", spec_tr')] *} |
194 print_translation {* [(@{const_syntax Valid}, spec_tr')] *} |
197 |
195 |
198 lemma SkipRule: "p \<subseteq> q \<Longrightarrow> Valid p (Basic id) q" |
196 lemma SkipRule: "p \<subseteq> q \<Longrightarrow> Valid p (Basic id) q" |
199 by (auto simp:Valid_def) |
197 by (auto simp:Valid_def) |
200 |
198 |
201 lemma BasicRule: "p \<subseteq> {s. f s \<in> q} \<Longrightarrow> Valid p (Basic f) q" |
199 lemma BasicRule: "p \<subseteq> {s. f s \<in> q} \<Longrightarrow> Valid p (Basic f) q" |