Assignment 2 Code Review

27 February 2003 - CS 509

Assignment 2 Code Review

Design
- Top-Down design and stepwise refinement
Design by wishful thinking.
Analysis
- What's the Problem?
- What's the Solution?
Design
- Computing values
- Comparing values
Coding problems

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, manageable 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.

Top-Down Design Problems

Abstraction is hard; some people don't get it.
- Usually your bosses, their bosses, and so on.
You have to make a lot of decisions all the time.
- And you have to remember them. And you have to fix them.
Sometimes it seems like it never ends.
- But, suddenly, it does.
All of these things are skills you have to learn.
- And learn, and learn, and learn.

Design by Wishful Thinking

Need a subroutine to help solve the problem? Pretend it exists and use it!
- Eventually it will have to exist.
- Until it exists, it's easy to change.
The problem will tell you the wishes to make.
- Make sure you understand the problem.
Wishes should correspond to significant subproblems.
- You have your choice of subproblems.
- Knowledge and experience make you a better wisher.
- A skilled professional is a good wisher.
Make sure the wishes significantly advance the solution.
- Wishing in small steps leads to a lot of work.
- When all the wishes are small, it's time to stop.
- Don't get ahead of your self too much.

What's the Problem?

Read in two code blocks,
Figure out what they compute,
Determine if the computations are the same..
That's it; that's the problem.
- What's a code block?
  - Who cares? Worry about it later.
- What happens if an operation is **?
  - Who cares? Worry about it later.
Done correctly, wishing is a form of abstraction.
- When not done correctly, wishing leads to too many details at once and insufficient abstraction.

At the Wishing Well

What to wish for?
- A function to read code blocks.
- A function to find computations.
- A function to compare computations.
Notice how high level these wishes are.
- What's a code block look like? Worry about that later.
- How do you find the computation? Worry about that later.
- How do you compare computations? Worry about that later.
Notice the wished-for functions solve the problem.
- This is a good indication you've wished well.
From where do these functions come?
- Time to start wishing again.

What's the Solution?

Given our wishes, the solution's easy.

int main(int argc, char * argv[])

  code_block 
    cb1 = read_code_block(std::cin),
    cb2 = read_code_block(std::cin);

  values
    c1 = compute_values(cb1),
    c2 = compute_values(cb2);

  if (c1 != c2)
    std::cout << "different values"

Notice we also wished up the types code_block and value.

Now what?

Where are the functions read_code_block(), compute_values(), and value equality?
Looks like it's time to start wishing again.
- Reading in code blocks doesn't seem that hard; assume no wishes are needed here.
- How do you compute values?
  - This seems hard; more wishes here.
- How do you compare computations?
  - Don't know; it depends on what computations are.
  - Put this aside for the moment.

Finding Computed Values

How do you compute a value?
- The hard thing here seems to be representing values.
- Fine, let's wish for a value representation.
Given values v1 and v2, how do you compute v1 + v2?
```
value sum(v1, '+', v2)
```

How do you find values computed by code?

for i = 1 to cb.size()
  if cb[i].opc = move
    storage[cb[i].dst] = storage[cb[i].src]
  else
    storage[cb[i].dst] = 
      value(storage[cb[i].dst]),
            cb[i].opc,
	    storage[cb[i].src])

Storage

What is this storage thing?
- It associates names with values.
- This should be simple enough to not need any more wishes.
There are a few tricks, though.
- Initial storage values.
- Values when src or dst are numbers.
But not too tricky.
- Use the name as the initial value.
  - storage["joe"] returns "joe" the first time.
  - There are other possibilities.
- Return the number itself as the value.
  - storage["-134"] returns "-134" always.

Values

We've delayed enough - what are values?
What operations do values need to support?
- Combine old values into new ones.
```
value v(v1, '+', v2)
```
- Compare two values for inequality.
```
if (v1 != v2)
```
Inequality seems the harder of the two; focus on that.
- If values were strings, inequality would be easy.
- And so would creating values.

Values as Strings

class value 

  string rep;

  value(string v) : rep(v) { }

  value(value left, string op, value right)
    : v(left.rep + op + right.rep) { }

  bool operator != (value v)
    return rep != v.rep

