src/HOL/Library/Sum_of_Squares/sum_of_squares.ML
changeset 67271 48ef58c6cf4c
parent 67091 1393c2340eec
child 67399 eab6ce8368fa
equal deleted inserted replaced
67270:f18c774acde4 67271:48ef58c6cf4c
    46     val s = if r < @0 then ~ o Rat.of_int else Rat.of_int
    46     val s = if r < @0 then ~ o Rat.of_int else Rat.of_int
    47     val x2 = 2 * (a - (b * d))
    47     val x2 = 2 * (a - (b * d))
    48   in s (if x2 >= b then d + 1 else d) end
    48   in s (if x2 >= b then d + 1 else d) end
    49 
    49 
    50 
    50 
    51 val trace = Attrib.setup_config_bool @{binding sos_trace} (K false);
    51 val trace = Attrib.setup_config_bool \<^binding>\<open>sos_trace\<close> (K false);
    52 val debug = Attrib.setup_config_bool @{binding sos_debug} (K false);
    52 val debug = Attrib.setup_config_bool \<^binding>\<open>sos_debug\<close> (K false);
    53 
    53 
    54 fun trace_message ctxt msg =
    54 fun trace_message ctxt msg =
    55   if Config.get ctxt trace orelse Config.get ctxt debug then tracing (msg ()) else ();
    55   if Config.get ctxt trace orelse Config.get ctxt debug then tracing (msg ()) else ();
    56 fun debug_message ctxt msg = if Config.get ctxt debug then tracing (msg ()) else ();
    56 fun debug_message ctxt msg = if Config.get ctxt debug then tracing (msg ()) else ();
    57 
    57 
   216       (fn (m, _) => union (is_equal o FuncUtil.cterm_ord) (monomial_variables m)) p []);
   216       (fn (m, _) => union (is_equal o FuncUtil.cterm_ord) (monomial_variables m)) p []);
   217 
   217 
   218 (* Conversion from HOL term.                                                 *)
   218 (* Conversion from HOL term.                                                 *)
   219 
   219 
   220 local
   220 local
   221   val neg_tm = @{cterm "uminus :: real => _"}
   221   val neg_tm = \<^cterm>\<open>uminus :: real \<Rightarrow> _\<close>
   222   val add_tm = @{cterm "op + :: real => _"}
   222   val add_tm = \<^cterm>\<open>op + :: real \<Rightarrow> _\<close>
   223   val sub_tm = @{cterm "op - :: real => _"}
   223   val sub_tm = \<^cterm>\<open>op - :: real \<Rightarrow> _\<close>
   224   val mul_tm = @{cterm "op * :: real => _"}
   224   val mul_tm = \<^cterm>\<open>op * :: real \<Rightarrow> _\<close>
   225   val inv_tm = @{cterm "inverse :: real => _"}
   225   val inv_tm = \<^cterm>\<open>inverse :: real \<Rightarrow> _\<close>
   226   val div_tm = @{cterm "op / :: real => _"}
   226   val div_tm = \<^cterm>\<open>op / :: real \<Rightarrow> _\<close>
   227   val pow_tm = @{cterm "op ^ :: real => _"}
   227   val pow_tm = \<^cterm>\<open>op ^ :: real \<Rightarrow> _\<close>
   228   val zero_tm = @{cterm "0:: real"}
   228   val zero_tm = \<^cterm>\<open>0:: real\<close>
   229   val is_numeral = can (HOLogic.dest_number o Thm.term_of)
   229   val is_numeral = can (HOLogic.dest_number o Thm.term_of)
   230   fun poly_of_term tm =
   230   fun poly_of_term tm =
   231     if tm aconvc zero_tm then poly_0
   231     if tm aconvc zero_tm then poly_0
   232     else
   232     else
   233       if RealArith.is_ratconst tm
   233       if RealArith.is_ratconst tm
   268               else poly_var tm
   268               else poly_var tm
   269             end handle CTERM ("dest_comb",_) => poly_var tm)
   269             end handle CTERM ("dest_comb",_) => poly_var tm)
   270         end handle CTERM ("dest_comb",_) => poly_var tm)
   270         end handle CTERM ("dest_comb",_) => poly_var tm)
   271 in
   271 in
   272   val poly_of_term = fn tm =>
   272   val poly_of_term = fn tm =>
   273     if type_of (Thm.term_of tm) = @{typ real}
   273     if type_of (Thm.term_of tm) = \<^typ>\<open>real\<close>
   274     then poly_of_term tm
   274     then poly_of_term tm
   275     else error "poly_of_term: term does not have real type"
   275     else error "poly_of_term: term does not have real type"
   276 end;
   276 end;
   277 
   277 
   278 
   278 
   755 (* FIXME: Replace tryfind by get_first !! *)
   755 (* FIXME: Replace tryfind by get_first !! *)
   756 fun real_nonlinear_prover proof_method ctxt =
   756 fun real_nonlinear_prover proof_method ctxt =
   757   let
   757   let
   758     val {add = _, mul = _, neg = _, pow = _, sub = _, main = real_poly_conv} =
   758     val {add = _, mul = _, neg = _, pow = _, sub = _, main = real_poly_conv} =
   759       Semiring_Normalizer.semiring_normalizers_ord_wrapper ctxt
   759       Semiring_Normalizer.semiring_normalizers_ord_wrapper ctxt
   760         (the (Semiring_Normalizer.match ctxt @{cterm "(0::real) + 1"}))
   760         (the (Semiring_Normalizer.match ctxt \<^cterm>\<open>(0::real) + 1\<close>))
   761         simple_cterm_ord
   761         simple_cterm_ord
   762     fun mainf cert_choice translator (eqs, les, lts) =
   762     fun mainf cert_choice translator (eqs, les, lts) =
   763       let
   763       let
   764         val eq0 = map (poly_of_term o Thm.dest_arg1 o concl) eqs
   764         val eq0 = map (poly_of_term o Thm.dest_arg1 o concl) eqs
   765         val le0 = map (poly_of_term o Thm.dest_arg o concl) les
   765         val le0 = map (poly_of_term o Thm.dest_arg o concl) les
   859   val shuffle2 =
   859   val shuffle2 =
   860     fconv_rule (rewr_conv @{lemma "(x + a == y) ==  (x == y - (a::real))"
   860     fconv_rule (rewr_conv @{lemma "(x + a == y) ==  (x == y - (a::real))"
   861       by (atomize (full)) (simp add: field_simps)})
   861       by (atomize (full)) (simp add: field_simps)})
   862   fun substitutable_monomial fvs tm =
   862   fun substitutable_monomial fvs tm =
   863     (case Thm.term_of tm of
   863     (case Thm.term_of tm of
   864       Free (_, @{typ real}) =>
   864       Free (_, \<^typ>\<open>real\<close>) =>
   865         if not (member (op aconvc) fvs tm) then (@1, tm)
   865         if not (member (op aconvc) fvs tm) then (@1, tm)
   866         else raise Failure "substitutable_monomial"
   866         else raise Failure "substitutable_monomial"
   867     | @{term "op * :: real => _"} $ _ $ (Free _) =>
   867     | \<^term>\<open>op * :: real \<Rightarrow> _\<close> $ _ $ (Free _) =>
   868         if RealArith.is_ratconst (Thm.dest_arg1 tm) andalso
   868         if RealArith.is_ratconst (Thm.dest_arg1 tm) andalso
   869           not (member (op aconvc) fvs (Thm.dest_arg tm))
   869           not (member (op aconvc) fvs (Thm.dest_arg tm))
   870         then (RealArith.dest_ratconst (Thm.dest_arg1 tm), Thm.dest_arg tm)
   870         then (RealArith.dest_ratconst (Thm.dest_arg1 tm), Thm.dest_arg tm)
   871         else raise Failure "substitutable_monomial"
   871         else raise Failure "substitutable_monomial"
   872     | @{term "op + :: real => _"}$_$_ =>
   872     | \<^term>\<open>op + :: real \<Rightarrow> _\<close>$_$_ =>
   873          (substitutable_monomial (Drule.cterm_add_frees (Thm.dest_arg tm) fvs) (Thm.dest_arg1 tm)
   873          (substitutable_monomial (Drule.cterm_add_frees (Thm.dest_arg tm) fvs) (Thm.dest_arg1 tm)
   874            handle Failure _ =>
   874            handle Failure _ =>
   875             substitutable_monomial (Drule.cterm_add_frees (Thm.dest_arg1 tm) fvs) (Thm.dest_arg tm))
   875             substitutable_monomial (Drule.cterm_add_frees (Thm.dest_arg1 tm) fvs) (Thm.dest_arg tm))
   876     | _ => raise Failure "substitutable_monomial")
   876     | _ => raise Failure "substitutable_monomial")
   877 
   877 
   880       val w = Thm.dest_arg1 (Thm.cprop_of th)
   880       val w = Thm.dest_arg1 (Thm.cprop_of th)
   881     in
   881     in
   882       if v aconvc w then th
   882       if v aconvc w then th
   883       else
   883       else
   884         (case Thm.term_of w of
   884         (case Thm.term_of w of
   885           @{term "op + :: real => _"} $ _ $ _ =>
   885           \<^term>\<open>op + :: real \<Rightarrow> _\<close> $ _ $ _ =>
   886             if Thm.dest_arg1 w aconvc v then shuffle2 th
   886             if Thm.dest_arg1 w aconvc v then shuffle2 th
   887             else isolate_variable v (shuffle1 th)
   887             else isolate_variable v (shuffle1 th)
   888         | _ => error "isolate variable : This should not happen?")
   888         | _ => error "isolate variable : This should not happen?")
   889    end
   889    end
   890 in
   890 in
   891 
   891 
   892 fun real_nonlinear_subst_prover prover ctxt =
   892 fun real_nonlinear_subst_prover prover ctxt =
   893   let
   893   let
   894     val {add = _, mul = real_poly_mul_conv, neg = _, pow = _, sub = _, main = real_poly_conv} =
   894     val {add = _, mul = real_poly_mul_conv, neg = _, pow = _, sub = _, main = real_poly_conv} =
   895       Semiring_Normalizer.semiring_normalizers_ord_wrapper ctxt
   895       Semiring_Normalizer.semiring_normalizers_ord_wrapper ctxt
   896         (the (Semiring_Normalizer.match ctxt @{cterm "(0::real) + 1"}))
   896         (the (Semiring_Normalizer.match ctxt \<^cterm>\<open>(0::real) + 1\<close>))
   897         simple_cterm_ord
   897         simple_cterm_ord
   898 
   898 
   899     fun make_substitution th =
   899     fun make_substitution th =
   900       let
   900       let
   901         val (c,v) = substitutable_monomial [] (Thm.dest_arg1(concl th))
   901         val (c,v) = substitutable_monomial [] (Thm.dest_arg1(concl th))
   902         val th1 =
   902         val th1 =
   903           Drule.arg_cong_rule
   903           Drule.arg_cong_rule
   904             (Thm.apply @{cterm "op * :: real => _"} (RealArith.cterm_of_rat (Rat.inv c)))
   904             (Thm.apply \<^cterm>\<open>op * :: real \<Rightarrow> _\<close> (RealArith.cterm_of_rat (Rat.inv c)))
   905             (mk_meta_eq th)
   905             (mk_meta_eq th)
   906         val th2 = fconv_rule (binop_conv (real_poly_mul_conv ctxt)) th1
   906         val th2 = fconv_rule (binop_conv (real_poly_mul_conv ctxt)) th1
   907       in fconv_rule (arg_conv (real_poly_conv ctxt)) (isolate_variable v th2) end
   907       in fconv_rule (arg_conv (real_poly_conv ctxt)) (isolate_variable v th2) end
   908 
   908 
   909     fun oprconv cv ct =
   909     fun oprconv cv ct =
   910       let val g = Thm.dest_fun2 ct in
   910       let val g = Thm.dest_fun2 ct in
   911         if g aconvc @{cterm "op <= :: real => _"} orelse g aconvc @{cterm "op < :: real => _"}
   911         if g aconvc \<^cterm>\<open>op \<le> :: real \<Rightarrow> _\<close> orelse g aconvc \<^cterm>\<open>op < :: real \<Rightarrow> _\<close>
   912         then arg_conv cv ct else arg1_conv cv ct
   912         then arg_conv cv ct else arg1_conv cv ct
   913       end
   913       end
   914     fun mainf cert_choice translator =
   914     fun mainf cert_choice translator =
   915       let
   915       let
   916         fun substfirst (eqs, les, lts) =
   916         fun substfirst (eqs, les, lts) =
   919               val modify =
   919               val modify =
   920                 fconv_rule (arg_conv (oprconv(subst_conv [eth] then_conv (real_poly_conv ctxt))))
   920                 fconv_rule (arg_conv (oprconv(subst_conv [eth] then_conv (real_poly_conv ctxt))))
   921             in
   921             in
   922               substfirst
   922               substfirst
   923                 (filter_out
   923                 (filter_out
   924                   (fn t => (Thm.dest_arg1 o Thm.dest_arg o Thm.cprop_of) t aconvc @{cterm "0::real"})
   924                   (fn t => (Thm.dest_arg1 o Thm.dest_arg o Thm.cprop_of) t aconvc \<^cterm>\<open>0::real\<close>)
   925                   (map modify eqs),
   925                   (map modify eqs),
   926                   map modify les,
   926                   map modify les,
   927                   map modify lts)
   927                   map modify lts)
   928             end handle Failure  _ =>
   928             end handle Failure  _ =>
   929               real_nonlinear_prover prover ctxt cert_choice translator (rev eqs, rev les, rev lts))
   929               real_nonlinear_prover prover ctxt cert_choice translator (rev eqs, rev les, rev lts))
   936   RealArith.gen_prover_real_arith ctxt (real_nonlinear_subst_prover prover ctxt)
   936   RealArith.gen_prover_real_arith ctxt (real_nonlinear_subst_prover prover ctxt)
   937 
   937 
   938 end;
   938 end;
   939 
   939 
   940 val known_sos_constants =
   940 val known_sos_constants =
   941   [@{term "op ==>"}, @{term "Trueprop"},
   941   [\<^term>\<open>op \<Longrightarrow>\<close>, \<^term>\<open>Trueprop\<close>,
   942    @{term HOL.False}, @{term HOL.implies}, @{term HOL.conj}, @{term HOL.disj},
   942    \<^term>\<open>HOL.False\<close>, \<^term>\<open>HOL.implies\<close>, \<^term>\<open>HOL.conj\<close>, \<^term>\<open>HOL.disj\<close>,
   943    @{term "Not"}, @{term "op = :: bool => _"},
   943    \<^term>\<open>Not\<close>, \<^term>\<open>op = :: bool \<Rightarrow> _\<close>,
   944    @{term "All :: (real => _) => _"}, @{term "Ex :: (real => _) => _"},
   944    \<^term>\<open>All :: (real \<Rightarrow> _) \<Rightarrow> _\<close>, \<^term>\<open>Ex :: (real \<Rightarrow> _) \<Rightarrow> _\<close>,
   945    @{term "op = :: real => _"}, @{term "op < :: real => _"},
   945    \<^term>\<open>op = :: real \<Rightarrow> _\<close>, \<^term>\<open>op < :: real \<Rightarrow> _\<close>,
   946    @{term "op <= :: real => _"},
   946    \<^term>\<open>op \<le> :: real \<Rightarrow> _\<close>,
   947    @{term "op + :: real => _"}, @{term "op - :: real => _"},
   947    \<^term>\<open>op + :: real \<Rightarrow> _\<close>, \<^term>\<open>op - :: real \<Rightarrow> _\<close>,
   948    @{term "op * :: real => _"}, @{term "uminus :: real => _"},
   948    \<^term>\<open>op * :: real \<Rightarrow> _\<close>, \<^term>\<open>uminus :: real \<Rightarrow> _\<close>,
   949    @{term "op / :: real => _"}, @{term "inverse :: real => _"},
   949    \<^term>\<open>op / :: real \<Rightarrow> _\<close>, \<^term>\<open>inverse :: real \<Rightarrow> _\<close>,
   950    @{term "op ^ :: real => _"}, @{term "abs :: real => _"},
   950    \<^term>\<open>op ^ :: real \<Rightarrow> _\<close>, \<^term>\<open>abs :: real \<Rightarrow> _\<close>,
   951    @{term "min :: real => _"}, @{term "max :: real => _"},
   951    \<^term>\<open>min :: real \<Rightarrow> _\<close>, \<^term>\<open>max :: real \<Rightarrow> _\<close>,
   952    @{term "0::real"}, @{term "1::real"},
   952    \<^term>\<open>0::real\<close>, \<^term>\<open>1::real\<close>,
   953    @{term "numeral :: num => nat"},
   953    \<^term>\<open>numeral :: num \<Rightarrow> nat\<close>,
   954    @{term "numeral :: num => real"},
   954    \<^term>\<open>numeral :: num \<Rightarrow> real\<close>,
   955    @{term "Num.Bit0"}, @{term "Num.Bit1"}, @{term "Num.One"}];
   955    \<^term>\<open>Num.Bit0\<close>, \<^term>\<open>Num.Bit1\<close>, \<^term>\<open>Num.One\<close>];
   956 
   956 
   957 fun check_sos kcts ct =
   957 fun check_sos kcts ct =
   958   let
   958   let
   959     val t = Thm.term_of ct
   959     val t = Thm.term_of ct
   960     val _ =
   960     val _ =
   961       if not (null (Term.add_tfrees t []) andalso null (Term.add_tvars t []))
   961       if not (null (Term.add_tfrees t []) andalso null (Term.add_tvars t []))
   962       then error "SOS: not sos. Additional type varables"
   962       then error "SOS: not sos. Additional type varables"
   963       else ()
   963       else ()
   964     val fs = Term.add_frees t []
   964     val fs = Term.add_frees t []
   965     val _ =
   965     val _ =
   966       if exists (fn ((_,T)) => not (T = @{typ "real"})) fs
   966       if exists (fn ((_,T)) => not (T = \<^typ>\<open>real\<close>)) fs
   967       then error "SOS: not sos. Variables with type not real"
   967       then error "SOS: not sos. Variables with type not real"
   968       else ()
   968       else ()
   969     val vs = Term.add_vars t []
   969     val vs = Term.add_vars t []
   970     val _ =
   970     val _ =
   971       if exists (fn ((_,T)) => not (T = @{typ "real"})) vs
   971       if exists (fn ((_,T)) => not (T = \<^typ>\<open>real\<close>)) vs
   972       then error "SOS: not sos. Variables with type not real"
   972       then error "SOS: not sos. Variables with type not real"
   973       else ()
   973       else ()
   974     val ukcs = subtract (fn (t,p) => Const p aconv t) kcts (Term.add_consts t [])
   974     val ukcs = subtract (fn (t,p) => Const p aconv t) kcts (Term.add_consts t [])
   975     val _ =
   975     val _ =
   976       if null ukcs then ()
   976       if null ukcs then ()
   994 local
   994 local
   995   val is_numeral = can (HOLogic.dest_number o Thm.term_of)
   995   val is_numeral = can (HOLogic.dest_number o Thm.term_of)
   996 in
   996 in
   997   fun get_denom b ct =
   997   fun get_denom b ct =
   998     (case Thm.term_of ct of
   998     (case Thm.term_of ct of
   999       @{term "op / :: real => _"} $ _ $ _ =>
   999       \<^term>\<open>op / :: real \<Rightarrow> _\<close> $ _ $ _ =>
  1000         if is_numeral (Thm.dest_arg ct)
  1000         if is_numeral (Thm.dest_arg ct)
  1001         then get_denom b (Thm.dest_arg1 ct)
  1001         then get_denom b (Thm.dest_arg1 ct)
  1002         else default_SOME (get_denom b) (get_denom b (Thm.dest_arg ct)) (Thm.dest_arg ct, b)
  1002         else default_SOME (get_denom b) (get_denom b (Thm.dest_arg ct)) (Thm.dest_arg ct, b)
  1003     | @{term "op < :: real => _"} $ _ $ _ =>
  1003     | \<^term>\<open>op < :: real \<Rightarrow> _\<close> $ _ $ _ =>
  1004         lift_SOME (get_denom true) (get_denom true (Thm.dest_arg ct)) (Thm.dest_arg1 ct)
  1004         lift_SOME (get_denom true) (get_denom true (Thm.dest_arg ct)) (Thm.dest_arg1 ct)
  1005     | @{term "op <= :: real => _"} $ _ $ _ =>
  1005     | \<^term>\<open>op \<le> :: real \<Rightarrow> _\<close> $ _ $ _ =>
  1006         lift_SOME (get_denom true) (get_denom true (Thm.dest_arg ct)) (Thm.dest_arg1 ct)
  1006         lift_SOME (get_denom true) (get_denom true (Thm.dest_arg ct)) (Thm.dest_arg1 ct)
  1007     | _ $ _ => lift_SOME (get_denom b) (get_denom b (Thm.dest_fun ct)) (Thm.dest_arg ct)
  1007     | _ $ _ => lift_SOME (get_denom b) (get_denom b (Thm.dest_fun ct)) (Thm.dest_arg ct)
  1008     | _ => NONE)
  1008     | _ => NONE)
  1009 end;
  1009 end;
  1010 
  1010