(* ========================================================================== *) (* Formal verification of nonlinear inequalities in HOL Light *) (* *) (* Copyright (c) 2012 Alexey Solovyev *) (* *) (* This file is distributed under the terms of the MIT licence *) (* ========================================================================== *) (* -------------------------------------------------------------------------- *) (* Commonly used variables and constants *) (* -------------------------------------------------------------------------- *) module Misc_vars = struct (* A performance improvement trick from calc_num.ml *) let standardize, standardize_tm, standardize_list, standardize_reset, standardize_enable = (* TODO: a custom hash table module is required for good hash values *) let cache = Hashtbl.create 100 in let enabled = ref true in let find t = try Hashtbl.find cache t with Not_found -> Hashtbl.add cache t t; t in let rec replace tm = match tm with | Var _ | Const _ -> find tm | Comb (s, t) -> (* find @@*) mk_comb (replace s, replace t) | Abs (v, b) -> (* find @@*) mk_abs (replace v, replace b) in let st th = let concl' = replace (concl th) in EQ_MP (REFL concl') th in let get () = Hashtbl.fold (fun _ t ts -> t :: ts) cache [] in let reset () = Hashtbl.clear cache in let enable flag = enabled := flag in (fun th -> if !enabled then st th else th), (fun tm -> if !enabled then replace tm else tm), get, reset, enable;; (* bool variables *) let s_var_bool = standardize_tm `s:bool` and s1_var_bool = standardize_tm `s1:bool` and s2_var_bool = standardize_tm `s2:bool`;; (* num variables *) let n_var_num = standardize_tm `n:num` and m_var_num = standardize_tm `m:num` and t_var_num = standardize_tm `t:num` and p_var_num = standardize_tm `p:num` and q_var_num = standardize_tm `q:num` and k_var_num = standardize_tm `k:num` and e_var_num = standardize_tm `e:num` and e1_var_num = standardize_tm `e1:num` and e2_var_num = standardize_tm `e2:num` and r_var_num = standardize_tm `r:num` and r1_var_num = standardize_tm `r1:num` and r2_var_num = standardize_tm `r2:num` and n1_var_num = standardize_tm `n1:num` and n2_var_num = standardize_tm `n2:num` and m1_var_num = standardize_tm `m1:num` and m2_var_num = standardize_tm `m2:num` and x_var_num = standardize_tm `x:num` and y_var_num = standardize_tm `y:num` and i_var_num = standardize_tm `i:num` and j_var_num = standardize_tm `j:num`;; (* real variables *) let x_var_real = standardize_tm `x : real` and y_var_real = standardize_tm `y : real` and z_var_real = standardize_tm `z : real` and w_var_real = standardize_tm `w : real` and a_var_real = standardize_tm `a : real` and b_var_real = standardize_tm `b : real` and a1_var_real = standardize_tm `a1 : real` and a2_var_real = standardize_tm `a2 : real` and b1_var_real = standardize_tm `b1 : real` and b2_var_real = standardize_tm `b2 : real` and c_var_real = standardize_tm `c : real` and d_var_real = standardize_tm `d : real` and h_var_real = standardize_tm `h : real` and m_var_real = standardize_tm `m : real` and n_var_real = standardize_tm `n : real` and r_var_real = standardize_tm `r : real` and x1_var_real = standardize_tm `x1 : real` and x2_var_real = standardize_tm `x2 : real` and y1_var_real = standardize_tm `y1 : real` and y2_var_real = standardize_tm `y2 : real` and f1_var_real = standardize_tm `f1 : real` and f2_var_real = standardize_tm `f2 : real` and f_var_fun = standardize_tm `f : real->real` and g_var_fun = standardize_tm `g : real->real` and f1_var_fun = standardize_tm `f1 : real->real` and f2_var_fun = standardize_tm `f2 : real->real` and int_var = standardize_tm `int : real#real` and f_bounds_var = standardize_tm `f_bounds : real#real` and df_bounds_var = standardize_tm `df_bounds : real#real` and dd_bounds_var = standardize_tm `dd_bounds : real#real` and x_lo_var = standardize_tm `x_lo : real` and x_hi_var = standardize_tm `x_hi : real` and low_var_real = standardize_tm `low : real` and high_var_real = standardize_tm `high : real` and lo_var_real = standardize_tm `lo : real` and hi_var_real = standardize_tm `hi : real` and dd_var_real = standardize_tm `dd : real` and df_lo_var = standardize_tm `df_lo : real` and df_hi_var = standardize_tm `df_hi : real` and df_var_real = standardize_tm `df : real` and f_lo_var = standardize_tm `f_lo : real` and f_hi_var = standardize_tm `f_hi : real` and w1_var_real = standardize_tm `w1 : real` and w2_var_real = standardize_tm `w2 : real` and t_var_real = standardize_tm `t : real` and g_bounds_var = standardize_tm `g_bounds : real#real` and dg_bounds_var = standardize_tm `dg_bounds : real#real` and bounds_var = standardize_tm `bounds : real#real` and d_bounds_var = standardize_tm `d_bounds : real#real` and x0_var_real = standardize_tm `x0 : real` and z0_var_real = standardize_tm `z0 : real` and w0_var_real = standardize_tm `w0 : real` and error_var = standardize_tm `error : real` and d_bounds_list_var = standardize_tm `d_bounds_list : (real#real)list` and dd_bounds_list_var = standardize_tm `dd_bounds_list : ((real#real)list)list` and df_bounds_list_var = standardize_tm `df_bounds_list : (real#real)list` and dd_list_var = standardize_tm `dd_list : (real#real)list` and t_var_real_list = standardize_tm `t:(real)list` and x_var_real_list = standardize_tm `x:(real)list` and y_var_real_list = standardize_tm `y:(real)list` and z_var_real_list = standardize_tm `z:(real)list` and w_var_real_list = standardize_tm `w:(real)list` and yw_var = standardize_tm `yw : (real#real)list` and xz_var = standardize_tm `xz : (real#real)list` and xz_pair_var = standardize_tm `xz : real#real` and yw_pair_var = standardize_tm `yw : real#real` and list_var_real_pair = standardize_tm `list : (real#real)list`;; (* bool constants *) let t_const = standardize_tm `T` and f_const = standardize_tm `F`;; (* num constants *) let zero_const = standardize_tm `_0` and zero_num = standardize_tm `0`;; (* num operations *) let add_op_num = standardize_tm `(+) : num->num->num` and sub_op_num = standardize_tm `(-) : num->num->num` and mul_op_num = standardize_tm `( * ) : num->num->num` and eq_op_num = standardize_tm `(=) : num->num->bool` and le_op_num = standardize_tm `(<=) : num->num->bool` and lt_op_num = standardize_tm `(<) : num->num->bool` and div_op_num = standardize_tm `(DIV): num->num->num` and pre_op_num = standardize_tm `PRE: num->num` and suc_op_num = standardize_tm `SUC : num->num`;; (* real constants *) let real_empty_list = standardize_tm `[]:(real)list`;; (* real operations *) let add_op_real = standardize_tm `(+) : real->real->real` and mul_op_real = standardize_tm `( * ) : real->real->real` and sub_op_real = standardize_tm `(-) : real->real->real` and div_op_real = standardize_tm `(/) :real->real->real` and inv_op_real = standardize_tm `inv : real->real` and neg_op_real = standardize_tm `(--) : real->real` and eq_op_real = standardize_tm `(=) : real->real->bool` and lt_op_real = standardize_tm `(<) : real->real->bool` and le_op_real = standardize_tm `(<=):real->real->bool` and ge_op_real = standardize_tm `(>=):real->real->bool` and amp_op_real = standardize_tm `(&) : num->real` and pow_op_real = standardize_tm `(pow) : real->num->real`;; (* types *) let real_ty = `:real` and real_list_ty = `:(real)list` and real_pair_ty = `:real#real` and real_pair_list_ty = `:(real#real)list` and num_type = `:num` and nty = `:N`;; (* Simple operations *) let mk_real_list tms = mk_list (tms, real_ty);; let mk_names n prefix = map (fun i -> prefix^(string_of_int i)) (1--n);; let mk_real_vars n prefix = map (C (curry mk_var) real_ty) (mk_names n prefix);; end;;