Adaptive methods and constants. No Type Classes

[gregsn]

Hello!

regarding haskell type classes: I once admired them, but then again: this is soo hard. How often would you come up with a type class and also get it right. Would they inherit from each other and how to name them properly. Look at all the type classes in haskell that deal with numbers only.

https://github.com/MattWindsor91/roslyn shows how type classes could look like in C#.

---

Here is another idea: Don't bundle methods and name the concept. Just focus on the members...
Introducing adaptive methods:

    public static adaptive T Add<T>(T x, T y);  
    public static adaptive T Zero<T>();

    public static int Add(int x, int y) => x + y; // implicitly implements adaptive Add for T = int
    public static int Zero() => 0; // implicitly implements adaptive Zero for T = int
    
    public static T Sum<T, uses Add<T>, Zero<T>>(T[] values)
    {
        T acc = Zero();
        foreach (var value in values)
            acc = Add(acc, value);
        return acc;
    }

    // compiler notices that T is int, and finds the public methods working with ints, feeds type parameter and implementations into Sum
    Sum(new int[] { 1, 2, 3, 4, 5 });  // 15

Comparison

Type classes bundle methods and give a name to the concept. Adaptive methods are lonesome cowboys. No burden to come up with "the right" type class design and give it "the right" name. Just use the methods you need and communicate via the signature that you long for some implementation for these methods.

Step 2: Cleanup mainly. Adding adaptive Constants and operators

Replace Add with the + operator. Zero with 0. The adaptive definitions for them and the implementations for basic data types would already get shipped with the BCL. With that in mind you get:

    public static T Sum<T, uses +<T>, 0<T>>(T[] values)
    {
        var acc = (T)0;
        foreach (var value in values)
            acc = acc + value;
        return acc;
    }

    // compiler notices that T is an int, finds the implicit adaptive operator implementation for int and the constant `int 0` that fits `0<T>` and feeds that stuff together with type argument `int` into Sum
    Sum(new int[] { 1, 2, 3, 4, 5 });  // 15

The proposed design works fine for the visual language VL that is also targeting .Net. We call it adaptive nodes.

@MattWindsor91

What do you think?

[YairHalberstadt]

How would this work under the hood?
What would the compiler generate?

[gregsn]

It would have to compile Sum for each TArg as each TArg comes with its own implementations

[YairHalberstadt]

I'm not sure I understand. Can you show some example code, as well as how that example looks 'desugared'

[gregsn]

under the hood it would compile

    public static int Sum_For_int(int[] values)
    {
        var acc = (int)0;
        foreach (var value in values)
            acc = acc + value;
        return acc;
    }

for a Vector2 it would use (0,0) and the + operator of Vector2 and compile another Sum_For_Vector2.

So when thinking from an entry point (you main program) where all the type parameters have been replaced with concrete type arguments the compiler will in the end have replaced all the adaptive calls with concrete implementations and will call the appropriate methods (like Sum_for_Vector2).

the big questionmark is how we would put a public static T Sum<T, uses +<T>, 0<T>>(T[] values) into a dll - when the type parameters are not yet clear. We can't really compile that yet. It is still in a kind of template state. But is that true for type classes as well?

[HaloFour]

It would have to compile Sum for each TArg as each TArg comes with its own implementations

That sounds like it would work like C++ templates rather than C#/CLR generics. How would that work across assemblies?

[gregsn]

It would have to compile Sum for each TArg as each TArg comes with its own implementations

That sounds like it would work like C++ templates rather than C#/CLR generics. How would that work across assemblies?

That indeed is a big ?.
This issue needs to be addressed. And it won't be easy. We'd probably need to get creative and try different ideas. Can we learn from F# quotations that I think get stored as expressions in the dll? Or would there be an option to ship the source code of Sum with the dll and compile later? How did the dynamic keyword get implemented again? Wasn't there some trick along these lines?
Guys, uh, please, help me out if there - if you like the basic idea!

[HaloFour]

It is still in a kind of template state. But is that true for type classes as well?

Yes, as of the "shapes" proposal the "typeclass" would be emitted more or less as a normal generic interface where all of the members would be converted into suitable instance members and that would be exposed from the assembly. The compiler would recognize that interface as a "typeclass" presumably using some additional metadata like an attribute. The compiler would then generate witness structs implementing that "typeclass" interface to wire up the target members.

