| 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 |
(* Commonly used variables and constants *) |
| 11 |
(* -------------------------------------------------------------------------- *) |
| 12 |
|
| 13 |
module Misc_vars = struct |
| 14 |
|
| 15 |
(* A performance improvement trick from calc_num.ml *) |
| 16 |
let standardize, standardize_tm, standardize_list, standardize_reset, standardize_enable = |
| 17 |
(* TODO: a custom hash table module is required for good hash values *) |
| 18 |
let cache = Hashtbl.create 100 in |
| 19 |
let enabled = ref true in |
| 20 |
let find t = |
| 21 |
try Hashtbl.find cache t |
| 22 |
with Not_found -> Hashtbl.add cache t t; t in |
| 23 |
let rec replace tm = |
| 24 |
match tm with |
| 25 |
| Var _ | Const _ -> find tm |
| 26 |
| Comb (s, t) -> (* find @@*) mk_comb (replace s, replace t) |
| 27 |
| Abs (v, b) -> (* find @@*) mk_abs (replace v, replace b) in |
| 28 |
let st th = |
| 29 |
let concl' = replace (concl th) in |
| 30 |
EQ_MP (REFL concl') th in |
| 31 |
let get () = Hashtbl.fold (fun _ t ts -> t :: ts) cache [] in |
| 32 |
let reset () = Hashtbl.clear cache in |
| 33 |
let enable flag = enabled := flag in |
| 34 |
(fun th -> if !enabled then st th else th), |
| 35 |
(fun tm -> if !enabled then replace tm else tm), |
| 36 |
get, reset, enable;; |
| 37 |
|
| 38 |
(* bool variables *) |
| 39 |
let s_var_bool = standardize_tm `s:bool` and |
| 40 |
s1_var_bool = standardize_tm `s1:bool` and |
| 41 |
s2_var_bool = standardize_tm `s2:bool`;; |
| 42 |
|
| 43 |
(* num variables *) |
| 44 |
let n_var_num = standardize_tm `n:num` and |
| 45 |
m_var_num = standardize_tm `m:num` and |
| 46 |
t_var_num = standardize_tm `t:num` and |
| 47 |
p_var_num = standardize_tm `p:num` and |
| 48 |
q_var_num = standardize_tm `q:num` and |
| 49 |
k_var_num = standardize_tm `k:num` and |
| 50 |
e_var_num = standardize_tm `e:num` and |
| 51 |
e1_var_num = standardize_tm `e1:num` and |
| 52 |
e2_var_num = standardize_tm `e2:num` and |
| 53 |
r_var_num = standardize_tm `r:num` and |
| 54 |
r1_var_num = standardize_tm `r1:num` and |
| 55 |
r2_var_num = standardize_tm `r2:num` and |
| 56 |
n1_var_num = standardize_tm `n1:num` and |
| 57 |
n2_var_num = standardize_tm `n2:num` and |
| 58 |
m1_var_num = standardize_tm `m1:num` and |
| 59 |
m2_var_num = standardize_tm `m2:num` and |
| 60 |
x_var_num = standardize_tm `x:num` and |
| 61 |
y_var_num = standardize_tm `y:num` and |
| 62 |
i_var_num = standardize_tm `i:num` and |
| 63 |
j_var_num = standardize_tm `j:num`;; |
| 64 |
|
| 65 |
(* real variables *) |
| 66 |
let x_var_real = standardize_tm `x : real` and |
| 67 |
y_var_real = standardize_tm `y : real` and |
| 68 |
z_var_real = standardize_tm `z : real` and |
| 69 |
w_var_real = standardize_tm `w : real` and |
| 70 |
a_var_real = standardize_tm `a : real` and |
| 71 |
b_var_real = standardize_tm `b : real` and |
| 72 |
a1_var_real = standardize_tm `a1 : real` and |
| 73 |
a2_var_real = standardize_tm `a2 : real` and |
| 74 |
b1_var_real = standardize_tm `b1 : real` and |
| 75 |
b2_var_real = standardize_tm `b2 : real` and |
| 76 |
c_var_real = standardize_tm `c : real` and |
| 77 |
d_var_real = standardize_tm `d : real` and |
| 78 |
h_var_real = standardize_tm `h : real` and |
| 79 |
m_var_real = standardize_tm `m : real` and |
| 80 |
n_var_real = standardize_tm `n : real` and |
| 81 |
r_var_real = standardize_tm `r : real` and |
| 82 |
x1_var_real = standardize_tm `x1 : real` and |
| 83 |
x2_var_real = standardize_tm `x2 : real` and |
| 84 |
y1_var_real = standardize_tm `y1 : real` and |
| 85 |
y2_var_real = standardize_tm `y2 : real` and |
| 86 |
f1_var_real = standardize_tm `f1 : real` and |
| 87 |
f2_var_real = standardize_tm `f2 : real` and |
| 88 |
f_var_fun = standardize_tm `f : real->real` and |
| 89 |
g_var_fun = standardize_tm `g : real->real` and |
| 90 |
f1_var_fun = standardize_tm `f1 : real->real` and |
| 91 |
f2_var_fun = standardize_tm `f2 : real->real` and |
| 92 |
int_var = standardize_tm `int : real#real` and |
| 93 |
f_bounds_var = standardize_tm `f_bounds : real#real` and |
| 94 |
df_bounds_var = standardize_tm `df_bounds : real#real` and |
| 95 |
dd_bounds_var = standardize_tm `dd_bounds : real#real` and |
| 96 |
x_lo_var = standardize_tm `x_lo : real` and |
| 97 |
x_hi_var = standardize_tm `x_hi : real` and |
| 98 |
low_var_real = standardize_tm `low : real` and |
| 99 |
high_var_real = standardize_tm `high : real` and |
| 100 |
lo_var_real = standardize_tm `lo : real` and |
| 101 |
hi_var_real = standardize_tm `hi : real` and |
| 102 |
dd_var_real = standardize_tm `dd : real` and |
| 103 |
df_lo_var = standardize_tm `df_lo : real` and |
| 104 |
df_hi_var = standardize_tm `df_hi : real` and |
| 105 |
df_var_real = standardize_tm `df : real` and |
| 106 |
f_lo_var = standardize_tm `f_lo : real` and |
| 107 |
f_hi_var = standardize_tm `f_hi : real` and |
| 108 |
w1_var_real = standardize_tm `w1 : real` and |
| 109 |
w2_var_real = standardize_tm `w2 : real` and |
| 110 |
t_var_real = standardize_tm `t : real` and |
| 111 |
g_bounds_var = standardize_tm `g_bounds : real#real` and |
| 112 |
dg_bounds_var = standardize_tm `dg_bounds : real#real` and |
| 113 |
bounds_var = standardize_tm `bounds : real#real` and |
| 114 |
d_bounds_var = standardize_tm `d_bounds : real#real` and |
| 115 |
x0_var_real = standardize_tm `x0 : real` and |
| 116 |
z0_var_real = standardize_tm `z0 : real` and |
| 117 |
w0_var_real = standardize_tm `w0 : real` and |
| 118 |
error_var = standardize_tm `error : real` and |
| 119 |
d_bounds_list_var = standardize_tm `d_bounds_list : (real#real)list` and |
| 120 |
dd_bounds_list_var = standardize_tm `dd_bounds_list : ((real#real)list)list` and |
| 121 |
df_bounds_list_var = standardize_tm `df_bounds_list : (real#real)list` and |
| 122 |
dd_list_var = standardize_tm `dd_list : (real#real)list` and |
| 123 |
t_var_real_list = standardize_tm `t:(real)list` and |
| 124 |
x_var_real_list = standardize_tm `x:(real)list` and |
| 125 |
y_var_real_list = standardize_tm `y:(real)list` and |
| 126 |
z_var_real_list = standardize_tm `z:(real)list` and |
| 127 |
w_var_real_list = standardize_tm `w:(real)list` and |
| 128 |
yw_var = standardize_tm `yw : (real#real)list` and |
| 129 |
xz_var = standardize_tm `xz : (real#real)list` and |
| 130 |
xz_pair_var = standardize_tm `xz : real#real` and |
| 131 |
yw_pair_var = standardize_tm `yw : real#real` and |
| 132 |
list_var_real_pair = standardize_tm `list : (real#real)list`;; |
| 133 |
|
| 134 |
(* bool constants *) |
| 135 |
let t_const = standardize_tm `T` and |
| 136 |
f_const = standardize_tm `F`;; |
| 137 |
|
| 138 |
(* num constants *) |
| 139 |
let zero_const = standardize_tm `_0` and |
| 140 |
zero_num = standardize_tm `0`;; |
| 141 |
|
| 142 |
(* num operations *) |
| 143 |
let add_op_num = standardize_tm `(+) : num->num->num` and |
| 144 |
sub_op_num = standardize_tm `(-) : num->num->num` and |
| 145 |
mul_op_num = standardize_tm `( * ) : num->num->num` and |
| 146 |
eq_op_num = standardize_tm `(=) : num->num->bool` and |
| 147 |
le_op_num = standardize_tm `(<=) : num->num->bool` and |
| 148 |
lt_op_num = standardize_tm `(<) : num->num->bool` and |
| 149 |
div_op_num = standardize_tm `(DIV): num->num->num` and |
| 150 |
pre_op_num = standardize_tm `PRE: num->num` and |
| 151 |
suc_op_num = standardize_tm `SUC : num->num`;; |
| 152 |
|
| 153 |
|
| 154 |
(* real constants *) |
| 155 |
let real_empty_list = standardize_tm `[]:(real)list`;; |
| 156 |
|
| 157 |
(* real operations *) |
| 158 |
let add_op_real = standardize_tm `(+) : real->real->real` and |
| 159 |
mul_op_real = standardize_tm `( * ) : real->real->real` and |
| 160 |
sub_op_real = standardize_tm `(-) : real->real->real` and |
| 161 |
div_op_real = standardize_tm `(/) :real->real->real` and |
| 162 |
inv_op_real = standardize_tm `inv : real->real` and |
| 163 |
neg_op_real = standardize_tm `(--) : real->real` and |
| 164 |
eq_op_real = standardize_tm `(=) : real->real->bool` and |
| 165 |
lt_op_real = standardize_tm `(<) : real->real->bool` and |
| 166 |
le_op_real = standardize_tm `(<=):real->real->bool` and |
| 167 |
ge_op_real = standardize_tm `(>=):real->real->bool` and |
| 168 |
amp_op_real = standardize_tm `(&) : num->real` and |
| 169 |
pow_op_real = standardize_tm `(pow) : real->num->real`;; |
| 170 |
|
| 171 |
(* types *) |
| 172 |
let real_ty = `:real` and |
| 173 |
real_list_ty = `:(real)list` and |
| 174 |
real_pair_ty = `:real#real` and |
| 175 |
real_pair_list_ty = `:(real#real)list` and |
| 176 |
num_type = `:num` and |
| 177 |
nty = `:N`;; |
| 178 |
|
| 179 |
|
| 180 |
(* Simple operations *) |
| 181 |
let mk_real_list tms = mk_list (tms, real_ty);; |
| 182 |
|
| 183 |
let mk_names n prefix = map (fun i -> prefix^(string_of_int i)) (1--n);; |
| 184 |
|
| 185 |
let mk_real_vars n prefix = map (C (curry mk_var) real_ty) (mk_names n prefix);; |
| 186 |
|
| 187 |
|
| 188 |
end;; |