author | nipkow |
Fri, 02 Oct 1998 14:28:39 +0200 | |
changeset 5608 | a82a038a3e7a |
parent 5596 | b29d18d8c4d2 |
child 5620 | 3ac11c4af76a |
permissions | -rw-r--r-- |
5111 | 1 |
(* Title: HOL/UNITY/Traces |
2 |
ID: $Id$ |
|
3 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
|
4 |
Copyright 1998 University of Cambridge |
|
5 |
||
6 |
Definitions of |
|
7 |
* traces: the possible execution traces |
|
8 |
* reachable: the set of reachable states |
|
9 |
||
10 |
*) |
|
11 |
||
5596 | 12 |
|
13 |
(*** The abstract type of programs ***) |
|
14 |
||
15 |
val rep_ss = simpset() addsimps |
|
16 |
[Init_def, Acts_def, mk_program_def, Program_def, Rep_Program, |
|
17 |
Rep_Program_inverse, Abs_Program_inverse]; |
|
18 |
||
19 |
||
5608 | 20 |
Goal "Id: Acts prg"; |
5596 | 21 |
by (cut_inst_tac [("x", "prg")] Rep_Program 1); |
22 |
by (auto_tac (claset(), rep_ss)); |
|
5608 | 23 |
qed "Id_in_Acts"; |
24 |
AddIffs [Id_in_Acts]; |
|
5584 | 25 |
|
26 |
||
5596 | 27 |
Goal "Init (mk_program (init,acts)) = init"; |
28 |
by (auto_tac (claset(), rep_ss)); |
|
29 |
qed "Init_eq"; |
|
4776 | 30 |
|
5608 | 31 |
Goal "Acts (mk_program (init,acts)) = insert Id acts"; |
5596 | 32 |
by (auto_tac (claset(), rep_ss)); |
5423 | 33 |
qed "Acts_eq"; |
34 |
||
5596 | 35 |
Addsimps [Acts_eq, Init_eq]; |
36 |
||
5423 | 37 |
|
5596 | 38 |
Goal "[| Init prg = Init prg'; Acts prg = Acts prg' |] ==> prg = prg'"; |
39 |
by (cut_inst_tac [("p", "Rep_Program prg")] surjective_pairing 1); |
|
40 |
by (auto_tac (claset(), rep_ss)); |
|
41 |
by (dres_inst_tac [("f", "Abs_Program")] arg_cong 1); |
|
42 |
by (full_simp_tac (rep_ss addsimps [surjective_pairing RS sym]) 1); |
|
43 |
qed "program_equalityI"; |
|
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
44 |
|
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
45 |
|
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
46 |
(*** These three rules allow "lazy" definition expansion ***) |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
47 |
|
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
48 |
val [rew] = goal thy |
5596 | 49 |
"[| prg == mk_program (init,acts) |] \ |
5608 | 50 |
\ ==> Init prg = init & Acts prg = insert Id acts"; |
5426
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
51 |
by (rewtac rew); |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
52 |
by Auto_tac; |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
53 |
qed "def_prg_simps"; |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
54 |
|
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
55 |
val [rew] = goal thy |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
56 |
"[| act == {(s,s'). P s s'} |] ==> ((s,s') : act) = P s s'"; |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
57 |
by (rewtac rew); |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
58 |
by Auto_tac; |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
59 |
qed "def_act_simp"; |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
60 |
|
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
61 |
fun simp_of_act def = def RS def_act_simp; |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
62 |
|
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
63 |
val [rew] = goal thy |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
64 |
"[| A == B |] ==> (x : A) = (x : B)"; |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
65 |
by (rewtac rew); |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
66 |
by Auto_tac; |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
67 |
qed "def_set_simp"; |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
68 |
|
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
69 |
fun simp_of_set def = def RS def_set_simp; |
566f47250bd0
A new approach, using simp_of_act and simp_of_set to activate definitions when
paulson
parents:
5423
diff
changeset
|
70 |
|
5596 | 71 |
|
72 |
(*** traces and reachable ***) |
|
73 |
||
74 |
Goal "reachable prg = {s. EX evs. (s,evs): traces (Init prg) (Acts prg)}"; |
|
75 |
by Safe_tac; |
|
76 |
by (etac traces.induct 2); |
|
77 |
by (etac reachable.induct 1); |
|
78 |
by (ALLGOALS (blast_tac (claset() addIs (reachable.intrs @ traces.intrs)))); |
|
79 |
qed "reachable_equiv_traces"; |
|
80 |
||
81 |
Goal "acts <= Acts prg ==> stable acts (reachable prg)"; |
|
82 |
by (blast_tac (claset() addIs ([stableI, constrainsI] @ reachable.intrs)) 1); |
|
83 |
qed "stable_reachable"; |