Can we learn from F# quotations that I think get stored as expressions in the dll? Or would there be an option to ship the source code of Sum with the dll and compile later?

Both would involve embedding a lot of voodoo into the assembly. Much of F#'s typesystem doesn't work outside of F# for this reason. In the case of embedded source, how would a compiler from any other language be able to interop? With "typeclasses" these issues don't exist.

[gregsn]

Ok, wait, this should be doable...
I think you can translate the adaptive idea into the type class idea:

• Each adaptive operator or constant is sugar for an adaptive method.
• Each adaptive method can be translated into a "concept" with one method (named by the method). So it would emit a generic interface with one method (or delegate).

---

But let's try it from scratch.

• If the source code of "Sum" is in the same project as the final closed usage (no type parameters pending), then we can compile it like suggested above. No dispatch calls = fast.
• If we compile to a dlll we want to give others the opportunity as well to use sum, so additionally we emit a "Sum_adaptive_via_delegate" that expects two delegates.
• In the other project you wouldn't call Sum_adaptive_via_delegate manually, but call Sum(new Color[] { Red, Green }); // White
• the compiler calls "Sum_adaptive_via_delegate" and feeds Color.Add and Color.Black as delegates. not so fast but functional.

[HaloFour]

If the source code of "Sum" is in the same project as the final closed usage (no type parameters pending), then we can compile it like suggested above. No dispatch calls = fast.

Having the C# compiler emit specialized versions of the method would be a pretty big departure from the current generic paradigm and the team has not expressed interest in implementing such a feature. If the compiler has to emit a different version of the method for every possible combination that will result in a lot of assembler bloat. Not to mention, I think that the declaration, use and consumption of these types of features will be mostly between separate assemblies.

If we compile to a dlll we want to give others the opportunity as well to use sum, so additionally we emit a "Sum_adaptive_via_delegate" that expects two delegates.

For what I consider to be the majority case that would be quite a bit more complicated and cumbersome while also being a lot less efficient than the interface/witness approach, where a constrained interface call guarantees both specialization and inlining. You don't get more efficient than that.

I personally don't see the benefit of having these "adaptive methods" separate from typeclasses. Grouping them under a nominal structure makes it easier to group them for common operations and it fits in a lot easier with the language and the runtime. You're still free to declare each typeclass with a single method.

[gregsn]

Having the C# compiler emit specialized versions of the method would be a pretty big departure from the current generic paradigm and the team has not expressed interest in implementing such a feature. If the compiler has to emit a different version of the method for every possible combination that will result in a lot of assembler bloat. Not to mention, I think that the declaration, use and consumption of these types of features will be mostly between separate assemblies.

Well, this is optional. In our examples, it's often been about computing with "number types" and it felt like a bad idea to do this via an interface method calls. I think several compilation strategies are possible. It would also be interesting what could be done with expression trees. But then there are still the interface or delegate way left, which is the easiest approach that also doesn't arise any issues between assemblies.

That said: the most important aspect of the proposal is the ease of use.

For what I consider to be the majority case that would be quite a bit more complicated and cumbersome while also being a lot less efficient than the interface/witness approach, where a constrained interface call guarantees both specialization and inlining. You don't get more efficient than that.

I am not sure if I can follow. In here I see regular interface calls.

Back to the adaptive idea: Wouldn't we get roughly the same performance with the delegate or interface compilation strategy?

I personally don't see the benefit of having these "adaptive methods" separate from typeclasses. Grouping them under a nominal structure makes it easier to group them for common operations and it fits in a lot easier with the language and the runtime. You're still free to declare each typeclass with a single method.

The main point is simplicity.
You don't have the burden to define a typeclass and you don't have to explicitly implement anything. Similarly to how the compiler finds the right overload when calling a method, it will just try to find the method that has the right name, arguments, and argument types when searching for the right methods to plug into.

[HaloFour]

@gregsn

Well, this is optional. In our examples, it's often been about computing with "number types" and it felt like a bad idea to do this via an interface method calls.

I am not sure if I can follow. In here I see regular interface calls.

I am basing the discussion on the "shapes" proposal which is probably the more of the fleshed out variations discussed on this repository. This is certainly very early in discussion, though, and there have been other alternative proposals put forth.

