Immutability in C# Part Three: A Covariant Immutable Stack

Immutability in C# Part Three: A Covariant Immutable Stack

Rate This
  • Comments 24

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?

  • 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)

  • 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.

  • 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.

  • > 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.

  • 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?

    Jon

  • 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.

  • 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 :)

    Jon

  • 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.

  • 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.

  • Sweet, but we *want* Push to be on IStack, don't we?

  • WaterBreath: There are tons of immutable tree demos on the web.  Google for it and I'm sure you can find a powerpoint or flash animation showing you exactly how it works.

  • I'll do immutable trees after immutable queues.

  • 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"));

    This doesn't work !!! Because :

    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

    but inside the constructor you'll have

    private Stack(T head, IStack<T> tail)

           {

               this.head = head;

               this.tail = tail;

           }

    is

    private Stack(Tiger head, IStack<Tiger> tail)

           {

               this.head = head;

               this.tail = tail;

           }

    abd you call the constructor with this call

    Stacknew Tiger(("Tony"), sm3) ... sm3 is sg3 witch is an IStack<Giraffe> so you bassically pass to to a constructor taking a tiger and a IStack<Tiger> and IStack<Giraffe> ... wich violates type safety.

  • it's 4:30 AM where I live but this ideea just pierced through my brain, because I can't sleep

    This is how you can have covariance in .Net

    let's say you want a method that pushes an animal in a queue and pops another one from the same queue

    1)

    public Animal Foo<Animal+>(Queue<Animal> queue) {

      Animal an = new Animal();

      queue.push(an);

      return queue.Pop();

    }

    what can you do to make the method work by passing an Queue<Giraffe>? this is the ideea

    the method above should exactly equivalent with :

    2)

    public Animal Foo<T>(Queue<T> queue) where T: Animal, new() {

      T an = new T();

      queue.Push(an);

      return queue.Pop();

    }

    so now the first method can be called with an Queue<Giraffe>

    Foo<Animal+>( new Queue<Giraffe)  // works because Animal+ is a T generic parameter that is of Animal type.

    Also this means if you write Bar<SomeType+> you don't create a closed generic definition but an open one and the instantiation is only when the method is called with a certain type.

    Also you need to allow references to open generic types, for example

    Queue<Animal+> q = new Queue<Giraffe>();

    this is a reference to Queue<T> where T: Animal like so (a reference to an open generic type)

    Queue<T> where T: Animal q = new Queue<Giraffe>(); //  ****** just like an object reference can point to any type instance and reference to an open generic type should be able  to point to any type constructed from  it ******

    so now

    when the method Foo<Animal+>(...) is called

    var x = Foo( new Queue<Tigger>()); //x is inferred as Animal

    The whole point is:

    -  with those 2 things :

    * allowing references to open generic types to be assigned with constructed types

    Another ex:

    List<Animal+> l1, l2; List<Animal+> is List<T> where T: Animal

    l1 = new List<Giraffe>;

    l2 = new List<Monkey>

    * Covariant and contravariant parameters should create open generic types not closed ones.

    is all that is needed to have covariance in .Net

    P.S.

    public Animal+ Foo<Animal+> (Queue<Animal> queue) should be

    equivalent with :

    public T Foo<T>(Queue<T> queue) where T: Animal

    P.S. doing this mental exercise i've found that .Net already has half the necesary things for covariance to work (  open generic methods already are covariant or contravariant...I hate those terms really)

  • > 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.

Page 1 of 2 (24 items) 12