Types

Previously, we saw that in C++, a variable is declared with its type, and the remains its type as long as the variable exists. C++ has several fundamental (also called primitive or atomic) types that are built-in to the language and always available, without any #include lines. The following are a few such types:

• int represents a signed (positive, negative, or zero) integer, and in most implementations, can represent integers between \(2^{-31}\) and \(2^{31} - 1\), inclusive

  int x = 3;
  

• double represents a floating-point number [1]

  double y = 2.5;
  

• bool represents a Boolean value, i.e. true or false

  bool z = true;
  

• char represents a single character (as opposed to a string, which is a sequence of characters), and a character literal is written with single quotes

  char c = 'w';
  

[1]

C++ also has a float type that represents floating-point numbers. A double typically uses twice the memory space of a float (hence the name), and it can represent a much larger range of values.

As with int, a variable of fundamental type must be explicitly initialized – otherwise its value is undefined.

int x;    // undefined value
double y; // undefined value
bool z;   // undefined value
char c;   // undefined value

The compiler’s type system detects misuse of types. For instance, the following attempts to initialize a double with a string literal, which is not a compatible type:

double y = "llama"; // COMPILE ERROR

On the other hand, there are some combinations of types for which C++ performs an implicit conversion, allowing one to be used where the other is expected. For instance, an int can be converted to a double, and vice versa:

int x = 3.1;   // narrowing conversion -- truncated to 3
double y = 42; // widening conversion -- value unchanged

Similarly, numeric types can be converted to bool, with zero values converted to false and non-zero values to true.

bool a = 3.1; // true
bool b = 0;   // false

Implicit conversions, while often useful, can also be a source of error. Consider the following code, which introduces a max() function that computes the maximum of two values. (We will discuss function definitions shortly.)

double max(double x, double y) {
  int result = x;
  if (y > x) {
    result = y;
  }
  return result;
}

Suppose we have the call max(3.4, 3.1). The first line of the function implicitly converts the value of x, which is 3.4, to an int, so that result contains the value 3. Then it is the case that y, whose value is 3.1, is larger than result, so result is assigned the truncated value of y, which again results in 3. Thus, the function returns the value 3 instead of 3.4.

Rather than relying on implicit conversions, which can be hard to detect when reading code, we can also do an explicit conversion via a cast. Depending on the types involved, C++ may require a cast, while in other cases it is optional. The following is an example of casting a double value to an int:

double x = 4.2;
int y = x;                   // implicit conversion -- easy to miss
int z = static_cast<int>(x); // explicit conversion -- obvious in code

While there are other kinds of casts, static_cast is the most common and the one we recommend.

Arithmetic and Comparisons

C++ supports common arithmetic operations, such as addition (+), subtraction (-), multiplication (*), division (/), and modulo (%). The behavior of these operators depends on the types of the operand – for example, adding two int values together produces an int, while adding two double values produces a double. The same holds for division, where dividing two int values truncates the result to produce another int value:

cout << (1 / 2) << endl; // prints 0

We can obtain a double value by ensuring that one of the operands is a double:

cout << (1.0 / 2) << endl; // prints 0.5
cout << (1 / 2.) << endl; // prints 0.5
cout << (static_cast<double>(1) / 2) << endl; // prints 0.5

When the operand types differ as above, one operand is promoted to the type of the other, generally to the one that allows for more precision. In the cases above, the int operand is promoted to double as part of the division operation.

The modulo operator requires both operands to be integers. The std::modf() function in the <cmath> library can be used on floating-point operands. (Similarly, the std::pow() function in <cmath> does exponentiation – C++ does not have an operator for that.)

As an example of modulo, the following functions convert a total number of seconds to whole minutes and leftover seconds, respectively:

int minutes(int seconds) {
  return seconds / 60;
}

int remaining_seconds(int seconds) {
  return seconds % 60;
}

int main() {
  int total = 153;
  int min = minutes(total); // 2
  int sec = remaining_seconds(total); // 33
}

We rely on integer division to truncate the result in minutes(), and we use the modulo operator in remaining_seconds() to compute the remainder of the total number of seconds with 60.

C++ also has standard comparison operators: equality (==), inequality (!=), less (<), less or equal (<=), greater (>), and greater or equal (>=). However, avoid two pitfalls when using these operators:

