src/HOL/Hoare/Examples.thy
author huffman
Fri Mar 30 12:32:35 2012 +0200 (2012-03-30)
changeset 47220 52426c62b5d0
parent 42154 478bdcea240a
child 58860 fee7cfa69c50
permissions -rw-r--r--
replace lemmas eval_nat_numeral with a simpler reformulation
clasohm@1476
     1
(*  Title:      HOL/Hoare/Examples.thy
clasohm@1476
     2
    Author:     Norbert Galm
nipkow@5646
     3
    Copyright   1998 TUM
nipkow@1335
     4
nipkow@5646
     5
Various examples.
nipkow@1335
     6
*)
nipkow@1335
     7
haftmann@35316
     8
theory Examples imports Hoare_Logic Arith2 begin
nipkow@13682
     9
nipkow@13682
    10
(*** ARITHMETIC ***)
nipkow@13682
    11
nipkow@13682
    12
(** multiplication by successive addition **)
nipkow@13682
    13
nipkow@13737
    14
lemma multiply_by_add: "VARS m s a b
nipkow@13682
    15
  {a=A & b=B}
nipkow@13682
    16
  m := 0; s := 0;
nipkow@13682
    17
  WHILE m~=a
nipkow@13682
    18
  INV {s=m*b & a=A & b=B}
nipkow@13682
    19
  DO s := s+b; m := m+(1::nat) OD
nipkow@13682
    20
  {s = A*B}"
nipkow@13682
    21
by vcg_simp
nipkow@13682
    22
nipkow@13789
    23
lemma "VARS M N P :: int
nipkow@13789
    24
 {m=M & n=N}
nipkow@13789
    25
 IF M < 0 THEN M := -M; N := -N ELSE SKIP FI;
nipkow@13789
    26
 P := 0;
nipkow@13789
    27
 WHILE 0 < M
nipkow@13789
    28
 INV {0 <= M & (EX p. p = (if m<0 then -m else m) & p*N = m*n & P = (p-M)*N)}
nipkow@13789
    29
 DO P := P+N; M := M - 1 OD
nipkow@13789
    30
 {P = m*n}"
nipkow@13789
    31
apply vcg_simp
nipkow@13789
    32
 apply (simp add:int_distrib)
nipkow@13789
    33
apply clarsimp
nipkow@13789
    34
apply(rule conjI)
nipkow@13789
    35
 apply clarsimp
nipkow@13789
    36
apply clarsimp
nipkow@13789
    37
done
nipkow@13682
    38
nipkow@13682
    39
