Imperative Programming

Motivation¶

It is time to learn to compose a program from its ingredients. Imperative programming is a programming paradigm that uses the flow of execution of statements, also known as the control flow, to change a program’s state for the desire computation.

GCD¶

To motivate the concept, recall the program for computing the GCD in Lecture 2:

{
  b = b % a;
  int c = b;
  b = a;
  a = c;
}

where a and b are the non-zero integer input as follows:

Using control flow statements, we can improve the program to conditionally stop calculating the GCD when it is obtained as the absolute value of b, i.e., when a becomes 0:

1
2
3
4
5
6
if (a) { // execute if a is non-zero
  b = b % a;
  int c = b;
  b = a;
  a = c;
} else if (b<0) b=-b; // get the absolute value of `b` as the GCD

See if you can crash it by running the program too many times!

We can also free ourselves from repeating the execution manually by writing an iteration or a loop using control flow statements.

1
2
3
4
5
6
7
8
int c;
while (a) {  // execute repeatedly as long as a is non-zero
    b = b % a;
    c = b;
    b = a;
    a = c;
}
if (b<0) b=-b;

The program returns the GCD in one go:

Inverse Square Root¶

Recall the update rule of the inverse square root in Lecture 2:

y = y * (1.5 - (x*0.5 * y * y));

where x is the input, and y is the initial guess:

We can improve the program to check whether further execution is required:

1
2
3
4
5
6
7
8
9
y = (y+1/y/x)/2;   // update the answer

if (auto x_=1/y/y, 
    gap=(x>x_)?(x-x_):(x_-x), 
    abs_x=(x>0?x:-x), 
    abs_x_=(x_>0?x_:-x_); 
    y<0 || x_!=x && gap > 1e-9*(abs_x>abs_x_?abs_x:abs_x_)) { // inaccurate?
    cout << format("Run again to improve the accuracy.");
}

Observe that the program prompts the user to run it again when the answer is inaccurate:

The repeated runs can be automated and optimized with the following code:

1
2
3
4
5
6
7
constexpr auto threehalfs = 1.5, rel_tol = 1e-9; // for compiler optimization
const auto x2 = x*0.5;                           // avoid redundant calculations
double x_, gap, abs_x, abs_x_;
do {
    y = y * (threehalfs - (x2 * y * y));
    x_=1/y/y; gap=(x>x_)?(x-x_):(x_-x); abs_x=(x>0?x:-x); abs_x_=(x_>0?x_:-x_);
} while (y<0 || x_!=x && gap > rel_tol*(abs_x>abs_x_?abs_x:abs_x_)); // repeat if inaccurate

This gives an accurate answer immediately:

Undecimal to decimal¶

Consider a new problem of converting an undecimal number to a decimal number.

The following is an implementation that converts an undecimal number represented by a C string to an unsigned integer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
auto value=0uLL;
constexpr auto m1=-1uL, m2=m1/11, m3=m1-10;
for (size_t i=0, length=strlen(s); i < length; ++i) {
    value *= value<=m2 ? 11 : throw runtime_error("The value is too big.");
    switch (unsigned char c=s[i]) {   // condition in the form of a character declaration
    case 'X':                // case label X
        [[fallthrough]];     // attribute to silent warning
    case 'x':
        value<=m3 ? value+=10 : throw runtime_error("The value is too big.");
        break;               // terminate the switch statement
    default:                 // default label
        if ((c=s[i]-'0')>9) throw runtime_error("Invalid character found.");
        value<=m1-c? value+=c : throw runtime_error("The value is too big.");
    }
}

Control flow statements allow the program to handle undecimal strings of any length, limited only by the maximum integer value.

Distinct Prime Factors¶

Finally, consider the problem of computing the prime factors:

The following is an implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
for (auto p=2uLL; p<=n; p++) {     // check candidate factors from 2 to n
    if (n%p) continue;          // continue to the next factor
    bool isprime=true;          // a flag to keep track of the primality
    for (auto d=2uLL; d*d<=p; d++)  // check candidate divisors
        if (p%d==0) {           // divisor found for p
            isprime=false;
            break;              // break to skip the test of other divisors
        }
    if (isprime) {              // prime factor found
        cout << p << '\n';
        do n/=p; while (n%p==0);
    }
}

