Test Driving Expression Template Programming
by Kent Lai


ADVERTISEMENT

It's 2 a.m. in the office. All your co-workers had left 8 hours ago, and are currently tucked in their beds, soundly asleep. The only sound that can be heard is your typing, as well as the occasional sipping of coffee. You're about to finally finish the major rewrite of the entire framework of the current project. As you finish typing the last character, you hit the Compile button and cross your fingers. It compiled smoothly. And then you ran the application using the new framework for the first time, and the results make you wish you have never been born. You wish you had not simply gone ahead and made all those changes. You wish you had written tests to verify that the changes did not break any existing functionality. You wish you had made the changes incrementally.

Perhaps that example is a little extreme, but it does demonstrate what most people do; code without testing. They make major changes without a clear and concrete way to verify the changes did not break existing functionality. This results in a lack of confidence in the code after making the changes, because there are not enough test cases written to cover every possible aspect.

In this article, you will be introduced to the concept of writing unit tests1 for your projects, and going a step further, to begin driving your development process with the test first, code later concept. And in order to introduce an interesting project to test drive with, you will be exposed to expression objects in the latter part of the article, where each action of an object does not result in a copy of itself, but merely an object representing that expression.

Motivational example

For some obscure reason, imagine there is a need in your application to have arrays of numeric values. The arrays as a whole must be able to perform multiplication by a scalar value, as well as addition and multiplication of two arrays of the same size and type. For even more obscure reasons, your project manager has decided it must be a template class so that it can be reused for other types and sizes. For further obscure reasons, he does not want to use an external library, but wants it written by you. (Gotta 'love' the management.) Citing an example of how it should work, 

array<int, 1000> x, y;
x = 5 * x + x * y;

Going through the user story, a list of the following requirements can be quickly generated:

  • Template array class that allows different types and sizes
  • Allows natural multiplication expression of an array with a scalar value
  • Allows natural multiplication expression of an array with other arrays of the same size and type
  • Allows natural addition expression of two arrays of same size and type
  • Allows assignment between arrays of same size and type

Beginning development on the new object

On receiving such a requirement, most programmers' first impulse is to simply fire up their editor and start chunking out code like a factory. However, I would like to restrain you from doing so, and to instead take a step back, breathe in, and begin considering how you can test each requirement. "Why?", you may ask. Citing the earlier introductory example, tests for each aspect of functionality is important, because they tell you that the code is still working even after the changes you just made. They also tell the customer that your code are still working, serving to boost their confidence in you. Knowing that your code are still working you can carry on adding more new things, with their corresponding new tests. And the cycle goes on.

Writing test cases that handle each requirement also ensures that we strictly follow the requirements handed to us, and secondly, writing test cases first ensures that we do not write unnecessary code. In most cases, starting work on a class without test cases is too much leeway given to programmers. They soon get creative and start introducing unnecessary features and functions, and what should have been a slim, thin, library class becomes bloatware. Secondly, some who start coding the classes first eventually produce classes that are hard to use, and similarly hard to test.

The development platform will be Microsoft Visual C++ 2003, using CPPUnit2 as our unit testing tool. To begin with the development, let's begin with a barebone skeleton suite3 for the unit test cases for our project. CPPUnit is not the topic to cover here, though, so I will simply provide the code required below. Note that for demonstration purpose, namespaces will not be used for the suite of test cases as well as the Array class. I would, however, strongly encourage the use of namespace in your own development.

//--------------main.cpp----------------
#include "array_test.hpp"
#include <cppunit/extensions/TestFactoryRegistry.h>
#include <cppunit/ui/text/TestRunner.h>
#include <iostream>

int main(int argc, char** argv)
{
  CppUnit::TextUi::TestRunner runner;
  CppUnit::TestFactoryRegistry &registry = CppUnit::TestFactoryRegistry::getRegistry();
  runner.addTest(registry.makeTest());
  bool success = runner.run("", false);

  std::cout << "Press enter to continue..." << std::endl;
  std::cin.get();
  return 0;
}

//--------------array_test.hpp----------------
// Generated by Henrik Stuart's .hpp generator: www.unprompted.com/hstuart/
#ifndef array_test_hpp_bf68b031_b047_4d13_92d8_2736b8dded2a
#define array_test_hpp_bf68b031_b047_4d13_92d8_2736b8dded2a

#include <cppunit/extensions/HelperMacros.h>

class array_test : public CppUnit::TestFixture 
{
public:

private:
  CPPUNIT_TEST_SUITE(array_test);
  CPPUNIT_TEST_SUITE_END();
};

CPPUNIT_TEST_SUITE_REGISTRATION( ArrayTest );

#endif // array_test_hpp_bf68b031_b047_4d13_92d8_2736b8dded2a

