Lecture Notes for CS 509, Advanced Programming II

10 February 2004, Assignment 1 Code Review

Outline

• Design

  • Top-Down design and stepwise refinement

• Design by wishful thinking.

• Analysis

  • What's the problem?

  • What's the solution?

• Design

  • Balancing tags.

• 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.

  Start with an abstract problem, end with a concrete problem.

  • 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 the document,
  Find the tags,
  See if the tags balance.

• That's it; is that the problem?

  • What's in a document?

    • Tags and text.

  • Do we care about text?

    • No.

  • So maybe the problem is

    Read in the tags,
    See if the tags balance.

    • Maybe.

• 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 tags.

  • A function to balance tags.

• Notice how high level these wishes are.

  • What's a tag look like? Worry about that later.

  • How do you balance tags? Worry about that later.

  • What happens if something goes wrong? Worry about that later.

  ---

  What's the Solution?

  • Given our wishes, the solution's easy.

    • This is a good indication you've wished well.

    int main()
    
      vector<tag> tags = read_tags(std::cin)
      string emsg = balance_tags(tags)
      if not emsg.empty()
        std::cout << emsg
    

    • Notice we also wished up the type tag.

  • From where do these functions come?

    • Time to start wishing again.

Now what?

• Where are the functions read_tags() and balance_tags()?

• Looks like it's time to start wishing again.

  • What do you need to read a tag?

    • Read in something between angle brackets.

    • Check to make sure the something is legal.

    • These probably don't need any more wishes.

  • How do you balance tags?

    • This seems hard; more wishes here.

Balancing Tags

• How do you balance tags? What does the problem say?

  • Tags are balanced if

    1. Every open tag has a paired close tag.

    2. The open tag appears before its paired close tag.

    3. All tags between the paired tags are also paired.

• Given a tag T is it paired?

  • If T is a close tag, rule 2 tells us no.

  • Rule 3 tells us that all tags between T and its pair must be balanced.

  • Rule 1 tells us the next tag must be T's close tag.

Implementing Tag Balancing

• With those three rules, implementation follows:

  balance_tags(i, tags)
  
    if i >= tags.size()
      return i
  
    if not is_open_tag(tags[i])
      error "unmatched close tag"
  
    j = balance_tags(i + 1, tags)
    if j > tags.size() 
      error "missing close tag"
  
    if tag_match(tags[i], tags[j])
      return j + 1
    else
      error "unmatched tags"
  

• Where's the stack here?

Tags

• Yes, but what are tags?

• Who cares?

  • They need to respond to is_open_tag() and tag_match().

  • As long as they do that, I'm happy.

• Notice the solution tells us what tags are.

  • The problem tells us how they behave.

class tag

  bool is_open_tag() { ... }

  bool matches(const tag & t) { ... }

  tag(bool open, string name) { ... }

Test cases

1. empty test

2. garbage test

3. < hello > < /hello > test

4. </hello> <hello> test

5. </hello> test

6. <hello> test

7. <hello test

8. <hel lo> </hello> test

9. <> </> test

10. <a> <b> </b> </a> test

11. <a> <b> </b> </a> <a> <b> <c> </c> </b> </a> test

• These are simple tests.

• 8 and 9 were inspired by your colleague's code.

What Happened

• There are five scores:

  1	y	:	the right answer.
  2	+	:	almost right.
  3	-	:	not completely wrong.
  4	n	:	the wrong answer.
  5	c	:	crash.

   
  c
  n
  -
  +
  y
  1
  0
  0
  0
  0
  7
  2
  0
  1
  0
  3
  3
  3
  0
  2
  0
  0
  5
  4
  1
  1
  1
  1
  3
  5
  1
  1
  1
  1
  3
  6
  0
  1
  1
  1
  4
  7
  0
  2
  0
  1
  4
  8
  0
  2
  0
  2
  3
  9
  1
  3
  0
  1
  2
 10
  0
  2
  0
  0
  5
 11
  0
  2
  0
  0
  5

Follow Directions

• What to do:

  "Error messages should be a single line of informative text starting with ! (that's bang followed by space)."

