src/HOL/ex/Word_Type.thy
author haftmann
Mon Oct 03 14:37:06 2016 +0200 (2016-10-03)
changeset 64015 c9f3a94cb825
child 64113 86efd3d4dc98
permissions -rw-r--r--
proof of concept for algebraically founded word types
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
haftmann@64015
     9
    "~~/src/HOL/Library/Type_Length"
haftmann@64015
    10
begin
haftmann@64015
    11
haftmann@64015
    12
subsection \<open>Compact syntax for types with a length\<close>
haftmann@64015
    13
haftmann@64015
    14
syntax "_type_length" :: "type \<Rightarrow> nat" ("(1LENGTH/(1'(_')))")
haftmann@64015
    15
haftmann@64015
    16
translations "LENGTH('a)" \<rightharpoonup>
haftmann@64015
    17
  "CONST len_of (CONST Pure.type :: 'a itself)"
haftmann@64015
    18
haftmann@64015
    19
print_translation \<open>
haftmann@64015
    20
  let
haftmann@64015
    21
    fun len_of_itself_tr' ctxt [Const (@{const_syntax Pure.type}, Type (_, [T]))] =
haftmann@64015
    22
      Syntax.const @{syntax_const "_type_length"} $ Syntax_Phases.term_of_typ ctxt T
