[Proposal]: Associated Types

# Practical existential types for interfaces

* Specification: None yet, see below
* Discussion: https://github.com/dotnet/csharplang/discussions/8710, https://github.com/dotnet/csharplang/discussions/8711

***Terminology note: What's called "existential types" in this proposal is more correctly called "associated types" in other languages. The previous proposal, referenced below, did not have the same restrictions and thus implemented something much closer to a pure existential type without type erasure. This proposal is more restrictive and doesn't support using interfaces with associated types in all locations. You can think of every mention of "existential type" in this proposal as meaning "associated type."***

## Intro

Previously I (@agocke) [proposed](https://github.com/dotnet/csharplang/issues/1328) adding some form of existential types to C#. In that proposal, I describe existential types at a high level and describe how some features could be added to C#. However, I didn't propose any particular implementation strategy and left many questions open, including the mechanism for enforcing type safety.

In this proposal I will describe a full implementation and type safety mechanism, as well as a metadata representation.

To start, the syntactic presentation. I propose that existential types be represented as abstract type members of interfaces. For example,

```C#
interface Iface
{
// Existential type
type Ext;

public Ext P { get; }
}
```

The existential type is substituted when the interface is implemented, e.g.

```C#
class C : Iface
{
type Iface.Ext = int;

public int P => 0;
}
```

This syntax is similar to other languages with existential types and provides a clear separation from existing type parameters on types.

This syntax also emphasizes the differences described in the earlier proposal: unlike regular type parameters, which are provided by the creator of a type, existential types are provided by the implementer of the interface and are invisible at type creation.

> **Note**: Some alternate syntaxes include

> 1. `interface IFace` (this was the syntax I used in my first proposal
> 2. `interface IFace`
> 3. `interface IFace`
> 4. `interface IFace|`

This does raise the question left open in the previous proposal: how to define type equality. Since each interface implementation may have a unique subsitution for the existential type, type equality depends on the exact type of the implementation. Notably, the interface itself is not an implementation, so the following would not type check:

```C#
void M(Iface left, Iface right)
{
var x = left.P;
x = right.P; // error, left.P and right.P may not be the same type
}
```

Worse, the type of `x` is difficult to express in the language, as-is. It is in some sense a type parameter, but there isn't a named type parameter in scope to use to refer to it. Inside the interface we call it `Iface.Ext`, but this is not actually a type, it is a type parameter. The actual type is whatever was substituted by the implementation. In the case of our example `C` above, the type is `int`.

However, we can improve the power of the feature using a different feature: existing C# generics. If we avoid using the type parameter as a type, and instead use it as a constraint, things get simpler:

```C#
void M(T left, T right)
where T : Iface
{
var x = left.P; // `var` could be type `T.Ext`
x = right.P; // type checks
}
```

With this usage, we can be confident that the implementations will produce "compatible" types. This leads to the following proposal: interfaces with type members should only be usable as generic constraints. With this restriction, we can treat type members as relatively standard C# types, usable in the places where type parameters would be permitted. That this is type safe may not be obvious, but the proposed reduction to existing .NET metadata will verify that the resulting code is type safe.

## Motivating example

The examples above demonstrate simple usages, but don't give an example of practical advantages. One opportunity is improved optimizations. Consider LINQ. As Jared Parsons described in a [blog post](https://blog.paranoidcoding.com/2014/08/19/rethinking-enumerable.html), two of the biggest weaknesses of `IEnumerable` are the repeated interface dispatches, and the abstraction of the enumerator type. As he describes, we could improve the pattern using generics:

```C#
public interface IFastEnum
{
TEnumerator Start { get; }
bool TryGetNext(ref TEnumerator enumerator, out TElement value);
}
```

One big problem with this pattern is it makes the enumerator into either an additional type parameter which needs to be manually propagated, or public surface area. This is a job much better left to the compiler. This is how it could be written with existential types:

```C#
public interface IFastEnum
{
type TEnumerator;
TEnumerator Start { get; }
bool TryGetNext(ref TEnumerator enumerator, out TElement value);
}
```

The enumerator type is now appropriately elided for everyone except the implementor. A user might write

```C#
void M(TEnum e) where TEnum : IFastEnum
{
foreach (var elem in e)
{
Console.WriteLine(elem);
}
}
```

This is more verbose than not using generics, but that is a more general concern about verbosity of generics.

And on the implementor side, it would look like this:

```C#
class List : IFastEnum
{
type IFastEnum.TEnumerator = int;
int Start => 0;
public bool TryGetNext(ref int enumerator, out TElement value)
{
if (enumerator >= Count) {
value = default(TElement);
return false;
}

value = _array[enumerator++];
return true;
}
}
```

This is much the same code that Jared wrote, and should provide the same performance benefits.

## Compilation

In the previous proposal, I described a lowering strategy based on logic theorems around existential and universal type equivalence. This technique is powerful and flexible, but much more complicated and difficult to implement. The above design has substantial limitations on how existential types can be used, therefore the implementation can be much simpler. If these limitations prove too onerous in the future, some restrictions may be loosened with a more complex compilation strategy.

The proposed compilation strategy is broadly quite simple: turn existential types into hidden generic parameters. This may seem extreme, but note that the language rule for type members requires the interface which contains them to only be used as constraints. This means that compilation may _add_ generic parameters, but it will never make a method generic which wasn't before, and the type parameters will not spread past the introduction of the constraint.

Here's a simple example of the code before and after.

Before:

```C#
interface Iface
{
type Ext : IDisposable;

Ext P { get; }
}
class A : Iface
{
type Ext = MemoryStream;

MemoryStream P => new MemoryStream();
}
void Dispose(T t)
where T : Iface
{
t.P.Dispose();
}
Dispose(new A());
```

After:

```C#
interface Iface
where Ext : IDisposable
{
Ext P { get; }
}
class A : Iface
{
MemoryStream P => new MemoryStream();
}
void Dispose(T t)
where T : Iface
{
t.P.Dispose();
}
Dispose(new A());
```

The important transformations are:

1. Type members become additonal type parameters on the interface.
1. Constraints on type members become constrains on the interface.
1. Type member assignments in the implementation become type substitutions
in the interface implementation.
1. In all places where type parameters are declared with constraints to interfaces
with type members, all type members must be added to the parameter list.
1. At all callsites with synthesized type parameters, the correct type arguments must be
inferred.

Most of the transformations are simple, but the synthesizing and inferring of type parameters may be worth some elaboration.

First, we need to establish what is necessary for inference. To do so, we need to determine which synthesized type parameters "belong" to which type parameter. This should be doable using synthesized attributes or modreqs to point to the "owning" parameter's index.

Once we know the owning parameters and the synthesized parameters, we can temporarily remove the synthesized parameters and perform type inference as currently specified in C#, or use the manual substitutions. Once the substitution is identified, we can identify the substitutions for the synthesized parameters. First, identify the needed interface by walking the constraint list in order. Next, determine the substitutions in the interface implementation. As currently proposed, the syntax only allows for a single implementation of a given interface for a given type. By searching types from most to least derived for the first implementation of the target interface, we can identify the substitutions on the argument. By matching the substitutions of the argument with the synthesized type parameters, synthesized type arguments can be generated.

The process above can be repeated for all type definitions and substitutions.

- [ ] **Open question**

Consider also banning re-implementation of the same interface across inheritance. It's not a type safety violation (and therefore shouldn't need a runtime check), but it could lead to confusing behavior on which implementation is chosen, especially since it is always fully inferred.

## Conclusion

**Advantages**

* Relatively simple to implement and explain
* Provides full performance benefits
* Compact metadata representation

**Drawbacks**

* More complexity in generics in C#
* Generics are different in metadata vs. source
* Other languages have to implement encoding/decoding separately

## Design Meetings

https://github.com/dotnet/csharplang/blob/main/meetings/2022/LDM-2022-02-16.md#practical-existential-types-for-interfaces