| 1 |
(* ========================================================================== *) |
| 2 |
(* Formal verification of nonlinear inequalities in HOL Light *) |
| 3 |
(* *) |
| 4 |
(* Copyright (c) 2012 Alexey Solovyev *) |
| 5 |
(* *) |
| 6 |
(* This file is distributed under the terms of the MIT licence *) |
| 7 |
(* ========================================================================== *) |
| 8 |
|
| 9 |
(* -------------------------------------------------------------------------- *) |
| 10 |
(* Cached natural arithmetic *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
(* Dependencies *) |
| 14 |
needs "Formal_ineqs/arith_options.hl";; |
| 15 |
needs "Formal_ineqs/arith/arith_num.hl";; |
| 16 |
|
| 17 |
|
| 18 |
module Arith_cache = struct |
| 19 |
|
| 20 |
let cache_size = if !Arith_options.cached then !Arith_options.init_cache_size else 1;; |
| 21 |
|
| 22 |
(* Hash tables *) |
| 23 |
let my_add h key v = |
| 24 |
if Hashtbl.length h >= !Arith_options.max_cache_size then |
| 25 |
Hashtbl.clear h |
| 26 |
(* let _ = Hashtbl.clear h in |
| 27 |
print_string "Clearing a nat hash table" *) |
| 28 |
else (); |
| 29 |
Hashtbl.add h key v;; |
| 30 |
|
| 31 |
let le_table = Hashtbl.create cache_size and |
| 32 |
add_table = Hashtbl.create cache_size and |
| 33 |
sub_table = Hashtbl.create cache_size and |
| 34 |
sub_le_table = Hashtbl.create cache_size and |
| 35 |
mul_table = Hashtbl.create cache_size and |
| 36 |
div_table = Hashtbl.create cache_size;; |
| 37 |
|
| 38 |
(* Counters for collecting stats *) |
| 39 |
let suc_counter = ref 0 and |
| 40 |
eq0_counter = ref 0 and |
| 41 |
pre_counter = ref 0 and |
| 42 |
gt0_counter = ref 0 and |
| 43 |
lt_counter = ref 0 and |
| 44 |
le_counter = ref 0 and |
| 45 |
add_counter = ref 0 and |
| 46 |
sub_counter = ref 0 and |
| 47 |
sub_le_counter = ref 0 and |
| 48 |
mul_counter = ref 0 and |
| 49 |
div_counter = ref 0 and |
| 50 |
even_counter = ref 0 and |
| 51 |
odd_counter = ref 0;; |
| 52 |
|
| 53 |
|
| 54 |
(* Clears all cached results *) |
| 55 |
let reset_cache () = |
| 56 |
let clear = Hashtbl.clear in |
| 57 |
clear le_table; |
| 58 |
clear add_table; |
| 59 |
clear sub_table; |
| 60 |
clear sub_le_table; |
| 61 |
clear mul_table; |
| 62 |
clear div_table;; |
| 63 |
|
| 64 |
|
| 65 |
(* Resets all counters *) |
| 66 |
let reset_stat () = |
| 67 |
suc_counter := 0; |
| 68 |
eq0_counter := 0; |
| 69 |
pre_counter := 0; |
| 70 |
gt0_counter := 0; |
| 71 |
lt_counter := 0; |
| 72 |
le_counter := 0; |
| 73 |
add_counter := 0; |
| 74 |
sub_counter := 0; |
| 75 |
sub_le_counter := 0; |
| 76 |
mul_counter := 0; |
| 77 |
div_counter := 0; |
| 78 |
even_counter := 0; |
| 79 |
odd_counter := 0;; |
| 80 |
|
| 81 |
(* Prints stats *) |
| 82 |
let print_stat () = |
| 83 |
let len = Hashtbl.length in |
| 84 |
let suc_pre_str = sprintf "suc = %d\npre = %d\n" !suc_counter !pre_counter in |
| 85 |
let cmp0_str = sprintf "eq0 = %d\ngt0 = %d\n" !eq0_counter !gt0_counter in |
| 86 |
let lt_str = sprintf "lt = %d\n" !lt_counter in |
| 87 |
let even_odd_str = sprintf "even = %d\nodd = %d\n" !even_counter !odd_counter in |
| 88 |
let le_str = sprintf "le = %d (le_hash = %d)\n" !le_counter (len le_table) in |
| 89 |
let add_str = sprintf "add = %d (add_hash = %d)\n" !add_counter (len add_table) in |
| 90 |
let sub_str = sprintf "sub = %d (sub_hash = %d)\n" !sub_counter (len sub_table) in |
| 91 |
let sub_le_str = sprintf "sub_le = %d (sub_le_hash = %d)\n" !sub_le_counter (len sub_le_table) in |
| 92 |
let mul_str = sprintf "mul = %d (mul_hash = %d)\n" !mul_counter (len mul_table) in |
| 93 |
let div_str = sprintf "div = %d (div_hash = %d)\n" !div_counter (len div_table) in |
| 94 |
print_string (suc_pre_str ^ cmp0_str ^ lt_str ^ even_odd_str ^ |
| 95 |
le_str ^ add_str ^ sub_str ^ sub_le_str ^ mul_str ^ div_str);; |
| 96 |
|
| 97 |
|
| 98 |
(* Note: the standard Hashtbl.hash function works very purely on terms *) |
| 99 |
let rec num_tm_hash tm = |
| 100 |
if is_comb tm then |
| 101 |
let b_tm, n_tm = dest_comb tm in |
| 102 |
let str = (fst o dest_const) b_tm in |
| 103 |
str ^ num_tm_hash n_tm |
| 104 |
else |
| 105 |
"";; |
| 106 |
|
| 107 |
let op_tm_hash tm = |
| 108 |
let lhs, tm2 = dest_comb tm in |
| 109 |
let tm1 = rand lhs in |
| 110 |
num_tm_hash tm1 ^ "x" ^ num_tm_hash tm2;; |
| 111 |
|
| 112 |
|
| 113 |
let tm1_tm2_hash tm1 tm2 = |
| 114 |
num_tm_hash tm1 ^ "x" ^ num_tm_hash tm2;; |
| 115 |
|
| 116 |
|
| 117 |
(* SUC *) |
| 118 |
let raw_suc_conv_hash tm = |
| 119 |
let _ = suc_counter := !suc_counter + 1 in |
| 120 |
(* let _ = suc_list := tm :: !suc_list in *) |
| 121 |
Arith_num.raw_suc_conv_hash tm;; |
| 122 |
|
| 123 |
(* x = 0 *) |
| 124 |
let raw_eq0_hash_conv tm = |
| 125 |
let _ = eq0_counter := !eq0_counter + 1 in |
| 126 |
(* let _ = eq0_list := tm :: !eq0_list in *) |
| 127 |
Arith_num.raw_eq0_hash_conv tm;; |
| 128 |
|
| 129 |
(* PRE *) |
| 130 |
let raw_pre_hash_conv tm = |
| 131 |
let _ = pre_counter := !pre_counter + 1 in |
| 132 |
Arith_num.raw_pre_hash_conv tm;; |
| 133 |
|
| 134 |
(* x > 0 *) |
| 135 |
let raw_gt0_hash_conv tm = |
| 136 |
let _ = gt0_counter := !gt0_counter + 1 in |
| 137 |
Arith_num.raw_gt0_hash_conv tm;; |
| 138 |
|
| 139 |
(* x < y *) |
| 140 |
let raw_lt_hash_conv tm = |
| 141 |
let _ = lt_counter := !lt_counter + 1 in |
| 142 |
Arith_num.raw_lt_hash_conv tm;; |
| 143 |
|
| 144 |
(* x <= y *) |
| 145 |
let raw_le_hash_conv tm = |
| 146 |
let _ = le_counter := !le_counter + 1 in |
| 147 |
let hash = op_tm_hash tm in |
| 148 |
try |
| 149 |
Hashtbl.find le_table hash |
| 150 |
with Not_found -> |
| 151 |
let result = Arith_num.raw_le_hash_conv tm in |
| 152 |
let _ = my_add le_table hash result in |
| 153 |
result;; |
| 154 |
|
| 155 |
(* x + y *) |
| 156 |
let raw_add_conv_hash tm = |
| 157 |
let _ = add_counter := !add_counter + 1 in |
| 158 |
let hash = op_tm_hash tm in |
| 159 |
try |
| 160 |
Hashtbl.find add_table hash |
| 161 |
with Not_found -> |
| 162 |
let result = Arith_num.raw_add_conv_hash tm in |
| 163 |
let _ = my_add add_table hash result in |
| 164 |
result;; |
| 165 |
|
| 166 |
(* x - y *) |
| 167 |
let raw_sub_hash_conv tm = |
| 168 |
let _ = sub_counter := !sub_counter + 1 in |
| 169 |
let hash = op_tm_hash tm in |
| 170 |
try |
| 171 |
Hashtbl.find sub_table hash |
| 172 |
with Not_found -> |
| 173 |
let result = Arith_num.raw_sub_hash_conv tm in |
| 174 |
let _ = my_add sub_table hash result in |
| 175 |
result;; |
| 176 |
|
| 177 |
let raw_sub_and_le_hash_conv tm1 tm2 = |
| 178 |
let _ = sub_le_counter := !sub_le_counter + 1 in |
| 179 |
let hash = tm1_tm2_hash tm1 tm2 in |
| 180 |
try |
| 181 |
Hashtbl.find sub_le_table hash |
| 182 |
with Not_found -> |
| 183 |
let result = Arith_num.raw_sub_and_le_hash_conv tm1 tm2 in |
| 184 |
let _ = my_add sub_le_table hash result in |
| 185 |
result;; |
| 186 |
|
| 187 |
(* x * y *) |
| 188 |
let raw_mul_conv_hash tm = |
| 189 |
let _ = mul_counter := !mul_counter + 1 in |
| 190 |
let hash = op_tm_hash tm in |
| 191 |
try |
| 192 |
Hashtbl.find mul_table hash |
| 193 |
with Not_found -> |
| 194 |
let result = Arith_num.raw_mul_conv_hash tm in |
| 195 |
let _ = my_add mul_table hash result in |
| 196 |
result;; |
| 197 |
|
| 198 |
(* x / y *) |
| 199 |
let raw_div_hash_conv tm = |
| 200 |
let _ = div_counter := !div_counter + 1 in |
| 201 |
let hash = op_tm_hash tm in |
| 202 |
try |
| 203 |
Hashtbl.find div_table hash |
| 204 |
with Not_found -> |
| 205 |
let result = Arith_num.raw_div_hash_conv tm in |
| 206 |
let _ = my_add div_table hash result in |
| 207 |
result;; |
| 208 |
|
| 209 |
(* EVEN, ODD *) |
| 210 |
let raw_even_hash_conv tm = |
| 211 |
let _ = even_counter := !even_counter + 1 in |
| 212 |
Arith_num.raw_even_hash_conv tm;; |
| 213 |
|
| 214 |
let raw_odd_hash_conv tm = |
| 215 |
let _ = odd_counter := !odd_counter + 1 in |
| 216 |
Arith_num.raw_odd_hash_conv tm;; |
| 217 |
|
| 218 |
end;; |