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,_,_))) $ |