After creation of the above two files, running the resulting application (after linking to the cppunit library you built with the source from the cppunit download), would show a console screen saying "OK (0 test)".

First Test Case

Let's see how we can start implementing the first requirement... oops, I mean the test for the first requirement.
Template array class that allows different types and sizes

That's actually pretty easy to write a test case for it. To fulfill the requirement, we simply need to be able to declare a template array class for different types and sizes.

void test_declaration()
{
  array<int, 100> a;
  array<double, 5> b;
}

Due to the lack of full-fledged reflection in c++, we would need to, after adding this test case to the array_test class, manually add an entry to the CPPUNIT_TEST_SUITE section. The resulting CPPUNIT_TEST_SUITE section should look as follow. 

CPPUNIT_TEST_SUITE(array_test);
  CPPUNIT_TEST(test_declaration);
CPPUNIT_TEST_SUITE_END();

Note that in languages that support a more powerful version reflection methods like Java and C#, there is no need for this manual creation of CPPUNIT_TEST_SUITE.

There, we have our first test case. So let's compile it. Compilation fails, as expected. Why did we compile even when we knew we would fail the compilation? The compiler acts as a to-do list for us. Our job is to simply resolve all the errors (and even warnings for those more zealous programmers out there), no more and no less. Looking at the list of compilation errors, we can simply deduce that they are all due to the missing array class. No worries, let's start coding the array class.

//--------------array.hpp----------------
// Generated by Henrik Stuart's .hpp generator: www.unprompted.com/hstuart/
#ifndef array_hpp_a650bf08_e950_4ea1_99bd_a579ae1d2179
#define array_hpp_a650bf08_e950_4ea1_99bd_a579ae1d2179

#include <cstddef>

template<typename T, std::size_t Size>
class array
{
};

#endif // array_hpp_a650bf08_e950_4ea1_99bd_a579ae1d2179

You may have noted that this class does nothing. In fact, it is not even an array, but simply an empty shell! It is, however, the perfect class. It does nothing more than it should right now, which is simply to eliminate the compilation error. With the inclusion of this file in our array_test.hpp, we managed to receive zero compilation errors (though we did get two unreferenced local variables warnings). After running the test case, you should get an OK (1 test). Great, we are progressing!

Moving along

Moving along to the next requirement,
Allows multiplication of an array with a scalar value

So how are we going to test this requirement? As easy as the first case, it appears.(Remember to add the function to be tested to the CPPUNIT_TEST_SUITE section, as with all the following test functions)

void test_scalar_multiplication()
{
  array<int, 100> a;
  a * 5;
}

And so we hit the compile button again, and the compilation error comes as no surprise. It can't find the * operator which multiples an array with a scalar, so we go ahead and add the operator in the array class. 

void operator*(T const& t) const {}

Yes, the operator is even more meaningless than the class. It simply does nothing, and returns nothing. Yet it serves its purpose for now, as the program compiles fine. Running the suite of test cases gives us the green bar4. All is well, but we realize the test case is pretty dumb. We need a way to verify that the array is working. How, then, can we verify that the scalar multiplication works? We need to assert it, of course.

void test_scalar_multiplication()
{
  array a;

  for (int i = 0; i < a.size(); ++i)
    a[i] = i;

  a = a * 5;
  for (int i = 0; i < a.size(); ++i)
    CPPUNIT_ASSERT(a[i] == i * 5);
}

Rethinking the testing, a new test case is developed. As expected, compilation fails. The new test case has forced us to introduce more functions to the class, but they are as we would most likely use them, a size member function, and a subscript member operator. We could just introduce them simply, but I would feel safer if I know that these functions work properly as well when tested independently. So, we take a step back, comment out the previous test case, and instead, we introduce a new test case for the size function first.

void test_size()
{
  array<int, 100> a;
  CPPUNIT_ASSERT(a.size() == 100);
}

And we compile again (I remind you of this repetitive step to reinforce what we are doing here), with the compiler complaining of the lack of the member function size. A typical implementation would be as below, 

const std::size_t size() const { return Size; }

But that is only when the implementation is crystal clear in your mind. A more TDD5 approach would be to simply make it work for our test case. Remember, resolve the errors, no more, no less.

const std::size_t size() const { return 100; }

After running the test case, and getting the expected result, we know we have to make size work for different template arrays. So we add in another assertion in the test_size function

array<double, 5> b;
CPPUNIT_ASSERT(b.size() == 5);

Before you make the change to the size function, run the suite of test cases first. Expect it to fail. If it does not, there is something wrong somewhere. Having it run successfully when you expect it to fail is as discomforting as you expect it to succeed instead of failing. In any case, you should have gotten a similar error message as below, 

