author | nipkow |
Mon, 13 Mar 2000 12:51:10 +0100 | |
changeset 8423 | 3c19160b6432 |
parent 7322 | d16d7ddcc842 |
child 8442 | 96023903c2df |
permissions | -rw-r--r-- |
1465 | 1 |
(* Title: HOL/Hoare/Examples.thy |
1335 | 2 |
ID: $Id$ |
5646 | 3 |
Author: Norbert Galm & Tobias Nipkow |
4 |
Copyright 1998 TUM |
|
1335 | 5 |
*) |
6 |
||
5646 | 7 |
(*** ARITHMETIC ***) |
1335 | 8 |
|
6802 | 9 |
(** multiplication by successive addition **) |
1335 | 10 |
|
5646 | 11 |
Goal "|- VARS m s. \ |
12 |
\ {m=0 & s=0} \ |
|
13 |
\ WHILE m~=a \ |
|
14 |
\ INV {s=m*b} \ |
|
15 |
\ DO s := s+b; m := m+1 OD \ |
|
16 |
\ {s = a*b}"; |
|
6162 | 17 |
by (hoare_tac (Asm_full_simp_tac) 1); |
1335 | 18 |
qed "multiply_by_add"; |
19 |
||
6802 | 20 |
(** Euclid's algorithm for GCD **) |
1335 | 21 |
|
5646 | 22 |
Goal "|- VARS a b. \ |
23 |
\ {0<A & 0<B & a=A & b=B} \ |
|
24 |
\ WHILE a~=b \ |
|
25 |
\ INV {0<a & 0<b & gcd A B = gcd a b} \ |
|
26 |
\ DO IF a<b THEN b := b-a ELSE a := a-b FI OD \ |
|
1335 | 27 |
\ {a = gcd A B}"; |
5646 | 28 |
by (hoare_tac (K all_tac) 1); |
1335 | 29 |
|
3372
6e472c8f0011
Replacement of "divides" by "dvd" from Divides.thy, and updating of proofs
paulson
parents:
2031
diff
changeset
|
30 |
(*Now prove the verification conditions*) |
5338 | 31 |
by Auto_tac; |
32 |
by (etac gcd_nnn 4); |
|
33 |
by (asm_full_simp_tac (simpset() addsimps [not_less_iff_le, gcd_diff_l]) 3); |
|
34 |
by (force_tac (claset(), |
|
5646 | 35 |
simpset() addsimps [not_less_iff_le, le_eq_less_or_eq]) 2); |
36 |
by (asm_simp_tac (simpset() addsimps [gcd_diff_r,less_imp_le]) 1); |
|
1335 | 37 |
qed "Euclid_GCD"; |
38 |
||
6802 | 39 |
(** Power by iterated squaring and multiplication **) |
1335 | 40 |
|
5646 | 41 |
Goal "|- VARS a b c. \ |
42 |
\ {a=A & b=B} \ |
|
43 |
\ c := 1; \ |
|
44 |
\ WHILE b ~= 0 \ |
|
45 |
\ INV {A^B = c * a^b} \ |
|
46 |
\ DO WHILE b mod 2 = 0 \ |
|
47 |
\ INV {A^B = c * a^b} \ |
|
48 |
\ DO a := a*a; b := b div 2 OD; \ |
|
49 |
\ c := c*a; b := b-1 \ |
|
50 |
\ OD \ |
|
4359 | 51 |
\ {c = A^B}"; |
6162 | 52 |
by (hoare_tac (Asm_full_simp_tac) 1); |
8423 | 53 |
by (cases_tac "b" 1); |
4356 | 54 |
by (hyp_subst_tac 1); |
55 |
by (asm_full_simp_tac (simpset() addsimps [mod_less]) 1); |
|
4359 | 56 |
by (asm_simp_tac (simpset() addsimps [mult_assoc]) 1); |
1335 | 57 |
qed "power_by_mult"; |
58 |
||
6802 | 59 |
(** Factorial **) |
60 |
||
5646 | 61 |
Goal "|- VARS a b. \ |
62 |
\ {a=A} \ |
|
63 |
\ b := 1; \ |
|
64 |
\ WHILE a ~= 0 \ |
|
65 |
\ INV {fac A = b * fac a} \ |
|
66 |
\ DO b := b*a; a := a-1 OD \ |
|
1335 | 67 |
\ {b = fac A}"; |
5646 | 68 |
by (hoare_tac Asm_full_simp_tac 1); |
5655
afd75136b236
Mods because of: Installed trans_tac in solver of simpset().
nipkow
parents:
5646
diff
changeset
|
69 |
by (Clarify_tac 1); |
8423 | 70 |
by (cases_tac "a" 1); |
1798
c055505f36d1
Explicitly included add_mult_distrib & add_mult_distrib2
paulson
parents:
1465
diff
changeset
|
71 |
by (ALLGOALS |
c055505f36d1
Explicitly included add_mult_distrib & add_mult_distrib2
paulson
parents:
1465
diff
changeset
|
72 |
(asm_simp_tac |
4089 | 73 |
(simpset() addsimps [add_mult_distrib,add_mult_distrib2,mult_assoc]))); |
5646 | 74 |
qed"factorial"; |
1335 | 75 |
|
6802 | 76 |
(** Square root **) |
77 |
||
6816 | 78 |
(* the easy way: *) |
6802 | 79 |
|
80 |
Goal "|- VARS x r. \ |
|
81 |
\ {u = 1 & w = 1 & r = 0} \ |
|
82 |
\ WHILE (r+1)*(r+1) <= x \ |
|
83 |
\ INV {r*r <= x} \ |
|
84 |
\ DO r := r+1 OD \ |
|
85 |
\ {r*r <= x & x < (r+1)*(r+1)}"; |
|
86 |
by (hoare_tac Asm_full_simp_tac 1); |
|
7322 | 87 |
by (arith_tac 1); |
6802 | 88 |
qed "sqrt"; |
89 |
||
90 |
(* without multiplication *) |
|
91 |
||
92 |
Goal "|- VARS x u w r. \ |
|
93 |
\ {u = 1 & w = 1 & r = 0} \ |
|
94 |
\ WHILE w <= x \ |
|
95 |
\ INV {u = r+r+1 & w = (r+1)*(r+1) & r*r <= x} \ |
|
96 |
\ DO r := r+1; w := w+u+2; u := u+2 OD \ |
|
97 |
\ {r*r <= x & x < (r+1)*(r+1)}"; |
|
98 |
by (hoare_tac Asm_full_simp_tac 1); |
|
7322 | 99 |
by (arith_tac 1); |
100 |
by (arith_tac 1); |
|
6802 | 101 |
qed "sqrt_without_multiplication"; |
102 |
||
103 |
||
5646 | 104 |
(*** LISTS ***) |
105 |
||
106 |
Goal "|- VARS y x. \ |
|
107 |
\ {x=X} \ |
|
108 |
\ y:=[]; \ |
|
109 |
\ WHILE x ~= [] \ |
|
110 |
\ INV {rev(x)@y = rev(X)} \ |
|
111 |
\ DO y := (hd x # y); x := tl x OD \ |
|
112 |
\ {y=rev(X)}"; |
|
113 |
by (hoare_tac Asm_full_simp_tac 1); |
|
114 |
by (asm_full_simp_tac (simpset() addsimps [neq_Nil_conv]) 1); |
|
115 |
by Safe_tac; |
|
116 |
by (ALLGOALS(Asm_full_simp_tac )); |
|
117 |
qed "imperative_reverse"; |
|
118 |
||
119 |
Goal |
|
120 |
"|- VARS x y. \ |
|
121 |
\ {x=X & y=Y} \ |
|
122 |
\ x := rev(x); \ |
|
123 |
\ WHILE x~=[] \ |
|
124 |
\ INV {rev(x)@y = X@Y} \ |
|
125 |
\ DO y := (hd x # y); \ |
|
126 |
\ x := tl x \ |
|
127 |
\ OD \ |
|
128 |
\ {y = X@Y}"; |
|
129 |
by (hoare_tac Asm_full_simp_tac 1); |
|
130 |
by (asm_full_simp_tac (simpset() addsimps [neq_Nil_conv]) 1); |
|
131 |
by Safe_tac; |
|
132 |
by (ALLGOALS(Asm_full_simp_tac)); |
|
133 |
qed "imperative_append"; |
|
134 |
||
135 |
||
136 |
(*** ARRAYS ***) |
|
137 |
||
138 |
(* Search for 0 *) |
|
139 |
Goal |
|
140 |
"|- VARS A i. \ |
|
141 |
\ {True} \ |
|
142 |
\ i := 0; \ |
|
143 |
\ WHILE i < length A & A!i ~= 0 \ |
|
144 |
\ INV {!j. j<i --> A!j ~= 0} \ |
|
145 |
\ DO i := i+1 OD \ |
|
146 |
\ {(i < length A --> A!i = 0) & \ |
|
147 |
\ (i = length A --> (!j. j < length A --> A!j ~= 0))}"; |
|
148 |
by (hoare_tac Asm_full_simp_tac 1); |
|
6162 | 149 |
by (blast_tac (claset() addSEs [less_SucE]) 1); |
5646 | 150 |
qed "zero_search"; |
151 |
||
152 |
(* |
|
153 |
The `partition' procedure for quicksort. |
|
154 |
`A' is the array to be sorted (modelled as a list). |
|
155 |
Elements of A must be of class order to infer at the end |
|
156 |
that the elements between u and l are equal to pivot. |
|
157 |
||
158 |
Ambiguity warnings of parser are due to := being used |
|
159 |
both for assignment and list update. |
|
160 |
*) |
|
161 |
Goal |
|
162 |
"[| leq == %A i. !k. k<i --> A!k <= pivot; \ |
|
163 |
\ geq == %A i. !k. i<k & k<length A --> pivot <= A!k |] ==> \ |
|
164 |
\ |- VARS A u l.\ |
|
165 |
\ {0 < length(A::('a::order)list)} \ |
|
166 |
\ l := 0; u := length A - 1; \ |
|
167 |
\ WHILE l <= u \ |
|
168 |
\ INV {leq A l & geq A u & u<length A & l<=length A} \ |
|
169 |
\ DO WHILE l < length A & A!l <= pivot \ |
|
170 |
\ INV {leq A l & geq A u & u<length A & l<=length A} \ |
|
171 |
\ DO l := l+1 OD; \ |
|
172 |
\ WHILE 0 < u & pivot <= A!u \ |
|
173 |
\ INV {leq A l & geq A u & u<length A & l<=length A} \ |
|
174 |
\ DO u := u-1 OD; \ |
|
175 |
\ IF l <= u THEN A := A[l := A!u, u := A!l] ELSE SKIP FI \ |
|
176 |
\ OD \ |
|
177 |
\ {leq A u & (!k. u<k & k<l --> A!k = pivot) & geq A l}"; |
|
178 |
(* expand and delete abbreviations first *) |
|
6162 | 179 |
by (asm_simp_tac HOL_basic_ss 1); |
180 |
by (REPEAT(etac thin_rl 1)); |
|
5646 | 181 |
by (hoare_tac Asm_full_simp_tac 1); |
6162 | 182 |
by (asm_full_simp_tac (simpset() addsimps [neq_Nil_conv]) 1); |
183 |
by (Clarify_tac 1); |
|
184 |
by (asm_full_simp_tac (simpset() addsimps [nth_list_update]) 1); |
|
185 |
by (blast_tac (claset() addSEs [less_SucE] addIs [Suc_leI]) 1); |
|
186 |
by (rtac conjI 1); |
|
187 |
by (Clarify_tac 1); |
|
188 |
by (dtac (pred_less_imp_le RS le_imp_less_Suc) 1); |
|
189 |
by (blast_tac (claset() addSEs [less_SucE]) 1); |
|
190 |
by (rtac less_imp_diff_less 1); |
|
191 |
by (Blast_tac 1); |
|
192 |
by (Clarify_tac 1); |
|
193 |
by (asm_simp_tac (simpset() addsimps [nth_list_update]) 1); |
|
194 |
by (Clarify_tac 1); |
|
195 |
by (Simp_tac 1); |
|
196 |
by (Clarify_tac 1); |
|
197 |
by (Asm_simp_tac 1); |
|
198 |
by (rtac conjI 1); |
|
199 |
by (Clarify_tac 1); |
|
200 |
by (rtac order_antisym 1); |
|
201 |
by (Asm_simp_tac 1); |
|
202 |
by (Asm_simp_tac 1); |
|
203 |
by (Clarify_tac 1); |
|
204 |
by (Asm_simp_tac 1); |
|
5646 | 205 |
qed "Partition"; |