(** Euclid's algorithm for GCD **)
nipkow@13682
    40
nipkow@13737
    41
lemma Euclid_GCD: "VARS a b
nipkow@13682
    42
 {0<A & 0<B}
nipkow@13682
    43
 a := A; b := B;
nipkow@13857
    44
 WHILE  a \<noteq> b
nipkow@13682
    45
 INV {0<a & 0<b & gcd A B = gcd a b}
nipkow@13682
    46
 DO IF a<b THEN b := b-a ELSE a := a-b FI OD
nipkow@13682
    47
 {a = gcd A B}"
nipkow@13682
    48
apply vcg
nipkow@13682
    49
(*Now prove the verification conditions*)
nipkow@13682
    50
  apply auto
nipkow@13682
    51
  apply(simp add: gcd_diff_r less_imp_le)
paulson@16796
    52
 apply(simp add: linorder_not_less gcd_diff_l)
nipkow@13682
    53
apply(erule gcd_nnn)
nipkow@13682
    54
done
nipkow@13682
    55
nipkow@13682
    56
(** Dijkstra's extension of Euclid's algorithm for simultaneous GCD and SCM **)
nipkow@13682
    57
(* From E.W. Disjkstra. Selected Writings on Computing, p 98 (EWD474),
nipkow@13682
    58
   where it is given without the invariant. Instead of defining scm
nipkow@13682
    59
   explicitly we have used the theorem scm x y = x*y/gcd x y and avoided
nipkow@13682
    60
   division by mupltiplying with gcd x y.
nipkow@13682
    61
*)
nipkow@13682
    62
nipkow@13682
    63
lemmas distribs =
nipkow@13682
    64
  diff_mult_distrib diff_mult_distrib2 add_mult_distrib add_mult_distrib2
nipkow@13682
    65
nipkow@13737
    66
lemma gcd_scm: "VARS a b x y
nipkow@13682
    67
 {0<A & 0<B & a=A & b=B & x=B & y=A}
nipkow@13682
    68
 WHILE  a ~= b
nipkow@13682
    69
 INV {0<a & 0<b & gcd A B = gcd a b & 2*A*B = a*x + b*y}
nipkow@13682
    70
 DO IF a<b THEN (b := b-a; x := x+y) ELSE (a := a-b; y := y+x) FI OD
nipkow@13682
    71
 {a = gcd A B & 2*A*B = a*(x+y)}"
nipkow@13682
    72
apply vcg
nipkow@13682
    73
  apply simp
paulson@16796
    74
 apply(simp add: distribs gcd_diff_r linorder_not_less gcd_diff_l)
nipkow@13682
    75
apply(simp add: distribs gcd_nnn)
nipkow@13682
    76
done
nipkow@13682
    77
nipkow@13682
    78
(** Power by iterated squaring and multiplication **)
nipkow@13682
    79
nipkow@13737
    80
lemma power_by_mult: "VARS a b c
nipkow@13682
    81
 {a=A & b=B}
nipkow@13682
    82
 c := (1::nat);
nipkow@13682
    83
 WHILE b ~= 0
nipkow@13682
    84
 INV {A^B = c * a^b}
nipkow@13682
    85
 DO  WHILE b mod 2 = 0
nipkow@13682
    86
     INV {A^B = c * a^b}
nipkow@13682
    87
     DO  a := a*a; b := b div 2 OD;
nipkow@13682
    88
     c := c*a; b := b - 1
nipkow@13682
    89
 OD
nipkow@13682
    90
 {c = A^B}"
nipkow@13682
    91
apply vcg_simp
nipkow@13682
    92
apply(case_tac "b")
wenzelm@42154
    93
 apply simp
nipkow@13682
    94
apply simp
nipkow@13682
    95
done
nipkow@13682
    96
nipkow@13682
    97
(** Factorial **)
nipkow@13682
    98
nipkow@13737
    99
lemma factorial: "VARS a b
nipkow@13682
   100
 {a=A}
nipkow@13682
   101
 b := 1;
nipkow@13682
   102
 WHILE a ~= 0
nipkow@13682
   103
 INV {fac A = b * fac a}
nipkow@13682
   104
 DO b := b*a; a := a - 1 OD
nipkow@13682
   105
 {b = fac A}"
nipkow@13682
   106
apply vcg_simp
nipkow@13682
   107
apply(clarsimp split: nat_diff_split)
nipkow@13682
   108
done
nipkow@13682
   109
nipkow@13684
   110
lemma [simp]: "1 \<le> i \<Longrightarrow> fac (i - Suc 0) * i = fac i"
nipkow@13684
   111
by(induct i, simp_all)
nipkow@13684
   112
nipkow@13737
   113
lemma "VARS i f
nipkow@13684
   114
 {True}
nipkow@13684
   115
 i := (1::nat); f := 1;
nipkow@13684
   116
 WHILE i <= n INV {f = fac(i - 1) & 1 <= i & i <= n+1}
nipkow@13684
   117
 DO f := f*i; i := i+1 OD
nipkow@13684
   118
 {f = fac n}"
nipkow@13684
   119
apply vcg_simp
nipkow@13684
   120
apply(subgoal_tac "i = Suc n")
nipkow@13684
   121
apply simp
nipkow@13684
   122
apply arith
nipkow@13684
   123
done
nipkow@13682
   124
nipkow@13682
   125
(** Square root **)
nipkow@13682
   126
nipkow@13682
   127
(* the easy way: *)
nipkow@13682
   128
nipkow@13737
   129
lemma sqrt: "VARS r x
nipkow@13682
   130
 {True}
nipkow@13682
   131
 x := X; r := (0::nat);
nipkow@13682
   132
 WHILE (r+1)*(r+1) <= x
nipkow@13682
   133
 INV {r*r <= x & x=X}
nipkow@13682
   134
 DO r := r+1 OD
nipkow@13682
   135
 {r*r <= X & X < (r+1)*(r+1)}"
nipkow@13682
   136
apply vcg_simp
nipkow@13682
   137
done
nipkow@13682
   138
nipkow@13682
   139
(* without multiplication *)
nipkow@13682
   140
nipkow@13737
   141
lemma sqrt_without_multiplication: "VARS u w r x
nipkow@13682
   142
 {True}
nipkow@13682
   143
 x := X; u := 1; w := 1; r := (0::nat);
nipkow@13682
   144
 WHILE w <= x
nipkow@13682
   145
 INV {u = r+r+1 & w = (r+1)*(r+1) & r*r <= x & x=X}
nipkow@13682
   146
 DO r := r + 1; w := w + u + 2; u := u + 2 OD
nipkow@13682
   147
 {r*r <= X & X < (r+1)*(r+1)}"
nipkow@13682
   148
apply vcg_simp
nipkow@13682
   149
done
nipkow@13682
   150
nipkow@13682
   151
nipkow@13682
   152
(*** LISTS ***)
nipkow@13682
   153
nipkow@13737
   154
lemma imperative_reverse: "VARS y x
nipkow@13682
   155
 {x=X}
nipkow@13682
   156
 y:=[];
nipkow@13682
   157
 WHILE x ~= []
nipkow@13682
   158
 INV {rev(x)@y = rev(X)}
nipkow@13682
   159
 DO y := (hd x # y); x := tl x OD
nipkow@13682
   160
 {y=rev(X)}"
nipkow@13682
   161
apply vcg_simp
nipkow@13682
   162
 apply(simp add: neq_Nil_conv)
nipkow@13682
   163
 apply auto
nipkow@13682
   164
done
nipkow@13682
   165
nipkow@13737
   166
lemma imperative_append: "VARS x y
nipkow@13682
   167
 {x=X & y=Y}
nipkow@13682
   168
 x := rev(x);
nipkow@13682
   169
 WHILE x~=[]
nipkow@13682
   170
 INV {rev(x)@y = X@Y}
nipkow@13682
   171
 DO y := (hd x # y);
nipkow@13682
   172
    x := tl x
nipkow@13682
   173
 OD
nipkow@13682
   174
 {y = X@Y}"
nipkow@13682
   175
apply vcg_simp
nipkow@13682
   176
apply(simp add: neq_Nil_conv)
nipkow@13682
   177
apply auto
nipkow@13682
   178
done
nipkow@13682
   179
nipkow@13682
   180
nipkow@13682
   181
(*** ARRAYS ***)
nipkow@13682
   182
nipkow@13682
   183
(* Search for a key *)
nipkow@13737
   184
lemma zero_search: "VARS A i
nipkow@13682
   185
 {True}
nipkow@13682
   186
 i := 0;
nipkow@13682
   187
 WHILE i < length A & A!i ~= key
nipkow@13682
   188
 INV {!j. j<i --> A!j ~= key}
nipkow@13682
   189
 DO i := i+1 OD
nipkow@13682
   190
 {(i < length A --> A!i = key) &
nipkow@13682
   191
  (i = length A --> (!j. j < length A --> A!j ~= key))}"
nipkow@13682
   192
apply vcg_simp
nipkow@13682
   193
apply(blast elim!: less_SucE)
nipkow@13682
   194
done
nipkow@13682
   195
nipkow@13682
   196
(* 
nipkow@13682
   197
The `partition' procedure for quicksort.
nipkow@13682
   198
`A' is the array to be sorted (modelled as a list).
nipkow@13682
   199
Elements of A must be of class order to infer at the end
nipkow@13682
   200
that the elements between u and l are equal to pivot.
nipkow@13682
   201
nipkow@13682
   202
Ambiguity warnings of parser are due to := being used
nipkow@13682
   203
both for assignment and list update.
nipkow@13682
   204
*)
nipkow@13682
   205
lemma lem: "m - Suc 0 < n ==> m < Suc n"
nipkow@13682
   206
by arith
nipkow@13682
   207
nipkow@13682
   208
nipkow@13682
   209
lemma Partition:
nipkow@13682
   210
"[| leq == %A i. !k. k<i --> A!k <= pivot;
nipkow@13682
   211
    geq == %A i. !k. i<k & k<length A --> pivot <= A!k |] ==>
nipkow@13737
   212
 VARS A u l
nipkow@13682
   213
 {0 < length(A::('a::order)list)}
nipkow@13682
   214
 l := 0; u := length A - Suc 0;
nipkow@13682
   215
 WHILE l <= u
nipkow@13682
   216
  INV {leq A l & geq A u & u<length A & l<=length A}
nipkow@13682
   217
  DO WHILE l < length A & A!l <= pivot
nipkow@13682
   218
     INV {leq A l & geq A u & u<length A & l<=length A}
nipkow@13682
   219
     DO l := l+1 OD;
nipkow@13682
   220
     WHILE 0 < u & pivot <= A!u
nipkow@13682
   221
     INV {leq A l & geq A u  & u<length A & l<=length A}
nipkow@13682
   222
     DO u := u - 1 OD;
nipkow@13682
   223
     IF l <= u THEN A := A[l := A!u, u := A!l] ELSE SKIP FI
nipkow@13682
   224
  OD
nipkow@13682
   225
 {leq A u & (!k. u<k & k<l --> A!k = pivot) & geq A l}"
nipkow@13682
   226
(* expand and delete abbreviations first *)
nipkow@13682
   227
apply (simp);
nipkow@13682
   228
apply (erule thin_rl)+
nipkow@13682
   229
apply vcg_simp
nipkow@16733
   230
   apply (force simp: neq_Nil_conv)
nipkow@16733
   231
  apply (blast elim!: less_SucE intro: Suc_leI)
nipkow@16733
   232
 apply (blast elim!: less_SucE intro: less_imp_diff_less dest: lem)
nipkow@16733
   233
apply (force simp: nth_list_update)
nipkow@13682
   234
done
nipkow@13682
   235
nipkow@13682
   236
end