src/HOL/IMP/VC.thy
author kleing
Sun Dec 09 14:35:36 2001 +0100 (2001-12-09)
changeset 12431 07ec657249e5
parent 9241 f961c1fdff50
child 12434 ff2efde4574d
permissions -rw-r--r--
converted to Isar
clasohm@1476
     1
(*  Title:      HOL/IMP/VC.thy
nipkow@1447
     2
    ID:         $Id$
clasohm@1476
     3
    Author:     Tobias Nipkow
nipkow@1447
     4
    Copyright   1996 TUM
nipkow@1447
     5
nipkow@1447
     6
acom: annotated commands
nipkow@1447
     7
vc:   verification-conditions
nipkow@2810
     8
awp:   weakest (liberal) precondition
nipkow@1447
     9
*)
nipkow@1447
    10
kleing@12431
    11
header "Verification Conditions"
kleing@12431
    12
kleing@12431
    13
theory VC = Hoare:
nipkow@1447
    14
nipkow@1447
    15
datatype  acom = Askip
nipkow@1447
    16
               | Aass   loc aexp
nipkow@1447
    17
               | Asemi  acom acom
nipkow@1447
    18
               | Aif    bexp acom acom
nipkow@1447
    19
               | Awhile bexp assn acom
nipkow@1447
    20
nipkow@1447
    21
consts
kleing@12431
    22
  vc :: "acom => assn => assn"
kleing@12431
    23
  awp :: "acom => assn => assn"
kleing@12431
    24
  vcawp :: "acom => assn => assn \<times> assn"
kleing@12431
    25
  astrip :: "acom => com"
nipkow@1447
    26
berghofe@5183
    27
primrec
nipkow@2810
    28
  "awp Askip Q = Q"
kleing@12431
    29
  "awp (Aass x a) Q = (\<lambda>s. Q(s[x\<mapsto>a s]))"
nipkow@2810
    30
  "awp (Asemi c d) Q = awp c (awp d Q)"
kleing@12431
    31
  "awp (Aif b c d) Q = (\<lambda>s. (b s-->awp c Q s) & (~b s-->awp d Q s))" 
nipkow@2810
    32
  "awp (Awhile b I c) Q = I"
nipkow@1447
    33
berghofe@5183
    34
primrec
kleing@12431
    35
  "vc Askip Q = (\<lambda>s. True)"
kleing@12431
    36
  "vc (Aass x a) Q = (\<lambda>s. True)"
kleing@12431
    37
  "vc (Asemi c d) Q = (\<lambda>s. vc c (awp d Q) s & vc d Q s)"
kleing@12431
    38
  "vc (Aif b c d) Q = (\<lambda>s. vc c Q s & vc d Q s)" 
kleing@12431
    39
  "vc (Awhile b I c) Q = (\<lambda>s. (I s & ~b s --> Q s) &
nipkow@2810
    40
                              (I s & b s --> awp c I s) & vc c I s)"
nipkow@1447
    41
berghofe@5183
    42
primrec
berghofe@1900
    43
  "astrip Askip = SKIP"
oheimb@9241
    44
  "astrip (Aass x a) = (x:==a)"
berghofe@1900
    45
  "astrip (Asemi c d) = (astrip c;astrip d)"
kleing@12431
    46
  "astrip (Aif b c d) = (\<IF> b \<THEN> astrip c \<ELSE> astrip d)"
kleing@12431
    47
  "astrip (Awhile b I c) = (\<WHILE> b \<DO> astrip c)"
nipkow@1451
    48
nipkow@2810
    49
(* simultaneous computation of vc and awp: *)
berghofe@5183
    50
primrec
kleing@12431
    51
  "vcawp Askip Q = (\<lambda>s. True, Q)"
kleing@12431
    52
  "vcawp (Aass x a) Q = (\<lambda>s. True, \<lambda>s. Q(s[x\<mapsto>a s]))"
nipkow@2810
    53
  "vcawp (Asemi c d) Q = (let (vcd,wpd) = vcawp d Q;
nipkow@2810
    54
                              (vcc,wpc) = vcawp c wpd
kleing@12431
    55
                          in (\<lambda>s. vcc s & vcd s, wpc))"
nipkow@2810
    56
  "vcawp (Aif b c d) Q = (let (vcd,wpd) = vcawp d Q;
nipkow@2810
    57
                              (vcc,wpc) = vcawp c Q
kleing@12431
    58
                          in (\<lambda>s. vcc s & vcd s,
kleing@12431
    59
                              \<lambda>s.(b s --> wpc s) & (~b s --> wpd s)))"
nipkow@2810
    60
  "vcawp (Awhile b I c) Q = (let (vcc,wpc) = vcawp c I
