author | oheimb |
Thu, 31 May 2001 16:52:47 +0200 | |
changeset 11348 | e08a0855af67 |
parent 10835 | f4745d77e620 |
child 11355 | 778c369559d9 |
permissions | -rw-r--r-- |
9169 | 1 |
(* Title: HOLCF/ex//Stream.ML |
2 |
ID: $Id$ |
|
2570 | 3 |
Author: Franz Regensburger, David von Oheimb |
4 |
Copyright 1993, 1995 Technische Universitaet Muenchen |
|
11348 | 5 |
Author: David von Oheimb (major extensions) |
6 |
License: GPL (GNU GENERAL PUBLIC LICENSE) |
|
2570 | 7 |
|
9169 | 8 |
general Stream domain |
2570 | 9 |
*) |
10 |
||
4044 | 11 |
fun stream_case_tac s i = res_inst_tac [("x",s)] stream.casedist i |
2570 | 12 |
THEN hyp_subst_tac i THEN hyp_subst_tac (i+1); |
13 |
||
14 |
||
9169 | 15 |
val [stream_con_rew1,stream_con_rew2] = stream.con_rews; |
16 |
||
11348 | 17 |
Addsimps stream.rews; |
18 |
Addsimps[eq_UU_iff RS sym]; |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
19 |
|
2570 | 20 |
(* ----------------------------------------------------------------------- *) |
21 |
(* theorems about scons *) |
|
22 |
(* ----------------------------------------------------------------------- *) |
|
23 |
||
24 |
section "scons"; |
|
25 |
||
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
26 |
Goal "a && s = UU = (a = UU)"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
27 |
by Safe_tac; |
10230 | 28 |
by (etac contrapos_pp 1); |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
29 |
by (safe_tac (claset() addSIs stream.con_rews)); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
30 |
qed "scons_eq_UU"; |
2570 | 31 |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
32 |
Goal "[| a && x = UU; a ~= UU |] ==> R"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
33 |
by (dresolve_tac [stream_con_rew2] 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
34 |
by (contr_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
35 |
qed "scons_not_empty"; |
2570 | 36 |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
37 |
Goal "x ~= UU = (EX a y. a ~= UU & x = a && y)"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
38 |
by (cut_facts_tac [stream.exhaust] 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
39 |
by (best_tac (claset() addDs [stream_con_rew2]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
40 |
qed "stream_exhaust_eq"; |
2570 | 41 |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
42 |
Goal |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
43 |
"[| a && s << t; a ~= UU |] ==> EX b tt. t = b && tt & b ~= UU & s << tt"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
44 |
by (stream_case_tac "t" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
45 |
by (fast_tac (claset() addDs [eq_UU_iff RS iffD2, stream_con_rew2]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
46 |
by (fast_tac (claset() addDs stream.inverts) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
47 |
qed "stream_prefix"; |
2570 | 48 |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
49 |
Goal "[| x && xs << y && ys; (x::'a::flat) ~= UU|] ==> x = y & xs << ys"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
50 |
by (cut_inst_tac [("x1","x::'a::flat"), ("x","y::'a::flat")] |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
51 |
(ax_flat RS spec RS spec) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
52 |
by (forward_tac stream.inverts 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
53 |
by Safe_tac; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
54 |
by (dtac (hd stream.con_rews RS subst) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
55 |
by (fast_tac (claset() addDs [eq_UU_iff RS iffD2, stream_con_rew2]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
56 |
qed "stream_flat_prefix"; |
2570 | 57 |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
58 |
Goal "b ~= UU ==> x << b && z = \ |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
59 |
\ (x = UU | (EX a y. x = a && y & a ~= UU & a << b & y << z))"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
60 |
by Safe_tac; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
61 |
by (stream_case_tac "x" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
62 |
by (safe_tac (claset() addSDs stream.inverts |
11348 | 63 |
addSIs [monofun_cfun, monofun_cfun_arg])); |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
64 |
by (Fast_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
65 |
qed "stream_prefix'"; |
2570 | 66 |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
67 |
Goal "[| a ~= UU; b ~= UU |] ==> (a && s = b && t) = (a = b & s = t)"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
68 |
by (best_tac (claset() addSEs stream.injects) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
69 |
qed "stream_inject_eq"; |
11348 | 70 |
Addsimps [stream_inject_eq]; |
2570 | 71 |
|
72 |
||
73 |
(* ----------------------------------------------------------------------- *) |
|
74 |
(* theorems about stream_when *) |
|
75 |
(* ----------------------------------------------------------------------- *) |
|
76 |
||
77 |
section "stream_when"; |
|
78 |
||
10835 | 79 |
Goal "stream_when$UU$s=UU"; |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
80 |
by (stream_case_tac "s" 1); |
11348 | 81 |
by (ALLGOALS Asm_simp_tac); |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
82 |
qed "stream_when_strictf"; |
2570 | 83 |
|
84 |
||
85 |
(* ----------------------------------------------------------------------- *) |
|
86 |
(* theorems about ft and rt *) |
|
87 |
(* ----------------------------------------------------------------------- *) |
|
88 |
||
89 |
section "ft & rt"; |
|
90 |
||
91 |
(* |
|
10835 | 92 |
Goal "ft$s=UU --> s=UU"; |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
93 |
by (stream_case_tac "s" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
94 |
by (REPEAT (asm_simp_tac (simpset() addsimps stream.rews) 1)); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
95 |
qed "stream_ft_lemma1"; |
2570 | 96 |
*) |
97 |
||
10835 | 98 |
Goal "s~=UU ==> ft$s~=UU"; |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
99 |
by (stream_case_tac "s" 1); |
11348 | 100 |
by (Blast_tac 1); |
101 |
by (Asm_simp_tac 1); |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
102 |
qed "ft_defin"; |
2570 | 103 |
|
10835 | 104 |
Goal "rt$s~=UU ==> s~=UU"; |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
105 |
by Auto_tac; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
106 |
qed "rt_strict_rev"; |
2570 | 107 |
|
10835 | 108 |
Goal "(ft$s)&&(rt$s)=s"; |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
109 |
by (stream_case_tac "s" 1); |
11348 | 110 |
by (ALLGOALS Asm_simp_tac); |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
111 |
qed "surjectiv_scons"; |
2570 | 112 |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
113 |
Goal "ALL x s. x << s --> iterate i rt x << iterate i rt s"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
114 |
by (induct_tac "i" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
115 |
by (Simp_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
116 |
by (strip_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
117 |
by (stream_case_tac "x" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
118 |
by (rtac (minimal RS (monofun_iterate2 RS monofunE RS spec RS spec RS mp))1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
119 |
by (dtac stream_prefix 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
120 |
by Safe_tac; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
121 |
by (asm_simp_tac (HOL_ss addsimps iterate_Suc2::stream.rews) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
122 |
qed_spec_mp "monofun_rt_mult"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
123 |
|
2570 | 124 |
|
125 |
||
126 |
(* ----------------------------------------------------------------------- *) |
|
127 |
(* theorems about stream_take *) |
|
128 |
(* ----------------------------------------------------------------------- *) |
|
129 |
||
130 |
section "stream_take"; |
|
131 |
||
10835 | 132 |
Goal "(LUB i. stream_take i$s) = s"; |
133 |
by (subgoal_tac "(LUB i. stream_take i$s) = fix$stream_copy$s" 1); |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
134 |
by (simp_tac (simpset() addsimps [fix_def2, stream.take_def, |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
135 |
contlub_cfun_fun, chain_iterate]) 2); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
136 |
by (asm_full_simp_tac (simpset() addsimps [stream.reach]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
137 |
qed "stream_reach2"; |
2570 | 138 |
|
10835 | 139 |
Goal "chain (%i. stream_take i$s)"; |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
140 |
by (rtac chainI 1); |
11348 | 141 |
by (subgoal_tac "ALL i s::'a stream. stream_take i$s << stream_take (Suc i)$s" 1); |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
142 |
by (Fast_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
143 |
by (rtac allI 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
144 |
by (induct_tac "ia" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
145 |
by (Simp_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
146 |
by (rtac allI 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
147 |
by (stream_case_tac "s" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
148 |
by (Simp_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
149 |
by (asm_simp_tac (simpset() addsimps [monofun_cfun_arg]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
150 |
qed "chain_stream_take"; |
2570 | 151 |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
152 |
|
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
153 |
Goalw [stream.take_def] |
10835 | 154 |
"stream_take n$x = x ==> stream_take (Suc n)$x = x"; |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
155 |
by (rtac antisym_less 1); |
10835 | 156 |
by (subgoal_tac "iterate (Suc n) stream_copy UU$x << fix$stream_copy$x" 1); |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
157 |
by (asm_full_simp_tac (simpset() addsimps [stream.reach]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
158 |
by (rtac monofun_cfun_fun 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
159 |
by (stac fix_def2 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
160 |
by (rtac is_ub_thelub 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
161 |
by (rtac chain_iterate 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
162 |
by (etac subst 1 THEN rtac monofun_cfun_fun 1); |
11348 | 163 |
by (rtac (rewrite_rule [chain_def] chain_iterate RS spec) 1); |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
164 |
qed "stream_take_more"; |
2570 | 165 |
|
166 |
(* |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
167 |
Goal |
10835 | 168 |
"ALL s2. stream_take n$s2 = s2 --> stream_take (Suc n)$s2=s2"; |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
169 |
by (induct_tac "n" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
170 |
by (simp_tac (simpset() addsimps stream_rews) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
171 |
by (strip_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
172 |
by (hyp_subst_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
173 |
by (simp_tac (simpset() addsimps stream_rews) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
174 |
by (rtac allI 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
175 |
by (res_inst_tac [("s","s2")] streamE 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
176 |
by (asm_simp_tac (simpset() addsimps stream_rews) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
177 |
by (asm_simp_tac (simpset() addsimps stream_rews) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
178 |
by (strip_tac 1 ); |
10835 | 179 |
by (subgoal_tac "stream_take n1$xs = xs" 1); |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
180 |
by (rtac ((hd stream_inject) RS conjunct2) 2); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
181 |
by (atac 4); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
182 |
by (atac 2); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
183 |
by (atac 2); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
184 |
by (rtac cfun_arg_cong 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
185 |
by (Blast_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
186 |
qed "stream_take_lemma2"; |
2570 | 187 |
*) |
188 |
||
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
189 |
Goal |
11348 | 190 |
"ALL x xs. x~=UU --> stream_take n$(x && xs) = x && xs --> stream_take n$xs=xs"; |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
191 |
by (induct_tac "n" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
192 |
by (Asm_simp_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
193 |
by (strip_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
194 |
by (res_inst_tac [("P","x && xs=UU")] notE 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
195 |
by (eresolve_tac stream.con_rews 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
196 |
by (etac sym 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
197 |
by (strip_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
198 |
by (rtac stream_take_more 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
199 |
by (res_inst_tac [("a1","x")] ((hd stream.injects) RS conjunct2) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
200 |
by (assume_tac 3); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
201 |
by (etac (hd(tl(tl(stream.take_rews))) RS subst) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
202 |
by (atac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
203 |
qed_spec_mp "stream_take_lemma3"; |
2570 | 204 |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
205 |
Goal |
10835 | 206 |
"ALL x xs. stream_take n$xs=xs --> stream_take (Suc n)$(x && xs) = x && xs"; |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
207 |
by (induct_tac "n" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
208 |
by Auto_tac; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
209 |
qed_spec_mp "stream_take_lemma4"; |
2570 | 210 |
|
211 |
||
212 |
(* ------------------------------------------------------------------------- *) |
|
213 |
(* special induction rules *) |
|
214 |
(* ------------------------------------------------------------------------- *) |
|
215 |
||
216 |
section "induction"; |
|
217 |
||
218 |
||
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
219 |
val prems = Goalw [stream.finite_def] |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
220 |
"[| stream_finite x; \ |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
221 |
\ P UU; \ |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
222 |
\ !!a s. [| a ~= UU; P s |] \ |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
223 |
\ ==> P (a && s) |] ==> P x"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
224 |
by (cut_facts_tac prems 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
225 |
by (etac exE 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
226 |
by (etac subst 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
227 |
by (rtac stream.finite_ind 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
228 |
by (atac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
229 |
by (eresolve_tac prems 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
230 |
by (atac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
231 |
qed "stream_finite_ind"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
232 |
|
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
233 |
val major::prems = Goal |
2570 | 234 |
"[| P UU;\ |
235 |
\ !! x . x ~= UU ==> P (x && UU); \ |
|
236 |
\ !! y z s. [| y ~= UU; z ~= UU; P s |] ==> P (y && z && s ) \ |
|
10835 | 237 |
\ |] ==> !s. P (stream_take n$s)"; |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
238 |
by (res_inst_tac [("n","n")] nat_induct2 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
239 |
by (asm_simp_tac (simpset() addsimps [major]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
240 |
by (rtac allI 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
241 |
by (stream_case_tac "s" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
242 |
by (asm_simp_tac (simpset() addsimps [major]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
243 |
by (asm_simp_tac (simpset() addsimps prems) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
244 |
by (rtac allI 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
245 |
by (stream_case_tac "s" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
246 |
by (asm_simp_tac (simpset() addsimps [major]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
247 |
by (res_inst_tac [("x","sa")] stream.casedist 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
248 |
by (asm_simp_tac (simpset() addsimps prems) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
249 |
by (asm_simp_tac (simpset() addsimps prems) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
250 |
qed "stream_finite_ind2"; |
2570 | 251 |
|
252 |
||
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
253 |
val prems = Goal |
2570 | 254 |
"[| adm P; P UU; !!a. a ~= UU ==> P (a && UU); \ |
255 |
\ !!a b s. [| a ~= UU; b ~= UU; P s |] ==> P (a && b && s)\ |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
256 |
\ |] ==> P x"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
257 |
by (rtac (stream.reach RS subst) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
258 |
by (rtac (adm_impl_admw RS wfix_ind) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
259 |
by (rtac adm_subst 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
260 |
by (cont_tacR 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
261 |
by (resolve_tac prems 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
262 |
by (rtac allI 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
263 |
by (rtac (rewrite_rule [stream.take_def] stream_finite_ind2 RS spec) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
264 |
by (resolve_tac prems 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
265 |
by (eresolve_tac prems 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
266 |
by (eresolve_tac prems 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
267 |
by (atac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
268 |
by (atac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
269 |
qed "stream_ind2"; |
2570 | 270 |
|
271 |
||
272 |
(* ----------------------------------------------------------------------- *) |
|
273 |
(* simplify use of coinduction *) |
|
274 |
(* ----------------------------------------------------------------------- *) |
|
275 |
||
276 |
section "coinduction"; |
|
277 |
||
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
278 |
|
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
279 |
Goalw [stream.bisim_def] |
10835 | 280 |
"!s1 s2. R s1 s2 --> ft$s1 = ft$s2 & R (rt$s1) (rt$s2) ==> stream_bisim R"; |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
281 |
by (strip_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
282 |
by (etac allE 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
283 |
by (etac allE 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
284 |
by (dtac mp 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
285 |
by (atac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
286 |
by (etac conjE 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
287 |
by (case_tac "x = UU & x' = UU" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
288 |
by (rtac disjI1 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
289 |
by (Blast_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
290 |
by (rtac disjI2 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
291 |
by (rtac disjE 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
292 |
by (etac (de_Morgan_conj RS subst) 1); |
10835 | 293 |
by (res_inst_tac [("x","ft$x")] exI 1); |
294 |
by (res_inst_tac [("x","rt$x")] exI 1); |
|
295 |
by (res_inst_tac [("x","rt$x'")] exI 1); |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
296 |
by (rtac conjI 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
297 |
by (etac ft_defin 1); |
11348 | 298 |
by (asm_simp_tac (simpset() addsimps [surjectiv_scons]) 1); |
10835 | 299 |
by (eres_inst_tac [("s","ft$x"),("t","ft$x'")] subst 1); |
11348 | 300 |
by (simp_tac (simpset() addsimps [surjectiv_scons]) 1); |
10835 | 301 |
by (res_inst_tac [("x","ft$x'")] exI 1); |
302 |
by (res_inst_tac [("x","rt$x")] exI 1); |
|
303 |
by (res_inst_tac [("x","rt$x'")] exI 1); |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
304 |
by (rtac conjI 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
305 |
by (etac ft_defin 1); |
11348 | 306 |
by (asm_simp_tac (simpset() addsimps [surjectiv_scons]) 1); |
10835 | 307 |
by (res_inst_tac [("s","ft$x"),("t","ft$x'")] ssubst 1); |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
308 |
by (etac sym 1); |
11348 | 309 |
by (simp_tac (simpset() addsimps [surjectiv_scons]) 1); |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
310 |
qed "stream_coind_lemma2"; |
2570 | 311 |
|
312 |
(* ----------------------------------------------------------------------- *) |
|
313 |
(* theorems about stream_finite *) |
|
314 |
(* ----------------------------------------------------------------------- *) |
|
315 |
||
316 |
section "stream_finite"; |
|
317 |
||
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
318 |
|
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
319 |
Goalw [stream.finite_def] "stream_finite UU"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
320 |
by (rtac exI 1); |
11348 | 321 |
by (Simp_tac 1); |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
322 |
qed "stream_finite_UU"; |
2570 | 323 |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
324 |
Goal "~ stream_finite s ==> s ~= UU"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
325 |
by (blast_tac (claset() addIs [stream_finite_UU]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
326 |
qed "stream_finite_UU_rev"; |
2570 | 327 |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
328 |
Goalw [stream.finite_def] "stream_finite xs ==> stream_finite (x && xs)"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
329 |
by (blast_tac (claset() addIs [stream_take_lemma4]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
330 |
qed "stream_finite_lemma1"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
331 |
|
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
332 |
Goalw [stream.finite_def] |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
333 |
"[| x ~= UU; stream_finite (x && xs) |] ==> stream_finite xs"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
334 |
by (blast_tac (claset() addIs [stream_take_lemma3]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
335 |
qed "stream_finite_lemma2"; |
2570 | 336 |
|
10835 | 337 |
Goal "stream_finite (rt$s) = stream_finite s"; |
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
338 |
by (stream_case_tac "s" 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
339 |
by (simp_tac (simpset() addsimps [stream_finite_UU]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
340 |
by (Asm_simp_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
341 |
by (fast_tac (claset() addIs [stream_finite_lemma1] |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
342 |
addDs [stream_finite_lemma2]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
343 |
qed "stream_finite_rt_eq"; |
2570 | 344 |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
345 |
Goal "stream_finite s ==> !t. t<<s --> stream_finite t"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
346 |
by (eres_inst_tac [("x","s")] stream_finite_ind 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
347 |
by (strip_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
348 |
by (dtac UU_I 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
349 |
by (asm_simp_tac (simpset() addsimps [stream_finite_UU]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
350 |
by (strip_tac 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
351 |
by (asm_full_simp_tac (simpset() addsimps [stream_prefix']) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
352 |
by (fast_tac (claset() addSIs [stream_finite_UU, stream_finite_lemma1]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
353 |
qed_spec_mp "stream_finite_less"; |
2570 | 354 |
|
9248
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
355 |
Goal "adm (%x. ~ stream_finite x)"; |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
356 |
by (rtac admI2 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
357 |
by (best_tac (claset() addIs [stream_finite_less, is_ub_thelub]) 1); |
e1dee89de037
massive tidy-up: goal -> Goal, remove use of prems, etc.
paulson
parents:
9169
diff
changeset
|
358 |
qed "adm_not_stream_finite"; |
11348 | 359 |
|
360 |
section "smap"; |
|
361 |
||
362 |
bind_thm ("smap_unfold", fix_prover2 thy smap_def |
|
363 |
"smap = (\\<Lambda>f s. case s of x && l => f\\<cdot>x && smap\\<cdot>f\\<cdot>l)"); |
|
364 |
||
365 |
Goal "smap\\<cdot>f\\<cdot>\\<bottom> = \\<bottom>"; |
|
366 |
by (stac smap_unfold 1); |
|
367 |
by (Simp_tac 1); |
|
368 |
qed "smap_empty"; |
|
369 |
||
370 |
Goal "x~=\\<bottom> ==> smap\\<cdot>f\\<cdot>(x&&xs) = (f\\<cdot>x)&&(smap\\<cdot>f\\<cdot>xs)"; |
|
371 |
by (rtac trans 1); |
|
372 |
by (stac smap_unfold 1); |
|
373 |
by (Asm_simp_tac 1); |
|
374 |
by (rtac refl 1); |
|
375 |
qed "smap_scons"; |
|
376 |
||
377 |
Addsimps [smap_empty, smap_scons]; |
|
378 |
||
379 |
(* ------------------------------------------------------------------------- *) |
|
380 |
||
381 |
section "slen"; |
|
382 |
||
383 |
Goalw [slen_def, stream.finite_def] "#\\<bottom> = 0"; |
|
384 |
by (Simp_tac 1); |
|
385 |
by (stac Least_equality 1); |
|
386 |
by Auto_tac; |
|
387 |
by (simp_tac(simpset() addsimps [Fin_0]) 1); |
|
388 |
qed "slen_empty"; |
|
389 |
||
390 |
Goalw [slen_def] "x ~= \\<bottom> ==> #(x&&xs) = iSuc (#xs)"; |
|
391 |
by (res_inst_tac [("Q1","stream_finite (x && xs)")] (split_if RS iffD2) 1); |
|
392 |
by Safe_tac; |
|
393 |
by (rtac (split_if RS iffD2) 2); |
|
394 |
by Safe_tac; |
|
395 |
by (fast_tac (claset() addIs [stream_finite_lemma1]) 2); |
|
396 |
by (rtac (iSuc_Infty RS sym) 2); |
|
397 |
by (rtac (split_if RS iffD2) 1); |
|
398 |
by (Simp_tac 1); |
|
399 |
by Safe_tac; |
|
400 |
by (eatac stream_finite_lemma2 1 2); |
|
401 |
by (rewtac stream.finite_def); |
|
402 |
by (Clarify_tac 1); |
|
403 |
by (eatac Least_Suc2 1 1); |
|
404 |
by (rtac not_sym 1); |
|
405 |
by Auto_tac; |
|
406 |
qed "slen_scons"; |
|
407 |
||
408 |
Addsimps [slen_empty, slen_scons]; |
|
409 |
||
410 |
Goal "#x < Fin 1 = (x = UU)"; |
|
411 |
by (stream_case_tac "x" 1); |
|
412 |
by (auto_tac (claset(), simpset() delsimps [iSuc_Fin] addsimps |
|
413 |
[Fin_0, iSuc_Fin RS sym,i0_iless_iSuc, iSuc_mono])); |
|
414 |
qed "slen_less_1_eq"; |
|
415 |
||
416 |
Goal "(#x = 0) = (x = \\<bottom>)"; |
|
417 |
by Auto_tac; |
|
418 |
by (stream_case_tac "x" 1); |
|
419 |
by (rotate_tac ~1 2); |
|
420 |
by Auto_tac; |
|
421 |
qed "slen_empty_eq"; |
|
422 |
||
423 |
Goal "Fin (Suc n) < #x = (? a y. x = a && y & a ~= \\<bottom> & Fin n < #y)"; |
|
424 |
by (stream_case_tac "x" 1); |
|
425 |
by (auto_tac (claset(), simpset() delsimps [iSuc_Fin] addsimps |
|
426 |
[iSuc_Fin RS sym, iSuc_mono])); |
|
427 |
by (dtac sym 1); |
|
428 |
by (rotate_tac 2 2); |
|
429 |
by Auto_tac; |
|
430 |
qed "slen_scons_eq"; |
|
431 |
||
432 |
||
433 |
Goal "#x = iSuc n --> (? a y. x = a&&y & a ~= \\<bottom> & #y = n)"; |
|
434 |
by (stream_case_tac "x" 1); |
|
435 |
by Auto_tac; |
|
436 |
qed_spec_mp "slen_iSuc"; |
|
437 |
||
438 |
||
439 |
Goal |
|
440 |
"#x < Fin (Suc (Suc n)) = (!a y. x ~= a && y | a = \\<bottom> | #y < Fin (Suc n))"; |
|
441 |
by (stac (iSuc_Fin RS sym) 1); |
|
442 |
by (stac (iSuc_Fin RS sym) 1); |
|
443 |
by (safe_tac HOL_cs); |
|
444 |
by (rotate_tac ~1 1); |
|
445 |
by (asm_full_simp_tac (HOL_ss addsimps [slen_scons, iSuc_mono]) 1); |
|
446 |
by (Asm_full_simp_tac 1); |
|
447 |
by (stream_case_tac "x" 1); |
|
448 |
by ( simp_tac (HOL_ss addsimps [slen_empty, i0_iless_iSuc]) 1); |
|
449 |
by (asm_simp_tac (HOL_ss addsimps [slen_scons, iSuc_mono]) 1); |
|
450 |
by (etac allE 1); |
|
451 |
by (etac allE 1); |
|
452 |
by (safe_tac HOL_cs); |
|
453 |
by ( contr_tac 2); |
|
454 |
by ( fast_tac HOL_cs 1); |
|
455 |
by (Asm_full_simp_tac 1); |
|
456 |
qed "slen_scons_eq_rev"; |
|
457 |
||
458 |
Goal "!x. Fin n < #x = (stream_take n\\<cdot>x ~= x)"; |
|
459 |
by (nat_ind_tac "n" 1); |
|
460 |
by (simp_tac(simpset() addsimps [slen_empty_eq, Fin_0]) 1); |
|
461 |
by (Fast_tac 1); |
|
462 |
by (rtac allI 1); |
|
463 |
by (asm_simp_tac (simpset() addsimps [slen_scons_eq]) 1); |
|
464 |
by (etac thin_rl 1); |
|
465 |
by (safe_tac HOL_cs); |
|
466 |
by (Asm_full_simp_tac 1); |
|
467 |
by (stream_case_tac "x" 1); |
|
468 |
by (rotate_tac ~1 2); |
|
469 |
by Auto_tac; |
|
470 |
qed_spec_mp "slen_take_eq"; |
|
471 |
||
472 |
Goalw [ile_def] "#x <= Fin n = (stream_take n\\<cdot>x = x)"; |
|
473 |
by (simp_tac (simpset() addsimps [slen_take_eq]) 1); |
|
474 |
qed "slen_take_eq_rev"; |
|
475 |
||
476 |
Goal "#x = Fin n ==> stream_take n\\<cdot>x = x"; |
|
477 |
by (asm_simp_tac (simpset() addsimps [slen_take_eq_rev RS sym]) 1); |
|
478 |
qed "slen_take_lemma1"; |
|
479 |
||
480 |
Goal "!x. ~stream_finite x --> #(stream_take i\\<cdot>x) = Fin i"; |
|
481 |
by (nat_ind_tac "i" 1); |
|
482 |
by (simp_tac(simpset() addsimps [Fin_0]) 1); |
|
483 |
by (rtac allI 1); |
|
484 |
by (stream_case_tac "x" 1); |
|
485 |
by (auto_tac (claset()addSIs [stream_finite_lemma1], simpset() delsimps [iSuc_Fin] addsimps [iSuc_Fin RS sym])); |
|
486 |
by (force_tac (claset(), simpset() addsimps [stream.finite_def]) 1); |
|
487 |
qed_spec_mp "slen_take_lemma2"; |
|
488 |
||
489 |
Goal "stream_finite x = (#x ~= Infty)"; |
|
490 |
by (rtac iffI 1); |
|
491 |
by (etac stream_finite_ind 1); |
|
492 |
by (Simp_tac 1); |
|
493 |
by (etac (slen_scons RS ssubst) 1); |
|
494 |
by (stac (iSuc_Infty RS sym) 1); |
|
495 |
by (etac contrapos_nn 1); |
|
496 |
by (etac (iSuc_inject RS iffD1) 1); |
|
497 |
by (case_tac "#x" 1); |
|
498 |
by (auto_tac (claset()addSDs [slen_take_lemma1], |
|
499 |
simpset() addsimps [stream.finite_def])); |
|
500 |
qed "slen_infinite"; |
|
501 |
||
502 |
Goal "s << t ==> #s <= #t"; |
|
503 |
by (case_tac "stream_finite t" 1); |
|
504 |
by (EVERY'[dtac (slen_infinite RS subst), dtac notnotD] 2); |
|
505 |
by (Asm_simp_tac 2); |
|
506 |
by (etac rev_mp 1); |
|
507 |
by (res_inst_tac [("x","s")] allE 1); |
|
508 |
by (atac 2); |
|
509 |
by (etac (stream_finite_ind) 1); |
|
510 |
by (Simp_tac 1); |
|
511 |
by (rtac allI 1); |
|
512 |
by (stream_case_tac "x" 1); |
|
513 |
by (asm_simp_tac (HOL_ss addsimps [slen_empty, i0_lb]) 1); |
|
514 |
by (asm_simp_tac (HOL_ss addsimps [slen_scons]) 1); |
|
515 |
by (fast_tac(claset() addSIs [iSuc_ile_mono RS iffD2] addSDs stream.inverts) 1); |
|
516 |
qed "slen_mono"; |
|
517 |
||
518 |
Goal "!(x::'a::flat stream) y. Fin n <= #x --> x << y --> \ |
|
519 |
\ stream_take n\\<cdot>x = stream_take n\\<cdot>y"; |
|
520 |
by (nat_ind_tac "n" 1); |
|
521 |
by ( simp_tac(simpset() addsimps [slen_empty_eq]) 1); |
|
522 |
by (strip_tac 1); |
|
523 |
by (stream_case_tac "x" 1); |
|
524 |
by (asm_full_simp_tac (HOL_ss addsimps [slen_empty, |
|
525 |
iSuc_Fin RS sym, not_iSuc_ilei0]) 1); |
|
526 |
by (fatac stream_prefix 1 1); |
|
527 |
by (safe_tac (claset() addSDs [stream_flat_prefix])); |
|
528 |
by (Simp_tac 1); |
|
529 |
by (rtac cfun_arg_cong 1); |
|
530 |
by (rotate_tac 3 1); |
|
531 |
by (asm_full_simp_tac (simpset() delsimps [iSuc_Fin] addsimps |
|
532 |
[iSuc_Fin RS sym, iSuc_ile_mono]) 1); |
|
533 |
qed_spec_mp "slen_take_lemma3"; |
|
534 |
||
535 |
Goal "stream_finite t ==> \ |
|
536 |
\!s. #(s::'a::flat stream) = #t & s << t --> s = t"; |
|
537 |
by (etac stream_finite_ind 1); |
|
538 |
by (fast_tac (claset() addDs [eq_UU_iff RS iffD2]) 1); |
|
539 |
by (Safe_tac); |
|
540 |
by (stream_case_tac "sa" 1); |
|
541 |
by (dtac sym 1); |
|
542 |
by (Asm_full_simp_tac 1); |
|
543 |
by (safe_tac (claset() addSDs [stream_flat_prefix])); |
|
544 |
by (rtac cfun_arg_cong 1); |
|
545 |
by (etac allE 1); |
|
546 |
by (etac mp 1); |
|
547 |
by (Asm_full_simp_tac 1); |
|
548 |
qed "slen_strict_mono_lemma"; |
|
549 |
||
550 |
Goal "[|stream_finite t; s ~= t; s << (t::'a::flat stream) |] ==> #s < #t"; |
|
551 |
by (rtac ilessI1 1); |
|
552 |
by (etac slen_mono 1); |
|
553 |
by (dtac slen_strict_mono_lemma 1); |
|
554 |
by (Fast_tac 1); |
|
555 |
qed "slen_strict_mono"; |
|
556 |
||
557 |
Goal "!x. Fin (i + j) <= #x --> Fin j <= #(iterate i rt x)"; |
|
558 |
by (nat_ind_tac "i" 1); |
|
559 |
by (Simp_tac 1); |
|
560 |
by (strip_tac 1); |
|
561 |
by (stream_case_tac "x" 1); |
|
562 |
by (asm_full_simp_tac (simpset() delsimps [iSuc_Fin] |
|
563 |
addsimps [iSuc_Fin RS sym]) 1); |
|
564 |
by (stac iterate_Suc2 1); |
|
565 |
by (rotate_tac 2 1); |
|
566 |
by (asm_full_simp_tac (simpset() delsimps [iSuc_Fin] |
|
567 |
addsimps [iSuc_Fin RS sym, iSuc_ile_mono]) 1); |
|
568 |
qed_spec_mp "slen_rt_mult"; |
|
569 |
||
570 |
||
571 |
(* ------------------------------------------------------------------------- *) |
|
572 |
||
573 |
section "sfilter"; |
|
574 |
||
575 |
bind_thm ("sfilter_unfold", fix_prover2 thy sfilter_def |
|
576 |
"sfilter = (\\<Lambda>p s. case s of x && xs => \ |
|
577 |
\ If p\\<cdot>x then x && sfilter\\<cdot>p\\<cdot>xs else sfilter\\<cdot>p\\<cdot>xs fi)"); |
|
578 |
||
579 |
Goal "sfilter\\<cdot>\\<bottom> = \\<bottom>"; |
|
580 |
by (rtac ext_cfun 1); |
|
581 |
by (stac sfilter_unfold 1); |
|
582 |
by (stream_case_tac "x" 1); |
|
583 |
by Auto_tac; |
|
584 |
qed "strict_sfilter"; |
|
585 |
||
586 |
Goal "sfilter\\<cdot>f\\<cdot>\\<bottom> = \\<bottom>"; |
|
587 |
by (stac sfilter_unfold 1); |
|
588 |
by (Simp_tac 1); |
|
589 |
qed "sfilter_empty"; |
|
590 |
||
591 |
Goal "x ~= \\<bottom> ==> sfilter\\<cdot>f\\<cdot>(x && xs) = \ |
|
592 |
\ If f\\<cdot>x then x && sfilter\\<cdot>f\\<cdot>xs else sfilter\\<cdot>f\\<cdot>xs fi"; |
|
593 |
by (rtac trans 1); |
|
594 |
by (stac sfilter_unfold 1); |
|
595 |
by (Asm_simp_tac 1); |
|
596 |
by (rtac refl 1); |
|
597 |
qed "sfilter_scons"; |
|
598 |