Operator Overloading: A demonstration using matrices (Matt Gertz)

Operator Overloading: A demonstration using matrices (Matt Gertz)

  • Comments 6

Over a decade ago, before I joined Microsoft, I was a doctoral candidate at Carnegie Mellon studying robotics.  One of the things that you had to do to get into the doctoral program was pass a qualifier test (“the qual”), which was a three-hour oral examination at the conclusion of the Master’s program.  My qual was, without a doubt, the most grueling experience I’d ever gone through – rougher than my actual dissertation several years later, and certainly rougher than a Microsoft interview.  (“You just want me to write a program to shuffle a deck of cards?  I think I can manage that…”)  For the “qual,” it was common knowledge that you’d be expected to memorize and write out on command just about every formula known to mankind about the physics of robotics.  To prepare, I wrote down 78 equations that I thought would be fair game during the exam, and I spent one hour a day for two months memorizing those equations – I kid you not.  Equations invaded my dreams; for example, “In order to slay the dragon, I’ll have to apply an iterative Newton-Euler dynamic formulation to determine the acceleration and velocity of the sword based on the degrees of freedom in my arm.”  One of the equations involved 26 variables and I was indeed asked to write it down during the exam, and to my utter delight, I got it right.

Within two days of passing my qualifier, the equations escaped from my brain, and I didn’t care.  Hey, that’s what docs are for.  I don’t memorize VB language syntax, for example – I look it up in a book or on-line, same as everyone else, except possibly our architect Paul Vick, whom I think has it all tattooed on his arms.

However, there comes a time when you need to use those equations, and working it out longhand would be tedious or impractical.  That’s where programming comes in.  I’m sure I’m not the only person, for example, who programmed his calculator in college to solve quadratic equations for the roots – very handy during exams where you could be expected to take that ability for granted.  Unfortunately, during my tenure as a graduate student, calculators didn’t have nearly enough memory to quickly solve matrix equations (at least not the ones I could afford), and matrices are the backbone of all robotics formulae.  However, these days a handheld device running Windows Mobile 5.0 or WindowsCE certainly has enough horsepower to do this, so in this two-part series I’ll walk through putting together such a matrix calculator.  In this part, I’ll just be working with a class library, and next week, I’ll get it onto the handheld.

Matrices

The first thing I’ll need is a matrix class, and to do that I’ll create a class library called Matrices simply by choosing CreateNewProject, choosing “Class Library,” and changing the name appropriately before clicking “OK.” (Don’t worry if you forget to change the name – in VB2005, it’s never too late to change it, and you can do it later simply be changing the name of the file in the solution explorer).

I’ll rename the class inside to be called “Matrix.”  Again, don’t worry, you can also do this later by right-clicking on the name of the class and choosing “Rename.”

 A matrix has some number of rows and columns (by the way, this entire series will be 0-based as far as arrays are concerned, not 1-based).  Here’s the bare-bones version:

    Private _rows As Integer = 0

    Private _columns As Integer = 0

    Public ReadOnly Property Rows() As Double

        Get

            Return _rows

        End Get

    End Property

    Public ReadOnly Property Columns() As Double

        Get

            Return _columns

        End Get

    End Property

 

    Public data(,) As Double

 

All very straightforward.  Note that the number of rows and columns default to zero.  Clearly, they need to be non-zero, so in the class constructor, I’ll enforce the requirement to supply dimensions:

    Public Sub New(ByVal m As Integer, ByVal n As Integer)

        ReDim data(m - 1, n - 1)

        _rows = m

        _columns = n

    End Sub

 

Note the use of ReDim – this will allow me to dynamically determine the size of the array at runtime, rather than having to hard-code the array size.  Also note that it looks like I’m re-dimming them for one size less than I need.  This is because VB automatically adds on element to each array for historical reasons, as many programmers in the past preferred to work with 1-based notation.  I don’t need the extra memory, and it makes looking at matrices in the debugger window confusing, so out it goes.  (And yes, if you call New(1,1), it will redim the array to (0,0), which, after VB adds the additional row and column as usual, turns out to be 1 allocated element.  It hurts my head to think too hard about that, but at least the right thing happens in the end.)

Now, if I wanted to add two matrices together, I could create a shared function called Add(m1,m2) which would add the two together, something like this:

    Public Shared Function Add(ByVal m1 As Matrix, ByVal m2 As Matrix) As Matrix

        ' … etc…

    End Function

   

    Dim m3 As Matrix = Matrix.Add(m1, m2)

 

But wouldn’t it be cooler if we could just do:

        Dim m3 As Matrix = m1 + m2

 

Well, we can, thanks to something in VB2005 called operating overloading.  I discussed operator overloading in some detail in this article here a few years ago, but the gist of it is that Operator Overloading allows you to assign methods to the various mathematical symbols (+, -, *, /, etc.) for a given class.  You can even define casting operators.  Let’s define an overload here for addition:

    Public Shared Operator +(ByVal m1 As Matrix, ByVal m2 As Matrix) As Matrix

        If m1.Rows = 0 OrElse m2.Rows = 0 OrElse m1.Columns = 0 OrElse m2.Columns = 0 Then

            Dim ex As New System.Exception("Attempt to add empty matrix.")

            Throw ex

        End If

        If m1.Rows <> m2.Rows OrElse m1.Columns <> m2.Columns Then

            Dim ex As New System.Exception("Attempt to add differently-shaped matrices.")

            Throw ex

        End If

 

        Dim m3 As New Matrix(m1.Rows, m1.Columns)

        For i As Integer = 0 To m1.Rows - 1

            For j As Integer = 0 To m1.Columns - 1

                m3.data(i, j) = m1.data(i, j) + m2.data(i, j)

            Next

        Next

        Return m3

    End Operator

 

Let’s start with the signature from above.  All operator overload methods are shared methods.  They work on a particular symbol or keyword (in this case, the plus sign, +), and they take arguments having particular classes (in this case, two matrices), and they return some type (again, in this case, a matrix).  What you do inside the rest of the method is totally up to you.  I start out by making sure the matrices are the same size and that they are not empty, throwing if they fail those tests.  Then, I simply create a new matrix, add together the contents of m1 and m2 to it, and then return the result.  Simple, isn’t it?

If you’ve guessed that an overloaded operator is really just a function, you’re right.  What you’re getting out of it is simply the ability to write more readable code.  You do need to take care to use them properly, though.  Take this (contrived) example, where I allow a matrix to be multiplied by a scalar:

    Public Shared Operator *(ByVal m1 As Matrix, ByVal val As Double) As Matrix

        Dim m2 As New Matrix(m1.Rows, m1.Columns)

        For i As Integer = 0 To m1.Rows - 1

            For j As Integer = 0 To m1.Columns - 1

                m2.data(i, j) = m1.data(i, j) * val

            Next

        Next

        Return m2

    End Operator

 

So, the following code works:

        Dim m1 As New Matrix(5, 5)

  ' … Pretend there’s code here that fills m1 with data

        Dim m2 As Matrix = m1 * 7.0

 

But this doesn’t – the arguments are in the wrong order:

        Dim m1 As New Matrix(5, 5)

  ' … Pretend there’s code here that fills m1 with data

        Dim m2 As Matrix = 7.0 * m1 ' ERROR!

 

We can fix this by also defining the opposite arguments in a different overload:

    Public Shared Operator *(ByVal val As Double, ByVal m1 As Matrix) As Matrix

        Return m1 * val ' This will just call the other overload

    End Operator

 

And now it doesn’t matter what order the arguments are in for this particular case.  (There are certainly cases where the argument order would matter for two different types, which is why VB doesn’t do this sort of thing automatically.)