This almost works.
- But "a+b" != "b+a" should be false.
- And so should "3+7" != "10".

Values as Trees

Strings are easy to compare, but hard to manipulate.

What does

value(value left, string op, value right 
  : v(left.rep + op + right.rep) { }

suggest?

Values as binary trees.

Binary trees are easy to manipulate, but hard to compare.
- Flattening a tree into a string is easy.
What about the manipulations?
- They're mostly easy, but there are a lot of them.
- Wish for a twiddle() operation to manipulate trees.
```
bool operator != (value v)
  while true
    if repl != v.repl return true
    if !twiddle(repl) return false
```

Implementing `twiddle()`

twiddle(), although simple in parts, is hard in total.
- Each value tree can be twiddled in many ways.
- May have to try all combinations of ways.
- Have to stop too.
- This is similar to generating all permutations.
As an alternative, define a canonical tree form.
- Both trees can be translated to canonical form.
- Flatten and compare the two canonical trees.
```
bool operator != (const value & v) 
  return 
    flatten(canon(rep)) != flatten(canon(v.rep))
```

Canonical Trees

Canonical tree form reflects arithmetic properties.
Flatten trees with identical associative operators.
Order the operands for commutative operators.
Replace operations on constants with their values.

Line Statistics - Newlines

	100	200	300	400	500	600	700	800	900	1000	1100	1200	1300	1400
0
10
20	1										1
30			1
40		1
50
60					1	1
70		1	1			1
80				1										2
90				1
Totals	1	2	2	2	1	2	0	0	0	0	1	0	0	2

Line Statistics - Semicolons

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

Procedure Statistics

total	pages per procedure
procs	1	2	3	4
4	2	1		1
4	3	1
10	7	2		1
15	11	4
17	12	4		1
21	21
22	17	5
37	32	4	1

Follow Directions

Understand what you're supposed to do.

Input (between the --- lines):
---
move  b 10

move  b 10
---

Expected output (between the --- lines):
---
---

Actual output (between the --- lines):
---
two blocks perform identical computations
---

When it says "read from std-in", read from std-in.

std::vector ReadFromFile() {
  ifstream iFile;
  iFile.open("input.txt");
  if (!iFile) {
    cerr <<" cannot open input file" << endl;
    exit(EXIT_FAILURE);
    }

Do Not Use `char` Arrays

char buf[4096];

while (cin.getline(buf, sizeof(buf), '\n'))
  // whatever.

This code isn't terrible.
- The length-limited form of getline() prevents buffer overflow.
But, it doesn't work for lines longer than 4095.
- And there's no good reason why it shouldn't.
To work correctly, this code has to re-implement strings.
- Go back and read the rest of the input line.
- Make sure there's enough space for the whole line.
- Why bother? Strings have already been implemented.
Don't use character arrays, use strings.

No Really - Don't Use `char` Arrays

static char tokens[4][100];

int chk_input(const char * line) 

  istringstream iss(line);
  unsigned i;

  for (i = 0; i < 4; i++) { 
    if (!(iss >> tokens[i])) break;
    }

The 200 character variable name kills this code.
This is a buffer-overlow error - bad, bad, bad.
The Microsoft Windows ME Help and Support Center is prone to a buffer overflow. This is due to insufficient bounds checking on input supplied through the HCP URI parameter.
--- Security Focus,
26 February 2003

Understand Your Code

You are responsible for every memory access that your code makes.

What's wrong with this code?

void Blocks::read_blocks()

  bool bl1;
  std::string line;

  while (getline(cin, line))
    if (block1.size() != 0 && isspace(line[0]))
      bl1 = false

How about this code?

int is_register(string str)

  char * temp_char = &str[1]

  if (str.size() > 0) && (str.size() < 3)
    // whatever

Points to Remember

Design from the top down with stepwise refinement.
- Little by little, bit by bit.
Wishful thinking is a powerful design technique.
- But remember, that the wishes have to come true.
Do not use char arrays.
- Do not use char arrays. Do not use char arrays.

This page last modified on 11 March 2003.