Immutability in C# Part Two: A Simple Immutable Stack
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.
Comments
Anonymous
December 04, 2007
PingBack from http://msdnrss.thecoderblogs.com/2007/12/04/immutability-in-c-part-two-a-simple-immutable-stack/Anonymous
December 04, 2007
The comment has been removedAnonymous
December 04, 2007
TSHAK: That's true, but I can't imagine it could reasonably work any other way and still preserve immutability.Anonymous
December 04, 2007
Any why is it the case that looking at a data structure should require you to change its contents? That has never made any sense to me.Anonymous
December 04, 2007
That's the same behavior as the STL's stack class. Seems reasonable (and not at all unusual) to me.Anonymous
December 04, 2007
The comment has been removedAnonymous
December 04, 2007
I wrote something like a Monad (which I have named it Monad!) in C# 3. I can achieve immutability throe it to an acceptable degree. Still I am meditating on it. But it looks somehow interesting to me. Here is the code: public class Monad<T> : IMonad<T> { private Monad (T inner) { this.__InnerHolder = inner; } private Monad () { } private readonly T __InnerHolder; private T Inner { get { return __InnerHolder; } } public static IMonad<TInner> Unit<TInner> (TInner inner) { return new Monad<TInner> (inner); } public static Func<A, IMonad<R>> Lift<A, R> (Func<A, R> fun) { if (fun.IsNull ()) throw new ArgumentNullException ("fun", "'fun' can not be null."); return (a => Unit<R> (fun (a))); } public static IMonad<B> Bind<A, B> (IMonad<A> a, Func<A, IMonad<B>> fun) { if (fun.IsNull ()) throw new ArgumentNullException ("fun", "'fun' can not be null."); return new Monad<B> (fun (a.Monad.Inner).Monad.Inner); } #region IMonad<T> Members Monad<T> IMonad<T>.Monad { get { return this; } } #endregion } public static partial class MonadExtra { public static IMonad<TInner> Unit<TInner> (this TInner inner) { return Monad<object>.Unit<TInner> (inner); } public static Func<A, IMonad<R>> Lift<A, R> (this Func<A, R> fun) { return Monad<object>.Lift<A, R> (fun); } public static IMonad<B> Bind<A, B> (this IMonad<A> a, Func<A, IMonad<B>> fun) { return Monad<object>.Bind<A, B> (a, fun); } } public interface IMonad<T> { Monad<T> Monad { get; } }Anonymous
December 04, 2007
Quite fine. You can think of C# 3.0 query expressions as using a form of monads. I might do a series of blog articles about that at some point.Anonymous
December 04, 2007
Why doesn't Pop use a ref variable to return the value?Anonymous
December 04, 2007
Sorry for scrambled code! I have replaced < and > with html literals. It seems that i was wrong about them!Anonymous
December 04, 2007
For the third time: why should it be necessary to change the data structure in order to look at it? A Pop which returns the value is a design flaw; it conflates two logically distinct and separate operations into one method.Anonymous
December 04, 2007
The comment has been removedAnonymous
December 05, 2007
Silky, This only part 2. You have to be patient and wait for the Journey to unfold.Anonymous
December 05, 2007
@Jay: public static readonly IStack<T> Empty = new EmptyStack();Anonymous
December 05, 2007
I don't understand; why can you not have an immutable stack as a member variable? (In a couple posts I'll be having data structures with immutable stacks as member variables.) Integers are also immutable. What are the disadvantages of immutable stacks which are shared by immutable integers? How do immutable integers "push work back onto the caller"?Anonymous
December 05, 2007
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.Anonymous
December 05, 2007
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!Anonymous
December 05, 2007
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(); }Anonymous
December 05, 2007
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.Anonymous
December 05, 2007
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();Anonymous
December 05, 2007
The comment has been removedAnonymous
December 05, 2007
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...Anonymous
December 05, 2007
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.Anonymous
December 05, 2007
IMHO a Pop without looking at the contents of the stack is actually quite common.Anonymous
December 06, 2007
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.Anonymous
December 06, 2007
The comment has been removedAnonymous
December 06, 2007
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.Anonymous
December 06, 2007
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.Anonymous
December 06, 2007
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.Anonymous
December 11, 2007
How about enabling Code Analysis? (throw InvalidOperationException() instead of a raw Exception()).Anonymous
December 11, 2007
Showcasing well-designed exception handling is not the point of this series of articles.Anonymous
December 12, 2007
@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.Anonymous
December 20, 2007
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?Anonymous
December 21, 2007
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...Anonymous
December 21, 2007
The comment has been removedAnonymous
January 02, 2008
The comment has been removedAnonymous
January 03, 2008
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.Anonymous
January 03, 2008
That question was the subject of part one of this series. Did you start with part two?Anonymous
January 03, 2008
Yes :$ Found part one, thanksAnonymous
January 03, 2008
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.Anonymous
January 04, 2008
> 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:
- Objects are "thread safe" because all changes made by all threads are visible to all threads.
- 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.
Anonymous
January 07, 2008
One would think Eric wants an object-type between 'struct's and 'class'es: (at compilers' discretion) having reference-implementation but always value-semantics.Anonymous
January 08, 2008
The comment has been removedAnonymous
January 15, 2008
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".Anonymous
January 15, 2008
The comment has been removedAnonymous
January 15, 2008
The comment has been removedAnonymous
January 16, 2008
For some reason, there's been a lot of buzz lately around immutability in C#. If you're interested inAnonymous
January 17, 2008
Eric, Excellent.. then you and I are in agreement, since there are most definitely uses for immutability in the toolbox... as long as they are intelligently applied.Anonymous
January 23, 2008
I have to agree with Kaveh Shahbazian on this one: fun cannot be null. :) My question is why change a way of programming in order to teach people immutability when you can change the compiler to take care of things like that in care of concurency and multi-processor computing? I think the whole FP and immutability buzz is generated by people thinking to abstractly to be able to debug anything :)Anonymous
March 02, 2008
Previously we discussed a multi-thread safe queue like data structure using locks as an internal synchronizationAnonymous
March 02, 2008
Previously we discussed a multi-thread safe queue like data structure using locks as an internal synchronizationAnonymous
March 17, 2008
Functional programming is in. There is a lot of buzz around the future of functional programming as applicationsAnonymous
July 22, 2008
This is genius... I'm using this algorithm to store the numbers 1-40 in a immutable stack: IStack<int> s0 = Stack<int>.Empty; IStack<int> s1 = s0.Push(1); IStack<int> s2 = s1.Push(2); IStack<int> s3 = s2.Push(3); IStack<int> s4 = s3.Push(4); IStack<int> s5 = s4.Push(5); IStack<int> s6 = s5.Push(6); IStack<int> s7 = s6.Push(7); IStack<int> s8 = s7.Push(8); IStack<int> s9 = s8.Push(9); IStack<int> s10 = s9.Push(10); IStack<int> s11 = s10.Push(11); IStack<int> s12 = s11.Push(12); IStack<int> s13 = s12.Push(13); IStack<int> s14 = s13.Push(14); IStack<int> s15 = s14.Push(15); IStack<int> s16 = s15.Push(16); IStack<int> s17 = s16.Push(17); IStack<int> s18 = s17.Push(18); IStack<int> s19 = s18.Push(19); IStack<int> s20 = s19.Push(20); IStack<int> s21 = s20.Push(21); IStack<int> s22 = s21.Push(22); IStack<int> s23 = s22.Push(23); IStack<int> s24 = s23.Push(24); IStack<int> s25 = s24.Push(25); IStack<int> s26 = s25.Push(26); IStack<int> s27 = s26.Push(27); IStack<int> s28 = s27.Push(28); IStack<int> s29 = s28.Push(29); IStack<int> s30 = s29.Push(30); IStack<int> s31 = s30.Push(31); IStack<int> s32 = s31.Push(32); IStack<int> s33 = s32.Push(33); IStack<int> s34 = s33.Push(34); IStack<int> s35 = s34.Push(35); IStack<int> s36 = s35.Push(36); IStack<int> s37 = s36.Push(37); IStack<int> s38 = s37.Push(38); IStack<int> s39 = s38.Push(39); IStack<int> s40 = s39.Push(40); programming was never easier before, but the best is, it's threadsafe ;) no one will ever change the stuff i stored in the stack. thank you Eric, made my day...Anonymous
November 11, 2008
I'm coming to this really late, and I'm probably failing to see the joke, so this is a waste of time, but I can't resist informing Gustav that he could have written: Enumerable.Range(1, 40).Aggregate(Stack<int>.Empty, (s, n) => s.Push(n));Anonymous
November 24, 2008
In this post I'll delve into the functional programming techniques that were used to develop ImplicitStyleManagerAnonymous
November 26, 2008
The comment has been removedAnonymous
November 27, 2008
Here is a link talk about the rules for immutable type: http://www.bluebytesoftware.com/blog/2007/11/11/ImmutableTypesForC.aspx Rules number five:
- Immutable types must not leak the ‘this’ reference during construction. public IStack<T> Push(T value) { return new Stack<T>(value, this); } Wonder if the above statement break the rules?
Anonymous
December 07, 2008
I talked a little bit about patterns using InvocationExpression in a previous post (you might want toAnonymous
June 09, 2009
I talked a little bit about patterns using InvocationExpression in a previous post (you might want toAnonymous
January 09, 2010
The comment has been removedAnonymous
August 21, 2012
Thank you very much for writing these blog posts, I learn so much!