In this proposal the interface call through to the "witness" struct is constrained and the generic type parameter for the witness of the method making the call is further constrained to be a struct. In that case the JIT will specialize the method for the witness class avoiding the boxing allocation and the virtual call, and given how simple the witness method will be that will certainly be inlined.

The main point is simplicity.
You don't have the burden to define a typeclass and you don't have to explicitly implement anything.

The same is true of the proposal I mentioned. While the typeclass does compile down to an interface you are never expected to actually implement it. When you call a method that expects the typeclass the compiler will determine if the type is compatible and will emit a witness struct which will handle wiring up the required members. You're not required to do anything else.

Here's another more recent discussion which explores the idea of "extension interfaces" instead, which are similar to "shapes"/"typeclasses" except building on the idea of "extension everywhere" which aims to allow developers to add arbitrary members to existing types, not just methods.

I expect that after C# 8.0 is released that this topic will explode and there will be a lot of discussions and spaghetti thrown at the wall. But in my opinion some of the critiques I have of this proposal will be important to whatever the team eventually decides to build, in that whatever it is has to have a good story for consumption across assembly boundaries without requiring very language/compiler-specific metadata (like embedded source) and not adding overhead at runtime.

[gregsn]

@HaloFour: thanks for all the good input so far!
I will have to read a lot before being able to discuss further.
But all these other proposals sound very powerful and promising indeed.

Regarding the optimization. Got it. It's a difference if you hand over the interface or a type that is constrained to the interface. Missed that bit.

Just a small comment to this adaptive proposal:
To make the JIT compiler do the specialization for us we would also need to use the same idea and just build a witness struct that implements the several interfaces that stem from the adaptive methods.

    public static adaptive T Add<T>(T x, T y);  
    public static adaptive T Zero<T>();

    public static int Add(int x, int y) => x + y; 
    public static int Zero() => 0; 
    
    public static T Sum<T, uses Add<T>, Zero<T>>(T[] values)
    {
        T acc = Zero();
        foreach (var value in values)
            acc = Add(acc, value);
        return acc;
    }

    void main()
    { 
        Sum(new int[] { 1, 2, 3, 4, 5 });  // 15
    }

could translate to

    public interface IAdaptiveAdd<T> { T Add(T x, T y); }
    public interface IAdaptiveZero<T> { T Zero(); }

    public static T Sum<T, TWitness>(T[] values) 
        where TWitness : struct, IAdaptiveAdd<T>, IAdaptiveZero<T>
    {
        TWitness witness = default(TWitness);
        T acc = witness.Zero();
        foreach (var value in values)
            acc = witness.Add(acc, value);
        return acc;
    }

    struct IntWitnessForSum : IAdaptiveAdd<int>, IAdaptiveZero<int>
    {
        public int Add(int x, int y) => x + y;
        public int Zero() => 0;
    }

    void main()
    { 
        Sum<int, IntWitnessForSum>(new int[] { 1, 2, 3, 4, 5 });  // 15
    }

interesting

[munael]

That would pollute the namespace, way more than typeclasses. Since they're static and 'open' (like extension methods, they don't need full names to access them, but they don't rely on the operand type to narrow down the search). And you have to mention every single function you want to use on a given type.

So it seems like the proposal's core is actually the generic constraint on method name, not the adaptive methods part. Like:

public static class IntExtensions { // no extension everything
    public static int Add(this int x, int y) => x + y;
    public static int Zero(this int _) => 0; // because no extension-everything yet
}
    
public static class Program {
    public static T Sum<T>(T[] values)
        where T : .Add(T), .Zero // method constraints
    {
        T acc = T().Zero(); // because no extension-everthing yet
                            // (here missing: static methods, properties)
        foreach (var value in values)
            acc = acc.Add(value); // missing static methods
        return acc;
    }

    void main()
    { 
        Sum(new int[] { 1, 2, 3, 4, 5 });  // 15
    }
}

But that doesn't say how such generic code is supposed to look for and choose the right extension methods. Are they all passed in a dictionary from the calling context?

Maybe a static class is implicitly defined for every type used in a file that gathers all of its extension methods, and that is passed to any generic method called that has a method-existence constraint?