• Be wary about comparing floating-point numbers that result from arithmetic operations – floating-point numbers cannot in general be represented exactly on a computer, so we can get unexpected results due to the loss of precision:

  cout << (0.1 + 0.2 == 0.3) << endl; // typically prints 0 (false)
  

  In such cases, values should be compared to within some margin of error rather than exactly:

  bool almost_equal(double x, double y, double epsilon) {
    return std::abs(x - y) < epsilon;
  }
  
  ...
  
  cout << almost_equal(0.1 + 0.2, 0.3, 0.00001) << endl; // prints 1 (true)
  

  Here, we use std::abs() to compute the absolute value of the difference between the two values, then compare against our margin of epsilon.

• C++ does not support Python-style chaining of comparisons:

  int x = 10;
  cout << (3 < x < 7) << endl; // prints 1 (true)
  

  In this example, 3 < x produces true, which is then promoted to the integer value of 1 for the subsequent comparison with 7. Since 1 < 7, the result is true.

  Rather than chaining comparisons, we need to use Boolean logic to combine the results of two separate comparisons:

  cout << (3 < x && x < 7) << endl; // prints 0 (false)
  

  More on logical operations below.

Library Types

Aside from the fundamental types that are always available to C++ programs, individual headers in the standard library define additional types. For instance, some commonly used types include std::string defined by the <string> header, std::vector defined by the <vector> header, and std::pair defined by the <utility> header.

The std::string type represents an ordered sequence of characters. Similar to the initial program we saw last time, we first need to import the relevant header to get access to the type. We can then either use the qualified name with the std:: prefix, or include a using declaration to allow us to use string without qualification. The following is an example:

#include <iostream>
#include <string>

using namespace std;

int main() {
  string str1 = "make a ";
  string str2 = "wish";

  str1 < str2; // true, alphabetic comparison

  cout << str1.size() << endl; // 7 (includes spaces)

  string str3 = str1 + str2; // "make a wish"
  str3[0] = str3[7];
  str3[7] = 'f';
  cout << str3 << endl; // "wake a fish";
}

We start by declaring and initializing two string variables. We can compare them with < and other operators – the strings are compared lexicographically, meaning that the characters at each position are compared in order according to the underlying numerical value for the character. In the case above, since 'm' comes before 'w', str1 compares less than str2. We can obtain the length of a string by calling .size() on it (the dot here is necessary, and we’ll see how this gets implemented later when we discuss classes and member functions). We can concatenate two strings with the + operator and use square brackets to read or write an individual character in a string. In the code above, we concatenate str1 and str2 to produce "make a wish". Then we copy the character at index 7, which is 'w`, to position 0, resulting in "wake a wish". Finally, we set the character at index 7 to 'f', which gives us the string "wake a fish".

Aside from characters, we might want to keep track of a sequence of other elements, such as int values. A std::vector is a generic sequence type that allows us to specify the type of element it holds. For instance, the following creates both a vector of double values and one that holds string values:

#include <vector>

using namespace std;

vector<double> nums = {1, 5, 3.5, 6.5};
vector<string> pets = {"cat", "dog", "fish"};

Here, we initialize each vector with an explicit set of values. There are other ways to initialize a vector:

vector<int> v;        // initialize v to be empty (NOT undefined)
vector<int> v(5);     // initialize v to contain five zeros
vector<int> v(3, 42); // initialize v to contain three 42's

As with a string, we can use square brackets to index into a vector:

vector<int> v = {3, 5, 42, 28};
cout << v[0] << endl;
v[3] = 7;
v[4] = 100; // out of bounds... undefined behavior!

Be careful not to access an index that is out of bounds – such an access results in undefined behavior. Alternatively, we can use the .at() function, which checks whether we are within the bounds and throws an exception if we are not:

vector<int> v = {3, 5, 42, 28};
cout << v[0] << endl;
v.at(3) = 7;
v.at(4) = 100; // out of bounds... throws an exception

Assuming we don’t handle the exception, this causes the program to crash, which is better than undefined behavior – the crash immediately tells us we did something wrong, and we can run the code through a debugger to get more details.

We can also modify the size of a vector by adding and removing elements. In particular, the .push_back() function adds an element to the end, and the .pop_back() function removes the last element. We can also remove all elements with .clear():

vector<int> v;
// v contains {}

