src/HOL/Library/Sum_of_Squares/sum_of_squares.ML
author wenzelm
Tue, 28 Jul 2015 19:49:54 +0200
changeset 60818 5e11a6e2b044
parent 60801 7664e0916eec
child 60867 86e7560e07d0
permissions -rw-r--r--
more direct access to atomic cterms;
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
41474
60d091240485 renamed Sum_Of_Squares to Sum_of_Squares;
wenzelm
parents: 40721
diff changeset
     1
(*  Title:      HOL/Library/Sum_of_Squares/sum_of_squares.ML
32949
aa6c470a962a eliminated slightly odd get/set operations in favour of Unsynchronized.ref;
wenzelm
parents: 32839
diff changeset
     2
    Author:     Amine Chaieb, University of Cambridge
aa6c470a962a eliminated slightly odd get/set operations in favour of Unsynchronized.ref;
wenzelm
parents: 32839
diff changeset
     3
    Author:     Philipp Meyer, TU Muenchen
32268
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
     4
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
     5
A tactic for proving nonlinear inequalities.
32268
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
     6
*)
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
     7
32949
aa6c470a962a eliminated slightly odd get/set operations in favour of Unsynchronized.ref;
wenzelm
parents: 32839
diff changeset
     8
signature SUM_OF_SQUARES =
32268
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
     9
sig
32949
aa6c470a962a eliminated slightly odd get/set operations in favour of Unsynchronized.ref;
wenzelm
parents: 32839
diff changeset
    10
  datatype proof_method = Certificate of RealArith.pss_tree | Prover of string -> string
aa6c470a962a eliminated slightly odd get/set operations in favour of Unsynchronized.ref;
wenzelm
parents: 32839
diff changeset
    11
  val sos_tac: (RealArith.pss_tree -> unit) -> proof_method -> Proof.context -> int -> tactic
38805
b09d8603f865 Sum_Of_Squares: proper configuration options;
wenzelm
parents: 38795
diff changeset
    12
  val trace: bool Config.T
58631
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
    13
  val debug: bool Config.T
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
    14
  val trace_message: Proof.context -> (unit -> string) -> unit
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
    15
  val debug_message: Proof.context -> (unit -> string) -> unit
32332
bc5cec7b2be6 misc changes to SOS by Philipp Meyer:
wenzelm
parents: 32268
diff changeset
    16
  exception Failure of string;
32268
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
    17
end
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
    18
41474
60d091240485 renamed Sum_Of_Squares to Sum_of_Squares;
wenzelm
parents: 40721
diff changeset
    19
structure Sum_of_Squares: SUM_OF_SQUARES =
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    20
struct
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    21
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    22
val rat_0 = Rat.zero;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    23
val rat_1 = Rat.one;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    24
val rat_2 = Rat.two;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    25
val rat_10 = Rat.rat_of_int 10;
33029
2fefe039edf1 uniform use of Integer.min/max;
wenzelm
parents: 33002
diff changeset
    26
val max = Integer.max;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    27
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    28
val denominator_rat = Rat.quotient_of_rat #> snd #> Rat.rat_of_int;
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    29
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
    30
fun int_of_rat a =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    31
  (case Rat.quotient_of_rat a of
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    32
    (i, 1) => i
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    33
  | _ => error "int_of_rat: not an int");
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    34
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    35
fun lcm_rat x y =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    36
  Rat.rat_of_int (Integer.lcm (int_of_rat x) (int_of_rat y));
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    37
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
    38
fun rat_pow r i =
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
    39
 let fun pow r i =
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
    40
   if i = 0 then rat_1 else
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    41
   let val d = pow r (i div 2)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    42
   in d */ d */ (if i mod 2 = 0 then rat_1 else r)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    43
   end
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    44
 in if i < 0 then pow (Rat.inv r) (~ i) else pow r i end;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    45
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
    46
fun round_rat r =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    47
  let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    48
    val (a,b) = Rat.quotient_of_rat (Rat.abs r)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    49
    val d = a div b
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    50
    val s = if r </ rat_0 then (Rat.neg o Rat.rat_of_int) else Rat.rat_of_int
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    51
    val x2 = 2 * (a - (b * d))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    52
  in s (if x2 >= b then d + 1 else d) end
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    53
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    54
val abs_rat = Rat.abs;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    55
val pow2 = rat_pow rat_2;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    56
val pow10 = rat_pow rat_10;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    57
58631
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
    58
42616
92715b528e78 added Attrib.setup_config_XXX conveniences, with implicit setup of the background theory;
wenzelm
parents: 41490
diff changeset
    59
val trace = Attrib.setup_config_bool @{binding sos_trace} (K false);
58631
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
    60
val debug = Attrib.setup_config_bool @{binding sos_debug} (K false);
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
    61
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
    62
fun trace_message ctxt msg =
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
    63
  if Config.get ctxt trace orelse Config.get ctxt debug then tracing (msg ()) else ();
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
    64
fun debug_message ctxt msg = if Config.get ctxt debug then tracing (msg ()) else ();
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    65
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    66
exception Sanity;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    67
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    68
exception Unsolvable;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    69
32332
bc5cec7b2be6 misc changes to SOS by Philipp Meyer:
wenzelm
parents: 32268
diff changeset
    70
exception Failure of string;
bc5cec7b2be6 misc changes to SOS by Philipp Meyer:
wenzelm
parents: 32268
diff changeset
    71
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents: 32332
diff changeset
    72
