src/HOL/Library/Old_SMT/old_smt_word.ML
author blanchet
Thu Aug 28 00:40:38 2014 +0200 (2014-08-28)
changeset 58058 1a0b18176548
parent 58057 src/HOL/Library/Old_SMT/smt_word.ML@883f3c4c928e
child 58825 2065f49da190
permissions -rw-r--r--
add 'old_' prefix to SMT file names; add 'Old_' to ML module names;
blanchet@58058
     1
(*  Title:      HOL/Library/Old_SMT/old_smt_word.ML
boehmes@41060
     2
    Author:     Sascha Boehme, TU Muenchen
boehmes@41060
     3
boehmes@41060
     4
SMT setup for words.
boehmes@41060
     5
*)
boehmes@41060
     6
blanchet@58058
     7
signature OLD_SMT_WORD =
boehmes@41060
     8
sig
boehmes@41060
     9
  val setup: theory -> theory
boehmes@41060
    10
end
boehmes@41060
    11
blanchet@58058
    12
structure Old_SMT_Word: OLD_SMT_WORD =
boehmes@41060
    13
struct
boehmes@41060
    14
thomas@47567
    15
open Word_Lib
boehmes@41060
    16
boehmes@41060
    17
(* SMT-LIB logic *)
boehmes@41060
    18
boehmes@41060
    19
fun smtlib_logic ts =
boehmes@41060
    20
  if exists (Term.exists_type (Term.exists_subtype is_wordT)) ts
boehmes@41060
    21
  then SOME "QF_AUFBV"
boehmes@41060
    22
  else NONE
boehmes@41060
    23
boehmes@41060
    24
boehmes@41060
    25
(* SMT-LIB builtins *)
boehmes@41060
    26
boehmes@41060
    27
local
blanchet@58058
    28
  val smtlibC = Old_SMTLIB_Interface.smtlibC
boehmes@41061
    29
boehmes@41061
    30
  val wordT = @{typ "'a::len word"}
boehmes@41061
    31
boehmes@41060
    32
  fun index1 n i = n ^ "[" ^ string_of_int i ^ "]"
boehmes@41060
    33
  fun index2 n i j = n ^ "[" ^ string_of_int i ^ ":" ^ string_of_int j ^ "]"
boehmes@41060
    34
boehmes@41061
    35
  fun word_typ (Type (@{type_name word}, [T])) =
boehmes@41060
    36
        Option.map (index1 "BitVec") (try dest_binT T)
boehmes@41061
    37
    | word_typ _ = NONE
boehmes@41060
    38
boehmes@41061
    39
  fun word_num (Type (@{type_name word}, [T])) i =
boehmes@41060
    40
        Option.map (index1 ("bv" ^ string_of_int i)) (try dest_binT T)
boehmes@41061
    41
    | word_num _ _ = NONE
boehmes@41060
    42
boehmes@41281
    43
  fun if_fixed pred m n T ts =
boehmes@41127
    44
    let val (Us, U) = Term.strip_type T
boehmes@41127
    45
    in
boehmes@41281
    46
      if pred (U, Us) then
boehmes@41281
    47
        SOME (n, length Us, ts, Term.list_comb o pair (Const (m, T)))
boehmes@41127
    48
      else NONE
boehmes@41127
    49
    end
boehmes@41061
    50
boehmes@41281
    51
  fun if_fixed_all m = if_fixed (forall (can dest_wordT) o (op ::)) m
boehmes@41281
    52
  fun if_fixed_args m = if_fixed (forall (can dest_wordT) o snd) m
boehmes@41281
    53
boehmes@41061
    54
  fun add_word_fun f (t, n) =
wenzelm@46124
    55
    let val (m, _) = Term.dest_Const t
blanchet@58058
    56
    in Old_SMT_Builtin.add_builtin_fun smtlibC (Term.dest_Const t, K (f m n)) end
boehmes@41281
    57
boehmes@41281
    58
  fun hd2 xs = hd (tl xs)
boehmes@41061
    59
boehmes@41281
    60
  fun mk_nat i = @{const nat} $ HOLogic.mk_number @{typ nat} i
boehmes@41281
    61
boehmes@41281
    62
  fun dest_nat (@{const nat} $ n) = snd (HOLogic.dest_number n)
boehmes@41281
    63
    | dest_nat t = raise TERM ("not a natural number", [t])
boehmes@41281
    64
boehmes@41281
    65
  fun mk_shift c [t, u] = Const c $ t $ mk_nat (snd (HOLogic.dest_number u))
boehmes@41281
    66
    | mk_shift c ts = raise TERM ("bad arguments", Const c :: ts)
boehmes@41061
    67
boehmes@41281
    68
  fun shift m n T ts =
boehmes@41281
    69
    let val U = Term.domain_type T
boehmes@41281
    70
    in
boehmes@41281
    71
      (case (can dest_wordT U, try (dest_nat o hd2) ts) of
boehmes@41281
    72
        (true, SOME i) =>
boehmes@41281
    73
          SOME (n, 2, [hd ts, HOLogic.mk_number U i], mk_shift (m, T))
boehmes@41281
    74
      | _ => NONE)   (* FIXME: also support non-numerical shifts *)
boehmes@41281
    75
    end
boehmes@41060
    76
boehmes@41281
    77
  fun mk_extract c i ts = Term.list_comb (Const c, mk_nat i :: ts)
