Assignment 2 Code Review

26 February 2002 - CS 509

Design

Two main design problems: how to start, how to keep going.
How to start - top-down design.
- Start from the problem, work towards a solution.
- You'll always have a problem to work on.
- Why bother if you're not going to pay attention to the problem?
How to keep going - stepwise refinement.
- Each step adds detail to the problem.
- Solve the problem at each step.
- The step-to-step solution changes should be small.
There are other approaches.
- Bottom-up design.
- Object-oriented analysis.

Top-Down Design and Stepwise Refinement

Top-down design starts with the problem.
- You'll always have a problem.
- The problem can provide a lot of guidance.
Start small, step small.
- Abstract away almost all problem details.
- Re-introduce abstracted details one at a time.
- The solution changes in small, managable steps.
You always have a working system.
- The initial solution works, but isn't useful.
- Each step keeps a working solution, improves usefulness.
- Test each step, add tests between steps.
Problems
- Abstraction is hard; some people don't get it.
- You have to make a lot of decisions all the time.
- Sometimes it seems like it never ends.
- All of these things are skills you have to learn

What's the Problem?

Input a statement block,
optimize a statement block,
write a statement block.
That's it; that's the problem.
- But, what's a statement block?
  - Who cares? Worry about it later.
- But, what about space characters?
  - Who cares? Worry about them later.
Abstracting away almost all details leaves a simple problem.
- "Abstracting" means "delaying", not "forgetting".
- The abstracted details are reintroduced one at a time.

What's the Solution?

Writing down the problem practicaly describes the solution.

int main() {

  statement_block sblock;
  std::string sep;

  while (sblock.input(std::cin)) {
    sblock.optimize();

    std::cout << sep;
    sblock.output(std::cout);
    sep = "\n";
    }
  }

This is not the only solution.

equation equn;

int main() {

  while (read_equ_blocks(std::cin)) { }
  equn = equation_compiler.run_compiler(equn);
  equn.output();

  return 0;
  }

Which is better?
- Which is simpler?
- Which reflects the problem more accurately?

What's a Statement Block?

main() tells us a lot.
- Statement blocks should input, optimize, and output.

The problem tells us a lot too.

A fixed-length sequence of statements.
What's a statement? I dunno - a string.
A statement block is a vector of strings.

class statement_block {
  public:
    bool input(istream & ins) {
      string s;

      if (read_nonblank_line(ins, s)) return false;
      do sblock.push_back(s);
      while (read_nonblank_line(ins, s));

      return true;
      }

    void output(ostream & outs) { 
      for (unsigned i = 0; i < sblock; i++)
        outs << sblock[i] << "\n";
      }

    void optimize(void) { }

  private:
    vector sblock;
  };

The First Solution

We now have a working program to solve the problem.
True, it doesn't work well, but
- It handles empty input correctly.
- It inputs and outputs statement blocks correctly.
- It handles unoptimizable statment blocks correctly.
- This program is worth a 75.
We have three test cases too.
- The empty input.
- A single unoptimizable statement block.
```
x = y + z
```
- Two unoptimizible statement blocks.
```
x = y + z

x = y + z
```
- Do not underestimate the power of simple tests.
Notice how main() influenced statement blocks.
- The previous solutions guide the current solution.

What's the Next Step?

How do we improve statement blocks?

What's the problem say?
A statement block is a sequence of statements.

class statement_block {
  public:
    bool input(istream & ins) {
      string s;

      if (read_nonblank_line(ins, s)) return false;
      do sblock.push_back(statement(s));
      while (read_nonblank_line(ins, s));

      return true;
      }

    void output(ostream & outs) { 
      for (unsigned i = 0; i < sblock; i++) {
        sblock[i].output(outs)
        outs << "\n";
        }
      }

    void optimize(void) { 
      for (unsigned i = 0; i < sblock; i++) {
        sblock[i].optimize()
      }

  private:
    vector<statement> sblock;
  };

Finishing Statement Blocks.

What's a statement? Who knows?

The problem does: it's a string.

class statement {

  public:

    statement(const string & s) : stmt(s) { }

    void optimize(void) { }

    void output(ostream & outs) const {
      outs << stmt;
      }

  private:
    string stmt;
  };

Notice that
- The program is working correctly again.
- Statement Blocks determined the statement interface.
- We're done with statement blocks (not really).

Statements

Statements are the next step.
- Is a string a good representation for a statement?
- What does the problem say?
  - Input - sure.
  - Output - fine.
  - Optimization - umm. . .
- Trying to optimize a string seems to be hard.
  - Checking syntax.
  - Substituting constants for variables.
  - Computing constant subexpressions.
How about a sequence of substrings.
- "x = y + 1" vs. "x", "=", "y", "+", "1".
- Better, it's easier to find parts and their relation.
- But it's still hard to figure out, for example, left and right.

Representing Statements

A statement has a lot of structure, a string or a vector doesn't.
- Ignoring given structure is not a good idea.
What is the statement structure? What does the problem say?
- A statement is variable = expression
- An expression is (with a little fiddling around)
  - value₁ op₁ value₂ op₂ . . . op_n value_{n + 1}
  - A value_i is an int, a variable or a parenthesized expression.
- Better, but moving left and right is still hard. Anything else?
  - The problem says the operators are binary.
  - Represent expressions as binary trees.
  - Great - no parentheses and easy to mainpulate.
    - Optimization and output's a walk of the tree.
    - What about the translation to binary trees?

Line Statistics - Newlines

	000	200	300	400	500	600	700	800	1300	1500
0		1				1
10							2	2
20			1
30						1
40				1	1	1	1			1
50						1
60	1					1		1	1
70					1
80		1				1
90		1					1
Totals	1	3	1	1	2	6	4	3	1	1

Line Statistics - Semicolons