!!!FAILURES!!!
Test Results:
Run:  2   Failures: 1   Errors: 0

1) test: array_test.test_size (F) line: 22 e:\development\projects\library\array_test.hpp
"b.size() == 5"

To make the code work, we do the obvious change, 

const std::size_t size() const { return Size; }

Compile and run. Green Bar.

Next we need the subscript operator. It should support reading and writing. An obvious test case would be as follows:

void test_subscript_read()
{
  array<int, 100> a;
  for (int i = 0; i < a.size(); ++i)
    CPPUNIT_ASSERT(a[i] == 0);
}

Compile, and fix the error. We need the subscript operator. Do we actually need to introduce the member array in the class? Not yet actually. A simple hack would have made the compiler happy.

const T operator[](std::size_t i) const { return 0; }

Compile and run. Green Bar. Now we need to test the writing part of a subscript operator. The test case should basically be a simple write and read and assert.

void test_subscript_write()
{
  array<int, 100> a;
  for (int i = 0; i < a.size(); ++i)
    a[i] = 0;

  for (int i = 0; i < a.size(); ++i)
    CPPUNIT_ASSERT(a[i] == 0);
}

Compile it, and the compiler complains of '=' : left operand must be l-value. Remember we had returned a const T from the subscript operator. So we actually need to have one that returns a value that we can assign to. So do we need the internal array now? Actually, no, not yet. Why, after this long, are we still not introducing the member array variable? The reason is that we must always follow the rule of not introducing new features until we must. That way, we can get away with the smallest/most slim class interface, as well as get the most return on investments on production, since there are cases where you introduce a new feature that will be useful earlier, but not necessary and get no return on investments. So, to resolve our current compiler error, 

public:
  T& operator[](std::size_t i) { return temp_; }
private:
  T temp_;

Compile and run. Red bar! An assertion error!

!!!FAILURES!!!
Test Results:
Run:  4   Failures: 1   Errors: 0
1) test: array_test.test_subscript_read (F) line: 28 e:\development\projects\library\array_test.hpp
 "a[i] == 0"

A quick look would tell us that the non-const version is actually called for both version, and temp_ has not been properly initialized. It turns out we need a constructor for our array class after all. 

explicit array():temp_(0) {}

Compile and run. Green bar, finally. Reviewing the implementation and test case, it is obvious that the subscript is not working as intended. We need to further assert the test case.

for (int i = 0; i < a.size(); ++i)
  a[i] = i;

for (int i = 0; i < a.size(); ++i)
  CPPUNIT_ASSERT(a[i] == i);

Compile and run. Red bar. So, we need the array after all. Let's introduce the variable first, as v_, and remove temp_.

T v_[Size];

Compile first so we get a list of errors to missing references of temp_. Remove and replace those with v_

explicit array() { std::fill_n(v_, Size, 0); }
T& operator[](std::size_t i) { return v_[i]; }

Compile and run. Green bar. We could now move on back to the scalar multiplication. But wait - why did it run properly, when we have a wrong implementation as the const version of the subscript? To get the bug to shout at us, we need to manifest it as a test case. We will add an additional assertion in the test_subscript_write

array const& b = a;
for (int i = 0; i < b.size(); ++i)
  CPPUNIT_ASSERT(b[i] == i);

Hooray! Red bar! Let's fix it!

const T& operator[](std::size_t i) const { return v_[i]; }

Hooray! Green bar! Back to scalar multiplication!

Back to scalar multiplication test case and others

Uncomment the scalar multiplication test case and compiling the code gives us one compilation error. It is complaining that there's no assignment operator defined that takes in a void, which is the returned type of operator*. So apparently we need to rework that a bit. Under most circumstances I might generate an assignment operator that takes in a void, but that function would be meaningless in other operations. So I went ahead and let operator* returned a new array object.

array operator*(T const& t) const { return array(); }

Compile and run. Red bar. That is expected, because no scalar multiplication was actually performed. So we need to rework the implementation of operator* to perform a multiplication of 5. Why did I say 5, specifically? Because that is the fix that will make this test case work, so we should do that for now.

array operator*(T const& t) const
{
  array tmp;
  for (std::size_t i = 0; i < size(); ++i)
    tmp[i] = operator[](i) * 5;
  return tmp;
}

Notice that also the function is expressed in terms of other member functions. In fact, it has given us a strong hint that we can create operator* not as a member function, but as a free function.

template<typename T, std::size_t Size>
inline array<T, Size> operator*(array<T, Size> const& a, T const& t)
{
  array<T, Size> tmp;
  for (std::size_t i = 0; i < tmp.size(); ++i)
    tmp[i] = a[i] * 5;
  return tmp;
}
template<typename T, std::size_t Size>
inline array<T, Size> operator*(T const& t, array<T, Size> const& a)
{
  return operator*(a, t);
}

