src/HOL/Hoare/Hoare.ML
changeset 3842 b55686a7b22c
parent 3537 79ac9b475621
child 4089 96fba19bcbe2
equal deleted inserted replaced
3841:22bbc1676768 3842:b55686a7b22c
     9 open Hoare;
     9 open Hoare;
    10 
    10 
    11 (*** Hoare rules ***)
    11 (*** Hoare rules ***)
    12 
    12 
    13 val SkipRule = prove_goalw thy [Spec_def,Skip_def]
    13 val SkipRule = prove_goalw thy [Spec_def,Skip_def]
    14   "(!!s.p(s) ==> q(s)) ==> Spec p Skip q"
    14   "(!!s. p(s) ==> q(s)) ==> Spec p Skip q"
    15   (fn prems => [fast_tac (!claset addIs prems) 1]);
    15   (fn prems => [fast_tac (!claset addIs prems) 1]);
    16 
    16 
    17 val AssignRule = prove_goalw thy [Spec_def,Assign_def]
    17 val AssignRule = prove_goalw thy [Spec_def,Assign_def]
    18   "(!!s. p s ==> q(%x.if x=v then e s else s x)) ==> Spec p (Assign v e) q"
    18   "(!!s. p s ==> q(%x. if x=v then e s else s x)) ==> Spec p (Assign v e) q"
    19   (fn prems => [fast_tac (!claset addIs prems) 1]);
    19   (fn prems => [fast_tac (!claset addIs prems) 1]);
    20 
    20 
    21 val SeqRule = prove_goalw thy [Spec_def,Seq_def]
    21 val SeqRule = prove_goalw thy [Spec_def,Seq_def]
    22   "[| Spec p c (%s.q s); Spec (%s.q s) c' r |] ==> Spec p (Seq c c') r"
    22   "[| Spec p c (%s. q s); Spec (%s. q s) c' r |] ==> Spec p (Seq c c') r"
    23   (fn prems => [cut_facts_tac prems 1, Fast_tac 1]);
    23   (fn prems => [cut_facts_tac prems 1, Fast_tac 1]);
    24 
    24 
    25 val IfRule = prove_goalw thy [Spec_def,Cond_def]
    25 val IfRule = prove_goalw thy [Spec_def,Cond_def]
    26   "[| !!s. p s ==> (b s --> q s) & (~b s --> q' s); \
    26   "[| !!s. p s ==> (b s --> q s) & (~b s --> q' s); \
    27 \     Spec (%s.q s) c r; Spec (%s.q' s) c' r |] \
    27 \     Spec (%s. q s) c r; Spec (%s. q' s) c' r |] \
    28 \  ==> Spec p (Cond b c c') r"
    28 \  ==> Spec p (Cond b c c') r"
    29   (fn [prem1,prem2,prem3] =>
    29   (fn [prem1,prem2,prem3] =>
    30      [REPEAT (rtac allI 1),
    30      [REPEAT (rtac allI 1),
    31       REPEAT (rtac impI 1),
    31       REPEAT (rtac impI 1),
    32       dtac prem1 1,
    32       dtac prem1 1,
    37   "[| !!s. p s ==> p' s; Spec p' c q |] ==> Spec p c q"
    37   "[| !!s. p s ==> p' s; Spec p' c q |] ==> Spec p c q"
    38   (fn [prem1,prem2] =>[cut_facts_tac [prem2] 1,
    38   (fn [prem1,prem2] =>[cut_facts_tac [prem2] 1,
    39                        fast_tac (!claset addIs [prem1]) 1]);
    39                        fast_tac (!claset addIs [prem1]) 1]);
    40 
    40 
    41 val lemma = prove_goalw thy [Spec_def,While_def]
    41 val lemma = prove_goalw thy [Spec_def,While_def]
    42   "[| Spec (%s.I s & b s) c I; !!s. [| I s; ~b s |] ==> q s |] \
    42   "[| Spec (%s. I s & b s) c I; !!s. [| I s; ~b s |] ==> q s |] \
    43 \  ==> Spec I (While b I c) q"
    43 \  ==> Spec I (While b I c) q"
    44   (fn [prem1,prem2] =>
    44   (fn [prem1,prem2] =>
    45      [REPEAT(rtac allI 1), rtac impI 1, etac exE 1, rtac mp 1, atac 2,
    45      [REPEAT(rtac allI 1), rtac impI 1, etac exE 1, rtac mp 1, atac 2,
    46       etac thin_rl 1, res_inst_tac[("x","s")]spec 1,
    46       etac thin_rl 1, res_inst_tac[("x","s")]spec 1,
    47       res_inst_tac[("x","s'")]spec 1, nat_ind_tac "n" 1,
    47       res_inst_tac[("x","s'")]spec 1, nat_ind_tac "n" 1,
   132 
   132 
   133 
   133 
   134 (* VarsElimTac: Taktik zum Eliminieren von bestimmten Programmvariablen aus dem Subgoal i
   134 (* VarsElimTac: Taktik zum Eliminieren von bestimmten Programmvariablen aus dem Subgoal i
   135  - v::vl:(term) list  Liste der zu eliminierenden Programmvariablen
   135  - v::vl:(term) list  Liste der zu eliminierenden Programmvariablen
   136  - meta_spec:thm      Theorem, welches zur Entfernung der Variablen benutzt wird
   136  - meta_spec:thm      Theorem, welches zur Entfernung der Variablen benutzt wird
   137 		      z.B.: "(!!s x.PROP P(s,x)) ==> (!!s.PROP P(s,x(s)))"
   137 		      z.B.: "(!!s x. PROP P(s,x)) ==> (!!s. PROP P(s,x(s)))"
   138  - namexAll:string    Name von    ^                                  (hier "x")
   138  - namexAll:string    Name von    ^                                  (hier "x")
   139  - varx:term          Term zu                                      ^ (hier Var(("x",0),...))
   139  - varx:term          Term zu                                      ^ (hier Var(("x",0),...))
   140  - varP:term          Term zu                                  ^     (hier Var(("P",0),...))
   140  - varP:term          Term zu                                  ^     (hier Var(("P",0),...))
   141  - type_pvar:typ      Typ der Programmvariablen (d.h. 'a bei 'a prog, z.B.: nat, bool, ...)
   141  - type_pvar:typ      Typ der Programmvariablen (d.h. 'a bei 'a prog, z.B.: nat, bool, ...)
   142 
   142 
   143  Vorgehen:
   143  Vorgehen:
   144       - eliminiere jede pvar durch Anwendung von comp_inst_ren_tac. Dazu:
   144       - eliminiere jede pvar durch Anwendung von comp_inst_ren_tac. Dazu:
   145       - Unbenennung in meta_spec: namexAll wird in den Namen der Prog.-Var. umbenannt
   145       - Unbenennung in meta_spec: namexAll wird in den Namen der Prog.-Var. umbenannt
   146 	z.B.: fuer die Prog.-Var. mit Namen "a" ergibt sich
   146 	z.B.: fuer die Prog.-Var. mit Namen "a" ergibt sich
   147 	      meta_spec zu "(!! s a.PROP P(s,a)) ==> (!! s.PROP P(s,x(s)))"
   147 	      meta_spec zu "(!! s a. PROP P(s,a)) ==> (!! s. PROP P(s,x(s)))"
   148       - Instanziierungen in meta_spec:
   148       - Instanziierungen in meta_spec:
   149 	      varx wird mit "%s:(type_pvar) state.s(pvar)" instanziiert
   149 	      varx wird mit "%s:(type_pvar) state. s(pvar)" instanziiert
   150 	      varP wird entsprechend instanziiert. Beispiel fuer Prog.-Var. "a":
   150 	      varP wird entsprechend instanziiert. Beispiel fuer Prog.-Var. "a":
   151 	 - zu Subgoal "!!s.s(Suc(0)) = s(0) ==> s(0) = 1" bestimme Term ohne "!!s.":
   151 	 - zu Subgoal "!!s. s(Suc(0)) = s(0) ==> s(0) = 1" bestimme Term ohne "!!s.":
   152 		trm0 = "s(Suc(0)) = s(0) ==> s(0) = 1" (s ist hier freie Variable)
   152 		trm0 = "s(Suc(0)) = s(0) ==> s(0) = 1" (s ist hier freie Variable)
   153 	 - substituiere alle Vorkommen von s(pvar) durch eine freie Var. xs:
   153 	 - substituiere alle Vorkommen von s(pvar) durch eine freie Var. xs:
   154 		trm1 = "s(Suc(0)) = xs ==> xs = 1"
   154 		trm1 = "s(Suc(0)) = xs ==> xs = 1"
   155 	 - abstrahiere ueber xs:
   155 	 - abstrahiere ueber xs:
   156 		trm2 = "%xs.s(Suc(0)) = xs ==> xs = 1"
   156 		trm2 = "%xs. s(Suc(0)) = xs ==> xs = 1"
   157 	 - abstrahiere ueber restliche Vorkommen von s:
   157 	 - abstrahiere ueber restliche Vorkommen von s:
   158 		trm3 = "%s xs.s(Suc(0)) = xs ==> xs = 1"
   158 		trm3 = "%s xs. s(Suc(0)) = xs ==> xs = 1"
   159 	 - instanziiere varP mit trm3
   159 	 - instanziiere varP mit trm3
   160 *)
   160 *)
   161 
   161 
   162 (* StateElimTac: tactic to eliminate all program variable from subgoal i
   162 (* StateElimTac: tactic to eliminate all program variable from subgoal i
   163     - applies to subgoals of the form "!!s:('a) state.P(s)",
   163     - applies to subgoals of the form "!!s:('a) state. P(s)",
   164         i.e. the term  Const("all",_) $ Abs ("s",pvar --> 'a,_)
   164         i.e. the term  Const("all",_) $ Abs ("s",pvar --> 'a,_)
   165     -   meta_spec has the form "(!!s x.PROP P(s,x)) ==> (!!s.PROP P(s,x(s)))"
   165     -   meta_spec has the form "(!!s x. PROP P(s,x)) ==> (!!s. PROP P(s,x(s)))"
   166 *)
   166 *)
   167 
   167 
   168 val StateElimTac = SUBGOAL (fn (Bi,i) =>
   168 val StateElimTac = SUBGOAL (fn (Bi,i) =>
   169   let val Const _ $ Abs (_,Type ("fun",[_,type_pvar]),trm) = Bi
   169   let val Const _ $ Abs (_,Type ("fun",[_,type_pvar]),trm) = Bi
   170       val _ $ (_ $ Abs (_,_,_ $ Abs (namexAll,_,_))) $
   170       val _ $ (_ $ Abs (_,_,_ $ Abs (namexAll,_,_))) $