Inner product, round 3: handling I/O

Entering round 3, our sub-problem backlog looks like this:

P1. Prompting the user. 
P2. Computing the inner product. 
P3. Displaying the output.
P4. Test inner product computation in a separate project. 

P1 and P3 deals with I/O, so let's take them both in this round.

Step U. Understanding the problem.

To be useful, your program needs to make contact with the outside world. In this case, the outside world is simply the console input and the console output, supported by C++ through std::cin and std::cout, respectively.

Console I/O seems straightforward enough that people get caught unprepared. As a programmer, you need to beware of what's beyond the console? Who's typing in the input? Who's reading the output? The answer in the most straightforward sense: the user. User makes mistakes; your program needs to be tolerant. This means that your program should do numerous checks for errors committed by the user and respond properly, keeping the program alive.
 

Step D. Devising a plan.

We had our first encounter with std::cout in a typical "hello, world!" program. That was easy. But now, since the console is both the input and the output, things are a little bit more cumbersome, especially in the case of std::cin. So, instead of working closely with std::cin on an item-by-item basis, e.g., reading the components of a vector one at a time, we are going to take the following strategy: get the one vector into a string in one read, and extract the vector from that string. Strings are easy to work with because it is now a variable inside your program, and C++ provides a powerful string object with many routines for manipulations. So we have a decomposition into tasks like

T1. Get user input into a string.

T2. Extract vector from the string.

T3. Test the function written in T2.

T4. Display output to cout.

Note that I have added T3, a task for unit testing. While unit test should accompany any unit of code, people tend to easily forget. The task serves as a reminder. This is simple strategy called "Be specific until it's a habit."

Step C. Carrying out the plan.

T3. Test the function written in T2. In the two tests below, the string s is the string for specifying the vector. For example, the string "2 [1,2]" stands for a 2-dimensional vector [1,1].

TEST (extractVectorFromString, OK)
{
    string s("2 [1,1]");
    int d;
    double * vec;
    vec = extractVectorFromString(s, d);
    LONGS_EQUAL(2, d);
    DOUBLES_EQUAL(1.0, vec[0], 0.0001);
    DOUBLES_EQUAL(1.0, vec[1], 0.0001);
}

TEST (extractVectorFromString, DimErrorUnder)
{
    string s("1 [1,1]");
    int d;
    try {
        extractVectorFromString(s, d);
        CHECK(false);
    }
    catch (char const * s) {
        CHECK(0==strcmp("Dimension error!",s));
    }
} 
 
There is one more point to T3. Our capability to test the user input under cppunitlite without breaking its promise to be "silent unless broken" depends on getting the inputs into strings. Strings are easy to work with in tests, but std::cin isn't. In the code above, the first test gets a string "2 [1,1]", reflecting the case where the user has, correctly, input a two dimensional vector [1,1]. In the second test simulate the case where the user types in "1 [1,1]", a one dimensional vector [1,1], which is obviously is error. Note that the function
extractVectorFromString() throws an exception after detecting this error. 

Here is the working program. 
 

Step L. Looking back. 

In this round, we solved two sub-problems due to to their similarity in nature. Also, looking back at the Step D,  you can see how your knowledge of unit testing changes the way partition a sub-problem into tasks. There is no longer throw-away test code that borrows space from the main function; test code now takes residence and accumulates in the test project. In fact, you can go one step further to practice what is called Test-driven development: write up the test code, then write the production code. We will have more to say about this later.  

Updating the sub-problem backlog, it is found that all sub-problems are solved:

P1. Prompting the user. 
P2. Computing the inner product. 
P3. Displaying the output.
P4. Test inner product computation in a separate project. 

With that, we have solved the problem of computing inner product. The program is mainly in C with some use of C++ objects from the standard library; exception handling is used to deal with errors; and unit tests were written for the program. So, if you run out of development time or the client is in a hurry to release, the program is good to go! 

But since we are doing object-oriented development, we will try to make our vectors object-oriented -- for what? It's time to look back again as a programmer and hunt for improvement opportunities.


Asking questions at the right time help one learn and improve. In How To Solve It, one of the question Pólya asks in Looking Back is this: Can you see it at a glance? Let's ask this question: As a programmer, can you or someone else easily understand what your program does?

We have the following two specific questions:

Can you see that your program is dealing with vectors and computation of inner products?

We can do this by reviewing the code. Let's do this for the the function computerInnerProduct. 

With the exception of lines 4 and 7, and probably the name of the variables that start with the letter v, nothing much of the function is about vectors! As it stands, the code has more "array-ness" than "vector-ness" to it. Further, if you ask anyone who knows vectors in mathematics, they will probably have trouble understanding the for-loop because a vectors starts with dimension 1 rather than dimension 0. 

If you use the functions of this program in the future, what mistakes are you most likely make?

In calling the function computeInnerProduct with vector v1 of dimensional d1 and vector v2 of dimension d2, someone could write

    double r = compuetInnerProduct(v1, v2, d1, d1);

Can you see what is wrong at a glance ? If yes, good for you! But now try this:

   double r = compuetInnerProduct(v2, v1, d1, d2);

Can you still see it at a glance? The trouble with representing a vector with an array of doubles is that the dimension is kept away from the vector. You know that they are tightly related only because you made the cognitive effort to remember this relationship. But the trouble is deeper than you think. If fact, in the array notation, it is easy for someone to write v[2] for getting the component at the second dimension when she/he should write v[1] instead. Having a v[2] instead of v[1] means there is a bug in code, and such a bug is difficult to catch.   
    

Let's pose a new problem in the backlog. 

P5. Representation of vectors: Vector should remember its own dimension; use of vector should follow the convention in mathematics. 

© Y C Cheng, 2013, 2014. All rights reserved.

Inner product, round 2: unit tests and basic exception handling

Entering round 2, our current sub-problem backlog looks like this:

P1. Prompting the user. 
P2. Computing the inner product. 
P3. Displaying the output.
P4. Test inner product computation in a separate project. 

Let's pick P4 for this round. Here, you will learn how to do unit testing and exception handling.

Step U. Understanding the problem.

To the whole program, the function computeInnerProduct is called a unit. By unit testing the function computeInnerProduct, we mean exercising it in numerous ways, away from other units of the program. So far we have two tests, one for normal computation and the other for dimension error, all inside the main program. So, our main program is a unit testing suite consisting of two test cases. How do we know the test results are as expected? We checked the console output. Checks like these can be tedious and error-prone, especially when you have many tests. (And If you are serious about unit testing, you will have many tests.) It is easy for you to miss a message indicating test failure.

There is another subtle but profound problem with unit testing inside the main function. When there are many tests, it becomes tempting to reuse some of the variables used in the tests. When this happens, the reused variables may have already acquired values from previous tests. They may no loner hold the correct values for checking the execution results. In other words, the variables are not clean. This can make test results difficult to decipher and trust. 

Obviously, you can do better than writing test cases in a main function. Before introducing you to one such way, let's summarize what is needed. A unit test is usually composed of a number of test cases, each of which is executed in four steps:

1. Prepare test data.
2. Call the function tested and obtain result.
3. Compare result with expected result.
4. Clean up the test data.

Such repetitive execution makes unit tests a suitable target for framework support. Many unit testing frameworks are available. In these articles, we will be using CppUnitLite, a dialect of xUnit for testing C++ programs. 

In addition to doing most of the repetitive work for you, a unit testing framework like CppUnitLite also makes it easy for you to organized test cases. When combined with the strategy of separating test projects from a production project, this gives you a nice way to accumulate many unit tests in well-organized projects.

For handling the case when two vectors of different dimensions are passed to the function computeInnerProduct, C++ provides a much better way: exception handling. 
 

Step D. Devising a plan.

Let's build our task backlog for sub-problem P4 as follows:

T1. Prepare the CppUnitLite library.

T2. Set up a test project and practice writing unit tests.

T3. Change the function computeInnerProduct so that it can be tested in the test project. 

T4. Relocate test cases from main to the test project.
T5. Learn exception, exception detection and exception handling. 
T6. Replace forced program exit with exception handling. 

The task T3 prepares the function computeInnerProduct for unit testing. The code of the function is allocated in a header file and an implementation file. (T3)
 

Step C. Carrying out the plan.

T3. Change the function computeInnerProduct so that it can be tested in the test project.