Compile and run. Green bar. But is it working yet? We know it's not, so we need a better assertion test.

for (int i = 0; i < a.size(); ++i)
  a[i] = i;

a = 8 * a;
for (int i = 0; i < a.size(); ++i)
  CPPUNIT_ASSERT(a[i] == i * 8);

Note the differing expression 8 * a, instead of the usual array * scalar format. This is to test and verify that the other operator* works. Compile and run. Red bar. Fix the scalar multiplication function to make use of the variable t now

tmp[i] = a[i] * t;

Compile and run. Green bar.

Rest of the list

Let's review the list again.

  • Template array class that allows different types and sizes
  • Allows natural multiplication expression of an array with a scalar value
  • Allows natural multiplication expression of an array with other arrays of the same size and type
  • Allows natural addition expression of two arrays of same size and type
  • Allows assignment between arrays of same size and type

Wait a minute, didn't we just perform assignments of arrays earlier? Well it turns out that C++ has synthesize (as it should) the default assignment operator for us (member wise copy semantics), and it worked for our purpose. So, crossing out the to-do list, we have the following left.

  • Allows natural multiplication expression of an array with other arrays of the same size and type
  • Allows natural addition expression of two arrays of same size and type

We will go with addition since it seems the easier to do (funny how one's brain always perceives multiplication as harder). The test case for addition would look like the following.

void test_array_addition()
{
  array<int, 100> a;
  array<int, 100> b;

  for (int i = 0; i < a.size(); ++i)
    a[i] = i;
  for (int i = 0; i < b.size(); ++i)
    b[i] = b.size() - i;

  a = a + b;
  for (int i = 0; i < a.size(); ++i)
    CPPUNIT_ASSERT(a[i] == i + (b.size() - i));
}

Good, a compile tells us we need the operator+ definition. Again we will build it as a free function.

template<typename T, std::size_t Size>
inline array<T, Size> operator+(array<T, Size> const& a, array<T, Size> const& b)
{
  array<T, Size> tmp;
  for (std::size_t i = 0; i < tmp.size(); ++i)
    tmp[i] = a[i] + b[i];
  return tmp;
}

Compile and run. Green bar. Next, onto multiplication of arrays.

void test_array_multiplication()
{
  array<int, 100> a;
  array<int, 100> b;

  for (int i = 0; i < a.size(); ++i)
    a[i] = i + 1;
  for (int i = 0; i < b.size(); ++i)
    b[i] = b.size() - i;

  a = a * b;
  for (int i = 0; i < a.size(); ++i)
    CPPUNIT_ASSERT(a[i] == (i + 1) * (b.size() - i));
}

Compile. It complains that we need the operator* for two arrays.

template<typename T, std::size_t Size>
inline array<T, Size> operator*(array<T, Size> const& a, array<T, Size> const& b)
{
  array<T, Size> tmp;
  for (std::size_t i = 0; i < tmp.size(); ++i)
    tmp[i] = a[i] * b[i];
  return tmp;
}

Compile and run. Green bar! To verify that what the manager cited as an example actually works, let's enter one last test case!

void test_example()
{
  array<int, 100> a;
  array<int, 100> b;

  for (int i = 0; i < a.size(); ++i)
    a[i] = i + 1;
  for (int i = 0; i < b.size(); ++i)
    b[i] = b.size() - i;

  array<int, 100> x = 5 * a + a * b;
  for (int i = 0; i < a.size(); ++i)
    CPPUNIT_ASSERT(x[i] == 5 * (i + 1) + (i + 1) * (b.size() - i));
}

Compile and run. Green bar! We're all done! Now this can be submitted to your project manager!

More changes

All was fine and great, until days later, your project manager come back and tell you that your array class is the performance bottleneck of the project. It creates and utilizes too many temporaries. Your job now is to optimize it.

Reviewing the code, it seems that we could rewrite the array class to provide operators *= and += instead, and eliminate temporaries. However, expression written with *= and += are not as natural as + and *, resulting in resulting unclear code compare to their * and + counterparts. Not to mention such a change would break all existing code that uses the array class. A solution to this problem seems impossible...

...or does it? Apparently the problem here is premature evaluation of expressions even when they are only used as an element in another expression. Reviewing the example given by the project manager, x = 5 * x + x * y, it can be parsed as x = ((5 * x) + (x * y)), where (5 * x) is an expression object and (x * y) is another expression object, and the encompassing ((5 * x) + (x * y)) is yet another expression object, which eventually can be used in a right hand side assignment of a template array object. So let's review a new list of requirements:

  • Expression object representing array multiplication with a scalar
  • Expression object representing array multiplication with another array
  • Expression object representing array addition with another array
  • Assignment of expression object to an array

We will pick addition to work with first.

Addition expression

An early attempt to introduce an addition expression would be to modify the operator+. But wait! Where's the test case? Well, the test case has already been defined. We are reusing the test case defined in the previous implementation of array. All changes should still result in a green bar with the previous test case, and since we are simply redefining operators previously defined, we can reuse the test case as well.

template<typename T, std::size_t Size>
inline array_addition<T, Size operator+(array<T, Size> const& a, array<T, Size> const& b)
{
  return array_addition<T, Size>(a, b);
}

Following the previous steps, we hit compile again. Error. Let's fix it by introducing array_addition:

template<typename T, std::size_t Size>
class array_addition
{
};

Compile, and we get an error again. We need the assignment operator to accept a type of array_addition. In fact, we do not have an assignment operator. So let's go about defining it.

array& operator=(array_addition<T, Size> const& a) { return *this; }

Compile, and error again. We need the copy constructor to accept a type of array_addition as well. In fact, we do not have a copy constructor. So let's go about defining it.

array(array_addition<T, Size> const& a) {}

Compile, and we get an error again (Does this ever end?). Ok, now it complains that we need an array_addition constructor that takes two array objects. Fine.

explicit array_addition(array<T, Size> const& a, array<T, Size> const& b) {}

Compile, and finally no errors. Run (and expect it to fail). Sure enough, we get two failures.

!!!FAILURES!!!
Test Results:
Run:  8   Failures: 2   Errors: 0


1) test: array_test.test_array_addition (F) line: 79 e:\development\projects\library\array_test.hpp
 "a[i] == i + (b.size() - i)"

