4 Copyright 1994 TUM |
4 Copyright 1994 TUM |
5 *) |
5 *) |
6 |
6 |
7 open Denotation; |
7 open Denotation; |
8 |
8 |
9 val denotation_cs = comp_cs addss (!simpset addsimps evalc.intrs); |
|
10 |
|
11 |
|
12 (**** Rewrite Rules for C ****) |
|
13 |
|
14 val C_simps = map (fn t => t RS eq_reflection) |
|
15 [C_skip,C_assign,C_comp,C_if,C_while]; |
|
16 |
|
17 |
9 |
18 (**** mono (Gamma(b,c)) ****) |
10 (**** mono (Gamma(b,c)) ****) |
19 |
11 |
20 qed_goalw "Gamma_mono" Denotation.thy [mono_def,Gamma_def] |
12 qed_goalw "Gamma_mono" Denotation.thy [mono_def,Gamma_def] |
21 "mono (Gamma b c)" |
13 "mono (Gamma b c)" |
22 (fn _ => [(best_tac comp_cs 1)]); |
14 (fn _ => [Fast_tac 1]); |
23 |
15 |
24 |
16 |
25 goal Denotation.thy "C(WHILE b DO c) = C(IF b THEN c;WHILE b DO c ELSE SKIP)"; |
17 goal Denotation.thy "C(WHILE b DO c) = C(IF b THEN c;WHILE b DO c ELSE SKIP)"; |
26 by(Simp_tac 1); |
18 by(Simp_tac 1); |
27 by(EVERY[stac (Gamma_mono RS lfp_Tarski) 1, |
19 by(EVERY[stac (Gamma_mono RS lfp_Tarski) 1, |
35 |
27 |
36 goal Denotation.thy "!!c s t. <c,s> -c-> t ==> (s,t) : C(c)"; |
28 goal Denotation.thy "!!c s t. <c,s> -c-> t ==> (s,t) : C(c)"; |
37 |
29 |
38 (* start with rule induction *) |
30 (* start with rule induction *) |
39 by (etac evalc.induct 1); |
31 by (etac evalc.induct 1); |
40 by (rewrite_tac (Gamma_def::C_simps)); |
32 auto(); |
41 (* simplification with HOL_ss too agressive *) |
|
42 (* skip *) |
|
43 by (fast_tac denotation_cs 1); |
|
44 (* assign *) |
|
45 by (fast_tac denotation_cs 1); |
|
46 (* comp *) |
|
47 by (fast_tac denotation_cs 1); |
|
48 (* if *) |
|
49 by (fast_tac denotation_cs 1); |
|
50 by (fast_tac denotation_cs 1); |
|
51 (* while *) |
33 (* while *) |
|
34 by(rewtac Gamma_def); |
52 by (rtac (rewrite_rule [Gamma_def] (Gamma_mono RS lfp_Tarski RS ssubst)) 1); |
35 by (rtac (rewrite_rule [Gamma_def] (Gamma_mono RS lfp_Tarski RS ssubst)) 1); |
53 by (fast_tac denotation_cs 1); |
36 by (Fast_tac 1); |
54 by (rtac (rewrite_rule [Gamma_def] (Gamma_mono RS lfp_Tarski RS ssubst)) 1); |
37 by (rtac (rewrite_rule [Gamma_def] (Gamma_mono RS lfp_Tarski RS ssubst)) 1); |
55 by (fast_tac denotation_cs 1); |
38 by (Fast_tac 1); |
56 |
39 |
57 qed "com1"; |
40 qed "com1"; |
58 |
|
59 |
41 |
60 (* Denotational Semantics implies Operational Semantics *) |
42 (* Denotational Semantics implies Operational Semantics *) |
61 |
43 |
62 goal Denotation.thy "!s t. (s,t):C(c) --> <c,s> -c-> t"; |
44 goal Denotation.thy "!s t. (s,t):C(c) --> <c,s> -c-> t"; |
63 by (com.induct_tac "c" 1); |
45 by (com.induct_tac "c" 1); |
64 by (rewrite_tac C_simps); |
46 |
65 by (ALLGOALS (TRY o fast_tac denotation_cs)); |
47 by(ALLGOALS Full_simp_tac); |
|
48 by(ALLGOALS (TRY o Fast_tac)); |
66 |
49 |
67 (* while *) |
50 (* while *) |
68 by (strip_tac 1); |
51 by (strip_tac 1); |
69 by (etac (Gamma_mono RSN (2,induct)) 1); |
52 by (etac (Gamma_mono RSN (2,induct)) 1); |
70 by (rewtac Gamma_def); |
53 by (rewtac Gamma_def); |
71 by (fast_tac denotation_cs 1); |
54 by (Fast_tac 1); |
72 |
55 |
73 qed_spec_mp "com2"; |
56 qed_spec_mp "com2"; |
74 |
57 |
75 |
58 |
76 (**** Proof of Equivalence ****) |
59 (**** Proof of Equivalence ****) |
77 |
60 |
78 goal Denotation.thy "(s,t) : C(c) = (<c,s> -c-> t)"; |
61 goal Denotation.thy "(s,t) : C(c) = (<c,s> -c-> t)"; |
79 by (fast_tac (set_cs addEs [com2] addDs [com1]) 1); |
62 by (fast_tac (!claset addEs [com2] addDs [com1]) 1); |
80 qed "denotational_is_natural"; |
63 qed "denotational_is_natural"; |