author | wenzelm |
Mon, 25 Mar 2019 17:21:26 +0100 | |
changeset 69981 | 3dced198b9ec |
parent 67961 | 9c31678d2139 |
child 70171 | 3173d7878274 |
permissions | -rw-r--r-- |
64015 | 1 |
(* Author: Florian Haftmann, TUM |
2 |
*) |
|
3 |
||
4 |
section \<open>Proof of concept for algebraically founded bit word types\<close> |
|
5 |
||
6 |
theory Word_Type |
|
7 |
imports |
|
8 |
Main |
|
66453
cc19f7ca2ed6
session-qualified theory imports: isabelle imports -U -i -d '~~/src/Benchmarks' -a;
wenzelm
parents:
64593
diff
changeset
|
9 |
"HOL-Library.Type_Length" |
64015 | 10 |
begin |
11 |
||
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
12 |
lemma take_bit_uminus: |
67816 | 13 |
fixes k :: int |
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
14 |
shows "take_bit n (- (take_bit n k)) = take_bit n (- k)" |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
15 |
by (simp add: take_bit_eq_mod mod_minus_eq) |
64015 | 16 |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
17 |
lemma take_bit_minus: |
67816 | 18 |
fixes k l :: int |
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
19 |
shows "take_bit n (take_bit n k - take_bit n l) = take_bit n (k - l)" |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
20 |
by (simp add: take_bit_eq_mod mod_diff_eq) |
64015 | 21 |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
22 |
lemma take_bit_nonnegative [simp]: |
64015 | 23 |
fixes k :: int |
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
24 |
shows "take_bit n k \<ge> 0" |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
25 |
by (simp add: take_bit_eq_mod) |
64015 | 26 |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
27 |
definition signed_take_bit :: "nat \<Rightarrow> int \<Rightarrow> int" |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
28 |
where signed_take_bit_eq_take_bit: |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
29 |
"signed_take_bit n k = take_bit (Suc n) (k + 2 ^ n) - 2 ^ n" |
64015 | 30 |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
31 |
lemma signed_take_bit_eq_take_bit': |
64015 | 32 |
assumes "n > 0" |
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
33 |
shows "signed_take_bit (n - Suc 0) k = take_bit n (k + 2 ^ (n - 1)) - 2 ^ (n - 1)" |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
34 |
using assms by (simp add: signed_take_bit_eq_take_bit) |
64015 | 35 |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
36 |
lemma signed_take_bit_0 [simp]: |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
37 |
"signed_take_bit 0 k = - (k mod 2)" |
64015 | 38 |
proof (cases "even k") |
39 |
case True |
|
40 |
then have "odd (k + 1)" |
|
41 |
by simp |
|
42 |
then have "(k + 1) mod 2 = 1" |
|
43 |
by (simp add: even_iff_mod_2_eq_zero) |
|
44 |
with True show ?thesis |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
45 |
by (simp add: signed_take_bit_eq_take_bit) |
64015 | 46 |
next |
47 |
case False |
|
48 |
then show ?thesis |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
49 |
by (simp add: signed_take_bit_eq_take_bit odd_iff_mod_2_eq_one) |
64015 | 50 |
qed |
51 |
||
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
52 |
lemma signed_take_bit_Suc [simp]: |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
53 |
"signed_take_bit (Suc n) k = signed_take_bit n (k div 2) * 2 + k mod 2" |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
54 |
by (simp add: odd_iff_mod_2_eq_one signed_take_bit_eq_take_bit algebra_simps) |
64015 | 55 |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
56 |
lemma signed_take_bit_of_0 [simp]: |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
57 |
"signed_take_bit n 0 = 0" |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
58 |
by (simp add: signed_take_bit_eq_take_bit take_bit_eq_mod) |
64015 | 59 |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
60 |
lemma signed_take_bit_of_minus_1 [simp]: |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
61 |
"signed_take_bit n (- 1) = - 1" |
64015 | 62 |
by (induct n) simp_all |
63 |
||
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
64 |
lemma signed_take_bit_eq_iff_take_bit_eq: |
64015 | 65 |
assumes "n > 0" |
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
66 |
shows "signed_take_bit (n - Suc 0) k = signed_take_bit (n - Suc 0) l \<longleftrightarrow> take_bit n k = take_bit n l" (is "?P \<longleftrightarrow> ?Q") |
64015 | 67 |
proof - |
68 |
from assms obtain m where m: "n = Suc m" |
|
69 |
by (cases n) auto |
|
70 |
show ?thesis |
|
71 |
proof |
|
72 |
assume ?Q |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
73 |
have "take_bit (Suc m) (k + 2 ^ m) = |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
74 |
take_bit (Suc m) (take_bit (Suc m) k + take_bit (Suc m) (2 ^ m))" |
67961 | 75 |
by (simp only: take_bit_add) |
64015 | 76 |
also have "\<dots> = |
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
77 |
take_bit (Suc m) (take_bit (Suc m) l + take_bit (Suc m) (2 ^ m))" |
64015 | 78 |
by (simp only: \<open>?Q\<close> m [symmetric]) |
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
79 |
also have "\<dots> = take_bit (Suc m) (l + 2 ^ m)" |
67961 | 80 |
by (simp only: take_bit_add) |
64015 | 81 |
finally show ?P |
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
82 |
by (simp only: signed_take_bit_eq_take_bit m) simp |
64015 | 83 |
next |
84 |
assume ?P |
|
85 |
with assms have "(k + 2 ^ (n - Suc 0)) mod 2 ^ n = (l + 2 ^ (n - Suc 0)) mod 2 ^ n" |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
86 |
by (simp add: signed_take_bit_eq_take_bit' take_bit_eq_mod) |
64015 | 87 |
then have "(i + (k + 2 ^ (n - Suc 0))) mod 2 ^ n = (i + (l + 2 ^ (n - Suc 0))) mod 2 ^ n" for i |
88 |
by (metis mod_add_eq) |
|
89 |
then have "k mod 2 ^ n = l mod 2 ^ n" |
|
90 |
by (metis add_diff_cancel_right' uminus_add_conv_diff) |
|
91 |
then show ?Q |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
92 |
by (simp add: take_bit_eq_mod) |
64015 | 93 |
qed |
94 |
qed |
|
95 |
||
96 |
||
97 |
subsection \<open>Bit strings as quotient type\<close> |
|
98 |
||
99 |
subsubsection \<open>Basic properties\<close> |
|
100 |
||
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
101 |
quotient_type (overloaded) 'a word = int / "\<lambda>k l. take_bit LENGTH('a) k = take_bit LENGTH('a::len0) l" |
64015 | 102 |
by (auto intro!: equivpI reflpI sympI transpI) |
103 |
||
104 |
instantiation word :: (len0) "{semiring_numeral, comm_semiring_0, comm_ring}" |
|
105 |
begin |
|
106 |
||
107 |
lift_definition zero_word :: "'a word" |
|
108 |
is 0 |
|
109 |
. |
|
110 |
||
111 |
lift_definition one_word :: "'a word" |
|
112 |
is 1 |
|
113 |
. |
|
114 |
||
115 |
lift_definition plus_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word" |
|
116 |
is plus |
|
67961 | 117 |
by (subst take_bit_add [symmetric]) (simp add: take_bit_add) |
64015 | 118 |
|
119 |
lift_definition uminus_word :: "'a word \<Rightarrow> 'a word" |
|
120 |
is uminus |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
121 |
by (subst take_bit_uminus [symmetric]) (simp add: take_bit_uminus) |
64015 | 122 |
|
123 |
lift_definition minus_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word" |
|
124 |
is minus |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
125 |
by (subst take_bit_minus [symmetric]) (simp add: take_bit_minus) |
64015 | 126 |
|
127 |
lift_definition times_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word" |
|
128 |
is times |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
129 |
by (auto simp add: take_bit_eq_mod intro: mod_mult_cong) |
64015 | 130 |
|
131 |
instance |
|
132 |
by standard (transfer; simp add: algebra_simps)+ |
|
133 |
||
134 |
end |
|
135 |
||
136 |
instance word :: (len) comm_ring_1 |
|
137 |
by standard (transfer; simp)+ |
|
138 |
||
139 |
||
140 |
subsubsection \<open>Conversions\<close> |
|
141 |
||
142 |
lemma [transfer_rule]: |
|
143 |
"rel_fun HOL.eq pcr_word int of_nat" |
|
144 |
proof - |
|
145 |
note transfer_rule_of_nat [transfer_rule] |
|
146 |
show ?thesis by transfer_prover |
|
147 |
qed |
|
148 |
||
149 |
lemma [transfer_rule]: |
|
150 |
"rel_fun HOL.eq pcr_word (\<lambda>k. k) of_int" |
|
151 |
proof - |
|
152 |
note transfer_rule_of_int [transfer_rule] |
|
153 |
have "rel_fun HOL.eq pcr_word (of_int :: int \<Rightarrow> int) (of_int :: int \<Rightarrow> 'a word)" |
|
154 |
by transfer_prover |
|
155 |
then show ?thesis by (simp add: id_def) |
|
156 |
qed |
|
157 |
||
158 |
context semiring_1 |
|
159 |
begin |
|
160 |
||
161 |
lift_definition unsigned :: "'b::len0 word \<Rightarrow> 'a" |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
162 |
is "of_nat \<circ> nat \<circ> take_bit LENGTH('b)" |
64015 | 163 |
by simp |
164 |
||
165 |
lemma unsigned_0 [simp]: |
|
166 |
"unsigned 0 = 0" |
|
167 |
by transfer simp |
|
168 |
||
169 |
end |
|
170 |
||
171 |
context semiring_char_0 |
|
172 |
begin |
|
173 |
||
174 |
lemma word_eq_iff_unsigned: |
|
175 |
"a = b \<longleftrightarrow> unsigned a = unsigned b" |
|
176 |
by safe (transfer; simp add: eq_nat_nat_iff) |
|
177 |
||
178 |
end |
|
179 |
||
180 |
context ring_1 |
|
181 |
begin |
|
182 |
||
183 |
lift_definition signed :: "'b::len word \<Rightarrow> 'a" |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
184 |
is "of_int \<circ> signed_take_bit (LENGTH('b) - 1)" |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
185 |
by (simp add: signed_take_bit_eq_iff_take_bit_eq [symmetric]) |
64015 | 186 |
|
187 |
lemma signed_0 [simp]: |
|
188 |
"signed 0 = 0" |
|
189 |
by transfer simp |
|
190 |
||
191 |
end |
|
192 |
||
193 |
lemma unsigned_of_nat [simp]: |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
194 |
"unsigned (of_nat n :: 'a word) = take_bit LENGTH('a::len) n" |
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
195 |
by transfer (simp add: nat_eq_iff take_bit_eq_mod zmod_int) |
64015 | 196 |
|
197 |
lemma of_nat_unsigned [simp]: |
|
198 |
"of_nat (unsigned a) = a" |
|
199 |
by transfer simp |
|
200 |
||
201 |
lemma of_int_unsigned [simp]: |
|
202 |
"of_int (unsigned a) = a" |
|
203 |
by transfer simp |
|
204 |
||
205 |
context ring_char_0 |
|
206 |
begin |
|
207 |
||
208 |
lemma word_eq_iff_signed: |
|
209 |
"a = b \<longleftrightarrow> signed a = signed b" |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
210 |
by safe (transfer; auto simp add: signed_take_bit_eq_iff_take_bit_eq) |
64015 | 211 |
|
212 |
end |
|
213 |
||
214 |
lemma signed_of_int [simp]: |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
215 |
"signed (of_int k :: 'a word) = signed_take_bit (LENGTH('a::len) - 1) k" |
64015 | 216 |
by transfer simp |
217 |
||
218 |
lemma of_int_signed [simp]: |
|
219 |
"of_int (signed a) = a" |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
220 |
by transfer (simp add: signed_take_bit_eq_take_bit take_bit_eq_mod mod_simps) |
64015 | 221 |
|
222 |
||
223 |
subsubsection \<open>Properties\<close> |
|
224 |
||
225 |
||
226 |
subsubsection \<open>Division\<close> |
|
227 |
||
228 |
instantiation word :: (len0) modulo |
|
229 |
begin |
|
230 |
||
231 |
lift_definition divide_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word" |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
232 |
is "\<lambda>a b. take_bit LENGTH('a) a div take_bit LENGTH('a) b" |
64015 | 233 |
by simp |
234 |
||
235 |
lift_definition modulo_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word" |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
236 |
is "\<lambda>a b. take_bit LENGTH('a) a mod take_bit LENGTH('a) b" |
64015 | 237 |
by simp |
238 |
||
239 |
instance .. |
|
240 |
||
241 |
end |
|
242 |
||
243 |
||
244 |
subsubsection \<open>Orderings\<close> |
|
245 |
||
246 |
instantiation word :: (len0) linorder |
|
247 |
begin |
|
248 |
||
249 |
lift_definition less_eq_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> bool" |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
250 |
is "\<lambda>a b. take_bit LENGTH('a) a \<le> take_bit LENGTH('a) b" |
64015 | 251 |
by simp |
252 |
||
253 |
lift_definition less_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> bool" |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
254 |
is "\<lambda>a b. take_bit LENGTH('a) a < take_bit LENGTH('a) b" |
64015 | 255 |
by simp |
256 |
||
257 |
instance |
|
258 |
by standard (transfer; auto)+ |
|
259 |
||
260 |
end |
|
261 |
||
262 |
context linordered_semidom |
|
263 |
begin |
|
264 |
||
265 |
lemma word_less_eq_iff_unsigned: |
|
266 |
"a \<le> b \<longleftrightarrow> unsigned a \<le> unsigned b" |
|
267 |
by (transfer fixing: less_eq) (simp add: nat_le_eq_zle) |
|
268 |
||
269 |
lemma word_less_iff_unsigned: |
|
270 |
"a < b \<longleftrightarrow> unsigned a < unsigned b" |
|
67907
02a14c1cb917
prefer convention to place operation name before type name
haftmann
parents:
67816
diff
changeset
|
271 |
by (transfer fixing: less) (auto dest: preorder_class.le_less_trans [OF take_bit_nonnegative]) |
64015 | 272 |
|
273 |
end |
|
274 |
||
275 |
end |