src/HOL/Tools/semiring_normalizer.ML
changeset 51717 9e7d1c139569
parent 47108 2a1953f0d20d
child 53078 cc06f17d8057
equal deleted inserted replaced
51709:19b47bfac6ef 51717:9e7d1c139569
    25   val semiring_normalize_ord_wrapper: Proof.context -> entry
    25   val semiring_normalize_ord_wrapper: Proof.context -> entry
    26     -> (cterm -> cterm -> bool) -> conv
    26     -> (cterm -> cterm -> bool) -> conv
    27   val semiring_normalizers_conv: cterm list -> cterm list * thm list
    27   val semiring_normalizers_conv: cterm list -> cterm list * thm list
    28     -> cterm list * thm list -> cterm list * thm list ->
    28     -> cterm list * thm list -> cterm list * thm list ->
    29       (cterm -> bool) * conv * conv * conv -> (cterm -> cterm -> bool) ->
    29       (cterm -> bool) * conv * conv * conv -> (cterm -> cterm -> bool) ->
    30         {add: conv, mul: conv, neg: conv, main: conv, pow: conv, sub: conv}
    30         {add: Proof.context -> conv,
       
    31          mul: Proof.context -> conv,
       
    32          neg: Proof.context -> conv,
       
    33          main: Proof.context -> conv,
       
    34          pow: Proof.context -> conv,
       
    35          sub: Proof.context -> conv}
    31   val semiring_normalizers_ord_wrapper:  Proof.context -> entry ->
    36   val semiring_normalizers_ord_wrapper:  Proof.context -> entry ->
    32     (cterm -> cterm -> bool) ->
    37     (cterm -> cterm -> bool) ->
    33       {add: conv, mul: conv, neg: conv, main: conv, pow: conv, sub: conv}
    38       {add: Proof.context -> conv,
       
    39        mul: Proof.context -> conv,
       
    40        neg: Proof.context -> conv,
       
    41        main: Proof.context -> conv,
       
    42        pow: Proof.context -> conv,
       
    43        sub: Proof.context -> conv}
    34 
    44 
    35   val setup: theory -> theory
    45   val setup: theory -> theory
    36 end
    46 end
    37 
    47 
    38 structure Semiring_Normalizer: SEMIRING_NORMALIZER = 
    48 structure Semiring_Normalizer: SEMIRING_NORMALIZER = 
   175       Rat.rat_of_int (snd
   185       Rat.rat_of_int (snd
   176         (HOLogic.dest_number (Thm.term_of ct)
   186         (HOLogic.dest_number (Thm.term_of ct)
   177           handle TERM _ => error "ring_dest_const")),
   187           handle TERM _ => error "ring_dest_const")),
   178     mk_const = fn phi => fn cT => fn x => Numeral.mk_cnumber cT
   188     mk_const = fn phi => fn cT => fn x => Numeral.mk_cnumber cT
   179       (case Rat.quotient_of_rat x of (i, 1) => i | _ => error "int_of_rat: bad int"),
   189       (case Rat.quotient_of_rat x of (i, 1) => i | _ => error "int_of_rat: bad int"),
   180     conv = fn phi => fn _ => Simplifier.rewrite (HOL_basic_ss addsimps @{thms semiring_norm})
   190     conv = fn phi => fn ctxt =>
   181       then_conv Simplifier.rewrite (HOL_basic_ss addsimps
   191       Simplifier.rewrite (put_simpset HOL_basic_ss ctxt addsimps @{thms semiring_norm})
   182         @{thms numeral_1_eq_1})};
   192       then_conv Simplifier.rewrite (put_simpset HOL_basic_ss ctxt addsimps @{thms numeral_1_eq_1})};
   183 
   193 
   184 fun field_funs key =
   194 fun field_funs key =
   185   let
   195   let
   186     fun numeral_is_const ct =
   196     fun numeral_is_const ct =
   187       case term_of ct of
   197       case term_of ct of
   206       end
   216       end
   207   in funs key
   217   in funs key
   208      {is_const = K numeral_is_const,
   218      {is_const = K numeral_is_const,
   209       dest_const = K dest_const,
   219       dest_const = K dest_const,
   210       mk_const = mk_const,
   220       mk_const = mk_const,
   211       conv = K (K Numeral_Simprocs.field_comp_conv)}
   221       conv = K Numeral_Simprocs.field_comp_conv}
   212   end;
   222   end;
   213 
   223 
   214 
   224 
   215 
   225 
   216 (** auxiliary **)
   226 (** auxiliary **)
   234 fun inst_thm inst = Thm.instantiate ([], inst);
   244 fun inst_thm inst = Thm.instantiate ([], inst);
   235 
   245 
   236 val dest_numeral = term_of #> HOLogic.dest_number #> snd;
   246 val dest_numeral = term_of #> HOLogic.dest_number #> snd;
   237 val is_numeral = can dest_numeral;
   247 val is_numeral = can dest_numeral;
   238 
   248 
   239 val numeral01_conv = Simplifier.rewrite
   249 fun numeral01_conv ctxt =
   240                          (HOL_basic_ss addsimps [@{thm numeral_1_eq_1}]);
   250   Simplifier.rewrite (put_simpset HOL_basic_ss ctxt addsimps [@{thm numeral_1_eq_1}]);
   241 val zero1_numeral_conv = 
   251 
   242  Simplifier.rewrite (HOL_basic_ss addsimps [@{thm numeral_1_eq_1} RS sym]);
   252 fun zero1_numeral_conv ctxt =
   243 fun zerone_conv cv = zero1_numeral_conv then_conv cv then_conv numeral01_conv;
   253   Simplifier.rewrite (put_simpset HOL_basic_ss ctxt addsimps [@{thm numeral_1_eq_1} RS sym]);
       
   254 
       
   255 fun zerone_conv ctxt cv =
       
   256   zero1_numeral_conv ctxt then_conv cv then_conv numeral01_conv ctxt;
   244 val natarith = [@{thm "numeral_plus_numeral"}, @{thm "diff_nat_numeral"},
   257 val natarith = [@{thm "numeral_plus_numeral"}, @{thm "diff_nat_numeral"},
   245                 @{thm "numeral_times_numeral"}, @{thm "numeral_eq_iff"}, 
   258                 @{thm "numeral_times_numeral"}, @{thm "numeral_eq_iff"}, 
   246                 @{thm "numeral_less_iff"}];
   259                 @{thm "numeral_less_iff"}];
   247 
   260 
   248 val nat_add_conv = 
   261 fun nat_add_conv ctxt =
   249  zerone_conv 
   262   zerone_conv ctxt
   250   (Simplifier.rewrite 
   263     (Simplifier.rewrite 
   251     (HOL_basic_ss 
   264       (put_simpset HOL_basic_ss ctxt
   252        addsimps @{thms arith_simps} @ natarith @ @{thms rel_simps}
   265          addsimps @{thms arith_simps} @ natarith @ @{thms rel_simps}
   253              @ [@{thm if_False}, @{thm if_True}, @{thm Nat.add_0}, @{thm add_Suc},
   266                @ [@{thm if_False}, @{thm if_True}, @{thm Nat.add_0}, @{thm add_Suc},
   254                  @{thm add_numeral_left}, @{thm Suc_eq_plus1}]
   267                    @{thm add_numeral_left}, @{thm Suc_eq_plus1}]
   255              @ map (fn th => th RS sym) @{thms numerals}));
   268                @ map (fn th => th RS sym) @{thms numerals}));
   256 
   269 
   257 val zeron_tm = @{cterm "0::nat"};
   270 val zeron_tm = @{cterm "0::nat"};
   258 val onen_tm  = @{cterm "1::nat"};
   271 val onen_tm  = @{cterm "1::nat"};
   259 val true_tm = @{cterm "True"};
   272 val true_tm = @{cterm "True"};
   260 
   273 
   314 
   327 
   315 (* Conversion for "x^n * x^m", with either x^n = x and/or x^m = x possible.  *)
   328 (* Conversion for "x^n * x^m", with either x^n = x and/or x^m = x possible.  *)
   316 (* Also deals with "const * const", but both terms must involve powers of    *)
   329 (* Also deals with "const * const", but both terms must involve powers of    *)
   317 (* the same variable, or both be constants, or behaviour may be incorrect.   *)
   330 (* the same variable, or both be constants, or behaviour may be incorrect.   *)
   318 
   331 
   319  fun powvar_mul_conv tm =
   332  fun powvar_mul_conv ctxt tm =
   320   let
   333   let
   321   val (l,r) = dest_mul tm
   334   val (l,r) = dest_mul tm
   322   in if is_semiring_constant l andalso is_semiring_constant r
   335   in if is_semiring_constant l andalso is_semiring_constant r
   323      then semiring_mul_conv tm
   336      then semiring_mul_conv tm
   324      else
   337      else
   326          val (lx,ln) = dest_pow l
   339          val (lx,ln) = dest_pow l
   327         in
   340         in
   328          ((let val (rx,rn) = dest_pow r
   341          ((let val (rx,rn) = dest_pow r
   329                val th1 = inst_thm [(cx,lx),(cp,ln),(cq,rn)] pthm_29
   342                val th1 = inst_thm [(cx,lx),(cp,ln),(cq,rn)] pthm_29
   330                 val (tm1,tm2) = Thm.dest_comb(concl th1) in
   343                 val (tm1,tm2) = Thm.dest_comb(concl th1) in
   331                Thm.transitive th1 (Drule.arg_cong_rule tm1 (nat_add_conv tm2)) end)
   344                Thm.transitive th1 (Drule.arg_cong_rule tm1 (nat_add_conv ctxt tm2)) end)
   332            handle CTERM _ =>
   345            handle CTERM _ =>
   333             (let val th1 = inst_thm [(cx,lx),(cq,ln)] pthm_31
   346             (let val th1 = inst_thm [(cx,lx),(cq,ln)] pthm_31
   334                  val (tm1,tm2) = Thm.dest_comb(concl th1) in
   347                  val (tm1,tm2) = Thm.dest_comb(concl th1) in
   335                Thm.transitive th1 (Drule.arg_cong_rule tm1 (nat_add_conv tm2)) end)) end)
   348                Thm.transitive th1 (Drule.arg_cong_rule tm1 (nat_add_conv ctxt tm2)) end)) end)
   336        handle CTERM _ =>
   349        handle CTERM _ =>
   337            ((let val (rx,rn) = dest_pow r
   350            ((let val (rx,rn) = dest_pow r
   338                 val th1 = inst_thm [(cx,rx),(cq,rn)] pthm_30
   351                 val th1 = inst_thm [(cx,rx),(cq,rn)] pthm_30
   339                 val (tm1,tm2) = Thm.dest_comb(concl th1) in
   352                 val (tm1,tm2) = Thm.dest_comb(concl th1) in
   340                Thm.transitive th1 (Drule.arg_cong_rule tm1 (nat_add_conv tm2)) end)
   353                Thm.transitive th1 (Drule.arg_cong_rule tm1 (nat_add_conv ctxt tm2)) end)
   341            handle CTERM _ => inst_thm [(cx,l)] pthm_32
   354            handle CTERM _ => inst_thm [(cx,l)] pthm_32
   342 
   355 
   343 ))
   356 ))
   344  end;
   357  end;
   345 
   358 
   351           then Thm.transitive th (inst_thm [(ca,r)] pthm_13)  else th end)
   364           then Thm.transitive th (inst_thm [(ca,r)] pthm_13)  else th end)
   352        handle CTERM _ => th;
   365        handle CTERM _ => th;
   353 
   366 
   354 (* Conversion for "(monomial)^n", where n is a numeral.                      *)
   367 (* Conversion for "(monomial)^n", where n is a numeral.                      *)
   355 
   368 
   356  val monomial_pow_conv =
   369  fun monomial_pow_conv ctxt =
   357   let
   370   let
   358    fun monomial_pow tm bod ntm =
   371    fun monomial_pow tm bod ntm =
   359     if not(is_comb bod)
   372     if not(is_comb bod)
   360     then Thm.reflexive tm
   373     then Thm.reflexive tm
   361     else
   374     else
   372          in
   385          in
   373            if opr aconvc pow_tm andalso is_numeral r
   386            if opr aconvc pow_tm andalso is_numeral r
   374           then
   387           then
   375             let val th1 = inst_thm [(cx,l),(cp,r),(cq,ntm)] pthm_34
   388             let val th1 = inst_thm [(cx,l),(cp,r),(cq,ntm)] pthm_34
   376                 val (l,r) = Thm.dest_comb(concl th1)
   389                 val (l,r) = Thm.dest_comb(concl th1)
   377            in Thm.transitive th1 (Drule.arg_cong_rule l (nat_add_conv r))
   390            in Thm.transitive th1 (Drule.arg_cong_rule l (nat_add_conv ctxt r))
   378            end
   391            end
   379            else
   392            else
   380             if opr aconvc mul_tm
   393             if opr aconvc mul_tm
   381             then
   394             then
   382              let
   395              let
   403       else monomial_deone(monomial_pow tm l r)
   416       else monomial_deone(monomial_pow tm l r)
   404    end
   417    end
   405   end;
   418   end;
   406 
   419 
   407 (* Multiplication of canonical monomials.                                    *)
   420 (* Multiplication of canonical monomials.                                    *)
   408  val monomial_mul_conv =
   421  fun monomial_mul_conv ctxt =
   409   let
   422   let
   410    fun powvar tm =
   423    fun powvar tm =
   411     if is_semiring_constant tm then one_tm
   424     if is_semiring_constant tm then one_tm
   412     else
   425     else
   413      ((let val (lopr,r) = Thm.dest_comb tm
   426      ((let val (lopr,r) = Thm.dest_comb tm
   433         then
   446         then
   434           let
   447           let
   435              val th1 = inst_thm [(clx,lx),(cly,ly),(crx,rx),(cry,ry)] pthm_15
   448              val th1 = inst_thm [(clx,lx),(cly,ly),(crx,rx),(cry,ry)] pthm_15
   436              val (tm1,tm2) = Thm.dest_comb(concl th1)
   449              val (tm1,tm2) = Thm.dest_comb(concl th1)
   437              val (tm3,tm4) = Thm.dest_comb tm1
   450              val (tm3,tm4) = Thm.dest_comb tm1
   438              val th2 = Drule.fun_cong_rule (Drule.arg_cong_rule tm3 (powvar_mul_conv tm4)) tm2
   451              val th2 = Drule.fun_cong_rule (Drule.arg_cong_rule tm3 (powvar_mul_conv ctxt tm4)) tm2
   439              val th3 = Thm.transitive th1 th2
   452              val th3 = Thm.transitive th1 th2
   440               val  (tm5,tm6) = Thm.dest_comb(concl th3)
   453               val  (tm5,tm6) = Thm.dest_comb(concl th3)
   441               val  (tm7,tm8) = Thm.dest_comb tm6
   454               val  (tm7,tm8) = Thm.dest_comb tm6
   442              val  th4 = monomial_mul tm6 (Thm.dest_arg tm7) tm8
   455              val  th4 = monomial_mul tm6 (Thm.dest_arg tm7) tm8
   443          in Thm.transitive th3 (Drule.arg_cong_rule tm5 th4)
   456          in Thm.transitive th3 (Drule.arg_cong_rule tm5 th4)
   456           if ord = 0 then
   469           if ord = 0 then
   457            let
   470            let
   458            val th1 = inst_thm [(clx,lx),(cly,ly),(crx,r)] pthm_18
   471            val th1 = inst_thm [(clx,lx),(cly,ly),(crx,r)] pthm_18
   459                  val (tm1,tm2) = Thm.dest_comb(concl th1)
   472                  val (tm1,tm2) = Thm.dest_comb(concl th1)
   460            val (tm3,tm4) = Thm.dest_comb tm1
   473            val (tm3,tm4) = Thm.dest_comb tm1
   461            val th2 = Drule.fun_cong_rule (Drule.arg_cong_rule tm3 (powvar_mul_conv tm4)) tm2
   474            val th2 = Drule.fun_cong_rule (Drule.arg_cong_rule tm3 (powvar_mul_conv ctxt tm4)) tm2
   462           in Thm.transitive th1 th2
   475           in Thm.transitive th1 th2
   463           end
   476           end
   464           else
   477           else
   465           if ord < 0 then
   478           if ord < 0 then
   466             let val th1 = inst_thm [(clx,lx),(cly,ly),(crx,r)] pthm_19
   479             let val th1 = inst_thm [(clx,lx),(cly,ly),(crx,r)] pthm_19
   478            val ord = vorder vl vr
   491            val ord = vorder vl vr
   479          in if ord = 0 then
   492          in if ord = 0 then
   480               let val th1 = inst_thm [(clx,l),(crx,rx),(cry,ry)] pthm_21
   493               let val th1 = inst_thm [(clx,l),(crx,rx),(cry,ry)] pthm_21
   481                  val (tm1,tm2) = Thm.dest_comb(concl th1)
   494                  val (tm1,tm2) = Thm.dest_comb(concl th1)
   482                  val (tm3,tm4) = Thm.dest_comb tm1
   495                  val (tm3,tm4) = Thm.dest_comb tm1
   483              in Thm.transitive th1 (Drule.fun_cong_rule (Drule.arg_cong_rule tm3 (powvar_mul_conv tm4)) tm2)
   496              in Thm.transitive th1 (Drule.fun_cong_rule (Drule.arg_cong_rule tm3 (powvar_mul_conv ctxt tm4)) tm2)
   484              end
   497              end
   485              else if ord > 0 then
   498              else if ord > 0 then
   486                  let val th1 = inst_thm [(clx,l),(crx,rx),(cry,ry)] pthm_22
   499                  let val th1 = inst_thm [(clx,l),(crx,rx),(cry,ry)] pthm_22
   487                      val (tm1,tm2) = Thm.dest_comb(concl th1)
   500                      val (tm1,tm2) = Thm.dest_comb(concl th1)
   488                     val (tm3,tm4) = Thm.dest_comb tm2
   501                     val (tm3,tm4) = Thm.dest_comb tm2
   491              else Thm.reflexive tm
   504              else Thm.reflexive tm
   492          end)
   505          end)
   493         handle CTERM _ =>
   506         handle CTERM _ =>
   494           (let val vr = powvar r
   507           (let val vr = powvar r
   495                val  ord = vorder vl vr
   508                val  ord = vorder vl vr
   496           in if ord = 0 then powvar_mul_conv tm
   509           in if ord = 0 then powvar_mul_conv ctxt tm
   497               else if ord > 0 then inst_thm [(ca,l),(cb,r)] pthm_09
   510               else if ord > 0 then inst_thm [(ca,l),(cb,r)] pthm_09
   498               else Thm.reflexive tm
   511               else Thm.reflexive tm
   499           end)) end))
   512           end)) end))
   500   in fn tm => let val (l,r) = dest_mul tm in monomial_deone(monomial_mul tm l r)
   513   in fn tm => let val (l,r) = dest_mul tm in monomial_deone(monomial_mul tm l r)
   501              end
   514              end
   502   end;
   515   end;
   503 (* Multiplication by monomial of a polynomial.                               *)
   516 (* Multiplication by monomial of a polynomial.                               *)
   504 
   517 
   505  val polynomial_monomial_mul_conv =
   518  fun polynomial_monomial_mul_conv ctxt =
   506   let
   519   let
   507    fun pmm_conv tm =
   520    fun pmm_conv tm =
   508     let val (l,r) = dest_mul tm
   521     let val (l,r) = dest_mul tm
   509     in
   522     in
   510     ((let val (y,z) = dest_add r
   523     ((let val (y,z) = dest_add r
   511           val th1 = inst_thm [(cx,l),(cy,y),(cz,z)] pthm_37
   524           val th1 = inst_thm [(cx,l),(cy,y),(cz,z)] pthm_37
   512           val (tm1,tm2) = Thm.dest_comb(concl th1)
   525           val (tm1,tm2) = Thm.dest_comb(concl th1)
   513           val (tm3,tm4) = Thm.dest_comb tm1
   526           val (tm3,tm4) = Thm.dest_comb tm1
   514           val th2 = Thm.combination (Drule.arg_cong_rule tm3 (monomial_mul_conv tm4)) (pmm_conv tm2)
   527           val th2 =
       
   528             Thm.combination (Drule.arg_cong_rule tm3 (monomial_mul_conv ctxt tm4)) (pmm_conv tm2)
   515       in Thm.transitive th1 th2
   529       in Thm.transitive th1 th2
   516       end)
   530       end)
   517      handle CTERM _ => monomial_mul_conv tm)
   531      handle CTERM _ => monomial_mul_conv ctxt tm)
   518    end
   532    end
   519  in pmm_conv
   533  in pmm_conv
   520  end;
   534  end;
   521 
   535 
   522 (* Addition of two monomials identical except for constant multiples.        *)
   536 (* Addition of two monomials identical except for constant multiples.        *)
   590   end
   604   end
   591  end;
   605  end;
   592 
   606 
   593 (* Addition of two polynomials.                                              *)
   607 (* Addition of two polynomials.                                              *)
   594 
   608 
   595 val polynomial_add_conv =
   609 fun polynomial_add_conv ctxt =
   596  let
   610  let
   597  fun dezero_rule th =
   611  fun dezero_rule th =
   598   let
   612   let
   599    val tm = concl th
   613    val tm = concl th
   600   in
   614   in
   688  in padd
   702  in padd
   689  end;
   703  end;
   690 
   704 
   691 (* Multiplication of two polynomials.                                        *)
   705 (* Multiplication of two polynomials.                                        *)
   692 
   706 
   693 val polynomial_mul_conv =
   707 fun polynomial_mul_conv ctxt =
   694  let
   708  let
   695   fun pmul tm =
   709   fun pmul tm =
   696    let val (l,r) = dest_mul tm
   710    let val (l,r) = dest_mul tm
   697    in
   711    in
   698     if not(is_add l) then polynomial_monomial_mul_conv tm
   712     if not(is_add l) then polynomial_monomial_mul_conv ctxt tm
   699     else
   713     else
   700      if not(is_add r) then
   714      if not(is_add r) then
   701       let val th1 = inst_thm [(ca,l),(cb,r)] pthm_09
   715       let val th1 = inst_thm [(ca,l),(cb,r)] pthm_09
   702       in Thm.transitive th1 (polynomial_monomial_mul_conv(concl th1))
   716       in Thm.transitive th1 (polynomial_monomial_mul_conv ctxt (concl th1))
   703       end
   717       end
   704      else
   718      else
   705        let val (a,b) = dest_add l
   719        let val (a,b) = dest_add l
   706            val th1 = inst_thm [(ca,a),(cb,b),(cc,r)] pthm_10
   720            val th1 = inst_thm [(ca,a),(cb,b),(cc,r)] pthm_10
   707            val (tm1,tm2) = Thm.dest_comb(concl th1)
   721            val (tm1,tm2) = Thm.dest_comb(concl th1)
   708            val (tm3,tm4) = Thm.dest_comb tm1
   722            val (tm3,tm4) = Thm.dest_comb tm1
   709            val th2 = Drule.arg_cong_rule tm3 (polynomial_monomial_mul_conv tm4)
   723            val th2 = Drule.arg_cong_rule tm3 (polynomial_monomial_mul_conv ctxt tm4)
   710            val th3 = Thm.transitive th1 (Thm.combination th2 (pmul tm2))
   724            val th3 = Thm.transitive th1 (Thm.combination th2 (pmul tm2))
   711        in Thm.transitive th3 (polynomial_add_conv (concl th3))
   725        in Thm.transitive th3 (polynomial_add_conv ctxt (concl th3))
   712        end
   726        end
   713    end
   727    end
   714  in fn tm =>
   728  in fn tm =>
   715    let val (l,r) = dest_mul tm
   729    let val (l,r) = dest_mul tm
   716    in
   730    in
   722    end
   736    end
   723  end;
   737  end;
   724 
   738 
   725 (* Power of polynomial (optimized for the monomial and trivial cases).       *)
   739 (* Power of polynomial (optimized for the monomial and trivial cases).       *)
   726 
   740 
   727 fun num_conv n =
   741 fun num_conv ctxt n =
   728   nat_add_conv (Thm.apply @{cterm Suc} (Numeral.mk_cnumber @{ctyp nat} (dest_numeral n - 1)))
   742   nat_add_conv ctxt (Thm.apply @{cterm Suc} (Numeral.mk_cnumber @{ctyp nat} (dest_numeral n - 1)))
   729   |> Thm.symmetric;
   743   |> Thm.symmetric;
   730 
   744 
   731 
   745 
   732 val polynomial_pow_conv =
   746 fun polynomial_pow_conv ctxt =
   733  let
   747  let
   734   fun ppow tm =
   748   fun ppow tm =
   735     let val (l,n) = dest_pow tm
   749     let val (l,n) = dest_pow tm
   736     in
   750     in
   737      if n aconvc zeron_tm then inst_thm [(cx,l)] pthm_35
   751      if n aconvc zeron_tm then inst_thm [(cx,l)] pthm_35
   738      else if n aconvc onen_tm then inst_thm [(cx,l)] pthm_36
   752      else if n aconvc onen_tm then inst_thm [(cx,l)] pthm_36
   739      else
   753      else
   740          let val th1 = num_conv n
   754          let val th1 = num_conv ctxt n
   741              val th2 = inst_thm [(cx,l),(cq,Thm.dest_arg (concl th1))] pthm_38
   755              val th2 = inst_thm [(cx,l),(cq,Thm.dest_arg (concl th1))] pthm_38
   742              val (tm1,tm2) = Thm.dest_comb(concl th2)
   756              val (tm1,tm2) = Thm.dest_comb(concl th2)
   743              val th3 = Thm.transitive th2 (Drule.arg_cong_rule tm1 (ppow tm2))
   757              val th3 = Thm.transitive th2 (Drule.arg_cong_rule tm1 (ppow tm2))
   744              val th4 = Thm.transitive (Drule.arg_cong_rule (Thm.dest_fun tm) th1) th3
   758              val th4 = Thm.transitive (Drule.arg_cong_rule (Thm.dest_fun tm) th1) th3
   745          in Thm.transitive th4 (polynomial_mul_conv (concl th4))
   759          in Thm.transitive th4 (polynomial_mul_conv ctxt (concl th4))
   746          end
   760          end
   747     end
   761     end
   748  in fn tm =>
   762  in fn tm =>
   749        if is_add(Thm.dest_arg1 tm) then ppow tm else monomial_pow_conv tm
   763        if is_add(Thm.dest_arg1 tm) then ppow tm else monomial_pow_conv ctxt tm
   750  end;
   764  end;
   751 
   765 
   752 (* Negation.                                                                 *)
   766 (* Negation.                                                                 *)
   753 
   767 
   754 fun polynomial_neg_conv tm =
   768 fun polynomial_neg_conv ctxt tm =
   755    let val (l,r) = Thm.dest_comb tm in
   769    let val (l,r) = Thm.dest_comb tm in
   756         if not (l aconvc neg_tm) then raise CTERM ("polynomial_neg_conv",[tm]) else
   770         if not (l aconvc neg_tm) then raise CTERM ("polynomial_neg_conv",[tm]) else
   757         let val th1 = inst_thm [(cx',r)] neg_mul
   771         let val th1 = inst_thm [(cx',r)] neg_mul
   758             val th2 = Thm.transitive th1 (Conv.arg1_conv semiring_mul_conv (concl th1))
   772             val th2 = Thm.transitive th1 (Conv.arg1_conv semiring_mul_conv (concl th1))
   759         in Thm.transitive th2 (polynomial_monomial_mul_conv (concl th2))
   773         in Thm.transitive th2 (polynomial_monomial_mul_conv ctxt (concl th2))
   760         end
   774         end
   761    end;
   775    end;
   762 
   776 
   763 
   777 
   764 (* Subtraction.                                                              *)
   778 (* Subtraction.                                                              *)
   765 fun polynomial_sub_conv tm =
   779 fun polynomial_sub_conv ctxt tm =
   766   let val (l,r) = dest_sub tm
   780   let val (l,r) = dest_sub tm
   767       val th1 = inst_thm [(cx',l),(cy',r)] sub_add
   781       val th1 = inst_thm [(cx',l),(cy',r)] sub_add
   768       val (tm1,tm2) = Thm.dest_comb(concl th1)
   782       val (tm1,tm2) = Thm.dest_comb(concl th1)
   769       val th2 = Drule.arg_cong_rule tm1 (polynomial_neg_conv tm2)
   783       val th2 = Drule.arg_cong_rule tm1 (polynomial_neg_conv ctxt tm2)
   770   in Thm.transitive th1 (Thm.transitive th2 (polynomial_add_conv (concl th2)))
   784   in Thm.transitive th1 (Thm.transitive th2 (polynomial_add_conv ctxt (concl th2)))
   771   end;
   785   end;
   772 
   786 
   773 (* Conversion from HOL term.                                                 *)
   787 (* Conversion from HOL term.                                                 *)
   774 
   788 
   775 fun polynomial_conv tm =
   789 fun polynomial_conv ctxt tm =
   776  if is_semiring_constant tm then semiring_add_conv tm
   790  if is_semiring_constant tm then semiring_add_conv tm
   777  else if not(is_comb tm) then Thm.reflexive tm
   791  else if not(is_comb tm) then Thm.reflexive tm
   778  else
   792  else
   779   let val (lopr,r) = Thm.dest_comb tm
   793   let val (lopr,r) = Thm.dest_comb tm
   780   in if lopr aconvc neg_tm then
   794   in if lopr aconvc neg_tm then
   781        let val th1 = Drule.arg_cong_rule lopr (polynomial_conv r)
   795        let val th1 = Drule.arg_cong_rule lopr (polynomial_conv ctxt r)
   782        in Thm.transitive th1 (polynomial_neg_conv (concl th1))
   796        in Thm.transitive th1 (polynomial_neg_conv ctxt (concl th1))
   783        end
   797        end
   784      else if lopr aconvc inverse_tm then
   798      else if lopr aconvc inverse_tm then
   785        let val th1 = Drule.arg_cong_rule lopr (polynomial_conv r)
   799        let val th1 = Drule.arg_cong_rule lopr (polynomial_conv ctxt r)
   786        in Thm.transitive th1 (semiring_mul_conv (concl th1))
   800        in Thm.transitive th1 (semiring_mul_conv (concl th1))
   787        end
   801        end
   788      else
   802      else
   789        if not(is_comb lopr) then Thm.reflexive tm
   803        if not(is_comb lopr) then Thm.reflexive tm
   790        else
   804        else
   791          let val (opr,l) = Thm.dest_comb lopr
   805          let val (opr,l) = Thm.dest_comb lopr
   792          in if opr aconvc pow_tm andalso is_numeral r
   806          in if opr aconvc pow_tm andalso is_numeral r
   793             then
   807             then
   794               let val th1 = Drule.fun_cong_rule (Drule.arg_cong_rule opr (polynomial_conv l)) r
   808               let val th1 = Drule.fun_cong_rule (Drule.arg_cong_rule opr (polynomial_conv ctxt l)) r
   795               in Thm.transitive th1 (polynomial_pow_conv (concl th1))
   809               in Thm.transitive th1 (polynomial_pow_conv ctxt (concl th1))
   796               end
   810               end
   797          else if opr aconvc divide_tm 
   811          else if opr aconvc divide_tm 
   798             then
   812             then
   799               let val th1 = Thm.combination (Drule.arg_cong_rule opr (polynomial_conv l)) 
   813               let val th1 = Thm.combination (Drule.arg_cong_rule opr (polynomial_conv ctxt l)) 
   800                                         (polynomial_conv r)
   814                                         (polynomial_conv ctxt r)
   801                   val th2 = (Conv.rewr_conv divide_inverse then_conv polynomial_mul_conv)
   815                   val th2 = (Conv.rewr_conv divide_inverse then_conv polynomial_mul_conv ctxt)
   802                               (Thm.rhs_of th1)
   816                               (Thm.rhs_of th1)
   803               in Thm.transitive th1 th2
   817               in Thm.transitive th1 th2
   804               end
   818               end
   805             else
   819             else
   806               if opr aconvc add_tm orelse opr aconvc mul_tm orelse opr aconvc sub_tm
   820               if opr aconvc add_tm orelse opr aconvc mul_tm orelse opr aconvc sub_tm
   807               then
   821               then
   808                let val th1 =
   822                let val th1 =
   809                     Thm.combination (Drule.arg_cong_rule opr (polynomial_conv l)) (polynomial_conv r)
   823                     Thm.combination
   810                    val f = if opr aconvc add_tm then polynomial_add_conv
   824                       (Drule.arg_cong_rule opr (polynomial_conv ctxt l)) (polynomial_conv ctxt r)
   811                       else if opr aconvc mul_tm then polynomial_mul_conv
   825                    val f = if opr aconvc add_tm then polynomial_add_conv ctxt
   812                       else polynomial_sub_conv
   826                       else if opr aconvc mul_tm then polynomial_mul_conv ctxt
       
   827                       else polynomial_sub_conv ctxt
   813                in Thm.transitive th1 (f (concl th1))
   828                in Thm.transitive th1 (f (concl th1))
   814                end
   829                end
   815               else Thm.reflexive tm
   830               else Thm.reflexive tm
   816          end
   831          end
   817   end;
   832   end;
   824     sub = polynomial_sub_conv}
   839     sub = polynomial_sub_conv}
   825  end
   840  end
   826 end;
   841 end;
   827 
   842 
   828 val nat_exp_ss =
   843 val nat_exp_ss =
   829   HOL_basic_ss addsimps (@{thms eval_nat_numeral} @ @{thms nat_arith} @ @{thms arith_simps} @ @{thms rel_simps})
   844   simpset_of
   830     addsimps [@{thm Let_def}, @{thm if_False}, @{thm if_True}, @{thm Nat.add_0}, @{thm add_Suc}];
   845    (put_simpset HOL_basic_ss @{context}
       
   846     addsimps (@{thms eval_nat_numeral} @ @{thms nat_arith} @ @{thms arith_simps} @ @{thms rel_simps})
       
   847     addsimps [@{thm Let_def}, @{thm if_False}, @{thm if_True}, @{thm Nat.add_0}, @{thm add_Suc}]);
   831 
   848 
   832 fun simple_cterm_ord t u = Term_Ord.term_ord (term_of t, term_of u) = LESS;
   849 fun simple_cterm_ord t u = Term_Ord.term_ord (term_of t, term_of u) = LESS;
   833 
   850 
   834 
   851 
   835 (* various normalizing conversions *)
   852 (* various normalizing conversions *)
   836 
   853 
   837 fun semiring_normalizers_ord_wrapper ctxt ({vars, semiring, ring, field, idom, ideal}, 
   854 fun semiring_normalizers_ord_wrapper ctxt ({vars, semiring, ring, field, idom, ideal}, 
   838                                      {conv, dest_const, mk_const, is_const}) ord =
   855                                      {conv, dest_const, mk_const, is_const}) ord =
   839   let
   856   let
   840     val pow_conv =
   857     val pow_conv =
   841       Conv.arg_conv (Simplifier.rewrite nat_exp_ss)
   858       Conv.arg_conv (Simplifier.rewrite (put_simpset nat_exp_ss ctxt))
   842       then_conv Simplifier.rewrite
   859       then_conv Simplifier.rewrite
   843         (HOL_basic_ss addsimps [nth (snd semiring) 31, nth (snd semiring) 34])
   860         (put_simpset HOL_basic_ss ctxt addsimps [nth (snd semiring) 31, nth (snd semiring) 34])
   844       then_conv conv ctxt
   861       then_conv conv ctxt
   845     val dat = (is_const, conv ctxt, conv ctxt, pow_conv)
   862     val dat = (is_const, conv ctxt, conv ctxt, pow_conv)
   846   in semiring_normalizers_conv vars semiring ring field dat ord end;
   863   in semiring_normalizers_conv vars semiring ring field dat ord end;
   847 
   864 
   848 fun semiring_normalize_ord_wrapper ctxt ({vars, semiring, ring, field, idom, ideal}, {conv, dest_const, mk_const, is_const}) ord =
   865 fun semiring_normalize_ord_wrapper ctxt ({vars, semiring, ring, field, idom, ideal}, {conv, dest_const, mk_const, is_const}) ord =
   849  #main (semiring_normalizers_ord_wrapper ctxt ({vars = vars, semiring = semiring, ring = ring, field = field, idom = idom, ideal = ideal},{conv = conv, dest_const = dest_const, mk_const = mk_const, is_const = is_const}) ord);
   866  #main (semiring_normalizers_ord_wrapper ctxt
       
   867   ({vars = vars, semiring = semiring, ring = ring, field = field, idom = idom, ideal = ideal},
       
   868    {conv = conv, dest_const = dest_const, mk_const = mk_const, is_const = is_const}) ord) ctxt;
   850 
   869 
   851 fun semiring_normalize_wrapper ctxt data = 
   870 fun semiring_normalize_wrapper ctxt data = 
   852   semiring_normalize_ord_wrapper ctxt data simple_cterm_ord;
   871   semiring_normalize_ord_wrapper ctxt data simple_cterm_ord;
   853 
   872 
   854 fun semiring_normalize_ord_conv ctxt ord tm =
   873 fun semiring_normalize_ord_conv ctxt ord tm =