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.

  • Showcasing well-designed exception handling is not the point of this series of articles.

  • @Eric,

    But in your bitmap example, there still has to be a thread-safe way for the drawing thread to 1) replace its current copy with the latest copy, or 2) retrieve the current copy on every iteration (depending on how it is implemented). This of course is not difficult to do, but once you have done it, what advantage does the immutability of the data structure really offer you? Your threads are never accessing the same object at the same time, so what difference does it make whether it is immutable or not? All you have really made a case for is duplicating objects rather than making them thread-safe; that is not the same thing as making them immutable. I think you have still yet to make a compelling case for why building thread-safety into C# and/or the CLR is an advantage.

  • Look at this Stack abused class:

    class WorkQueue {

       private IStack<WorkItem> workQueue = Stack<WorkItem>.Empty;

       public void EnqueueWorkItem(WorkItem item) {

           workQueue = workQueue.Push(item);    // No lock needed because it's immutable??

       }

       public WorkItem DequeueWorkItem() {

           WorkItem topItem = workQueue.Peek();

           workQueue = workQueue.Pop();    // No lock needed because it's immutable??

       }

    }

    Does this mean "thread-safe" ability of immutable objects can't apply here, doesn't it?  Because, in practical use, you still have to sync those operations in parallel world.

    So what is the really benefit of immutable object? Isn't it just syntactic sugar?

  • Ruxo, the stack in your example is still thread-safe - it is WorkQueue that isn't thread-safe, and you'll notice that it isn't immutable...

  • Thanks Michael.  Point taken.  But, then, where's the real benefit of Stack's "thread-safe"?  The point is, I think, working with a stack, we usually need to access one with the most updated data.  So we need synchronization at some place.  This immutable stack so seems like new way to express the usage.  Would it finally become style preference fight?

  • I love this series.

    <nit picky complaint>

    The only part I don't like is that Stack<T>.Pop returns an IStack<T>.  Instead have Stack<T> be non-sealed and define virtual members.  Let EmptyStack overrdie the bad ones that need to throw (Pop,Push,Peek).  

    Since you're no longer dealing with a sealed class, the Jitter won't be able to avoid virtual calls for the Pop,Push,Peek methods.  However since most methods in the original implementation return interfaces.  AFAIK (which doesn't mean it's still true) all mtehod calls on interfaces require virtual dispatch because it could be a Transparent Proxy.  This was true ages ago though so I'm not suer if it's still valid.  

    The upside is that you don't have to worry about Stack<T> vs IStack<T>.  

    </nit picky complaint>

  • Would one still define this stack as immutable if T is mutable.

    It probably depends what one defines as the "state" of the object.

    If one was to take a snapshot of the object (call it s1), then call stack.Peek.DoSomethingMutable(), then take another snapshot (s2), then s1 != s2.

    (Again, depending on the definition of equals)

    This then begs the question how deep must the "immutablility" be (e.g. member variables, member variables of member variables, member variables of member variables of member variables) in order for an object do be defined as immutable.

  • That question was the subject of part one of this series. Did you start with part two?

  • Yes :$

    Found part one, thanks

  • This stack has no utility to multithreaded programming when more then one thread is getting objects from the stack.  Peek and Pop are traditionally combined into a single operation (which is atomic or locked in the multithreaded case) so that an external lock around both the peek and pop operation is not needed.  If one thread is putting things on the stack and two others are getting work from it in a LIFO fashion then they can both get the same piece of information to work on.

    Of course this is most likely not the problem this stack was designed to solve.

    Immutable data structures can be nice, but well designed syncronized/atomic operations still need to be used to communicate between the threads.

  • > Of course this is most likely not the problem this stack was designed to solve.

    Correct. There are (at least) two kinds of thread safety:

    1) Objects are "thread safe" because all changes made by all threads are visible to all threads.

    2) Objects are "thread safe" because changes made by one thread are invisible to other threads.

    Immutable stacks implement the latter kind of safety. A safe-in-the-latter-sense stack has the property that it has predictable behaviour.  You push something on it, it gets one bigger.  A safe-in-the-first-sense stack does not have this property -- you push something on it, and you have absolutely no idea what the size of that thing is because n other threads might have been pushing and popping it at the same time.

    And, combining this with the comments above -- in a stack designed to have the first kind of thread safety, it makes more sense to combine "peek" with "pop". After all, you have no idea after "peeking" the stack that the item you just peeked is still on the top of the stack, or even on the stack at all. Eliminating peek means that you can at least guarantee that popping the stack gives you an element that was once at the top of the stack and is no longer.

  • One would think Eric wants an object-type between 'struct's and 'class'es: (at compilers' discretion) having reference-implementation but always value-semantics.  

  • Two things:

    Regarding Pop returning the Head:

    public static class StackExtensions

    {

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

    {

     value = stack.Peek();

     return stack.Pop();

    }

    }

    And as to users who want "mutable usage", you could do a mutable wrapper

    public class MutableStack<T>

    {

     private IStack<T> innerStack;

     public MutableStack(IStack<T> stack) { innerStack = stack; }

     public void Push(T value) { innerStack = innerStack.Push(value); }

     public T Pop() { T value; innerStack = innerStack.Pop(out value); return value; }

     public bool IsEmpty { return innerStack.IsEmpty; }

     public T Peek() { return innerStack.Peek(); }

    }

  • Thanks for the great ideas...  I'm actually thinking an immutable stack might be great as the Undo/Redo stack in a puzzle game I'm building.   It might even come in handy in the puzzle generation phase...  providing a nice way to manage and analyze alternative "paths".

  • Eric,

    Thread safety is more than just 'immutable'.  In systems where performance is an issue, where thread safety is an issue, and where stack size can be significant, an immutable stack provides one type of thread safety at the cost of performance (in much the same way immutable strings can impact performance if you don't take the underlying mechanisms of strings into account).

    I do not deny that immutability is a way to solve these problems, but we can't oversimplify the problem of parallel programming.  The trade-offs between the use of immutable objects (strings, stacks, whatever) vs. more traditional techniques must be COMPLETELY understood by the engineers solving the problems, there is no simple 'off the shelf solution'.  

    If you are not implying this, my apologies, I just seem to be getting this impression from many in this thread, and its dangerous thinking (there are no silver bullets).

Page 3 of 5 (61 items) 12345