RFC 0369: num-reform

libs (arithmetic)

• Start Date: 2014-09-16
• RFC PR: rust-lang/rfcs#369
• Rust Issue: rust-lang/rust#18640

Summary

This RFC is preparation for API stabilization for the std::num module. The proposal is to finish the simplification efforts started in @bjz's reversal of the numerics hierarchy.

Broadly, the proposal is to collapse the remaining numeric hierarchy in std::num, and to provide only limited support for generic programming (roughly, only over primitive numeric types that vary based on size). Traits giving detailed numeric hierarchy can and should be provided separately through the Cargo ecosystem.

Thus, this RFC proposes to flatten or remove most of the traits currently provided by std::num, and generally to simplify the module as much as possible in preparation for API stabilization.

Motivation

History

Starting in early 2013, there was an effort to design a comprehensive "numeric hierarchy" for Rust: a collection of traits classifying a wide variety of numbers and other algebraic objects. The intent was to allow highly-generic code to be written for algebraic structures and then instantiated to particular types.

This hierarchy covered structures like bigints, but also primitive integer and float types. It was an enormous and long-running community effort.

Later, it was recognized that building such a hierarchy within libstd was misguided:

@bjz The API that resulted from #4819 attempted, like Haskell, to blend both the primitive numerics and higher level mathematical concepts into one API. This resulted in an ugly hybrid where neither goal was adequately met. I think the libstd should have a strong focus on implementing fundamental operations for the base numeric types, but no more. Leave the higher level concepts to libnum or future community projects.

The std::num module has thus been slowly migrating away from a large trait hierarchy toward a simpler one providing just APIs for primitive data types: this is @bjz's reversal of the numerics hierarchy.

Along side this effort, there are already external numerics packages like @bjz's num-rs.

But we're not finished yet.

The current state of affairs

The std::num module still contains quite a few traits that subdivide out various features of numbers:

pub trait Zero: Add<Self, Self> {
    fn zero() -> Self;
    fn is_zero(&self) -> bool;
}

pub trait One: Mul<Self, Self> {
    fn one() -> Self;
}

pub trait Signed: Num + Neg<Self> {
    fn abs(&self) -> Self;
    fn abs_sub(&self, other: &Self) -> Self;
    fn signum(&self) -> Self;
    fn is_positive(&self) -> bool;
    fn is_negative(&self) -> bool;
}

pub trait Unsigned: Num {}

pub trait Bounded {
    fn min_value() -> Self;
    fn max_value() -> Self;
}

pub trait Primitive: Copy + Clone + Num + NumCast + PartialOrd + Bounded {}

pub trait Num: PartialEq + Zero + One + Neg<Self> + Add<Self,Self> + Sub<Self,Self>
             + Mul<Self,Self> + Div<Self,Self> + Rem<Self,Self> {}

pub trait Int: Primitive + CheckedAdd + CheckedSub + CheckedMul + CheckedDiv
             + Bounded + Not<Self> + BitAnd<Self,Self> + BitOr<Self,Self>
             + BitXor<Self,Self> + Shl<uint,Self> + Shr<uint,Self> {
    fn count_ones(self) -> uint;
    fn count_zeros(self) -> uint { ... }
    fn leading_zeros(self) -> uint;
    fn trailing_zeros(self) -> uint;
    fn rotate_left(self, n: uint) -> Self;
    fn rotate_right(self, n: uint) -> Self;
    fn swap_bytes(self) -> Self;
    fn from_be(x: Self) -> Self { ... }
    fn from_le(x: Self) -> Self { ... }
    fn to_be(self) -> Self { ... }
    fn to_le(self) -> Self { ... }
}

pub trait FromPrimitive {
    fn from_i64(n: i64) -> Option<Self>;
    fn from_u64(n: u64) -> Option<Self>;

    // many additional defaulted methods
    // ...
}

pub trait ToPrimitive {
    fn to_i64(&self) -> Option<i64>;
    fn to_u64(&self) -> Option<u64>;

    // many additional defaulted methods
    // ...
}

pub trait NumCast: ToPrimitive {
    fn from<T: ToPrimitive>(n: T) -> Option<Self>;
}

pub trait Saturating {
    fn saturating_add(self, v: Self) -> Self;
    fn saturating_sub(self, v: Self) -> Self;
}

pub trait CheckedAdd: Add<Self, Self> {
    fn checked_add(&self, v: &Self) -> Option<Self>;
}

pub trait CheckedSub: Sub<Self, Self> {
    fn checked_sub(&self, v: &Self) -> Option<Self>;
}

pub trait CheckedMul: Mul<Self, Self> {
    fn checked_mul(&self, v: &Self) -> Option<Self>;
}

