Immutability in C# Part Three: A Covariant Immutable Stack
Now suppose we had a hypothetical future version of C# in which interface covariance worked, and we wanted a covariant immutable stack. That is, we want to be able to implicitly convert an IStack<Giraffe> to IStack<Mammal>. As we've already discussed, this doesn't make much sense in an array, even though doing so is legal in C# today. If you cast a Giraffe[] to Mammal[] then you can try to put a Tiger into the Mammal[] and it will fail at run time. It seems like the same should be true of stacks -- if you cast an IStack<Giraffe> to IStack<Mammal> then you can push a Tiger onto the stack of Giraffes, which should fail, right?
Maybe. Maybe not.
The interface we defined the other day is not suitable for covariance because it uses the variant parameter as both an input and and output. Let's get a bit crazy for a minute here -- suppose we got rid of the input on the Push:
public interface IStack<+T> : IEnumerable<T>
{
IStack<T> Pop();
T Peek();
bool IsEmpty { get; }
}
This interface is now suitable for covariance. If you have a stack of Giraffes and you want to treat it as a stack of Mammals, you can do so with perfect type safety, since we know that we will never be pushing a Tiger onto that thing. We'll only be reading off Giraffes, all of which are Mammals. This may seem less than useful, but we'll see what we can do:
public sealed class Stack<T> : IStack<T>
{
private sealed class EmptyStack : IStack<T>
{
public bool IsEmpty { get { return true; } }
public T Peek() { throw new Exception("Empty stack"); }
public IStack<T> Pop() { throw new Exception("Empty stack"); }
public IEnumerator<T> GetEnumerator() { yield break; }
IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); }
}
private static readonly EmptyStack empty = new EmptyStack();
public static IStack<T> Empty { get { return empty; } }
private readonly T head;
private readonly IStack<T> tail;
private Stack(T head, IStack<T> tail)
{
this.head = head;
this.tail = tail;
}
public bool IsEmpty { get { return false; } }
public T Peek() { return head; }
public IStack<T> Pop() { return tail; }
public static IStack<T> Push(T head, IStack<T> tail) { return new Stack<T>(head, tail); }
public IEnumerator<T> GetEnumerator()
{
for(IStack<T> stack = this; !stack.IsEmpty ; stack = stack.Pop())
yield return stack.Peek();
}
IEnumerator IEnumerable.GetEnumerator() {return this.GetEnumerator();}
}
Notice that Push has disappeared from the empty stack and is static on the nonempty stack, and hey, check it out:
IStack<Giraffe> s1 = Stack<Giraffe>.Empty;
IStack<Giraffe> s2 = Stack<Giraffe>.Push(new Giraffe("Gerry"), s1);
IStack<Giraffe> s3 = Stack<Giraffe>.Push(new Giraffe("Geoffrey"), s2);
IStack<Mammal> s4 = Stack<Mammal>.Push(new Tiger("Tony"), s3);
Oh my goodness, we just pushed a Tiger onto a stack of Mammals that is actually a stack of Giraffes underneath, but everything is still typesafe! There is nothing we can do here to cause an exception at runtime in the type system. It all just works. All the stacks of Giraffes continue to be stacks of Giraffes; they're immutable, so they could hardly be anything else.
This code is pretty ugly though. So...
public static class Extensions
{
public static IStack<T> Push<T>(this IStack<T> s, T t)
{
return Stack<T>.Push(t, s);
}
}
and now we can say
IStack<Giraffe> sg1 = Stack<Giraffe>.Empty;
IStack<Giraffe> sg2 = s1.Push(new Giraffe("Gerry"));
IStack<Giraffe> sg3 = s2.Push(new Giraffe("Geoffrey"));
IStack<Mammal> sm3 = sg3; // Legal because of covariance.
IStack<Mammal> sm4 = sm3.Push(new Tiger("Tony"));
Is that slick or what?
Next time: what about an immutable queue?
Comments
Anonymous
December 06, 2007
Couldn't we do: public interface IStack<+T> { ... all the stuff you already have... IStack<U> Push<U>(U u) where T : U; } public sealed class Stack<T> : IStack<T> { ... all the stuff you already have... public Stack<U> Push<U>(U u) where T : U { return new Stack<U>(u, this); } } (notice the sneaky way I just presumed the existence of return-type covariance in this future hypothetical C# version ;) Of course it works equally well if the method in Stack returns IStack<U> instead)Anonymous
December 06, 2007
does that mean that sg3.Push(new Tiger("Tony")) would be legal and that the compiler will automatically deduce that the result is of type IStack<Mammal>, finding Mammal from the given Giraffe and Tiger types? It would be nice, too.Anonymous
December 06, 2007
Stuart: you also sneakily added in another feature not currently in C#, namely constraining the type variable U to be a supertype, not a subtype. Yes, if we had return type covariance on virtual overloads/interface implementations AND supertype constraints AND interface variance, then this would all work. In Scala, which has all those features, you can do exactly that.Anonymous
December 06, 2007
> the compiler will automatically deduce that the result is of type IStack<Mammal>, finding Mammal from the given Giraffe and Tiger types? No, that is not a feature that we want to add to C#. One of the guiding principles of our type inference design is "the type inferrer deduces the best of a set of given types; it never picks a type as "best" which is not in the input set". In this case we would have the set { Giraffe, Tiger } and be unable to pick a best type from that. That is why in my examples I made sure that the type was either explicitly mammal, or that we were picking from the set {Mammal, Tiger}, which has an unambiguous best type of Mammal. Some languages (Java, eg) will attempt to deduce a type not in the input set, but we do not want to go there. It greatly complicates the inference rules, which are already rather complicated.Anonymous
December 06, 2007
I'm not sure I follow the example, Eric. When you write: <quote> Oh my goodness, we just pushed a Tiger onto a stack of Mammals that is actually a stack of Giraffes underneath, but everything is still typesafe! There is nothing we can do here to cause an exception at runtime in the type system. It all just works. </quote> Do you mean that it should cause an exception, and indeed does, or that due to the immutability (i.e. we're actually always creating "new" stacks) we're okay without any exceptions? JonAnonymous
December 06, 2007
I mean that in a world where IStack<+T> is legal, the code above would just work as you'd expect and be perfectly typesafe. Because it IS perfectly typesafe. The only reason that array covariance is broken is because arrays are mutable. Since immutable stacks are immutable, stack covariance is perfectly safe.Anonymous
December 06, 2007
Good, that's what I'd hoped :) The point being that the stack of giraffes is still a stack of giraffes and can never contain anything else because it can never change at all - so appearing to add a tiger doesn't change the view of the world for clients which only have the original stack. I think I'm with it now :) JonAnonymous
December 06, 2007
It is 1 A.M. and you made me read this post, with sleep gone away. ;) I'll have to dig up my lost C++ skills to see if I can come up with something similar with templates. After all, they are compile-time UTM! C++ already has covariant return types for virtual functions, templated conversion operators should take care of supertype conversions and immutables datastructures aren't any big deal. Only thing missing from the picture is constraints.Anonymous
December 06, 2007
I can mentally extrapolate the workings of immutable versions of most traditional data structures based on what you've shown with the stack... At least all the "linear" ones. What I'm really curious about is some good ways to create an immutable tree. It seems like building a useful immutable tree would be a lot more challenging. For one thing, the structure can diverge at any point, rather than only at the end. This reveals the limitation of this sort of immutability you have been illustrating: it makes incremental adding and removing very easy, but to insert or remove data at some middle point can be much more complex, and may necessitate breaking the "sharing". This type of mid-structure change is such a critical operation for trees that, if it can't be done without breaking "sharing", then I wonder whether many of the benefits of immutability still apply in most tree use cases.Anonymous
December 06, 2007
Sweet, but we want Push to be on IStack, don't we?Anonymous
December 06, 2007
The comment has been removedAnonymous
December 06, 2007
I'll do immutable trees after immutable queues.Anonymous
December 06, 2007
The comment has been removedAnonymous
December 06, 2007
The comment has been removedAnonymous
December 06, 2007
> IStack<Mammal> sm4 = sm3.Push(new Tiger("Tony")) is actually > IStack<Mammal> sm4 = sm3.Push<Tiger>(new Tiger("Tony")) > because the type is inferred from from type of the parameter that the method is called with Nope. Did you actually try it? (Obviously the covariant conversion will not work, but this call will.) Hint: the type argument for the generic method is inferred from more than just the "new Tiger" parameter.Anonymous
December 06, 2007
The comment has been removedAnonymous
December 12, 2007
Will the hypothetical covariant C# have a way of enforcing covariantability (is that a word)? For example, would it be possible to add a "covariant" keyword to a type definition, and then have the compiler enforce that all operations in that type are covariant?Anonymous
December 12, 2007
Yes. I just wrote a ten part series of blog posts on exactly that subject.Anonymous
December 13, 2007
So you did :) Looks like I have a lot more reading to do.Anonymous
December 18, 2007
Hi, em i try ur code Where to put this code below,so the code can work: public static class Extensions { public static IStack<T> Push<T>(this IStack<T> s, T t) { return Stack<T>.Push(t, s); } } IStack<+T> , + is unexpected token how come + generate error is this for .net 2.0 or not? Please give me a complete listing code, so i can follow this one, i've followed your part one and two and success.Anonymous
December 19, 2007
The point of this was that IF we add covariance to the language in some future version, THEN this would work. We have not yet added covariance, so this does not work. See my recent ten part series on covariance for more details.Anonymous
January 16, 2008
For some reason, there's been a lot of buzz lately around immutability in C#. If you're interested inAnonymous
October 17, 2008
The comment has been removedAnonymous
December 18, 2008
So nicely step by step blogged by Eric Lippert for "Covariance and Contravariance" as "Fabulous