	000	100	200	300	400	500
0				2
10
20		1			1
30	1	1	2	1
40			3
50
60			2			1
70			2	1
80	1			1
90	1	1	1
Totals	3	3	10	5	1	1

File Statistics

File Counts	Count	Average Lines/File	Avg Semicolons per File
1	11	476	188
2	1	224	115
3	1	287	128
4	2	169	80
5	5	169	65
6	2	125	45
7	0
8	0
9	0
10	0
11	1	124	38

Procedure Statistics

total	pages per procedure
procs	1	2	3	4	5	6	7	8	9	10
3	3
4	3	1
4	3						1
6	4		1	1
7	1	1	3			2
7	4	2	1
10	5	2	1	1		1
11	5	4	1							1
13	11	1						1
14	7	4	1	1		1
14	9	5
20	15	2	3
20	17		3
22	13	6	3
22	18	3	1
22	19	1			1		1
22	20	2
24	20	3		1
28	25	3
31	24	4	3
33	31	2
59	50	7	1	1
70	66	3		1

Know Your Tools

Consider lltostr().
- A bad library routine.
- Converts a long long to a character array.
- Has prototype char * lltostr(long long, char *).
- The char * argument points to the buffer end, not the beginning.
Observe.
- Both trash whatever's preceeding intstr.
- Both use dynamic memory and don't free it.
- Both don't need to use dynamic memory.
- Ten characters is too short; a long long's 64 bits.

Use Named Constants

A magic number just appears in code with no explanation.

What does this code do?

int ans = check(s.substr(i,j-i));
     if (ans == 1) { /* whatever */ }
else if (ans == 2) { /* whatever */ }
else if (ans == 3) { /* whatever */ }
else if (ans == 4) { /* whatever */ }
else if (ans == 5) { /* whatever */ }
else if (ans == 6) { /* whatever */ }
else if (ans == 0) return false;

Magic numbers are hard to understand, use, and change. Avoid them.

Replace magic numbers with named constants.

#define INVALID  0
#define NUMBER   1
#define VARIABLE 2
#define OPERATOR 3
#define LB       4
#define RB       5
#define EQUAL    6

if (StBlk[row][0].Type() != VARIABLE) /* . . . */
if (StBlk[row][col].Type() == INVALID) /* . . . */
if ((StBlk[row][col].Type() == NUMBER ||
     StBlk[row][col].Type() == VARIABLE) &&
    (StBlk[row][col+1].Type() == LB)) /* . . . */
if (StBlk[row][col].Type() == EQUAL) /* . . . */
if (StBlk[row][1] .Type() != EQUAL) /* . . . */

Factor Common Code

Duplicated code is bad code.
- It leads to code bloat.
- It hard to understand. (Is this the same as that?)
- It's a pain to maintain and modify.
Factor out duplicate code and make it common.
- Move it into subroutines.

Example Factoring


int ans = check(s.substr(i,j-i));
if (ans ==1) {
  string str = s.substr(i,j-i);
  dq.push_back("n");
  smallv.push_back(str);
  i = j;
  }
else if (ans == 2) {
  string str = s.substr(i,j-i);
  dq.push_back("s");
   smallv.push_back(str);
  i = j;
  }
else if (ans == 3) {
  string str = s.substr(i,j-i);
  dq.push_back("o");
   smallv.push_back(str);
  i = j;
  }
else if (ans == 4) {
  string str = s.substr(i,j-i);
  dq.push_back("e");
   smallv.push_back(str);
  i = j;
  }
else if (ans == 5) {
  string str = s.substr(i,j-i);
  dq.push_back("pl");
   smallv.push_back(str);
  i = j;
  }
else if (ans == 6) {
  string str = s.substr(i,j-i);
  dq.push_back("pr");
   smallv.push_back(str);
  i = j;
  }
else if (ans == 0)
  return false;

int ans = check(s.substr(i,j-i));

if (ans == 0)
  return false;

string str = s.substr(i,j-i);
if (ans == 1)
  dq.push_back("n");
else if (ans == 2)
  dq.push_back("s");
else if (ans == 3)
  dq.push_back("o");
else if (ans == 4)
  dq.push_back("e");
else if (ans == 5)
  dq.push_back("pl");
else if (ans == 6)
  dq.push_back("pr");

smallv.push_back(str);
i = j;

  

int ans = check(s.substr(i,j-i));

if (ans == 0)
  return false;

char * what[] = {
  "", "n", "s", "o", 
  "e", "pl", "pr" };

assert((ans > 0) && (ans < 7);
dq.push_back(what[6]);

smallv.push_back(s.substr(i,j-i));
i = j;

Test Cases

Most were simple.
- They came from the problem or people's code.
The killer was
```
a = 1
b = a + 1
a = c + 1
c = a + 1
```
- Everybody forgot to unset a the second time.
- I made this mistake too.

This page last modified on 26 February 2002.

File Counts	Count	Average Lines/File	Avg Semicolons per File
1	11	476	188
2	1	224	115
3	1	287	128
4	2	169	80
5	5	169	65
6	2	125	45
7	0
8	0
9	0
10	0
11	1	124	38

File Counts	Count	Average Lines/File	Avg Semicolons per File
1	11	476	188
2	1	224	115
3	1	287	128
4	2	169	80
5	5	169	65
6	2	125	45
7	0
8	0
9	0
10	0
11	1	124	38

File Counts	Count	Average Lines/File	Avg Semicolons per File
1	11	476	188
2	1	224	115
3	1	287	128
4	2	169	80
5	5	169	65
6	2	125	45
7	0
8	0
9	0
10	0
11	1	124	38