And that brings us right around to coherence issues. Which justifies the adaptive declarations (supposedly, no type can define several implementations to an adaptive). But at this point, why not just typeclasses?

It feels like adaptive methods would be to typeclasses what free functions would be to the language.

[gregsn]

@narfanar:
Thanks for joining the discussion!

So maybe I should be honest about that I wasn't really aware of all the work that went into the above-mentioned proposals. It will take me some time to catch up. And I am not sure if I actually already want to go and compete against concepts, shapes, roles, static interface members, extension-everywhere and Haskell type classes etc. at the same time :D! My proposal comes from a different background: adaptive nodes in VL and type classes in Haskell. And I do want to see how it would apply to C# and what it could bring to the table.

---

Your points:

Not Extension-everywhere:
Let's try not to mix extension-everywhere ideas into the idea, for now, to keep it manageable. I think we can reason about it without potential other upcoming features.

About pollution:
Let's say adaptive declarations are organized in namespaces that you have to use.
public static adaptive T operator *(T, T); would be in System.Math.Adaptive.
So the using statement helps to get stuff organized.

public static adaptive TResult operator *(T0, T1); //order or owner of type parameters should not matter! no need to specify via <,,>: the witness implementation helps with wiring it properly.

would maybe be more special and hide somewhere else or it wouldn't even be predefined. You would need to define it yourself.
With the proper namespaces used I can write something like this (syntax still flexible):

    public static T Lerp<T, TScalar>(T a, T b, TScalar scalar) 
        using TScalar One, 
        using TScalar operator -(TScalar, TScalar),  // names of operands are ignored  
        using T operator *(T, TScalar), 
        using T operator +(T, T)
    {
        return a * (One - scalar) + b * scalar;
    }

where I specialize the adaptive operators and the adaptive One with my own type parameters.
My guess is that the adaptive definitions themselves don't pollute anything as I only can make use of them in a very special place in my code (in that particular using statement).
In the body of the function I only directly refer to the ones in my signature.

But on application side, I want to provide implementations. So what about application side?
I could imagine that you would need to do something like this:

using static SharpDX.Vector2; // a struct with static operators for Vector2 * float, Vector2 * Vector2, float * Vector2

I wasn't aware up to now of the using static feature, but it comes in handy...
You might argue that this is even worse as I now see all the static members and I have all static members that I didn't even want.
Well. Maybe just maybe we could do another trick and do something like:

using adaptive SharpDX.Vector2;

which would now make the static members only visible for when it's about finding implementations for an adaptive method argument on the calling site Lerp(p0, p1, t). If we still have too many possible implementations I can imagine to help out by handing over the particular ambiguous member explicitly.

(Lerp(p0, p1, t) using Vector2 operator MyAdaptives.*(Vector2, float))

or similar.

---

I don't want to push this too far as I actually think that all the other proposals definitely have A LOT to offer and seeing all the hard work to get each small detail right and make different ideas to work together is just impressive. It's also very good to see a community trying to work all this out together.

I am just curious what this rather small grained feature can offer over type classes. I don't know. Maybe you would argue: This combination of members is somewhat special. So define your own type class. If possible I would maybe do so and don't use any of the other number type classes, even though there are already plenty for every little added members there is just another one. Haskell number type classes also "inherit" from each other. So the user gets the feeling: these you need to understand and to know of and to use. Don't even go near defining your own concept. Even though that is the real power: To be able to define the smallest possible shape for already existing functionality, make it match if it doesn't already and when adding new types only having to offer the actually needed functionality to apply to that shape.
My fear with type classes is that users come up with own type classes too seldomly and use existing ones when constraining their methods even if some member is not needed. This would then affect users that want to provide a new matching type. They need to provide a member that is not used in the end. This is the main point why I tried another idea.

---

