src/HOL/ex/Word_Type.thy
author haftmann
Sun Oct 08 22:28:22 2017 +0200 (21 months ago)
changeset 66815 93c6632ddf44
parent 66806 a4e82b58d833
child 67816 2249b27ab1dd
permissions -rw-r--r--
one uniform type class for parity structures
haftmann@64015
     1
(*  Author:  Florian Haftmann, TUM
haftmann@64015
     2
*)
haftmann@64015
     3
haftmann@64015
     4
section \<open>Proof of concept for algebraically founded bit word types\<close>
haftmann@64015
     5
haftmann@64015
     6
theory Word_Type
haftmann@64015
     7
  imports
haftmann@64015
     8
    Main
wenzelm@66453
     9
    "HOL-Library.Type_Length"
haftmann@64015
    10
begin
haftmann@64015
    11
haftmann@64015
    12
subsection \<open>Truncating bit representations of numeric types\<close>
haftmann@64015
    13
haftmann@66815
    14
class semiring_bits = semiring_parity +
haftmann@64015
    15
  assumes semiring_bits: "(1 + 2 * a) mod of_nat (2 * n) = 1 + 2 * (a mod of_nat n)"
haftmann@64015
    16
begin
haftmann@64015
    17
haftmann@64114
    18
definition bitrunc :: "nat \<Rightarrow> 'a \<Rightarrow> 'a"
haftmann@64114
    19
  where bitrunc_eq_mod: "bitrunc n a = a mod of_nat (2 ^ n)"
haftmann@64015
    20
haftmann@64114
    21
lemma bitrunc_bitrunc [simp]:
haftmann@64114
    22
  "bitrunc n (bitrunc n a) = bitrunc n a"
haftmann@64114
    23
  by (simp add: bitrunc_eq_mod)
haftmann@64015
    24
  
haftmann@64114
    25
lemma bitrunc_0 [simp]:
haftmann@64114
    26
  "bitrunc 0 a = 0"
haftmann@64114
    27
  by (simp add: bitrunc_eq_mod)
haftmann@64015
    28
haftmann@64114
    29
lemma bitrunc_Suc [simp]:
haftmann@66815
    30
  "bitrunc (Suc n) a = bitrunc n (a div 2) * 2 + of_bool (odd a)"
haftmann@64015
    31
proof -
haftmann@66815
    32
  have "1 + 2 * (a div 2) mod (2 * 2 ^ n) = (a div 2 * 2 + a mod 2) mod (2 * 2 ^ n)"
haftmann@66815
    33
    if "odd a"
haftmann@66815
    34
    using that semiring_bits [of "a div 2" "2 ^ n"]
haftmann@66815
    35
      by (simp add: algebra_simps odd_iff_mod_2_eq_one mult_mod_right)
haftmann@66815
    36
  also have "\<dots> = a mod (2 * 2 ^ n)"
haftmann@66815
    37
    by (simp only: div_mult_mod_eq)
haftmann@66815
    38
  finally show ?thesis
haftmann@66815
    39
    by (simp add: bitrunc_eq_mod algebra_simps mult_mod_right)
haftmann@64015
    40
qed
haftmann@64015
    41
haftmann@64114
    42
lemma bitrunc_of_0 [simp]:
haftmann@64114
    43
  "bitrunc n 0 = 0"
haftmann@64114
    44
  by (simp add: bitrunc_eq_mod)
haftmann@64015
    45
haftmann@64114
    46
lemma bitrunc_plus:
haftmann@64114
    47
  "bitrunc n (bitrunc n a + bitrunc n b) = bitrunc n (a + b)"
haftmann@66815
    48
  by (simp add: bitrunc_eq_mod mod_simps)
haftmann@64015
    49
haftmann@64114
    50
lemma bitrunc_of_1_eq_0_iff [simp]:
haftmann@64114
    51
  "bitrunc n 1 = 0 \<longleftrightarrow> n = 0"
haftmann@66815
    52
  by (simp add: bitrunc_eq_mod)
haftmann@64015
    53
haftmann@64015
    54
end
haftmann@64015
    55
haftmann@64015
    56
instance nat :: semiring_bits
haftmann@64015
    57
  by standard (simp add: mod_Suc Suc_double_not_eq_double)