datatype proof_method =
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents: 32332
diff changeset
    73
    Certificate of RealArith.pss_tree
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents: 32332
diff changeset
    74
  | Prover of (string -> string)
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents: 32332
diff changeset
    75
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    76
(* Turn a rational into a decimal string with d sig digits.                  *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    77
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    78
local
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    79
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    80
fun normalize y =
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    81
  if abs_rat y </ (rat_1 // rat_10) then normalize (rat_10 */ y) - 1
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    82
  else if abs_rat y >=/ rat_1 then normalize (y // rat_10) + 1
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
    83
  else 0
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    84
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    85
in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    86
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
    87
fun decimalize d x =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    88
  if x =/ rat_0 then "0.0"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    89
  else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    90
    let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    91
      val y = Rat.abs x
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    92
      val e = normalize y
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    93
      val z = pow10(~ e) */ y +/ rat_1
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    94
      val k = int_of_rat (round_rat(pow10 d */ z))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    95
    in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    96
      (if x </ rat_0 then "-0." else "0.") ^
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    97
      implode (tl (raw_explode(string_of_int k))) ^
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    98
      (if e = 0 then "" else "e" ^ string_of_int e)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
    99
    end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   100
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   101
end;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   102
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   103
(* Iterations over numbers, and lists indexed by numbers.                    *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   104
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   105
fun itern k l f a =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   106
  (case l of
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   107
    [] => a
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   108
  | h::t => itern (k + 1) t f (f h k a));
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   109
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   110
fun iter (m,n) f a =
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   111
  if n < m then a
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   112
  else iter (m + 1, n) f (f m a);
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   113
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   114
(* The main types.                                                           *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   115
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   116
type vector = int * Rat.rat FuncUtil.Intfunc.table;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   117
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   118
type matrix = (int * int) * Rat.rat FuncUtil.Intpairfunc.table;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   119
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   120
fun iszero (_, r) = r =/ rat_0;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   121
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   122
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   123
(* Vectors. Conventionally indexed 1..n.                                     *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   124
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   125
fun vector_0 n = (n, FuncUtil.Intfunc.empty): vector;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   126
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   127
fun dim (v: vector) = fst v;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   128
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   129
fun vector_cmul c (v: vector) =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   130
  let val n = dim v in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   131
    if c =/ rat_0 then vector_0 n
39027
e4262f9e6a4e Table.map replaces Table.map'
haftmann
parents: 38805
diff changeset
   132
    else (n,FuncUtil.Intfunc.map (fn _ => fn x => c */ x) (snd v))
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   133
  end;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   134
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   135
fun vector_of_list l =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   136
  let val n = length l in
58635
010b610eb55d eliminated some exotic combinators;
wenzelm
parents: 58631
diff changeset
   137
    (n, fold_rev FuncUtil.Intfunc.update (1 upto n ~~ l) FuncUtil.Intfunc.empty): vector
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   138
  end;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   139
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   140
(* Matrices; again rows and columns indexed from 1.                          *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   141
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   142
fun dimensions (m: matrix) = fst m;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   143
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   144
fun row k (m: matrix) : vector =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   145
  let val (_, j) = dimensions m in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   146
    (j,
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   147
      FuncUtil.Intpairfunc.fold (fn ((i, j), c) => fn a =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   148
        if i = k then FuncUtil.Intfunc.update (j, c) a else a) (snd m) FuncUtil.Intfunc.empty)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   149
  end;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   150
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   151
(* Monomials.                                                                *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   152
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   153
fun monomial_eval assig m =
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   154
  FuncUtil.Ctermfunc.fold (fn (x, k) => fn a => a */ rat_pow (FuncUtil.Ctermfunc.apply assig x) k)
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   155
    m rat_1;
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   156
32829
671eb46eb0a3 tuned FuncFun and FuncUtil structure in positivstellensatz.ML
Philipp Meyer
parents: 32828
diff changeset
   157
val monomial_1 = FuncUtil.Ctermfunc.empty;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   158
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   159
fun monomial_var x = FuncUtil.Ctermfunc.onefunc (x, 1);
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   160
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   161
val monomial_mul =
33002
f3f02f36a3e2 uniform use of Integer.add/mult/sum/prod;
wenzelm
parents: 32949
diff changeset
   162
  FuncUtil.Ctermfunc.combine Integer.add (K false);
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   163
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   164
fun monomial_multidegree m =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   165
  FuncUtil.Ctermfunc.fold (fn (_, k) => fn a => k + a) m 0;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   166
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   167
fun monomial_variables m = FuncUtil.Ctermfunc.dom m;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   168
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   169
(* Polynomials.                                                              *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   170
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   171
fun eval assig p =
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   172
  FuncUtil.Monomialfunc.fold (fn (m, c) => fn a => a +/ c */ monomial_eval assig m) p rat_0;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   173
32829
671eb46eb0a3 tuned FuncFun and FuncUtil structure in positivstellensatz.ML
Philipp Meyer
parents: 32828
diff changeset
   174
val poly_0 = FuncUtil.Monomialfunc.empty;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   175
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   176
fun poly_isconst p =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   177
  FuncUtil.Monomialfunc.fold (fn (m, _) => fn a => FuncUtil.Ctermfunc.is_empty m andalso a)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   178
    p true;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   179
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   180
fun poly_var x = FuncUtil.Monomialfunc.onefunc (monomial_var x, rat_1);
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   181
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   182
fun poly_const c =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   183
  if c =/ rat_0 then poly_0 else FuncUtil.Monomialfunc.onefunc (monomial_1, c);
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   184
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   185
fun poly_cmul c p =
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   186
  if c =/ rat_0 then poly_0
39027
e4262f9e6a4e Table.map replaces Table.map'
haftmann
parents: 38805
diff changeset
   187
  else FuncUtil.Monomialfunc.map (fn _ => fn x => c */ x) p;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   188
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   189
fun poly_neg p = FuncUtil.Monomialfunc.map (K Rat.neg) p;
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   190
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   191
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   192
fun poly_add p1 p2 =
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   193
  FuncUtil.Monomialfunc.combine (curry op +/) (fn x => x =/ rat_0) p1 p2;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   194
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   195
fun poly_sub p1 p2 = poly_add p1 (poly_neg p2);
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   196
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   197
fun poly_cmmul (c,m) p =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   198
  if c =/ rat_0 then poly_0
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   199
  else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   200
    if FuncUtil.Ctermfunc.is_empty m
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   201
    then FuncUtil.Monomialfunc.map (fn _ => fn d => c */ d) p
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   202
    else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   203
      FuncUtil.Monomialfunc.fold (fn (m', d) => fn a =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   204
          (FuncUtil.Monomialfunc.update (monomial_mul m m', c */ d) a)) p poly_0;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   205
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   206
fun poly_mul p1 p2 =
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   207
  FuncUtil.Monomialfunc.fold (fn (m, c) => fn a => poly_add (poly_cmmul (c,m) p2) a) p1 poly_0;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   208
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   209
fun poly_square p = poly_mul p p;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   210
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   211
fun poly_pow p k =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   212
  if k = 0 then poly_const rat_1
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   213
  else if k = 1 then p
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   214
  else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   215
    let val q = poly_square(poly_pow p (k div 2))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   216
    in if k mod 2 = 1 then poly_mul p q else q end;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   217
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   218
fun multidegree p =
44453
082edd97ffe1 comment out dead code to avoid compiler warnings
huffman
parents: 42616
diff changeset
   219
  FuncUtil.Monomialfunc.fold (fn (m, _) => fn a => max (monomial_multidegree m) a) p 0;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   220
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   221
fun poly_variables p =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   222
  sort FuncUtil.cterm_ord
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   223
    (FuncUtil.Monomialfunc.fold_rev
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   224
      (fn (m, _) => union (is_equal o FuncUtil.cterm_ord) (monomial_variables m)) p []);
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   225
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   226
(* Conversion from HOL term.                                                 *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   227
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   228
local
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   229
  val neg_tm = @{cterm "uminus :: real => _"}
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   230
  val add_tm = @{cterm "op + :: real => _"}
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   231
  val sub_tm = @{cterm "op - :: real => _"}
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   232
  val mul_tm = @{cterm "op * :: real => _"}
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   233
  val inv_tm = @{cterm "inverse :: real => _"}
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   234
  val div_tm = @{cterm "op / :: real => _"}
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   235
  val pow_tm = @{cterm "op ^ :: real => _"}
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   236
  val zero_tm = @{cterm "0:: real"}
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
   237
  val is_numeral = can (HOLogic.dest_number o Thm.term_of)
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   238
  fun poly_of_term tm =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   239
    if tm aconvc zero_tm then poly_0
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   240
    else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   241
      if RealArith.is_ratconst tm
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   242
      then poly_const(RealArith.dest_ratconst tm)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   243
      else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   244
       (let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   245
          val (lop, r) = Thm.dest_comb tm
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   246
        in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   247
          if lop aconvc neg_tm then poly_neg(poly_of_term r)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   248
          else if lop aconvc inv_tm then
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   249
            let val p = poly_of_term r in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   250
              if poly_isconst p
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   251
              then poly_const(Rat.inv (eval FuncUtil.Ctermfunc.empty p))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   252
              else error "poly_of_term: inverse of non-constant polyomial"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   253
            end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   254
          else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   255
           (let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   256
              val (opr,l) = Thm.dest_comb lop
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   257
            in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   258
              if opr aconvc pow_tm andalso is_numeral r
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
   259
              then poly_pow (poly_of_term l) ((snd o HOLogic.dest_number o Thm.term_of) r)
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   260
              else if opr aconvc add_tm
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   261
              then poly_add (poly_of_term l) (poly_of_term r)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   262
              else if opr aconvc sub_tm
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   263
              then poly_sub (poly_of_term l) (poly_of_term r)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   264
              else if opr aconvc mul_tm
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   265
              then poly_mul (poly_of_term l) (poly_of_term r)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   266
              else if opr aconvc div_tm
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   267
              then
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   268
                let
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   269
                  val p = poly_of_term l
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   270
                  val q = poly_of_term r
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   271
                in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   272
                  if poly_isconst q
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   273
                  then poly_cmul (Rat.inv (eval FuncUtil.Ctermfunc.empty q)) p
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   274
                  else error "poly_of_term: division by non-constant polynomial"
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   275
                end
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   276
              else poly_var tm
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   277
            end handle CTERM ("dest_comb",_) => poly_var tm)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   278
        end handle CTERM ("dest_comb",_) => poly_var tm)
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   279
in
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   280
  val poly_of_term = fn tm =>
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
   281
    if type_of (Thm.term_of tm) = @{typ real}
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   282
    then poly_of_term tm
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   283
    else error "poly_of_term: term does not have real type"
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   284
end;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   285
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   286
(* String of vector (just a list of space-separated numbers).                *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   287
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   288
fun sdpa_of_vector (v: vector) =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   289
  let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   290
    val n = dim v
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   291
    val strs =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   292
      map (decimalize 20 o (fn i => FuncUtil.Intfunc.tryapplyd (snd v) i rat_0)) (1 upto n)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   293
  in space_implode " " strs ^ "\n" end;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   294
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   295
fun triple_int_ord ((a, b, c), (a', b', c')) =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   296
  prod_ord int_ord (prod_ord int_ord int_ord) ((a, (b, c)), (a', (b', c')));
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   297
structure Inttriplefunc = FuncFun(type key = int * int * int val ord = triple_int_ord);
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   298
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   299
fun index_char str chr pos =
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   300
  if pos >= String.size str then ~1
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   301
  else if String.sub(str,pos) = chr then pos
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   302
  else index_char str chr (pos + 1);
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   303
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   304
fun rat_of_quotient (a,b) =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   305
  if b = 0 then rat_0 else Rat.rat_of_quotient (a, b);
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   306
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   307
fun rat_of_string s =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   308
  let val n = index_char s #"/" 0 in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   309
    if n = ~1 then s |> Int.fromString |> the |> Rat.rat_of_int
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   310
    else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   311
      let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   312
        val SOME numer = Int.fromString(String.substring(s,0,n))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   313
        val SOME den = Int.fromString (String.substring(s,n+1,String.size s - n - 1))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   314
      in rat_of_quotient(numer, den) end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   315
  end;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   316
53975
22ee3fb9d596 backout c6297fa1031a -- strange parsers are required to make this work;
wenzelm
parents: 53972
diff changeset
   317
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   318
fun isnum x = member (op =) ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"] x;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   319
53975
22ee3fb9d596 backout c6297fa1031a -- strange parsers are required to make this work;
wenzelm
parents: 53972
diff changeset
   320
(* More parser basics. *)
22ee3fb9d596 backout c6297fa1031a -- strange parsers are required to make this work;
wenzelm
parents: 53972
diff changeset
   321
(* FIXME improper use of parser combinators ahead *)
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   322
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   323
val numeral = Scan.one isnum
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   324
val decimalint = Scan.repeat1 numeral >> (rat_of_string o implode)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   325
val decimalfrac = Scan.repeat1 numeral
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   326
  >> (fn s => rat_of_string(implode s) // pow10 (length s))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   327
val decimalsig =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   328
  decimalint -- Scan.option (Scan.$$ "." |-- decimalfrac)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   329
  >> (fn (h,NONE) => h | (h,SOME x) => h +/ x)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   330
fun signed prs =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   331
     $$ "-" |-- prs >> Rat.neg
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   332
  || $$ "+" |-- prs
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   333
  || prs;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   334
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   335
fun emptyin def xs = if null xs then (def, xs) else Scan.fail xs
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   336
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   337
val exponent = ($$ "e" || $$ "E") |-- signed decimalint;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   338
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   339
val decimal = signed decimalsig -- (emptyin rat_0|| exponent)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   340
  >> (fn (h, x) => h */ pow10 (int_of_rat x));
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   341
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   342
fun mkparser p s =
53975
22ee3fb9d596 backout c6297fa1031a -- strange parsers are required to make this work;
wenzelm
parents: 53972
diff changeset
   343
  let val (x,rst) = p (raw_explode s)
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   344
  in if null rst then x else error "mkparser: unparsed input" end;
53975
22ee3fb9d596 backout c6297fa1031a -- strange parsers are required to make this work;
wenzelm
parents: 53972
diff changeset
   345
32332
bc5cec7b2be6 misc changes to SOS by Philipp Meyer:
wenzelm
parents: 32268
diff changeset
   346
(* Parse back csdp output.                                                      *)
53975
22ee3fb9d596 backout c6297fa1031a -- strange parsers are required to make this work;
wenzelm
parents: 53972
diff changeset
   347
(* FIXME improper use of parser combinators ahead *)
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   348
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   349
fun ignore _ = ((),[])
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   350
fun csdpoutput inp =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   351
  ((decimal -- Scan.repeat (Scan.$$ " " |-- Scan.option decimal) >>
33067
a70d5baa53ee use plain Scan.repeat (NB: Scan.bulk is for cascading sources -- mostly interna use);
wenzelm
parents: 33042
diff changeset
   352
    (fn (h,to) => map_filter I ((SOME h)::to))) --| ignore >> vector_of_list) inp
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   353
val parse_csdpoutput = mkparser csdpoutput
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   354
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   355
(* Try some apparently sensible scaling first. Note that this is purely to   *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   356
(* get a cleaner translation to floating-point, and doesn't affect any of    *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   357
(* the results, in principle. In practice it seems a lot better when there   *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   358
(* are extreme numbers in the original problem.                              *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   359
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   360
(* Version for (int*int*int) keys *)
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   361
local
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   362
  fun max_rat x y = if x </ y then y else x
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   363
  fun common_denominator fld amat acc =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   364
    fld (fn (_,c) => fn a => lcm_rat (denominator_rat c) a) amat acc
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   365
  fun maximal_element fld amat acc =
44453
082edd97ffe1 comment out dead code to avoid compiler warnings
huffman
parents: 42616
diff changeset
   366
    fld (fn (_,c) => fn maxa => max_rat maxa (abs_rat c)) amat acc
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   367
  fun float_of_rat x =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   368
    let val (a,b) = Rat.quotient_of_rat x
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   369
    in Real.fromInt a / Real.fromInt b end;
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   370
  fun int_of_float x = (trunc x handle Overflow => 0 | Domain => 0)
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   371
in
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   372
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   373
fun tri_scale_then solver (obj:vector) mats =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   374
  let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   375
    val cd1 = fold_rev (common_denominator Inttriplefunc.fold) mats (rat_1)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   376
    val cd2 = common_denominator FuncUtil.Intfunc.fold (snd obj)  (rat_1)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   377
    val mats' = map (Inttriplefunc.map (fn _ => fn x => cd1 */ x)) mats
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   378
    val obj' = vector_cmul cd2 obj
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   379
    val max1 = fold_rev (maximal_element Inttriplefunc.fold) mats' (rat_0)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   380
    val max2 = maximal_element FuncUtil.Intfunc.fold (snd obj') (rat_0)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   381
    val scal1 = pow2 (20 - int_of_float(Math.ln (float_of_rat max1) / Math.ln 2.0))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   382
    val scal2 = pow2 (20 - int_of_float(Math.ln (float_of_rat max2) / Math.ln 2.0))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   383
    val mats'' = map (Inttriplefunc.map (fn _ => fn x => x */ scal1)) mats'
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   384
    val obj'' = vector_cmul scal2 obj'
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   385
  in solver obj'' mats'' end
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   386
end;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   387
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   388
(* Round a vector to "nice" rationals.                                       *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   389
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   390
fun nice_rational n x = round_rat (n */ x) // n;
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   391
fun nice_vector n ((d,v) : vector) =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   392
  (d, FuncUtil.Intfunc.fold (fn (i,c) => fn a =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   393
      let val y = nice_rational n c in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   394
        if c =/ rat_0 then a
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   395
        else FuncUtil.Intfunc.update (i,y) a
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   396
      end) v FuncUtil.Intfunc.empty): vector
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   397
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   398
fun dest_ord f x = is_equal (f x);
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   399
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   400
(* Stuff for "equations" ((int*int*int)->num functions).                         *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   401
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   402
fun tri_equation_cmul c eq =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   403
  if c =/ rat_0 then Inttriplefunc.empty
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   404
  else Inttriplefunc.map (fn _ => fn d => c */ d) eq;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   405
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   406
fun tri_equation_add eq1 eq2 =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   407
  Inttriplefunc.combine (curry op +/) (fn x => x =/ rat_0) eq1 eq2;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   408
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   409
fun tri_equation_eval assig eq =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   410
  let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   411
    fun value v = Inttriplefunc.apply assig v
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   412
  in Inttriplefunc.fold (fn (v, c) => fn a => a +/ value v */ c) eq rat_0 end;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   413
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   414
(* Eliminate all variables, in an essentially arbitrary order.               *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   415
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   416
fun tri_eliminate_all_equations one =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   417
  let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   418
    fun choose_variable eq =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   419
      let val (v,_) = Inttriplefunc.choose eq
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   420
      in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   421
        if is_equal (triple_int_ord(v,one)) then
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   422
          let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   423
            val eq' = Inttriplefunc.delete_safe v eq
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   424
          in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   425
            if Inttriplefunc.is_empty eq' then error "choose_variable"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   426
            else fst (Inttriplefunc.choose eq')
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   427
          end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   428
        else v
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   429
      end
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   430
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   431
    fun eliminate dun eqs =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   432
      (case eqs of
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   433
        [] => dun
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   434
      | eq :: oeqs =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   435
          if Inttriplefunc.is_empty eq then eliminate dun oeqs
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   436
          else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   437
            let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   438
              val v = choose_variable eq
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   439
              val a = Inttriplefunc.apply eq v
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   440
              val eq' =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   441
                tri_equation_cmul ((Rat.rat_of_int ~1) // a) (Inttriplefunc.delete_safe v eq)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   442
              fun elim e =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   443
                let val b = Inttriplefunc.tryapplyd e v rat_0 in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   444
                  if b =/ rat_0 then e
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   445
                  else tri_equation_add e (tri_equation_cmul (Rat.neg b // a) eq)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   446
                end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   447
            in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   448
              eliminate (Inttriplefunc.update(v, eq') (Inttriplefunc.map (K elim) dun))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   449
                (map elim oeqs)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   450
            end)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   451
  in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   452
    fn eqs =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   453
      let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   454
        val assig = eliminate Inttriplefunc.empty eqs
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   455
        val vs = Inttriplefunc.fold (fn (_, f) => fn a =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   456
          remove (dest_ord triple_int_ord) one (Inttriplefunc.dom f) @ a) assig []
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   457
      in (distinct (dest_ord triple_int_ord) vs,assig) end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   458
  end;
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   459
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   460
(* Multiply equation-parametrized poly by regular poly and add accumulator.  *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   461
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   462
fun tri_epoly_pmul p q acc =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   463
  FuncUtil.Monomialfunc.fold (fn (m1, c) => fn a =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   464
    FuncUtil.Monomialfunc.fold (fn (m2, e) => fn b =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   465
      let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   466
        val m =  monomial_mul m1 m2
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   467
        val es = FuncUtil.Monomialfunc.tryapplyd b m Inttriplefunc.empty
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   468
      in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   469
        FuncUtil.Monomialfunc.update (m,tri_equation_add (tri_equation_cmul c e) es) b
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   470
      end) q a) p acc;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   471
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   472
(* Hence produce the "relevant" monomials: those whose squares lie in the    *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   473
(* Newton polytope of the monomials in the input. (This is enough according  *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   474
(* to Reznik: "Extremal PSD forms with few terms", Duke Math. Journal,       *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   475
(* vol 45, pp. 363--374, 1978.                                               *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   476
(*                                                                           *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   477
(* These are ordered in sort of decreasing degree. In particular the         *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   478
(* constant monomial is last; this gives an order in diagonalization of the  *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   479
(* quadratic form that will tend to display constants.                       *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   480
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   481
(* Diagonalize (Cholesky/LDU) the matrix corresponding to a quadratic form.  *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   482
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   483
local
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   484
  fun diagonalize n i m =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   485
    if FuncUtil.Intpairfunc.is_empty (snd m) then []
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   486
    else
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   487
      let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   488
        val a11 = FuncUtil.Intpairfunc.tryapplyd (snd m) (i,i) rat_0
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   489
      in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   490
        if a11 </ rat_0 then raise Failure "diagonalize: not PSD"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   491
        else if a11 =/ rat_0 then
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   492
          if FuncUtil.Intfunc.is_empty (snd (row i m))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   493
          then diagonalize n (i + 1) m
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   494
          else raise Failure "diagonalize: not PSD ___ "
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   495
        else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   496
          let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   497
            val v = row i m
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   498
            val v' =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   499
              (fst v, FuncUtil.Intfunc.fold (fn (i, c) => fn a =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   500
                let val y = c // a11
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   501
                in if y = rat_0 then a else FuncUtil.Intfunc.update (i,y) a
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   502
                end) (snd v) FuncUtil.Intfunc.empty)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   503
            fun upt0 x y a =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   504
              if y = rat_0 then a
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   505
              else FuncUtil.Intpairfunc.update (x,y) a
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   506
            val m' =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   507
              ((n, n),
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   508
                iter (i + 1, n) (fn j =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   509
                  iter (i + 1, n) (fn k =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   510
                    (upt0 (j, k)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   511
                      (FuncUtil.Intpairfunc.tryapplyd (snd m) (j, k) rat_0 -/
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   512
                        FuncUtil.Intfunc.tryapplyd (snd v) j rat_0 */
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   513
                        FuncUtil.Intfunc.tryapplyd (snd v') k rat_0))))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   514
                    FuncUtil.Intpairfunc.empty)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   515
          in (a11, v') :: diagonalize n (i + 1) m' end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   516
      end
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   517
in
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   518
  fun diag m =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   519
    let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   520
      val nn = dimensions m
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   521
      val n = fst nn
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   522
    in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   523
      if snd nn <> n then error "diagonalize: non-square matrix"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   524
      else diagonalize n 1 m
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   525
    end
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   526
end;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   527
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   528
(* Enumeration of monomials with given multidegree bound.                    *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   529
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   530
fun enumerate_monomials d vars =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   531
  if d < 0 then []
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   532
  else if d = 0 then [FuncUtil.Ctermfunc.empty]
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   533
  else if null vars then [monomial_1]
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   534
  else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   535
    let val alts =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   536
      map_range (fn k =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   537
        let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   538
          val oths = enumerate_monomials (d - k) (tl vars)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   539
        in map (fn ks => if k = 0 then ks else FuncUtil.Ctermfunc.update (hd vars, k) ks) oths end)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   540
        (d + 1)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   541
  in flat alts end;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   542
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   543
(* Enumerate products of distinct input polys with degree <= d.              *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   544
(* We ignore any constant input polynomials.                                 *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   545
(* Give the output polynomial and a record of how it was derived.            *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   546
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   547
fun enumerate_products d pols =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   548
  if d = 0 then [(poly_const rat_1,RealArith.Rational_lt rat_1)]
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   549
  else if d < 0 then []
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   550
  else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   551
    (case pols of
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   552
      [] => [(poly_const rat_1, RealArith.Rational_lt rat_1)]
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   553
    | (p, b) :: ps =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   554
        let val e = multidegree p in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   555
          if e = 0 then enumerate_products d ps
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   556
          else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   557
            enumerate_products d ps @
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   558
            map (fn (q, c) => (poly_mul p q, RealArith.Product (b, c)))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   559
              (enumerate_products (d - e) ps)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   560
        end)
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   561
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   562
(* Convert regular polynomial. Note that we treat (0,0,0) as -1.             *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   563
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   564
fun epoly_of_poly p =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   565
  FuncUtil.Monomialfunc.fold (fn (m, c) => fn a =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   566
      FuncUtil.Monomialfunc.update (m, Inttriplefunc.onefunc ((0, 0, 0), Rat.neg c)) a)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   567
    p FuncUtil.Monomialfunc.empty;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   568
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   569
(* String for block diagonal matrix numbered k.                              *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   570
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   571
fun sdpa_of_blockdiagonal k m =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   572
  let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   573
    val pfx = string_of_int k ^" "
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   574
    val ents =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   575
      Inttriplefunc.fold
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   576
        (fn ((b, i, j), c) => fn a => if i > j then a else ((b, i, j), c) :: a)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   577
        m []
59058
a78612c67ec0 renamed "pairself" to "apply2", in accordance to @{apply 2};
wenzelm
parents: 58635
diff changeset
   578
    val entss = sort (triple_int_ord o apply2 fst) ents
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   579
  in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   580
    fold_rev (fn ((b,i,j),c) => fn a =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   581
      pfx ^ string_of_int b ^ " " ^ string_of_int i ^ " " ^ string_of_int j ^
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   582
      " " ^ decimalize 20 c ^ "\n" ^ a) entss ""
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   583
  end;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   584
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   585
(* SDPA for problem using block diagonal (i.e. multiple SDPs)                *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   586
32268
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
   587
fun sdpa_of_blockproblem nblocks blocksizes obj mats =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   588
  let val m = length mats - 1
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   589
  in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   590
    string_of_int m ^ "\n" ^
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   591
    string_of_int nblocks ^ "\n" ^
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   592
    (space_implode " " (map string_of_int blocksizes)) ^
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   593
    "\n" ^
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   594
    sdpa_of_vector obj ^
58635
010b610eb55d eliminated some exotic combinators;
wenzelm
parents: 58631
diff changeset
   595
    fold_rev (fn (k, m) => fn a => sdpa_of_blockdiagonal (k - 1) m ^ a)
010b610eb55d eliminated some exotic combinators;
wenzelm
parents: 58631
diff changeset
   596
      (1 upto length mats ~~ mats) ""
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   597
  end;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   598
32268
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
   599
(* Run prover on a problem in block diagonal form.                       *)
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
   600
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   601
fun run_blockproblem prover nblocks blocksizes obj mats =
32268
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
   602
  parse_csdpoutput (prover (sdpa_of_blockproblem nblocks blocksizes obj mats))
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
   603
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   604
(* 3D versions of matrix operations to consider blocks separately.           *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   605
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   606
val bmatrix_add = Inttriplefunc.combine (curry op +/) (fn x => x =/ rat_0);
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   607
fun bmatrix_cmul c bm =
32829
671eb46eb0a3 tuned FuncFun and FuncUtil structure in positivstellensatz.ML
Philipp Meyer
parents: 32828
diff changeset
   608
  if c =/ rat_0 then Inttriplefunc.empty
39027
e4262f9e6a4e Table.map replaces Table.map'
haftmann
parents: 38805
diff changeset
   609
  else Inttriplefunc.map (fn _ => fn x => c */ x) bm;
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   610
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   611
val bmatrix_neg = bmatrix_cmul (Rat.rat_of_int ~1);
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   612
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   613
(* Smash a block matrix into components.                                     *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   614
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   615
fun blocks blocksizes bm =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   616
  map (fn (bs, b0) =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   617
    let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   618
      val m =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   619
        Inttriplefunc.fold
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   620
          (fn ((b, i, j), c) => fn a =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   621
            if b = b0 then FuncUtil.Intpairfunc.update ((i, j), c) a else a)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   622
        bm FuncUtil.Intpairfunc.empty
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   623
      val _ = FuncUtil.Intpairfunc.fold (fn ((i, j), _) => fn a => max a (max i j)) m 0
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   624
    in (((bs, bs), m): matrix) end)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   625
  (blocksizes ~~ (1 upto length blocksizes));
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   626
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   627
(* FIXME : Get rid of this !!!*)
32268
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
   628
local
44453
082edd97ffe1 comment out dead code to avoid compiler warnings
huffman
parents: 42616
diff changeset
   629
  fun tryfind_with msg _ [] = raise Failure msg
082edd97ffe1 comment out dead code to avoid compiler warnings
huffman
parents: 42616
diff changeset
   630
    | tryfind_with _ f (x::xs) = (f x handle Failure s => tryfind_with s f xs);
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   631
in
32268
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
   632
  fun tryfind f = tryfind_with "tryfind" f
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
   633
end
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
   634
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   635
(* Positiv- and Nullstellensatz. Flag "linf" forces a linear representation. *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   636
38805
b09d8603f865 Sum_Of_Squares: proper configuration options;
wenzelm
parents: 38795
diff changeset
   637
fun real_positivnullstellensatz_general ctxt prover linf d eqs leqs pol =
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   638
  let
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   639
    val vars =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   640
      fold_rev (union (op aconvc) o poly_variables)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   641
        (pol :: eqs @ map fst leqs) []
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   642
    val monoid =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   643
      if linf then
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   644
        (poly_const rat_1,RealArith.Rational_lt rat_1)::
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   645
        (filter (fn (p,_) => multidegree p <= d) leqs)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   646
      else enumerate_products d leqs
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   647
    val nblocks = length monoid
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   648
    fun mk_idmultiplier k p =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   649
      let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   650
        val e = d - multidegree p
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   651
        val mons = enumerate_monomials e vars
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   652
        val nons = mons ~~ (1 upto length mons)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   653
      in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   654
        (mons,
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   655
          fold_rev (fn (m, n) =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   656
            FuncUtil.Monomialfunc.update (m, Inttriplefunc.onefunc ((~k, ~n, n), rat_1)))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   657
          nons FuncUtil.Monomialfunc.empty)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   658
      end
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   659
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   660
    fun mk_sqmultiplier k (p,_) =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   661
      let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   662
        val e = (d - multidegree p) div 2
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   663
        val mons = enumerate_monomials e vars
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   664
        val nons = mons ~~ (1 upto length mons)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   665
      in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   666
        (mons,
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   667
          fold_rev (fn (m1, n1) =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   668
            fold_rev (fn (m2, n2) => fn a =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   669
              let val m = monomial_mul m1 m2 in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   670
                if n1 > n2 then a
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   671
                else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   672
                  let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   673
                    val c = if n1 = n2 then rat_1 else rat_2
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   674
                    val e = FuncUtil.Monomialfunc.tryapplyd a m Inttriplefunc.empty
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   675
                  in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   676
                    FuncUtil.Monomialfunc.update
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   677
                      (m, tri_equation_add (Inttriplefunc.onefunc ((k, n1, n2), c)) e) a
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   678
                  end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   679
              end) nons) nons FuncUtil.Monomialfunc.empty)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   680
      end
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   681
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   682
    val (sqmonlist,sqs) = split_list (map2 mk_sqmultiplier (1 upto length monoid) monoid)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   683
    val (_(*idmonlist*),ids) =  split_list (map2 mk_idmultiplier (1 upto length eqs) eqs)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   684
    val blocksizes = map length sqmonlist
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   685
    val bigsum =
58635
010b610eb55d eliminated some exotic combinators;
wenzelm
parents: 58631
diff changeset
   686
      fold_rev (fn (p, q) => fn a => tri_epoly_pmul p q a) (eqs ~~ ids)
010b610eb55d eliminated some exotic combinators;
wenzelm
parents: 58631
diff changeset
   687
        (fold_rev (fn ((p, _), s) => fn a => tri_epoly_pmul p s a) (monoid ~~ sqs)
010b610eb55d eliminated some exotic combinators;
wenzelm
parents: 58631
diff changeset
   688
          (epoly_of_poly (poly_neg pol)))
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   689
    val eqns = FuncUtil.Monomialfunc.fold (fn (_, e) => fn a => e :: a) bigsum []
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   690
    val (pvs, assig) = tri_eliminate_all_equations (0, 0, 0) eqns
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   691
    val qvars = (0, 0, 0) :: pvs
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   692
    val allassig =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   693
      fold_rev (fn v => Inttriplefunc.update (v, (Inttriplefunc.onefunc (v, rat_1)))) pvs assig
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   694
    fun mk_matrix v =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   695
      Inttriplefunc.fold (fn ((b, i, j), ass) => fn m =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   696
          if b < 0 then m
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   697
          else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   698
            let val c = Inttriplefunc.tryapplyd ass v rat_0 in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   699
              if c = rat_0 then m
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   700
              else Inttriplefunc.update ((b, j, i), c) (Inttriplefunc.update ((b, i, j), c) m)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   701
            end)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   702
        allassig Inttriplefunc.empty
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   703
    val diagents =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   704
      Inttriplefunc.fold
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   705
        (fn ((b, i, j), e) => fn a => if b > 0 andalso i = j then tri_equation_add e a else a)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   706
        allassig Inttriplefunc.empty
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   707
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   708
    val mats = map mk_matrix qvars
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   709
    val obj =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   710
      (length pvs,
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   711
        itern 1 pvs (fn v => fn i =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   712
          FuncUtil.Intfunc.updatep iszero (i,Inttriplefunc.tryapplyd diagents v rat_0))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   713
          FuncUtil.Intfunc.empty)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   714
    val raw_vec =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   715
      if null pvs then vector_0 0
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   716
      else tri_scale_then (run_blockproblem prover nblocks blocksizes) obj mats
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   717
    fun int_element (_, v) i = FuncUtil.Intfunc.tryapplyd v i rat_0
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   718
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   719
    fun find_rounding d =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   720
      let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   721
        val _ =
58631
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
   722
          debug_message ctxt (fn () => "Trying rounding with limit "^Rat.string_of_rat d ^ "\n")
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   723
        val vec = nice_vector d raw_vec
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   724
        val blockmat =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   725
          iter (1, dim vec)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   726
            (fn i => fn a => bmatrix_add (bmatrix_cmul (int_element vec i) (nth mats i)) a)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   727
            (bmatrix_neg (nth mats 0))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   728
        val allmats = blocks blocksizes blockmat
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   729
      in (vec, map diag allmats) end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   730
    val (vec, ratdias) =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   731
      if null pvs then find_rounding rat_1
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   732
      else tryfind find_rounding (map Rat.rat_of_int (1 upto 31) @ map pow2 (5 upto 66))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   733
    val newassigs =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   734
      fold_rev (fn k => Inttriplefunc.update (nth pvs (k - 1), int_element vec k))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   735
        (1 upto dim vec) (Inttriplefunc.onefunc ((0, 0, 0), Rat.rat_of_int ~1))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   736
    val finalassigs =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   737
      Inttriplefunc.fold (fn (v, e) => fn a =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   738
        Inttriplefunc.update (v, tri_equation_eval newassigs e) a) allassig newassigs
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   739
    fun poly_of_epoly p =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   740
      FuncUtil.Monomialfunc.fold (fn (v, e) => fn a =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   741
          FuncUtil.Monomialfunc.updatep iszero (v, tri_equation_eval finalassigs e) a)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   742
        p FuncUtil.Monomialfunc.empty
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   743
    fun mk_sos mons =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   744
      let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   745
        fun mk_sq (c, m) =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   746
          (c, fold_rev (fn k => fn a =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   747
              FuncUtil.Monomialfunc.updatep iszero (nth mons (k - 1), int_element m k) a)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   748
            (1 upto length mons) FuncUtil.Monomialfunc.empty)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   749
      in map mk_sq end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   750
    val sqs = map2 mk_sos sqmonlist ratdias
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   751
    val cfs = map poly_of_epoly ids
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   752
    val msq = filter (fn (_, b) => not (null b)) (map2 pair monoid sqs)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   753
    fun eval_sq sqs = fold_rev (fn (c, q) => poly_add (poly_cmul c (poly_mul q q))) sqs poly_0
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   754
    val sanity =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   755
      fold_rev (fn ((p, _), s) => poly_add (poly_mul p (eval_sq s))) msq
58635
010b610eb55d eliminated some exotic combinators;
wenzelm
parents: 58631
diff changeset
   756
        (fold_rev (fn (p, q) => poly_add (poly_mul p q)) (cfs ~~ eqs) (poly_neg pol))
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   757
  in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   758
    if not(FuncUtil.Monomialfunc.is_empty sanity) then raise Sanity
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   759
    else (cfs, map (fn (a, b) => (snd a, b)) msq)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   760
  end
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   761
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   762
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   763
(* Iterative deepening.                                                      *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   764
58631
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
   765
fun deepen ctxt f n =
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
   766
  (trace_message ctxt (fn () => "Searching with depth limit " ^ string_of_int n);
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
   767
    (f n handle Failure s =>
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
   768
      (trace_message ctxt (fn () => "failed with message: " ^ s); deepen ctxt f (n + 1))));
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   769
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   770
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents: 32332
diff changeset
   771
(* Map back polynomials and their composites to a positivstellensatz.        *)
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   772
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   773
fun cterm_of_sqterm (c, p) = RealArith.Product (RealArith.Rational_lt c, RealArith.Square p);
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   774
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   775
fun cterm_of_sos (pr,sqs) =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   776
  if null sqs then pr
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   777
  else RealArith.Product (pr, foldr1 RealArith.Sum (map cterm_of_sqterm sqs));
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   778
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   779
(* Interface to HOL.                                                         *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   780
local
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   781
  open Conv
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
   782
  val concl = Thm.dest_arg o Thm.cprop_of
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
   783
  fun simple_cterm_ord t u = Term_Ord.fast_term_ord (Thm.term_of t, Thm.term_of u) = LESS
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   784
in
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   785
(* FIXME: Replace tryfind by get_first !! *)
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents: 32332
diff changeset
   786
fun real_nonlinear_prover proof_method ctxt =
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   787
  let
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   788
    val {add = _, mul = _, neg = _, pow = _, sub = _, main = real_poly_conv} =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   789
      Semiring_Normalizer.semiring_normalizers_ord_wrapper ctxt
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   790
        (the (Semiring_Normalizer.match ctxt @{cterm "(0::real) + 1"}))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   791
        simple_cterm_ord
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   792
    fun mainf cert_choice translator (eqs, les, lts) =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   793
      let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   794
        val eq0 = map (poly_of_term o Thm.dest_arg1 o concl) eqs
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   795
        val le0 = map (poly_of_term o Thm.dest_arg o concl) les
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   796
        val lt0 = map (poly_of_term o Thm.dest_arg o concl) lts
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   797
        val eqp0 = map_index (fn (i, t) => (t,RealArith.Axiom_eq i)) eq0
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   798
        val lep0 = map_index (fn (i, t) => (t,RealArith.Axiom_le i)) le0
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   799
        val ltp0 = map_index (fn (i, t) => (t,RealArith.Axiom_lt i)) lt0
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   800
        val (keq,eq) = List.partition (fn (p, _) => multidegree p = 0) eqp0
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   801
        val (klep,lep) = List.partition (fn (p, _) => multidegree p = 0) lep0
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   802
        val (kltp,ltp) = List.partition (fn (p, _) => multidegree p = 0) ltp0
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   803
        fun trivial_axiom (p, ax) =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   804
          (case ax of
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   805
            RealArith.Axiom_eq n =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   806
              if eval FuncUtil.Ctermfunc.empty p <>/ Rat.zero then nth eqs n
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   807
              else raise Failure "trivial_axiom: Not a trivial axiom"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   808
          | RealArith.Axiom_le n =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   809
              if eval FuncUtil.Ctermfunc.empty p </ Rat.zero then nth les n
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   810
              else raise Failure "trivial_axiom: Not a trivial axiom"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   811
          | RealArith.Axiom_lt n =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   812
              if eval FuncUtil.Ctermfunc.empty p <=/ Rat.zero then nth lts n
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   813
              else raise Failure "trivial_axiom: Not a trivial axiom"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   814
          | _ => error "trivial_axiom: Not a trivial axiom")
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   815
      in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   816
        let val th = tryfind trivial_axiom (keq @ klep @ kltp) in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   817
          (fconv_rule (arg_conv (arg1_conv (real_poly_conv ctxt))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   818
            then_conv Numeral_Simprocs.field_comp_conv ctxt) th,
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   819
            RealArith.Trivial)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   820
        end handle Failure _ =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   821
          let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   822
            val proof =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   823
              (case proof_method of
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   824
                Certificate certs =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   825
                  (* choose certificate *)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   826
                  let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   827
                    fun chose_cert [] (RealArith.Cert c) = c
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   828
                      | chose_cert (RealArith.Left::s) (RealArith.Branch (l, _)) = chose_cert s l
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   829
                      | chose_cert (RealArith.Right::s) (RealArith.Branch (_, r)) = chose_cert s r
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   830
                      | chose_cert _ _ = error "certificate tree in invalid form"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   831
                  in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   832
                    chose_cert cert_choice certs
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   833
                  end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   834
              | Prover prover =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   835
                  (* call prover *)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   836
                  let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   837
                    val pol = fold_rev poly_mul (map fst ltp) (poly_const Rat.one)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   838
                    val leq = lep @ ltp
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   839
                    fun tryall d =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   840
                      let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   841
                        val e = multidegree pol
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   842
                        val k = if e = 0 then 0 else d div e
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   843
                        val eq' = map fst eq
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   844
                      in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   845
                        tryfind (fn i =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   846
                            (d, i, real_positivnullstellensatz_general ctxt prover false d eq' leq
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   847
                              (poly_neg(poly_pow pol i))))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   848
                          (0 upto k)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   849
                      end
58631
41333b45bff9 clarified messages depending on options;
wenzelm
parents: 57889
diff changeset
   850
                    val (_,i,(cert_ideal,cert_cone)) = deepen ctxt tryall 0
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   851
                    val proofs_ideal =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   852
                      map2 (fn q => fn (_,ax) => RealArith.Eqmul(q,ax)) cert_ideal eq
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   853
                    val proofs_cone = map cterm_of_sos cert_cone
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   854
                    val proof_ne =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   855
                      if null ltp then RealArith.Rational_lt Rat.one
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   856
                      else
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   857
                        let val p = foldr1 RealArith.Product (map snd ltp) in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   858
                          funpow i (fn q => RealArith.Product (p, q))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   859
                            (RealArith.Rational_lt Rat.one)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   860
                        end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   861
                  in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   862
                    foldr1 RealArith.Sum (proof_ne :: proofs_ideal @ proofs_cone)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   863
                  end)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   864
          in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   865
            (translator (eqs,les,lts) proof, RealArith.Cert proof)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   866
          end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   867
      end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   868
  in mainf end
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   869
end
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   870
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   871
(* FIXME : This is very bad!!!*)
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   872
fun subst_conv eqs t =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   873
  let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   874
    val t' = fold (Thm.lambda o Thm.lhs_of) eqs t
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   875
  in
60329
e85ed7a36b2f eliminated odd C combinator -- Isabelle/ML usually has canonical argument order;
wenzelm
parents: 59582
diff changeset
   876
    Conv.fconv_rule (Thm.beta_conversion true)
e85ed7a36b2f eliminated odd C combinator -- Isabelle/ML usually has canonical argument order;
wenzelm
parents: 59582
diff changeset
   877
      (fold (fn a => fn b => Thm.combination b a) eqs (Thm.reflexive t'))
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   878
  end
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   879
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   880
(* A wrapper that tries to substitute away variables first.                  *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   881
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   882
local
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   883
  open Conv
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
   884
  fun simple_cterm_ord t u = Term_Ord.fast_term_ord (Thm.term_of t, Thm.term_of u) = LESS
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
   885
  val concl = Thm.dest_arg o Thm.cprop_of
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   886
  val shuffle1 =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   887
    fconv_rule (rewr_conv @{lemma "(a + x == y) == (x == y - (a::real))"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   888
      by (atomize (full)) (simp add: field_simps)})
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   889
  val shuffle2 =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   890
    fconv_rule (rewr_conv @{lemma "(x + a == y) ==  (x == y - (a::real))"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   891
      by (atomize (full)) (simp add: field_simps)})
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   892
  fun substitutable_monomial fvs tm =
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
   893
    (case Thm.term_of tm of
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   894
      Free (_, @{typ real}) =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   895
        if not (member (op aconvc) fvs tm) then (Rat.one, tm)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   896
        else raise Failure "substitutable_monomial"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   897
    | @{term "op * :: real => _"} $ _ $ (Free _) =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   898
        if RealArith.is_ratconst (Thm.dest_arg1 tm) andalso
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   899
          not (member (op aconvc) fvs (Thm.dest_arg tm))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   900
        then (RealArith.dest_ratconst (Thm.dest_arg1 tm), Thm.dest_arg tm)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   901
        else raise Failure "substitutable_monomial"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   902
    | @{term "op + :: real => _"}$_$_ =>
60818
5e11a6e2b044 more direct access to atomic cterms;
wenzelm
parents: 60801
diff changeset
   903
         (substitutable_monomial (Drule.cterm_add_frees (Thm.dest_arg tm) fvs) (Thm.dest_arg1 tm)
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   904
           handle Failure _ =>
60818
5e11a6e2b044 more direct access to atomic cterms;
wenzelm
parents: 60801
diff changeset
   905
            substitutable_monomial (Drule.cterm_add_frees (Thm.dest_arg1 tm) fvs) (Thm.dest_arg tm))
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   906
    | _ => raise Failure "substitutable_monomial")
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   907
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   908
  fun isolate_variable v th =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   909
    let
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
   910
      val w = Thm.dest_arg1 (Thm.cprop_of th)
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   911
    in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   912
      if v aconvc w then th
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   913
      else
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
   914
        (case Thm.term_of w of
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   915
          @{term "op + :: real => _"} $ _ $ _ =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   916
            if Thm.dest_arg1 w aconvc v then shuffle2 th
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   917
            else isolate_variable v (shuffle1 th)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   918
        | _ => error "isolate variable : This should not happen?")
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   919
   end
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   920
in
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   921
32268
d50f0cb67578 Functionality for sum of squares to call a remote csdp prover
Philipp Meyer
parents: 32150
diff changeset
   922
fun real_nonlinear_subst_prover prover ctxt =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   923
  let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   924
    val {add = _, mul = real_poly_mul_conv, neg = _, pow = _, sub = _, main = real_poly_conv} =
44453
082edd97ffe1 comment out dead code to avoid compiler warnings
huffman
parents: 42616
diff changeset
   925
      Semiring_Normalizer.semiring_normalizers_ord_wrapper ctxt
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   926
        (the (Semiring_Normalizer.match ctxt @{cterm "(0::real) + 1"}))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   927
        simple_cterm_ord
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   928
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   929
    fun make_substitution th =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   930
      let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   931
        val (c,v) = substitutable_monomial [] (Thm.dest_arg1(concl th))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   932
        val th1 =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   933
          Drule.arg_cong_rule
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   934
            (Thm.apply @{cterm "op * :: real => _"} (RealArith.cterm_of_rat (Rat.inv c)))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   935
            (mk_meta_eq th)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   936
        val th2 = fconv_rule (binop_conv (real_poly_mul_conv ctxt)) th1
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   937
      in fconv_rule (arg_conv (real_poly_conv ctxt)) (isolate_variable v th2) end
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   938
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   939
    fun oprconv cv ct =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   940
      let val g = Thm.dest_fun2 ct in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   941
        if g aconvc @{cterm "op <= :: real => _"} orelse g aconvc @{cterm "op < :: real => _"}
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   942
        then arg_conv cv ct else arg1_conv cv ct
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   943
      end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   944
    fun mainf cert_choice translator =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   945
      let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   946
        fun substfirst (eqs, les, lts) =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   947
          (let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   948
              val eth = tryfind make_substitution eqs
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   949
              val modify =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   950
                fconv_rule (arg_conv (oprconv(subst_conv [eth] then_conv (real_poly_conv ctxt))))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   951
            in
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   952
              substfirst
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   953
                (filter_out
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
   954
                  (fn t => (Thm.dest_arg1 o Thm.dest_arg o Thm.cprop_of) t aconvc @{cterm "0::real"})
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   955
                  (map modify eqs),
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   956
                  map modify les,
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   957
                  map modify lts)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   958
            end handle Failure  _ =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   959
              real_nonlinear_prover prover ctxt cert_choice translator (rev eqs, rev les, rev lts))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   960
      in substfirst end
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   961
  in mainf end
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   962
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   963
(* Overall function. *)
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   964
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents: 32332
diff changeset
   965
fun real_sos prover ctxt =
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32740
diff changeset
   966
  RealArith.gen_prover_real_arith ctxt (real_nonlinear_subst_prover prover ctxt)
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   967
31119
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   968
end;
2532bb2d65c7 A decision method for universal multivariate real arithmetic with add
chaieb
parents:
diff changeset
   969
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   970
val known_sos_constants =
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   971
  [@{term "op ==>"}, @{term "Trueprop"},
56625
54505623a8ef sos accepts False, returns apply command
paulson <lp15@cam.ac.uk>
parents: 56536
diff changeset
   972
   @{term HOL.False}, @{term HOL.implies}, @{term HOL.conj}, @{term HOL.disj},
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   973
   @{term "Not"}, @{term "op = :: bool => _"},
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   974
   @{term "All :: (real => _) => _"}, @{term "Ex :: (real => _) => _"},
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   975
   @{term "op = :: real => _"}, @{term "op < :: real => _"},
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   976
   @{term "op <= :: real => _"},
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   977
   @{term "op + :: real => _"}, @{term "op - :: real => _"},
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   978
   @{term "op * :: real => _"}, @{term "uminus :: real => _"},
31512
27118561c2e0 Tuned sos tactic to reject non SOS goals
chaieb
parents: 31131
diff changeset
   979
   @{term "op / :: real => _"}, @{term "inverse :: real => _"},
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   980
   @{term "op ^ :: real => _"}, @{term "abs :: real => _"},
31512
27118561c2e0 Tuned sos tactic to reject non SOS goals
chaieb
parents: 31131
diff changeset
   981
   @{term "min :: real => _"}, @{term "max :: real => _"},
47108
2a1953f0d20d merged fork with new numeral representation (see NEWS)
huffman
parents: 46497
diff changeset
   982
   @{term "0::real"}, @{term "1::real"},
2a1953f0d20d merged fork with new numeral representation (see NEWS)
huffman
parents: 46497
diff changeset
   983
   @{term "numeral :: num => nat"},
2a1953f0d20d merged fork with new numeral representation (see NEWS)
huffman
parents: 46497
diff changeset
   984
   @{term "numeral :: num => real"},
2a1953f0d20d merged fork with new numeral representation (see NEWS)
huffman
parents: 46497
diff changeset
   985
   @{term "Num.Bit0"}, @{term "Num.Bit1"}, @{term "Num.One"}];
31512
27118561c2e0 Tuned sos tactic to reject non SOS goals
chaieb
parents: 31131
diff changeset
   986
32839
a007a7cd8c2f tuned header;
wenzelm
parents: 32838
diff changeset
   987
fun check_sos kcts ct =
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   988
  let
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
   989
    val t = Thm.term_of ct
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   990
    val _ =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   991
      if not (null (Term.add_tfrees t []) andalso null (Term.add_tvars t []))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   992
      then error "SOS: not sos. Additional type varables"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   993
      else ()
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   994
    val fs = Term.add_frees t []
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   995
    val _ =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   996
      if exists (fn ((_,T)) => not (T = @{typ "real"})) fs
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   997
      then error "SOS: not sos. Variables with type not real"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   998
      else ()
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
   999
    val vs = Term.add_vars t []
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1000
    val _ =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1001
      if exists (fn ((_,T)) => not (T = @{typ "real"})) vs
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1002
      then error "SOS: not sos. Variables with type not real"
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1003
      else ()
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1004
    val ukcs = subtract (fn (t,p) => Const p aconv t) kcts (Term.add_consts t [])
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1005
    val _ =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1006
      if null ukcs then ()
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1007
      else error ("SOSO: Unknown constants in Subgoal:" ^ commas (map fst ukcs))
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1008
  in () end
31512
27118561c2e0 Tuned sos tactic to reject non SOS goals
chaieb
parents: 31131
diff changeset
  1009
60752
b48830b670a1 prefer tactics with explicit context;
wenzelm
parents: 60329
diff changeset
  1010
fun core_sos_tac print_cert prover = SUBPROOF (fn {concl, context = ctxt, ...} =>
32831
1352736e5727 changed core_sos_tac to use SUBPROOF
Philipp Meyer
parents: 32830
diff changeset
  1011
  let
32838
d9dfd30af9ae core_sos_tac: SUBPROOF body operates on subgoal 1;
wenzelm
parents: 32831
diff changeset
  1012
    val _ = check_sos known_sos_constants concl
60752
b48830b670a1 prefer tactics with explicit context;
wenzelm
parents: 60329
diff changeset
  1013
    val (th, certificates) = real_sos prover ctxt (Thm.dest_arg concl)
32838
d9dfd30af9ae core_sos_tac: SUBPROOF body operates on subgoal 1;
wenzelm
parents: 32831
diff changeset
  1014
    val _ = print_cert certificates
60752
b48830b670a1 prefer tactics with explicit context;
wenzelm
parents: 60329
diff changeset
  1015
  in resolve_tac ctxt [th] 1 end);
31131
d9752181691a Now deals with division
chaieb
parents: 31119
diff changeset
  1016
44453
082edd97ffe1 comment out dead code to avoid compiler warnings
huffman
parents: 42616
diff changeset
  1017
fun default_SOME _ NONE v = SOME v
082edd97ffe1 comment out dead code to avoid compiler warnings
huffman
parents: 42616
diff changeset
  1018
  | default_SOME _ (SOME v) _ = SOME v;
31131
d9752181691a Now deals with division
chaieb
parents: 31119
diff changeset
  1019
d9752181691a Now deals with division
chaieb
parents: 31119
diff changeset
  1020
fun lift_SOME f NONE a = f a
44453
082edd97ffe1 comment out dead code to avoid compiler warnings
huffman
parents: 42616
diff changeset
  1021
  | lift_SOME _ (SOME a) _ = SOME a;
31131
d9752181691a Now deals with division
chaieb
parents: 31119
diff changeset
  1022
d9752181691a Now deals with division
chaieb
parents: 31119
diff changeset
  1023
d9752181691a Now deals with division
chaieb
parents: 31119
diff changeset
  1024
local
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
  1025
  val is_numeral = can (HOLogic.dest_number o Thm.term_of)
31131
d9752181691a Now deals with division
chaieb
parents: 31119
diff changeset
  1026
in
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1027
  fun get_denom b ct =
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59058
diff changeset
  1028
    (case Thm.term_of ct of
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1029
      @{term "op / :: real => _"} $ _ $ _ =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1030
        if is_numeral (Thm.dest_arg ct)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1031
        then get_denom b (Thm.dest_arg1 ct)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1032
        else default_SOME (get_denom b) (get_denom b (Thm.dest_arg ct)) (Thm.dest_arg ct, b)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1033
    | @{term "op < :: real => _"} $ _ $ _ =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1034
        lift_SOME (get_denom true) (get_denom true (Thm.dest_arg ct)) (Thm.dest_arg1 ct)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1035
    | @{term "op <= :: real => _"} $ _ $ _ =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1036
        lift_SOME (get_denom true) (get_denom true (Thm.dest_arg ct)) (Thm.dest_arg1 ct)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1037
    | _ $ _ => lift_SOME (get_denom b) (get_denom b (Thm.dest_fun ct)) (Thm.dest_arg ct)
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1038
    | _ => NONE)
31131
d9752181691a Now deals with division
chaieb
parents: 31119
diff changeset
  1039
end;
d9752181691a Now deals with division
chaieb
parents: 31119
diff changeset
  1040
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1041
fun elim_one_denom_tac ctxt = CSUBGOAL (fn (P, i) =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1042
  (case get_denom false P of
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1043
    NONE => no_tac
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1044
  | SOME (d, ord) =>
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1045
      let
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1046
        val simp_ctxt =
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1047
          ctxt addsimps @{thms field_simps}
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1048
          addsimps [@{thm nonzero_power_divide}, @{thm power_divide}]
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1049
        val th =
60801
7664e0916eec tuned signature;
wenzelm
parents: 60752
diff changeset
  1050
          Thm.instantiate' [] [SOME d, SOME (Thm.dest_arg P)]
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1051
            (if ord then @{lemma "(d=0 --> P) & (d>0 --> P) & (d<(0::real) --> P) ==> P" by auto}
90c42b130652 tuned whitespace;
wenzelm
parents: 54742
diff changeset
  1052
             else @{lemma "(d=0 --> P) & (d ~= (0::real) --> P) ==> P" by blast})
60752
b48830b670a1 prefer tactics with explicit context;
wenzelm
parents: 60329
diff changeset
  1053
      in resolve_tac ctxt [th] i THEN Simplifier.asm_full_simp_tac simp_ctxt i end));
31131
d9752181691a Now deals with division
chaieb
parents: 31119
diff changeset
  1054
d9752181691a Now deals with division
chaieb
parents: 31119
diff changeset
  1055
fun elim_denom_tac ctxt i = REPEAT (elim_one_denom_tac ctxt i);
d9752181691a Now deals with division
chaieb
parents: 31119
diff changeset
  1056
32949
aa6c470a962a eliminated slightly odd get/set operations in favour of Unsynchronized.ref;
wenzelm
parents: 32839
diff changeset
  1057
fun sos_tac print_cert prover ctxt =
56536
aefb4a8da31f made mult_nonneg_nonneg a simp rule
nipkow
parents: 55508
diff changeset
  1058
  (* The SOS prover breaks if mult_nonneg_nonneg is in the simpset *)
57889
049e13f616d4 reduced warnings;
wenzelm
parents: 56625
diff changeset
  1059
  let val ctxt' = Context_Position.set_visible false ctxt delsimps @{thms mult_nonneg_nonneg}
56536
aefb4a8da31f made mult_nonneg_nonneg a simp rule
nipkow
parents: 55508
diff changeset
  1060
  in Object_Logic.full_atomize_tac ctxt' THEN'
aefb4a8da31f made mult_nonneg_nonneg a simp rule
nipkow
parents: 55508
diff changeset
  1061
     elim_denom_tac ctxt' THEN'
aefb4a8da31f made mult_nonneg_nonneg a simp rule
nipkow
parents: 55508
diff changeset
  1062
     core_sos_tac print_cert prover ctxt'
aefb4a8da31f made mult_nonneg_nonneg a simp rule
nipkow
parents: 55508
diff changeset
  1063
  end;
31131
d9752181691a Now deals with division
chaieb
parents: 31119
diff changeset
  1064
31512
27118561c2e0 Tuned sos tactic to reject non SOS goals
chaieb
parents: 31131
diff changeset
  1065
end;