• What not to do:

  !INVALID DOCUMENT
  
  --
  
   !Non-alphanumeric. OR ! tag without text 
   couldn't find matching close tag 
  
  --
  
  !NON ALPHANUMERIC CHARACTER IN TAG NAME.
  
  --
  

Be Wary of Duplicate Code

• Duplicate code is bad code.

  if ctag.length() != 0 && !alphaNum(ctag)
    cout << "!Non-alphanumeric"
    exit(1)
  else
    cout<<"! unterminated  tag"
    exit(1)
  
  if segment.size() == 0
    cout << "matching close tag missing"
    exit(1)
  

• Oops.

  ***
  *** <hello> test
  ***
  
  !!! Error message expected; actual output:
  
  ---
   matching close tag missing 
  ---
  

Factor Duplicate Code

• Factor duplicate code into a subroutine.

  static void 
  oops(const std::string & emsg) 
    cout << "! " << emsg << ".\n"
    exit(1)
  
  if ctag.length() != 0 && !alphaNum(ctag)
    oops("Non-alphanumeric in name")
  else
    oops("Unterminated tag")
  
  if segment.size() == 0
    oops("Matching close tag missing")
  

• Now it's easy to make sure of proper behavior.

  • It's also easier to understand what's going on.

  • oops() clearly indicates an error state.

• This is a fatal mistake.

Follow Directions, Part 2

• What to do:

  "Input comes entirely from std-in."

• What not to do:

  int main()
  
   data_info D(ReadFile("DATA.txt"))
   if (D.get_Vdata().empty())
     return EXIT_SUCCESS
  
    // and so forth
  

Don't be Sloppy

• What's special about this code?

  /*
  bool Is_empty(string tag)  {
   tag.erase(0,1)
   tag.erase(tag.length() - 1, 1)
   return tag.length() == 0
   }  
  */
  

• Don't leave your trash laying around - clean it up.

  while i < in.length() && !bracket(in[i])
    chars++
    i++
  // cout << "i = " << i
  // cout << "in[" << i << "] = " << in[i]
  if (in[i] == '>')
    // cout << "in[" << i << "] = " << in[i]
    // cout << "j = " << j
    // cout << "chars = " << chars
    tag = in.substr(j, chars + 2)
    tag = remove_space(tag)
    ctag = trim(tag)
    // cout << "tag " << tag
    if ctag.length() !=0  && !alphaNum(ctag)
      // cout << "tag =" << tag
  

Favor Local Variables

• Global variables are hard to understand and use.

  /* save all the stuff read in. */
     string read_in
  
  int check_error(string str)
  
   int error_status = ALL_OK
   int length
   clear_tagStack()
   read_in += str
  
   pos = read_in.find(LEFT_ANGLE_BRACKET)
  
  

• Also - nothing to do with globals, this is expensive.

  • Do one thing at a time.

  • Read then parse, not read and parse.

Understand Array Accesses

• You are responsible for every array access in your code.

  void readNextElement()
  
    string tag
    getline(cin, tag, '>')
    if !formatElement(tag)
      error("...")
  
    if(tag[0] == '/')
      if(elements.empty() == true) 
        error("...")
  
      // and so forth
  

• Oops.

***
*** <> </> test
***

!!! Error message expected; actual output:

---
Accessing index 0 in a string of size 0.
../../test-code: line 10: Abort ./$ex <$ifile
---

Test Your Assumptions

• If your code uses an assumption, make sure it's true.

  assert(not tag.empty())
  if(tag[0] == '/')
    if(elements.empty() == true) 
      error("...")
  
  if(tag.at(0) == '/')
    if(elements.empty() == true) 
      error("...")
  

• Even better, make it obviously true:

  txt = trim(txt)
  if txt.empty()
    error "tag contains no text"
  
  bool close_tag = txt[0] == '/'
  if close_tag
    txt[0] = ' '
    txt = trim(txt)
  

Points to Remember

• Wishful thinking is a powerful design tool.

  • But remember who the genii is.

• Follow directions.

• You are responsible for everything in your code.

This page last modified on 25 March 2004.