haftmann@64015
    58
haftmann@64015
    59
instance int :: semiring_bits
haftmann@64015
    60
  by standard (simp add: pos_zmod_mult_2)
haftmann@64015
    61
haftmann@64114
    62
lemma bitrunc_uminus:
haftmann@64015
    63
  fixes k :: int
haftmann@64114
    64
  shows "bitrunc n (- (bitrunc n k)) = bitrunc n (- k)"
haftmann@64593
    65
  by (simp add: bitrunc_eq_mod mod_minus_eq)
haftmann@64015
    66
haftmann@64114
    67
lemma bitrunc_minus:
haftmann@64015
    68
  fixes k l :: int
haftmann@64114
    69
  shows "bitrunc n (bitrunc n k - bitrunc n l) = bitrunc n (k - l)"
haftmann@64593
    70
  by (simp add: bitrunc_eq_mod mod_diff_eq)
haftmann@64015
    71
haftmann@64114
    72
lemma bitrunc_nonnegative [simp]:
haftmann@64015
    73
  fixes k :: int
haftmann@64114
    74
  shows "bitrunc n k \<ge> 0"
haftmann@64114
    75
  by (simp add: bitrunc_eq_mod)
haftmann@64015
    76
haftmann@64114
    77
definition signed_bitrunc :: "nat \<Rightarrow> int \<Rightarrow> int"
haftmann@64114
    78
  where signed_bitrunc_eq_bitrunc:
haftmann@64114
    79
    "signed_bitrunc n k = bitrunc (Suc n) (k + 2 ^ n) - 2 ^ n"
haftmann@64015
    80
haftmann@64114
    81
lemma signed_bitrunc_eq_bitrunc':
haftmann@64015
    82
  assumes "n > 0"
haftmann@64114
    83
  shows "signed_bitrunc (n - Suc 0) k = bitrunc n (k + 2 ^ (n - 1)) - 2 ^ (n - 1)"
haftmann@64114
    84
  using assms by (simp add: signed_bitrunc_eq_bitrunc)
haftmann@64015
    85
  
haftmann@64114
    86
lemma signed_bitrunc_0 [simp]:
haftmann@64114
    87
  "signed_bitrunc 0 k = - (k mod 2)"
haftmann@64015
    88
proof (cases "even k")
haftmann@64015
    89
  case True
haftmann@64015
    90
  then have "odd (k + 1)"
haftmann@64015
    91
    by simp
haftmann@64015
    92
  then have "(k + 1) mod 2 = 1"
haftmann@64015
    93
    by (simp add: even_iff_mod_2_eq_zero)
haftmann@64015
    94
  with True show ?thesis
haftmann@64114
    95
    by (simp add: signed_bitrunc_eq_bitrunc)
haftmann@64015
    96
next
haftmann@64015
    97
  case False
haftmann@64015
    98
  then show ?thesis
haftmann@64114
    99
    by (simp add: signed_bitrunc_eq_bitrunc odd_iff_mod_2_eq_one)
haftmann@64015
   100
qed
haftmann@64015
   101
haftmann@64114
   102
lemma signed_bitrunc_Suc [simp]:
haftmann@64114
   103
  "signed_bitrunc (Suc n) k = signed_bitrunc n (k div 2) * 2 + k mod 2"
haftmann@66815
   104
  by (simp add: odd_iff_mod_2_eq_one signed_bitrunc_eq_bitrunc algebra_simps)
haftmann@64015
   105
haftmann@64114
   106
lemma signed_bitrunc_of_0 [simp]:
haftmann@64114
   107
  "signed_bitrunc n 0 = 0"
haftmann@64114
   108
  by (simp add: signed_bitrunc_eq_bitrunc bitrunc_eq_mod)
haftmann@64015
   109
haftmann@64114
   110
lemma signed_bitrunc_of_minus_1 [simp]:
haftmann@64114
   111
  "signed_bitrunc n (- 1) = - 1"
haftmann@64015
   112
  by (induct n) simp_all
haftmann@64015
   113
haftmann@64114
   114
lemma signed_bitrunc_eq_iff_bitrunc_eq:
haftmann@64015
   115
  assumes "n > 0"
