src/HOL/Tools/Groebner_Basis/normalizer.ML
changeset 23580 998a6fda9bb6
parent 23559 0de527730294
child 23880 64b9806e160b
equal deleted inserted replaced
23579:1a8ca0e480cd 23580:998a6fda9bb6
     3     Author:     Amine Chaieb, TU Muenchen
     3     Author:     Amine Chaieb, TU Muenchen
     4 *)
     4 *)
     5 
     5 
     6 signature NORMALIZER = 
     6 signature NORMALIZER = 
     7 sig
     7 sig
     8  val mk_cnumber : ctyp -> integer -> cterm
       
     9  val mk_cnumeral : integer -> cterm
       
    10  val semiring_normalize_conv : Proof.context -> conv
     8  val semiring_normalize_conv : Proof.context -> conv
    11  val semiring_normalize_ord_conv : Proof.context -> (cterm -> cterm -> bool) -> conv
     9  val semiring_normalize_ord_conv : Proof.context -> (cterm -> cterm -> bool) -> conv
    12  val semiring_normalize_tac : Proof.context -> int -> tactic
    10  val semiring_normalize_tac : Proof.context -> int -> tactic
    13  val semiring_normalize_wrapper :  Proof.context -> NormalizerData.entry -> conv
    11  val semiring_normalize_wrapper :  Proof.context -> NormalizerData.entry -> conv
    14  val semiring_normalize_ord_wrapper :  Proof.context -> NormalizerData.entry ->
    12  val semiring_normalize_ord_wrapper :  Proof.context -> NormalizerData.entry ->
    22 structure Normalizer: NORMALIZER = 
    20 structure Normalizer: NORMALIZER = 
    23 struct
    21 struct
    24 
    22 
    25 open Conv Misc;
    23 open Conv Misc;
    26 
    24 
    27 local
       
    28  val pls_const = @{cterm "Numeral.Pls"}
       
    29    and min_const = @{cterm "Numeral.Min"}
       
    30    and bit_const = @{cterm "Numeral.Bit"}
       
    31    and zero = @{cpat "0"}
       
    32    and one = @{cpat "1"}
       
    33  fun mk_cbit 0 = @{cterm "Numeral.bit.B0"}
       
    34   | mk_cbit 1 = @{cterm "Numeral.bit.B1"}
       
    35   | mk_cbit _ = raise CTERM ("mk_cbit", []);
       
    36 
       
    37 in
       
    38 
       
    39 fun mk_cnumeral 0 = pls_const
       
    40   | mk_cnumeral ~1 = min_const
       
    41   | mk_cnumeral i =
       
    42       let val (q, r) = Integer.divmod i 2
       
    43       in Thm.capply (Thm.capply bit_const (mk_cnumeral q)) (mk_cbit (Integer.machine_int r)) end;
       
    44 
       
    45 fun mk_cnumber cT = 
       
    46  let 
       
    47   val [nb_of, z, on] = 
       
    48     map (Drule.cterm_rule (instantiate' [SOME cT] [])) [@{cpat "number_of"}, zero, one]
       
    49   fun h 0 = z
       
    50     | h 1 = on
       
    51     | h x = Thm.capply nb_of (mk_cnumeral x)
       
    52  in h end;
       
    53 end;
       
    54 
       
    55 
       
    56 (* Very basic stuff for terms *)
    25 (* Very basic stuff for terms *)
    57 val dest_numeral = term_of #> HOLogic.dest_number #> snd;
    26 val dest_numeral = term_of #> HOLogic.dest_number #> snd;
    58 val is_numeral = can dest_numeral;
    27 val is_numeral = can dest_numeral;
    59 
    28 
    60 val numeral01_conv = Simplifier.rewrite
    29 val numeral01_conv = Simplifier.rewrite
    61                          (HOL_basic_ss addsimps [numeral_1_eq_1, numeral_0_eq_0]);
    30                          (HOL_basic_ss addsimps [numeral_1_eq_1, numeral_0_eq_0]);
    62 val zero1_numeral_conv = 
    31 val zero1_numeral_conv = 
    63  Simplifier.rewrite (HOL_basic_ss addsimps [numeral_1_eq_1 RS sym, numeral_0_eq_0 RS sym]);
    32  Simplifier.rewrite (HOL_basic_ss addsimps [numeral_1_eq_1 RS sym, numeral_0_eq_0 RS sym]);
    64 val zerone_conv = fn cv => zero1_numeral_conv then_conv cv then_conv numeral01_conv;
    33 fun zerone_conv cv = zero1_numeral_conv then_conv cv then_conv numeral01_conv;
    65 val natarith = [@{thm "add_nat_number_of"}, @{thm "diff_nat_number_of"},
    34 val natarith = [@{thm "add_nat_number_of"}, @{thm "diff_nat_number_of"},
    66                 @{thm "mult_nat_number_of"}, @{thm "eq_nat_number_of"}, 
    35                 @{thm "mult_nat_number_of"}, @{thm "eq_nat_number_of"}, 
    67                 @{thm "less_nat_number_of"}];
    36                 @{thm "less_nat_number_of"}];
    68 val nat_add_conv = 
    37 val nat_add_conv = 
    69  zerone_conv 
    38  zerone_conv 
   529    end
   498    end
   530  end;
   499  end;
   531 
   500 
   532 (* Power of polynomial (optimized for the monomial and trivial cases).       *)
   501 (* Power of polynomial (optimized for the monomial and trivial cases).       *)
   533 
   502 
   534 val Succ = @{cterm "Suc"};
   503 fun num_conv n =
   535 val num_conv = fn n =>
   504   nat_add_conv (Thm.capply @{cterm Suc} (Numeral.mk_cnumber @{ctyp nat} (dest_numeral n - 1)))
   536         nat_add_conv (Thm.capply (Succ) (mk_cnumber @{ctyp "nat"} ((dest_numeral n) - 1)))
   505   |> Thm.symmetric;
   537                      |> Thm.symmetric;
       
   538 
   506 
   539 
   507 
   540 val polynomial_pow_conv =
   508 val polynomial_pow_conv =
   541  let
   509  let
   542   fun ppow tm =
   510   fun ppow tm =
   557        if is_add(Thm.dest_arg1 tm) then ppow tm else monomial_pow_conv tm
   525        if is_add(Thm.dest_arg1 tm) then ppow tm else monomial_pow_conv tm
   558  end;
   526  end;
   559 
   527 
   560 (* Negation.                                                                 *)
   528 (* Negation.                                                                 *)
   561 
   529 
   562 val polynomial_neg_conv =
   530 fun polynomial_neg_conv tm =
   563  fn tm =>
       
   564    let val (l,r) = Thm.dest_comb tm in
   531    let val (l,r) = Thm.dest_comb tm in
   565         if not (l aconvc neg_tm) then raise CTERM ("polynomial_neg_conv",[tm]) else
   532         if not (l aconvc neg_tm) then raise CTERM ("polynomial_neg_conv",[tm]) else
   566         let val th1 = inst_thm [(cx',r)] neg_mul
   533         let val th1 = inst_thm [(cx',r)] neg_mul
   567             val th2 = transitive th1 (arg1_conv semiring_mul_conv (concl th1))
   534             val th2 = transitive th1 (arg1_conv semiring_mul_conv (concl th1))
   568         in transitive th2 (polynomial_monomial_mul_conv (concl th2))
   535         in transitive th2 (polynomial_monomial_mul_conv (concl th2))
   569         end
   536         end
   570    end;
   537    end;
   571 
   538 
   572 
   539 
   573 (* Subtraction.                                                              *)
   540 (* Subtraction.                                                              *)
   574 val polynomial_sub_conv = fn tm =>
   541 fun polynomial_sub_conv tm =
   575   let val (l,r) = dest_sub tm
   542   let val (l,r) = dest_sub tm
   576       val th1 = inst_thm [(cx',l),(cy',r)] sub_add
   543       val th1 = inst_thm [(cx',l),(cy',r)] sub_add
   577       val (tm1,tm2) = Thm.dest_comb(concl th1)
   544       val (tm1,tm2) = Thm.dest_comb(concl th1)
   578       val th2 = Drule.arg_cong_rule tm1 (polynomial_neg_conv tm2)
   545       val th2 = Drule.arg_cong_rule tm1 (polynomial_neg_conv tm2)
   579   in transitive th1 (transitive th2 (polynomial_add_conv (concl th2)))
   546   in transitive th1 (transitive th2 (polynomial_add_conv (concl th2)))