Of course, we can define other overloads on the multiplication operator, so long as the types and orders are different.  For example, let's add a third overload which multiplies two matrices, which is a vastly different operation than multiplying a matrix by a scalar:

    Public Shared Operator *(ByVal m1 As Matrix, ByVal m2 As Matrix) As Matrix

        If m1.Rows = 0 OrElse m2.Rows = 0 OrElse m1.Columns = 0 OrElse m2.Columns = 0 Then

            Dim ex As New System.Exception("Attempt to subtract empty matrix.")

            Throw ex

        End If

        If m1.Columns <> m2.Rows Then

            Dim ex As New System.Exception("Attempt to multiply incompatible matrices.")

            Throw ex

        End If

        Dim m3 As New Matrix(m1.Rows, m2.Columns)

        For ci As Integer = 0 To m3.Rows - 1

            For cj As Integer = 0 To m3.Columns - 1

                ' Fill in the Cij value in m3

                m3.data(ci, cj) = 0

                For i As Integer = 0 To m1.Columns - 1

                    m3.data(ci, cj) = m3.data(ci, cj) + m1.data(ci, i) * m2.data(i, cj)

                Next

            Next

        Next

        Return m3

    End Operator

 

So, I can call:

1.       5.0 * m1 (scalar multiplied by matrix)

2.       m1 * 5.0 (matrix multiplied by scalar)

3.       m1 * m2 (matrix multiplied by matrix)

and in each case a totally different operator overload will be called, despite the consistent use of the asterisk operator.

I’ve attached the full library to this post.  It includes methods for finding the determinant of a matrix, the inverse of a matrix, and the transpose of a matrix as well, since we’ll need those next week – there’s nothing particularly special about those methods, so I won't dig into them here.  (Keen eyes will note that I deliberately used the easiest calculations for the determinant and inverse, in order to make them more readable and to allow me to focus on the real subject, which was operator overloading.  You can find more performant algorithms out on the web – they tend to be iterative and are often ghastly to try to read.)  I’ve also attached some test cases in a console application.

Next week, we’ll work on our hand-held matrix calculator.  ‘Til then…

--Matt--*

 

Attachment: Matrices.zip
Leave a Comment
  • Please add 6 and 1 and type the answer here:
  • Post
  • >  This is because VB automatically adds on element to each array for historical reasons, as many programmers in the past preferred to work with 1-based notation.

    I sounds like you are thinking about it in the wrong terms. Redim X(a) doesn't create an array of a elements, it creates an array with a as the upper bound.

    If you read it in the old syntax, it makes more sense...

    ReDim X(0 to a)

    Or really old syntax...

    ReDim X(87 to 94)

  • Mea culpa -- I got sloppy.  The point I was trying to make, irrespective of ReDim, that if the programmer uses the syntax Dim x(n) As Double (i.e., just specify the upper bound), it may be unclear to that programmer what the actual size of the array will be, because ranges aren't commonly used in other languages.  For me, with my zero-based background (along with anyone else who started out in C, C++, etc.), I would always assume that I'd get three elements -- but I'd be wrong.  

    However, my comment is still correct.  I'll explain: during the development of VB.NET 2002, there was serious consideration as to what Dim x(3) would actually do -- should we ditch the whole "lower/upper bound" concept and just go with element allocation, and specifically only allocate 3 slots in this case (instead of 4, which was the established VB6 behavior -- "0 to 3").  This would have gotten us in better line with the rest of the .NET languages when passing memory around (since ultimately our memory allocation derives from .NET functionality).  However, we knew that many customers were treating the allocation as if it were 1 to 3 rather than 0 to 3 in VB6 (and not all changed the lower bound default for their module), and so forcing the shift down to zero would be very tough on migrated VB6 apps, particular those that had hard-coded 0 as being a stop condition when counting down.  Thus, for legacy reasons, we couldn't shift to an element count allocation which would enforce a zero-based notation.

    Nevertheless, it's currently illegal to have a non-zero lower-bound, which kind of puts us half-way between the two extremes.  Effectively, the only reason now that we even have a "to" notation in the array syntax is precisely because of 1-based applications.  Internally, it really is implemented as "add 1 to whatever they specified to the upper bound and allocate that many elements" -- the "0 to" part is just sugar, a useful mnemonic for the VB programmer to remember that the external concept is bounds.  For people coming into VB, though, it's a bit alien.

    --Matt--*

  • The Visual Basic team blog has had quite a run of great posts lately. The topics have been very interesting

  • Glad to hear it!  They've been a lot of fun for us to put together, and we have every plan to keep it up.

    --Matt--*

  • your article was really helpfull

  • That's great to hear, thanks for the feedback!

    --Matt--*

Page 1 of 1 (6 items)