This project is read-only.

Extended Expressiveness of Generic Constraints

Topics: C# Language Design, VB Language Design
Apr 14, 2014 at 1:20 AM
Edited Apr 14, 2014 at 1:34 AM

Extended Expressiveness of Generic Constraints

Let's say that non-nullable reference types were introduced (T!) into .net languages.
It would bring a potential hole in the Generics Constraints syntax.

Since every T! is also a valid T

For example let's take the following extension method.
static INonNullableEnumerable<T> NonNulls<T> ( this IEnumerable<T> xs )
{
// code to filter out the null value and return only the non-null values.
} 
It would also appear as an extension method on IEnumerable<T : struct> and IEnumerable<T!> which wouldn't make any sense, since we know the none of the value can be null.

Fixing the first aspect is easy with constraint T : class
The second one isn't so easy,

How to express the constraint that it can not appear on non-null reference types?

I think to fix this issue we would require to express that T isn't a particular type.
static INonNullableEnumerable<T> NonNulls<T> ( this IEnumerable<T> xs )
  where T : class,
        T != T!
{
//
} 
or express that T can contain null
static INonNullableEnumerable<T> NonNulls<T> ( this IEnumerable<T> xs )
  where T : class,
        T allows null
{
//
} 
What are your thoughts and ideas on how to express this?
Apr 14, 2014 at 2:12 AM
More expressive Constraints would have allowed Sum to be defined like this
static T Sum<T> ( this IEnumerable<T> source )
   where static Zero,
         static T op_Plus ( T x, T, y )
{
  T total = (T).Zero;
  foreach( value In source)
  {
    total = total + value;
  }
  return total; 
}
Apr 14, 2014 at 8:44 AM
You might want to look into type classes, which provide very similar functionality in a more general fashion. In particular, I very much recommend the "Type Classes as Objects and Implicits" paper. I remember going from C# to Scala and discovering type classes - that was an absolute blast!
Apr 14, 2014 at 10:52 AM
AdamSpeight2008 wrote:
More expressive Constraints would have allowed Sum to be defined like this
Something like this has been discussed here: http://roslyn.codeplex.com/discussions/541436

The main problem is that the CLR has no support for such constraints, you can't encode them in metadata nor there's any reasonably efficient way to call such methods in IL. Something like the Sum method in your example can actually be implemented efficiently in C# but you need an additional type argument and because of that you lose generic argument type inference, basically you have to write something like Sum<int, Int32Calculator>(new[] { 1, 3 }) instead of just Sum(new[] { 1, 3 }).

As for T! constraints, well, the idea of non nullability has a lot of holes to begin with. Having a T! constraint wouldn't solve much.
Apr 14, 2014 at 11:23 AM
Edited Apr 14, 2014 at 6:29 PM
mdanes My proposal is different and doesn't need the requirements of static interface members.
static T Sum<T> ( this IEnumerable<T> source )
   where static T Zero,   /* <- requires the type (T) to have a static method called Zero that returns a type */
         static T op_Plus ( T x, T, y )  /* requires the type (T) to have a static method (operator +) that is a Func<T,T,T> */ 
{
  T total = (T).Zero; /* uses the static method zero on the type T */
  foreach( value In source)
  {
    total = total + value; /* uses the  + operator from type (T) */
  }
  return total; 
}
Other example
 where T : class, /* is a ref type */
        T != T!   /* is not the nonnull ref version of T
Constraint is the type (T) is ref-type and not a nonnull ref-type,
Apr 14, 2014 at 11:58 AM
AdamSpeight2008 wrote:
mdanes My proposal is different and doesn't need the requirements of static interface members.
The main problem still stays, there's no CLR support for any constraints beyond those that already exist. Besides, such constraints are completely pointless. They can be used to enforce that the type argument has certain static method but it doesn't solve the real problem which everyone seem to ignore: you can't call those static methods unless you use reflection. Static interface members, as weird as they are, could probably solve this but they too require runtime support.
Apr 14, 2014 at 5:29 PM
I think type classes are a nice pattern, but it's not that hard to implement them using C#:

Declare type class as a generic interface
    public interface Calculator<T>
    {
        T Zero { get; }
        T Add(T a, T b);
    }
Use a generic static class to contain the default instances
    public static class DefaultCalculator<T>  //repository for implicits
    {
        public static Calculator<T> Default;
    }
Use optional parameters and the generic container to fake Scala implicits
    static class MyAlgorithms
    {
        public static T SumGeneric<T>(this IEnumerable<T> collection,  //generic algorithm
            Calculator<T> calculator = null)
        {
            if (calculator == null)
                calculator = DefaultCalculator<T>.Default;

            if (calculator == null)
                throw new InvalidOperationException("Calculator<T> not defined"); 

             T total = calculator.Zero; 
              foreach(var value in collection)
              {
                  total = calculator.Add(total, value); /* uses the  + operator from type (T) */
              }
              return total; 
        }
    }
