src/HOL/Hoare/Hoare.thy
changeset 35054 a5db9779b026
parent 32149 ef59550a55d3
child 35113 1a0c129bb2e0
equal deleted inserted replaced
35053:43175817d83b 35054:a5db9779b026
    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"