Debian Codegraph @

Formal_ineqs/arith/arith_cache.hl

raw
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;;