Instantiate the type class for int
    public class IntCalculator : Calculator<int> // implicits
    {
        static IntCalculator()
        {
            DefaultCalculator<int>.Default = new IntCalculator();
        }

        public int Zero
        {
            get { return 0; }
        }

        public int Add(int a, int b)
        {
            return a + b; ;
        }
    }
    public static class Program
    {
        public static void Main()
        {
           IntCalculator.Register();  //Register instance as default
   
            new[] { 1, 2, 3 }.SumGeneric(); //implicit calculator!
        }
    }
There are some drawbacks, like having to register the default instances at the beginning and relying on run-time exceptions, but I think the main concern is that this patterns have to be build-in in the BCL in order to be useful.

The performance should be good enough, maybe not for int calculations but nothing to do with reflection costs.
Apr 14, 2014 at 6:17 PM
but nothing to do with reflection costs.
You've completely missed the point of AdamSpeight2008's request and in doing that you also missed the point of my comment about reflection.

People have been asking for things like static interface members and other similar things because they think that this will enable them to use operators in generic code. And people don't get this feature either because there's no support in the CLR for it (static interface members) or because it's impossible to do it efficiently (static method constraints such as "static T op_Plus(T x, T, y)". The reason why reflection (or something reflection like) is needed in the later case is that when you ask for something like op_Plus you're basically asking for a method name and nothing more. You can't call e method by name from IL so the only alternative is reflection.

As for performance, yes, it's not going to be good enough for numeric calculations because you're replacing a single instruction such as 'add' with a call through interface which is the slowest possible call there is. Anyway, I'm not sure how much generics can be used for numeric. Simple algorithms such as Sum and Average work fine but if you to do more complicated stuff you soon run into problems - for example you can't quite use numeric literals in such code. Well, I suppose you could expose such constants on ICalculator but it's getting complicated.

It's actually possible to use operators efficiently in generic code. The following produces code that's as fast as a non generic version of Sum.
class Program {
    interface ICalculator<T> {
        T Add(T x, T y);
    }

    struct Int32Calculator : ICalculator<int> {
        private int dummy; // hack to avoid JIT mess-up

        public int Add(int x, int y) {
            return x + y;
        }
    }

    struct Number<T, TCalc> where TCalc : struct, ICalculator<T> {
        T value;

        public Number(T value) {
            this.value = value;
        }

        public static implicit operator Number<T, TCalc>(T value) {
            return new Number<T, TCalc>(value);
        }

        public static implicit operator T(Number<T, TCalc> number) {
            return number.value;
        }

        static TCalc Calc { get { return new TCalc(); } }

        public static Number<T, TCalc> operator +(Number<T, TCalc> x, Number<T, TCalc> y) {
            return Calc.Add(x, y);
        }
    }

    static T Sum<T, TCalc>(IEnumerable<T> values) where TCalc : struct, ICalculator<T> {
        var sum = new Number<T, TCalc>();

        foreach (var value in values)
            sum += value;

        return sum;
    }

    static void Main() {
        Console.WriteLine(Sum<int, Int32Calculator>(new[] { 1, 2, 3 }));
    }
}