src/HOL/Library/Sum_of_Squares/positivstellensatz_tools.ML
author wenzelm
Wed, 08 Mar 2017 10:50:59 +0100
changeset 65151 a7394aa4d21c
parent 63208 3251e9dfea91
child 67271 48ef58c6cf4c
permissions -rw-r--r--
tuned proofs;
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
41474
60d091240485 renamed Sum_Of_Squares to Sum_of_Squares;
wenzelm
parents: 37744
diff changeset
     1
(*  Title:      HOL/Library/Sum_of_Squares/positivstellensatz_tools.ML
60d091240485 renamed Sum_Of_Squares to Sum_of_Squares;
wenzelm
parents: 37744
diff changeset
     2
    Author:     Philipp Meyer, TU Muenchen
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
     3
41474
60d091240485 renamed Sum_Of_Squares to Sum_of_Squares;
wenzelm
parents: 37744
diff changeset
     4
Functions for generating a certificate from a positivstellensatz and vice
60d091240485 renamed Sum_Of_Squares to Sum_of_Squares;
wenzelm
parents: 37744
diff changeset
     5
versa.
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
     6
*)
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
     7
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
     8
signature POSITIVSTELLENSATZ_TOOLS =
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
     9
sig
58629
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    10
  val print_cert: RealArith.pss_tree -> string
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    11
  val read_cert: Proof.context -> string -> RealArith.pss_tree
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    12
end
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    13
58629
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    14
structure Positivstellensatz_Tools : POSITIVSTELLENSATZ_TOOLS =
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    15
struct
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    16
58629
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    17
(** print certificate **)
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    18
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    19
local
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    20
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    21
(* map polynomials to strings *)
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    22
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    23
fun string_of_varpow x k =
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    24
  let
59582
0fbed69ff081 tuned signature -- prefer qualified names;
wenzelm
parents: 59580
diff changeset
    25
    val term = Thm.term_of x
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    26
    val name =
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    27
      (case term of
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    28
        Free (n, _) => n
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    29
      | _ => error "Term in monomial not free variable")
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    30
  in
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    31
    if k = 1 then name else name ^ "^" ^ string_of_int k
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    32
  end
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    33
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    34
fun string_of_monomial m =
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    35
  if FuncUtil.Ctermfunc.is_empty m then "1"
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    36
  else
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    37
    let
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    38
      val m' = FuncUtil.dest_monomial m
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    39
      val vps = fold_rev (fn (x,k) => cons (string_of_varpow x k)) m' []
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    40
    in foldr1 (fn (s, t) => s ^ "*" ^ t) vps end
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    41
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    42
fun string_of_cmonomial (m,c) =
63208
3251e9dfea91 clarified string_of_rat operations;
wenzelm
parents: 63205
diff changeset
    43
  if FuncUtil.Ctermfunc.is_empty m then Rat.string_of_rat c
63205
97b721666890 prefer rat numberals;
wenzelm
parents: 63201
diff changeset
    44
  else if c = @1 then string_of_monomial m
63208
3251e9dfea91 clarified string_of_rat operations;
wenzelm
parents: 63205
diff changeset
    45
  else Rat.string_of_rat c ^ "*" ^ string_of_monomial m
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    46
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    47
fun string_of_poly p =
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    48
  if FuncUtil.Monomialfunc.is_empty p then "0"
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    49
  else
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    50
    let
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    51
      val cms = map string_of_cmonomial
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    52
        (sort (prod_ord FuncUtil.monomial_order (K EQUAL)) (FuncUtil.Monomialfunc.dest p))
58629
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    53
    in foldr1 (fn (t1, t2) => t1 ^ " + " ^ t2) cms end
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    54
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    55
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    56
(* print cert *)
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    57
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32646
diff changeset
    58
fun pss_to_cert (RealArith.Axiom_eq i) = "A=" ^ string_of_int i
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32646
diff changeset
    59
  | pss_to_cert (RealArith.Axiom_le i) = "A<=" ^ string_of_int i
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32646
diff changeset
    60
  | pss_to_cert (RealArith.Axiom_lt i) = "A<" ^ string_of_int i