v.push_back(1);
v.push_back(2);
v.push_back(3);
// v contains {1, 2, 3}

v.pop_back();
// v contains {1, 2}

v.clear();
// v contains {}

A few other useful vector functions are the following:

• .size() returns the number of elements in the vector

• .front() returns a reference to the first element

• .back() returns a reference to the last element

• .empty() returns whether or not the vector is empty

For both strings and vectors, .size() returns the size as the size_t type, which is an unsigned integer, meaning that it cannot represent negative values. If we compare to a signed integer such as an int, the compiler may warn us that we are comparing a signed and unsigned integer, which might produce surprising results:

int x = -3;
size_t s = 5;
cout << (s > x) << endl;  // prints 0 (i.e. false)

The following is an example of a compiler warning for this:

foo.cpp:9:14: warning: comparison of integers of different signs:
'size_t' (aka 'unsigned long') and 'int' [-Wsign-compare]
  cout << (s > x) << endl;
           ~ ^ ~
1 warning generated.

To avoid this, we can use a cast to ensure that we are comparing values with the same “signedness”:

cout << (static_cast<int>(s) > x) << endl;  // prints 1 (i.e. true)

One last library type we examine now is std::pair, which represents a pair of values rather than an arbitrary sequence. The following is an example of using pairs:

#include <utility>

int main() {
  std::pair<int, bool> p1;  // initialized to {0, false}
  std::pair<int, bool> p2 = {-3, true};
  p1.first = 7;
  p1.second = true;
  // p1 now is {7, true}

  std::pair<string, double> p3; // initialized to {"", 0.0}
  std::pair<string, double> p4 = {"hello", 73};
  p3 = p4; // copy the values from p4 to p3
  // p3 now is {"hello", 73}
}

Control Structures

C++ is an imperative language, meaning that we specify computation as a sequence of statements. Like other languages, we often organize statements into functions, which we can then use as abstractions; we will return to this shortly. The syntax of a function definition is as follows:

<return type> <function name>(<optional parameters>) {
  <body statements>
}

The return type is specified first, and it corresponds to the type of value that the function returns. In some cases, a function does not return a value at all, in which case we use the special type void to specify that this is the case:

void print_value(int x) {
  cout << x << endl;
}

If a function has a non-void return type, we explicitly provide the return value using a return statement:

double square(double x) {
  return x * x;
}

We need to ensure that every path through a non-void function reaches a return statement that provides a value compatible with the return type. Otherwise, the behavior of the function is undefined, and the compiler may generate a warning or error. [2]

[2]

The one exception in C++ is the main() function, which implicitly returns the value 0 if no return statement is reached. However, this is not the case for any other function, even if its return type is int.

After the return type, we specify the name of the function, and if it takes arguments, the function parameters within the following parentheses. A parameter specifies both the type of the value it expects, as well as the name we use to refer to the corresponding argument within the function body. Finally, we have the body consisting of a sequence of statements enclosed by curly braces.

We can specify more complex control flow within a function through the use of compound statements such as conditionals and loops. The following demonstrates a conditional:

double abs(double x) {
  if (x < 0) {
    return -x;
  } else {
    return x;
  }
}

We use the if keyword to introduce a conditional, followed by a test expression within parentheses. The “then” branch can be a single statement, or it can be a block of statements enclosed by curly braces. We recommend using blocks, as that makes it clear what is part of a branch and what isn’t. For the “else” branch, we use the else keyword followed by a statement or block. We can also chain conditionals using else if:

double describe(int x) {
  if (x < 0) {
    cout << "negative" << endl;
  } else if (x > 0) {
    cout << "positive" << endl;
  } else {
    cout << "zero" << endl;
  }
}

At most one branch a conditional chain may execute.

A for statement can be used to express a loop that repeats until some condition is false. Its syntax is as follows:

for (<initialization>; <test>; <update>) {
  <body statements>
}

The initialization is run once at the beginning of the loop, and it can introduce new variables – the scope of such a variable is just the loop itself. The test is run before each iteration of the loop – if the test is true, the loop body runs, otherwise the loop exits. The update is run after each loop iteration completes. [3] As with a conditional, the body may be a single statement or a block – we recommend the latter.

[3]

Any of the initialization, test, or update may be omitted, but the semicolons separating them must still be present. If the test is omitted, it is assumed to always be true.