haftmann@64015
    23
  in [(@{const_syntax len_of}, len_of_itself_tr')] end
haftmann@64015
    24
\<close>
haftmann@64015
    25
haftmann@64015
    26
haftmann@64015
    27
subsection \<open>Truncating bit representations of numeric types\<close>
haftmann@64015
    28
haftmann@64015
    29
class semiring_bits = semiring_div_parity +
haftmann@64015
    30
  assumes semiring_bits: "(1 + 2 * a) mod of_nat (2 * n) = 1 + 2 * (a mod of_nat n)"
haftmann@64015
    31
haftmann@64015
    32
context semiring_bits
haftmann@64015
    33
begin
haftmann@64015
    34
haftmann@64015
    35
definition bits :: "nat \<Rightarrow> 'a \<Rightarrow> 'a"
haftmann@64015
    36
  where bits_eq_mod: "bits n a = a mod of_nat (2 ^ n)"
haftmann@64015
    37
haftmann@64015
    38
lemma bits_bits [simp]:
haftmann@64015
    39
  "bits n (bits n a) = bits n a"
haftmann@64015
    40
  by (simp add: bits_eq_mod)
haftmann@64015
    41
  
haftmann@64015
    42
lemma bits_0 [simp]:
haftmann@64015
    43
  "bits 0 a = 0"
haftmann@64015
    44
  by (simp add: bits_eq_mod)
haftmann@64015
    45
haftmann@64015
    46
lemma bits_Suc [simp]:
haftmann@64015
    47
  "bits (Suc n) a = bits n (a div 2) * 2 + a mod 2"
haftmann@64015
    48
proof -
haftmann@64015
    49
  define b and c
haftmann@64015
    50
    where "b = a div 2" and "c = a mod 2"
haftmann@64015
    51
  then have a: "a = b * 2 + c" 
haftmann@64015
    52
    and "c = 0 \<or> c = 1"
haftmann@64015
    53
    by (simp_all add: mod_div_equality parity)
haftmann@64015
    54
  from \<open>c = 0 \<or> c = 1\<close>
haftmann@64015
    55
  have "bits (Suc n) (b * 2 + c) = bits n b * 2 + c"
haftmann@64015
    56
  proof
haftmann@64015
    57
    assume "c = 0"
haftmann@64015
    58
    moreover have "(2 * b) mod (2 * 2 ^ n) = 2 * (b mod 2 ^ n)"
haftmann@64015
    59
      by (simp add: mod_mult_mult1)
haftmann@64015
    60
    ultimately show ?thesis
haftmann@64015
    61
      by (simp add: bits_eq_mod ac_simps)
haftmann@64015
    62
  next
haftmann@64015
    63
    assume "c = 1"
haftmann@64015
    64
    with semiring_bits [of b "2 ^ n"] show ?thesis
haftmann@64015
    65
      by (simp add: bits_eq_mod ac_simps)
haftmann@64015
    66
  qed
haftmann@64015
    67
  with a show ?thesis
haftmann@64015
    68
    by (simp add: b_def c_def)
haftmann@64015
    69
qed
haftmann@64015
    70
haftmann@64015
    71
lemma bits_of_0 [simp]:
haftmann@64015
    72
  "bits n 0 = 0"
haftmann@64015
    73
  by (simp add: bits_eq_mod)
haftmann@64015
    74
haftmann@64015
    75
lemma bits_plus:
haftmann@64015
    76
  "bits n (bits n a + bits n b) = bits n (a + b)"
haftmann@64015
    77
  by (simp add: bits_eq_mod mod_add_eq [symmetric])
haftmann@64015
    78
haftmann@64015
    79
lemma bits_of_1_eq_0_iff [simp]:
haftmann@64015
    80
  "bits n 1 = 0 \<longleftrightarrow> n = 0"
haftmann@64015
    81
  by (induct n) simp_all
haftmann@64015
    82
haftmann@64015
    83
end
haftmann@64015
    84
haftmann@64015
    85
instance nat :: semiring_bits
haftmann@64015
    86
  by standard (simp add: mod_Suc Suc_double_not_eq_double)
haftmann@64015
    87
haftmann@64015
    88
instance int :: semiring_bits
haftmann@64015
    89
  by standard (simp add: pos_zmod_mult_2)
haftmann@64015
    90
haftmann@64015
    91
lemma bits_uminus:
haftmann@64015
    92
  fixes k :: int
haftmann@64015
    93
  shows "bits n (- (bits n k)) = bits n (- k)"
haftmann@64015
    94
  by (simp add: bits_eq_mod mod_minus_eq [symmetric])
haftmann@64015
    95
haftmann@64015
    96
lemma bits_minus:
haftmann@64015
    97
  fixes k l :: int
haftmann@64015
    98
  shows "bits n (bits n k - bits n l) = bits n (k - l)"
haftmann@64015
    99
  by (simp add: bits_eq_mod mod_diff_eq [symmetric])
haftmann@64015
   100
haftmann@64015
   101
lemma bits_nonnegative [simp]:
haftmann@64015
   102
  fixes k :: int
haftmann@64015
   103
  shows "bits n k \<ge> 0"
haftmann@64015
   104
  by (simp add: bits_eq_mod)
haftmann@64015
   105
haftmann@64015
   106
definition signed_bits :: "nat \<Rightarrow> int \<Rightarrow> int"
haftmann@64015
   107
  where signed_bits_eq_bits:
haftmann@64015
   108
    "signed_bits n k = bits (Suc n) (k + 2 ^ n) - 2 ^ n"
haftmann@64015
   109
haftmann@64015
   110
lemma signed_bits_eq_bits':
haftmann@64015
   111
  assumes "n > 0"
haftmann@64015
   112
  shows "signed_bits (n - Suc 0) k = bits n (k + 2 ^ (n - 1)) - 2 ^ (n - 1)"
haftmann@64015
   113
  using assms by (simp add: signed_bits_eq_bits)
haftmann@64015
   114
  
haftmann@64015
   115
lemma signed_bits_0 [simp]:
haftmann@64015
   116
  "signed_bits 0 k = - (k mod 2)"
haftmann@64015
   117
proof (cases "even k")
haftmann@64015
   118
  case True
haftmann@64015
   119
  then have "odd (k + 1)"
haftmann@64015
   120
    by simp
haftmann@64015
   121
  then have "(k + 1) mod 2 = 1"
haftmann@64015
   122
    by (simp add: even_iff_mod_2_eq_zero)
haftmann@64015
   123
  with True show ?thesis
haftmann@64015
   124
    by (simp add: signed_bits_eq_bits)
haftmann@64015
   125
next
haftmann@64015
   126
  case False
haftmann@64015
   127
  then show ?thesis
haftmann@64015
   128
    by (simp add: signed_bits_eq_bits odd_iff_mod_2_eq_one)
haftmann@64015
   129
qed
haftmann@64015
   130
haftmann@64015
   131
lemma signed_bits_Suc [simp]:
haftmann@64015
   132
  "signed_bits (Suc n) k = signed_bits n (k div 2) * 2 + k mod 2"
haftmann@64015
   133
  using zero_not_eq_two by (simp add: signed_bits_eq_bits algebra_simps)
haftmann@64015
   134
haftmann@64015
   135
lemma signed_bits_of_0 [simp]:
haftmann@64015
   136
  "signed_bits n 0 = 0"
haftmann@64015
   137
  by (simp add: signed_bits_eq_bits bits_eq_mod)
haftmann@64015
   138
haftmann@64015
   139
lemma signed_bits_of_minus_1 [simp]:
haftmann@64015
   140
  "signed_bits n (- 1) = - 1"
haftmann@64015
   141
  by (induct n) simp_all
haftmann@64015
   142
haftmann@64015
   143
lemma signed_bits_eq_iff_bits_eq:
haftmann@64015
   144
  assumes "n > 0"
haftmann@64015
   145
  shows "signed_bits (n - Suc 0) k = signed_bits (n - Suc 0) l \<longleftrightarrow> bits n k = bits n l" (is "?P \<longleftrightarrow> ?Q")
haftmann@64015
   146
proof -
haftmann@64015
   147
  from assms obtain m where m: "n = Suc m"
haftmann@64015
   148
    by (cases n) auto
haftmann@64015
   149
  show ?thesis
haftmann@64015
   150
  proof 
haftmann@64015
   151
    assume ?Q
haftmann@64015
   152
    have "bits (Suc m) (k + 2 ^ m) =
haftmann@64015
   153
      bits (Suc m) (bits (Suc m) k + bits (Suc m) (2 ^ m))"
haftmann@64015
   154
      by (simp only: bits_plus)
haftmann@64015
   155
    also have "\<dots> =
haftmann@64015
   156
      bits (Suc m) (bits (Suc m) l + bits (Suc m) (2 ^ m))"
haftmann@64015
   157
      by (simp only: \<open>?Q\<close> m [symmetric])
haftmann@64015
   158
    also have "\<dots> = bits (Suc m) (l + 2 ^ m)"
haftmann@64015
   159
      by (simp only: bits_plus)
haftmann@64015
   160
    finally show ?P
haftmann@64015
   161
      by (simp only: signed_bits_eq_bits m) simp
haftmann@64015
   162
  next
haftmann@64015
   163
    assume ?P
haftmann@64015
   164
    with assms have "(k + 2 ^ (n - Suc 0)) mod 2 ^ n = (l + 2 ^ (n - Suc 0)) mod 2 ^ n"
haftmann@64015
   165
      by (simp add: signed_bits_eq_bits' bits_eq_mod)
haftmann@64015
   166
    then have "(i + (k + 2 ^ (n - Suc 0))) mod 2 ^ n = (i + (l + 2 ^ (n - Suc 0))) mod 2 ^ n" for i
haftmann@64015
   167
      by (metis mod_add_eq)
haftmann@64015
   168
    then have "k mod 2 ^ n = l mod 2 ^ n"
haftmann@64015
   169
      by (metis add_diff_cancel_right' uminus_add_conv_diff)
haftmann@64015
   170
    then show ?Q
haftmann@64015
   171
      by (simp add: bits_eq_mod)
haftmann@64015
   172
  qed
haftmann@64015
   173
qed 
haftmann@64015
   174
haftmann@64015
   175
haftmann@64015
   176
subsection \<open>Bit strings as quotient type\<close>
haftmann@64015
   177
haftmann@64015
   178
subsubsection \<open>Basic properties\<close>
haftmann@64015
   179
haftmann@64015
   180
quotient_type (overloaded) 'a word = int / "\<lambda>k l. bits LENGTH('a) k = bits LENGTH('a::len0) l"
haftmann@64015
   181
  by (auto intro!: equivpI reflpI sympI transpI)
haftmann@64015
   182
haftmann@64015
   183
instantiation word :: (len0) "{semiring_numeral, comm_semiring_0, comm_ring}"
haftmann@64015
   184
begin
haftmann@64015
   185
haftmann@64015
   186
lift_definition zero_word :: "'a word"
haftmann@64015
   187
  is 0
haftmann@64015
   188
  .
haftmann@64015
   189
haftmann@64015
   190
lift_definition one_word :: "'a word"
haftmann@64015
   191
  is 1
haftmann@64015
   192
  .
haftmann@64015
   193
haftmann@64015
   194
lift_definition plus_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
haftmann@64015
   195
  is plus
haftmann@64015
   196
  by (subst bits_plus [symmetric]) (simp add: bits_plus)
haftmann@64015
   197
haftmann@64015
   198
lift_definition uminus_word :: "'a word \<Rightarrow> 'a word"
haftmann@64015
   199
  is uminus
haftmann@64015
   200
  by (subst bits_uminus [symmetric]) (simp add: bits_uminus)
haftmann@64015
   201
haftmann@64015
   202
lift_definition minus_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
haftmann@64015
   203
  is minus
haftmann@64015
   204
  by (subst bits_minus [symmetric]) (simp add: bits_minus)
haftmann@64015
   205
haftmann@64015
   206
lift_definition times_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
haftmann@64015
   207
  is times
haftmann@64015
   208
  by (auto simp add: bits_eq_mod intro: mod_mult_cong)
haftmann@64015
   209
haftmann@64015
   210
instance
haftmann@64015
   211
  by standard (transfer; simp add: algebra_simps)+
haftmann@64015
   212
haftmann@64015
   213
end
haftmann@64015
   214
haftmann@64015
   215
instance word :: (len) comm_ring_1
haftmann@64015
   216
  by standard (transfer; simp)+
haftmann@64015
   217
haftmann@64015
   218
haftmann@64015
   219
subsubsection \<open>Conversions\<close>
haftmann@64015
   220
haftmann@64015
   221
lemma [transfer_rule]:
haftmann@64015
   222
  "rel_fun HOL.eq pcr_word int of_nat"
haftmann@64015
   223
proof -
haftmann@64015
   224
  note transfer_rule_of_nat [transfer_rule]
haftmann@64015
   225
  show ?thesis by transfer_prover
haftmann@64015
   226
qed
haftmann@64015
   227
  
haftmann@64015
   228
lemma [transfer_rule]:
haftmann@64015
   229
  "rel_fun HOL.eq pcr_word (\<lambda>k. k) of_int"
haftmann@64015
   230
proof -
haftmann@64015
   231
  note transfer_rule_of_int [transfer_rule]
haftmann@64015
   232
  have "rel_fun HOL.eq pcr_word (of_int :: int \<Rightarrow> int) (of_int :: int \<Rightarrow> 'a word)"
haftmann@64015
   233
    by transfer_prover
haftmann@64015
   234
  then show ?thesis by (simp add: id_def)
haftmann@64015
   235
qed
haftmann@64015
   236
haftmann@64015
   237
context semiring_1
haftmann@64015
   238
begin
haftmann@64015
   239
haftmann@64015
   240
lift_definition unsigned :: "'b::len0 word \<Rightarrow> 'a"
haftmann@64015
   241
  is "of_nat \<circ> nat \<circ> bits LENGTH('b)"
haftmann@64015
   242
  by simp
haftmann@64015
   243
haftmann@64015
   244
lemma unsigned_0 [simp]:
haftmann@64015
   245
  "unsigned 0 = 0"
haftmann@64015
   246
  by transfer simp
haftmann@64015
   247
haftmann@64015
   248
end
haftmann@64015
   249
haftmann@64015
   250
context semiring_char_0
haftmann@64015
   251
begin
haftmann@64015
   252
haftmann@64015
   253
lemma word_eq_iff_unsigned:
haftmann@64015
   254
  "a = b \<longleftrightarrow> unsigned a = unsigned b"
haftmann@64015
   255
  by safe (transfer; simp add: eq_nat_nat_iff)
haftmann@64015
   256
haftmann@64015
   257
end
haftmann@64015
   258
haftmann@64015
   259
context ring_1
haftmann@64015
   260
begin
haftmann@64015
   261
haftmann@64015
   262
lift_definition signed :: "'b::len word \<Rightarrow> 'a"
haftmann@64015
   263
  is "of_int \<circ> signed_bits (LENGTH('b) - 1)"
haftmann@64015
   264
  by (simp add: signed_bits_eq_iff_bits_eq [symmetric])
haftmann@64015
   265
haftmann@64015
   266
lemma signed_0 [simp]:
haftmann@64015
   267
  "signed 0 = 0"
haftmann@64015
   268
  by transfer simp
haftmann@64015
   269
haftmann@64015
   270
end
haftmann@64015
   271
haftmann@64015
   272
lemma unsigned_of_nat [simp]:
haftmann@64015
   273
  "unsigned (of_nat n :: 'a word) = bits LENGTH('a::len) n"
haftmann@64015
   274
  by transfer (simp add: nat_eq_iff bits_eq_mod zmod_int)
haftmann@64015
   275
haftmann@64015
   276
lemma of_nat_unsigned [simp]:
haftmann@64015
   277
  "of_nat (unsigned a) = a"
haftmann@64015
   278
  by transfer simp
haftmann@64015
   279
haftmann@64015
   280
lemma of_int_unsigned [simp]:
haftmann@64015
   281
  "of_int (unsigned a) = a"
haftmann@64015
   282
  by transfer simp
haftmann@64015
   283
haftmann@64015
   284
context ring_char_0
haftmann@64015
   285
begin
haftmann@64015
   286
haftmann@64015
   287
lemma word_eq_iff_signed:
haftmann@64015
   288
  "a = b \<longleftrightarrow> signed a = signed b"
haftmann@64015
   289
  by safe (transfer; auto simp add: signed_bits_eq_iff_bits_eq)
haftmann@64015
   290
haftmann@64015
   291
end
haftmann@64015
   292
haftmann@64015
   293
lemma signed_of_int [simp]:
haftmann@64015
   294
  "signed (of_int k :: 'a word) = signed_bits (LENGTH('a::len) - 1) k"
haftmann@64015
   295
  by transfer simp
haftmann@64015
   296
haftmann@64015
   297
lemma of_int_signed [simp]:
haftmann@64015
   298
  "of_int (signed a) = a"
haftmann@64015
   299
  by transfer (simp add: signed_bits_eq_bits bits_eq_mod zdiff_zmod_left)
haftmann@64015
   300
haftmann@64015
   301
haftmann@64015
   302
subsubsection \<open>Properties\<close>
haftmann@64015
   303
haftmann@64015
   304
haftmann@64015
   305
subsubsection \<open>Division\<close>
haftmann@64015
   306
haftmann@64015
   307
instantiation word :: (len0) modulo
haftmann@64015
   308
begin
haftmann@64015
   309
haftmann@64015
   310
lift_definition divide_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
haftmann@64015
   311
  is "\<lambda>a b. bits LENGTH('a) a div bits LENGTH('a) b"
haftmann@64015
   312
  by simp
haftmann@64015
   313
haftmann@64015
   314
lift_definition modulo_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> 'a word"
haftmann@64015
   315
  is "\<lambda>a b. bits LENGTH('a) a mod bits LENGTH('a) b"
haftmann@64015
   316
  by simp
haftmann@64015
   317
haftmann@64015
   318
instance ..
haftmann@64015
   319
haftmann@64015
   320
end
haftmann@64015
   321
haftmann@64015
   322
haftmann@64015
   323
subsubsection \<open>Orderings\<close>
haftmann@64015
   324
haftmann@64015
   325
instantiation word :: (len0) linorder
haftmann@64015
   326
begin
haftmann@64015
   327
haftmann@64015
   328
lift_definition less_eq_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> bool"
haftmann@64015
   329
  is "\<lambda>a b. bits LENGTH('a) a \<le> bits LENGTH('a) b"
haftmann@64015
   330
  by simp
haftmann@64015
   331
haftmann@64015
   332
lift_definition less_word :: "'a word \<Rightarrow> 'a word \<Rightarrow> bool"
haftmann@64015
   333
  is "\<lambda>a b. bits LENGTH('a) a < bits LENGTH('a) b"
haftmann@64015
   334
  by simp
haftmann@64015
   335
haftmann@64015
   336
instance
haftmann@64015
   337
  by standard (transfer; auto)+
haftmann@64015
   338
haftmann@64015
   339
end
haftmann@64015
   340
haftmann@64015
   341
context linordered_semidom
haftmann@64015
   342
begin
haftmann@64015
   343
haftmann@64015
   344
lemma word_less_eq_iff_unsigned:
haftmann@64015
   345
  "a \<le> b \<longleftrightarrow> unsigned a \<le> unsigned b"
haftmann@64015
   346
  by (transfer fixing: less_eq) (simp add: nat_le_eq_zle)
haftmann@64015
   347
haftmann@64015
   348
lemma word_less_iff_unsigned:
haftmann@64015
   349
  "a < b \<longleftrightarrow> unsigned a < unsigned b"
haftmann@64015
   350
  by (transfer fixing: less) (auto dest: preorder_class.le_less_trans [OF bits_nonnegative])
haftmann@64015
   351
haftmann@64015
   352
end
haftmann@64015
   353
haftmann@64015
   354
end