2) test: array_test.test_example (F) line: 109 e:\development\projects\library\array_test.hpp
 "x[i] == 5 * (i + 1) + (i + 1) * (b.size() - i)"

There are people who wouldn't mind dealing with two failures at a part, but personally, I prefer to work on one problem one at a time. So, in order to concentrate on one problem only, I comment out the second test case.

//  CPPUNIT_TEST(test_example);

Looking at the code, we see that the error happens because a = a + b is not assigned the proper value (as expected). So let's fix that first failure first. First step, let's do the proper assignment in the assignment operator.

array& operator=(array_addition<T, Size> const& a)
{
  for (std::size_t i = 0; i < size(); ++i)
    v_[i] = a[i];
  return *this;
}

Compile, and we get an error again, because array_addition did not define a subscript operator. To fix it, 

const T operator[](std::size_t i) const { return 0; }

Notice it's one of those small fixes again. Our goal is to get our program to compile properly first, then fix the failures as indicated by the test case. In cases where the failure rate is too high, or where we get too many compilation errors, comment out parts of the test cases so we get to fix errors bit by bit. Compile, and run. Red bar, as expected again. Now, we are forced to evaluate the addition expression. So let's work top down again, from outside to inside, black box to white box.

const T operator[](std::size_t i) const { return a_[i] + b_[i]; }

Compile, and it complains that a_ and b_ are not defined.

private:
  array<T, Size> a_;
  array<T, Size> b_;

Small fixes again. Compile, run, red bar again. That's expected because the values of a_ and b_ are not the arrays that were passed in. So we actually need to make them reference the previous array.

private:
  array<T, Size> const& a_;
  array<T, Size> const& b_;

And the compiler now complains of uninitialized references in constructed array_addition objects. We fix it:

explicit array_addition(array const& a, array const& b):a_(a), b_(b) {}

Compile, run. Green bar! Woo hoo! Now let's move on and uncomment the commented out test case. Our rule of thumb is to get all test cases running green before we attempt any more new features. Compile, run. Red bar, as expected (yet again). Looking at the code, the copy constructor is not doing what it should be doing. So let's remedy that.

array(array_addition<T, Size> const& a)
{
  for (std::size_t i = 0; i < size(); ++i)
    v_[i] = a[i];
}

Compile, run. Green bar. Now let's move on to the next feature!

Generalizing the expression object

...or should we? Looking at the example code, we see code breaking, for example, as below. 
a = a + b + a;

To confirm our suspicions, let's add more meat to our test_array_addition test case.

for (int i = 0; i < a.size(); ++i)
  a[i] = i;
for (int i = 0; i < b.size(); ++i)
  b[i] = b.size() - i;

a = a + b + a;

for (int i = 0; i < a.size(); ++i)
  CPPUNIT_ASSERT(a[i] == i + (b.size() - i) + i);

Sure enough, the compiler complains. It seems that we could either come up with operator that accepts array_addition, as well as the other future possible variation, or we could create a generic addition operator. An instinctive first attempt might generate one that looks as follow, 

