Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
gafter opened this issue Feb 15, 2017 · 165 comments

Comments

@gafter
Copy link
Member

commented Feb 15, 2017

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

See

@gafter

This comment has been minimized.

Copy link
Member Author

commented Feb 15, 2017

@gafter gafter changed the title Type Classes (aka Concepts, Structural Generic Constraints) Champion Type Classes (aka Concepts, Structural Generic Constraints) Feb 15, 2017

@orthoxerox

This comment has been minimized.

Copy link

commented Feb 15, 2017

Please consider type classes on generic types as well.

@gafter

This comment has been minimized.

Copy link
Member Author

commented Feb 15, 2017

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

@orthoxerox

This comment has been minimized.

Copy link

commented Feb 15, 2017

@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

This comment has been minimized.

Copy link
Member Author

commented Feb 15, 2017

@orthoxerox It does not support higher-order generics.

@orthoxerox

This comment has been minimized.

Copy link

commented Feb 15, 2017

That's what I meant.

@louthy

This comment has been minimized.

Copy link

commented Feb 16, 2017

@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:

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

This comment has been minimized.

Copy link
Member Author

commented Feb 16, 2017

@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 comment has been minimized.

Copy link

commented Feb 17, 2017

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

@MattWindsor91

This comment has been minimized.

Copy link

commented Feb 17, 2017

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

This comment has been minimized.

Copy link

commented Feb 17, 2017

@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

This comment has been minimized.

Copy link

commented Feb 17, 2017

@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

This comment has been minimized.

Copy link
Member Author

commented Feb 17, 2017

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

This comment has been minimized.

Copy link

commented Feb 17, 2017

@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

This comment has been minimized.

Copy link
Member Author

commented Feb 17, 2017

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.

@Thaina

This comment has been minimized.

Copy link

commented Feb 18, 2017

@gafter Does this concept proposal also support anonymous concept?

Such as

public void SetPosition<T>(T pos) where T : concept{ float X,Y,Z; }
{
    x = pos.X;
    y = pos.Y;
    z = pos.Z;
}
@gafter

This comment has been minimized.

Copy link
Member Author

commented Feb 18, 2017

@Thaina You can read it for yourself; I believe the answer is "no". What translation strategy would you recommend for that?

@Thaina

This comment has been minimized.

Copy link

commented Feb 18, 2017

@gafter Direct answer like that is what I just need. I can't understand that is it yes or no. I don't really even sure that your comment was directed at me

I would not mix higher-kinded types into this issue

I still don't understand what higher-kinded types means too

@orthoxerox

This comment has been minimized.

Copy link

commented Feb 18, 2017

@Thaina the answer is no, it doesn't. Open a separate issue if you want anonymous concepts.

@Thaina

This comment has been minimized.

Copy link

commented Feb 18, 2017

@orthoxerox That's what I want. Actually I try to ask because I don't want to create duplicate issue. So I want to make sure that I could post new

@MattWindsor91

This comment has been minimized.

Copy link

commented Feb 20, 2017

(I thought I'd replied to this, but seemingly not… maybe I forgot to hit comment!)

@Thaina I'm not entirely sure I understand the anonymous concept syntax you propose, because it seems to be selecting on object-level fields/properties instead of type-level functions (Claudio's/my proposal only does the latter). This seems more like it'd be an anonymous interface?

Interop between concepts and 'normal' interfaces is another unresolved issue with our proposal. Ideally there should be a better connection between the two. The main distinction is that interfaces specify methods on objects, whereas concepts specify methods on an intermediate 'instance' structure: concepts can capture functions that don't map directly onto existing objects, but are ergonomically awkward for those that do.

@Thaina

This comment has been minimized.

Copy link

commented Feb 20, 2017

@MattWindsor91 I was really misunderstanding thanks for your clarification

@gafter gafter changed the title Champion Type Classes (aka Concepts, Structural Generic Constraints) Champion "Type Classes (aka Concepts, Structural Generic Constraints)" Feb 21, 2017

@gafter gafter modified the milestone: 8.0 candidate Mar 17, 2017

@sighoya

This comment has been minimized.

Copy link

commented Sep 20, 2018

I'm not sure what that means either. In one case you're referencing the type. In other, you're just referencing a value of that type. In either even, it's not something you are interacting with, so it's not clear to me why there's really an issue there.

default(T) incurs any cost whatever it is. It is equal to me, what is done under the hood, but I don't want to clutter this manually all the time.
For that reason, it seems that concepts and instances are preferred leaving interfaces behind.

Any language can make these decisions at the beginnign and build up everything accordingly past that point. My concern is how such a suggestion could possibly work for C# given that it's 20 years old, has tons of APIs built around it, and has billions of lines of code that depend on this sort of thing.

Yes, that is the point.

That seems like a massive massive massive breaking change. It could never be taken.

