src/HOL/Integ/int_arith1.ML
changeset 22997 d4f3b015b50b
parent 22578 b0eb5652f210
child 23058 c722004c5a22
equal deleted inserted replaced
22996:5f82c5f8478e 22997:d4f3b015b50b
   101   fun prove_conv_nohyps tacs sg = prove_conv tacs sg [];
   101   fun prove_conv_nohyps tacs sg = prove_conv tacs sg [];
   102 
   102 
   103   fun prep_simproc (name, pats, proc) =
   103   fun prep_simproc (name, pats, proc) =
   104     Simplifier.simproc (the_context()) name pats proc;
   104     Simplifier.simproc (the_context()) name pats proc;
   105 
   105 
   106   fun is_numeral (Const("Numeral.number_of", _) $ w) = true
   106   fun is_numeral (Const(@{const_name Numeral.number_of}, _) $ w) = true
   107     | is_numeral _ = false
   107     | is_numeral _ = false
   108 
   108 
   109   fun simplify_meta_eq f_number_of_eq f_eq =
   109   fun simplify_meta_eq f_number_of_eq f_eq =
   110       mk_meta_eq ([f_eq, f_number_of_eq] MRS trans)
   110       mk_meta_eq ([f_eq, f_number_of_eq] MRS trans)
   111 
   111 
   116 
   116 
   117   (*reorientation simplification procedure: reorients (polymorphic) 
   117   (*reorientation simplification procedure: reorients (polymorphic) 
   118     0 = x, 1 = x, nnn = x provided x isn't 0, 1 or a numeral.*)
   118     0 = x, 1 = x, nnn = x provided x isn't 0, 1 or a numeral.*)
   119   fun reorient_proc sg _ (_ $ t $ u) =
   119   fun reorient_proc sg _ (_ $ t $ u) =
   120     case u of
   120     case u of
   121 	Const("HOL.zero", _) => NONE
   121 	Const(@{const_name HOL.zero}, _) => NONE
   122       | Const("HOL.one", _) => NONE
   122       | Const(@{const_name HOL.one}, _) => NONE
   123       | Const("Numeral.number_of", _) $ _ => NONE
   123       | Const(@{const_name Numeral.number_of}, _) $ _ => NONE
   124       | _ => SOME (case t of
   124       | _ => SOME (case t of
   125 		  Const("HOL.zero", _) => meta_zero_reorient
   125 		  Const(@{const_name HOL.zero}, _) => meta_zero_reorient
   126 		| Const("HOL.one", _) => meta_one_reorient
   126 		| Const(@{const_name HOL.one}, _) => meta_one_reorient
   127 		| Const("Numeral.number_of", _) $ _ => meta_number_of_reorient)
   127 		| Const(@{const_name Numeral.number_of}, _) $ _ => meta_number_of_reorient)
   128 
   128 
   129   val reorient_simproc = 
   129   val reorient_simproc = 
   130       prep_simproc ("reorient_simproc", ["0=x", "1=x", "number_of w = x"], reorient_proc)
   130       prep_simproc ("reorient_simproc", ["0=x", "1=x", "number_of w = x"], reorient_proc)
   131 
   131 
   132   end;
   132   end;
   156 local open Term 
   156 local open Term 
   157 in 
   157 in 
   158 fun numterm_ord (Abs (_, T, t), Abs(_, U, u)) =
   158 fun numterm_ord (Abs (_, T, t), Abs(_, U, u)) =
   159       (case numterm_ord (t, u) of EQUAL => typ_ord (T, U) | ord => ord)
   159       (case numterm_ord (t, u) of EQUAL => typ_ord (T, U) | ord => ord)
   160   | numterm_ord
   160   | numterm_ord
   161      (Const("Numeral.number_of", _) $ v, Const("Numeral.number_of", _) $ w) =
   161      (Const(@{const_name Numeral.number_of}, _) $ v, Const(@{const_name Numeral.number_of}, _) $ w) =
   162      num_ord (HOLogic.dest_numeral v, HOLogic.dest_numeral w)
   162      num_ord (HOLogic.dest_numeral v, HOLogic.dest_numeral w)
   163   | numterm_ord (Const("Numeral.number_of", _) $ _, _) = LESS
   163   | numterm_ord (Const(@{const_name Numeral.number_of}, _) $ _, _) = LESS
   164   | numterm_ord (_, Const("Numeral.number_of", _) $ _) = GREATER
   164   | numterm_ord (_, Const(@{const_name Numeral.number_of}, _) $ _) = GREATER
   165   | numterm_ord (t, u) =
   165   | numterm_ord (t, u) =
   166       (case int_ord (size_of_term t, size_of_term u) of
   166       (case int_ord (size_of_term t, size_of_term u) of
   167         EQUAL =>
   167         EQUAL =>
   168           let val (f, ts) = strip_comb t and (g, us) = strip_comb u in
   168           let val (f, ts) = strip_comb t and (g, us) = strip_comb u in
   169             (case hd_ord (f, g) of EQUAL => numterms_ord (ts, us) | ord => ord)
   169             (case hd_ord (f, g) of EQUAL => numterms_ord (ts, us) | ord => ord)
   185 fun find_first_numeral past (t::terms) =
   185 fun find_first_numeral past (t::terms) =
   186         ((snd (HOLogic.dest_number t), rev past @ terms)
   186         ((snd (HOLogic.dest_number t), rev past @ terms)
   187          handle TERM _ => find_first_numeral (t::past) terms)
   187          handle TERM _ => find_first_numeral (t::past) terms)
   188   | find_first_numeral past [] = raise TERM("find_first_numeral", []);
   188   | find_first_numeral past [] = raise TERM("find_first_numeral", []);
   189 
   189 
   190 val mk_plus = HOLogic.mk_binop "HOL.plus";
   190 val mk_plus = HOLogic.mk_binop @{const_name HOL.plus};
   191 
   191 
   192 fun mk_minus t = 
   192 fun mk_minus t = 
   193   let val T = Term.fastype_of t
   193   let val T = Term.fastype_of t
   194   in Const ("HOL.uminus", T --> T) $ t
   194   in Const (@{const_name HOL.uminus}, T --> T) $ t
   195   end;
   195   end;
   196 
   196 
   197 (*Thus mk_sum[t] yields t+0; longer sums don't have a trailing zero*)
   197 (*Thus mk_sum[t] yields t+0; longer sums don't have a trailing zero*)
   198 fun mk_sum T []        = mk_number T 0
   198 fun mk_sum T []        = mk_number T 0
   199   | mk_sum T [t,u]     = mk_plus (t, u)
   199   | mk_sum T [t,u]     = mk_plus (t, u)
   201 
   201 
   202 (*this version ALWAYS includes a trailing zero*)
   202 (*this version ALWAYS includes a trailing zero*)
   203 fun long_mk_sum T []        = mk_number T 0
   203 fun long_mk_sum T []        = mk_number T 0
   204   | long_mk_sum T (t :: ts) = mk_plus (t, mk_sum T ts);
   204   | long_mk_sum T (t :: ts) = mk_plus (t, mk_sum T ts);
   205 
   205 
   206 val dest_plus = HOLogic.dest_bin "HOL.plus" Term.dummyT;
   206 val dest_plus = HOLogic.dest_bin @{const_name HOL.plus} Term.dummyT;
   207 
   207 
   208 (*decompose additions AND subtractions as a sum*)
   208 (*decompose additions AND subtractions as a sum*)
   209 fun dest_summing (pos, Const ("HOL.plus", _) $ t $ u, ts) =
   209 fun dest_summing (pos, Const (@{const_name HOL.plus}, _) $ t $ u, ts) =
   210         dest_summing (pos, t, dest_summing (pos, u, ts))
   210         dest_summing (pos, t, dest_summing (pos, u, ts))
   211   | dest_summing (pos, Const ("HOL.minus", _) $ t $ u, ts) =
   211   | dest_summing (pos, Const (@{const_name HOL.minus}, _) $ t $ u, ts) =
   212         dest_summing (pos, t, dest_summing (not pos, u, ts))
   212         dest_summing (pos, t, dest_summing (not pos, u, ts))
   213   | dest_summing (pos, t, ts) =
   213   | dest_summing (pos, t, ts) =
   214         if pos then t::ts else mk_minus t :: ts;
   214         if pos then t::ts else mk_minus t :: ts;
   215 
   215 
   216 fun dest_sum t = dest_summing (true, t, []);
   216 fun dest_sum t = dest_summing (true, t, []);
   217 
   217 
   218 val mk_diff = HOLogic.mk_binop "HOL.minus";
   218 val mk_diff = HOLogic.mk_binop @{const_name HOL.minus};
   219 val dest_diff = HOLogic.dest_bin "HOL.minus" Term.dummyT;
   219 val dest_diff = HOLogic.dest_bin @{const_name HOL.minus} Term.dummyT;
   220 
   220 
   221 val mk_times = HOLogic.mk_binop "HOL.times";
   221 val mk_times = HOLogic.mk_binop @{const_name HOL.times};
   222 
   222 
   223 fun mk_prod T = 
   223 fun mk_prod T = 
   224   let val one = mk_number T 1
   224   let val one = mk_number T 1
   225   fun mk [] = one
   225   fun mk [] = one
   226     | mk [t] = t
   226     | mk [t] = t
   229 
   229 
   230 (*This version ALWAYS includes a trailing one*)
   230 (*This version ALWAYS includes a trailing one*)
   231 fun long_mk_prod T []        = mk_number T 1
   231 fun long_mk_prod T []        = mk_number T 1
   232   | long_mk_prod T (t :: ts) = mk_times (t, mk_prod T ts);
   232   | long_mk_prod T (t :: ts) = mk_times (t, mk_prod T ts);
   233 
   233 
   234 val dest_times = HOLogic.dest_bin "HOL.times" Term.dummyT;
   234 val dest_times = HOLogic.dest_bin @{const_name HOL.times} Term.dummyT;
   235 
   235 
   236 fun dest_prod t =
   236 fun dest_prod t =
   237       let val (t,u) = dest_times t
   237       let val (t,u) = dest_times t
   238       in  dest_prod t @ dest_prod u  end
   238       in  dest_prod t @ dest_prod u  end
   239       handle TERM _ => [t];
   239       handle TERM _ => [t];
   240 
   240 
   241 (*DON'T do the obvious simplifications; that would create special cases*)
   241 (*DON'T do the obvious simplifications; that would create special cases*)
   242 fun mk_coeff (k, t) = mk_times (mk_number (Term.fastype_of t) k, t);
   242 fun mk_coeff (k, t) = mk_times (mk_number (Term.fastype_of t) k, t);
   243 
   243 
   244 (*Express t as a product of (possibly) a numeral with other sorted terms*)
   244 (*Express t as a product of (possibly) a numeral with other sorted terms*)
   245 fun dest_coeff sign (Const ("HOL.uminus", _) $ t) = dest_coeff (~sign) t
   245 fun dest_coeff sign (Const (@{const_name HOL.uminus}, _) $ t) = dest_coeff (~sign) t
   246   | dest_coeff sign t =
   246   | dest_coeff sign t =
   247     let val ts = sort Term.term_ord (dest_prod t)
   247     let val ts = sort Term.term_ord (dest_prod t)
   248         val (n, ts') = find_first_numeral [] ts
   248         val (n, ts') = find_first_numeral [] ts
   249                           handle TERM _ => (1, ts)
   249                           handle TERM _ => (1, ts)
   250     in (sign*n, mk_prod (Term.fastype_of t) ts') end;
   250     in (sign*n, mk_prod (Term.fastype_of t) ts') end;
   336 );
   336 );
   337 
   337 
   338 structure LessCancelNumerals = CancelNumeralsFun
   338 structure LessCancelNumerals = CancelNumeralsFun
   339  (open CancelNumeralsCommon
   339  (open CancelNumeralsCommon
   340   val prove_conv = Int_Numeral_Base_Simprocs.prove_conv
   340   val prove_conv = Int_Numeral_Base_Simprocs.prove_conv
   341   val mk_bal   = HOLogic.mk_binrel "Orderings.less"
   341   val mk_bal   = HOLogic.mk_binrel @{const_name Orderings.less}
   342   val dest_bal = HOLogic.dest_bin "Orderings.less" Term.dummyT
   342   val dest_bal = HOLogic.dest_bin @{const_name Orderings.less} Term.dummyT
   343   val bal_add1 = less_add_iff1 RS trans
   343   val bal_add1 = less_add_iff1 RS trans
   344   val bal_add2 = less_add_iff2 RS trans
   344   val bal_add2 = less_add_iff2 RS trans
   345 );
   345 );
   346 
   346 
   347 structure LeCancelNumerals = CancelNumeralsFun
   347 structure LeCancelNumerals = CancelNumeralsFun
   348  (open CancelNumeralsCommon
   348  (open CancelNumeralsCommon
   349   val prove_conv = Int_Numeral_Base_Simprocs.prove_conv
   349   val prove_conv = Int_Numeral_Base_Simprocs.prove_conv
   350   val mk_bal   = HOLogic.mk_binrel "Orderings.less_eq"
   350   val mk_bal   = HOLogic.mk_binrel @{const_name Orderings.less_eq}
   351   val dest_bal = HOLogic.dest_bin "Orderings.less_eq" Term.dummyT
   351   val dest_bal = HOLogic.dest_bin @{const_name Orderings.less_eq} Term.dummyT
   352   val bal_add1 = le_add_iff1 RS trans
   352   val bal_add1 = le_add_iff1 RS trans
   353   val bal_add2 = le_add_iff2 RS trans
   353   val bal_add2 = le_add_iff2 RS trans
   354 );
   354 );
   355 
   355 
   356 val cancel_numerals =
   356 val cancel_numerals =