haftmann@64114
   116
  shows "signed_bitrunc (n - Suc 0) k = signed_bitrunc (n - Suc 0) l \<longleftrightarrow> bitrunc n k = bitrunc n l" (is "?P \<longleftrightarrow> ?Q")
haftmann@64015
   117
proof -
haftmann@64015
   118
  from assms obtain m where m: "n = Suc m"
haftmann@64015
   119
    by (cases n) auto
haftmann@64015
   120
  show ?thesis
haftmann@64015
   121
  proof 
haftmann@64015
   122
    assume ?Q
haftmann@64114
   123
    have "bitrunc (Suc m) (k + 2 ^ m) =
haftmann@64114
   124
      bitrunc (Suc m) (bitrunc (Suc m) k + bitrunc (Suc m) (2 ^ m))"
haftmann@64114
   125
      by (simp only: bitrunc_plus)
haftmann@64015
   126
    also have "\<dots> =
haftmann@64114
   127
      bitrunc (Suc m) (bitrunc (Suc m) l + bitrunc (Suc m) (2 ^ m))"
haftmann@64015
   128
      by (simp only: \<open>?Q\<close> m [symmetric])
haftmann@64114
   129
    also have "\<dots> = bitrunc (Suc m) (l + 2 ^ m)"
haftmann@64114
   130
      by (simp only: bitrunc_plus)
haftmann@64015
   131
    finally show ?P
haftmann@64114
   132
      by (simp only: signed_bitrunc_eq_bitrunc m) simp
haftmann@64015
   133
  next
haftmann@64015
   134
    assume ?P
haftmann@64015
   135
    with assms have "(k + 2 ^ (n - Suc 0)) mod 2 ^ n = (l + 2 ^ (n - Suc 0)) mod 2 ^ n"