63208
3251e9dfea91 clarified string_of_rat operations;
wenzelm
parents: 63205
diff changeset
    61
  | pss_to_cert (RealArith.Rational_eq r) = "R=" ^ Rat.string_of_rat r
3251e9dfea91 clarified string_of_rat operations;
wenzelm
parents: 63205
diff changeset
    62
  | pss_to_cert (RealArith.Rational_le r) = "R<=" ^ Rat.string_of_rat r
3251e9dfea91 clarified string_of_rat operations;
wenzelm
parents: 63205
diff changeset
    63
  | pss_to_cert (RealArith.Rational_lt r) = "R<" ^ Rat.string_of_rat r
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32646
diff changeset
    64
  | pss_to_cert (RealArith.Square p) = "[" ^ string_of_poly p ^ "]^2"
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    65
  | pss_to_cert (RealArith.Eqmul (p, pss)) =
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    66
      "([" ^ string_of_poly p ^ "] * " ^ pss_to_cert pss ^ ")"
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    67
  | pss_to_cert (RealArith.Sum (pss1, pss2)) =
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    68
      "(" ^ pss_to_cert pss1 ^ " + " ^ pss_to_cert pss2 ^ ")"
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    69
  | pss_to_cert (RealArith.Product (pss1, pss2)) =
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    70
      "(" ^ pss_to_cert pss1 ^ " * " ^ pss_to_cert pss2 ^ ")"
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    71
58629
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    72
in
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    73
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    74
fun print_cert RealArith.Trivial = "()"
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    75
  | print_cert (RealArith.Cert pss) = "(" ^ pss_to_cert pss ^ ")"
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    76
  | print_cert (RealArith.Branch (t1, t2)) =
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    77
      "(" ^ print_cert t1 ^ " & " ^ print_cert t2 ^ ")"
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    78
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    79
end
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    80
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    81
58629
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    82
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    83
(** read certificate **)
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    84
58629
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    85
local
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    86
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    87
(* basic parsers *)
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    88
32646
962b4354ed90 used standard fold function and type aliases
Philipp Meyer
parents: 32645
diff changeset
    89
val str = Scan.this_string
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    90
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    91
val number =
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    92
  Scan.repeat1 (Scan.one Symbol.is_ascii_digit >> (fn s => ord s - ord "0"))
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
    93
    >> foldl1 (fn (n, d) => n * 10 + d)
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    94
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    95
val nat = number
58629
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
    96
val int = Scan.optional (str "~" >> K ~1) 1 -- nat >> op *
63201
f151704c08e4 tuned signature;
wenzelm
parents: 59621
diff changeset
    97
val rat = int --| str "/" -- int >> Rat.make
f151704c08e4 tuned signature;
wenzelm
parents: 59621
diff changeset
    98
val rat_int = rat || int >> Rat.of_int
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
    99
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
   100
58629
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
   101
(* polynomial parsers *)
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   102
32646
962b4354ed90 used standard fold function and type aliases
Philipp Meyer
parents: 32645
diff changeset
   103
fun repeat_sep s f = f ::: Scan.repeat (str s |-- f)
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   104
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   105
val parse_id = Scan.one Symbol.is_letter ::: Scan.many Symbol.is_letdig >> implode
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   106
32646
962b4354ed90 used standard fold function and type aliases
Philipp Meyer
parents: 32645
diff changeset
   107
fun parse_varpow ctxt = parse_id -- Scan.optional (str "^" |-- nat) 1 >>
59621
291934bac95e Thm.cterm_of and Thm.ctyp_of operate on local context;
wenzelm
parents: 59582
diff changeset
   108
  (fn (x, k) => (Thm.cterm_of ctxt (Free (x, @{typ real})), k))
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   109
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   110
fun parse_monomial ctxt = repeat_sep "*" (parse_varpow ctxt) >>
33339
d41f77196338 eliminated some old folds;
wenzelm
parents: 33030
diff changeset
   111
  (fn xs => fold FuncUtil.Ctermfunc.update xs FuncUtil.Ctermfunc.empty)
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   112
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   113
fun parse_cmonomial ctxt =
32646
962b4354ed90 used standard fold function and type aliases
Philipp Meyer
parents: 32645
diff changeset
   114
  rat_int --| str "*" -- (parse_monomial ctxt) >> swap ||