For structs, but for class objects?, aren't they always passed by reference (pass reference as value here).

@sighoya

This comment has been minimized.

Copy link

commented Sep 20, 2018

That would not work because you can't call statics off of a type parameter. There is no way to express this at even the runtime level.

Not at momentum, but how big would be the change for this?

@CyrusNajmabadi

This comment has been minimized.

Copy link

commented Sep 20, 2018

default(T) incurs any cost whatever it is.

Why would that be hte case? The runtime can certainly detect and optimize this pattern away entirely.

For structs, but for class objects?, aren't they always passed by reference (pass reference as value here).

Things are only passed by reference in C# if explicitly asked for by the user using "ref" **

--

** 7.3. changed this slightly. if you have a readonly-struct, and an 'in' parameter, then that is passed by ref implicitly. However, except for that single safe case, nothing is passed by ref unless the user specified that. Changing to a model where things are passed by ref would likely cause a break in every single codebase in the world.

@CyrusNajmabadi

This comment has been minimized.

Copy link

commented Sep 20, 2018

Not at momentum, but how big would be the change for this?

You'd have to ask the runtime. :)

@Pzixel

This comment has been minimized.

Copy link

commented Sep 20, 2018

@sighoya

In the case of primitive types you would pass by value because of better performance characteristics. In case of readonly objects, it doesn't matter.

For the case of mutable class objects, I would pass them by default by reference, so local mutations become global, but you can override this simply by an 'val' attribute additional to 'ref'.

C# Doesn't have any val keywords or so on. if you want some Sihhoya# language then you're free to clone Roslyn repo alongside with this one. But this won't work for C#

If you think, it can't work, look at julia lang, they have only structs, and the compiler can decide how to pass immutable objects, unfortunately, you don't have an optional 'val' attribute.
To the better, they only allow abstract structs to be inherit- and subtypeable, whereas plain structs are sealed classes and therefore efficient c structs.

It may work if it was designed from scratch in this way. Why take julia, we have much closer relative called Java, where you don't have structs, you have classes only, and runtime decides if it want place it onto the stack. It works like a charm, that's true. However, this is one of decision C# team has not taken, because it's not that golden as it looks like. For example, I've seen tons of tutorials about how to fool JIT and make your object be places on the stack.

I'd like to link several posts of on guy who wanted change C# as well (for who knows, I'm talking about "bad" recursive pattern matching discussions that was ones of the biggest ones in the repo history), but unfortunately insead of just freezing these posts they were been physically deleted by @gafter .

@juepiezhongren

This comment has been minimized.

Copy link

commented Sep 21, 2018

role is good enough for extension, please don't make concept support extension!!!!
#1711
just make concept only for type's extension

@narfanar

This comment has been minimized.

Copy link

commented Mar 13, 2019

Confused. How is this and the various Shape, Role, and ExtensionEverything proposals supposed to compete or complement one another?

@YairHalberstadt

This comment has been minimized.

Copy link
Contributor

commented Mar 13, 2019

They are all alternative flavours of solutions to the same basic problem.

@narfanar

This comment has been minimized.

Copy link

commented Mar 13, 2019

@YairHalberstadt , So by being tagged [proposal champion], is it currently the top proposal for this issue space?

@HaloFour

This comment has been minimized.

Copy link
Contributor

commented Mar 13, 2019

@narfanar

It means that someone from the LDM is willing to champion the topic at design meetings. It doesn't necessarily mean any one proposal is what will be implemented, or that anything will be implemented at all.

In this case the team has expressed a lot of interest in structural typing and I expect that something will happen in this space, but it's very early in the process and it's quite likely that a number of different designs will be proposed and discussed before they settle on a specific design.

@sakno

This comment has been minimized.

Copy link

commented Mar 25, 2019

I would like to share and discuss the way how to implement Type Class feature in Roslyn using Lowering technique without modification or CLR. This information is too large for the comment post so I put it into this Gist

@HaloFour

This comment has been minimized.

Copy link
Contributor

commented Mar 25, 2019

@sanko

Using reflection seems like it would be a lot more work and a lot more fragile. Not to mention that would completely preclude the ability to use extensions to satisfy the type class.

While the mechanism remains entirely up in the air I think the "witness struct" method used by the shapes proposal is probably the most flexible in that it allows the compiler to wire up the type class to the target type in a flexible manner based on whatever it finds in scope. That does rely on generic specialization on the part of the JIT as well as method inlining but it should be as efficient as a direct method call.

@sanko

This comment has been minimized.

Copy link

commented Mar 25, 2019

@HaloFour

You mean @sakno not @sanko. :) Confused me for a second.

@sakno

This comment has been minimized.

Copy link

commented Mar 25, 2019

@HaloFour

a lot more fragile

What you mean by fragile? Any backward incompatible change in public method signature can break the code even if it is compiled statically without reflection. Moreover, reflection code is generated by compiler. Source code still controlled by compiler using attributes and it can prevent compilation of concept if something was broken.

