# Lab 7: Repetition

## Introduction

We have seen that the C++ `if` statement uses a condition to selectively execute statements. In addition to facilitating selection, most modern programming languages also use conditions to permit statements to be executed repeatedly.

Let's consider an example. Suppose we have 2500 words that we want to translate into Pig Latin---about as many words as this lab exercise. The program we wrote in Lab #5 could do this, although the `englishToPigLatin()` function only worked on one word. The key was that the main driver repeatedly called `englishToPigLatin()` for each word that the user typed in. We can use that program to translate all 2500 words, and that's so much easier than running the program 2500 times or writing 2500 calls to `englishToPigLatin()`.

C++ technically provides three different loops, although we'll have four different uses for them. These are called the `while` loop, the `do` loop, the `for` loop, and what we call the forever loop.

This lab's exercise is to make a calculator program that has more functionality and is more user-friendly than the one we wrote in the last exercise.

## Files

Directory: `lab7`

Create the specified directory, and copy the files above into the new directory. Only `gcc` users need a makefile; all others should create a project and add all of the `.cpp` files to it.

Add your name, date, and purpose to the opening documentation of the code and documentation files; if you're modifying and adding to the code written by someone else, add your data as part of the file's modification history.

## The Exponentiation Operation

We will implement xn by writing a function `power()`, such that a call:

`power(x, n)`
will compute and return `x` raised to the power `n`. To simplify our task, we will assume that `n` is a nonnegative integer.

You may recall that exponentiation is available in C++ via the function `pow()` in the `cmath` library. Just for this lab, we will not use `pow()` so that we can try to implement it with loops.

### Function Design

As usual, we begin by using object-centered design to carefully design an exponentiation function. However, before we can describe its behavior, some simple analysis may shed light on what our function must do.

Function Analysis. When faced with a new problem, it is often helpful to solve it by hand first. For example, to calculate `power(2,0)`, `power(2,1)`, `power(2,3)` and `power(2,4)` by hand, we might write out expressions for these computations:

power(2,0) = 1
power(2,1) = 2
power(2,2) = 2 * 2
power(2,3) = 2 * 2 * 2
power(2,4) = 2 * 2 * 2 * 2

The first case defines our starting point. The other cases make explicit what we already know: n tells us how many times we need to use x as factor. How do you know we have enough factors? You count them! Now if we could only count in our programs...

Function Behavior. We can describe what we want to happen as follows:

Our function should receive a base value and an exponent value from the caller of the function. It should initialize `result` to one, and then repeatedly multiple `result` by the base value, with the number of repetitions being the exponent value. Our function should then return `result`.

Function Objects. From our behavioral description, we can identify the following objects:

Description Type Kind Movement Name
The base value `double` varying received `base`
The exponent value `int` varying received `exponent`
The result value `double` varying returned `result`

From this, we can specify the task of our function as follows:

Specification:
receive: `base`, a `double`; `exponent`, an `int`.
precondition: `exponent` is non-negative
return: `result`, a `double`

While we could worry about negative exponents, we choose not to since it would require a bit more work. We also won't test this precondition since our specification makes it quite clear that we aren't coding for this; we've given other programmers fair notice of our assumption. Our function will simply return 1, as if the exponent were 0.

Using this specification, go to `mathops.h` and `mathops.cpp` and replace the appropriate lines with a prototype and a stub for `power()`. Then, uncomment the call to `power()` within `apply()`. Finally, compile the code and fix your errors.

The call to `power()` in `apply()` uses `int()` to convert the `double` argument `op2` to an integer. Without this conversion, our attempt to pass a `double` argument into an `int` parameter would result in a compilation error.

Function Operations. From our behavioral description, we have the following operations:

Description Predefined? Name Library
Receive `base` and `exponent` yes parameter built-in
Initialize `result` to 1.0 yes declaration built-in
Set `result` to `result`*`base` yes `*=` built-in
Repeat `*=` `exponent` times yes `for` loop built-in
Return `result` yes `return` built-in

Function Algorithm. We can organize these operations into the following algorithm:

1. Receive `base` and `exponent` from caller.
2. Initialize `result` to 1.0.
3. For each `count` from 1 to `exponent`:
`result` *= `base`.
4. Return `result`.

### Coding

The C++ `for` loop is designed to facilitate the counting behavior required by step 2. The pattern for the counting `for` loop is:

```for (`Type` `Var` = `Start`; `Var` <= `Stop`; `Var`++)
`Statement````
where `Type` is a C++ numeric type, `Var` is the loop control variable used to do the counting, `Start` is the first value, and `Stop` is the last value.

For example, if we wanted to print `x` 20 times, here's the algorithm and the code:
 For each `i` from 1 to 20: Display `x`. ```for (int i = 1; i <= 20; i++) cout << x;```
Compare the algorithm and code, then using the pattern and the example, complete the `power()` function. Read the algorithm carefully. There are several variables that you have to create and use in writing your loop, so read the algorithm carefully. Remember that you aren't supposed to invent new things with your code; just translate the algorithm above.

When you've written the code, compile and test your program. Test exponentiation on several values. Make sure you test 0 as an exponent. Try values larger than 2 and 3 as both bases and exponents.

## Characterizing Loops

The pattern for a C++ `for` loop is actually more general:

```for (`InitializationExpr`; `Condition`; `StepExpr`)
`Statement````
where `InitializationExpr` is any initialization expression, `Condition` is any boolean expression, and `StepExpr` is an arbitrary expression.

If for some reason we wanted to count downwards and output the multiples of 12 from 1200 to 12, then we'd have this algorithm and code:

 For each i from 100 down to 1: Display 12 * `i`. ```for (int i = 100; i >= 1; i--) cout << 12 * i << endl;```

The `Condition` controls the loop. As long as it is true when it is tested, then the loop `Statement` is executed. C++ `for` loops are controlled by conditions, just as `if` statements are controlled by conditions. As we shall see, each of the other C++ loop statements are also controlled by conditions.

A loop is categorized by when it evaluates its condition:

1. A pretest loop evaluates its condition before its statements.
2. A posttest loop evaluates its condition after its statements.
3. An unrestricted loop evaluates its condition whenever you like.

The `for` loop is a pretest loop, because it evaluates its condition before the loop's statement is executed. You can prove it to yourself: `power()` should return 1 if the exponent is 0 (which you know since you tested this above). The only way this happens is if the loop in `power()` does not execute its statement; if the statement did execute, then the value returned wouldn't be 1.

The `for` loop is designed primarily for problems that involve counting through ranges of numbers, or problems in which the number of repetitions can be determined in advance. Many problems need other types of repetition.

The other three C++ loops differ from the `for` loop in that they are general-purpose loops, designed for problems where the number of repetitions is not known in advance.

1. The C++ `while` loop provides a general pretest loop.
2. The C++ `do` loop provides a general posttest loop.
3. The C++ forever loop provides a general unrestricted loop.

Let's try out these loops to handle our menu input.

## Getting a Valid Menu Choice

`getMenuChoice()` is defined in `menus.cpp`.

```char getMenuChoice(const string MENU)
{
char choice;
cin >> choice;
return choice;
}```
What happens if the user types in a bad value? Try it out.

We can be more user-friendly by handling the input errors in this function.

One way to handle such errors is to repeatedly display the menu and input the user's choice, so long as they continue to enter invalid menu choices. This isn't something we can predict since we have no idea how many times the user will enter in bad data.

The general-purpose loops give us a way to handle user errors, but we must decide which one to use. We can begin by writing a partial algorithm for this problem using a generic `Loop` statement, in which we don't worry (for the moment) how control will leave the loop:

1. Loop:
1. Display `MENU`.
2. Read `choice`.
End loop.
2. Return `choice`.

We've looked at how conditions are used in `if` and `for` statements. The other loops work quite similar to the `for` loop. There are two types of conditions we have to work with.

• A continuation condition defines the circumstances under which we want repetition to continue. "When do I keep on going?"
• A termination condition defines the circumstances under which repetition should terminate. "When do I stop?"
The loop we use will determine what type of condition we need. When we switch from one loop to another, we might have to switch the type of condition. Rethinking the logic isn't too tricky.

For our problem, we want the repetition

• to continue so long as `choice` is an invalid menu choice, and
• to terminate when `choice` is a valid menu choice.

Since `choice` is not known until after Step (b), it seems logical to see if we're done after that step, which we can describe using our termination condition as follows:

1. Loop:
1. Display `MENU`.
2. Read `choice`.
3. If `choice` is a valid menu choice, exit the loop.
End loop.
2. Return `choice`.
In this algorithm, it is apparent that the controlling condition is evaluated at the bottom of the loop, which implies that a post-test loop is the appropriate loop to choose.

In C++, the post-test loop is called the `do` loop, and its pattern is as follows:

```do
{
`Statements`
}
while ( `Condition` );```
When execution reaches such a loop, the following actions occur:
1. `Statements` execute.
2. `Condition` is evaluated.
3. If `Condition` is true, control returns to step 1; otherwise, control proceeds to the next statement after the loop.
Since repetition continues so long as the condition is true, a `do` loop uses a continuation condition.

Since its `Condition` is not evaluated until after the first execution of `Statements`, the `do` loop guarantees that `Statements` will be executed one or more times. For this reason, the `do` loop is said to exhibit one-trip behavior: we must make at least one trip through `Statements`.

The notion of a "valid" menu choice is a bit tricky. One way to handle it is to require that the valid menu choices be consecutive letters of the alphabet (e.g., `'a'` through `'e'`). If we then pass the first and last valid choices to `getMenuChoice()` as arguments:

`char operation = getMenuChoice(MENU, 'a', 'e');`
and add parameters to the function prototype and definition to store these arguments:
`char getMenuChoice(const string MENU, char firstChoice, char lastChoice);`

Add the new arguments to the function call in the driver. Add the new parameters to the prototype and the function itself. You can recompile the code to make sure the compiler is happy with your changes, but the program won't run any differently yet.

Since `firstChoice` and `lastChoice` will define the range of valid choices, we can express our loop's continuation condition in terms of those values: `choice` is invalid if and only if

`choice < firstChoice || choice > lastChoice`
We are then ready to add a `do` loop to the function to implement our algorithm.

Code it up. Here are the pieces we need for the `do` loop:

• The `Statements` are the output of `MENU` and the input of `choice`.
• The `Condition` is in the previous paragraph.
• We'll have to declare `choice` outside the loop so that it can be returned outside the loop.

## Getting Valid Numeric Input

Another potential source of error occurs when our program reads values for `op1` and `op2` from the keyboard -- the user might enter some non-numeric value. Our current version checks for this using the `assert()` mechanism and the `good()` method of `cin`.

But suppose we wished to give the user another chance to enter valid values, instead of just terminating the program (which seems terribly drastic)? At first glance, it looks like we could use the same approach as before, by replacing the `assert()` with a posttest loop that repeats the steps so long as `good()` returns false:

```do
{
// prompt for op1 and op2
// input op1 and op2
}
while ( !cin.good() );```
However, this approach is inappropriate because of two subtleties about `cin` input (actually, `istream` input in general). When the >> operator is expecting a real value, but gets a non-real value, two things happen, each of which causes a difficulty:

1. The internal status of `cin` is set so that its method `good()` will return false. No input operations can be performed with `cin` so long as `cin.good()` returns false.
2. After failed input, the bad input value is left (unread) in the input stream.

The first problem can be fixed with `cin.clear()`, which resets the status of `cin` so that `cin.good()` returns true again.

The second problem takes some more work. We don't want the loop to continue reading the same bad value over and over and over again. We need some way to skip over the bad input. This can be accomplished using the `ignore()` method:

`cin.ignore( `NumChars`, `UntilChar` );`
Characters in `cin` will be skipped until `NumChars` have been skipped or until the character `UntilChar` is encountered, whichever comes first. Since lines are usually not more than 120 characters in length, and the end of a line of input is marked by the newline character (`'\n'`), we can use the following call to solve this difficulty:
`cin.ignore(120, '\n');`

All of this complicates our choice of which loop to use, because we now have four steps to perform:

1. Display a prompt for two real values. [One or more times.]
2. Input `op1` and `op2`. [One or more times.]
3. `cin.clear();` [Only if necessary, zero or more times.]
4. `cin,ignore(120, '\n');` [Only if necessary, zero or more times.]
It looks like the test should be placed in the middle there. A `do` loop isn't going to work.

One traditional solution is modify our algorithm to use a pre-test loop in the following way:

1. Display a prompt for two real values.
2. Input `op1` and `op2`.
3. Loop so long as `cin.good()` is false:
1. `cin.clear();`
2. `cin.ignore(120, '\n');`
3. Display a prompt for two real values.
4. Input `op1` and `op2`.
End loop.
The drawback to this approach is its redundancy: the prompt and input steps are written twice. This is not too much of an inefficiency, so long as one does not mind the extra typing. In the final part of this exercise, we will see a way to avoid this redundancy.

The C++ pretest loop is called the `while` loop:

```while ( `Condition` )
`Statement````
As usual, `Condition` is any C++ Boolean expression, and `Statement` can be either a single or compound C++ statement. `Statement` is often referred to as the body of the loop.

This works just like a `do` loop except that `Condition` is evaluated before the `Statement` is evaluated. If `Condition` is false right away, `Statement` is never executed. For this reason, a `while` loop is said to exhibit zero-trip behavior: we might make zero trips through `Statement`.

Add a `while` loop to encode our modified algorithm. The condition `!cin.good()` can be used to control the `while` loop. Since the `while` loop must repeat multiple statements, its `Statement` must be a compound statement or bad things will result.

Compile and thoroughly test what you have written. Continue when what you have written makes the entry of numeric values fool-proof.

## One Execution, Multiple Calculations

The algorithm that our program is using is basically as follows:

1. Display a greeting.
2. Display a menu of operations and read `operation`, guaranteed to be a valid menu operation.
3. Display a prompt for two real values.
4. Read `op1` and `op2`.
5. Loop (pretest), so long as a real value was not entered:
1. Clear the status of cin.
2. Skip the invalid input.
3. Display a prompt for two real values.
4. Input Op1 and Op2.
5. End loop.
6. Compute `result` by applying `operation` to `op1` and `op2`.
7. Display `result`.
Using this algorithm, we have to re-run our program for every calculation, which is inconvenient for the user. A more convenient calculator would wrap some of the statements in a loop, so that the user could perform multiple calculations without having to re-run the program.

To add the loop, we modify our algorithm:

1. Display a greeting.
2. Loop:
1. Display a menu of operations and read `operation`, guaranteed to be a valid menu operation.
2. Display a prompt for two real values.
3. Read `op1` and `op2`.
4. Loop so long as a real value was not entered:
1. Clear the status of `cin`.
2. Skip the invalid input.
3. Display a prompt for two real values.
4. Input `op1` and `op2`.
5. End loop.
5. Compute `result` by applying `operation` to `op1` and `op2`.
6. Display `result`.
7. End loop.
In order to determine which kind of loop to use, we must determine where to evaluate the loop's termination condition, which we might express as "the user wants to quit".

One way to have the user indicate that they want to quit is to view quitting as an operation, and provide an additional menu choice (i.e., `'f'`) by which the user can indicate that they want to quit. The condition `(operation == 'f')` evaluates to true if the user wishes to quit.

So when do we check this condition? The ideal place is to evaluate it as soon as it can be known; in this case this would be immediately following the input of `operation`. We thus have a situation where the loop's condition should not be evaluated at the loop's beginning nor at its end. It must be evaluated in the middle of the loop.

1. Display a greeting.
2. Loop:
1. Display a menu of operations and read `operation`, guaranteed to be a valid menu operation.
2. If `operation` is quit, exit the loop.
3. Display a prompt for two real values.
4. Read `op1` and `op2`.
5. Loop so long as a real value was not entered:
1. Clear the status of `cin`.
2. Skip the invalid input.
3. Display a prompt for two real values.
4. Input `op1` and `op2`.
5. End loop.
6. Compute `result` by applying `operation` to `op1` and `op2`.
7. Display `result`.
8. End loop.

In C++, the unrestricted loop is a simplification of the `for` loop that we call the forever loop, that has the following pattern:

```for (;;)
{
`StatementList1`
if ( `Condition` ) break;
`StatementList2`
}```
By leaving out the three expressions that normally control a `for` loop, it becomes an infinite loop. Of course, we do not want an infinite number of repetitions, but instead we want execution to leave the loop when a termination condition becomes true. As shown in the pattern above, this can be accomplished by placing an `if` statement that uses a termination condition to control a `break` statement within the body of the loop.

When a `break` statement is executed, execution is immediately transferred out of the forever loop to the first statement following the loop. By only selecting the `break` statement when `Condition` is true, a forever loop's repetition can be controlled in a manner similar to the other general-purpose loops.

Modify your source program to incorporate this approach, and then translate and test the newly added statements.

This loop can also be used for the "valid numeric input" loop that we wrote before. Give it a try.

## Submit

Turn in your code and sample runs of your program to demonstrate that it does everything we added to it this week. We added a lot of things, including some error handling, so make sure you test it fully.

## Terminology

condition, continuation condition, counting `for` loop, `do` loop, forever loop, general-purpose loop, generic loop, infinite loop, loop body, one-trip behavior, posttest loop, pretestloop, repeated, selective execution, termination condition, unrestricted loop, zero-trip behavior