src/HOL/Word/Bit_Operations.thy
author wenzelm
Wed Dec 29 17:34:41 2010 +0100 (2010-12-29)
changeset 41413 64cd30d6b0b8
parent 37655 f4d616d41a59
child 53062 3af1a6020014
permissions -rw-r--r--
explicit file specifications -- avoid secondary load path;
haftmann@37655
     1
(*  Title:      HOL/Word/Bit_Operations.thy
haftmann@37655
     2
    Author:     Author: Brian Huffman, PSU and Gerwin Klein, NICTA
kleing@24334
     3
*)
kleing@24334
     4
haftmann@26559
     5
header {* Syntactic classes for bitwise operations *}
kleing@24333
     6
haftmann@37655
     7
theory Bit_Operations
wenzelm@41413
     8
imports "~~/src/HOL/Library/Bit"
kleing@24333
     9
begin
kleing@24333
    10
haftmann@29608
    11
class bit =
haftmann@26559
    12
  fixes bitNOT :: "'a \<Rightarrow> 'a"       ("NOT _" [70] 71)
haftmann@26559
    13
    and bitAND :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" (infixr "AND" 64)
haftmann@26559
    14
    and bitOR  :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" (infixr "OR"  59)
haftmann@26559
    15
    and bitXOR :: "'a \<Rightarrow> 'a \<Rightarrow> 'a" (infixr "XOR" 59)
kleing@24333
    16
kleing@24333
    17
text {*
kleing@24333
    18
  We want the bitwise operations to bind slightly weaker
kleing@24333
    19
  than @{text "+"} and @{text "-"}, but @{text "~~"} to 
kleing@24333
    20
  bind slightly stronger than @{text "*"}.
kleing@24333
    21
*}
huffman@24352
    22
kleing@24333
    23
text {*
kleing@24333
    24
  Testing and shifting operations.
kleing@24333
    25
*}
haftmann@26559
    26
haftmann@26559
    27
class bits = bit +
haftmann@26559
    28
  fixes test_bit :: "'a \<Rightarrow> nat \<Rightarrow> bool" (infixl "!!" 100)
haftmann@26559
    29
    and lsb      :: "'a \<Rightarrow> bool"
haftmann@26559
    30
    and set_bit  :: "'a \<Rightarrow> nat \<Rightarrow> bool \<Rightarrow> 'a"
haftmann@26559
    31
    and set_bits :: "(nat \<Rightarrow> bool) \<Rightarrow> 'a" (binder "BITS " 10)
haftmann@26559
    32
    and shiftl   :: "'a \<Rightarrow> nat \<Rightarrow> 'a" (infixl "<<" 55)
haftmann@26559
    33
    and shiftr   :: "'a \<Rightarrow> nat \<Rightarrow> 'a" (infixl ">>" 55)
haftmann@26559
    34
haftmann@26559
    35
class bitss = bits +
haftmann@26559
    36
  fixes msb      :: "'a \<Rightarrow> bool"
kleing@24333
    37
kleing@24333
    38
huffman@26086
    39
subsection {* Bitwise operations on @{typ bit} *}
kleing@24333
    40
haftmann@25762
    41
instantiation bit :: bit
haftmann@25762
    42
begin
haftmann@25762
    43
haftmann@26559
    44
primrec bitNOT_bit where
haftmann@37655
    45
  "NOT 0 = (1::bit)"
haftmann@37655
    46
  | "NOT 1 = (0::bit)"
haftmann@25762
    47
haftmann@26559
    48
primrec bitAND_bit where
haftmann@37655
    49
  "0 AND y = (0::bit)"
haftmann@37655
    50
  | "1 AND y = (y::bit)"
haftmann@25762
    51
haftmann@26559
    52
primrec bitOR_bit where
haftmann@37655
    53
  "0 OR y = (y::bit)"
haftmann@37655
    54
  | "1 OR y = (1::bit)"
haftmann@25762
    55
haftmann@26559
    56
primrec bitXOR_bit where
haftmann@37655
    57
  "0 XOR y = (y::bit)"
haftmann@37655
    58
  | "1 XOR y = (NOT y :: bit)"
haftmann@25762
    59
haftmann@25762
    60
instance  ..
haftmann@25762
    61
haftmann@25762
    62
end
kleing@24333
    63
haftmann@26559
    64
lemmas bit_simps =
haftmann@26559
    65
  bitNOT_bit.simps bitAND_bit.simps bitOR_bit.simps bitXOR_bit.simps
kleing@24333
    66
huffman@24366
    67
lemma bit_extra_simps [simp]: 
haftmann@37655
    68
  "x AND 0 = (0::bit)"
haftmann@37655
    69
  "x AND 1 = (x::bit)"
haftmann@37655
    70
  "x OR 1 = (1::bit)"
haftmann@37655
    71
  "x OR 0 = (x::bit)"
haftmann@37655
    72
  "x XOR 1 = NOT (x::bit)"
haftmann@37655
    73
  "x XOR 0 = (x::bit)"
huffman@24366
    74
  by (cases x, auto)+
huffman@24366
    75
huffman@24366
    76
lemma bit_ops_comm: 
huffman@24366
    77
  "(x::bit) AND y = y AND x"
huffman@24366
    78
  "(x::bit) OR y = y OR x"
huffman@24366
    79
  "(x::bit) XOR y = y XOR x"
huffman@24366
    80
  by (cases y, auto)+
huffman@24366
    81
huffman@24366
    82
lemma bit_ops_same [simp]: 
huffman@24366
    83
  "(x::bit) AND x = x"
huffman@24366
    84
  "(x::bit) OR x = x"
haftmann@37655
    85
  "(x::bit) XOR x = 0"
huffman@24366
    86
  by (cases x, auto)+
huffman@24366
    87
huffman@24366
    88
lemma bit_not_not [simp]: "NOT (NOT (x::bit)) = x"
huffman@24366
    89
  by (cases x) auto
kleing@24333
    90
kleing@24333
    91
end