to use extensions to satisfy the type class

Not sure if it will be possible ever. Generic type instance can be created at runtime using typeof(List<>).MakeGenericType(typeof(string)). How do you imagine implementation of MakeGenericType which takes into account extension methods? What about runtime loading of assemblies with extension methods using SimpleInjector or similar mechanisms? At this moment, Reflection completely ignores extension methods. I don't expect that Reflection will ever be possible to discover extension methods.

it should be as efficient as a direct method call

It is. Calling of method that is not candidate for inlining has the same cost as with calli instruction. I guess that Invoke special method of the delegate using the same approach. My proposal contains benchmarks. Prototype implementation based on delegates, not function pointers, but it demonstrates the same performance as regular method calls. I can provide results of these benchmarks if it necessary. Anyway, calli is more efficient in comparison with delegates because you don't need to dereference pointer twice (pointer to delegate instance, then pointer to the method stored in the delegate).

If I could choose between Type Classes without extension methods or nothing then choice is Type Classes without extensions methods.

@HaloFour

This comment has been minimized.

Copy link
Contributor

commented Mar 25, 2019

@sakno

What you mean by fragile?

Compared to directly compiling against the methods. You're relying on the runtime binders to correctly identify the target methods, which may differ in behavior compared to the C# compiler itself and may enforce different accessibility rules than the C# compiler. And it involves a lot more plumbing than would be necessary to accomplish this compared to witness structs.

Not sure if it will be possible ever.

Based on the major proposals already put forth by the LDM team here, they definitely want extensions to participate with type classes (or shapes or concepts or extension interfaces, whatever they end up being called).

If I could choose between Type Classes without extension methods or nothing then choice is Type Classes without extensions methods.

The LDM has already proposed two different solutions to implement type classes which don't require CLR changes and do support extensions, so this is not an either/or proposition.

#164
#1711

@sakno

This comment has been minimized.

Copy link

commented Mar 25, 2019

@HaloFour
Can you provide precise example of fragility? Let's look at the code generated by compiler in my proposal:

typeof(int).GetMethod("Parse", BindingFlags.Static | BindingFlags.DeclaredOnly, null, new [] { typeof(string) }, Array.Empty<ParameterModifier>())

How it can be broken unexpectedly? The only way is to change Parse method in some backward incompatible way. Such change will break statically compiled code. Moreover, I don't propose to use reflection for method calling.

The LDM has already proposed two different solutions

I saw these solutions. However, it is not forbidden to offer alternative ways, right?

do support extensions

Yes, that's correct. But these proposals break Reflection, just look at the example with MakeGenericType described in my previous post. The same problem with MakeGenericMethod. Look at the translation of method T AddAll<T>(T[] ts) where T : SGroup<T> proposed by Mads. After translation, method will have two generic parameters instead of single one: T AddAll<T, Impl>(T[] ts) where Impl : struct, SGroup<T>. Such translation is not compatible with non-reflection code:

var f = new Func<int[], int>(AddAll<int>);

Obviously, this delegate cannot be created because AddAll after translation will have two generic parameters. My proposal doesn't modify signature of the original method constrained with concept type.

Anyway, your comment about extensions makes sense. I'll try to cover this feature in my proposal.

@HaloFour

This comment has been minimized.

Copy link
Contributor

commented Mar 25, 2019

@sakno

Can you provide precise example of fragility?

Two examples.

First, what if the method is an explicit implementation? Then all bets are off when it comes to name and accessibility (yes, C# follows a specific convention, but VB.NET lets you rename the method to literally anything).

Second, by using function pointers and calli aren't you bypassing virtual dispatch? What if the generated code was for a base class? IIRC that also bypasses built-in null checks which C#/CLR guarantee when using callvirt on instance members.

However, it is not forbidden to offer alternative ways, right?

Alternatives are always welcome! At this early juncture it seems that the LDM is more concerned with how these kinds of features are surfaced within the language than the implementation details. I'm not sure that I see what the benefit is between using function pointers to method handles vs. witness structs. The benefit of the latter is that the method resolution is done at compile-time so there is no cost to look them up, and breaks would fail at type-load rather than at some arbitrary point. Just seems ... simpler ... to me.

After translation, method will have two generic parameters instead of single one

Yes, that has been specifically called out in the proposals as potentially problematic. Given some hesitation around the eager generation of the witness struct it wouldn't surprise me if the declared method would have to explicitly specify the generic type parameter for the witness and potentially also pass it as the generic type argument if it cannot be inferred from usage. I wouldn't be surprised if that aspect of either proposal goes through a couple more iterations.

Either way, there seems to be a lot of interest around these features from the C# team and I expect that after C# 8.0 ships that they'll start diving into some design sessions on the subject and I'm sure that they'd be interested to explore a variety of different approaches.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.