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.
-
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). ↩
Top comments (2)
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?
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:Note that I've removed the
<T>
declaration after the name ofDeserializeList
, but the function still returns anIList<T>
. This would currently generate a compiler error, but we could instead safely (I think) interpret the returnedIList<T>
to be existentially quantified. Basically, this would mean "I give you back anIList<T>
, but you can't know whatT
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.