haftmann@64114
   136
      by (simp add: signed_bitrunc_eq_bitrunc' bitrunc_eq_mod)
haftmann@64015
   137
    then have "(i + (k + 2 ^ (n - Suc 0))) mod 2 ^ n = (i + (l + 2 ^ (n - Suc 0))) mod 2 ^ n" for i
haftmann@64015
   138
      by (metis mod_add_eq)
haftmann@64015
   139
    then have "k mod 2 ^ n = l mod 2 ^ n"
haftmann@64015
   140
      by (metis add_diff_cancel_right' uminus_add_conv_diff)
haftmann@64015
   141
    then show ?Q
haftmann@64114
   142
      by (simp add: bitrunc_eq_mod)
haftmann@64015
   143
  qed
haftmann@64015
   144
qed 
haftmann@64015
   145
haftmann@64015
   146
haftmann@64015
   147
subsection \<open>Bit strings as quotient type\<close>
haftmann@64015
   148
haftmann@64015
   149
subsubsection \<open>Basic properties\<close>
haftmann@64015
   150
haftmann@64114
   151
quotient_type (overloaded) 'a word = int / "\<lambda>k l. bitrunc LENGTH('a) k = bitrunc LENGTH('a::len0) l"
haftmann@64015
   152
  by (auto intro!: equivpI reflpI sympI transpI)
haftmann@64015
   153
haftmann@64015
   154
instantiation word :: (len0) "{semiring_numeral, comm_semiring_0, comm_ring}"
haftmann@64015
   155
begin
haftmann@64015
   156
haftmann@64015
   157
lift_definition zero_word :: "'a word"
haftmann@64015
   158
  is 0
haftmann@64015
   159
  .
haftmann@64015
   160
haftmann@64015
   161
lift_definition one_word :: "'a word"
haftmann@64015
   162
  is 1
haftmann@64015
   163
  .
haftmann@64015
   164
haftmann@64015
   165
lift_definition plus_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
haftmann@64015
   166
  is plus
haftmann@64114
   167
  by (subst bitrunc_plus [symmetric]) (simp add: bitrunc_plus)
haftmann@64015
   168
haftmann@64015
   169
lift_definition uminus_word :: "'a word \<Rightarrow> 'a word"
haftmann@64015
   170
  is uminus
haftmann@64114
   171
  by (subst bitrunc_uminus [symmetric]) (simp add: bitrunc_uminus)
haftmann@64015
   172
haftmann@64015
   173
lift_definition minus_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
haftmann@64015
   174
  is minus
haftmann@64114
   175
  by (subst bitrunc_minus [symmetric]) (simp add: bitrunc_minus)
haftmann@64015
   176
haftmann@64015
   177
lift_definition times_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
haftmann@64015
   178
  is times
haftmann@64114
   179
  by (auto simp add: bitrunc_eq_mod intro: mod_mult_cong)
haftmann@64015
   180
haftmann@64015
   181
instance
haftmann@64015
   182
  by standard (transfer; simp add: algebra_simps)+
haftmann@64015
   183
haftmann@64015
   184
end
haftmann@64015
   185
haftmann@64015
   186
instance word :: (len) comm_ring_1
haftmann@64015
   187
  by standard (transfer; simp)+
haftmann@64015
   188
haftmann@64015
   189
haftmann@64015
   190
subsubsection \<open>Conversions\<close>
haftmann@64015
   191
haftmann@64015
   192
lemma [transfer_rule]:
haftmann@64015
   193
  "rel_fun HOL.eq pcr_word int of_nat"
haftmann@64015
   194
proof -
haftmann@64015
   195
  note transfer_rule_of_nat [transfer_rule]
haftmann@64015
   196
  show ?thesis by transfer_prover
haftmann@64015
   197
qed
haftmann@64015
   198
  
haftmann@64015
   199
lemma [transfer_rule]:
haftmann@64015
   200
  "rel_fun HOL.eq pcr_word (\<lambda>k. k) of_int"
haftmann@64015
   201
proof -
haftmann@64015
   202
  note transfer_rule_of_int [transfer_rule]
haftmann@64015
   203
  have "rel_fun HOL.eq pcr_word (of_int :: int \<Rightarrow> int) (of_int :: int \<Rightarrow> 'a word)"
haftmann@64015
   204
    by transfer_prover
haftmann@64015
   205
  then show ?thesis by (simp add: id_def)
haftmann@64015
   206
qed
haftmann@64015
   207
haftmann@64015
   208
context semiring_1
haftmann@64015
   209
begin
haftmann@64015
   210
haftmann@64015
   211
lift_definition unsigned :: "'b::len0 word \<Rightarrow> 'a"
haftmann@64114
   212
  is "of_nat \<circ> nat \<circ> bitrunc LENGTH('b)"
haftmann@64015
   213
  by simp
haftmann@64015
   214
haftmann@64015
   215
lemma unsigned_0 [simp]:
haftmann@64015
   216
  "unsigned 0 = 0"
haftmann@64015
   217
  by transfer simp
haftmann@64015
   218
haftmann@64015
   219
end
haftmann@64015
   220
haftmann@64015
   221
context semiring_char_0
haftmann@64015
   222
begin
haftmann@64015
   223
haftmann@64015
   224
lemma word_eq_iff_unsigned:
haftmann@64015
   225
  "a = b \<longleftrightarrow> unsigned a = unsigned b"
haftmann@64015
   226
  by safe (transfer; simp add: eq_nat_nat_iff)
haftmann@64015
   227
haftmann@64015
   228
end
haftmann@64015
   229
haftmann@64015
   230
context ring_1
haftmann@64015
   231
begin
haftmann@64015
   232
haftmann@64015
   233
lift_definition signed :: "'b::len word \<Rightarrow> 'a"
haftmann@64114
   234
  is "of_int \<circ> signed_bitrunc (LENGTH('b) - 1)"
haftmann@64114
   235
  by (simp add: signed_bitrunc_eq_iff_bitrunc_eq [symmetric])
haftmann@64015
   236
haftmann@64015
   237
lemma signed_0 [simp]:
haftmann@64015
   238
  "signed 0 = 0"
haftmann@64015
   239
  by transfer simp
haftmann@64015
   240
haftmann@64015
   241
end
haftmann@64015
   242
haftmann@64015
   243
lemma unsigned_of_nat [simp]:
haftmann@64114
   244
  "unsigned (of_nat n :: 'a word) = bitrunc LENGTH('a::len) n"
haftmann@64114
   245
  by transfer (simp add: nat_eq_iff bitrunc_eq_mod zmod_int)
haftmann@64015
   246
haftmann@64015
   247
lemma of_nat_unsigned [simp]:
haftmann@64015
   248
  "of_nat (unsigned a) = a"
haftmann@64015
   249
  by transfer simp
haftmann@64015
   250
haftmann@64015
   251
lemma of_int_unsigned [simp]:
haftmann@64015
   252
  "of_int (unsigned a) = a"
haftmann@64015
   253
  by transfer simp
haftmann@64015
   254
haftmann@64015
   255
context ring_char_0
haftmann@64015
   256
begin
haftmann@64015
   257
haftmann@64015
   258
lemma word_eq_iff_signed:
haftmann@64015
   259
  "a = b \<longleftrightarrow> signed a = signed b"
haftmann@64114
   260
  by safe (transfer; auto simp add: signed_bitrunc_eq_iff_bitrunc_eq)
haftmann@64015
   261
haftmann@64015
   262
end
haftmann@64015
   263
haftmann@64015
   264
lemma signed_of_int [simp]:
haftmann@64114
   265
  "signed (of_int k :: 'a word) = signed_bitrunc (LENGTH('a::len) - 1) k"
haftmann@64015
   266
  by transfer simp
haftmann@64015
   267
haftmann@64015
   268
lemma of_int_signed [simp]:
haftmann@64015
   269
  "of_int (signed a) = a"
haftmann@64593
   270
  by transfer (simp add: signed_bitrunc_eq_bitrunc bitrunc_eq_mod mod_simps)
haftmann@64015
   271
haftmann@64015
   272
haftmann@64015
   273
subsubsection \<open>Properties\<close>
haftmann@64015
   274
haftmann@64015
   275
haftmann@64015
   276
subsubsection \<open>Division\<close>
haftmann@64015
   277
haftmann@64015
   278
instantiation word :: (len0) modulo
haftmann@64015
   279
begin
haftmann@64015
   280
haftmann@64015
   281
lift_definition divide_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
haftmann@64114
   282
  is "\<lambda>a b. bitrunc LENGTH('a) a div bitrunc LENGTH('a) b"
haftmann@64015
   283
  by simp
haftmann@64015
   284
haftmann@64015
   285
lift_definition modulo_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
haftmann@64114
   286
  is "\<lambda>a b. bitrunc LENGTH('a) a mod bitrunc LENGTH('a) b"
haftmann@64015
   287
  by simp
haftmann@64015
   288
haftmann@64015
   289
instance ..
haftmann@64015
   290
haftmann@64015
   291
end
haftmann@64015
   292
haftmann@64015
   293
haftmann@64015
   294
subsubsection \<open>Orderings\<close>
haftmann@64015
   295
haftmann@64015
   296
instantiation word :: (len0) linorder
haftmann@64015
   297
begin
haftmann@64015
   298
haftmann@64015
   299
lift_definition less_eq_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> bool"
haftmann@64114
   300
  is "\<lambda>a b. bitrunc LENGTH('a) a \<le> bitrunc LENGTH('a) b"
haftmann@64015
   301
  by simp
haftmann@64015
   302
haftmann@64015
   303
lift_definition less_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> bool"
haftmann@64114
   304
  is "\<lambda>a b. bitrunc LENGTH('a) a < bitrunc LENGTH('a) b"
haftmann@64015
   305
  by simp
haftmann@64015
   306
haftmann@64015
   307
instance
haftmann@64015
   308
  by standard (transfer; auto)+
haftmann@64015
   309
haftmann@64015
   310
end
haftmann@64015
   311
haftmann@64015
   312
context linordered_semidom
haftmann@64015
   313
begin
haftmann@64015
   314
haftmann@64015
   315
lemma word_less_eq_iff_unsigned:
haftmann@64015
   316
  "a \<le> b \<longleftrightarrow> unsigned a \<le> unsigned b"
haftmann@64015
   317
  by (transfer fixing: less_eq) (simp add: nat_le_eq_zle)
haftmann@64015
   318
haftmann@64015
   319
lemma word_less_iff_unsigned:
haftmann@64015
   320
  "a < b \<longleftrightarrow> unsigned a < unsigned b"
haftmann@64114
   321
  by (transfer fixing: less) (auto dest: preorder_class.le_less_trans [OF bitrunc_nonnegative])
haftmann@64015
   322
haftmann@64015
   323
end
haftmann@64015
   324
haftmann@64015
   325
end