Champion "Type Classes (aka Concepts, Structural Generic Constraints)"

[gafter]

• Proposal added
• Discussed in LDM
• Decision in LDM
• Finalized (done, rejected, inactive)
• Spec'ed

See

• https://github.com/MattWindsor91/roslyn/blob/master/concepts/docs/csconcepts.md
• https://c10109cf-a-62cb3a1a-s-sites.googlegroups.com/site/mlworkshoppe/2016-7.pdf
• https://github.com/MattWindsor91/roslyn
• Previously discussed at Please Add Type Classes to C# roslyn#16312
• https://github.com/dotnet/csharplang/blob/main/meetings/2022/LDM-2022-09-26.md#roles--extensions

[gafter]

/cc @MattWindsor91

[orthoxerox]

Please consider type classes on generic types as well.

[gafter]

@orthoxerox The proposal supports type classes on generic types. Unless perhaps I don't understand what you mean.

[orthoxerox]

@gafter the proposal might have evolved since I last read it, but I remember that a monad concept could be implemented only in a very convoluted way, the signature of SelectMany with a projector had like 10 generic parameters.

[gafter]

@orthoxerox It does not support higher-order generics.

[orthoxerox]

That's what I meant.

[louthy]

@gafter Is there any chance that higher-order generics could be considered? I was going to stay out of this conversation for a while, but I have managed to get most of the way there by using interfaces as type-classes, structs as class-instances (as with Matt Windsor's prototypes), and then using constraints to enforce relationships:

• Type-classes
• Class instances
• Data types

Along the way I have had to make a number of compromises as I'm sure you would expect. But the majority of the 'higher order generics' story can be achieved with a significantly improved constraints story I feel. And with some syntax improvements that give the appearance of higher-order generics, but behind the scenes rewritten to use constraints.

For example I have a Monad type-class

    public interface Monad<MA, A>
    {
        MB Bind<MONADB, MB, B>(MA ma, Func<A, MB> f) where MONADB : struct, Monad<MB, B>;

        MA Return(A x);

        MA Fail(Exception err = null);
    }

Then a Option 'class instance'

    public struct MOption<A> : Monad<Option<A>, A>
    {
        public MB Bind<MONADB, MB, B>(Option<A> ma, Func<A, MB> f) where MONADB : struct, Monad<MB, B>
        {
            if (f == null) throw new ArgumentNullException(nameof(f));
            return ma.IsSome && f != null
                ? f(ma.Value)
                : default(MONADB).Fail(ValueIsNoneException.Default);
        }

        public Option<A> Fail(Exception err = null) =>
            Option<A>.None;

        public Option<A> Return(A x) =>
            isnull(x)
                ? Option<A>.None
                : new Option<A>(new SomeValue<A>(x));
    }

The big problem here is that for Bind the return type is only constrained to be a Monad<MB, B>, when I need it to be constrained to Monad<Option<B>, B>.

The functor story is an interesting one:

    public interface Functor<FA, FB, A, B>
    {
        FB Map(FA ma, Func<A, B> f);
    }

With an example Option class instance:

    public struct FOption<A, B> : Functor<Option<A>, Option<B>, A, B>
    {
        public Option<B> Map(Option<A> ma, Func<A, B> f) =>
            ma.IsSome && f != null
                ? Optional(f(ma.Value))
                : None;
    }

Notice how I've had to encode the source and destination into the interface. And that's because this isn't possible:

    public interface Functor<FA, A>
    {
        FB Map<FB, B>(FA ma, Func< A, B> f) where FB == FA except A is B;
    }

If we could specify:

    public interface Functor<F<A>>
    {
        F<B> Map<F<B>>(F<A> ma, Func<A, B> f);
    }

And the compiler 'auto-expand out' the F<A> into FA, A and inject the correct constraints. Then maybe the (apparently impossible) job of updating the CLR wouldn't be needed?

As @orthoxerox mentioned, the generics story gets pretty awful pretty quickly. Here's a totally generic Join and SelectMany

        public static MD Join<EQ, MONADA, MONADB, MONADD, MA, MB, MD, A, B, C, D>(
            MA self,
            MB inner,
            Func<A, C> outerKeyMap,
            Func<B, C> innerKeyMap,
            Func<A, B, D> project)
            where EQ     : struct, Eq<C>
            where MONADA : struct, Monad<MA, A>
            where MONADB : struct, Monad<MB, B>
            where MONADD : struct, Monad<MD, D> =>
                default(MONADA).Bind<MONADD, MD, D>(self,  x =>
                default(MONADB).Bind<MONADD, MD, D>(inner, y =>
                    default(EQ).Equals(outerKeyMap(x), innerKeyMap(y))
                        ? default(MONADD).Return(project(x,y))
                        : default(MONADD).Fail()));

        public static MC SelectMany<MONADA, MONADB, MONADC, MA, MB, MC, A, B, C>(
            MA self,
            Func<A, MB> bind,
            Func<A, B, C> project)
            where MONADA : struct, Monad<MA, A>
            where MONADB : struct, Monad<MB, B>
            where MONADC : struct, Monad<MC, C> =>
                default(MONADA).Bind<MONADC, MC, C>( self,    t => 
                default(MONADB).Bind<MONADC, MC, C>( bind(t), u => 
                default(MONADC).Return(project(t, u))));

A couple of issues there are:

• I can't put a this in front of MA self. If I do, then every type gains a SelectMany and Join method, even if they're not monadic.
• The type-inference story is obviously non-existent, and LINQ cannot work this out

Obviously all of this is of limited use to consumers of my library, but what I have started doing is re-implementing the manual overrides of things like SelectMany with calls to the generic versions. This is SelectMany for Option:

public Option<C> SelectMany<B, C>(
    Func<A, Option<B>> bind,
    Func<A, B, C> project) =>
    SelectMany<MOption<A>, MOption<B>, MOption<C>, Option<A>, Option<B>, Option<C>, A, B, C>(this, bind, project);

So my wishlists would be (if higher-order generics, or similar are not available):

• Significantly improved generic-parameter type-inference story. i.e. not providing arguments when not needed would be a good start.
• Constraints that link return types to generic arguments

Apologies if this is out-of-scope, I just felt some feedback from the 'front line' would be helpful here. And just to be clear, this all works, and I'm using it various projects. It's just boilerplate hell in places, and some hacks have had to be added (a FromSeq for Monad<MA,A> for example)

[gafter]

@louthy Without thinking too deeply about it, I would ask the questions

1. Are higher-order types related to type classes, or orthogonal (but perhaps complementary) to them?
2. Do they require CLR support (e.g. for using a higher-order API across assembly boundaries)?
3. Are they obvious/straightforward to specify and implement? Are the design choices obvious?
4. Would they "pay for themselves"?

[gulshan]

This may lead to a totally new (and separate?) standard library, with this as the base.

[MattWindsor91]

My understanding was that higher-kinded types would need CLR changes, hence why Claudio and I didn't propose them (our design specifically avoids CLR changes). I could be wrong though.

[orthoxerox]

@gafter

Are higher-order types related to type classes, or orthogonal (but perhaps complementary) to them?

Related, since you can only express a subset of type classes without them (Show, Read, Ord, Num and friends, Eq, Bounded). Functor, Applicative, Monad and the rest require HKTs.

Do they require CLR support (e.g. for using a higher-order API across assembly boundaries)?

Yes. Unless there's some clever trick, but then they won't be CLS compliant.

Are they obvious/straightforward to specify and implement? Are the design choices obvious?

Not that straightforward. The design choices are more or less clear.

Would they "pay for themselves"?

As much as any other type classes would.

[louthy]

@gafter

@orthoxerox has concisely covered the points, so I'll try not to repeat too much.

Do they require CLR support (e.g. for using a higher-order API across assembly boundaries)?

I think this was always the understanding. Obviously the 'hack' that I've done of injecting the inner and outer type (i.e. MOption<Option<A>, A>>) into the higher-order type's argument list is something that doesn't require CLR support. But types like Functor<FA, FB, A, B> have no constraints that enforce the F part of FA and FB to be the same. So this is possible:

    public struct MOptTry<A, B> : Functor<Option<A>, Try<B>, A, B>
    {
        public Try<B> Map(Option<A> ma, Func<A, B> f) => ...
    }

Which obviously breaks the functor laws. It would be nice to lock that down. If it were possible for the compiler to expand Functor<F<A>> into Functor<FA, A> and enforce the outer type F to be the same (for the return type of Map), then good things would happen. That is the single biggest issue I've found with all of the 'type classes'. Also the type inference story should significantly improve by default (well, obviously none of this is free, but currently having to specify Option<A> and A is redundant).

So, I'm not 100% sure a CLR change would be needed. The current system works cross assembly boundaries, so that's all good. The main thing would be to carry the constraints with the type (is that CLR? or compiler?). If adding a new more powerful constraints system means updating the CLR, is it better to add support for higher-order types proper?

Are they obvious/straightforward to specify and implement? Are the design choices obvious?

I've gotten a little too close to using them with C# as-is. But I suspect looking at Scala's higher-order types would give guidance here. I'm happy to spend some time thinking about how this could work with Roslyn, but I would be starting from scratch. Still, if this is going to be seriously considered, I will happily spend day and night on this because I believe very strongly that this is the best story for generic programming out there.

Would they "pay for themselves"?

I believe so, but obviously after spending a reasonable amount of time working on my library, I'm biased. The concepts proposal is great, and I'd definitely like to see that pushed forwards. But the real benefits. for me, come with the higher-order types.

[gafter]

Given that changes that require CLR changes are much, much more expensive to roll out and require a much longer timeframe, I would not mix higher-kinded types into this issue. If you want higher-kinded types, that would have to be a separate proposal.

[louthy]

@gafter Sure. Out of interest, does 'improved constraints' fall into CLR or compiler? I assume CLR because it needs to work cross-assembly. And would you consider an improved constraints system to be a less risky change to the CLR than HKTs? (it feels like that would be the case).

I'm happy to flesh out a couple of proposals.

[gafter]

If the constraints are already expressible (supported) in current CLRs, then enhancing C# constraints to expose that is a language request (otherwise a CLR and language request). I don't know which is easier, constraints or HKTs.

[TheJayMann]

The idea of the functor and the monad require higher kinded polymorphism, even more so than it requires the concept of type classes. In fact, in a language and runtime such as C# and .NET, should higher kinded polymorphism be made available (most likely as a form of generic constraint), the concept of functors and monads could be implemented as an interface instead of a type class.

Really, the way I was most able to understand the concept of a type class is that it is similar to the idea of an interface which can be externally applied to a type, similar to how extension methods are methods which can be externally applied to a type.

[NickSeagull]

In languages like Kotlin, that do not support Higher Kinded Polymorphism, they have adopted a pattern that specifies the kind separately see https://arrow-kt.io/docs/0.10/patterns/glossary/#higher-kinds . Yet type classes are still useful

[tgrospic]

I enjoyed the whole discussion on this thread. Thanks all!

I hope C# will eventually have nice solution for higher-kinded types. I'd like to share my experiments to encode HKT with generics.
https://github.com/tgrospic/object-algebras

My interest is how we can use HKT and escape know issues like difficult composition of monad transformers or free monads which requires extra structure with impact on performance.
In the repository there are two samples. One is re-implementation of Banking sample from language-ext library which gave me initial inspiration (thanks Paul!). It is easier to extend both the data and the functions over data, as a solution to expression problem.
Another example is more in the functional style. JSON parser defined with parser combinators which is almost in step translation from Haskell code.

If we see generics as ability to have type level variables, higher-kinded type is ability to define a function on the type level. Of course in a limited way like in Scala, not "the same" function like in Idris.
https://gist.github.com/tgrospic/661f6504c4940ac6b15e13c06abbdffe
Lightweight higher-kinded polymorphism paper describes how with a technique of defunctionalization, functions can be encoded into a first-order language (type level C#). Similar how predicate functions are encoded in Mongo query or GraphQL (filter, sort, ...).

[333fred]

@tgrospic the hkt issue is here: #339

[hez2010]

@tgrospic the hkt issue is here: #339

I think HKT and Type Classes should be considered together.

[Pzixel]

They are completely unrelated. For example, Rust has type classes but doesn't have HKT, and there is no reason why the opposite configuration cannot exist (although I don't recall any example). Thus there is no reason to "consider them together"

[huoyaoyuan]

Thus there is no reason to "consider them together"

There's one possible reason: leaving places in syntax tokens and BCL for "once it's a thing", to avoid future breaking and ecosystem inconsistence.

[chkn]

Interop between concepts and 'normal' interfaces is another unresolved issue with our proposal

Has there been any progress on this issue? I'm not quite sure why concepts/shapes/whatever would be distinct in the language from interfaces. It seems to me that they both serve the same purpose, to define contracts. Is the separation just an ugly manifestation of the underlying implementation details, or am I missing something?

[BreyerW]

@chkn there is seperate proposal to extend interfaces themselves, type roles in search and that proposal should pop up.

As for different implementations this is because shapes and the like wouldnt require changes to the runtime which is huge plus for language team. Extending interfaces require changes to the runtime which is considered highly undesirable but not showstopper though

[333fred]

Extending interfaces require changes to the runtime which is considered highly undesirable but not showstopper though

This was highly undesirable before core/5. It is not now. Personally, I believe interfaces should indeed be turned into type classes.

[MattWindsor91]

Just to concur here, really: a lot of the specifics about the version of concepts Claudio and I prototyped were explicitly to avoid runtime changes per the situation with the CLR circa 2016. Now that the CLR is less immutable, it makes sense to do whatever makes concepts a good citizen in the C# ecosystem and with existing code and practices, and having them stand entirely separately from and parallel to interfaces is an issue I remember coming up repeatedly.

One of the nice things about the concepts prototype was the degree of static resolution/devirtualisation/inlining that the CLR could do when it applied concept methods on known types - it'd be nice from a perf point of view to have something like this, but it's arguably a very different world to normal interfaces. (Apologies, I've been mostly out of the loop on this for a few years now, so this might've already been a point of discussion!)

[andre-ss6]

Extending interfaces require changes to the runtime which is considered highly undesirable but not showstopper though

This was highly undesirable before core/5. It is not now.

What changed?

[333fred]

Extending interfaces require changes to the runtime which is considered highly undesirable but not showstopper though

This was highly undesirable before core/5. It is not now.

What changed?

We no longer ship major version updates same day to billions of devices.

[chkn]

@chkn there is seperate proposal to extend interfaces themselves, type roles in search and that proposal should pop up.

Thanks! I found #1711, which is more what I was imagining.

One of the nice things about the concepts prototype was the degree of static resolution/devirtualisation/inlining that the CLR could do when it applied concept methods on known types

Yeah it's a good proposal, and using structs as witnesses is a brilliant idea. Definitely the nicest thing if runtime support is out of the question. I also believe the same optimizations can occur for generic types constrained to interfaces.

[Shadowblitz16]

does this topic cover restraining generics to operators?
dotnet/roslyn#3391