loading...

Existentially quantified types in C#

shimmer profile image Brian Berns ・3 min read

Emulating first-class polymorphism

Last time, we talked about universally quantified types and the challenge of passing a generic function to a non-generic function. The best way to do this is with a non-generic interface that contains one or more generic methods. This allows us to limit the scope of the type variables to each method. In our case, we can define an interface that represents operations on generic lists:

interface IListOperations
{
    int GetWeight<T>(IList<T> items);   // scope of T is limited to GetWeight
    // ... other methods with other type variables
}

At the moment, we only have one such operation, GetWeight, but we could add more in the future. We can then modify our SumWeights function to take an IListOperations:

static int SumWeights(
    IList<int> ints,
    IList<string> strs,
    IListOperations listOps)
    => listOps.GetWeight(ints) + listOps.GetWeight(strs);

This technique is a bit more verbose than a plain function, but it effectively supports universally quantified function types. (Shout out to @costinmanda for digging into this problem in the comments!)

Deserialization challenge

Now let's switch to a different, more unusual, problem. Imagine that we have a file that contains a list of serialized objects, all of the same type. For example, we might store a list of circles like this:

MyNamespace.Shapes.Circle
Origin=(3,4), Radius=5
Origin=(-2,3), Radius=7
...

And we might store rectangles like this:

MyNamespace.Shapes.Rectangle
TopLeft=(0,3), BottomRight=(3,0)
TopLeft=(1,1), BottomRight=(4,-3)
...

The file format itself doesn't really matter, so don't get hung up on why it's not CSV, JSON, or XML. What's important is that we can use the format to store a list of values of any relevant type.1

How would you design an API to deserialize the contents of such a file? You might start with something like this:

static IList<T> DeserializeList<T>(string path)
{
   // implementation
}

var circles = DeserializeList<Circle>("Circles.txt);
var rectangles = DeserializeList<Rectangle>("Rectangles.txt");

This works great, but only if you know the type contained in each file ahead of time. What if you need to be able to deserialize an arbitrary file without knowing the type of objects it contains at compile-time?

var values = DeserializeList<???>("Arbitrary.txt");

We could potentially use obj as the type variable, so that values is of type IList<obj>:

IList<obj> values = DeserializeList<obj>("Arbitrary.txt");

The problem with this approach is that an IList<obj> (or a non-generic IList) could contain a mixture of different types of objects. We don't want to lose the fact that all the values in a given file are in fact of the same type. Is there a way to represent this in C#?

Existentially quantified types

Ideally, we'd want to write the signature of DeserializeList like this:

static T.IList<T> DeserializeList(string path)   // not legal C#
{
   // implementation
}

We've introduced ∃T., which means "there exists a type T", so ∃T.IList<T> is a generic list containing items of some unspecified type. We call ∃T.IList<T> an existentially quantified type. Note that we no longer pass a type parameter to DeserializeList at all, since there's no way to know the actual type that T represents at compile-time.

Obviously, existential types are not directly supported by C#. But is there a way to emulate them using universal types instead? The answer is yes, but the solution is not at all obvious. We'll cover it next time.


  1. Note that the first line of the file contains the name of the stored type. We can use this metadata to dynamically instantiate the type at runtime (via reflection or some other mechanism). 

Discussion

pic
Editor guide
Collapse
integerman profile image
Matt Eland

What syntax would you recommend if it were supported? I can't expect you think users should type nonstandard characters in regular use. Is there a keyword that might make more sense?

Collapse
shimmer profile image
Brian Berns Author

This is a good question. We could introduce a keyword like exists for existential quantification, but I don't it would actually be necessary. Imagine if we could declare a function like this:

IList<T> DeserializeList(string path) { /*impl*/ }

Note that I've removed the <T> declaration after the name of DeserializeList, but the function still returns an IList<T>. This would currently generate a compiler error, but we could instead safely (I think) interpret the returned IList<T> to be existentially quantified. Basically, this would mean "I give you back an IList<T>, but you can't know what T actually is at compile-time."

Someone who knows more about the C# compiler and type theory could probably give a better answer than me, though. In practice, existential types can be converted to universal types with some effort (as we'll see in the next post), so we do have a workaround for now.