We need to make the function computeInnerProduct accessible to the unit tests. Wit unit tests to reside in a separate file, this is done by separating a function into a declaration and a definition; the former is allocated to a header (.h) file and the latter in an implementation (.cpp) file.

   
T6. Replace forced program exit with exception handling.  
By throwing a C-style string, we now replace the forced program exit with following code:

double computeInnerProduct (double v1[], double v2[], int d1, int d2)
{
    if (d1 != d2)
        throw "Vectors of different dimension!";
    double r=0;
    for (int i=0; i<d1; ++i) {
        r += v1[i]*v2[i];
    }
    return r;
}

To test it, enclose the call to the function comuteInnerProduct in a try block and the check in a catch clause:

TEST (computeInnerProduct, dimension_error)
{
    double u[2] ={1,0};
    double v[3] ={1,1,1};

    try {
        computeInnerProduct(u,v,2,3);
    }
    catch (const char * s) {
        CHECK(0==strcmp("Vectors of different dimension!",s));    
    }
}

Here's the working program.

Step L. Looking back.

We now have a separated test project for testing computeInnerProduct. The test project is now the working program for sub-program P2. Can you see the difference? Rather than showing a screen full of messages that confuse you, CppUnitLite is silent if all tests pass, as below:

Best of all, CppUnitLite is specific when a test fails:

 
Another important thing we have learned is writing unit tests for the exception handling code. (T6)

In the future, when we solve sub-problems P1 and P3, we shall write unit tests for any functions we code up. When any change is made to the functions in the production project, make sure to run the unit tests in the test project. This way, if any thing is broken, we'll be able to know quickly.

Now that we have freed up the main program from borrowed use by the tests, we can move forward to the next sub-problems.

© Y C Cheng, 2013, 2014. All rights reserved.

Inner product, round 1.

Problem. Prompt the user to input two vectors. Compute the inner product (or dot product) of two vectors when it is defined. For example,

    [1, 0] · [1, 1] = 1,
    [1, 1, 0] · [0, 1, 1] = 1, and
    [1, 0] · [1, 1, 0] => undefined.

Prompt the user whether to continue or stop.

Step U. Understanding the problem.

The examples in the problem are simple enough, and there is no mentioning of the the case where the user inputs an malformed vector. (We will get back to this problem later.) So, let's do a similar but slightly different decomposition from the last article by decomposing the problem into three sub-problems: prompting the user for vector, computing the inner product, and displaying the output. Let's list the sub-problems in a backlog:

Problem backlog
P1. Prompting the user. Display a welcome message; invite user to input a vector, and get the vector. 
P2. Computing the inner product. Given two well-formed vectors, compute their inner product if defined. Flag an error otherwise. 
P3. Displaying the output. Display the output message that show the input vectors and the inner product.
 
Each sub-problem is called a backlog item in the sub-problem backlog. Upon its entrance to the backlog, a sub-problem has been analyzed to give a more precise definition. With the definition, we should be able to determine the type of the sub-problem. Thus, P1 and P3 are about i/o; P2 is about computation.

You should check if you can solve the problem by solving all sub-problems. A little thinking shows that you can: Write a main program that works as follows:

repeat 
    P1(prompt for vector 1)
    P1(prompt for vector 2) 
    P2(vector 1, vector 2)
    P3(output result and prompt for continuation)

Since the decomposition is only a guess, it does not have to be perfect. At any rate, since we are doing multiple rounds, in step L for each round, we can always write up new items for what we did not do so well initially.

Which sub-problem should you begin with? Although any sub-problem in the backlog would do, the general rule is to select the sub-problem that the user cares the most. Since the solution of the whole problem hinges on computing the inner product, let us begin with sub-problem P2.

Step D. Devising a plan. 

List the tasks to be completed for sub-problem P2. Recall that a task is a unit of work that should be straightforward. That said, it should be clear that the list of tasks depends on the worker -- you. If you know C programming already, you'll probably have a list like this:

T1. Write a function to compute inner product - normal case.
T2. Handle the case where an inner product is not defined.
T3. Write supporting program to exercise the function.  

Task T3 is needed because we insist on having a working program at the end of a round. Without T3, you don't know if you're coding up the function correctly.

However, if you do not yet know how to code up a function, represent a vector, and so on, T1 would probably benefit from further decomposition into something like

T1. Write a function to compute inner product.
    T1-1. Learn C function.
    T1-2. Learn how to represent vector.
    T1-3. Learn passing vector to a function.
    T1-4. Write the inner product function.