pub trait CheckedDiv: Div<Self, Self> {
    fn checked_div(&self, v: &Self) -> Option<Self>;
}

pub trait Float: Signed + Primitive {
    // a huge collection of static functions (for constants) and methods
    ...
}

pub trait FloatMath: Float {
    // an additional collection of methods
}

The Primitive traits are intended primarily to support a mechanism, #[deriving(FromPrimitive)], that makes it easy to provide conversions from numeric types to C-like enums.

The Saturating and Checked traits provide operations that provide special handling for overflow and other numeric errors.

Almost all of these traits are currently included in the prelude.

In addition to these traits, the std::num module includes a couple dozen free functions, most of which duplicate methods available though traits.

Where we want to go: a summary

The goal of this RFC is to refactor the std::num hierarchy with the following goals in mind:

• Simplicity.

• Limited generic programming: being able to work generically over the natural classes of primitive numeric types that vary only by size. There should be enough abstraction to support porting strconv, the generic string/number conversion code used in std.

• Minimizing dependencies for libcore. For example, it should not require cmath.

• Future-proofing for external numerics packages. The Cargo ecosystem should ultimately provide choices of sophisticated numeric hierarchies, and std::num should not get in the way.

Detailed design

Overview: the new hierarchy

This RFC proposes to collapse the trait hierarchy in std::num to just the following traits:

• Int, implemented by all primitive integer types (u8 - u64, i8-i64)
  • UnsignedInt, implemented by u8 - u64
• Signed, implemented by all signed primitive numeric types (i8-i64, f32-f64)
• Float, implemented by f32 and f64
  • FloatMath, implemented by f32 and f64, which provides functionality from cmath

These traits inherit from all applicable overloaded operator traits (from core::ops). They suffice for generic programming over several basic categories of primitive numeric types.

As designed, these traits include a certain amount of redundancy between Int and Float. The Alternatives section shows how this could be factored out into a separate Num trait. But doing so suggests a level of generic programming that these traits aren't intended to support.

The main reason to pull out Signed into its own trait is so that it can be added to the prelude. (Further discussion below.)

Detailed definitions

Below is the full definition of these traits. The functionality remains largely as it is today, just organized into fewer traits:

pub trait Int: Copy + Clone + PartialOrd + PartialEq
             + Add<Self,Self> + Sub<Self,Self>
             + Mul<Self,Self> + Div<Self,Self> + Rem<Self,Self>
             + Not<Self> + BitAnd<Self,Self> + BitOr<Self,Self>
             + BitXor<Self,Self> + Shl<uint,Self> + Shr<uint,Self>
{
    // Constants
    fn zero() -> Self;  // These should be associated constants when those are available
    fn one() -> Self;
    fn min_value() -> Self;
    fn max_value() -> Self;

    // Deprecated:
    // fn is_zero(&self) -> bool;

    // Bit twiddling
    fn count_ones(self) -> uint;
    fn count_zeros(self) -> uint { ... }
    fn leading_zeros(self) -> uint;
    fn trailing_zeros(self) -> uint;
    fn rotate_left(self, n: uint) -> Self;
    fn rotate_right(self, n: uint) -> Self;
    fn swap_bytes(self) -> Self;
    fn from_be(x: Self) -> Self { ... }
    fn from_le(x: Self) -> Self { ... }
    fn to_be(self) -> Self { ... }
    fn to_le(self) -> Self { ... }

    // Checked arithmetic
    fn checked_add(self, v: Self) -> Option<Self>;
    fn checked_sub(self, v: Self) -> Option<Self>;
    fn checked_mul(self, v: Self) -> Option<Self>;
    fn checked_div(self, v: Self) -> Option<Self>;
    fn saturating_add(self, v: Self) -> Self;
    fn saturating_sub(self, v: Self) -> Self;
}

pub trait UnsignedInt: Int {
    fn is_power_of_two(self) -> bool;
    fn checked_next_power_of_two(self) -> Option<Self>;
    fn next_power_of_two(self) -> Self;
}

pub trait Signed: Neg<Self> {
    fn abs(&self) -> Self;
    fn signum(&self) -> Self;
    fn is_positive(&self) -> bool;
    fn is_negative(&self) -> bool;

    // Deprecated:
    // fn abs_sub(&self, other: &Self) -> Self;
}

