In this article I will shamelessly “steal” the great work originally posted by Eric Lippert on his blog. However I will translate his code into VB and try to explain it from a VB developers point of view.
In my last post, I described what immutable objects are and what the advantage of using them would be. It also described how you could create an immutable class and use it as if it was value type. This time we are going to take this a step further and create an immutable stack.
An immutable stack, is that possible?
As Eric pointed out on his blog: This might sound a bit strange to you since a stack is by its very nature something that changes. You push stuff to it and pop things from it, last-in-first-out. So how can something like that be immutable? If we create a new stack object each time we push or pop something to/from the stack wouldn’t we then be allocating a great deal of memory? Well, in this case the answer is nope. Eric showed a very elegant way of saving memory, in some cases it might even be more efficient than a mutable version.
The idea is that you simply have a head object which is the last value or reference object (depending on what you’re storing on the stack) that was push onto the stack, and a tail which is a reference to the old stack. The state the stack was before the last item was pushed upon it.
Creating the Stack
As I’ve already mentioned, I did not create this code, all credit goes to Eric Lippert. All I have done is to translate it to VB, except for one detail. Eric implemented his stack as an IEnumerable(Of T), taking advantage of the iterator support that C# has with its yield keyword. Since VB currently doesn’t support that I simply didn’t implement it here. In the next part of this The Untouchables series I will however extend this stack class with support for iterators. As you will see it currently requires a whole lot more code in VB than it does in C#. If you’re interesting in learning more about how to use iterators in VB now, I would recommend that you read Bill McCarthy’s excellent article about the subject. But for now we just leave them out.
OK, onward! We are going to implement our stack using generics, so that you can use it to push any type onto the stack. The first thing we will do is to define an interface for our class.
Public Interface IStack(Of T) Function Push(ByVal value As T) As IStack(Of T) Function Pop() As IStack(Of T) Function Peek() As T ReadOnly Property IsEmpty() As Boolean End Interface
If you have ever used a stack object before, you are probably accustomed that the Pop() method would return the value it just removed from the stack. In this case it doesn’t it simply returns another stack object without the value that was just popped. I must say that I agree with Eric here, that looking at the data should not require you to change it. A Pop which returns the value is a design flaw since it conflates two logically distinct and separate operations into one method. So in our case we use the Peek() method to look at the top value, and Pop() to remove it.
Our Stack class which will implement the above interface will have a constructor, but we will keep that private. You will get a new Stack object by calling the Push() and Pop() methods. However we also need a way to create an empty stack, otherwise we have nothing that we can Push or Pop anything to or from. Since every empty stack is the same, we will have a singleton empty stack that is created via a shared (static) method that we simply call Empty(). So we will be creating a new empty stack object (of strings in this example) in this manner:
Dim myStack As IStack(Of String) = Stack(Of String).Empty
Note that the myStack object above is not declared as Stack(Of String) but rather as our interface IStack(Of String). This is because our Empty() method returns an IStack(Of T) object that contains an instance to a private inner class called EmptyStack that like our Stack(Of T) class also implements the IStack(Of T) interface.
OK, here’s the full listing of the class.
Public NotInheritable Class Stack(Of T) Implements IStack(Of T) Private NotInheritable Class EmptyStack Implements IStack(Of T) Public ReadOnly Property IsEmpty() As Boolean _
Implements IStack(Of T).IsEmpty Get Return True End Get End Property Public Function Peek() As T Implements IStack(Of T).Peek Throw New Exception("Empty stack") End Function Public Function Pop() As IStack(Of T) Implements IStack(Of T).Pop Throw New Exception("Empty stack") End Function Public Function Push(ByVal value As T) As IStack(Of T) _
Implements IStack(Of T).Push Return New Stack(Of T)(value, Me) End Function End Class Private ReadOnly _head As T Private ReadOnly _tail As IStack(Of T) Private Shared ReadOnly _empty As New EmptyStack Public Shared Function Empty() As IStack(Of T) Return _empty End Function Public ReadOnly Property IsEmpty() As Boolean _
Implements IStack(Of T).IsEmpty Get Return False End Get End Property Public Function Peek() As T Implements IStack(Of T).Peek Return _head End Function Public Function Pop() As IStack(Of T) Implements IStack(Of T).Pop Return _tail End Function Public Function Push(ByVal value As T) As IStack(Of T) _
Implements IStack(Of T).Push Return New Stack(Of T)(value, Me) End Function Private Sub New(ByVal head As T, ByVal tail As IStack(Of T)) _head = head _tail = tail End Sub End Class
Notice how each time we Push a new value onto the Stack we call our private constructor that create a new Stack object. However our _tail will simply contain a reference to the old stack, that way we conserve memory resources. Since more than one stack object can share the same tail it will actually be more effective than a regular mutable version of a Stack object.
Dim s1 As IStack(Of Integer) = Stack(Of Integer).Empty Dim s2 As IStack(Of Integer) = s1.Push(10) Dim s3 As IStack(Of Integer) = s2.Push(20) Dim s4 As IStack(Of Integer) = s2.Push(30) 'shares its tail with s3
Remember that the Stack object is immutable so pushing a value onto the stack doesn’t change it. Instead it returns a new Stack object containing the newly pushed value. The following code will raise an exception “Empty Stack” since myStack is still empty.
Dim myStack As IStack(Of String) = Stack(Of String).Empty() myStack.Push("Hello")
Console.WriteLine(myStack.Peek) 'raises an exception since myStack is empty
That is like calling the Replace() method of a string without assigning the return value to anything. It will not have changed the immutable string. The correct way of doing the above would be this:
Dim myStack As IStack(Of String) = Stack(Of String).Empty() myStack = myStack.Push("Hello") 'change the reference of myStack Console.WriteLine(myStack.Peek) 'writes "Hello"
OK, next time I’m going to extend our Stack class to add support for iterators, so that we can use a For Each loop on our stack object. So stay tuned…
Until then, have fun!