63205
97b721666890 prefer rat numberals;
wenzelm
parents: 63201
diff changeset
   115
  (parse_monomial ctxt) >> (fn m => (m, @1)) ||
32829
671eb46eb0a3 tuned FuncFun and FuncUtil structure in positivstellensatz.ML
Philipp Meyer
parents: 32828
diff changeset
   116
  rat_int >> (fn r => (FuncUtil.Ctermfunc.empty, r))
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   117
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   118
fun parse_poly ctxt = repeat_sep "+" (parse_cmonomial ctxt) >>
33339
d41f77196338 eliminated some old folds;
wenzelm
parents: 33030
diff changeset
   119
  (fn xs => fold FuncUtil.Monomialfunc.update xs FuncUtil.Monomialfunc.empty)
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   120
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
   121
58629
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
   122
(* positivstellensatz parsers *)
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   123
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   124
val parse_axiom =
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32646
diff changeset
   125
  (str "A=" |-- int >> RealArith.Axiom_eq) ||
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32646
diff changeset
   126
  (str "A<=" |-- int >> RealArith.Axiom_le) ||
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32646
diff changeset
   127
  (str "A<" |-- int >> RealArith.Axiom_lt)
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   128
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   129
val parse_rational =
32828
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32646
diff changeset
   130
  (str "R=" |-- rat_int >> RealArith.Rational_eq) ||
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32646
diff changeset
   131
  (str "R<=" |-- rat_int >> RealArith.Rational_le) ||
ad76967c703d removed opening of structures
Philipp Meyer
parents: 32646
diff changeset
   132
  (str "R<" |-- rat_int >> RealArith.Rational_lt)
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   133
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   134
fun parse_cert ctxt input =
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   135
  let
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   136
    val pc = parse_cert ctxt
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   137
    val pp = parse_poly ctxt
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   138
  in
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
   139
    (parse_axiom ||
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
   140
     parse_rational ||
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
   141
     str "[" |-- pp --| str "]^2" >> RealArith.Square ||
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
   142
     str "([" |-- pp --| str "]*" -- pc --| str ")" >> RealArith.Eqmul ||
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
   143
     str "(" |-- pc --| str "*" -- pc --| str ")" >> RealArith.Product ||
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
   144
     str "(" |-- pc --| str "+" -- pc --| str ")" >> RealArith.Sum) input
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   145
  end
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   146
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   147
fun parse_cert_tree ctxt input =
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   148
  let
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   149
    val pc = parse_cert ctxt
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   150
    val pt = parse_cert_tree ctxt
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   151
  in
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
   152
    (str "()" >> K RealArith.Trivial ||
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
   153
     str "(" |-- pc --| str ")" >> RealArith.Cert ||
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
   154
     str "(" |-- pt --| str "&" -- pt --| str ")" >> RealArith.Branch) input
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   155
  end
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   156
58629
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
   157
in
55508
90c42b130652 tuned whitespace;
wenzelm
parents: 43946
diff changeset
   158
58629
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
   159
fun read_cert ctxt input_str =
43946
wenzelm
parents: 42361
diff changeset
   160
  Symbol.scanner "Bad certificate" (parse_cert_tree ctxt)
wenzelm
parents: 42361
diff changeset
   161
    (filter_out Symbol.is_blank (Symbol.explode input_str))
32645
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   162
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   163
end
1cc5b24f5a01 sos method generates and uses proof certificates
Philipp Meyer
parents:
diff changeset
   164
58629
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
   165
end
a6a6cd499d4e tuned signature;
wenzelm
parents: 55508
diff changeset
   166