template<typename Arg1, typename Arg2>
inline array_addition<Arg1, Arg2> operator+(Arg1 const& a, Arg2 const& b)
{
  return array_addition<Arg1, Arg2>(a, b);
}

Except that it wouldn't work, as it's too generic. What we need is a operator+ that only works on array as well as array expressions. Taking advantage of that array and array expression note, it seems we need to introduce another layer of array. However, since array is already in production, we need to abstract the code instead so that existing code is unaffected. So commenting the newly introduced test case out first so we can get the changes to compile, 

template<typename T, std::size_t Size>
class array_impl
{
public:
  explicit array_impl() { std::fill_n(v_, Size, 0); }
  array_impl(array_addition<T, Size> const& a)
  {
    for (std::size_t i = 0; i < size(); ++i)
      v_[i] = a[i];
  }

  const std::size_t size() const { return Size; }

  T const& operator[](std::size_t i) const { return v_[i]; }
  T& operator[](std::size_t i) { return v_[i]; }

private:
  T v_[Size];
};

template<typename T, std::size_t Size, typename Rep = array_impl<T, Size> >
class array
{
public:
  explicit array() {}
  array(array_addition<T, Size> const& a):rep_(a) {}

  const std::size_t size() const { return rep_.size(); }

  T const& operator[](std::size_t i) const { return rep_[i]; }
  T& operator[](std::size_t i) { return rep_[i]; }

  array& operator=(array_addition<T, Size> const& a)
  {
    for (std::size_t i = 0; i < size(); ++i)
      rep_[i] = a[i];
    return *this;
  }

private:
  Rep rep_;
};

Compile, and we get more errors. The array_addition has to change as well. Though we could employ a quick fix here, such a fix would cause too much problem to undo later on. 

template<typename T, std::size_t Size, typename Arg1, typename Arg2>
class array_addition
{
public:
  explicit array_addition(Arg1 const& a, Arg2 const& b):a_(a), b_(b) {}

  const T operator[](std::size_t i) const { return a_[i] + b_[i]; }

private:
  Arg1 const& a_;
  Arg2 const& b_;
};

Compile, and we get more errors. Let's generalize all the usage of array_addition.

template<typename T, std::size_t Size, typename Rep = array_impl<T, Size> >
class array
{
public:
  explicit array() {}
  array(Rep const& a):rep_(a) {}

  const std::size_t size() const { return rep_.size(); }

  T const& operator[](std::size_t i) const { return rep_[i]; }
  T& operator[](std::size_t i) { return rep_[i]; }

  template<typename Array>
  array& operator=(Array const& a)
  {
    for (std::size_t i = 0; i < size(); ++i)
      rep_[i] = a[i];
    return *this;
  }

private:
  Rep rep_;
};

template<typename T, std::size_t Size, typename Arg1, typename Arg2>
inline array_addition<T, Size, Arg1, Arg2> operator+
  (array<T, Size, Arg1> const& a, array<T, Size, Arg2> const& b)
{
  return array_addition<T, Size, Arg1, Arg2>(a, b);
}

Compile, and we get errors. error C2676: binary '+' : 'array_addition' does not define this operator or a conversion to a type acceptable to the predefined operator. Well, apparently it's because operator+ returned an array_addition, and there's no defined operators working with that. No biggie. Let's just change it so that it returns an Array object.

template<typename T, std::size_t Size, typename Arg1, typename Arg2>
inline array<T, Size, array_addition<T, Size, array<T, Size, Arg1>, array<T, Size, Arg2> > > 
  operator+(array<T, Size, Arg1> const& a, array<T, Size, Arg2> const& b)
{
  return array<T, Size, array_addition<T, Size, array<T, Size, Arg1>, 
    array<T, Size, Arg2> > >(
      array_addition<T, Size, array<T, Size, Arg1>, array<T, Size, Arg2> >
        (a, b));
}

Compile. Finally we're down to one error. Right now it's complaining that it can't construct an object out of an addition expression. Looking at the copy constructor we have, it seems to be in the wrong form. So let's provide it with a generic expression copy constructor.

template<typename Array>
array(Array const& a)
{
  for (std::size_t i = 0; i < size(); ++i)
    rep_[i] = a[i];
}

Compile, and woo hoo! Finally all done! But wait! We get a compiler warning. warning C4172: returning address of local variable or temporary. Whoops, we are doing such nasty thing? Let's change the definition of array::operator[](std::size_t) const to not return a reference, but a temporary copy. 

const T operator[](std::size_t i) const { return rep_[i]; }

