Some more revision of {P,N,Z}Arith + bitwise ops in Ndigits

Initial plan was only to add shiftl/shiftr/land/... to N and
other number type, this is only partly done, but this work has
diverged into a big reorganisation and improvement session
of PArith,NArith,ZArith.

Bool/Bool: add lemmas orb_diag (a||a = a) and andb_diag (a&&a = a)

PArith/BinPos:
 - added a power function Ppow
 - iterator iter_pos moved from Zmisc to here + some lemmas
 - added Psize_pos, which is 1+log2, used to define Nlog2/Zlog2
 - more lemmas on Pcompare and succ/+/* and order, allow
   to simplify a lot some old proofs elsewhere.
 - new/revised results on Pminus (including some direct proof of
   stuff from Pnat)

PArith/Pnat:
 - more direct proofs (limit the need of stuff about Pmult_nat).
 - provide nicer names for some lemmas (eg. Pplus_plus instead of
   nat_of_P_plus_morphism), compatibility notations provided.
 - kill some too-specific lemmas unused in stdlib + contribs

NArith/BinNat:
 - N_of_nat, nat_of_N moved from Nnat to here.
 - a lemma relating Npred and Nminus
 - revised definitions and specification proofs of Npow and Nlog2

NArith/Nnat:
 - shorter proofs.
 - stuff about Z_of_N is moved to Znat. This way, NArith is
   entirely independent from ZArith.

NArith/Ndigits:
 - added bitwise operations Nand Nor Ndiff Nshiftl Nshiftr
 - revised proofs about Nxor, still using functional bit stream
 - use the same approach to prove properties of Nand Nor Ndiff

ZArith/BinInt: huge simplification of Zplus_assoc + cosmetic stuff

ZArith/Zcompare: nicer proofs of ugly things like Zcompare_Zplus_compat

ZArith/Znat: some nicer proofs and names, received stuff about Z_of_N

ZArith/Zmisc: almost empty new, only contain stuff about badly-named
 iter. Should be reformed more someday.

ZArith/Zlog_def: Zlog2 is now based on Psize_pos, this factorizes
 proofs and avoid slowdown due to adding 1 in Z instead of in positive

Zarith/Zpow_def: Zpower_opt is renamed more modestly Zpower_alt
 as long as I dont't know why it's slower on powers of two.

Elsewhere: propagate new names + some nicer proofs

NB: Impact on compatibility is probably non-zero, but should be
really moderate. We'll see on contribs, but a few Require here
and there might be necessary.

git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@13651 85f007b7-540e-0410-9357-904b9bb8a0f7

1 files changed, 0 insertions, 56 deletions

diff --git a/theories/ZArith/Zmisc.v b/theories/ZArith/Zmisc.v
index b4bd470ab..f6b038cbd 100644
--- a/theories/ZArith/Zmisc.v
+++ b/theories/ZArith/Zmisc.v
@@ -18,13 +18,6 @@ Open Local Scope Z_scope.
 
 (** [n]th iteration of the function [f] *)
 
-Fixpoint iter_pos (n:positive) (A:Type) (f:A -> A) (x:A) : A :=
-  match n with
-    | xH => f x
-    | xO n' => iter_pos n' A f (iter_pos n' A f x)
-    | xI n' => f (iter_pos n' A f (iter_pos n' A f x))
-  end.
-
 Definition iter (n:Z) (A:Type) (f:A -> A) (x:A) :=
   match n with
     | Z0 => x
@@ -32,58 +25,9 @@ Definition iter (n:Z) (A:Type) (f:A -> A) (x:A) :=
     | Zneg p => x
   end.
 
-Theorem iter_nat_of_P :
-  forall (p:positive) (A:Type) (f:A -> A) (x:A),
-    iter_pos p A f x = iter_nat (nat_of_P p) A f x.
-Proof.
-  intro n; induction n as [p H| p H| ];
-    [ intros; simpl in |- *; rewrite (H A f x);
-      rewrite (H A f (iter_nat (nat_of_P p) A f x));
-	rewrite (ZL6 p); symmetry  in |- *; apply f_equal with (f := f);
-	  apply iter_nat_plus
-      | intros; unfold nat_of_P in |- *; simpl in |- *; rewrite (H A f x);
-	rewrite (H A f (iter_nat (nat_of_P p) A f x));
-	  rewrite (ZL6 p); symmetry  in |- *; apply iter_nat_plus
-      | simpl in |- *; auto with arith ].
-Qed.
-
 Lemma iter_nat_of_Z : forall n A f x, 0 <= n ->
   iter n A f x = iter_nat (Zabs_nat n) A f x.
 intros n A f x; case n; auto.
 intros p _; unfold iter, Zabs_nat; apply iter_nat_of_P.
 intros p abs; case abs; trivial.
 Qed.
-
-Theorem iter_pos_plus :
-  forall (p q:positive) (A:Type) (f:A -> A) (x:A),
-    iter_pos (p + q) A f x = iter_pos p A f (iter_pos q A f x).
-Proof.
-  intros n m; intros.
-  rewrite (iter_nat_of_P m A f x).
-  rewrite (iter_nat_of_P n A f (iter_nat (nat_of_P m) A f x)).
-  rewrite (iter_nat_of_P (n + m) A f x).
-  rewrite (nat_of_P_plus_morphism n m).
-  apply iter_nat_plus.
-Qed.
-
-(** Preservation of invariants : if [f : A->A] preserves the invariant [Inv],
-    then the iterates of [f] also preserve it. *)
-
-Theorem iter_nat_invariant :
-  forall (n:nat) (A:Type) (f:A -> A) (Inv:A -> Prop),
-    (forall x:A, Inv x -> Inv (f x)) ->
-    forall x:A, Inv x -> Inv (iter_nat n A f x).
-Proof.
-  simple induction n; intros;
-    [ trivial with arith
-      | simpl in |- *; apply H0 with (x := iter_nat n0 A f x); apply H;
-	trivial with arith ].
-Qed.
-
-Theorem iter_pos_invariant :
-  forall (p:positive) (A:Type) (f:A -> A) (Inv:A -> Prop),
-    (forall x:A, Inv x -> Inv (f x)) ->
-    forall x:A, Inv x -> Inv (iter_pos p A f x).
-Proof.
-  intros; rewrite iter_nat_of_P; apply iter_nat_invariant; trivial with arith.
-Qed.