• 06/27/04 03:13 PM
    Sign in to follow this  

    Test Driving Expression Template Programming

    General and Gameplay Programming

    Myopic Rhino
    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 tests[sup]1[/sup] 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 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 CPPUnit[sup]2[/sup] as our unit testing tool. To begin with the development, let's begin with a barebone skeleton suite[sup]3[/sup] 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 #include #include int main(int argc, char** argv) { CppUnit::TextUi::TestRunner runner; CppUnit::TestFactoryRegistry (R)istry = 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 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 a; array 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 template 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 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 bar[sup]4[/sup]. 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; a = a * 5; for (int i = 0; i < a.size(); ++i) CPPUNIT_ASSERT(a == 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 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 TDD[sup]5[/sup] 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 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 a; for (int i = 0; i < a.size(); ++i) CPPUNIT_ASSERT(a == 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 a; for (int i = 0; i < a.size(); ++i) a = 0; for (int i = 0; i < a.size(); ++i) CPPUNIT_ASSERT(a == 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 == 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; for (int i = 0; i < a.size(); ++i) CPPUNIT_ASSERT(a == 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_; } 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); Hooray! Red bar! Let's fix it!

      const T& operator[](std::size_t i) const { return v_; } 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 = 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 inline array operator*(array const& a, T const& t) { array tmp; for (std::size_t i = 0; i < tmp.size(); ++i) tmp = a * 5; return tmp; } template inline array operator*(T const& t, array 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; a = 8 * a; for (int i = 0; i < a.size(); ++i) CPPUNIT_ASSERT(a == 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 = a * 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 a; array b; for (int i = 0; i < a.size(); ++i) a = i; for (int i = 0; i < b.size(); ++i) b = b.size() - i; a = a + b; for (int i = 0; i < a.size(); ++i) CPPUNIT_ASSERT(a == i + (b.size() - i)); } Good, a compile tells us we need the operator+ definition. Again we will build it as a free function.

          template inline array operator+(array const& a, array const& b) { array tmp; for (std::size_t i = 0; i < tmp.size(); ++i) tmp = a + b; return tmp; } Compile and run. Green bar. Next, onto multiplication of arrays.

          void test_array_multiplication() { array a; array b; for (int i = 0; i < a.size(); ++i) a = i + 1; for (int i = 0; i < b.size(); ++i) b = b.size() - i; a = a * b; for (int i = 0; i < a.size(); ++i) CPPUNIT_ASSERT(a == (i + 1) * (b.size() - i)); } Compile. It complains that we need the operator* for two arrays.

          template inline array operator*(array const& a, array const& b) { array tmp; for (std::size_t i = 0; i < tmp.size(); ++i) tmp = a * b; 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 a; array b; for (int i = 0; i < a.size(); ++i) a = i + 1; for (int i = 0; i < b.size(); ++i) b = b.size() - i; array x = 5 * a + a * b; for (int i = 0; i < a.size(); ++i) CPPUNIT_ASSERT(x == 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 inline array_addition


      Report Article
    Sign in to follow this  


    User Feedback

    Create an account or sign in to leave a review

    You need to be a member in order to leave a review

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

    There are no reviews to display.