syntactic classes for bit operations
authorhaftmann
Fri Apr 04 13:40:26 2008 +0200 (2008-04-04)
changeset 26559799983936aad
parent 26558 7fcc10088e72
child 26560 d2fc9a18ee8a
syntactic classes for bit operations
src/HOL/Word/BitSyntax.thy
src/HOL/Word/WordDefinition.thy
     1.1 --- a/src/HOL/Word/BitSyntax.thy	Fri Apr 04 13:40:25 2008 +0200
     1.2 +++ b/src/HOL/Word/BitSyntax.thy	Fri Apr 04 13:40:26 2008 +0200
     1.3 @@ -6,17 +6,17 @@
     1.4  *)
     1.5  
     1.6  
     1.7 -header {* Syntactic class for bitwise operations *}
     1.8 +header {* Syntactic classes for bitwise operations *}
     1.9  
    1.10  theory BitSyntax
    1.11 -imports Main Num_Lemmas
    1.12 +imports BinGeneral
    1.13  begin
    1.14  
    1.15  class bit = type +
    1.16 -  fixes bitNOT :: "'a \<Rightarrow> 'a"
    1.17 -    and bitAND :: "'a \<Rightarrow> 'a \<Rightarrow> 'a"
    1.18 -    and bitOR  :: "'a \<Rightarrow> 'a \<Rightarrow> 'a"
    1.19 -    and bitXOR :: "'a \<Rightarrow> 'a \<Rightarrow> 'a"
    1.20 +  fixes bitNOT :: "'a \<Rightarrow> 'a"       ("NOT _" [70] 71)
    1.21 +    and bitAND :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" (infixr "AND" 64)
    1.22 +    and bitOR  :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" (infixr "OR"  59)
    1.23 +    and bitXOR :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" (infixr "XOR" 59)
    1.24  
    1.25  text {*
    1.26    We want the bitwise operations to bind slightly weaker
    1.27 @@ -24,23 +24,20 @@
    1.28    bind slightly stronger than @{text "*"}.
    1.29  *}
    1.30  
    1.31 -notation
    1.32 -  bitNOT  ("NOT _" [70] 71) and
    1.33 -  bitAND  (infixr "AND" 64) and
    1.34 -  bitOR   (infixr "OR"  59) and
    1.35 -  bitXOR  (infixr "XOR" 59)
    1.36 -
    1.37  text {*
    1.38    Testing and shifting operations.
    1.39  *}
    1.40 -consts
    1.41 -  test_bit :: "'a::bit \<Rightarrow> nat \<Rightarrow> bool" (infixl "!!" 100)
    1.42 -  lsb      :: "'a::bit \<Rightarrow> bool"
    1.43 -  msb      :: "'a::bit \<Rightarrow> bool"
    1.44 -  set_bit  :: "'a::bit \<Rightarrow> nat \<Rightarrow> bool \<Rightarrow> 'a"
    1.45 -  set_bits :: "(nat \<Rightarrow> bool) \<Rightarrow> 'a::bit" (binder "BITS " 10)
    1.46 -  shiftl   :: "'a::bit \<Rightarrow> nat \<Rightarrow> 'a" (infixl "<<" 55)
    1.47 -  shiftr   :: "'a::bit \<Rightarrow> nat \<Rightarrow> 'a" (infixl ">>" 55)
    1.48 +
    1.49 +class bits = bit +
    1.50 +  fixes test_bit :: "'a \<Rightarrow> nat \<Rightarrow> bool" (infixl "!!" 100)
    1.51 +    and lsb      :: "'a \<Rightarrow> bool"
    1.52 +    and set_bit  :: "'a \<Rightarrow> nat \<Rightarrow> bool \<Rightarrow> 'a"
    1.53 +    and set_bits :: "(nat \<Rightarrow> bool) \<Rightarrow> 'a" (binder "BITS " 10)
    1.54 +    and shiftl   :: "'a \<Rightarrow> nat \<Rightarrow> 'a" (infixl "<<" 55)
    1.55 +    and shiftr   :: "'a \<Rightarrow> nat \<Rightarrow> 'a" (infixl ">>" 55)
    1.56 +
    1.57 +class bitss = bits +
    1.58 +  fixes msb      :: "'a \<Rightarrow> bool"
    1.59  
    1.60  
    1.61  subsection {* Bitwise operations on @{typ bit} *}
    1.62 @@ -48,33 +45,28 @@
    1.63  instantiation bit :: bit
    1.64  begin
    1.65  
    1.66 -definition
    1.67 -  NOT_bit_def: "NOT x = (case x of bit.B0 \<Rightarrow> bit.B1 | bit.B1 \<Rightarrow> bit.B0)"
    1.68 +primrec bitNOT_bit where
    1.69 +  "NOT bit.B0 = bit.B1"
    1.70 +  | "NOT bit.B1 = bit.B0"
    1.71  
    1.72 -definition
    1.73 -  AND_bit_def: "x AND y = (case x of bit.B0 \<Rightarrow> bit.B0 | bit.B1 \<Rightarrow> y)"
    1.74 +primrec bitAND_bit where
    1.75 +  "bit.B0 AND y = bit.B0"
    1.76 +  | "bit.B1 AND y = y"
    1.77  
    1.78 -definition
    1.79 -  OR_bit_def: "(x OR y \<Colon> bit) = NOT (NOT x AND NOT y)"
    1.80 +primrec bitOR_bit where
    1.81 +  "bit.B0 OR y = y"
    1.82 +  | "bit.B1 OR y = bit.B1"
    1.83  
    1.84 -definition
    1.85 -  XOR_bit_def: "(x XOR y \<Colon> bit) = (x AND NOT y) OR (NOT x AND y)"
    1.86 +primrec bitXOR_bit where
    1.87 +  "bit.B0 XOR y = y"
    1.88 +  | "bit.B1 XOR y = NOT y"
    1.89  
    1.90  instance  ..
    1.91  
    1.92  end
    1.93  
    1.94 -lemma bit_simps [simp]:
    1.95 -  "NOT bit.B0 = bit.B1"
    1.96 -  "NOT bit.B1 = bit.B0"
    1.97 -  "bit.B0 AND y = bit.B0"
    1.98 -  "bit.B1 AND y = y"
    1.99 -  "bit.B0 OR y = y"
   1.100 -  "bit.B1 OR y = bit.B1"
   1.101 -  "bit.B0 XOR y = y"
   1.102 -  "bit.B1 XOR y = NOT y"
   1.103 -  by (simp_all add: NOT_bit_def AND_bit_def OR_bit_def
   1.104 -                    XOR_bit_def split: bit.split)
   1.105 +lemmas bit_simps =
   1.106 +  bitNOT_bit.simps bitAND_bit.simps bitOR_bit.simps bitXOR_bit.simps
   1.107  
   1.108  lemma bit_extra_simps [simp]: 
   1.109    "x AND bit.B0 = bit.B0"
     2.1 --- a/src/HOL/Word/WordDefinition.thy	Fri Apr 04 13:40:25 2008 +0200
     2.2 +++ b/src/HOL/Word/WordDefinition.thy	Fri Apr 04 13:40:26 2008 +0200
     2.3 @@ -8,7 +8,9 @@
     2.4  
     2.5  header {* Definition of Word Type *}
     2.6  
     2.7 -theory WordDefinition imports Size BinBoolList TdThs begin
     2.8 +theory WordDefinition
     2.9 +imports Size BinBoolList TdThs
    2.10 +begin
    2.11  
    2.12  typedef (open word) 'a word
    2.13    = "{(0::int) ..< 2^len_of TYPE('a::len0)}" by auto
    2.14 @@ -97,9 +99,8 @@
    2.15  declare uint_def [code func del]
    2.16  
    2.17  lemma [code func]: "uint (word_of_int w \<Colon> 'a\<Colon>len0 word) = bintrunc (len_of TYPE('a)) w"
    2.18 -  unfolding uint_def word_of_int_def
    2.19 -  apply (rule Abs_word_inverse)
    2.20 -  using range_bintrunc by auto
    2.21 +  by (auto simp add: uint_def word_of_int_def intro!: Abs_word_inverse)
    2.22 +    (insert range_bintrunc, auto)
    2.23  
    2.24  instantiation word :: (len0) "{number, uminus, minus, plus, one, zero, times, Divides.div, power, ord, bit}"
    2.25  begin
    2.26 @@ -187,25 +188,54 @@
    2.27    "(x <s y) == (x <=s y & x ~= y)"
    2.28  
    2.29  
    2.30 +
    2.31  subsection "Bit-wise operations"
    2.32  
    2.33 -defs (overloaded)
    2.34 -  word_test_bit_def: 
    2.35 -  "test_bit (a::'a::len0 word) == bin_nth (uint a)"
    2.36 +
    2.37 +
    2.38 +instantiation word :: (len0) bits
    2.39 +begin
    2.40  
    2.41 -  word_set_bit_def: 
    2.42 -  "set_bit (a::'a::len0 word) n x == 
    2.43 +definition
    2.44 +  word_test_bit_def: "test_bit a = bin_nth (uint a)"
    2.45 +
    2.46 +definition
    2.47 +  word_set_bit_def: "set_bit a n x =
    2.48     word_of_int (bin_sc n (If x bit.B1 bit.B0) (uint a))"
    2.49  
    2.50 -  word_set_bits_def:  
    2.51 -  "(BITS n. f n)::'a::len0 word == of_bl (bl_of_nth (len_of TYPE ('a)) f)"
    2.52 +definition
    2.53 +  word_set_bits_def: "(BITS n. f n) = of_bl (bl_of_nth (len_of TYPE ('a)) f)"
    2.54 +
    2.55 +definition
    2.56 +  word_lsb_def: "lsb a \<longleftrightarrow> bin_last (uint a) = bit.B1"
    2.57 +
    2.58 +definition shiftl1 :: "'a word \<Rightarrow> 'a word" where
    2.59 +  "shiftl1 w = word_of_int (uint w BIT bit.B0)"
    2.60 +
    2.61 +definition shiftr1 :: "'a word \<Rightarrow> 'a word" where
    2.62 +  -- "shift right as unsigned or as signed, ie logical or arithmetic"
    2.63 +  "shiftr1 w = word_of_int (bin_rest (uint w))"
    2.64 +
    2.65 +definition
    2.66 +  shiftl_def: "w << n = (shiftl1 ^ n) w"
    2.67  
    2.68 -  word_lsb_def: 
    2.69 -  "lsb (a::'a::len0 word) == bin_last (uint a) = bit.B1"
    2.70 +definition
    2.71 +  shiftr_def: "w >> n = (shiftr1 ^ n) w"
    2.72 +
    2.73 +instance ..
    2.74 +
    2.75 +end
    2.76  
    2.77 +instantiation word :: (len) bitss
    2.78 +begin
    2.79 +
    2.80 +definition
    2.81    word_msb_def: 
    2.82 -  "msb (a::'a::len word) == bin_sign (sint a) = Int.Min"
    2.83 +  "msb a \<longleftrightarrow> bin_sign (sint a) = Int.Min"
    2.84  
    2.85 +instance ..
    2.86 +
    2.87 +end
    2.88  
    2.89  constdefs
    2.90    setBit :: "'a :: len0 word => nat => 'a word" 
    2.91 @@ -218,13 +248,6 @@
    2.92  subsection "Shift operations"
    2.93  
    2.94  constdefs
    2.95 -  shiftl1 :: "'a :: len0 word => 'a word"
    2.96 -  "shiftl1 w == word_of_int (uint w BIT bit.B0)"
    2.97 -
    2.98 -  -- "shift right as unsigned or as signed, ie logical or arithmetic"
    2.99 -  shiftr1 :: "'a :: len0 word => 'a word"
   2.100 -  "shiftr1 w == word_of_int (bin_rest (uint w))"
   2.101 -
   2.102    sshiftr1 :: "'a :: len word => 'a word" 
   2.103    "sshiftr1 w == word_of_int (bin_rest (sint w))"
   2.104  
   2.105 @@ -247,11 +270,6 @@
   2.106    "slice n w == slice1 (size w - n) w"
   2.107  
   2.108  
   2.109 -defs (overloaded)
   2.110 -  shiftl_def: "(w::'a::len0 word) << n == (shiftl1 ^ n) w"
   2.111 -  shiftr_def: "(w::'a::len0 word) >> n == (shiftr1 ^ n) w"
   2.112 -
   2.113 -
   2.114  subsection "Rotation"
   2.115  
   2.116  constdefs
   2.117 @@ -304,7 +322,6 @@
   2.118    "of_bool True = 1"
   2.119  
   2.120  
   2.121 -
   2.122  lemmas of_nth_def = word_set_bits_def
   2.123  
   2.124  lemmas word_size_gt_0 [iff] = 
   2.125 @@ -936,7 +953,7 @@
   2.126  lemmas ucast_down_bl = ucast_down_bl' [OF refl]
   2.127  
   2.128  lemmas slice_def' = slice_def [unfolded word_size]
   2.129 -lemmas test_bit_def' = word_test_bit_def [THEN meta_eq_to_obj_eq, THEN fun_cong]
   2.130 +lemmas test_bit_def' = word_test_bit_def [THEN fun_cong]
   2.131  
   2.132  lemmas word_log_defs = word_and_def word_or_def word_xor_def word_not_def
   2.133  lemmas word_log_bin_defs = word_log_defs