Immutability in C# Part Two: A Simple Immutable Stack

Immutability in C# Part Two: A Simple Immutable Stack

Rate This
  • Comments 61

Let’s start with something simple: an immutable stack.

Now, immediately I hear the objection: a stack is by its very nature something that changes. A stack is an abstract data type with the interface

void Push(T t);
T Pop();
bool IsEmpty { get; }

You push stuff onto it, you pop stuff off of it, it changes. How can it be immutable?

Every time you need to make a data structure immutable, you use basically the same trick: an operation which “changes” the data structure does so by constructing a new data structure. The original data structure stays the same.

How can that possibly be efficient? Surely we’ll be allocating memory all over the place! Well, actually, in this case, no. An immutable stack is every bit as efficient as a mutable stack. Even better: in some cases, it can be considerably more efficient, as we'll see.

Let’s start by defining an interface for our immutable structure. While we’re at it, we’ll fix a problem with the stack ADT above, namely that you cannot interrogate the stack without changing it. And we’ll make the stack enumerable just for the heck of it:

    public interface IStack<T> : IEnumerable<T>
    {
        IStack<T> Push(T value);
        IStack<T> Pop();
        T Peek();
        bool IsEmpty { get; }
    }

Pushing and popping give you back an entirely new stack, and Peek lets you look at the top of the stack without popping it.

Now let’s think about constructing one of these things here. Clearly if we have an existing stack we can construct a new one by pushing or popping it. But we have to start somewhere. Since every empty stack is the same, it seems sensible to have a singleton empty stack.

    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> Push(T value) { return new Stack<T>(value, this); }
            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 IStack<T> Push(T value) { return new Stack<T>(value, this); }
        public IEnumerator<T> GetEnumerator()
        {
            for(IStack<T> stack = this; !stack.IsEmpty ; stack = stack.Pop())
                yield return stack.Peek();
        }
        IEnumerator IEnumerable.GetEnumerator() {return this.GetEnumerator();}
    }

And now we can easily create stacks and push stuff onto them. Notice how the fact that we have immutability means that stacks with the same tail can share state, saving on memory:

IStack<int> s1 = Stack<int>.Empty;
IStack<int> s2 = s1.Push(10);
IStack<int> s3 = s2.Push(20);
IStack<int> s4 = s2.Push(30); // shares its tail with s3.

