1 (* Title: HOL/IMP/VC.thy |
|
2 Author: Tobias Nipkow |
|
3 |
|
4 acom: annotated commands |
|
5 vc: verification-conditions |
|
6 awp: weakest (liberal) precondition |
|
7 *) |
|
8 |
|
9 header "Verification Conditions" |
|
10 |
|
11 theory VC imports Hoare_Op begin |
|
12 |
|
13 datatype acom = Askip |
|
14 | Aass loc aexp |
|
15 | Asemi acom acom |
|
16 | Aif bexp acom acom |
|
17 | Awhile bexp assn acom |
|
18 |
|
19 primrec awp :: "acom => assn => assn" |
|
20 where |
|
21 "awp Askip Q = Q" |
|
22 | "awp (Aass x a) Q = (\<lambda>s. Q(s[x\<mapsto>a s]))" |
|
23 | "awp (Asemi c d) Q = awp c (awp d Q)" |
|
24 | "awp (Aif b c d) Q = (\<lambda>s. (b s-->awp c Q s) & (~b s-->awp d Q s))" |
|
25 | "awp (Awhile b I c) Q = I" |
|
26 |
|
27 primrec vc :: "acom => assn => assn" |
|
28 where |
|
29 "vc Askip Q = (\<lambda>s. True)" |
|
30 | "vc (Aass x a) Q = (\<lambda>s. True)" |
|
31 | "vc (Asemi c d) Q = (\<lambda>s. vc c (awp d Q) s & vc d Q s)" |
|
32 | "vc (Aif b c d) Q = (\<lambda>s. vc c Q s & vc d Q s)" |
|
33 | "vc (Awhile b I c) Q = (\<lambda>s. (I s & ~b s --> Q s) & |
|
34 (I s & b s --> awp c I s) & vc c I s)" |
|
35 |
|
36 primrec astrip :: "acom => com" |
|
37 where |
|
38 "astrip Askip = SKIP" |
|
39 | "astrip (Aass x a) = (x:==a)" |
|
40 | "astrip (Asemi c d) = (astrip c;astrip d)" |
|
41 | "astrip (Aif b c d) = (\<IF> b \<THEN> astrip c \<ELSE> astrip d)" |
|
42 | "astrip (Awhile b I c) = (\<WHILE> b \<DO> astrip c)" |
|
43 |
|
44 (* simultaneous computation of vc and awp: *) |
|
45 primrec vcawp :: "acom => assn => assn \<times> assn" |
|
46 where |
|
47 "vcawp Askip Q = (\<lambda>s. True, Q)" |
|
48 | "vcawp (Aass x a) Q = (\<lambda>s. True, \<lambda>s. Q(s[x\<mapsto>a s]))" |
|
49 | "vcawp (Asemi c d) Q = (let (vcd,wpd) = vcawp d Q; |
|
50 (vcc,wpc) = vcawp c wpd |
|
51 in (\<lambda>s. vcc s & vcd s, wpc))" |
|
52 | "vcawp (Aif b c d) Q = (let (vcd,wpd) = vcawp d Q; |
|
53 (vcc,wpc) = vcawp c Q |
|
54 in (\<lambda>s. vcc s & vcd s, |
|
55 \<lambda>s.(b s --> wpc s) & (~b s --> wpd s)))" |
|
56 | "vcawp (Awhile b I c) Q = (let (vcc,wpc) = vcawp c I |
|
57 in (\<lambda>s. (I s & ~b s --> Q s) & |
|
58 (I s & b s --> wpc s) & vcc s, I))" |
|
59 |
|
60 (* |
|
61 Soundness and completeness of vc |
|
62 *) |
|
63 |
|
64 declare hoare.conseq [intro] |
|
65 |
|
66 |
|
67 lemma vc_sound: "(ALL s. vc c Q s) \<Longrightarrow> |- {awp c Q} astrip c {Q}" |
|
68 proof(induct c arbitrary: Q) |
|
69 case (Awhile b I c) |
|
70 show ?case |
|
71 proof(simp, rule While') |
|
72 from `\<forall>s. vc (Awhile b I c) Q s` |
|
73 have vc: "ALL s. vc c I s" and IQ: "ALL s. I s \<and> \<not> b s \<longrightarrow> Q s" and |
|
74 awp: "ALL s. I s & b s --> awp c I s" by simp_all |
|
75 from vc have "|- {awp c I} astrip c {I}" using Awhile.hyps by blast |
|
76 with awp show "|- {\<lambda>s. I s \<and> b s} astrip c {I}" |
|
77 by(rule strengthen_pre) |
|
78 show "\<forall>s. I s \<and> \<not> b s \<longrightarrow> Q s" by(rule IQ) |
|
79 qed |
|
80 qed auto |
|
81 |
|
82 |
|
83 lemma awp_mono: |
|
84 "(!s. P s --> Q s) ==> awp c P s ==> awp c Q s" |
|
85 proof (induct c arbitrary: P Q s) |
|
86 case Asemi thus ?case by simp metis |
|
87 qed simp_all |
|
88 |
|
89 lemma vc_mono: |
|
90 "(!s. P s --> Q s) ==> vc c P s ==> vc c Q s" |
|
91 proof(induct c arbitrary: P Q) |
|
92 case Asemi thus ?case by simp (metis awp_mono) |
|
93 qed simp_all |
|
94 |
|
95 lemma vc_complete: assumes der: "|- {P}c{Q}" |
|
96 shows "(\<exists>ac. astrip ac = c & (\<forall>s. vc ac Q s) & (\<forall>s. P s --> awp ac Q s))" |
|
97 (is "? ac. ?Eq P c Q ac") |
|
98 using der |
|
99 proof induct |
|
100 case skip |
|
101 show ?case (is "? ac. ?C ac") |
|
102 proof show "?C Askip" by simp qed |
|
103 next |
|
104 case (ass P x a) |
|
105 show ?case (is "? ac. ?C ac") |
|
106 proof show "?C(Aass x a)" by simp qed |
|
107 next |
|
108 case (semi P c1 Q c2 R) |
|
109 from semi.hyps obtain ac1 where ih1: "?Eq P c1 Q ac1" by fast |
|
110 from semi.hyps obtain ac2 where ih2: "?Eq Q c2 R ac2" by fast |
|
111 show ?case (is "? ac. ?C ac") |
|
112 proof |
|
113 show "?C(Asemi ac1 ac2)" |
|
114 using ih1 ih2 by simp (fast elim!: awp_mono vc_mono) |
|
115 qed |
|
116 next |
|
117 case (If P b c1 Q c2) |
|
118 from If.hyps obtain ac1 where ih1: "?Eq (%s. P s & b s) c1 Q ac1" by fast |
|
119 from If.hyps obtain ac2 where ih2: "?Eq (%s. P s & ~b s) c2 Q ac2" by fast |
|
120 show ?case (is "? ac. ?C ac") |
|
121 proof |
|
122 show "?C(Aif b ac1 ac2)" |
|
123 using ih1 ih2 by simp |
|
124 qed |
|
125 next |
|
126 case (While P b c) |
|
127 from While.hyps obtain ac where ih: "?Eq (%s. P s & b s) c P ac" by fast |
|
128 show ?case (is "? ac. ?C ac") |
|
129 proof show "?C(Awhile b P ac)" using ih by simp qed |
|
130 next |
|
131 case conseq thus ?case by(fast elim!: awp_mono vc_mono) |
|
132 qed |
|
133 |
|
134 lemma vcawp_vc_awp: "vcawp c Q = (vc c Q, awp c Q)" |
|
135 by (induct c arbitrary: Q) (simp_all add: Let_def) |
|
136 |
|
137 end |
|