T2. Handle the case where an inner product is not defined.
T3. Write supporting program to exercise the function.  
    T2-1. Learn how to call a C function.
    T2-2. Write supporting program.

A rule of thumb: if a task is not straightforward to you as a unit of work, further decompose it until you feel comfortable handling. 

The two lists intend to solve the same problem. In the first list, you are applying what you already know. In the second list, you are learning something new and putting it to work immediately afterward. So, don't feel you are behind just because you happen to have a longer list for a problem. A longer list just means you have to spend more time but it is definitely doable.

Back to the list. The list of tasks is called a task backlog for solving a sub-problem. In general, there is no implied order of working on the tasks; you get to decide which task to work on.
 
Step C. Carrying out the plan.

This is the step you can expect to spend the most amount of time in the four steps in solving a sub-problem. While each task is straightforward, in this step you use -- and learn -- your knowledge on programming and engineering practices to write code of good quality. Without getting into detail for now, at the end of T1, you have code like this:

double computeInnerProduct (double v1[], double v2[], int d1, int d2)
{
    double r=0;
    for (int i=0; i<d1; ++i) {
        r = r + v1[i]*v2[i];
    }
    return r;
}

But does the function work? How do we check it? The obvious way is to call it and output something for you to check. This is the task of T3. So, we are going to write a main function and call the inner product function there. At the end of T3, you have supporting code to exercise the function like this:

#include <iostream>

using namespace std;
 
int main() 
{
    double u[2] ={1,0};
    double v[2] ={1,1};
    double ip; 
    
    ip = computeInnerProduct(u,v,2,2);
    cout << ip << endl;
    return 0;    
}

Compile and run, you get something like this:

The first line shows the expected inner product "1" of the two vectors "[1,0]" and "[1,1]".

Carry on with T2. The inner product is not defined if the two vectors are of different dimensions. We fix the code in the function computeInnerProduct and the function main like this:


#include <stdlib.h> 
#include <iostream>

using namespace std;
double computeInnerProduct (double v1[], double v2[], int d1, int d2)
{
    if (d1 != d2) {
        cout << "vectors of different dimension, aborting..." << endl;
        exit(-1);
    }

    double r=0;
    for (int i=0; i<d1; ++i) {
        r = r + v1[i]*v2[i];
    }
    return r;
}

int main()
{
    double u[2] ={1,0};
    double v[2] ={1,1};
    double ip;

    ip = computeInnerProduct(u,v,2,2);
    cout << ip << endl;

    double x[2] ={1,0};
    double y[3] ={1,1,1};
    ip = computeInnerProduct(x,y,2,3);
    return 0;
}
The result is something like this:

We have a working program!

Step L. Looking back.

In this step, inspect the program and identify places where improvements are needed. We have a function that appears to compute inner product when two vectors are of the same dimension and abort otherwise. Also, we are using the main function to exercise the function. The main function consists of two tests for computeInnerProduct: a normal case and a case where inner product is undefined. Because the program is not yet complete, it is probably premature to look back in the role of a user. On the other hand, we can always look back as a programmer. 

The program aborts when given two vectors of different dimensions, but the problem says it should continue after displaying a proper message. This needs to be fixed.

Are the two tests sufficient? It seems so because every line of code in the function computeInnerProduct is exercised. But you can always add new tests. When you do, the tests will be added to the main function in the current structure of the program. This means that the main function has to be changed frequently. But there is another problem: later, we will need the main function to interacts with the user. When that moment comes, what do you do with the tests? 

My suggestion: relocate the tests from the main function. Even better, relocate the tests into another project, one which we shall call a test project. That way you have two projects: a production project and a test project. We will add a new sub-problem: 

P4. Test computeInnerProduct in a test project.

© Y C Cheng, 2013, 2014. All rights reserved.

Introducing "How to solve it: CPP"

Learning to develop object-oriented software can be challenging for three reasons.

First, you are learning features of a new language, in this case, C++. Being a superset of the C language, C++ adds many new features for representing objects, exceptions, name spaces and templates, etc.

Second, you are learning a new way to think about program design where objects and collaborations are the main abstractions. You may not be able to write a object-oriented program even if you learn the features of an object-oriented programming language. In the case of C++, many new language features enable you to use it as a better C, but that does not guarantee object orientation.

