Quelle  Hoare_Ex.thy

section ‹Using Hoare Logic›

theory Hoare_Ex
  imports Hoare
begin

subsection ‹State spaces›

text ‹
  First of all we provide a store of program variables that occur in any of
  the programs considered later. Slightly unexpected things may happen when
  attempting to work with undeclared variables.
 ›

record vars =
  I :: nat
  M :: nat
  N :: nat
  S :: nat

text ‹
  While all of our variables happen to have the same type, nothing would
  prevent us from working with many-sorted programs as well, or even
  polymorphic ones. Also note that Isabelle/HOL's extensible record types even
  provides simple means to extend the state space later.
 ›


subsection ‹Basic examples›

text ‹
  We look at few trivialities involving assignment and sequential composition,
  in order to get an idea of how to work with our formulation of Hoare Logic.
 
  🪙
  Using the basic ‹assign› rule directly is a bit cumbersome.
 ›

lemma "⊨ {🍋(N_update (λ_. (2 * 🍋N))) ∈ {🍋N = 10}} 🍋N := 2 * 🍋N {🍋N = 10}"
  by (rule assign)

text ‹
  Certainly we want the state modification already done, e.g.\ by
  simplification. The ‹hoare› method performs the basic state update for us;
  we may apply the Simplifier afterwards to achieve ``obvious'' consequences
  as well.
 ›

lemma "⊨ {True} 🍋N := 10 {🍋N = 10}"
  by hoare

lemma "⊨ {2 * 🍋N = 10} 🍋N := 2 * 🍋N {🍋N = 10}"
  by hoare

lemma "⊨ {🍋N = 5} 🍋N := 2 * 🍋N {🍋N = 10}"
  by hoare simp

lemma "⊨ {🍋N + 1 = a + 1} 🍋N := 🍋N + 1 {🍋N = a + 1}"
  by hoare

lemma "⊨ {🍋N = a} 🍋N := 🍋N + 1 {🍋N = a + 1}"
  by hoare simp

lemma "⊨ {a = a ∧ b = b} 🍋M := a; 🍋N := b {🍋M = a ∧ 🍋N = b}"
  by hoare

lemma "⊨ {True} 🍋M := a; 🍋N := b {🍋M = a ∧ 🍋N = b}"
  by hoare

lemma
  "⊨ {🍋M = a ∧ 🍋N = b}
      🍋I := 🍋M; 🍋M := 🍋N; 🍋N := 🍋I
      {🍋M = b ∧ 🍋N = a}"
  by hoare simp

text ‹
  It is important to note that statements like the following one can only be
  proven for each individual program variable. Due to the extra-logical nature
  of record fields, we cannot formulate a theorem relating record selectors
  and updates schematically.
 ›

lemma "⊨ {🍋N = a} 🍋N := 🍋N {🍋N = a}"
  by hoare

lemma "⊨ {🍋x = a} 🍋x := 🍋x {🍋x = a}"
  oops

lemma
  "Valid {s. x s = a} (Basic (λs. x_update (x s) s)) {s. x s = n}"
  🍋 ‹same statement without concrete syntax›
  oops


text ‹
  In the following assignments we make use of the consequence rule in order to
  achieve the intended precondition. Certainly, the ‹hoare› method is able to
  handle this case, too.
 ›

lemma "⊨ {🍋M = 🍋N} 🍋M := 🍋M + 1 {🍋M ≠ 🍋N}"
proof -
  have "{🍋M = 🍋N} ⊆ {🍋M + 1 ≠ 🍋N}"
    by auto
  also have "⊨ … 🍋M := 🍋M + 1 {🍋M ≠ 🍋N}"
    by hoare
  finally show ?thesis .
qed

lemma "⊨ {🍋M = 🍋N} 🍋M := 🍋M + 1 {🍋M ≠ 🍋N}"
proof -
  have "m = n ⟶ m + 1 ≠ n" for m n :: nat
      🍋 ‹inclusion of assertions expressed in ``pure'' logic,›
      🍋 ‹without mentioning the state space›
    by simp
  also have "⊨ {🍋M + 1 ≠ 🍋N} 🍋M := 🍋M + 1 {🍋M ≠ 🍋N}"
    by hoare
  finally show ?thesis .
qed

lemma "⊨ {🍋M = 🍋N} 🍋M := 🍋M + 1 {🍋M ≠ 🍋N}"
  by hoare simp


subsection ‹Multiplication by addition›

text ‹
  We now do some basic examples of actual 🍋‹WHILE› programs. This one is a
  loop for calculating the product of two natural numbers, by iterated
  addition. We first give detailed structured proof based on single-step Hoare
  rules.
 ›

lemma
  "⊨ {🍋M = 0 ∧ 🍋S = 0}
      WHILE 🍋M ≠ a
      DO 🍋S := 🍋S + b; 🍋M := 🍋M + 1 OD
      {🍋S = a * b}"
proof -
  let "⊨ _ ?while _" = ?thesis
  let "{🍋?inv}" = "{🍋S = 🍋M * b}"

  have "{🍋M = 0 ∧ 🍋S = 0} ⊆ {🍋?inv}" by auto
  also have "⊨ … ?while {🍋?inv ∧ ¬ (🍋M ≠ a)}"
  proof
    let ?c = "🍋S := 🍋S + b; 🍋M := 🍋M + 1"
    have "{🍋?inv ∧ 🍋M ≠ a} ⊆ {🍋S + b = (🍋M + 1) * b}"
      by auto
    also have "⊨ … ?c {🍋?inv}" by hoare
    finally show "⊨ {🍋?inv ∧ 🍋M ≠ a} ?c {🍋?inv}" .
  qed
  also have "… ⊆ {🍋S = a * b}" by auto
  finally show ?thesis .
qed

text ‹
  The subsequent version of the proof applies the ‹hoare› method to reduce the
  Hoare statement to a purely logical problem that can be solved fully
  automatically. Note that we have to specify the 🍋‹WHILE› loop invariant in
  the original statement.
 ›

lemma
  "⊨ {🍋M = 0 ∧ 🍋S = 0}
      WHILE 🍋M ≠ a
      INV {🍋S = 🍋M * b}
      DO 🍋S := 🍋S + b; 🍋M := 🍋M + 1 OD
      {🍋S = a * b}"
  by hoare auto


subsection ‹Summing natural numbers›

text ‹
  We verify an imperative program to sum natural numbers up to a given limit.
  First some functional definition for proper specification of the problem.
 
  🪙
  The following proof is quite explicit in the individual steps taken, with
  the ‹hoare› method only applied locally to take care of assignment and
  sequential composition. Note that we express intermediate proof obligation
  in pure logic, without referring to the state space.
 ›

theorem
  "⊨ {True}
      🍋S := 0; 🍋I := 1;
      WHILE 🍋I ≠ n
      DO
        🍋S := 🍋S + 🍋I;
        🍋I := 🍋I + 1
      OD
      {🍋S = (∑j}"
  (is "⊨ _ (_; ?while) _")
proof -
  let ?sum = "λk::nat. ∑j
  let ?inv = "λs i::nat. s = ?sum i"

  have "⊨ {True} 🍋S := 0; 🍋I := 1 {?inv 🍋S 🍋I}"
  proof -
    have "True ⟶ 0 = ?sum 1"
      by simp
    also have "⊨ {…} 🍋S := 0; 🍋I := 1 {?inv 🍋S 🍋I}"
      by hoare
    finally show ?thesis .
  qed
  also have "⊨ … ?while {?inv 🍋S 🍋I ∧ ¬ 🍋I ≠ n}"
  proof
    let ?body = "🍋S := 🍋S + 🍋I; 🍋I := 🍋I + 1"
    have "?inv s i ∧ i ≠ n ⟶ ?inv (s + i) (i + 1)" for s i
      by simp
    also have "⊨ {🍋S + 🍋I = ?sum (🍋I + 1)} ?body {?inv 🍋S 🍋I}"
      by hoare
    finally show "⊨ {?inv 🍋S 🍋I ∧ 🍋I ≠ n} ?body {?inv 🍋S 🍋I}" .
  qed
  also have "s = ?sum i ∧ ¬ i ≠ n ⟶ s = ?sum n" for s i
    by simp
  finally show ?thesis .
qed

text ‹
  The next version uses the ‹hoare› method, while still explaining the
  resulting proof obligations in an abstract, structured manner.
 ›

theorem
  "⊨ {True}
      🍋S := 0; 🍋I := 1;
      WHILE 🍋I ≠ n
      INV {🍋S = (∑j<🍋I. j)}
      DO
        🍋S := 🍋S + 🍋I;
        🍋I := 🍋I + 1
      OD
      {🍋S = (∑j}"
proof -
  let ?sum = "λk::nat. ∑j
  let ?inv = "λs i::nat. s = ?sum i"
  show ?thesis
  proof hoare
    show "?inv 0 1" by simp
    show "?inv (s + i) (i + 1)" if "?inv s i ∧ i ≠ n" for s i
      using that by simp
    show "s = ?sum n" if "?inv s i ∧ ¬ i ≠ n" for s i
      using that by simp
  qed
qed

text ‹
  Certainly, this proof may be done fully automatic as well, provided that the
  invariant is given beforehand.
 ›

theorem
  "⊨ {True}
      🍋S := 0; 🍋I := 1;
      WHILE 🍋I ≠ n
      INV {🍋S = (∑j<🍋I. j)}
      DO
        🍋S := 🍋S + 🍋I;
        🍋I := 🍋I + 1
      OD
      {🍋S = (∑j}"
  by hoare auto


subsection ‹Time›

text ‹
  A simple embedding of time in Hoare logic: function ‹timeit› inserts an
  extra variable to keep track of the elapsed time.
 ›

record tstate = time :: nat

type_synonym 'a time = "(time :: nat, … :: 'a)"

primrec timeit :: "'a time com ==> 'a time com"
  where
    "timeit (Basic f) = (Basic f; Basic(λs. s(time := Suc (time s))))"
  | "timeit (c1; c2) = (timeit c1; timeit c2)"
  | "timeit (Cond b c1 c2) = Cond b (timeit c1) (timeit c2)"
  | "timeit (While b iv v c) = While b iv v (timeit c)"

record tvars = tstate +
  I :: nat
  J :: nat

lemma lem: "(0::nat) < n ==> n + n ≤ Suc (n * n)"
  by (induct n) simp_all

lemma
  "⊨ {i = 🍋I ∧ 🍋time = 0}
    (timeit
      (WHILE 🍋I ≠ 0
        INV {2 *🍋 time + 🍋I * 🍋I + 5 * 🍋I = i * i + 5 * i}
        DO
          🍋J := 🍋I;
          WHILE 🍋J ≠ 0
          INV {0 < 🍋I ∧ 2 * 🍋time + 🍋I * 🍋I + 3 * 🍋I + 2 * 🍋J - 2 = i * i + 5 * i}
          DO 🍋J := 🍋J - 1 OD;
          🍋I := 🍋I - 1
        OD))
    {2 * 🍋time = i * i + 5 * i}"
  apply simp
  apply hoare
      apply simp
     apply clarsimp
    apply clarsimp
   apply arith
   prefer 2
   apply clarsimp
  apply (clarsimp simp: nat_distrib)
  apply (frule lem)
  apply arith
  done

end