kleing@12431
    61
                             in (\<lambda>s. (I s & ~b s --> Q s) &
nipkow@2810
    62
                                     (I s & b s --> wpc s) & vcc s, I))"
nipkow@1451
    63
kleing@12431
    64
(*
kleing@12431
    65
Soundness and completeness of vc
kleing@12431
    66
*)
kleing@12431
    67
kleing@12431
    68
declare hoare.intros [intro]
kleing@12431
    69
kleing@12431
    70
lemma l: "!s. P s --> P s" by fast
kleing@12431
    71
kleing@12431
    72
lemma vc_sound: "!Q. (!s. vc c Q s) --> |- {awp c Q} astrip c {Q}"
kleing@12431
    73
apply (induct_tac "c")
kleing@12431
    74
    apply (simp_all (no_asm))
kleing@12431
    75
    apply fast
kleing@12431
    76
   apply fast
kleing@12431
    77
  apply fast
kleing@12431
    78
 (* if *)
kleing@12431
    79
 apply (tactic "Deepen_tac 4 1")
kleing@12431
    80
(* while *)
kleing@12431
    81
apply (intro allI impI) 
kleing@12431
    82
apply (rule conseq)
kleing@12431
    83
  apply (rule l)
kleing@12431
    84
 apply (rule While)
kleing@12431
    85
 defer
kleing@12431
    86
 apply fast
kleing@12431
    87
apply (rule_tac P="awp acom fun2" in conseq)
kleing@12431
    88
  apply fast
kleing@12431
    89
 apply fast
kleing@12431
    90
apply fast
kleing@12431
    91
done
kleing@12431
    92
kleing@12431
    93
lemma awp_mono [rule_format (no_asm)]: "!P Q. (!s. P s --> Q s) --> (!s. awp c P s --> awp c Q s)"
kleing@12431
    94
apply (induct_tac "c")
kleing@12431
    95
    apply (simp_all (no_asm_simp))
kleing@12431
    96
apply (rule allI, rule allI, rule impI)
kleing@12431
    97
apply (erule allE, erule allE, erule mp)
kleing@12431
    98
apply (erule allE, erule allE, erule mp, assumption)
kleing@12431
    99
done
kleing@12431
   100
kleing@12431
   101
kleing@12431
   102
lemma vc_mono [rule_format (no_asm)]: "!P Q. (!s. P s --> Q s) --> (!s. vc c P s --> vc c Q s)"
kleing@12431
   103
apply (induct_tac "c")
kleing@12431
   104
    apply (simp_all (no_asm_simp))
kleing@12431
   105
apply safe
kleing@12431
   106
apply (erule allE,erule allE,erule impE,erule_tac [2] allE,erule_tac [2] mp) 
kleing@12431
   107
prefer 2 apply assumption
kleing@12431
   108
apply (fast elim: awp_mono)
kleing@12431
   109
done
kleing@12431
   110
kleing@12431
   111
lemma vc_complete: "|- {P}c{Q} ==>  
kleing@12431
   112
   (? ac. astrip ac = c & (!s. vc ac Q s) & (!s. P s --> awp ac Q s))"
kleing@12431
   113
apply (erule hoare.induct)
kleing@12431
   114
     apply (rule_tac x = "Askip" in exI)
kleing@12431
   115
     apply (simp (no_asm))
kleing@12431
   116
    apply (rule_tac x = "Aass x a" in exI)
kleing@12431
   117
    apply (simp (no_asm))
kleing@12431
   118
   apply clarify
kleing@12431
   119
   apply (rule_tac x = "Asemi ac aca" in exI)
kleing@12431
   120
   apply (simp (no_asm_simp))
kleing@12431
   121
   apply (fast elim!: awp_mono vc_mono)
kleing@12431
   122
  apply clarify
kleing@12431
   123
  apply (rule_tac x = "Aif b ac aca" in exI)
kleing@12431
   124
  apply (simp (no_asm_simp))
kleing@12431
   125
 apply clarify
kleing@12431
   126
 apply (rule_tac x = "Awhile b P ac" in exI)
kleing@12431
   127
 apply (simp (no_asm_simp))
kleing@12431
   128
apply safe
kleing@12431
   129
apply (rule_tac x = "ac" in exI)
kleing@12431
   130
apply (simp (no_asm_simp))
kleing@12431
   131
apply (fast elim!: awp_mono vc_mono)
kleing@12431
   132
done
kleing@12431
   133
kleing@12431
   134
lemma vcawp_vc_awp: "!Q. vcawp c Q = (vc c Q, awp c Q)"
kleing@12431
   135
apply (induct_tac "c")
kleing@12431
   136
apply (simp_all (no_asm_simp) add: Let_def)
kleing@12431
   137
done
kleing@12431
   138
nipkow@1447
   139
end