As an example, let’s compute the sum of the elements in a vector:

vector<double> values = /* fill with some values */;
double sum = 0;
for (size_t i = 0; i < values.size(); ++i) {
  sum += values[i];
}

We initialize a new variable i with value 0, representing the current index into the vector. We declare i to be of type size_t, so that we don’t get a compiler warning by comparing it against values.size(), which produces a size_t. We execute the loop body as long as our index i is less than the size of the vector. After each iteration, i gets incremented, and the loop exits once its value is equal to values.size().

In addition to for loops, C++ has while loops, which are a simplification of for loops:

while (<test>) {
  <body statements>
}

The loop will execute the body as long as the test is true, and it will exit when the test becomes false. We can translate our for loop above to a while loop as follows:

size_t i = 0;
while (i < values.size()) {
  sum += values[i];
  ++i;
}

Depending on the computation, it may be more naturally expressed using one loop construct or the other. In this case, iterating over the elements of a vector arguably is more cleanly expressed with a for loop than a while loop.

In addition to the normal behavior of a loop, we further control execution through the loop with return, break, and continue statements. A return statement immediately exits the enclosing function. A break statement exits the (most inner) loop, proceeding past the loop:

// Print elements until the first 0
for (size_t i = 0; i < values.size(); ++i) {
  if (values[i] == 0) {
    break;
  }
  cout << values[i] << endl;
}

A continue statement skips the rest of the current loop iteration, but does not immediately exit the loop:

// Print the square root of non-negative numbers
for (size_t i = 0; i < v.size(); ++i) {
  if (v[i] < 0)) {
    continue;
  }
  cout << v[i] << endl;
}

Often, a loop can be restructured to avoid break or continue statements, but in other cases, a computation may be more easily expressed using them. For the second loop above, we can rewrite it as follows:

// Print the square root of non-negative numbers
for (size_t i = 0; i < v.size(); ++i) {
  if (v[i] >= 0)) {
    cout << v[i] << endl;
  }
}

For the first loop that uses a break statement, we can use logical operations instead:

// Print elements until the first 0
for (size_t i = 0; i < values.size() && values[i] != 0; ++i) {
  cout << values[i] << endl;
}

We can use either && or and to specify a conjunction (an “and” of two conditions), either || or or for a disjunction (an “or” of two conditions), and either ! or not to negate a truth value. Conjunction and disjunction are short-circuiting, meaning that the right-hand side will only be evaluated if necessary to compute the result. In our example here, values[i] != 0 only gets evaluated when i < values.size() – good thing, because otherwise we could access an element past the end of the vector, producing the dreaded undefined behavior.

Procedural Abstraction

Abstraction is the principle of separating what something is or does from how it does it. It is the primary tool for managing complexity in Computer Science and other fields. As a non-programming example, consider the task of making a sandwich. In order to make a sandwich, we don’t need to know how bread is made, nor peanut butter nor jelly. All we need to know is how to put those ingredients together to construct a sandwich. Thus, we rely on the abstractions of bread, peanut butter, and jelly to make a sandwich. Similarly, the person who eats our sandwich doesn’t need to know how it’s made – all they need to know is that it is a delicious sandwich.

Figure 1 Abstraction layers for making a sandwich.

In a complex system, there are multiple layers of abstraction, each of which relies on the “what” knowledge of the lower layers without needing to know the “how.” In the case of a sandwich, the top layer is the consumer of the sandwich, who only needs to know that it is a sandwich. The layer below is the maker of the sandwich, who needs to know what bread, peanut butter, and jelly are and how to combine them into a sandwich. They do not need to know how to make each of the ingredients. The jelly manufacturer needs to know how to combine fruit and other ingredients into a container and apply heat to make jelly. However, they do not need to know how to grow fruit. That’s a farmer’s job, who needs to know how to use plants, water, and pollinators in order to produce fruit.

Computer programs are similarly built using layers of abstraction. When it comes to computational procedures, functions are our mechanism for defining procedural abstractions. The user of a function need only know what the function does without caring about how the function accomplishes its task. Specifically, the user needs to know the interface of the function, including its actual code interface and the documentation of what the function does. The user does not need to concern themselves with the implementation of the function, the actual details of how the function works.

Code Organization in C++