Third, you are learning to develop software not just out of curiosity. You do so because you want to able to build useful applications. Since useful applications are usually are somewhat complicated, this will require you to learn good work habits and engineering practices.

I am writing these articles to help you take up the three challenges when you learn C++ for the first time. The articles come in groups that are threaded by a number of long running examples. My preference for long running examples over short examples is that the former sets a context where object orientation and engineering practices really make more sense. That said, isolated, small examples come in handy when you are trying out a new language feature. Many existing textbooks and online resources do a good job covering this aspect. Thus, I am not going to spend time writing about them in these articles.

In these articles, an example always begins with a problem statement and ends with a program that solves the problem. You may ask, then, what makes an example long running? The obvious answer would be that the problem in the example is complicated enough that a conceivable program for solving it will be large in size (e.g., when measured in lines of code, or LOC.) Real world applications fall into this category. In these articles, there is another category of long running examples: ones that are designed to give you opportunities for learning new language features, object orientation, and engineering practices. 

Since the examples will be long running, some kind of decomposition of the problem is necessary. Nearly all problems can benefit from decomposition. Let us look at an example.

Problem. Compute the inner product (or dot product) of two vectors when it is defined.

As a problem it is simple enough if you know what a vector is, but we can still benefit from a decomposition into three sub-problems: handling the input, computing the inner product, and displaying the output. In handling the input, you have to decide how the user inputs data (i.e., two vectors) to your program. Does she type in the input on the command line? Does she react to prompts by your program? Or, does she put the data in a file to be read by your program? To know exactly which option(s) to take, you'll have to ask your user. (Then again, always be aware that the user can change her mind.) You must also address errors committed by the user such as inputting two vectors of different dimensions, a malformed vector, and so on. Handling the input ensures that inner product is only computed for two well-formed vectors with an identical dimension. 

The benefit? You can then organize the code in handling input and computing inner product in separate units, each of which will be easy to understand and modify. Your code for computing an inner product will be clean without the need for checking for malformed vectors. Even better, when the user changes her mind about the way vectors are input, you'll be glad that you have a single place to look for the required change.

With a decomposition into sub-problems, you can now start working on them. You certainly don't want to work on all sub-problems simultaneously, being aware of our cognitive limit and the fact that it defeats the purpose of decomposition. So, a practical way to do it is something like this: work on one sub-problem at a time; work on the next sub-problem, and so on, until you're done. In these articles, I am going to frame the problem-solving process after George Pólya's four well-known steps of solving mathematical problems in his classic How To Solve It: understanding the problem, devising a plan, carrying out the plan, and looking back.

• Understanding the problem (U): you must first understand what the requirements are before building a program to solve the (sub-)problem on hand.Thus, ask the following questions: What is the input? What is the output? What are the constraints?
• Devising a plan (D): once you fully understand the (sub-)problem on hand, list the tasks required for its solution. The tasks, once determined, should have the quality of being straightforward to complete. That is, the tasks are your units of work.
• Carrying out the plan (C): pick one task at a time, code it, test it, and integrate it with the existing code. Repeat this until all tasks related to the (sub-)problem are done.
• Looking back (L): Inspect the program and identify places where improvements are needed. Do this in your role as a programmer and as a user. Treat any identified improvement as a new task or a new sub-problem.

 Each sub-problem goes through the four steps. Combining decomposition and the four steps, we have something like this:  

    U--D--C--LU--D--C--LU ... U--D--C--L
    1---------2---------3-... n--------done!

Each of the numbers 1,2, ..., n  denotes an episode or a round of solving a sub-problem. At the end of each round, you must have a working program, i.e., one that can be run. When I say a working program, I mean it in the accumulative sense: you don't want to solve a sub-problem only to break a previously solved sub-problem. When you reach the "done!" mark, you have solved all the sub-problems and hence the problem.

You must have many questions. Some of them could be: which sub-problem should I work on first when there are many sub-problems? How do I make sure the working program I get at the end of a round really solves the sub-problem? How do I integrate the code for the current sub-problem into the code base for the whole program? An so on. Later, I will help you find out the answers for yourself. But enough principles now, let us move on to our first long running example.

© Y C Cheng, 2013, 2014. All rights reserved.