Proposal: Add Support for Ad-hoc existential Types

[gregsn]

Being a proponent of static typing and generics, mainly for the reason of safety and code readability, I have to admit that I sometimes find it hard to understand when to actually embrace generics and when to keep things simple.

Let's pretend I'm not the only one that sometimes is unsure about the best design. And let's pretend we want to use a third party library where the library designer decided to make use of generics:

void ConsumeAB<T>(T ab) where T: IA, IB;   // let's communicate precisely what we need

we could introduce our own types that implement the required interfaces and all will work out fine.

    class ABC : IA, IB, IC { }
    class ABD : IA, IB, ID { }

    ConsumeAB(new ABC());
    ConsumeAB(new ABD());

Now, there are quite some problematic scenarios that we could come up with.

Let's pretend that we want to mix instances of ABC and ABD in a collection and then loop over them and call ConsumeAB(item);

        var items = new _QUESTIONABLETYPE_[] { new ABC(), new ABD() };
        foreach (var item in items)
        {
            ConsumeAB(item);
        }

What's the type of that collection?

Or let's say that we want to design a method that hands us a value that can be consumed by ConsumeAB();

        _QUESTIONABLETYPE_ item = ABProducer.ProduceOneByChance();
        ConsumeAB(item);

If you regard this as a legitimate problem, let me go on. Otherwise please tell me why this is not legitimate. I have the feeling that the type system is a tad unbalanced in a way that it allows to express constraints on the consumer side easier than being able to fulfill them and provide data of a type that matches the constraints.

My take on it is this: The method ABProducer.ProduceOneByChance(); should be able to output an ad-hoc existential type. It should be able to tell us "there exists a type that supports IA and IB and I'll hand you a value of such a type, but I can't tell you which type it is. It might be ABC or ABD or something you never heard of..." So it is not a type parameter in a sense that the caller would be allowed to hand over a type argument of any type that supports IA and IB.
It is more something like ∃T: IA, IB or in other words: it is an ad-hoc type intersection: something that supports IA and IB. And to avoid the notion of a type parameter waiting to be replaced by a type argument, let's just think of it like this: (IA & IB).

so this is still our library function. We are unable to change the signature of the method.

void ConsumeAB<T>(T ab) where T: IA, IB;   // let's communicate precisely what we need

but (IA & IB) is assignment compatible:

        var items = new (IA & IB)[] { new ABC(), new ABD() };
        foreach (var item in items)
            ConsumeAB(item); // fullfills the constraints
        
        (IA & IB) item = ABProducer.ProduceOneByChance();
        ConsumeAB(item);

This type would only be existent at compile time. The JIT compiler would be aware of it and would be able to check type safety. At runtime, however, we'd see instances of ABC (...): the concrete non-abstract types. So basically we just introduced anonymous, transparent, ad-hoc abstract data types, that are unlike interfaces as they don't appear in the supertype list of the concrete types, but share a certain aspect with interfaces: they are abstract data types and therefore GetType() will never report such a type.

And I think this would be a reason to be very happy as all sorts of equality and identity issues do not arise. No wrappers involved...

Now, what's the output type of ProduceOneByChance?

Here are two options:

(IA & IB) ProduceOneByChance(); // let's focus on the intersection of ABC and ABD

(ABC | ABD) ProduceOneByChance(); // no eager intersection of supertypes

it would be great if both would be possible.

(ABC | ABD) x = ProduceOneByChance();
(IA & IB) item = x;  // fine:  all union cases ABC and ABD support IA and IB

Let's call (ABC | ABD) an ad-hoc type union for now, which is not the same as a union type like seen in F#. Again at runtime, these types don't exist. Again GetType() will return ABC or ABD.

We could also imagine to directly work with the union type like this:

typeswitch (item)
{
   ABC abc: abc.C();
   ABD abd: abd.D();
   IA a: a.A(); // fallback
}

But these are language details and optional.

The most important point of the proposal is that none of this can be done without some support by the underlying type system.
This proposal is about symmetry. We have to admit that we have a yet unbalanced type system that allows us to introduce constraints that have the potential to turn beautiful precise code into a barely usable piece of functionality as we can't fulfill the constraints in certain cases.

---

Note: Working around the issue by introducing a wrapper type that supports the needed interfaces is not the same. The consuming method might still want to check for certain additional interfaces like seen here: https://github.com/dotnet/corefx/blob/master/src/System.Linq/src/System/Linq/Count.cs

By building a wrapper that supports the needed interfaces IA and IB we lose the runtime type information and a check for IC and ID will always fail. We'd also need to get dirty and rethink equality and identity when comparing original and wrapped objects in certain scenarios.
And suddenly we are just fighting with the type system, which is not its original purpose.

[NinoFloris]

Makes me think of roles dotnet/csharplang#1711

[jakobbotsch]

See also dotnet/csharplang#1328

[gregsn]

@NinoFloris:

Makes me think of roles dotnet/csharplang#1711

It would be nice to hear where you see the connection. On parts of how it could get implemented or on a conceptional level?

Roles: Lightweight "transparent wrapper types" that can be applied to individual objects of a given type, can add additional members to them [...]

On a conceptional level, I think they are quite different: Roles are introducing new nominal types and allow to add members to existing types, ad-hoc existential types don't add new named types and don't allow to add members to existing types.
The idea here is more about combining types in a way that you don't have to go for one supertype (and by that lose the information that all producers actually implement several interfaces). Instead of being forced to focus on one supertype e.g. in an array IA[], you now can focus on many supertypes at the same time. (IA & IB)[].

@jakobbotsch

See also dotnet/csharplang#1328

Interesting read! And another take on what existential types can look like. Interestingly a completely different use-case where it's about type crafting. Where here it's more about being able to pipe data in a way that you don't lose type information.

---

Note: in the above code one could just use dynamic as a replacement for the QUESTIONABLETYPE and it would work. But that's like opting out of the static type system and by that not a fair suggestion for anyone interested in static typing and generics.

[ghost]

Due to lack of recent activity, this issue has been marked as a candidate for backlog cleanup. It will be closed if no further activity occurs within 14 more days. Any new comment (by anyone, not necessarily the author) will undo this process.

This process is part of our issue cleanup automation.

[ghost]

This issue will now be closed since it had been marked no-recent-activity but received no further activity in the past 14 days. It is still possible to reopen or comment on the issue, but please note that the issue will be locked if it remains inactive for another 30 days.