In general, we organize a program by decomposing it into independent modules, defined in separate files. In C++, a single module is further decomposed into a header file and a source file. In this course, we will use the .hpp extension for header files and the .cpp extension for source files [4]. The header contains the interface of the module, while the source file contains the actual implementation.

[4]

The extensions .hxx and .h are other common conventions for header files, and .cxx and .cc are also common for source files.

As an example, the following is a subset of stats.hpp from Project 1:

#include <vector>

//REQUIRES: v is not empty
//EFFECTS: returns the arithmetic mean of the numbers in v
double mean(std::vector<double> v);

Only a declaration of the mean() function appears in the header, along with its documentation. The actual definition goes in stats.cpp, the source file for the module:

#include "stats.hpp"
#include "p1_library.hpp"

using namespace std;

double mean(vector<double> v) {
  return sum(v) / count(v);
}

Other source files that use the functions in the stats module need only include the header file (stats.hpp) with the #include directive:

#include <iostream>
#include "stats.hpp"

using namespace std;

int main() {
  vector<double> data = { 1, 2, 3 };
  cout << mean(data) << endl;
}

A source file that uses the stats module only needs to know about the interface of the module. As long as the interface remains the same, the implementation of a module can change arbitrarily without affecting the behavior of a source file that uses it.

The #include directive actually pulls in the code from the target into the current file. So the end result is as if the declarations for the stats functions actually were written in this source file as well. We get access to those functions’ declarations without having to manually repeat them.

