src/HOL/Tools/nat_numeral_simprocs.ML
changeset 51717 9e7d1c139569
parent 47108 2a1953f0d20d
child 57514 bdc2c6b40bf2
equal deleted inserted replaced
51709:19b47bfac6ef 51717:9e7d1c139569
     3 Simprocs for nat numerals.
     3 Simprocs for nat numerals.
     4 *)
     4 *)
     5 
     5 
     6 signature NAT_NUMERAL_SIMPROCS =
     6 signature NAT_NUMERAL_SIMPROCS =
     7 sig
     7 sig
     8   val combine_numerals: simpset -> cterm -> thm option
     8   val combine_numerals: Proof.context -> cterm -> thm option
     9   val eq_cancel_numerals: simpset -> cterm -> thm option
     9   val eq_cancel_numerals: Proof.context -> cterm -> thm option
    10   val less_cancel_numerals: simpset -> cterm -> thm option
    10   val less_cancel_numerals: Proof.context -> cterm -> thm option
    11   val le_cancel_numerals: simpset -> cterm -> thm option
    11   val le_cancel_numerals: Proof.context -> cterm -> thm option
    12   val diff_cancel_numerals: simpset -> cterm -> thm option
    12   val diff_cancel_numerals: Proof.context -> cterm -> thm option
    13   val eq_cancel_numeral_factor: simpset -> cterm -> thm option
    13   val eq_cancel_numeral_factor: Proof.context -> cterm -> thm option
    14   val less_cancel_numeral_factor: simpset -> cterm -> thm option
    14   val less_cancel_numeral_factor: Proof.context -> cterm -> thm option
    15   val le_cancel_numeral_factor: simpset -> cterm -> thm option
    15   val le_cancel_numeral_factor: Proof.context -> cterm -> thm option
    16   val div_cancel_numeral_factor: simpset -> cterm -> thm option
    16   val div_cancel_numeral_factor: Proof.context -> cterm -> thm option
    17   val dvd_cancel_numeral_factor: simpset -> cterm -> thm option
    17   val dvd_cancel_numeral_factor: Proof.context -> cterm -> thm option
    18   val eq_cancel_factor: simpset -> cterm -> thm option
    18   val eq_cancel_factor: Proof.context -> cterm -> thm option
    19   val less_cancel_factor: simpset -> cterm -> thm option
    19   val less_cancel_factor: Proof.context -> cterm -> thm option
    20   val le_cancel_factor: simpset -> cterm -> thm option
    20   val le_cancel_factor: Proof.context -> cterm -> thm option
    21   val div_cancel_factor: simpset -> cterm -> thm option
    21   val div_cancel_factor: Proof.context -> cterm -> thm option
    22   val dvd_cancel_factor: simpset -> cterm -> thm option
    22   val dvd_cancel_factor: Proof.context -> cterm -> thm option
    23 end;
    23 end;
    24 
    24 
    25 structure Nat_Numeral_Simprocs : NAT_NUMERAL_SIMPROCS =
    25 structure Nat_Numeral_Simprocs : NAT_NUMERAL_SIMPROCS =
    26 struct
    26 struct
    27 
    27 
    28 (*Maps n to #n for n = 1, 2*)
    28 (*Maps n to #n for n = 1, 2*)
    29 val numeral_syms = [@{thm numeral_1_eq_1} RS sym, @{thm numeral_2_eq_2} RS sym];
    29 val numeral_syms = [@{thm numeral_1_eq_1} RS sym, @{thm numeral_2_eq_2} RS sym];
    30 val numeral_sym_ss = HOL_basic_ss addsimps numeral_syms;
    30 val numeral_sym_ss =
    31 
    31   simpset_of (put_simpset HOL_basic_ss @{context} addsimps numeral_syms);
    32 val rename_numerals = simplify numeral_sym_ss o Thm.transfer @{theory};
       
    33 
    32 
    34 (*Utilities*)
    33 (*Utilities*)
    35 
    34 
    36 fun mk_number 1 = HOLogic.numeral_const HOLogic.natT $ HOLogic.one_const
    35 fun mk_number 1 = HOLogic.numeral_const HOLogic.natT $ HOLogic.one_const
    37   | mk_number n = HOLogic.mk_number HOLogic.natT n;
    36   | mk_number n = HOLogic.mk_number HOLogic.natT n;
   132        else mk_number k :: ts
   131        else mk_number k :: ts
   133      else raise TERM("Nat_Numeral_Simprocs.dest_Sucs_sum", [t])
   132      else raise TERM("Nat_Numeral_Simprocs.dest_Sucs_sum", [t])
   134   end;
   133   end;
   135 
   134 
   136 
   135 
       
   136 (* FIXME !? *)
       
   137 val rename_numerals = simplify (put_simpset numeral_sym_ss @{context}) o Thm.transfer @{theory};
       
   138 
   137 (*Simplify 1*n and n*1 to n*)
   139 (*Simplify 1*n and n*1 to n*)
   138 val add_0s  = map rename_numerals [@{thm Nat.add_0}, @{thm Nat.add_0_right}];
   140 val add_0s  = map rename_numerals [@{thm Nat.add_0}, @{thm Nat.add_0_right}];
   139 val mult_1s = map rename_numerals [@{thm nat_mult_1}, @{thm nat_mult_1_right}];
   141 val mult_1s = map rename_numerals [@{thm nat_mult_1}, @{thm nat_mult_1_right}];
   140 
   142 
   141 (*Final simplification: cancel + and *; replace Numeral0 by 0 and Numeral1 by 1*)
   143 (*Final simplification: cancel + and *; replace Numeral0 by 0 and Numeral1 by 1*)
   160   val mk_coeff = mk_coeff
   162   val mk_coeff = mk_coeff
   161   val dest_coeff = dest_coeff
   163   val dest_coeff = dest_coeff
   162   val find_first_coeff = find_first_coeff []
   164   val find_first_coeff = find_first_coeff []
   163   val trans_tac = Numeral_Simprocs.trans_tac
   165   val trans_tac = Numeral_Simprocs.trans_tac
   164 
   166 
   165   val norm_ss1 = Numeral_Simprocs.num_ss addsimps numeral_syms @ add_0s @ mult_1s @
   167   val norm_ss1 =
   166     [@{thm Suc_eq_plus1_left}] @ @{thms add_ac}
   168     simpset_of (put_simpset Numeral_Simprocs.num_ss @{context}
   167   val norm_ss2 = Numeral_Simprocs.num_ss addsimps bin_simps @ @{thms add_ac} @ @{thms mult_ac}
   169       addsimps numeral_syms @ add_0s @ mult_1s @
   168   fun norm_tac ss = 
   170         [@{thm Suc_eq_plus1_left}] @ @{thms add_ac})
   169     ALLGOALS (simp_tac (Simplifier.inherit_context ss norm_ss1))
   171   val norm_ss2 =
   170     THEN ALLGOALS (simp_tac (Simplifier.inherit_context ss norm_ss2))
   172     simpset_of (put_simpset Numeral_Simprocs.num_ss @{context}
   171 
   173       addsimps bin_simps @ @{thms add_ac} @ @{thms mult_ac})
   172   val numeral_simp_ss = HOL_basic_ss addsimps add_0s @ bin_simps;
   174   fun norm_tac ctxt = 
   173   fun numeral_simp_tac ss = ALLGOALS (simp_tac (Simplifier.inherit_context ss numeral_simp_ss));
   175     ALLGOALS (simp_tac (put_simpset norm_ss1 ctxt))
       
   176     THEN ALLGOALS (simp_tac (put_simpset norm_ss2 ctxt))
       
   177 
       
   178   val numeral_simp_ss =
       
   179     simpset_of (put_simpset HOL_basic_ss @{context}
       
   180       addsimps add_0s @ bin_simps);
       
   181   fun numeral_simp_tac ctxt =
       
   182     ALLGOALS (simp_tac (put_simpset numeral_simp_ss ctxt));
   174   val simplify_meta_eq  = simplify_meta_eq
   183   val simplify_meta_eq  = simplify_meta_eq
   175   val prove_conv = Arith_Data.prove_conv
   184   val prove_conv = Arith_Data.prove_conv
   176 end;
   185 end;
   177 
   186 
   178 structure EqCancelNumerals = CancelNumeralsFun
   187 structure EqCancelNumerals = CancelNumeralsFun
   205   val dest_bal = HOLogic.dest_bin @{const_name Groups.minus} HOLogic.natT
   214   val dest_bal = HOLogic.dest_bin @{const_name Groups.minus} HOLogic.natT
   206   val bal_add1 = @{thm nat_diff_add_eq1} RS trans
   215   val bal_add1 = @{thm nat_diff_add_eq1} RS trans
   207   val bal_add2 = @{thm nat_diff_add_eq2} RS trans
   216   val bal_add2 = @{thm nat_diff_add_eq2} RS trans
   208 );
   217 );
   209 
   218 
   210 fun eq_cancel_numerals ss ct = EqCancelNumerals.proc ss (term_of ct)
   219 fun eq_cancel_numerals ctxt ct = EqCancelNumerals.proc ctxt (term_of ct)
   211 fun less_cancel_numerals ss ct = LessCancelNumerals.proc ss (term_of ct)
   220 fun less_cancel_numerals ctxt ct = LessCancelNumerals.proc ctxt (term_of ct)
   212 fun le_cancel_numerals ss ct = LeCancelNumerals.proc ss (term_of ct)
   221 fun le_cancel_numerals ctxt ct = LeCancelNumerals.proc ctxt (term_of ct)
   213 fun diff_cancel_numerals ss ct = DiffCancelNumerals.proc ss (term_of ct)
   222 fun diff_cancel_numerals ctxt ct = DiffCancelNumerals.proc ctxt (term_of ct)
   214 
   223 
   215 
   224 
   216 (*** Applying CombineNumeralsFun ***)
   225 (*** Applying CombineNumeralsFun ***)
   217 
   226 
   218 structure CombineNumeralsData =
   227 structure CombineNumeralsData =
   226   val dest_coeff = dest_coeff
   235   val dest_coeff = dest_coeff
   227   val left_distrib = @{thm left_add_mult_distrib} RS trans
   236   val left_distrib = @{thm left_add_mult_distrib} RS trans
   228   val prove_conv = Arith_Data.prove_conv_nohyps
   237   val prove_conv = Arith_Data.prove_conv_nohyps
   229   val trans_tac = Numeral_Simprocs.trans_tac
   238   val trans_tac = Numeral_Simprocs.trans_tac
   230 
   239 
   231   val norm_ss1 = Numeral_Simprocs.num_ss addsimps numeral_syms @ add_0s @ mult_1s @ [@{thm Suc_eq_plus1}] @ @{thms add_ac}
   240   val norm_ss1 =
   232   val norm_ss2 = Numeral_Simprocs.num_ss addsimps bin_simps @ @{thms add_ac} @ @{thms mult_ac}
   241     simpset_of (put_simpset Numeral_Simprocs.num_ss @{context}
   233   fun norm_tac ss =
   242       addsimps numeral_syms @ add_0s @ mult_1s @ [@{thm Suc_eq_plus1}] @ @{thms add_ac})
   234     ALLGOALS (simp_tac (Simplifier.inherit_context ss norm_ss1))
   243   val norm_ss2 =
   235     THEN ALLGOALS (simp_tac (Simplifier.inherit_context ss norm_ss2))
   244     simpset_of (put_simpset Numeral_Simprocs.num_ss @{context}
   236 
   245       addsimps bin_simps @ @{thms add_ac} @ @{thms mult_ac})
   237   val numeral_simp_ss = HOL_basic_ss addsimps add_0s @ bin_simps;
   246   fun norm_tac ctxt =
   238   fun numeral_simp_tac ss = ALLGOALS (simp_tac (Simplifier.inherit_context ss numeral_simp_ss))
   247     ALLGOALS (simp_tac (put_simpset norm_ss1 ctxt))
       
   248     THEN ALLGOALS (simp_tac (put_simpset norm_ss2 ctxt))
       
   249 
       
   250   val numeral_simp_ss =
       
   251     simpset_of (put_simpset HOL_basic_ss @{context}
       
   252       addsimps add_0s @ bin_simps);
       
   253   fun numeral_simp_tac ctxt =
       
   254     ALLGOALS (simp_tac (put_simpset numeral_simp_ss ctxt))
   239   val simplify_meta_eq = simplify_meta_eq
   255   val simplify_meta_eq = simplify_meta_eq
   240 end;
   256 end;
   241 
   257 
   242 structure CombineNumerals = CombineNumeralsFun(CombineNumeralsData);
   258 structure CombineNumerals = CombineNumeralsFun(CombineNumeralsData);
   243 
   259 
   244 fun combine_numerals ss ct = CombineNumerals.proc ss (term_of ct)
   260 fun combine_numerals ctxt ct = CombineNumerals.proc ctxt (term_of ct)
   245 
   261 
   246 
   262 
   247 (*** Applying CancelNumeralFactorFun ***)
   263 (*** Applying CancelNumeralFactorFun ***)
   248 
   264 
   249 structure CancelNumeralFactorCommon =
   265 structure CancelNumeralFactorCommon =
   250 struct
   266 struct
   251   val mk_coeff = mk_coeff
   267   val mk_coeff = mk_coeff
   252   val dest_coeff = dest_coeff
   268   val dest_coeff = dest_coeff
   253   val trans_tac = Numeral_Simprocs.trans_tac
   269   val trans_tac = Numeral_Simprocs.trans_tac
   254 
   270 
   255   val norm_ss1 = Numeral_Simprocs.num_ss addsimps
   271   val norm_ss1 =
   256     numeral_syms @ add_0s @ mult_1s @ [@{thm Suc_eq_plus1_left}] @ @{thms add_ac}
   272     simpset_of (put_simpset Numeral_Simprocs.num_ss @{context}
   257   val norm_ss2 = Numeral_Simprocs.num_ss addsimps bin_simps @ @{thms add_ac} @ @{thms mult_ac}
   273       addsimps numeral_syms @ add_0s @ mult_1s @ [@{thm Suc_eq_plus1_left}] @ @{thms add_ac})
   258   fun norm_tac ss =
   274   val norm_ss2 =
   259     ALLGOALS (simp_tac (Simplifier.inherit_context ss norm_ss1))
   275     simpset_of (put_simpset Numeral_Simprocs.num_ss @{context}
   260     THEN ALLGOALS (simp_tac (Simplifier.inherit_context ss norm_ss2))
   276       addsimps bin_simps @ @{thms add_ac} @ @{thms mult_ac})
   261 
   277   fun norm_tac ctxt =
   262   val numeral_simp_ss = HOL_basic_ss addsimps bin_simps
   278     ALLGOALS (simp_tac (put_simpset norm_ss1 ctxt))
   263   fun numeral_simp_tac ss = ALLGOALS (simp_tac (Simplifier.inherit_context ss numeral_simp_ss))
   279     THEN ALLGOALS (simp_tac (put_simpset norm_ss2 ctxt))
       
   280 
       
   281   val numeral_simp_ss =
       
   282     simpset_of (put_simpset HOL_basic_ss @{context} addsimps bin_simps)
       
   283   fun numeral_simp_tac ctxt =
       
   284     ALLGOALS (simp_tac (put_simpset numeral_simp_ss ctxt))
   264   val simplify_meta_eq = simplify_meta_eq
   285   val simplify_meta_eq = simplify_meta_eq
   265   val prove_conv = Arith_Data.prove_conv
   286   val prove_conv = Arith_Data.prove_conv
   266 end;
   287 end;
   267 
   288 
   268 structure DivCancelNumeralFactor = CancelNumeralFactorFun
   289 structure DivCancelNumeralFactor = CancelNumeralFactorFun
   303   val dest_bal = HOLogic.dest_bin @{const_name Orderings.less_eq} HOLogic.natT
   324   val dest_bal = HOLogic.dest_bin @{const_name Orderings.less_eq} HOLogic.natT
   304   val cancel = @{thm nat_mult_le_cancel1} RS trans
   325   val cancel = @{thm nat_mult_le_cancel1} RS trans
   305   val neg_exchanges = true
   326   val neg_exchanges = true
   306 )
   327 )
   307 
   328 
   308 fun eq_cancel_numeral_factor ss ct = EqCancelNumeralFactor.proc ss (term_of ct)
   329 fun eq_cancel_numeral_factor ctxt ct = EqCancelNumeralFactor.proc ctxt (term_of ct)
   309 fun less_cancel_numeral_factor ss ct = LessCancelNumeralFactor.proc ss (term_of ct)
   330 fun less_cancel_numeral_factor ctxt ct = LessCancelNumeralFactor.proc ctxt (term_of ct)
   310 fun le_cancel_numeral_factor ss ct = LeCancelNumeralFactor.proc ss (term_of ct)
   331 fun le_cancel_numeral_factor ctxt ct = LeCancelNumeralFactor.proc ctxt (term_of ct)
   311 fun div_cancel_numeral_factor ss ct = DivCancelNumeralFactor.proc ss (term_of ct)
   332 fun div_cancel_numeral_factor ctxt ct = DivCancelNumeralFactor.proc ctxt (term_of ct)
   312 fun dvd_cancel_numeral_factor ss ct = DvdCancelNumeralFactor.proc ss (term_of ct)
   333 fun dvd_cancel_numeral_factor ctxt ct = DvdCancelNumeralFactor.proc ctxt (term_of ct)
   313 
   334 
   314 
   335 
   315 (*** Applying ExtractCommonTermFun ***)
   336 (*** Applying ExtractCommonTermFun ***)
   316 
   337 
   317 (*this version ALWAYS includes a trailing one*)
   338 (*this version ALWAYS includes a trailing one*)
   327 
   348 
   328 (** Final simplification for the CancelFactor simprocs **)
   349 (** Final simplification for the CancelFactor simprocs **)
   329 val simplify_one = Arith_Data.simplify_meta_eq  
   350 val simplify_one = Arith_Data.simplify_meta_eq  
   330   [@{thm mult_1_left}, @{thm mult_1_right}, @{thm div_1}, @{thm numeral_1_eq_Suc_0}];
   351   [@{thm mult_1_left}, @{thm mult_1_right}, @{thm div_1}, @{thm numeral_1_eq_Suc_0}];
   331 
   352 
   332 fun cancel_simplify_meta_eq ss cancel_th th =
   353 fun cancel_simplify_meta_eq ctxt cancel_th th =
   333     simplify_one ss (([th, cancel_th]) MRS trans);
   354     simplify_one ctxt (([th, cancel_th]) MRS trans);
   334 
   355 
   335 structure CancelFactorCommon =
   356 structure CancelFactorCommon =
   336 struct
   357 struct
   337   val mk_sum = (fn T : typ => long_mk_prod)
   358   val mk_sum = (fn T : typ => long_mk_prod)
   338   val dest_sum = dest_prod
   359   val dest_sum = dest_prod
   339   val mk_coeff = mk_coeff
   360   val mk_coeff = mk_coeff
   340   val dest_coeff = dest_coeff
   361   val dest_coeff = dest_coeff
   341   val find_first = find_first_t []
   362   val find_first = find_first_t []
   342   val trans_tac = Numeral_Simprocs.trans_tac
   363   val trans_tac = Numeral_Simprocs.trans_tac
   343   val norm_ss = HOL_basic_ss addsimps mult_1s @ @{thms mult_ac}
   364   val norm_ss =
   344   fun norm_tac ss = ALLGOALS (simp_tac (Simplifier.inherit_context ss norm_ss))
   365     simpset_of (put_simpset HOL_basic_ss @{context}
       
   366       addsimps mult_1s @ @{thms mult_ac})
       
   367   fun norm_tac ctxt =
       
   368     ALLGOALS (simp_tac (put_simpset norm_ss ctxt))
   345   val simplify_meta_eq  = cancel_simplify_meta_eq
   369   val simplify_meta_eq  = cancel_simplify_meta_eq
   346   fun mk_eq (a, b) = HOLogic.mk_Trueprop (HOLogic.mk_eq (a, b))
   370   fun mk_eq (a, b) = HOLogic.mk_Trueprop (HOLogic.mk_eq (a, b))
   347 end;
   371 end;
   348 
   372 
   349 structure EqCancelFactor = ExtractCommonTermFun
   373 structure EqCancelFactor = ExtractCommonTermFun
   379   val mk_bal   = HOLogic.mk_binrel @{const_name Rings.dvd}
   403   val mk_bal   = HOLogic.mk_binrel @{const_name Rings.dvd}
   380   val dest_bal = HOLogic.dest_bin @{const_name Rings.dvd} HOLogic.natT
   404   val dest_bal = HOLogic.dest_bin @{const_name Rings.dvd} HOLogic.natT
   381   fun simp_conv _ _ = SOME @{thm nat_mult_dvd_cancel_disj}
   405   fun simp_conv _ _ = SOME @{thm nat_mult_dvd_cancel_disj}
   382 );
   406 );
   383 
   407 
   384 fun eq_cancel_factor ss ct = EqCancelFactor.proc ss (term_of ct)
   408 fun eq_cancel_factor ctxt ct = EqCancelFactor.proc ctxt (term_of ct)
   385 fun less_cancel_factor ss ct = LessCancelFactor.proc ss (term_of ct)
   409 fun less_cancel_factor ctxt ct = LessCancelFactor.proc ctxt (term_of ct)
   386 fun le_cancel_factor ss ct = LeCancelFactor.proc ss (term_of ct)
   410 fun le_cancel_factor ctxt ct = LeCancelFactor.proc ctxt (term_of ct)
   387 fun div_cancel_factor ss ct = DivideCancelFactor.proc ss (term_of ct)
   411 fun div_cancel_factor ctxt ct = DivideCancelFactor.proc ctxt (term_of ct)
   388 fun dvd_cancel_factor ss ct = DvdCancelFactor.proc ss (term_of ct)
   412 fun dvd_cancel_factor ctxt ct = DvdCancelFactor.proc ctxt (term_of ct)
   389 
   413 
   390 end;
   414 end;