Now let's run the test case. Whoa! Green bar! After such a big refactoring6. Don't you feel much more confident continuing, knowing that your changes have resulted in more efficient code, and yet not broken any existing code?

Multiplication of Arrays

Before we move on, let's review the list again.

  • Expression object representing array multiplication with a scalar
  • Expression object representing array multiplication with another array
  • Expression object representing array addition with another array
  • Assignment of expression object to an array

Looking at the list, we had unknowingly implemented two requirements, because of the need to have a successful 100% compile rate. Nevertheless, that leaves us with two remaining requirements to meet. We will first touch on multiplication of two arrays. As explained, we will need to introduce an array_multiply object. Let's change the definition of operator* to return an array_multiply, and let the compiler tell us where the errors to fix are at. Because we have implemented an array_addition successfully, we already have a rough idea how the array_multiply should look like. In fact, we can speed things up a bit here, because we are confident that if the test cases break, we know it's when we are adding the array_multiply.

template<typename T, std::size_t Size, typename Arg1, typename Arg2>
class array_multiply
{
public:
  explicit array_multiply(Arg1 const& a, Arg2 const& b):a_(a), b_(b) {}

  const T operator[](std::size_t i) const { return a_[i] * b_[i]; }

private:
  Arg1 const& a_;
  Arg2 const& b_;
};

template<typename T, std::size_t Size, typename Arg1, typename Arg2>
inline array<T, Size, array_multiply<T, Size, array<T, Size, Arg1>, array<T, Size, Arg2> > > 
  operator*(array<T, Size, Arg1> const& a, array<T, Size, Arg2> const& b)
{
  return array<T, Size, array_multiply<T, Size, array<T, Size, Arg1>, 
    array<T, Size, Arg2> > >(
      array_multiply<T, Size, array<T, Size, Arg1>, array<T, Size, Arg2> >
        (a, b));
}

Compile and run. Green bar. Ok, let's move on to scalar multiplication, the last on the list. We need to create a scalar expression that can perform lazy evaluation7, as well as be able to be performed on another expression object, as well as be part of another expression object. So that would mean we need to represent it as an expression object itself. Using the same approach, we change the operator* for scalar multiplication. 

template<typename T, std::size_t Size, typename Arg1>
inline array<T, Size, array_multiply<T, Size, array<T, Size, Arg1>, array_scalar_value<T, Size> > >
  operator*(array<T, Size, Arg1> const& a, T const& t)
{
  return array<T, Size, array_multiply<T, Size, array<T, Size, Arg1>, 
    array_scalar_value<T, Size> > >(
      array_multiply<T, Size, array<T, Size, Arg1>, array_scalar_value<T, Size> >(a, 
        array_scalar_value<T, Size>(t)));
}

template<typename T, std::size_t Size, typename Arg1>
inline array<T, Size, array_multiply<T, Size, array<T, Size, Arg1>, array_scalar_value<T, Size> > >
  operator*(T const& t, array<T, Size, Arg1> const& a)
{
  return operator*(a, t);
}

Upon compiling, the compiler complains of not knowing what array_scalar_value is (actually, as usual, the error message are much more obscure and a lot more, but for the sake of simplicity, I will tell you what the error message is about). So let's introduce the array_scalar_value class.

template<typename T, std::size_t Size>
class array_scalar_value
{
};

Compile and the compiler complains about the lack of a constructor that accepts a type T for array_scalar_value (as expected). Let's add one in.

explicit array_scalar_value(T const& t) {}

Compile and the compiler complains about the lack of a subscript operator for array_scalar_value. Now, a array_scalar_value is not actually an array, so what should its subscript return? To make array_scalar_value mimic an array, it should, of course, return the same scalar value regardless of what subscript index it is passed. I am going to bypass the small fix here again, and instead provide the proper implementation of array_scalar_value:

template<typename T, std::size_t Size>
class array_scalar_value
{
public:
  explicit array_scalar_value(T const& t):t_(t) {}

  const T operator[](std::size_t i) const { return t_; }

private:
  const T t_;
};

All seems to be in good hands, and so we begin to compile, and run the test case. Boom. The red bar appears. Why? After much stepping through, the problem appears to be because multiply is holding reference to a temporary scalar. Apparently this would mean that we would run into the same problem else where. So how do we resolve it? Well, we need a smart way to tell the templates to use reference for array and expression objects, but a copy of the original expression if they are array_scalar_value. So, to solve it, we introduce a array_trait class.

template<typename T>
class array_traits
{
public:
  typedef T const& reference;
};

template<typename T, std::size_t Size>
class array_scalar_value;

template<typename T, std::size_t Size>
class array_traits<array_scalar_value<T, Size> >
{
public:
  typedef const array_scalar_value<T, Size> reference;
};

