Our programs are getting longer. On one hand complicated problems require complicated programs, but on the other hand, long programs are difficult to understand, and after reliability, understandability is the most important design goal. More time and money is spent in the maintenance phase of a program's life cycle than in its development phase. Maintenance means testing, debugging, and modifying. These are difficult and risky operations if the person performing them—often not the developer --doesn't understand the program.

We need some way to manage the complexity of large programs. Comments, documentation, layout, and choosing suggestive names help, but not nearly enough. We need something more powerful. The two most powerful principles in engineering for controlling complexity are:

A module is any kind of programming building block: functions, files, namespaces, data structures, types, classes, objects, etc. Loosely coupled means dependencies between modules are minimized. Coherent means the function or purpose of a module is well defined. A coherent, loosely coupled module is easy to replace and easy to reuse.

There are two ways to look at a module. The client (i.e., user) sees a module in terms of its function or purpose, while the implementer sees a module in terms of its internal structure, in terms of how rather than what function it performs. We call the client's view the module's interface and the implementers view the module's implementation. The abstraction principle says a client shouldn't need to know about a module's implementation in order to use it, and the implementer should be able to change the module's implementation without breaking the client's code (assuming the interface doesn't change).

For example, we are clients of the functions, classes, and objects in the C++ standard library. We use cin, cout, sin(), sqrt(), <<, etc. but we don't particularly care how they are implemented. We become frustrated when, for example in the case of having to flush cin's buffer, we are forced to understand implementation details. (Many of the functions and classes in the C++ standard library-- not to mention the language itself --are poorly designed.)

Taken together, the modularity and abstraction principles say that the overall design or architecture of a program should be understandable without needing to understand the implementation of the component modules, and the design of a component module should be understandable without needing to understand the entire program.

C++ provides many types of modules or abstraction mechanisms. For now we will focus on functions. Functions are sometimes called procedures, so building programs out of functions—i.e. using functions as the primary building block --is called procedural programming. The terms structured programming, functional decomposition, and imperative programming are also used.

A function definition consists of a function header followed by a block statement. The header tells us the function's return type, name, and parameter list. For example:

defines a function named dist. It expects two parameters of type double. (Be sure to include <cmath> to declare fabs.) Inside the program's block these parameters are called x and y. The function returns a double representing the distance between x and y on the number line. (Note the helpful comment explaining the interpretation of the return value.)

The function may be called many times. Each time it is called, two expressions called operands must be supplied. Executing the operands produces values called arguments. These arguments are substituted for the parameters x and y in the function's block. For example:

prints:

We called dist three times. (Don't confuse calling and defining a function). In the first call we supplied two arguments: 6.5 and 6.56. These arguments replace the parameters in the function's block, producing the statement:

The statement is executed. fabs(6.5 – 6.56) produces the value 0.06, which is returned to the caller, i.e. the function that called dist(). Every function except main() has a caller. In our example the caller was the insertion operator: <<. Essentially, fabs(6.5 – 6.56) is an expression that produces the value 0.06.

Important terms: calling a function, defining a function, caller, parameter, operand, argument, return value.

The basic idea behind procedural programming is top down design: when main() gets too long—say more than half a page –we break it up into calls to loosely coupled, coherent supporting functions. We apply the same idea to the supporting functions. We repeat this process until there are no more supporting functions to be defined.

Assume a plumbing supply manufacturer assembles pipes capped at both ends:

The assemblies have different lengths (l) and diameters (d). The manufacturer would like a program that perpetually prompts users for l and d, then computes and displays the pipe's volume.

We might begin with the interpreter pattern we have been using:

Notice that we computed the volume of the pipe by calling a function named pipeVolume(). Is this a standard C++ library function? It might be; it's worth a check, but alas, it is not. No worries, we'll define our own:

Note that we can choose any names we want for our parameters, as long as there are two and they are of type double (because that's what the caller expects). Following the modularity principle, we look for some way to break pipeVolume() into calls to loosely coupled, coherent supporting functions. We use the physical geometry of the pipe as our guide. The pipe is assembled out of a cylinder of radius = d/2 and length = l – d and two hemispherical caps, which, when glued together, form a sphere of radius = d/2. The volume of our pipe is simply the sum of the cylinder volume and the sphere volume:

Perhaps cylinderVolume() and sphereVolume() are standard C++ library functions. Again, it's worth checking, again we're disappointed, and again we must define our own:

The volume of a cylinder is the area of its circular base times its length:

Is circleArea() in the C++ library? No, but the area of a circle is simply pi times the radius squared:

Surely square() is in the standard library. Nope:

Pi must also be defined, but we will also need pi to compute the sphere's volume. If we define pi as a local variable of circleArea(), i.e. inside circleArea()'s block, then it won't be visible inside sphereVolume(). Even if we make pi a local variable of main() it won't be visible inside sphereVolume(). The solution is to make pi a global variable. A global variable is defined outside of all function blocks, including main()'s. the scope of a global variable is the entire program:

Of course sphereVolume() isn't in the C++ library, so we must define it. According to my geometry book the volume of a sphere is:

It seems wasteful to recalculate the constant 4/3 p each time sphereVolume() is called. By defining it as a global variable it will be calculated once at the beginning of the program:

Here is our implementation of sphereVolume():

What about cube()? It too must be defined:

Now we can build (i.e. compile and link) and test our program:

Diagrams are often useful for understanding the structure of a program. In procedural programming dependency graphs are often used. The nodes of a dependency graph represent functions and an arrow connecting nodes indicates that one function calls another:

The calling function depends on or is supported by the called function. A change to the called function may impact the calling function. Here's a dependency graph for our application:

Note that we can eliminate the dependency of cube() on square() by redefining cube() as follows:

This actually makes cube() more reusable because we only need to add cube() to a new project. We don't need to remember that square must also be added.

Here's an alternative implementation of pipeVolume(). It is correct, but would you want to maintain it?

The three "helper" functions are not cohesive, hence not reusable:

I have over simplified the function call mechanism used by C++. I said when a function is called:

For example, assume we want to call dist(6 + 7, 6 * 7). In step 1 the operands 6 + 7 and 6 * 7 are executed (i.e., evaluated) to produce the arguments 13 and 42. (Note: the order of evaluation is not specified.) In step 2 the arguments replace the parameters x and y in the block to form the new block:

Finally, the block is executed, producing the value: 29.

this is called the substitution model for function calling. Unfortunately, because of local variables, the substitution model is too simple. Instead, we must use the stack model. Instead, of substituting arguments for parameters in step2, a frame is created containing variables corresponding to the parameters and local variables. These variables are initialized by the arguments:

The frame is pushed on the program's stack. The block is now executed relative to this frame. When the function terminates, the frame is popped off the stack.

Constructing and destroying frames can be inefficient. It almost seems wasteful for short functions. C++ solves this problem with inline functions. Calls to an inline function use the substitution model instead of the stack model. To do this, just place the inline specifier in front of the function definition:

Warning: only declare a function to be inline if its block is simple. Functions containing loops in their blocks should not be declared inline. Also, an inline function must be defined in every file where it is called.

The stack model has two potential downsides. First, if the arguments are large data structures, for example, long arrays, then copying them into the parameters may be inefficient. Second, any modifications a function makes to its parameters will be lost when the frame is destroyed (i.e., popped off the stack).

The second disadvantage can also be an advantage. If, for example, the argument is a global variable that must be shared with other functions, then inadvertently modifying a parameter unintentionally modifies the global. However, there are some cases where this is exactly what we want. For example, suppose we want to create a function that swaps the values of any pair of integer variables. We might try this:

A quick observation is needed here. The goal of swap() is to swap the values stored in two variables. This is the way it might be called:

Notice that no return value is expected, only the side effect of swapping a and b. Because swap() isn't expected to return a value, it does not contain a return statement. Instead, the function terminates when control reaches the end of its block. But all C++ function headers must declare a return type. C++ provides a void type which is used in two situations. It is used as the return type for functions that don't return values, such as swap() and it is used as the base type for generic pointers:

Unfortunately, swap(a, b) fails to swap a and b. A frame is created with x = 42, temp = 42, and y = 35. x and y are swapped:

then the frame is destroyed, leaving a and b unchanged.

The traditional solution to this problem is to use pointers. Instead of passing the values of a and b to swap, their addresses are passed:

Of course the client must pass addresses, not integers, to swap():

Here's what the frames look like:

I have two objections to the implementation of swap(). First, all the pointer dereferencing is confusing and scary. I suppose I could get used to it, but what about my poor client. He too must know enough about pointers to remember that it's &a and &b, not a and b that must be passed to swap().

C++ offers another solution. A reference is basically a constant pointer, only C++ automatically dereferences them and automatically converts variables assigned to them into addresses. For example, assume x is an integer variable:

An integer reference is declared like this:

This is translated to:

The assignment:

is translated to:

With references we can re implement swap() as follows:

The client doesn't need to compute addresses:

Passing references is more efficient than passing values because only addresses are copied, but passing references is risky because programmers aren't protected from inadvertently modifying the client's variables. We can have the best of both worlds by declaring parameters to be constant. For example, assume members of a user defined type are large:

A function that expects a shape as an input can declare a constant reference parameter:

Any attempt to modify s in the block of the function generates a compiler error.

Functions that return references can be called from the left side of an assignment operator. For example:

When getChar() is not called on the left of an assignment operator, C++ performs automatic dereferencing, as usual:

Calling getChar() on the left of an assignment operator suppresses the dereferencing operation:

C++ allows default arguments to be specified when a function is defined. For example:

Initializes an array, nums, of length size with a fill value. Here are some sample calls:

Note that in the second call, the fill argument was assumed to be 0. In the third call the fill was assumed to be 0 and the size was assumed to be 3.

Also note that arrays are not passed by value, so we are not initializing a private copy of vals.

A great feature of C++ is that function names can be overloaded or shared. The compiler will determine which function to call by matching the argument types with the parameter types.

For example, assume three geometric types are declared:

We would like to write functions that compute the areas of these shapes. In C++ we can give all of them the same name:

These three functions are called variants of area. When the compiler sees a call to area():

The C++ compiler uses the types of the arguments: t, r, and c, to decide which variant to call.

Compare this with C. The three area functions must have distinct names:

The poor user must look up the name each time he wants to compute the area of a triangle. Was it triangle_area, area_triangle, triangleArea, etc.?

A powerful way to define a family of functions instead of a single function is a template. For example, the swap function only swaps integer variables. We'll need to define another swap function to swap doubles or strings or employee records. We can define all of these swap functions in one definition by declaring the type of the parameters to also be a parameter!

(The "class" keyword can be used instead of "typename".) When the C++ compiler sees a call to swap, it determines the type of the arguments and automatically generates definitions of the needed swap variants. For example, when C++ compiles:

It automatically generates the definitions:

and

Because of overloading, the functions can share the swap name.

Let's use some of these tools in the context of an example: vector arithmetic. We will use the vectors in the standard library:

We can hide the fact that vectors are C++ vectors by providing an inline dimension function that calls the size() function encapsulated by vectors:

Next, we define with a simple utility for displaying vectors. Note the use of default arguments and constant reference parameters:

The ostream parameter was passed by reference because the argument is modified internally. Characters were inserted into it.

The vector addition function also uses constant reference parameters. One problem is that we don't want to add vectors of different sizes. We can easily check if two vectors have different sizes, but what should we return if they don't?

One solution is to stop the program if the sizes are different. This is fine when we are debugging the program. If we're not, then the solution is to throw an exception that can be handled in a part of the program that can deal with the problem. We use a #define directive to create a debug mode flag (we could have used a constant declaration, too):

Our error handling function prints an error message to cerr and calls the library function exit(1). Calling exit(1) is the same as calling return 1 in main(). It immediately terminates the program returning an exit code of 1 (meaning unsuccessful completion) to the operating system. If debug mode is false, an object called an exception is created by calling runtime_error(). The exception encapsulates the error message. The exception object is then thrown. A thrown exception can be caught and handled in another part of the program able to deal with the problem. Uncaught exceptions cause the program to terminate. More on this later. Here's the code:

We are now ready for add(). We don't use an else clause because then we would have to specify a bogus return value when the vector dimensions were different, even though error() will cause the program to terminate before the value is returned:

Note that unlike C, C++ allows structures, i.e. non simple values, can be returned by functions. Here is a simple test harness. Note that C++ vectors allow us to specify their initial sizes when they are declared:

Here's the output produced:

Other vector arithmetic functions can be defined similarly.

Recall the interpreter defined earlier that prompted users for the diameter and length of a capped pipe, then computed and printed the pipe's volume. The interpreter is such a common design pattern that it might be wise to consider improvements to the interpreter we can make using some of our new found technology.

Many of our early interpreters will ask the user if he wants to continue, then use the answer to set more, the Boolean LCV for the interpreter's main loop. We can define a general question asking function that returns true if the answer to the question is true, and false otherwise. The function can even handle bogus responses to the question by re prompting the user:

Our early interpreters frequently prompt the user to input some data. The type of data varies, so we can use a template to postpone deciding what type of data to read.

Another problem we can solve is what to do if the user enters the wrong type of data. The problem is more difficult than the problem of the user merely entering data that is out of range. Presumably that part is application-specific and can be dealt with by the interpreter.

Recall that the extraction operator, >>, reads a string, then translates it into a binary value determined by the type of its right argument. If the translation can't be done, for example if the user types "three" when an integer is expected, then the input stream enters a fail state, it turns into 0. We can fix a failed stream by calling its clear() function and flushing the buffer using the stream's sync() function. Notice that var is passed by reference because this is where we will store the value read:

We are now ready to rewrite main().

Here's a sample output from the program:

The insertion operators (<<) for streams are handy because they translate binary data into sequences of characters. Too bad there are no translators for strings. But like files and the monitor, strings can be sinks for a class of streams called output string streams (ostringstream). An output string stream is a special type of output stream (ostream), so any operations that can be performed on an output stream can also be performed on an output string stream. Thus, any type that defines a variant of the insertion operator can use it to change itself into a string:

Here is a patch of code that uses this template:

Strings can also be character sources for input string streams. An input string stream (istingstream) is a special kind of input stream (istream), so all operations that can be performed on an input stream can also be performed on an input string stream. Here's the mate of the toString() function. This one translates strings into values. We must pass the value as a reference parameter so C++ can infer Value from calls to the function:

Here's a sample call::

The string stream declarations are in a header file called <sstream>, so you'll need the following include directive:

We can use string streams to build another, more traditional type of interpreter. The interpreter itself doesn't do much, it only executes simple infix arithmetic expressions, nested expressions aren't allowed, but the same pattern can be re used to build very powerful interpreters. Here's a sample run:

Notice that invalid inputs don't crash the interpreter. Also notice that instead of prompting the user each time with the annoying "Continue (y/n)?" prompt, the user simply types "quit" to end the program.

Taking another step toward reuse, we move the interpreter's control loop out of main():

The control loop prompts the user for a command, then reads the command. At the moment, there are only two possibilities: either the command is the quit command, in which case the loop exits, or not, in which case the command is executed by a separately defined execute() function, and the result is displayed. To keep the execute() function general, we only assume that it expects a string as an input and returns a string as an output:

To make the control loop more functional, we could add other possible "meta" commands such as help, undo, redo, and "\r".

The control loop doesn't assume the command is a single token (i.e., contains no white space). Instead of using the extraction operator, >>, which extracts up to the first white space character, the getLine() function is called. This function reads the entire line up to the first newline character. The C++ standard library has a function like this called getline(), but the VC++ version doesn't work, so I had to define my own:

The execute function converts the command line (cmmd) into an input string stream (is), then uses the extraction operators (>>), to extract individual tokens. Next, else-if statements are used to determine the operator (+, -, /. *) and compute the result. Of course the result returned must be a string, to the toString() function is called to perform the conversion.

The execute() function checks for invalid operators and division by 0, but it doesn't check that there are enough tokens or that the arguments are really doubles. How could these types of errors be caught? What should be done?

Here are the include directives this program needs. Note that the string stream declarations are contained in <sstream>:

The main() function is dead simple:

Write a program that plays Blackjack with the user. After each game the program displays the number of draws, user wins, and computer wins, then asks the user if the user wants another game.

A game of Blackjack consists of dealing a hand of two random cards to the user , then printing the value of the hand. The value is the sum of the card values, where:

The user is repeatedly asked if he wants another card until he "holds" or until the value of the hand exceeds 21, in which case the game is over and the user looses.

If the user holds, then the computer deals two random cards to itself and displays the sum. The computer continues to deal itself a card until the sum of the cards is greater than or equal to 17. If the sum is greater than 21 or less than the sum of the user's hand, then the computer looses, if the sums are the same, then the game ends in a draw. Otherwise, the computer wins.

Use top down design. Start by defining a short main()function, then move on to define coherent, loosely coupled supporting functions.

Representing cards and decks provides an opportunity to introduce some new C++ features:

An enumeration is a user-defined type consisting of a finite number of names. For example:

The names in an enumeration can be used like integer constants. The definition of Suit is equivalent to:

Of course programmers can initialize the names in an enumeration in different ways.

Sometimes values in one type can be converted to equivalent values in another type. Sometimes C++ will automatically perform these conversions where needed, other times programmers must explicitly request the conversion using a casting operator.

C++ will automatically perform conversions between its built-in types:

But some conversions involving user-defined types must be explicit. For example, C++ will automatically convert members of Suit to integers, but the reverse conversion must be explicit:

A structure (i.e., a struct) is a convenient way for grouping variables (later we will learn structures can do a lot more):

Declaring a structure:

declares the variables it encapsulates:

C++ allows assignment between structures:

Structures can be passed as parameters and returned as return values.

Here's a feeble way for printing cards. Write a better one later:

A deck is simply any array of 52 cards:

Here's a tricky way to initialize a deck. Note the conversion operators used to change integers into suits and values:

Shuffling a deck is just a matter of clearing the dealt flags:

Here's a little utility for determining the number of undealt cards in a deck:

To pick a card, generate a random number between 0 and 51. If the card at that position is dealt, then increment the number modulo 52 until an undealt card is found:

You'll need to seed the random number generator at the beginning of main:

Earlier, we used a strange looking, unexplained algorithm to compute the number of ways to choose m items from n items. How would we compute this without such an algorithm dropping into our laps? When faced with a complex problem that can be divided into sub problems that are smaller versions of the original problem, we can use recursion.

Select one item from the n candidates to choose from; call it x. There are:

ways to choose m items from n items assuming we aren't allowed to pick x, and there are

ways to choose m items from n items assuming x is already selected. Because x either will or will not be a selected item, there are

ways to choose m items from n items, altogether. This leads to the following recursive function: