CS 509 Test 2

CS 509, Advanced Programming II

Spring 2002 - Test 2

Describe some test cases to determine of an optimizer handles precedence correctly. You needn't cover all possibilities; just give a couple of test cases to indicate you understand the basic ideas.
You should give the input statement blocks, the expected output blocks for each input block, and a description of how the tests show.
The key here is to remember that the operators in the assignment all have the same precedence, which is equivalent to having no precedence at all. Only associativity and parentheses determine the order of evaluation.
The first test case checks for identical precedence. The input statement block is
```
a = 1 + 2 * 3
```
With identical precedence for operators + and *, left to right associativity determines the order of evaluation, which is equivalent to (1 + 2) * 3, producing the correct output statement block
```
a = 9
```
An optimizer that incorrectly assigned C++ precedence to the operators would evaluate * first, producing the incorrect output statement block
```
a = 7
```
A lot of people submitted test cases that contained only a single binary operator
```
a = 7 + 3
```
or contained more than one operator of the same kind
```
a = 7 + 3 + 9
```
or contained several operators of different kinds but with full parenthesization
```
a = (7 + ((9 / 3) * 8))
```
None of these test cases are particularly helpful when testing for correct precedence handling.
The classes A, B, and C are all related to one another. The following code
```
int main() { 

  try { throw new A(); }
  catch (A*) { cout << "caught an A*.\n"; }
  catch (C*) { cout << "caught a C*.\n"; }
  catch (B*) { cout << "caught a B*.\n"; }

  try { throw new B(); }
  catch (A*) { cout << "caught an A*.\n"; }
  catch (C*) { cout << "caught a C*.\n"; }
  catch (B*) { cout << "caught a B*.\n"; }

  try { throw new C(); }
  catch (A*) { cout << "caught an A*.\n"; }
  catch (C*) { cout << "caught a C*.\n"; }
  catch (B*) { cout << "caught a B*.\n"; }

  cout << "\n";

  try { throw new A(); }
  catch (B*) { cout << "caught a B*.\n"; }
  catch (C*) { cout << "caught a C*.\n"; }
  catch (A*) { cout << "caught an A*.\n"; }

  try { throw new B(); }
  catch (B*) { cout << "caught a B*.\n"; }
  catch (C*) { cout << "caught a C*.\n"; }
  catch (A*) { cout << "caught an A*.\n"; }

  try { throw new C(); }
  catch (B*) { cout << "caught a B*.\n"; }
  catch (C*) { cout << "caught a C*.\n"; }
  catch (A*) { cout << "caught an A*.\n"; }
  }
```
produces the following output
```
caught an A*.
caught a C*.
caught a C*.

caught a B*.
caught a B*.
caught a C*.
```
What is the parent-child relation between the classes A, B, and C? Explain.
The first try statement throws an A*, which is caught by the A* block; nothing to learn here.
The second try statement throws a B*, which is caught by the C* block. This tells us that B is a child of C. But, we also know that A can't be a parent of B because otherwise the A* block would have caught the B*.
The third try statement throws a C*, which is caught by the C* block; nothing new here. But, again, because the A* block didn't catch the C*, then A can't be a parent of C.
The fourth try statement throws a A*, which is caught by the B* block: A must be a child of B.
The fifth try statement throws a B*, which is caught by the B* block; nothing to learn here.
The sixth try statement throws a C*, which is caught by the C* block; nothing to learn here, but B can't be C's parent because otherwise B* would have been caught the C*.
In summary: A can't be anybody's parent, and B can't be C's parent. Because they're all the classes are related, C must be B's parent and B must be C's parent.
A colleague of yours (actually Koenig and Moo) has written the following loop and invariant to explain the loop:
```
vector<double> homework;
double x;

// invariant:  homework contains all the homework grades

while (cin >> x) 
  homework.push_back(x);
```
Do you think the invariant is acceptable? If you think the invariant is acceptable, make sure you explain how it's initially true; if you think the invariant's unacceptable, propose an alternative.
The problem with this invariant is that it might not be initially true; in fact, the only time it will be initially true is when cin is empty.
To discover a better invariant, it's a good idea to look at the loop that's being described and try to capture what the loop is trying to do (this is backwards, of course - the invariant should be written before the loop is written). The trick is to describe the loop's behavior in a way that is always true.
The loop copies values from cin to homework; that is, homework contains some initial part of the homework grades. This suggests the invariant
The sequence of values given by (cin, homework) contains all the homework grades.
This invariant is initially true, because cin contains all the grades and homework is empty. Each iteration of the loop removes a value from cin and pushes it into homework, preserving the truth of the invariant. When the loop ends,
The sequence of values given by (cin, homework) contains all the homework grades, and cin is empty.
is true, which means that homework contains all the homework grades, which is a pretty accurate description not only of the loop's behavior, but also of the the behavior needed by the rest of the code.
Koenig and Moo describe three kinds of formal parameters definitions for functions. What are they, and what are they used for?
The three formal parameter kinds are
1. Non-constant non-reference parameters - these are local variables within the procedure; changes made Non-constant, non-reference formal parameters in the procedure do not change the associated actual parameter value. They are safe (because changes are localized) but can be expensive (because it requires copying the value from the actual parameter to the formal parameter) and inconvenient (when more than one value has to be returned from a procedure).
2. Non-constant reference parameters - these are aliases within the procedure for the actual parameters; changes made to non-constant, reference formal parameters within the procedure appear in the associated actual parameters. They are unsafe (because they can change the caller's data) but are efficient (because they involve only address manipulations and no data copying) and convenient (when more than one value has to be returned from a procedure).
3. Constant reference parameters - these are read-only aliases within the procedure for the actual parameters; changes cannot be made to constant, reference formal parameters within the procedure, so the associated actual parameters will also be unchanged. They are safe (because they can't be changed at all) and efficient (because they involve only address manipulations and no data copying), and can be both convenient (they preserve values) and inconvenient (they prevent values from changing).

This page last modified on 21 February 2002.