Now, to take advantage of the newly introduced trait class, we change all instances of Arg1 and Arg2 to become as follows

typename array_traits<Arg1>::reference a_;
typename array_traits<Arg2>::reference b_;

Ok, let's compile and run the test case. Green bar! We managed to introduce expression objects into our array class without breaking any existing code and functionalities! And we still have a robust suite of test cases to run the next time we make changes.

Afterword

The article introduces TDD (Test Driven Development). The example in this code is as it should be, simply an example. For example, in a real scenario, I will simply provide a member operator *= and +=, and simply build the free function operator * and + with the member operators *= and +=. However, for example purpose the above suits the purpose well enough.

The article also goes at the speed of a turtle crawling. Does employing TDD necessarily mean that you will be programming this slowly? Well, yes and no. For most trivial cases you don't need to go through those little fixes like multiply by 5 instead of i first. In fact, for the later stage, I had to skip most of the small fixes and go straight for the actual implementation due to the fact that this is an article, not a book. The little fixes are just a preparation of the thinking for more complicated implementations. Note that beginners to TDD will find the approach rather daunting and weird. But once adopted, they will produce code of a better quality and easy to maintain.

If you have followed through the entire article to this very last stage, you would have appreciated the existence of unit test cases, especially when there is a sudden requirement change, or additional requirements are requested. Should a unit test be removed? No. You should only add more test case, and not remove anything. This allows you to create components that only abide to a stronger binding of the contract it agrees to live by with the rest of the software, not weaken it. Not only that, it allows us to take solid steps one at a time, confidently. Seeing green bars frequently can boost one's confidence. In fact, there are people who got addicted to this method of development, that people start calling them "Test-infected". (Yes I admit, I am one of them)

In the second part of the article, in order to introduce a change to show that the test cases are not a waste of our time, but a helpful toolkit, the concept of expression objects is introduced. I first encountered expression objects in [C++ Templates 2002], and was amazed by their implementation. In terms of games, I can see it expressed, primarily, in terms of matrix and vector calculation. However, I would like to stress that expression objects should, as the intention of my previous article, policy-based particle system, be presented as food for thought, and not the means to all ends. In fact, some can even take it to an extreme to represent actions as commands, and expression objects to stack them up using runtime mechanism, with the key being delayed computation of actions. The main idea presented here is lazy evaluation7, as well as eliminating unnecessary temporaries, yet still using a natural expression form.

All in all, I hope this article has shown you the importance, and benefit of driving your project with tests, as well as opening your mind to the possibilities of expression objects in your code.

Footnotes

1 Unit Tests: http://www.xprogramming.com/Practices/PracUnitTest.html
2 CPPUnit: http://cppunit.sourceforge.net/cgi-bin/moin.cgi
3 Suite of test cases: A collection of related test cases grouped together as a class, so that it can be treated, by itself, as a test case as well.
4 Green bar: the GUI interface of the unit testing tools typically shows the green bars for test cases that succeed, and red bars for test cases that fail.
5 Test Driven Development: Driving your projects with tests. For more information, refer to [Beck 2002]
6 Refactoring: Refactoring is making changes to a body of code in order to improve its internal structure, without changing its external behavior. For more information, refer to [Refactoring 1999]
7 Lazy evaluation: As opposed to eager computation of expression, lazy evaluation delays the evaluation until the very moment it is needed. The up-side is, of course, you don't pay for the evaluation if you do not need it at all. The down-side is, of course, at the point of evaluation cpu cycles is spent to evaluate the expression. At real-time critical situations this is unacceptable. In such case, people would employ eager evaluation instead.

Further Reading

1 [Beck 2002]
2 Engineering Notebook: An Extreme Programming Episode http://www.cuj.com/documents/s=7998/cujcexp1902martin/
3 Artima Articles Articles About Testing http://www.artima.com/articles/index.jsp?topic=testing
4 XP and Agile Methods http://martinfowler.com/articles.html#N400069

References

1 [C++ Templates 2002] David Vandevoorde , Nicolai M. Josuttis : C++ Templates: The Complete Guide, Addison-Wesley Pub Co (12 November, 2002)

2 [Beck 2002] Kent Beck : Test Driven Development: By Example, Addison-Wesley Pub Co (08 November, 2002)

3 [Refactoring 1999] Don Roberts , John Brant , Kent Beck , Martin Fowler , William Opdyke : Refactoring: Improving the Design of Existing Code, Addison-Wesley Pub Co (28 June, 1999)

Sample Code

Get the sample code for this article here.

Discuss this article in the forums


Date this article was posted to GameDev.net: 6/27/2004
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Featured Articles
Formal Methods
Game Engineering

© 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy
Comments? Questions? Feedback? Click here!