pub trait Float: Copy + Clone + PartialOrd + PartialEq + Signed
               + Add<Self,Self> + Sub<Self,Self>
               + Mul<Self,Self> + Div<Self,Self> + Rem<Self,Self>
{
    // Constants
    fn zero() -> Self;  // These should be associated constants when those are available
    fn one() -> Self;
    fn min_value() -> Self;
    fn max_value() -> Self;

    // Classification and decomposition
    fn is_nan(self) -> bool;
    fn is_infinite(self) -> bool;
    fn is_finite(self) -> bool;
    fn is_normal(self) -> bool;
    fn classify(self) -> FPCategory;
    fn integer_decode(self) -> (u64, i16, i8);

    // Float intrinsics
    fn floor(self) -> Self;
    fn ceil(self) -> Self;
    fn round(self) -> Self;
    fn trunc(self) -> Self;
    fn mul_add(self, a: Self, b: Self) -> Self;
    fn sqrt(self) -> Self;
    fn powi(self, n: i32) -> Self;
    fn powf(self, n: Self) -> Self;
    fn exp(self) -> Self;
    fn exp2(self) -> Self;
    fn ln(self) -> Self;
    fn log2(self) -> Self;
    fn log10(self) -> Self;

    // Conveniences
    fn fract(self) -> Self;
    fn recip(self) -> Self;
    fn rsqrt(self) -> Self;
    fn to_degrees(self) -> Self;
    fn to_radians(self) -> Self;
    fn log(self, base: Self) -> Self;
}

// This lives directly in `std::num`, not `core::num`, since it requires `cmath`
pub trait FloatMath: Float {
    // Exactly the methods defined in today's version
}

Float constants, float math, and cmath

This RFC proposes to:

• Remove all float constants from the Float trait. These constants are available directly from the f32 and f64 modules, and are not really useful for the kind of generic programming these new traits are intended to allow.

• Continue providing various cmath functions as methods in the FloatMath trait. Putting this in a separate trait means that libstd depends on cmath but libcore does not.

Free functions

All of the free functions defined in std::num are deprecated.

The prelude

The prelude will only include the Signed trait, as the operations it provides are widely expected to be available when they apply.

The reason for removing the rest of the traits is two-fold:

• The remaining operations are relatively uncommon. Note that various overloaded operators, like +, work regardless of this choice. Those doing intensive work with e.g. floats would only need to import Float and FloatMath.

• Keeping this functionality out of the prelude means that the names of methods and associated items remain available for external numerics libraries in the Cargo ecosystem.

strconv, FromStr, ToStr, FromStrRadix, ToStrRadix

Currently, traits for converting from &str and to String are both included, in their own modules, in libstd. This is largely due to the desire to provide impls for numeric types, which in turn relies on std::num::strconv.

This RFC proposes to:

• Move the FromStr trait into core::str.
• Rename the ToStr trait to ToString, and move it to collections::string.
• Break up and revise std::num::strconv into separate, private modules that provide the needed functionality for the from_str and to_string methods. (Some of this functionality has already migrated to fmt and been deprecated in strconv.)
• Move the FromStrRadix into core::num.
• Remove ToStrRadix, which is already deprecated in favor of fmt.

FromPrimitive and friends

Ideally, the FromPrimitive, ToPrimitive, Primitive, NumCast traits would all be removed in favor of a more principled way of working with C-like enums. However, such a replacement is outside of the scope of this RFC, so these traits are left (as #[experimental]) for now. A follow-up RFC proposing a better solution should appear soon.

In the meantime, see this proposal and the discussion on this issue about Ordinal for the rough direction forward.

Drawbacks

This RFC somewhat reduces the potential for writing generic numeric code with std::num traits. This is intentional, however: the new design represents "just enough" generics to cover differently-sized built-in types, without any attempt at general algebraic abstraction.

Alternatives

The status quo is clearly not ideal, and as explained above there was a long attempt at providing a more complete numeric hierarchy in std. So some collapse of the hierarchy seems desirable.

That said, there are other possible factorings. We could introduce the following Num trait to factor out commonalities between Int and Float:

pub trait Num: Copy + Clone + PartialOrd + PartialEq
             + Add<Self,Self> + Sub<Self,Self>
             + Mul<Self,Self> + Div<Self,Self> + Rem<Self,Self>
{
    fn zero() -> Self;  // These should be associated constants when those are available
    fn one() -> Self;
    fn min_value() -> Self;
    fn max_value() -> Self;
}

However, it's not clear whether this factoring is worth having a more complex hierarchy, especially because the traits are not intended for generic programming at that level (and generic programming across integer and floating-point types is likely to be extremely rare)

The signed and unsigned operations could be offered on more types, allowing removal of more traits but a less clear-cut semantics.

Unresolved questions

This RFC does not propose a replacement for #[deriving(FromPrimitive)], leaving the relevant traits in limbo status. (See this proposal and the discussion on this issue about Ordinal for the rough direction forward.)