Joacim's view on stuff : visual basic, generics

The Untouchables (part II) – Creating an Immutable stack with VB

Joacim Andersson — Mon, 07 Sep 2009 01:02:03 GMT

Introduction

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!

Go for the Generic brand…

Joacim Andersson — Wed, 02 Sep 2009 15:05:33 GMT

Before .Net 2.0 the only way that you could use a generic type was to use System.Object. Although it’s been 4 years since the release of .Net 2.0 I still see developers using the System.Object way too often, which leads to unnecessary boxing/unboxing and casting. So in this article I’m going to explain how you can use Generics in your classes and methods.

What are Generics?

I entitled this article “Go for the Generic brand” because outside the world of programming the term generic means something that is not tied to a particular brand name. You may buy a bottle of shampoo without it having one of the more recognizable names printed on its label but you can still use it and expect it to clean your hair. Generics in programming works in a similar manner, you can refer to a class without it being related to a particular Type, but we can still use it in a type-safe manner.

However unlike generic brands of merchandises, that often are thought of as inferior to well known household brands, Generics in .Net are usually a good thing. I said usually a good thing because you should not look at generics as a way to replace other techniques such as method overloading, but rather as a way to replace the usage of System.Object.

A quick example

Below is a small example on what a generic class could look like.

Public Class MyGenericClass(Of T)
  Private _value As T
  Public Property Value() As T
    Get
      Return _value
    End Get
    Set(ByVal value As T)
      _value = value
    End Set
  End Property
End Class

The (Of T) part after the class name tells the compiler that this is a generic class. The T itself is merely a placeholder of a type, any type. The name T doesn’t really matter, you could just as well have typed (Of MyType) if you wanted to, however it has become a general convention to just use the capital T, unless the class expects more than one type.

In C# the same class would look like this:

public class MyGenericClass<T>
{
  private T _value;
  public T Value
  {
    get{ return _value; }
    set{ _value = value;}
  }
}

C# uses the angle brackets instead of the Of keyword as VB does, but other than that they work exactly in the same manner.

So let’s see how this class can be used. When we create a new object from the class we must provide the type we want to use.

Dim myString As New MyGenericClass(Of String)
Dim myInteger As New MyGenericClass(Of Integer)
myString.Value = "Hello World"
myInteger.Value = 123
Console.WriteLine(myString.Value)
Console.WriteLine(myInteger.Value)

Here I create two instances of the MyGenericClass one of the String type and the other of the Integer type. The Value property will then become of that particular type, so trying to do the following would create a compile error (or a runtime error if you have Option Strict set to Off) since I’m trying to assign a string value to an integer type.

myInteger.Value = "Hello"

This generic class is in no way restricted to only primitives and strings, you could use it with any type. Below I use a StringBuilder.

Dim myStringBuilder As New MyGenericClass(Of StringBuilder)
myStringBuilder.Value = New StringBuilder
myStringBuilder.Value.AppendLine("A string")
myStringBuilder.Value.AppendLine("Another string")
Console.WriteLine(myStringBuilder.Value)

Generic Methods

The whole class doesn’t have to use generics, you can use generics on a single method as well.

Public Function CreateArray(Of T)(ByVal size As Integer) As T()
  Dim array(size) As T
  Return array
End Function

Public Sub Main()
  Dim myIntArray As Integer() = CreateArray(Of Integer)(5)
  Dim myStringArray As String() = CreateArray(Of String)(5)
End Sub

This can be especially useful for extension methods, when you want to add a generic method to any type.

Type constraints

Even though the code in a generic type definition should be as type-independent as possible it is sometimes useful to add some constraints to limit the number of types that are possible. A good example is if you for example need to compare items to be able to sort them in which case they must implement the IComparable interface.

Public Class MyComparer(Of T As IComparable)
  'Insert code...
End Class

Apart from interfaces the type of constraints you can use are:

The type must be of a type of, or inherit from, a class.
The type must expose a parameterless constructor.
The type must be a reference type, or it must be a value type.

Let’s have a look at the first, the the type must be of, or inherit from, a specified class. Let’s say you have the following classes:

Public Class Identity
  Private _id As Integer
  Public Property ID() As Integer
    Get
      Return _id
    End Get
    Set(ByVal value As Integer)
      _id = value
    End Set
  End Property
End Class

Public Class Person
  Inherits Identity

  Private _firstName As String
  Public Property FirstName() As String
    Get
      Return _firstName
    End Get
    Set(ByVal value As String)
      _firstName = value
    End Set
  End Property

  Private _lastName As String
  Public Property LastName() As String
    Get
      Return _lastName
    End Get
    Set(ByVal value As String)
      _lastName = value
    End Set
  End Property
End Class

Public Class Company
  Inherits Identity

  Private _name As String
  Public Property Name() As String
    Get
      Return _name
    End Get
    Set(ByVal value As String)
      _name = value
    End Set
  End Property

  Private _city As String
  Public Property City() As String
    Get
      Return _city
    End Get
    Set(ByVal value As String)
      _city = value
    End Set
  End Property
  'more properties goes here...
End Class

So basically we here have an Identity class that expose an ID property and then we have a Person and a Company class that both inherit from the Identity class. Now let’s say that you want to create a collection class that only accepts objects of the Identity class or one of its descendants, it could then look something like the following.

Public Class IdentityCollection(Of T As Identity)
  Inherits List(Of T)
End Class

You can specify more than one constraint if you like, in which case you list the different constraints inside curly braces.

Public Class IdentityCollection(Of T As {Identity, IComparable})
  Inherits List(Of T)
End Class

To require an accessible parameterless constructor you would include the New keyword in the list. For a reference type include the Class keyword, and for value types you would include the Structure keyword.

Generic collections

Generics are mostly used with collections, and the .Net team have included a bunch of various generic collections for us, including list, stack, queue, and dictionary collections. They are all part of the System.Collections.Generic namespace.

In .Net 1.1 we where more or less forced to use the ArrayList collection type. However that excepted items of the System.Object type which means that casting and, if you use value types, boxing/unboxing needs to be performed. That can be very inefficient, especially in For Each loops. Using the List(Of T) we don’t have to do any of that.

Dim myList As New List(Of Person)

Conclusion

So in this article I’ve covered most of what you need to know about using generics. If you haven’t started using generics yet, I hope this article will get you started.

Have fun.