Generic Code for Math Operations

[migueldeicaza]

Generic Code for Math Operations

Today C# does not allow code to be generic over math operations, so there is no way of expressing in generic code things like computing the average of a numeric type. Ideally, we would like to be able to write a generic function Average that can work on any numeric data type:

T Average<T> (T [] elements) where T: IReal
{
    T sum = T.Zero;
    foreach (var e in elements) {
        sum += e;
    }
    return sum / elements.Length
}

It would be desirable to express that algorithm and have this work for double, float, int, decimal and even newer data types like half-floats, or SIMD-accelerated types.

In the example above, there are three capabilities missing: the initialization of the sum to a zero, the addition of numbers of the given type and the division of the number. And of course, there is no such thing as the IReal interface.

F# has a ways of achieving the above solution, and we can draw some inspiration from this, to bring it to C#, and also draw inspiration from the work being done for Swift Numerics.

To address this problem, we want to introduce support to interfaces to declare static members that are a part of the interface contract, requiring that types that implement the interface should expose those as static members. While the word static would have been ideal for this, recently the word static was used in interfaces to declare helper methods. We will differentiate static helper members from static contract members using the abstract modifier.

For the required elements above, this would allow us to author some interfaces, like this:

interface IAdditiveNumeric<TSelf> where TSelf: IAdditiveNumber<TSelf> {
  abstract static TSelf Zero { get; }
  abstract static operator TSelf + (TSelf left, TSelf right);
  abstract static operator TSelf - (TSelf left, TSelf right);
}

interface INumeric {
  abstract static operator TSelf * (TSelf left, TSelf right);
  abstract static operator TSelf / (TSelf left, TSelf right);
}

We would then make our existing data types in .NET conform to this new set of interfaces:

public struct Double : ..., IAdditiveNumeric<Double>, INumeric {
    public static Double Zero => 0.0;
    public static operator double + (double left, double right) => left + right;
    public static operator double / (double left, double right) => left / right;
}

Behind the scenes, the JIT compiler would need to recognize the calls to those operators and replace those with the equivalent JIT operation. For example, a simple generic Add method:

T Add<T> (T left, T right) where T: IAdditiveNumeric<T>
{
    return left + right;
}

Would produce IL that looks like this:

 .method private hidebysig 
  instance default void Add<(class IAdditiveNumeric) T> (!!T v, !!T x)  cil managed
ldarg.0
ldarg.1
call class IAdditiveNumeric`1<!!T>::op_Addition(!0, !0)
ret

When the runtime finds this code for the built-in data types, it would treat that call to the op_Addition operator the same way that it would have treated the add opcode in that scenario. For other types, it would call the method.

Additionally, it would be desirable to write generic code for elementary functions, which means that we would like the types to implement those functions (Sin, Cos, Tan, Exp, Atan2 and so on).

This would let us express code like this:

// This is a generic implementation of the sigmoid function
T Sigmoid<T> (T x) where T: IReal 
{
    return 1 / (1 + T.Exp (x))
}

Where the IReal interface would be:

interface IReal<T> : INumeric<T>, IAdditiveNumeric<T> where T: IAdditiveNumeric<T> {
  abstract static T Sin (T value);
  abstract static T Cos (T value);
  abstract static T Tan (T value);
  abstract static T Exp (T value);
}

An alternative is to not require static methods in the classes, but rather surface these as instance methods, so rather than surfacing Double.Sin (0.23) developers could write (0.23).Sin().

In either case, our core types would surface those methods. This means that Double would now have a method Sin for example in addition to the existing System.Math.Sin method that is already present.

With this capability, new data types can be introduced, and they can independently choose to conform to the new numeric interfaces, allowing those types to be plugged into existing codebases.

Conversion Operators

Just like it is possible to define operators in interfaces, we would allow conversion operators to be declared on those interfaces. This would allow for implicit conversions in the code.

At the beginning of this section, I used T.Zero in generic code to represent the zero value. With this solution, we would not have to use this constant of limited value, but we could use any constants that we desire, or initialize from other values.

This would allow code like this to be written

T IntegrateErdosAt (T start, Func<T,T> cb, T step) where T : IReal
{
    T erdosBow = 1.60669;
    T f = 0;
    for (T v = 0; t <= erdosBow; t += step) {
       f += cb (v);
    }
}

We would introduce a family of interfaces for common data types, and our core types would need to implement these:

interface IInitializeFromDouble<T> : where T: IInitializeFromDouble<T> {
    abstract static implicit operator T (double value);
}

Summary of Generic Code for Math Operations

So in short, we would need:

• The introduction of static members in interfaces, including operator definitions.
• The runtime to recognize the various operator calls for built-in types and treat as intrinsics
• Introduce a hierarchy of numeric data interfaces that can express the various capabilities of the numeric types (Swift has already done the legwork to split those up: IAdditiveNumeric, INumeric, IReal, ISignedNumeric, new work is happening in Swift Numerics, and includes things like IElementaryFunctions).
• Extending the core types to implement the new interfaces

[benaadams]

As well as abstract operators virtual ones? https://github.com/Partydonk/partydonk/pull/7

e.g. implementing IEquatable<T> can give == and != for free:

public interface IEquatable<T>
{
    bool Equals(T other);
    // Implement IEquatable<TSelf>.Equals and get operators == and != for free.
    virtual static bool operator ==(T left, T right) => left.Equals(right);
    virtual static bool operator !=(T left, T right) => !(left == right);
}

Subtraction can be defaulted to negation and add

interface INumeric<TSelf> where TSelf : INumeric<TSelf>
{
    abstract static TSelf Zero { get; }
    abstract static TSelf operator +(TSelf a, TSelf b);
    // Implement negation operator.
    abstract static TSelf operator -(TSelf a);
    // Default subtraction operator is implemented as negation and add.
    virtual static TSelf operator -(TSelf a, TSelf b) => a + -b;
}

This helps reduce the ceremony boilerplate where one operator can be defined in terms of another; while allowing the type to provide a more efficient (or different e.g. Quaternion) implementation if required.

[abock]

@benaadams I've given a little thought to virtual as well and I think we should do it, as a natural extension to default interface methods. In the mean time I've added IOperatorEquatable<T> to the numerics playground code.

[abock]

@benaadams as for the shapes of the interfaces themselves, I was strictly following what Swift Numerics has done so far.