Observe that the program prints the distinct prime factors of a positive integer n line by line in ascending order, regardless of how many prime factors there are:

Imperative programming focuses on using different control flow statements to make decisions and repeat actions in response to different conditions. In the following sections, we will learn how to write conditions and control flow statements.

Condition¶

Boolean Value¶

Control flow statements determine the flow of execution based on the program state, often summarized as a condition that can be regarded as true or false. Such a condition is said to take a boolean value, named after George Boole.

bool is a categorical type consisting of only the two values true and false. For instance, Program 6 declares a boolean variable isprime, which is initialized to true, may be updated to false later, and is used as a condition to decide whether to print the factor.

...
    bool isprime=true;          // a flag to keep track of the primality
    ...
            isprime=false;      // i is not prime
            ...
    if (isprime) ...            // prime factor found
...

Theoretically, a boolean value only requires 1 bit of storage, but C++ stores a boolean value with 1 byte:

Similar to Python, C++ regards true as 1, and false as 0:

We can even apply arithmetic operations on boolean values:

Boolean Expression¶

A simple way to turn the program state to a boolean value is to apply comparison operators such as

<, <=, >, >=, <=>, ==, !=, <=>

to numeric values to form a boolean expression, and then combine boolean expressions into a compound boolean expression using logical operators such as

1. negation: !

2. logical AND: &&

3. logical OR: ||.

Unlike C++, Python uses more expressive names for the logical operators: not vs !, and vs &&, or vs ||. In particular, 1 != 0 can be rewritten as !(1==0) in C++ but not Python.

Similar to Python, C++ regards any non-zero numeric value as true in boolean expressions. For instance, the following checks if all the variables are zero:

Even though x + y + z is not boolean, C++ contextually converts it to boolean since the logical operators expect a boolean context for their operands. Contextual conversion is one of the implicit conversions in C++ that follows the following rule.

The value zero (for integral, floating-point, and unscoped enumeration) and the null pointer and the null pointer-to-member values become false. All other values become true.

Unlike Python, an empty C string "" is regarded as true but the null character '\0' is regarded as false:

A better check for all-zero is:

An important benefit of using logical operator || in !(x || y || z) vs the addition + in !(x + y + z) is the short-circuit evaluation of logical expressions. To show this, run the following slightly modified code:

y and z are not incremented because ++x already evaluates to true, and so the execution of ++y and ++z are skipped as their values do not change the overall value of the boolean expression. In comparison, there is no short-circuiting for the addition operations:

Python also has short-circuit evaluation, but it returns the value of an operand in its original type without contextual conversion to boolean:

In contrast, C++'s logical operations return a boolean as the operands are contextually converted to boolean:

Categories¶

It is possible to express a condition that takes multiple values. For instance, while most of the comparison operations evaluate to a boolean value, there is an exception—the three-way comparison operator <=>, also known as the spaceship operator, which returns a comparison category:

std::strong_ordering from <compare> is another categorical type similar to boolean, but with three possible categories below.^[1]

• std::strong_ordering::equal: The operands are equal.

• std::strong_ordering::less: The first operand is less than the second.

• std::strong_ordering::greater: The first operand is greater than the second.

The check for equality can also be simplified to:

The check for the other two possible categories are as follows:

We can define custom categorical type using the enum declaration. E.g., the following declares the values for three-valued logic (TVL):

Manual assignments to integer values are optional, but they ensure that the integer values of TRUE and FALSE aligns with those of the corresponding boolean values true and false. Indeed, even the name of the enumeration is optional, as illustrated by the following unnamed enumeration:

Unlike std::strong_ordering, the above enumerations are unscoped, which can lead to name conflicts if multiple such enumerations contain a value with the same name.

To resolve the issue, C++11 introduced scoped enumerations, declared with enum class (and enum struct), such as:

The above also added short aliases U, F, and T without worry of name conflicts because the qualification TVL:: is required to access the enumerators.

However, the following code will fail because scoped enumerations are not implicitly converted to integers, which is intended to ensure type safety:

cout << a << ' ' << b << ' ' << c << '\n';
a==true && b==false

Conditional¶

if statement¶