I can imagine warnings on unused adaptive nodes. So intellisense offers me to kick them out of my signature. I can also imagine an intellisense feature that helps me adding missing "using" statements. (In our visual language VL you don't need to specify them as the body of the method gets looked at before finishing the signature, but I guess something like that is a no go; isn't an operator already kind of "adaptive" in C#: you only can specify which one to use via the used types. It just happens to not work over method borders and type parameters.)

It would be interesting for what other cases these little fellows can be used. Can I call new T(42) if specify that i use new T(int answerToAQuestion) or just new T(int) if i don't care about the name of the argument?
I actually can imagine many use cases and it would be very interesting which other of the plenty ideas would be necessary to get the most out of it. And which other ideas would conflict as they solve the same problem but different.

[gregsn]

we can turn things around and ask for some sugar for this console app written in C#7.0:

using System.Text;
using static System.Console;
using static System.Math;
using System.Numerics;

namespace BezierEverything
{
    class Program
    {
        //std stuff
        public interface IAdaptive_op_Addition<T> { T op_Addition(T x, T y); }
        public interface IAdaptive_op_Subtractation<T> { T op_Subtraction(T x, T y); }
        public interface IAdaptive_1<T> { T One { get; } }

        //my own defintions
        public interface IAdaptive_op_Multiply<T1, T2, TResult> { TResult op_Multiply(T1 x, T2 y); }

        public static T Lerp<T, TScalar, TWitness>(T a, T b, TScalar scalar)
            where TWitness : struct, 
            IAdaptive_1<TScalar>,
            IAdaptive_op_Subtractation<TScalar>, 
            IAdaptive_op_Multiply<T, TScalar, T>,
            IAdaptive_op_Addition<T>
        {
            TWitness witness = default(TWitness);
            var scaledA = witness.op_Multiply(a, witness.op_Subtraction(witness.One, scalar));
            var scaledB = witness.op_Multiply(b, scalar);
            return witness.op_Addition(scaledA, scaledB);
        }

        //handcrafted <int, float> lerp 
        public static int Lerp(int a, int b, float scalar) => 
            //using generated <float, float> lerp
            (int)Round(Lerp<float, float, FloatFloatWitnessForLerp>(a, b, scalar));

        //handcrafted <string, float> lerp
        public static string Lerp(string a, string b, float scalar)
        {
            if (a.Length == 0 || b.Length == 0) return "";
            var charCount = Lerp(a.Length, b.Length, scalar); // <int, float> lerp
            var stringb = new StringBuilder();
            for (int i = 0; i < charCount; i++)
                stringb.Append((char)Lerp(a[i % a.Length], b[i % b.Length], scalar)); // <int, float> lerp
            return stringb.ToString();
        }

        //abstract over lerp again to be able to mix the generic lerp with the handcrafted ones
        public interface IAdaptive_Lerp<T, TScalar> { T Lerp(T a, T b, TScalar scalar); }

        //bezier doesn't care if Lerp is handcrafted or not
        static T CubicBezier<T, TX, TWitness>(T p0, T p1, T p2, T p3, TX x)
            where TWitness : struct,
            IAdaptive_Lerp<T, TX>
        {
            TWitness witness = default(TWitness);

            var q0 = witness.Lerp(p0, p1, x);
            var q1 = witness.Lerp(p1, p2, x);
            var q2 = witness.Lerp(p2, p3, x);

            var r0 = witness.Lerp(q0, q1, x);
            var r1 = witness.Lerp(q1, q2, x);

            return witness.Lerp(r0, r1, x);
        }


        //witnesses
        struct FloatFloatWitnessForLerp :
            IAdaptive_1<float>,
            IAdaptive_op_Subtractation<float>,
            IAdaptive_op_Multiply<float, float, float>,
            IAdaptive_op_Addition<float>
        {
            public float One => 1f;
            public float op_Subtraction(float x, float y) => x - y;
            public float op_Multiply(float x, float y) => x * y;
            public float op_Addition(float x, float y) => x + y;
        }

        struct StringFloatWitnessForCubicBezier :
            IAdaptive_Lerp<string, float>
        {
            // for cubic bezier in strings i only need to point to my handcrafted string lerp
            public string Lerp(string a, string b, float scalar) => Program.Lerp(a, b, scalar);
        }

        struct ComplexComplexWitnessForCubicBezier :
            IAdaptive_Lerp<Complex, Complex>
        {
            struct ComplexComplexWitnessForLerp :
                IAdaptive_1<Complex>,
                IAdaptive_op_Subtractation<Complex>,
                IAdaptive_op_Multiply<Complex, Complex, Complex>,
                IAdaptive_op_Addition<Complex>
            {
                public Complex One => 1f;
                public Complex op_Subtraction(Complex x, Complex y) => x - y;
                public Complex op_Multiply(Complex x, Complex y) => x * y;
                public Complex op_Addition(Complex x, Complex y) => x + y;
            }

            public Complex Lerp(Complex a, Complex b, Complex scalar) => 
                Lerp<Complex, Complex, ComplexComplexWitnessForLerp>(a, b, scalar);
        }

        static void Main(string[] args)
        {
            var x = 10;
            var y = 10;
            for (int i = 0; i <= x; i++)
            {
                var normX = i / (float)x;
                WriteLine(CubicBezier<string, float, StringFloatWitnessForCubicBezier>
                    ("everything", "you", "know", "is", normX));
                for (int j = 0; j <= y; j++)
                {
                    var normY = j / (float)y;
                    var complexResult = CubicBezier<Complex, Complex, ComplexComplexWitnessForCubicBezier>(
                        new Complex(0, 0), new Complex(0, 1),
                        new Complex(1, 1), new Complex(1, 0), 
                        new Complex(normX, normY));
                    WriteLine($"({normX},{normY}) -> {complexResult}");
                }
            }
            ReadKey();
        }
    }
}

how would that look like with the different approaches?

[gregsn]

maybe there is a more performant way to compute the cubic bezier for floats and 2d vectors using polynomials? Then I would again abstract over CubicBezier via another adaptive definition so that the generic implementation is just one of the possible implementations of the now adaptive CubicBezier.
This looks like a pattern. So maybe each member that uses adaptive members would implicitly define an adaptive member on its own so that we can specialize this.

Maybe we could even show warnings when someone calls the generic Lerp (handing over 4 members) instead of the adaptive implicitly defined adaptive Lerp (that not only simplifies the set of constraints quite a bit but also opens the door for new ways to plug into the system.

Dear all, sorry, I know this goes into a whole other direction than everything that you were up to. So please take it as a hopefully refreshing and somewhat different idea from a parallel universe.

[gregsn]

Could that work:

IEnumerable<float> Foo<T>(T values)
    using IEnumerator<float> GetEnumerator(T) 
{
    foreach (var x in values)
        yield return x+1.0;
}

The compiler could try different approaches to get its enumerator:

• if we have a concrete type or a type parameter with concrete type constraints -> test the concrete type(s) for IEnumerable<> and IEnumerable
• test if there is an adaptive node IEnumerator<> GetEnumerator(T) that can be used

On caller site you would be able to hand over a static (extension) method or an instance method or getter. The compiler would generate a static method for you that takes the instance, calls the getter and returns the enumerator...

Is it a good style to use such a using statement? Probably not. I think the question has been answered somewhere already: the user doesn't want to have different ways of specifying that she/he needs an enumerable thing. We want to accept an argument of type IEnumerable<>, which then also allows us to call .Where() etc.

But: how to get one on the fly on the calling site if the original type doesn't offer one? That's totally unrelated, but here is another idea: instead of attaching interfaces via an extension with implicit (identity) conversion, we could steal from other more explicit ideas like https://fsharpforfunandprofit.com/posts/object-expressions/. In C# this could read like this:

var x = new IEnumerable<int>(seethrough: myObject) 
{ 
    GetEnumerator = anotherObject.GetEnumerator //plugs the "method group" into our new type    
    //GetEnumerator = anotherType.GetEnumerator //works if GetEnumerator is a static method
};

which would extend the anonymous type feature, with see-through capabilities and the ability to implement interfaces. It would also implement all the interfaces of the compile time type of myObject. As it is the anonymous type feature it would also allow to add more state.
But wether you have a little expression to implement an interface or not, I am leaning towards this: The act of gluing an interface to a type has to be explicit - even if it is lightweight and doesn't add state.
Everything under "Eagerness of "Witnessing", "Object Identity" is super scary to me. As if it would break basic intuitions of how to think about types.
It is more than an implicit cast: IFoo foo = originalObject;. foo now holds on to a different object. It is something else. It is a sort of proxy, but not the original object. You have to be able to see that in your code. I think you don't want to get a magically created facade that has a different object identity - by no language feature.
Still, roles and extensions could get fixed. I just think you should be forced to write something like (originalObject as IEnumerable<int> via extension) to make it explicit that you now deal with another object.