6 For fix.thy. |
6 For fix.thy. |
7 *) |
7 *) |
8 |
8 |
9 open Fix; |
9 open Fix; |
10 |
10 |
11 val prems = goalw Fix.thy [INCL_def] |
|
12 "[| !!x.P(x) <-> Q(x) |] ==> INCL(%x.P(x)) <-> INCL(%x.Q(x))"; |
|
13 by (REPEAT (ares_tac ([refl] @ FOL_congs @ set_congs @ prems) 1)); |
|
14 val INCL_cong = result(); |
|
15 |
|
16 val fix_congs = [INCL_cong] @ ccl_mk_congs Fix.thy ["napply"]; |
|
17 |
|
18 (*** Fixed Point Induction ***) |
11 (*** Fixed Point Induction ***) |
19 |
12 |
20 val [base,step,incl] = goalw Fix.thy [INCL_def] |
13 val [base,step,incl] = goalw Fix.thy [INCL_def] |
21 "[| P(bot); !!x.P(x) ==> P(f(x)); INCL(P) |] ==> P(fix(f))"; |
14 "[| P(bot); !!x.P(x) ==> P(f(x)); INCL(P) |] ==> P(fix(f))"; |
22 br (incl RS spec RS mp) 1; |
15 br (incl RS spec RS mp) 1; |
23 by (rtac (Nat_ind RS ballI) 1 THEN atac 1); |
16 by (rtac (Nat_ind RS ballI) 1 THEN atac 1); |
24 by (ALLGOALS (SIMP_TAC term_ss)); |
17 by (ALLGOALS (simp_tac term_ss)); |
25 by (REPEAT (ares_tac [base,step] 1)); |
18 by (REPEAT (ares_tac [base,step] 1)); |
26 val fix_ind = result(); |
19 val fix_ind = result(); |
27 |
20 |
28 (*** Inclusive Predicates ***) |
21 (*** Inclusive Predicates ***) |
29 |
22 |
46 val incl::prems = goal Fix.thy |
39 val incl::prems = goal Fix.thy |
47 "[| INCL(P); (ALL n:Nat.P(f^n`bot))-->P(fix(f)) ==> R |] ==> R"; |
40 "[| INCL(P); (ALL n:Nat.P(f^n`bot))-->P(fix(f)) ==> R |] ==> R"; |
48 by (fast_tac (term_cs addIs ([incl RS inclD] @ prems)) 1); |
41 by (fast_tac (term_cs addIs ([incl RS inclD] @ prems)) 1); |
49 val inclE = result(); |
42 val inclE = result(); |
50 |
43 |
51 val fix_ss = term_ss addcongs fix_congs; |
|
52 |
44 |
53 (*** Lemmas for Inclusive Predicates ***) |
45 (*** Lemmas for Inclusive Predicates ***) |
54 |
46 |
55 goal Fix.thy "INCL(%x.~ a(x) [= t)"; |
47 goal Fix.thy "INCL(%x.~ a(x) [= t)"; |
56 br inclI 1; |
48 br inclI 1; |
74 val prems = goal Fix.thy "[| !!a.a:A ==> INCL(P(a)) |] ==> INCL(%x.ALL a:A.P(a,x))"; |
66 val prems = goal Fix.thy "[| !!a.a:A ==> INCL(P(a)) |] ==> INCL(%x.ALL a:A.P(a,x))"; |
75 by (fast_tac (set_cs addSIs ([inclI] @ (prems RL [inclD]))) 1);; |
67 by (fast_tac (set_cs addSIs ([inclI] @ (prems RL [inclD]))) 1);; |
76 val ball_INCL = result(); |
68 val ball_INCL = result(); |
77 |
69 |
78 goal Fix.thy "INCL(%x.a(x) = b(x)::'a::prog)"; |
70 goal Fix.thy "INCL(%x.a(x) = b(x)::'a::prog)"; |
79 by (SIMP_TAC (fix_ss addrews [eq_iff]) 1); |
71 by (simp_tac (term_ss addsimps [eq_iff]) 1); |
80 by (REPEAT (resolve_tac [conj_INCL,po_INCL] 1)); |
72 by (REPEAT (resolve_tac [conj_INCL,po_INCL] 1)); |
81 val eq_INCL = result(); |
73 val eq_INCL = result(); |
82 |
74 |
83 (*** Derivation of Reachability Condition ***) |
75 (*** Derivation of Reachability Condition ***) |
84 |
76 |
87 goal Fix.thy "idgen(fix(idgen)) = fix(idgen)"; |
79 goal Fix.thy "idgen(fix(idgen)) = fix(idgen)"; |
88 br (fixB RS sym) 1; |
80 br (fixB RS sym) 1; |
89 val fix_idgenfp = result(); |
81 val fix_idgenfp = result(); |
90 |
82 |
91 goalw Fix.thy [idgen_def] "idgen(lam x.x) = lam x.x"; |
83 goalw Fix.thy [idgen_def] "idgen(lam x.x) = lam x.x"; |
92 by (SIMP_TAC term_ss 1); |
84 by (simp_tac term_ss 1); |
93 br (term_case RS allI) 1; |
85 br (term_case RS allI) 1; |
94 by (ALLGOALS (SIMP_TAC term_ss)); |
86 by (ALLGOALS (simp_tac term_ss)); |
95 val id_idgenfp = result(); |
87 val id_idgenfp = result(); |
96 |
88 |
97 (* All fixed points are lam-expressions *) |
89 (* All fixed points are lam-expressions *) |
98 |
90 |
99 val [prem] = goal Fix.thy "idgen(d) = d ==> d = lam x.?f(x)"; |
91 val [prem] = goal Fix.thy "idgen(d) = d ==> d = lam x.?f(x)"; |
104 |
96 |
105 (* Lemmas for rewriting fixed points of idgen *) |
97 (* Lemmas for rewriting fixed points of idgen *) |
106 |
98 |
107 val prems = goalw Fix.thy [idgen_def] |
99 val prems = goalw Fix.thy [idgen_def] |
108 "[| a = b; a ` t = u |] ==> b ` t = u"; |
100 "[| a = b; a ` t = u |] ==> b ` t = u"; |
109 by (SIMP_TAC (term_ss addrews (prems RL [sym])) 1); |
101 by (simp_tac (term_ss addsimps (prems RL [sym])) 1); |
110 val l_lemma= result(); |
102 val l_lemma= result(); |
111 |
103 |
112 val idgen_lemmas = |
104 val idgen_lemmas = |
113 let fun mk_thm s = prove_goalw Fix.thy [idgen_def] s |
105 let fun mk_thm s = prove_goalw Fix.thy [idgen_def] s |
114 (fn [prem] => [rtac (prem RS l_lemma) 1,SIMP_TAC term_ss 1]) |
106 (fn [prem] => [rtac (prem RS l_lemma) 1,simp_tac term_ss 1]) |
115 in map mk_thm |
107 in map mk_thm |
116 [ "idgen(d) = d ==> d ` bot = bot", |
108 [ "idgen(d) = d ==> d ` bot = bot", |
117 "idgen(d) = d ==> d ` true = true", |
109 "idgen(d) = d ==> d ` true = true", |
118 "idgen(d) = d ==> d ` false = false", |
110 "idgen(d) = d ==> d ` false = false", |
119 "idgen(d) = d ==> d ` <a,b> = <d ` a,d ` b>", |
111 "idgen(d) = d ==> d ` <a,b> = <d ` a,d ` b>", |
139 "idgen(d) = d ==> \ |
131 "idgen(d) = d ==> \ |
140 \ {p.EX a b.p=<a,b> & (EX t.a=fix(idgen) ` t & b = d ` t)} <= \ |
132 \ {p.EX a b.p=<a,b> & (EX t.a=fix(idgen) ` t & b = d ` t)} <= \ |
141 \ POgen({p.EX a b.p=<a,b> & (EX t.a=fix(idgen) ` t & b = d ` t)})"; |
133 \ POgen({p.EX a b.p=<a,b> & (EX t.a=fix(idgen) ` t & b = d ` t)})"; |
142 by (REPEAT (step_tac term_cs 1)); |
134 by (REPEAT (step_tac term_cs 1)); |
143 by (term_case_tac "t" 1); |
135 by (term_case_tac "t" 1); |
144 by (ALLGOALS (SIMP_TAC (term_ss addrews (POgenXH::([prem,fix_idgenfp] RL idgen_lemmas))))); |
136 by (ALLGOALS (simp_tac (term_ss addsimps (POgenXH::([prem,fix_idgenfp] RL idgen_lemmas))))); |
145 by (ALLGOALS (fast_tac set_cs)); |
137 by (ALLGOALS (fast_tac set_cs)); |
146 val lemma1 = result(); |
138 val lemma1 = result(); |
147 |
139 |
148 val [prem] = goal Fix.thy |
140 val [prem] = goal Fix.thy |
149 "idgen(d) = d ==> fix(idgen) [= d"; |
141 "idgen(d) = d ==> fix(idgen) [= d"; |
155 val [prem] = goal Fix.thy |
147 val [prem] = goal Fix.thy |
156 "idgen(d) = d ==> \ |
148 "idgen(d) = d ==> \ |
157 \ {p.EX a b.p=<a,b> & b = d ` a} <= POgen({p.EX a b.p=<a,b> & b = d ` a})"; |
149 \ {p.EX a b.p=<a,b> & b = d ` a} <= POgen({p.EX a b.p=<a,b> & b = d ` a})"; |
158 by (REPEAT (step_tac term_cs 1)); |
150 by (REPEAT (step_tac term_cs 1)); |
159 by (term_case_tac "a" 1); |
151 by (term_case_tac "a" 1); |
160 by (ALLGOALS (SIMP_TAC (term_ss addrews (POgenXH::([prem] RL idgen_lemmas))))); |
152 by (ALLGOALS (simp_tac (term_ss addsimps (POgenXH::([prem] RL idgen_lemmas))))); |
161 by (ALLGOALS (fast_tac set_cs)); |
153 by (ALLGOALS (fast_tac set_cs)); |
162 val lemma2 = result(); |
154 val lemma2 = result(); |
163 |
155 |
164 val [prem] = goal Fix.thy |
156 val [prem] = goal Fix.thy |
165 "idgen(d) = d ==> lam x.x [= d"; |
157 "idgen(d) = d ==> lam x.x [= d"; |
166 br (allI RS po_eta) 1; |
158 br (allI RS po_eta) 1; |
167 br (lemma2 RSN(2,po_coinduct)) 1; |
159 br (lemma2 RSN(2,po_coinduct)) 1; |
168 by (SIMP_TAC term_ss 1); |
160 by (simp_tac term_ss 1); |
169 by (ALLGOALS (fast_tac (term_cs addIs [prem,po_eta_lemma,fix_idgenfp]))); |
161 by (ALLGOALS (fast_tac (term_cs addIs [prem,po_eta_lemma,fix_idgenfp]))); |
170 val id_least_idgen = result(); |
162 val id_least_idgen = result(); |
171 |
163 |
172 goal Fix.thy "fix(idgen) = lam x.x"; |
164 goal Fix.thy "fix(idgen) = lam x.x"; |
173 by (fast_tac (term_cs addIs [eq_iff RS iffD2, |
165 by (fast_tac (term_cs addIs [eq_iff RS iffD2, |
194 by (REPEAT_SOME (ares_tac [allI])); |
186 by (REPEAT_SOME (ares_tac [allI])); |
195 br (applyBbot RS ssubst) 1; |
187 br (applyBbot RS ssubst) 1; |
196 brs prems 1; |
188 brs prems 1; |
197 br (applyB RS ssubst )1; |
189 br (applyB RS ssubst )1; |
198 by (res_inst_tac [("t","xa")] term_case 1); |
190 by (res_inst_tac [("t","xa")] term_case 1); |
199 by (ALLGOALS (SIMP_TAC term_ss)); |
191 by (ALLGOALS (simp_tac term_ss)); |
200 by (ALLGOALS (fast_tac (term_cs addIs ([all_INCL,INCL_subst] @ prems)))); |
192 by (ALLGOALS (fast_tac (term_cs addIs ([all_INCL,INCL_subst] @ prems)))); |
201 val term_ind = result(); |
193 val term_ind = result(); |
202 |
194 |