Now that we know how to specify a condition, we can begin to write programs with control flow statements.

The if statements is a control flow statement that executes a block of code based on whether a condition is true. For instance, in Program 1, there are two nested if statements:

if (a) {
    ... // executed when `a` is true
} else if (b<0) ... // executed when `a` is false but `b<0` is true

The first if statement executes a compound statement if the condition is true. Otherwise, the control goes to its else clause, which consists of a simple if statement without an else clause.

Unlike Python, the condition for the if statement must be enclosed by parentheses ( ... ), and there is no elif keyword to compress else if:

Program 3 also has an if statement:

...
if (auto x_=1/y/y, 
    gap=(x>x_)?(x-x_):(x_-x), 
    abs_x=(x>0?x:-x), 
    abs_x_=(x_>0?x_:-x_); 
    y<0 || x_!=x && gap > 1e-9*(abs_x>abs_x_?abs_x:abs_x_)) { // inaccurate?
    ... //
}  // 

Different from the previous if statements, there is an initialization statement in front of the condition:

...
if (auto x_=1/y/y, 
    gap=(x>x_)?(x-x_):(x_-x), 
    abs_x=(x>0?x:-x), 
    abs_x_=(x_>0?x_:-x_);
    ...

The initializer defines variables local to the scope of the if statement. Hence, repeating the execution does not re-declare the variables in the global scope.

What does the condition mean, however?

    ...
    y<0 || x_!=x && gap > 1e-9*(abs_x>abs_x_?abs_x:abs_x_)) { // inaccurate?
...

Due to the limited precision of floating point numbers, the accuracy, or the closeness of two floating point numbers, say $x$ and $x'$, should be determined with some tolerance.

In python, (1) is implemented by the function isclose from the math module:

-inf, inf and NaN behave similarly to the IEEE 754 Standard:

Although there is no isclose function readily available in C++, it is not difficult to implement it. Program 3 implements it with the help of the conditional/ternary operator:

x>0 ? x : -x

The above is analogous to the conditional expression x if x>0 else -x in Python, which evaluates to the absolute value of x.

Unlike the conditional expression in Python, the conditional operator in C++ has to decide on the resulting data type based on the types of the operands, since C++ is statically typed.

As another example, the conditional expression in Program 5

value *= value<=m2 ? 11 : throw runtime_error("The value is too big.");

increases value by a factor of 11 only if there is no overflow. Otherwise, the throw expression will raise a runtime error and transfers the control to an exception handler, and if not handled, exits the program with an error message saying that “The value is too big.”^[2] The assignment works because the conditional expression has type int even though the type of the throw expression is void:

In contrast, the following code fails because of incompatible operand types.

value<=m2 ? 11 : cerr << "The value is too big.";

Unlike throw, the expression above is not void, but rather, the same type as that of cerr (to allow the operator << to be chained.) This case is not handled by the conditional operator, resulting in an error.

switch statement¶

Other than the if statement, C++ provides another conditional statement called the switch statement, which acts like the match statement in Python to switch execution among possibly more than two cases.

For instance, Program 5 uses the switch statement to convert a digit in an undecimal string to an integer value:

...
    switch (unsigned char c=s[i]) {   // condition in the form of a character declaration
    case 'X':                         // case label X
        [[fallthrough]];              // attribute to silent warning
    case 'x':
        ...
        break;                        // terminate the switch statement
    default:                          // default label
        ...
    }
...

Similar to the if statement, the condition in a switch statement is

• enclosed in parentheses and,

• optionally, follows an initialization of any number of variables of the same type.

However, unlike the if statement, where the condition is expected to be a boolean expression, the switch statement allows the condition to be of

• an integral type (such as int, char, short, long),

• an enumeration type (such as enum, enum class, enum struct), or

• a class type that can be implicitly converted to an integral or enumeration type.

The condition can even be a variable declaration like (auto c=s[i]) above.

The body of the switch statement is typically a compound statement containing

• several case labels, and

• optionally a default label

When a switch statement is executed:

1. The control is passed to the first case label that matches the value of the condition.

2. If no such match exists, the control is passed to the default label. A break statement can be used to terminate the switch statement.

3. Otherwise, the control will continue to flow to other cases after the matched case. Such a fall through may trigger a warning, but the attribute [[fallthrough]] introduced in C++17 can be used to silence the warning.

Another way to write the switch statement is as follows:

To show how the switch statement can be applied to enumerations, recall the TVL enumeration:

The following code randomly assigns a TVL value to a:

The following code implements the logical NOT operation on the randomly drawn value in a:

Iteration¶

while loop¶

Consider Program 2 for computing the GCD iteratively:

int c;
while (a) {  // execute repeatedly as long as a is non-zero
    ...
}
...

This is almost the same as its previous version Program 1 except that:

1. The if keyword is changed to the while keyword so the body of the while loop gets executed repeatedly as long as the condition holds, i.e., a is non-zero.

2. The declaration int c; is moved out of the local scope to avoid repeated declarations.

Consider Program 4 for computing the inverse square root iteratively:

...
double x_, gap, abs_x, abs_x_;
do {
    ...
    x_=1/y/y; gap=(x>x_)?(x-x_):(x_-x); abs_x=(x>0?x:-x); abs_x_=(x_>0?x_:-x_);
} while (y<0 || x_!=x && gap > 1e-9*(abs_x>abs_x_?abs_x:abs_x_));  // repeat if inaccurate

Instead of a while loop, the code uses a do-while loop, where the looping condition is checked after the execution of the body. This ensures that the accuracy is checked after the answer is updated.

When compared to the previous version Program 3:

1. The declaration double x_, gap, abs_x, abs_x_; has moved out of the local scope because while/do-while loop does not support initializer in the condition, and even if it did support, the repeated declaration would be redundant.

2. The update rule is modified to use the constant x2 and constant expression threehalfs to avoid repeated calculations and speed up the access to the values.

   constexpr auto threehalfs = 1.5, rel_tol = 1e-9;
   const auto x2 = x*0.5;
   auto x2 = x*0.5;
   double x_, gap, abs_x, abs_x_;
   ...
       y = y * (threehalfs - (x2 * y * y));
       ...

for loop¶

Instead of a while loop, Program 5 uses a for loop:

...
for (size_t i=0, length=strlen(s); i < length; ++i) {
    ...
}

This can be rewritten as a while loop:

...
{
    size_t i=0, length=strlen(s);
    while (i < length) {
        ...
        ++i;
    }
}

C++11 introduced a less error prone range-based for loop:

The for loop declares i to take a value from the initializer list {0, 1, 2, 3, 4} one-by-one for each iteration. This is analogous to the Python code:

C++23 also introduced <ranges> that makes the range of items more composable and lightweight:

std::views::iota(0, 5) from <ranges> specifies the sequence of integers from 0 up to but excluding 5, like range in Python code:

Finally, Program 6 uses a nested for loop to print the prime factors:

for (auto p=2; p<=n; p++) {     // check candidate factors from 2 to n
    ...
    for (auto d=2uLL; d*d<=p; d++)  // check candidate divisors
        ...
    ...
}

For each number p from 2 to n, it checks whether p is divisible by a number d from 2 up to the integer square root of p, using the condition d*d<=p.

In the outer loop, it uses the continue statement to continue to the next iteration:

for (auto p=2; p<=n; p++) {     // check candidate factors from 2 to n
    if (n%p) continue;          // continue to the next factor
    ... // code skipped by `continue`
}

This is equivalent to

for (auto p=2; p<=n; p++) {     // check candidate factors from 2 to n
    if (!n%p) {
        ... // code skipped by `continue`
    }
}

The code also uses the break statement to terminate the inner loop:

    ...
    for (auto d=2uLL; d*d<=p; d++)  // check candidate divisors
        if (p%d==0) {           // divisor found for `p`
            ...
            break;              // break to skip the test of other divisors
        }
    ... // `break` transfers the control to here

The code also uses a flag isprime to keep track of the primality of p to decide whether to print it as a prime factor later:

    ...
    bool isprime=true;          // a flag to keep track of the primality
    for (auto d=2uLL; d*d<=p; d++)  // check candidate divisors
        if (p%d==0) {           // divisor found for `p`
            isprime=false;
            break;              // break to skip the test of other divisors
        }
    if (isprime) cout << p << '\n'; // prime factor found
    ...