1465
|
1 |
(* Title: HOL/IMP/Hoare.ML
|
938
|
2 |
ID: $Id$
|
1465
|
3 |
Author: Tobias Nipkow
|
936
|
4 |
Copyright 1995 TUM
|
|
5 |
|
1481
|
6 |
Soundness (and part of) relative completeness of Hoare rules
|
|
7 |
wrt denotational semantics
|
936
|
8 |
*)
|
|
9 |
|
|
10 |
open Hoare;
|
|
11 |
|
1486
|
12 |
goalw Hoare.thy [hoare_valid_def] "!P c Q. |- {P}c{Q} --> |= {P}c{Q}";
|
1465
|
13 |
by (rtac hoare.mutual_induct 1);
|
1447
|
14 |
by(ALLGOALS Asm_simp_tac);
|
|
15 |
by(fast_tac rel_cs 1);
|
|
16 |
by(fast_tac HOL_cs 1);
|
1465
|
17 |
by (rtac allI 1);
|
|
18 |
by (rtac allI 1);
|
|
19 |
by (rtac impI 1);
|
|
20 |
by (etac induct2 1);
|
1447
|
21 |
br Gamma_mono 1;
|
1465
|
22 |
by (rewtac Gamma_def);
|
936
|
23 |
by(eres_inst_tac [("x","a")] allE 1);
|
|
24 |
by (safe_tac comp_cs);
|
1447
|
25 |
by(ALLGOALS Asm_full_simp_tac);
|
1486
|
26 |
qed_spec_mp "hoare_sound";
|
936
|
27 |
|
1481
|
28 |
goalw Hoare.thy [swp_def] "swp Skip Q = Q";
|
|
29 |
by(Simp_tac 1);
|
|
30 |
br ext 1;
|
|
31 |
by(fast_tac HOL_cs 1);
|
|
32 |
qed "swp_Skip";
|
|
33 |
|
|
34 |
goalw Hoare.thy [swp_def] "swp (x:=a) Q = (%s.Q(s[A a s/x]))";
|
|
35 |
by(Simp_tac 1);
|
|
36 |
br ext 1;
|
|
37 |
by(fast_tac HOL_cs 1);
|
|
38 |
qed "swp_Ass";
|
|
39 |
|
|
40 |
goalw Hoare.thy [swp_def] "swp (c;d) Q = swp c (swp d Q)";
|
|
41 |
by(Simp_tac 1);
|
|
42 |
br ext 1;
|
|
43 |
by(fast_tac comp_cs 1);
|
|
44 |
qed "swp_Semi";
|
936
|
45 |
|
1481
|
46 |
goalw Hoare.thy [swp_def]
|
|
47 |
"swp (IF b THEN c ELSE d) Q = (%s. (B b s --> swp c Q s) & \
|
|
48 |
\ (~B b s --> swp d Q s))";
|
|
49 |
by(Simp_tac 1);
|
|
50 |
br ext 1;
|
|
51 |
by(fast_tac comp_cs 1);
|
|
52 |
qed "swp_If";
|
936
|
53 |
|
1481
|
54 |
goalw Hoare.thy [swp_def]
|
|
55 |
"!!s. B b s ==> swp (WHILE b DO c) Q s = swp (c;WHILE b DO c) Q s";
|
|
56 |
by(stac C_While_If 1);
|
|
57 |
by(Asm_simp_tac 1);
|
|
58 |
qed "swp_While_True";
|
|
59 |
|
|
60 |
goalw Hoare.thy [swp_def] "!!s. ~B b s ==> swp (WHILE b DO c) Q s = Q s";
|
|
61 |
by(stac C_While_If 1);
|
|
62 |
by(Asm_simp_tac 1);
|
|
63 |
by(fast_tac HOL_cs 1);
|
|
64 |
qed "swp_While_False";
|
|
65 |
|
|
66 |
Addsimps [swp_Skip,swp_Ass,swp_Semi,swp_If,swp_While_True,swp_While_False];
|
|
67 |
|
|
68 |
Delsimps [C_while];
|
936
|
69 |
|
1481
|
70 |
goalw Hoare.thy [hoare_valid_def,swp_def]
|
1486
|
71 |
"!!c. |= {P}c{Q} ==> !s. P s --> swp c Q s";
|
1481
|
72 |
by(fast_tac HOL_cs 1);
|
|
73 |
qed "swp_is_weakest";
|
|
74 |
|
1486
|
75 |
goal Hoare.thy "!Q. |- {swp c Q} c {Q}";
|
1481
|
76 |
by(com.induct_tac "c" 1);
|
|
77 |
by(ALLGOALS Simp_tac);
|
|
78 |
by(fast_tac (HOL_cs addIs [hoare.skip]) 1);
|
|
79 |
by(fast_tac (HOL_cs addIs [hoare.ass]) 1);
|
|
80 |
by(fast_tac (HOL_cs addIs [hoare.semi]) 1);
|
|
81 |
by(safe_tac (HOL_cs addSIs [hoare.If]));
|
|
82 |
br hoare.conseq 1;
|
|
83 |
by(fast_tac HOL_cs 2);
|
|
84 |
by(fast_tac HOL_cs 2);
|
|
85 |
by(fast_tac HOL_cs 1);
|
|
86 |
br hoare.conseq 1;
|
|
87 |
by(fast_tac HOL_cs 2);
|
|
88 |
by(fast_tac HOL_cs 2);
|
|
89 |
by(fast_tac HOL_cs 1);
|
|
90 |
br hoare.conseq 1;
|
|
91 |
br hoare.While 2;
|
|
92 |
be thin_rl 1;
|
|
93 |
by(fast_tac HOL_cs 1);
|
|
94 |
br hoare.conseq 1;
|
|
95 |
be thin_rl 3;
|
|
96 |
br allI 3;
|
|
97 |
br impI 3;
|
|
98 |
ba 3;
|
|
99 |
by(fast_tac HOL_cs 2);
|
|
100 |
by(safe_tac HOL_cs);
|
|
101 |
by(rotate_tac ~1 1);
|
|
102 |
by(Asm_full_simp_tac 1);
|
|
103 |
by(rotate_tac ~1 1);
|
|
104 |
by(Asm_full_simp_tac 1);
|
1486
|
105 |
qed_spec_mp "swp_is_pre";
|
1481
|
106 |
|
1486
|
107 |
goal Hoare.thy "!!c. |= {P}c{Q} ==> |- {P}c{Q}";
|
1481
|
108 |
br (swp_is_pre RSN (2,hoare.conseq)) 1;
|
|
109 |
by(fast_tac HOL_cs 2);
|
|
110 |
be swp_is_weakest 1;
|
|
111 |
qed "hoare_relative_complete";
|