|
9243
|
1 |
(* Title: HOL/IMP/Examples.thy
|
|
|
2 |
Author: David von Oheimb, TUM
|
|
|
3 |
*)
|
|
|
4 |
|
|
12431
|
5 |
header "Examples"
|
|
|
6 |
|
|
16417
|
7 |
theory Examples imports Natural begin
|
|
12431
|
8 |
|
|
27362
|
9 |
definition
|
|
|
10 |
factorial :: "loc => loc => com" where
|
|
|
11 |
"factorial a b = (b :== (%s. 1);
|
|
12431
|
12 |
\<WHILE> (%s. s a ~= 0) \<DO>
|
|
27362
|
13 |
(b :== (%s. s b * s a); a :== (%s. s a - 1)))"
|
|
12431
|
14 |
|
|
|
15 |
declare update_def [simp]
|
|
|
16 |
|
|
|
17 |
subsection "An example due to Tony Hoare"
|
|
9243
|
18 |
|
|
18372
|
19 |
lemma lemma1:
|
|
|
20 |
assumes 1: "!x. P x \<longrightarrow> Q x"
|
|
|
21 |
and 2: "\<langle>w,s\<rangle> \<longrightarrow>\<^sub>c t"
|
|
|
22 |
shows "w = While P c \<Longrightarrow> \<langle>While Q c,t\<rangle> \<longrightarrow>\<^sub>c u \<Longrightarrow> \<langle>While Q c,s\<rangle> \<longrightarrow>\<^sub>c u"
|
|
|
23 |
using 2 apply induct
|
|
|
24 |
using 1 apply auto
|
|
|
25 |
done
|
|
12431
|
26 |
|
|
18372
|
27 |
lemma lemma2 [rule_format (no_asm)]:
|
|
|
28 |
"[| !x. P x \<longrightarrow> Q x; \<langle>w,s\<rangle> \<longrightarrow>\<^sub>c u |] ==>
|
|
12431
|
29 |
!c. w = While Q c \<longrightarrow> \<langle>While P c; While Q c,s\<rangle> \<longrightarrow>\<^sub>c u"
|
|
|
30 |
apply (erule evalc.induct)
|
|
|
31 |
apply (simp_all (no_asm_simp))
|
|
|
32 |
apply blast
|
|
|
33 |
apply (case_tac "P s")
|
|
|
34 |
apply auto
|
|
|
35 |
done
|
|
|
36 |
|
|
18372
|
37 |
lemma Hoare_example: "!x. P x \<longrightarrow> Q x ==>
|
|
12431
|
38 |
(\<langle>While P c; While Q c, s\<rangle> \<longrightarrow>\<^sub>c t) = (\<langle>While Q c, s\<rangle> \<longrightarrow>\<^sub>c t)"
|
|
|
39 |
by (blast intro: lemma1 lemma2 dest: semi [THEN iffD1])
|
|
|
40 |
|
|
9243
|
41 |
|
|
12431
|
42 |
subsection "Factorial"
|
|
|
43 |
|
|
18372
|
44 |
lemma factorial_3: "a~=b ==>
|
|
|
45 |
\<langle>factorial a b, Mem(a:=3)\<rangle> \<longrightarrow>\<^sub>c Mem(b:=6, a:=0)"
|
|
|
46 |
by (simp add: factorial_def)
|
|
12431
|
47 |
|
|
|
48 |
text {* the same in single step mode: *}
|
|
|
49 |
lemmas [simp del] = evalc_cases
|
|
|
50 |
lemma "a~=b \<Longrightarrow> \<langle>factorial a b, Mem(a:=3)\<rangle> \<longrightarrow>\<^sub>c Mem(b:=6, a:=0)"
|
|
|
51 |
apply (unfold factorial_def)
|
|
|
52 |
apply (frule not_sym)
|
|
|
53 |
apply (rule evalc.intros)
|
|
|
54 |
apply (rule evalc.intros)
|
|
|
55 |
apply simp
|
|
|
56 |
apply (rule evalc.intros)
|
|
|
57 |
apply simp
|
|
|
58 |
apply (rule evalc.intros)
|
|
|
59 |
apply (rule evalc.intros)
|
|
|
60 |
apply simp
|
|
|
61 |
apply (rule evalc.intros)
|
|
|
62 |
apply simp
|
|
|
63 |
apply (rule evalc.intros)
|
|
|
64 |
apply simp
|
|
|
65 |
apply (rule evalc.intros)
|
|
|
66 |
apply (rule evalc.intros)
|
|
|
67 |
apply simp
|
|
|
68 |
apply (rule evalc.intros)
|
|
|
69 |
apply simp
|
|
|
70 |
apply (rule evalc.intros)
|
|
|
71 |
apply simp
|
|
|
72 |
apply (rule evalc.intros)
|
|
|
73 |
apply (rule evalc.intros)
|
|
|
74 |
apply simp
|
|
|
75 |
apply (rule evalc.intros)
|
|
|
76 |
apply simp
|
|
|
77 |
apply (rule evalc.intros)
|
|
|
78 |
apply simp
|
|
|
79 |
done
|
|
18372
|
80 |
|
|
9243
|
81 |
end
|