Painless. Next time: a variant variation on this theme.

  • I think silky was objecting to:

     this.s = this.s.Push(...);

    rather than just:

     this.s.Push(...);

    Given the advantages that immutability gives you when thinking about systems in flight I think the tiny bit of extra syntax is a very small code tax.

  • If that is really your concern then you are clearly not yet in the "immutable" mindset. Why would you change the value of a member variable? Design the system so that the "variable" is immutable, and you never need to worry about changing it!

  • I'd love to see such immutable objects in the framework soon. The implementation is that easy and straight-forward and it's so nice to work with immutable things when doing parallel stuff. It's really a very important requirement (in addition to the parallel extenstions) of .net to be successfull in the future where heavy parallelism is as important as oop.

    If someone really can't live with the IMO clean distinction between pop and peek, it's as easy as one simple extension method to have what you want:

    public static IStack<T> Pop(this IStack<T> stack, out T value)

    {

       value = stack.Peek();

       return stack.Pop();

    }

  • Tom: Yes, that's what I mean.

    Eric: Look at what tom has done; his usage there shows that he's kind of bypassed the point of your immutable stack. From his apps perspective "this.s" is not immutable. It changes because it's constantly re-assigned to something new.

    The point is that he still needs to use the stack in a non-immutable fashion (i.e. changes need to be reflected in other parts of the code, etc).

    My point was that an immutable stack is fine (I understand the concept) but it still requires you to use it differently (which you could do just as fine with a regular stack). The only difference is that it forces you to. Which is, I suppose, your point, but to me it seems more interesting to perhaps focus on the mysterious surrounding implementation that will make the application using this stack more "Thread Safe" then one that doesn't. It'll still require a smart programmer to do it, IMHO.

  • I think Thomas has a good idea. It's pretty rare that I want to remove an item from a stack without looking at it. Hence, it makes sense to combine those two operations. That combination of operations is traditionally called Pop, thus I expect an operation called Pop to both remove an item from a stack and tell me what it is. Otherwise you've just reimplemented a List, only with methods named Peek/Pop/Push instead of car/cdr/cons.

    All stacks should have a Push and Peek that work as implemented here. However, I've never seen something called a Stack with an operation that discards the top item and doesn't return it. The Pop function that doesn't return the item should be called something like Discard.

    It would be nice if I could do this in C#:

    Stack<T> s; var v;

    s, v = s.Pop();

  • Wouldn't it be better to define Pop as follows?

    public T Pop(out IStack<T> stack)

    {

      stack = tail;

      return head;

    }

  • The benefit of the other implementation (I think the pattern also has a name but I don't remember) is, that you can do the following:

    T one, two, tree;

    stack.Pop(out one).Pop(out two).Pop(out three)...

    This pattern is very nice.

    Eric, it would be nice to have same typical usage pattern of this immutable stack. The community here doesn't see the possibilities, an immutable stack would offer to us.

    Though I also can't imagine of anything really concrete yet.

    The stack would be useful if you're passing it to other methods. But you'd be required to wait for the invoked method till it returns a stack without the element popped by this method. Not really a parallel workflow.

    IMO, for a parallel workflow, you'd rather need an atomic pop method which also returns the popped element.

    With this immutable stack you'll have to do something like this:

    T item = stack.Peek();

    tellOthers(stack.Pop());

    This task can't be run in parallel without any synchronization.

    I like immutable types and I think there's really a way to use them in a reasonable fashion. I also like Eric's implementation in this post, really nice.

    So my question to Eric: How is this stack used? I just can't imagine...

  • That's how it could be used in a parallel world:

    Stack<T> temp;

    do

    {

        temp = stack;

    }

    while(Interlocked.CompareExchange(ref stack, temp.Pop(), temp));

    T value = temp.Peek();

    It's nicer than the usage of a mutable stack, but not nice.

  • IMHO a Pop without looking at the contents of the stack is actually quite common.

  • I think I've actually used stacks that use the Peek/Pop style more than the Pop-only style.  For example, STL's stack template has a top() to grab the top element and a pop() that returns nothing.  

  • Hi Thomas, I was just tinking in a solution like yours. Would be possible to make a helper method for this common operation for any kind or inmutable data structures:

    Assign(ref stack, s=>s.Pop());

    Where

    void Assign<T>(ref variable, Func<T,T> fun)

    {

    T val;

     do

     {

       temp = variable;

     }

     while(Interlocked.CompareExchange(ref variable, fun(temp), temp));

    }

    God bless lambdas :)

  • Re: don't you always want to see what you're popping?

    No, you don't. For example, consider the stack used by the script engine runtime to keep track of temporary variables. We have separate operations for "peek at the temporary variables" and "these temporaries are dead, remove them from the stack".  We have no need to know what the _values_ of the temps are when they become dead!

    I am not sure why I have to keep on saying this. Peeking and popping are logically distinct operations. If you want to combine them, then you can always write an extension method which does so.  But if you package them together and later want to split them apart, that's hard to do.  A well-designed interface is factored so that things which are logically distinct are actually distinct.

  • Re: when would you use immutable objects?

    I wrote a program just the other day that has two threads. One constantly recalculates what comes down to an immutable bitmap. The other thread takes whatever bitmap is the latest available and displays it. I do not need to ever worry that the drawing thread's "copy" will ever be updated halfway through rendering, because the structure in question is immutable. Likewise, the calculation thread doesn't ever have to worry that it can't continue to do calculations because it is waiting on the rendering thread to unlock the resource for writing.

  • Or, here's another use. Suppose you have a database consisting of an immutable search tree. You add and delete a bunch of stuff from the tree. If you have an immutable stack of immutable search trees, then you can do undo/redo operations trivially and efficiently on add/delete operations on the search tree. Undo/redo is usually both more efficient and much more straightforward to implement if you have immutable state.

  • How about enabling Code Analysis?  (throw InvalidOperationException() instead of a raw Exception()).

Page 2 of 5 (61 items) 12345