csharplang

csharplang copied to clipboard

• [ ] 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 https://github.com/dotnet/roslyn/issues/16312
• https://github.com/dotnet/csharplang/blob/main/meetings/2022/LDM-2022-09-26.md#roles--extensions

/cc @MattWindsor91

Please consider type classes on generic types as well.

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

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

@orthoxerox It does not support higher-order generics.

That's what I meant.

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

@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"?

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

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.

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

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

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.

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

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.

@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;
}

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

@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

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

@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

(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.

@MattWindsor91 I was really misunderstanding thanks for your clarification

HKT emulation via associated types is included in the new prototype: https://github.com/MattWindsor91/roslyn/blob/2017-stable/concepts/docs/writeup.docx

@orthoxerox Thanks for the mention! @crusso and I still actively working on the prototype until the 27th.

Some things that would normally use HKTs can indeed be mocked up using associated types. (See the various implementations of LINQ methods in /concepts/code/TinyLinq/TinyLinq.Core 😀). I’ve found a few issues with this approach in the prototype:

1. This encoding balloons to a lot of type parameters (both normal and associated). In the prototype, associated types are just normal type parameters syntactically, which means there’s a huge cascade of them all the way down from the concepts where they’re actually fixed through any derived instances. See SelectMany’s instances for the nightmare scenario. Some clever syntax might make this less horrendous though...!
2. More an implementation issue, but encoding HKTs using ATs makes inference very tricky to do right. Again, SelectMany over enumerables, as encoded in the prototype, is a good (horrible) example: we need to do a round of concept inference to get the AT corresponding to the input collection’s element type, then output inference to get the type of the collection coming out of the collection selector function, then more concept inference to get that collection’s element, then output to get the result type, and all of this has to happen in the context of working out an instance for the SelectMany concept.

I apologise for the horrors within the prototype implementation of that back-and-forth-switching-with-backtracking inference scheme 😰. There are still a few consistency issues I haven’t worked out.

@MattWindsor91 How'd it go? Very curious in the progress of it all :)

@MattWindsor91

Well, may be I'm suggesting a stupid idea or something that ends to be technically impossible. All in all, what if concepts will be passed using single generic parameter, something alike

void Process<T, implicit TConcept>(T state) where TConcept: struct, LogConcept, MathConcept
{
    Log(Increment(state));
}

?

This should solve your issue with explosion of concepts in generic args.

Undercover Concept1 and Concept 2 are interfaces with default method implementations, TConcept is emitted by compiler and looks like

struct c<>_bla-bla-bla: IMathConceptImpl<int>, ILogConceptImpl<string> {}
// no methods here, taken from default implementations in interfaces

(yes, there is a set of such dummy structs for each assembly. Like it was done for anonymous types).

There is no penalty for calls or boxing as JIT is smart enough to emit effective assembly instructions for constrained. interface calls over TStructs. Random googled example.

Of course there is need to be a syntax for concept impl resolution on caller-side and TConcept method resolution on end-side. Both are a just a syntax issues and I do not think it has to be a major problem.

It looks like concepts will poison long chains of generic method calls. As far as I can see there's no way to call a concept method from normal generic method, ala

void SomeCode<T>(T state) => Process(state);

To enable such scenarios there should be a support for dynamic concepts

void SomeCode<T>(T state) => dynamic Process(state);

or may be some specialized api|syntax that will allow to improve performance for such calls via emitting and caching call wrappers.

@MattWindsor91, @gafter Have you given any thought to instance coherence / overlapping instances?

One of the advantages of (at least Haskell 98/Haskell 2010) typeclasses as opposed to the various typeclass-like implicit dictionary mechanisms in other languages is that the design encourages coherence: whichever path through discovers an instance is guaranteed to be as good as any other (e.g. (Eq a => Ord a) and (Ord a => Ord [a]) gives a path to Ord [a], but so does (Eq a => Eq [a]) and (Eq [a] => Ord [a]) and it does not matter which one the compiler chooses.

For those following along: Edward Kmett's Typeclasses vs The World talk outlines from a practitioner's perspective why coherent typeclasses are more usable than implicit dictionaries.

@MattWindsor91 I have the feeling that you do not introduce typeclasses directly into C# rather indirectly via "modules" (modular type classes), such that concepts are signatures and c# structs/instances implementing concepts are modules. Advantages are that modules (though we need support for functors) are more powerfull than the typeclass system in Haskell and solve additionally some problems that Haskell have with type classes (global uniqueness problem) Disadvantages are that they harder to understand and the syntax is more verbose than for normal typeclasses.

What was your intention for? Elimination of the global uniques problem in Haskell?

Sorry for the ignorance, but can someone clarify this for me:

1. How is this related to #164? Does this proposal make it possible to implement Mads' extension proposal on top of it? I mean, in relation to #164, is this just a different way to implement type classes into C# or is this another thing entirely? As I understood (and I don't feel I've really understood this), this issue, in relation to Mad's, just proposes implementing type classes in a more optimized manner. But, in the end, mad's proposal could easily be built on top of this. Is this understanding right?

Edit: There's actually a side-by-side comparison of Mad's proposed code to concept-c# code at Concept-C# repo

2. Will following this route [of implementing type classes via compiler tricks] make implementing HKP with CLR support in an ideal future easier, harder or indifferent? I mean, in a future where you decide to fully support HKP, will this proposal be looked upon as a necessary building block or as a "bad design decision that seemed good at the time"? Personally, I'd rather have this and HKP with CLR support in 5 years as opposed to having this only, but now.

Again, sorry for any lack of knowledge. It is already quite difficult to follow along all the FP math, but it is way harder when you throw compiler, runtime, spec/syntax magic into the mix.

2. This is completely orthogonal to higher-kinded-types. I don't think having it would make it either easier or harder.