boehmes@41281
    78
boehmes@41281
    79
  fun extract m n T ts =
boehmes@41281
    80
    let val U = Term.range_type (Term.range_type T)
boehmes@41060
    81
    in
boehmes@41281
    82
      (case (try (dest_nat o hd) ts, try dest_wordT U) of
boehmes@41281
    83
        (SOME lb, SOME i) =>
boehmes@41281
    84
          SOME (index2 n (i + lb - 1) lb, 1, tl ts, mk_extract (m, T) lb)
boehmes@41060
    85
      | _ => NONE)
boehmes@41060
    86
    end
boehmes@41060
    87
boehmes@41281
    88
  fun mk_extend c ts = Term.list_comb (Const c, ts)
boehmes@41061
    89
boehmes@41281
    90
  fun extend m n T ts =
boehmes@41281
    91
    let val (U1, U2) = Term.dest_funT T
boehmes@41281
    92
    in
boehmes@41281
    93
      (case (try dest_wordT U1, try dest_wordT U2) of
boehmes@41281
    94
        (SOME i, SOME j) =>
boehmes@41281
    95
          if j-i >= 0 then SOME (index1 n (j-i), 1, ts, mk_extend (m, T))
boehmes@41281
    96
          else NONE
boehmes@41281
    97
      | _ => NONE)
boehmes@41281
    98
    end
boehmes@41060
    99
boehmes@41281
   100
  fun mk_rotate c i ts = Term.list_comb (Const c, mk_nat i :: ts)
boehmes@41281
   101
boehmes@41281
   102
  fun rotate m n T ts =
boehmes@41281
   103
    let val U = Term.domain_type (Term.range_type T)
boehmes@41127
   104
    in
boehmes@41281
   105
      (case (can dest_wordT U, try (dest_nat o hd) ts) of
boehmes@41281
   106
        (true, SOME i) => SOME (index1 n i, 1, tl ts, mk_rotate (m, T) i)
boehmes@41281
   107
      | _ => NONE)
boehmes@41127
   108
    end
boehmes@41060
   109
in
boehmes@41060
   110
boehmes@41061
   111
val setup_builtins =
blanchet@58058
   112
  Old_SMT_Builtin.add_builtin_typ smtlibC (wordT, word_typ, word_num) #>
boehmes@41281
   113
  fold (add_word_fun if_fixed_all) [
boehmes@41061
   114
    (@{term "uminus :: 'a::len word => _"}, "bvneg"),
boehmes@41061
   115
    (@{term "plus :: 'a::len word => _"}, "bvadd"),
boehmes@41061
   116
    (@{term "minus :: 'a::len word => _"}, "bvsub"),
boehmes@41061
   117
    (@{term "times :: 'a::len word => _"}, "bvmul"),
boehmes@41061
   118
    (@{term "bitNOT :: 'a::len word => _"}, "bvnot"),
boehmes@41061
   119
    (@{term "bitAND :: 'a::len word => _"}, "bvand"),
boehmes@41061
   120
    (@{term "bitOR :: 'a::len word => _"}, "bvor"),
boehmes@41061
   121
    (@{term "bitXOR :: 'a::len word => _"}, "bvxor"),
boehmes@41061
   122
    (@{term "word_cat :: 'a::len word => _"}, "concat") ] #>
boehmes@41061
   123
  fold (add_word_fun shift) [
boehmes@41061
   124
    (@{term "shiftl :: 'a::len word => _ "}, "bvshl"),
boehmes@41061
   125
    (@{term "shiftr :: 'a::len word => _"}, "bvlshr"),
boehmes@41061
   126
    (@{term "sshiftr :: 'a::len word => _"}, "bvashr") ] #>
boehmes@41061
   127
  add_word_fun extract
boehmes@41061
   128
    (@{term "slice :: _ => 'a::len word => _"}, "extract") #>
boehmes@41061
   129
  fold (add_word_fun extend) [
boehmes@41061
   130
    (@{term "ucast :: 'a::len word => _"}, "zero_extend"),
boehmes@41061
   131
    (@{term "scast :: 'a::len word => _"}, "sign_extend") ] #>
boehmes@41061
   132
  fold (add_word_fun rotate) [
boehmes@41061
   133
    (@{term word_rotl}, "rotate_left"),
boehmes@41061
   134
    (@{term word_rotr}, "rotate_right") ] #>
boehmes@41281
   135
  fold (add_word_fun if_fixed_args) [
boehmes@41061
   136
    (@{term "less :: 'a::len word => _"}, "bvult"),
boehmes@41061
   137
    (@{term "less_eq :: 'a::len word => _"}, "bvule"),
boehmes@41061
   138
    (@{term word_sless}, "bvslt"),
boehmes@41061
   139
    (@{term word_sle}, "bvsle") ]
boehmes@41060
   140
boehmes@41060
   141
end
boehmes@41060
   142
boehmes@41060
   143
boehmes@41060
   144
(* setup *)
boehmes@41060
   145
boehmes@41060
   146
val setup = 
boehmes@41072
   147
  Context.theory_map (
blanchet@58058
   148
    Old_SMTLIB_Interface.add_logic (20, smtlib_logic) #>
boehmes@41072
   149
    setup_builtins)
boehmes@41060
   150
boehmes@41060
   151
end