Library modules such as vector and iostream are surrounded by angle brackets (e.g. #include <vector>) in a #include directive. Non-library headers that are located in the same directory are surrounded by double quotes (e.g. #include "stats.hpp"). For the purposes of this course, we never #include anything other than header files and standard libraries – we never #include a .cpp source file.

The using namespace std; directive allows us to refer to standard-library entities without prefixing them with std::. An alternative is to avoid the prefix for specific entities with individual using declarations:

#include <iostream>
#include "stats.hpp"

using std::cout;  // allow cout to be used without std::
using std::endl;  // allow endl to be used without std::

int main() {
  // must prefix vector with std::
  std::vector<double> data = { 1, 2, 3 };
  // can elide std:: with cout and endl
  cout << mean(data) << endl;
}

It is considered bad practice among C++ programmers to include a using namespace std; directive, or generally other using declarations, in a header file – this forces those directives and declarations on anyone who #includes the header. On the other hand, they are fine to place in a source file, since source files are generally not #included.

The overall file structure for Project 1 is shown in Figure 2, excluding testing modules.

Figure 2 File structure for Project 1.

Arrows are shown between header files and the source files that #include them.

When compiling the project, only source files are passed to the compiler. The header files are folding into the source files through the #include directives:

$ g++ --std=c++17 -pedantic -g -Wall -Werror p1_library.cpp stats.cpp main.cpp -o main.exe

Any number of source files can be passed to the compiler, but only one of those may contain a main() function.

The Compilation Process

Consider the compilation command above. The elements of the command are:

• g++ is the C++ compiler we are invoking.

• The --std=c++17 argument tells it to compile according to the C++17 language standard.

• The -pedantic argument tells the compiler to adhere strictly to the C++ standard. Without this flag, compilers often provide extensions or allow behavior that is not permitted by the standard.

• The -g argument tells the compiler to produce an executable that facilitates debugging.

• The -Wall argument asks the compiler to generate warnings about possible programming errors.

• The -Werror argument configures the compiler to treat warnings as errors, so that it does not compile code that has warnings.

• The arguments -o main.exe tell the compiler to produce the output file main.exe.

• The remaining three arguments are the source files for our program – p1_library.cpp, stats.cpp, and main.cpp.

For the source files, the compiler will compile each of them separately, producing temporary object files. It will then attempt to link the object files together into the output executable. The linking step can fail if:

• A function is declared and used in the source files, but no definition is found. For example, if the definition for percentile() is missing, a linker error such as the following results:

  Undefined symbols for architecture x86_64:
    "percentile(std::__1::vector<double, std::__1::allocator<double> >, double)", referenced from:
        _main in main-dc223c.o
  ld: symbol(s) not found for architecture x86_64
  clang: error: linker command failed with exit code 1 (use -v to see invocation)
  

• Multiple definitions of the same function are found. For example, if we try to compile and link multiple source files that define a main() function, we get a linker error like the following:

  duplicate symbol _main in:
      /var/folders/gc/0lqwygqx381fmx9hhvj0373h0000gp/T/main-9eba7c.o
      /var/folders/gc/0lqwygqx381fmx9hhvj0373h0000gp/T/stats_tests-b74225.o
  ld: 1 duplicate symbol for architecture x86_64
  clang: error: linker command failed with exit code 1 (use -v to see invocation)
  

Upon success, the result of the linking step is the final program executable, main.exe for the compilation command above.

Specification Comments (RMEs)

The interface of a function includes its signature, which consists of the function’s name and parameter types. The return type of the function [5] is also part of its interface.

[5]

Technically, the return type of a regular (i.e. non-template) function is not part of its signature as defined by the C++ standard (see [defns.signature] in the standard). It is, however, part of the function’s interface.

Another part of a function’s interface is documentation about what it does, as in the following:

//REQUIRES: v is not empty
//EFFECTS: returns the arithmetic mean of the numbers in v
double mean(std::vector<double> v);

This documentation describes the what of the function, so it is an integral part of what a user of the function needs to know.

The documentation format we use in this course is an RME, which consists of a REQUIRES clause, a MODIFIES clause, and an EFFECTS clause.

REQUIRES Clause

The REQUIRES clause lists what the function requires in order to accomplish its task. If the requirements are not met, then the function provides no guarantees – the behavior is undefined, and anything the function does (e.g. crashing your computer, stealing your credit-card info, etc.) is valid. Thus, a user should never call a function with arguments or in a state that violates the REQUIRES clause.

Within the function definition, the implementation is allowed to assume that the REQUIRES clause is met – again, a user should never call the function if they are violated. A good practice is to assert that the REQUIRES clause is met, if it is possible to do so:

#include <cassert>
#include "stats.hpp"
#include "p1_library.hpp"

using namespace std;

double mean(vector<double> v) {
  assert(!v.empty());
  return sum(v) / count(v);
}

In order to use assert, the <cassert> header must be included. Then a boolean expression can be passed to assert. If the expression evaluates to a true value, execution proceeds normally. However, if it evaluates to a false value, then the program crashes with a meaningful error message:

Assertion failed: (!v.empty()), function mean, file stats.cpp, line 8.

This is much more desirable than computing a wrong answer (or stealing your credit-card info!), as it tells the user they did something wrong and where the requirements were violated.

If a function doesn’t have any requirements, the REQUIRES clause may be elided. Such a function is called complete, while one that has requirements is called partial.

MODIFIES Clause

The MODIFIES clause specifies the entities outside the function that might be modified by it. This includes pass-by-reference parameters, global variables (not in this course – only global constants are permitted), and input and output streams (e.g. cout, cin, a file stream, etc.):

//MODIFIES: v
//EFFECTS: sorts v in ascending order
void sort(std::vector<double> &v);

The MODIFIES clause only specifies what entities may be modified, leaving out any details about what those modifications actually might be. The latter is the job of the EFFECTS clause. Instead, the purpose of the MODIFIES clause is for the user to quickly tell what items might be modified.

If no non-local entities are modified, the MODIFIES clause may be elided.

EFFECTS Clause

The EFFECTS clause specifies what the function actually does. This includes details about what modifications are made, if any, as well as what the return value means, if there is one. All functions should have an EFFECTS clause – if a function does nothing, there is no point to writing the function.

The EFFECTS clause should generally only indicate what the function does without getting into implementation details (the how). It is part of the interface of a function, so it should not be affected if the implementation were to change.

Properties of Procedural Abstraction

As mentioned previously, the implementation of an abstraction should be able to change without affecting the way the abstraction is used. More formally, abstractions are substitutable – we should be able to swap out an implementation of an abstraction for a different one. As long as the interface remains the same, code that uses the abstraction will still work.

Abstractions should also be local, meaning that it should be possible to understand the implementation of one abstraction without knowing anything about the implementation of other abstractions. This implies that the implementation of one abstraction should not rely on implementation details of another – instead, the former should only work with the latter through the interface of the latter.

Testing

Testing is the primary mechanism we have for determining whether or not code is correct. Most programs are too complex to formally prove correct with reasonable effort. Instead, thorough testing provides a measure of confidence that the code behaves correctly.

Insufficient testing can lead to code that breaks when deployed, with potentially disastrous consequences. A canonical example is the Therac-25, a radiation-therapy machine from the 1980s. A combination of poor design and software bugs led to several cases where patients received massive radiation overdoses. Three patients died as a result. A more recent example of software bugs leading to catastrophic failure is Knight Capital Group, a financial-services firm that engaged in high-frequency trading. Lack of regression testing, poor software maintenance, and a mistake in deployment caused a new version of their software to execute millions of trades that bought shares at high prices and sold them at lower ones – all in a span of just 45 minutes. The end result was a pre-tax loss of $440 million, and the company was forced to sell itself to a competitor.

In this course, the stakes aren’t quite as high as in the cases above. However, it is often the case that the difference between doing poorly on a project and doing well is how well you test your code. Testing is the mechanism for determining whether or not code is buggy. Once a bug has been detected, debugging is the process used to identify and fix the source of the bug.

There are two main categories of test cases:

• Unit tests test once piece of code at a time, often at the granularity of individual functions or small groups of functions. This helps to find bugs early as well as make them easier to debug, since a failed unit test identifies exactly which function is broken.

• System tests test an entire module or program as a whole. This can identify bugs that occur when integrating multiple units together – it’s possible that two units appear to work individually, but one unit makes an incorrect assumption about the other that only manifests when they are tested together. System tests can also be closer to the real use case of a program, providing a measure of confidence that the program works as a whole.

In software development, it is important to maintain a set of regression tests, or tests that are run every time a code change is made. That way, a breaking change is identified immediately and can be fixed before the software is deployed. Regression tests generally include both unit and system tests.

Test-driven development is a common programming practice that integrates writing tests with developing the implementation of a program. Once the interface of a unit has been determined, tests can be written even before the implementation – that way, once the implementation is written, there are tests that can be run immediately. Furthermore, the process of writing tests can help inform the right strategy to use in implementation, reducing development time. The implementation in turn inspires new test cases, based on an understanding of what mistakes could have been made in the code. The result is an iterative process: writing tests for a unit, implementing the unit, writing more tests, fixing bugs, and so on until the code has been thoroughly vetted.

Only valid test cases should be written. Those that don’t compile are useless, as well as those that result in undefined behavior (e.g. by violating the REQUIRES clause of a function). There are several types of valid test cases:

• Simple test cases are for the “average” case. For instance, in testing a mode() function in Project 1, an example of a simple test case is one that tests a vector that contains exactly one mode (e.g. { 1, 2, 3, 2 }).

• Edge cases are those that test special cases in a unit’s behavior. For instance, the mode() function requires that its argument vector be non-empty. Thus, the smallest vector that can be passed to mode() is one with a single element – this is an edge case. Another special case is when the input has two modes – in this case, the documentation of the function specifies that it returns the smaller one. So we should test that the function indeed behaves correctly in this case.

• Stress tests are intensive tests that ensure that a system will work under a heavy load. For example, an autograder for a 1000-person course should be able to withstand hundreds of students trying to submit right before the deadline. Thus, it is important to test the autograder with large numbers of concurrent requests. Stress tests will not be used in this course, since the projects we will focus on are not performance-critical.

Test cases should focus on cases that realistically could be erroneous. For example, a malicious programmer could insert a bug that only occurs for a specific, arbitrary input (e.g. if the number 42 is in the input). However, we generally can’t test every possible input, so we have to concentrate on those cases where a reasonable programmer could make a mistake. (Other mechanisms, such as code reviews, are used to guard against malicious programmers.)

The small scope hypothesis states that thorough testing with “small” test cases is sufficient to catch most bugs in a system [6]. Thus, our test cases need not be large – in general, they should be small enough where we can compute the expected results by hand. Similarly, having more test cases is not necessarily better. Fewer test cases that are meaningfully different is more effective than having many, redundant test cases. As an example, the data sets { 1, 1, 2, 2, 2 } and { 1, 1, 2, 2, 2, 2 } are not meaningfully different for the mode() function – there is no good reason why it would behave differently in the two cases. On the other hand, the data set { 1, 1, 2, 2 } is meaningfully different, since it contains two modes.

[6]

See Evaluating the “Small Scope Hypothesis” by Andoni et al. and On the Small-Scope Hypothesis for Testing Answer-Set Programs by Oetsch et al. for empirical evaluations of the hypothesis.