Lecture Notes for Advanced Programming II

6 November 2001 - Assignment 3 Code Review

The Test Cases

1. The empty input.

2. The input

   x = 1
   y = 1
   z = x + y
   

3. The input

   x = 1
   y = 1
   z = x + y
   
   x = 1
   y = 1
   z = x + y
   

4. The input

   x = 1000000000000000000000000
   

5. The input

   x = 1000000000000000000000000
   y = 1000000000000000000000000
   z = x + y
   

The Results

• 23 programs, 2 didn't compile.

• Working programs produced correct output.

• Sorta working programs echoed the input correctly.

1. Empty input - 20 programs worked.

2. xyz input - 1 program worked, 10 sorta worked.

3. xyzxyz input - 9 programs sorta worked.

4. 14 programs worked.

5. 6 programs sorta worked.

Line Statistics - Newlines

Statistics derived from all files ending in .cc, .cpp, .CC, .C, and .h.

Line Statistics - Semicolons

Statistics derived from all files ending in .cc, .cpp, .CC, .C, and .h.

Procedure Statistics

Statistics derived from all files ending in .cc, .cpp, .CC, .C, and .h.

File Statistics

Statistics derived from all files ending in .cc, .cpp, .CC, .C, and .h.

A Design Problem

• Human brains are small, programming problems are big.

  • Break the problem into smaller pieces.

  • Delay decisions for as long as possible.

  • Hide decisions so they can be easily changed.

• This is an iterative process.

  • Design a little, implement a little, design a little, . . .

  • You should always have a working program around.

• This is a trial and error process.

  • You will make wrong or poor decisions.

  • Be prepared to throw away some or all of your code.

  • The write-once program doesn't exist.

Top-Down Decomposition

• What's the problem?

  1. Read an equation set.

  2. Simplify the equation set.

  3. Write the simplified set.

  4. Repeat.

• What program solves that problem?

  #include "equation-set.h"
  
  int main() {
  
    equation_set eset;
  
    while (eset.read(cin)) {
      eset.simplify();
      eset.write(cout);
      cout << "\n";
      }
    }
  

• Wishful thinking is a powerful design tool.

Small Code Is Good

• Small code is easier to design, implement, and understand.

• Which is better?

  void main() {
    LList list;
  
    cout << "Please enter a sequence of sets of "
         << "algebraic eq. (ctrl+d) to end" << endl;
  
    int setCount = readInput(list);
    printResults(list, setCount);
    }
  

  or

  

Details Matter

• Details are easier to manage in small code.

• Which is better?

  void main() {
    LList list;
  
    cout << "Please enter a sequence of sets of "
         << "algebraic eq. (ctrl+d) to end" << endl;
  
    int setCount = readInput(list);
    printResults(list, setCount);
    }
  

  or

  int main() {
    equation_set eset;
  
    while (eset.read(cin)) {
      eset.simplify();
      eset.write(cout);
      cout << "\n";
      }
    }
  

• What is each main() doing?

• Which main() is correct, which is wrong?

• Simplification's broken. Which main() tells you more?

What's an Equation Set?

• What does main() say?

  class equation_set {
  
    public:
  
      bool read(istream &);
      void simplify(void);
      void write(ostream &) const;
  
    };
  

• What's the data representation?

  • I don't know - pick something and hide it.

  • If it's hidden, it's easier to change.

  • And remember to change it when you know more.

  class equation_set {
  
    private:
  
      typedef vector<string>          eqn_set;
      typedef eqn_set::iterator       eset_iter;
      typedef eqn_set::const_iterator eset_citer;
  
      eqn_set equations;
    };
  

What About the Equation Set Code?

• What does read() do?

  bool equation_set::read(istream & is) {
  
    string l;
  
    equations.clear();
  
    while (true) {
      if (!getline(is, l)) return false;
      if (!is_blank(l)) break;
      }
  
    do equations.push_back(l);
    while (getline(is, l) && !is_blank(l));
  
    return true;
    }
  

• What does write() do?

  void equation_set::write(ostream & os) const {
    std::copy(equations.begin(), equations.end(),
      ostream_iter<string>(os, "\n"));
    }
  

• What does simplify() do?

  • Who knows?

  • This is a hard decision, delay it.

    void equation_set::simplify(void) {
      }
    

What Have We Got?

• We have a working program.

  • True, it doesn't do much work.

  • But, the work it does do is correct.

    • Empty input is correct.

    • Output formatting is correct.

      • 66% (14 of 21) of the programs didn't do i-o correctly.

  • And it took about 20 minutes.

  • Mistakes I made.

    • Forgot the equations.clear().

    • Used is_nonblank() instead of is_blank().

    • Forgot to change the sense of the is_blank() tests.

• We have some guidance as to the next steps.

  • What's an equation?

  • What are the simplifications?

  • What about errors?

What's An Equation?

• Currently, a string. Is this ok?

• Probably not.

  1. Need to look at equation pieces.

  2. Need to look at one piece in relation to another.

  3. Need to group pieces non-linearly.

• "Pieces" appears a lot - how about pieces of a string?

  • Definitely solves 1, makes 2 easier, not much help for 3.

  • Two out of three ain't bad.

• How to split into pieces? Where are the pieces stored?

  • These decisions should be hidden in an equation class.

Equation Sets Reconsidered

• The data representation.

  class equation_set {
  
    private:
  
      typedef vector<equation>        eqn_set;
      typedef eqn_set::iterator       eset_iter;
      typedef eqn_set::const_iterator eset_citer;
  
      eqn_set equations;
    };
  

• The code.

  bool equation_set::read(istream & is) {
  
    string l;
  
    equations.clear();
  
    while (true) {
      if (!getline(is, l)) return false;
      if (!is_blank(l)) break;
      }
  
    do equations.push_back(equation(l));
    while (getline(is, l) && !is_blank(l));
  
    return true;
    }
  
  void equation_set::write(ostream & os) const {
    for (eset_citer i = equations.begin(); i != equations.end(); i++)
      *i->write(os);
    }
  

Program for Change

• You'll make changes; others will make changes.

• Which is better?

  typedef vector<equation>        eqn_set;
  typedef eqn_set::iterator       eset_iter;
  typedef eqn_set::const_iterator eset_citer;
  
  eqn_set equations;
  

  or

  vector<vector<string> > process_set(
    vector<vector<string> >, int, int);
  
  int No_solution(
    vector<vector<string> >, vector<vector<string> >, vector<string>);
  
  vector<vector<string> > calculation(
    vector<vector<string> >, vector<vector<string> >, vector<string>);
  

• Isolate decisions in one place so they can be easily changed.

The Equation Class

• What does an equation do? What does the code say?

  class equation {
    public:
      equation(const string &);
      void write(ostream &) const;
    };
  

• How are equations represented? Later for that.

  class equation {
    private:
      string eqn;
    };
  

• And the code.

  equation::equation(const string & str) : eqn(str) { }
  
  equation::equation(ostream & os) {
    os << eqn << "\n";
    }
  

• What's the point?

  • Important decisions are hidden.

  • We still have working code.

Breaking An Equation Into Parts

• split() doesn't work on x=7+z.

• Also, what about syntax errors?

• Some thought is required. What does the data say?

  • An equation is two expressions separated by an equals sign.

  • An expression is

    • A variable name (a letter).

    • A number.

    • Two expressions separated by an operator.

  • An expression is a sequence of values separated by operators.

    • A value is a variable or a number.

• The data suggests the following code:

  fragment_equation()
    fragment_expression()
    check_for("=")
    fragment_expression()
  
  fragment_expression()
    fragment_value()
    while check_for("*-+/")
      fragment_value()
  
  fragment_value()
    if !fragment_number()
      fragment_variable()
  

Fragmenting Code

typedef vector<string> fragments;

fragments fragment_eqn(const string & str) {
  fragments pieces;
  str_citer s = str.begin();
  fragment_expr(s, str.end(), pieces);
  fragment_char("=", s, str.end(), pieces);
  fragment_expr(s, str.end(), pieces);
  return pieces;
  }

void fragment_expr(s, e, pieces) {
  fragment_value(s, e, pieces);
  while (fragment_char("+-*/", s, e, pieces))
    fragment_value(s, e, pieces);
  }

void fragment_value(s, e, pieces) {
  if (!fragment_var(s, e, pieces))
    fragment_number(s, e, pieces);
  }

bool fragment_var(s, e, pieces) {
  return fragment_char("A...Za...z", s, e, pieces);
  }

bool fragment_number(s, e, pieces) {
  if (!skip_space(s, e) || !isdigit(*s))
    return false;
  str_citer n = std::find_if(s, e, is_not_digit);
  pieces.push_back(string(s, n));
  s = n;
  return true;
  }

bool fragment_char(chars, s, e, pieces) {
  if (!skip_space(s, e) || (index(chars, *s) == NULL))
    return false;
  pieces.push_back(string(s, s + 1));
  s++;
  return true;
  }

Fragments and Equations

• How does equation change?

  class equation {
    private:
      fragments eqn;
    };
  
  equation::equation(const string & str) 
    : eqn(fragment_equation(str)) { }
  
  equation::equation(ostream & os) {
    copy(eqn.start(), eqn.end(), ostream_iter(os, " "));
    os << "\n";
    }
  

• Fragmenting code has nothing to do with the equation class.

  • Separate concerns and keep them separate.

• Also, we still have working code.

Can We Simplify Yet?

• No - we need big numbers.

• What do they look like?

  Who cares? Just make some decisions and hide them.

  class bignum {
  
    public:
  
      bignum(const string & str) : val(atoi(str.c_str())) { }
  
      bignum operator + (const bignum & bn)
        { return bignum(val + bn.val); }
  
      bignum operator - (const bignum & bn)
        { return bignum(val - bn.val); }
  
      bignum operator * (const bignum & bn)
        { return bignum(val * bn.val); }
  
      bignum operator / (const bignum & bn)
        { return bignum(val / bn.val); }
  
    private:
  
      bignum(int v) : val(v) { }
      int val;
    };
  

Can We Simplify Now?

• Not yet - the equations don't contain bignums.

• Also, do the equations make simplification convenient?

  • Not really - accounting for precedence and associativity is hard.

  • Relating one variable to others is hard.

  • Given ...x + y * z...,

    • How to get rid of y?

    • What's the result look like?

• What's a better representation?

  • That depends on how the equations are going to be used.

  • Uh oh, the designer's deadlock.

    • To design the data structure, I need the code.

    • To design the code, I need the data structure.

  • Breaking the designer's deadlock.

    • Design the code using wishful thinking.

    • Design the data structures using bottom-up design.

Bottom-Up Expression Design

• What is an equation? What does the problem say?

  • Two expressions separated by an equals sign.

• What is an equation? What does the problem say?

  • A variable, a number, or two expressions separated by an operator.

• A little playing around suggests a binary tree.

  • The leaves are variables or numbers.

  • Internal nodes are operators, the children operands.

    

  • Precedence and associativity are represented implicitly.

  • Traversal is easy.

Other Equation Designs

• Postfix representation.

  
  void convertToPostfix(string infix, string & postfix) {
  
     Stack S;
     int infixIndex = 0;
  
     S.Push('(');
     infix += ")";
  
     while ( ! S.isEmpty() ) {
        if ( isspace(infix[infixIndex]) ) {
           infixIndex++;
           continue;
        }
  
        if ( isdigit(infix[infixIndex]) )
           postfix += infix[infixIndex++];
        else
           if ( infix[infixIndex] == '(')
              S.Push(infix[infixIndex++]);
           else
              if ( isOperator(infix[infixIndex]) )
              {
                 while ( ! S.isEmpty() && isOperator(S.Top() ) &&
                         precedence(S.Top(), infix[infixIndex]) >= 0 )
                    postfix += S.Pop();p
                 S.Push(infix[infixIndex++]);
              }
              else if ( infix[infixIndex] == ')' ) {
                 while ( S.Top() != '(' )
                    postfix += S.Pop();
                 S.Push(infix[infixIndex++]);
              }
              else if ( infix[infixIndex] == ')' ) {
                 while ( S.Top() != '(' )
                    postfix += S.Pop();
                 infixIndex++ ;
                 char temp = S.Pop();
              }
     }
  }
  

• Document your code.

  • What's going on here?

  • What's with those parentheses?

  • This is not a game of 20-Questions.

The Expression Class

class expression {

  public:

    enum type {
      number,
      variable,
      operation
      };

    expression(const tkns_citer & s, const tkns_citer & e);
    expression(const expression &);

   ~expression();
    expression & operator = (const expression &);

    void write(ostream &) const;

  private:

    type expr_t;

    string prep;

    bignum val;

    expression * left;
    expression * right;

  };

Expression Code

• Remember, trees are recursive.

  void expression::write(ostream & os) const {
  
    if (expr_t == operation) {
      left->write(os);
      os << " " << prep << " ";
      right->write(os);
      }
    else if (expr_t == number)
      val.write(os);
    else {
      assert(expr_t == name);
      os << prep;
      }
    }
  

• The other functions have a similar structure.

Expressions and Equations

• How does equation change?

  class equation {
    private:
      expression lhs, rhs;
    };
  
  equation::equation(const string & str) {
  
    fragments tkns = fragment(str);
  
    tkns_citer gets = std::find_if(tkns.begin(), tkns.end(), is_gets);
    assert((gets != tkns.begin()) && (gets != tkns.end()));
  
    lhs = expression(tkns.begin(), gets);
    gets++;
    rhs = expression(gets, tkns.end());
    }
  
  
  void equation::write(ostream & os) {
    lhs.write(os);
    os << " = ";
    rhs.write(os);
    }
  

• Expressions don't change, neither do equation-sets.

  • Separate concerns and keep them separate.

• Also, we still have working code.

A Recap

• There are 11 files.

  $ wc -l *[ch]
       50 bignum.cc
       53 bignum.h
       47 equation-set.cc
       44 equation-set.h
       85 equation.cc
       59 equation.h
      114 expression.cc
       69 expression.h
      115 fragment.cc
       20 fragment.h
       12 main.cc
      698 total
  
  $ 
  

• fragment.cc is the biggest; let's take a look.

    is_not_digit    Lines        6
    is_not_space    Lines        6
    skip_space      Lines        9
    fragment_char   Lines       15
    fragment_number Lines       17
    fragment_var    Lines       10
    fragment_value  Lines        5
    fragment_expr   Lines        7
    fragment        Lines       12
  

• expression.cc's big too.

    is_muldiv               Lines        3
    is_addsub               Lines        3
    expression::expression  Lines       32
    expression::expression  Lines       14
    expression::~expression Lines        4
    expression::operator =  Lines       14
    expression::write       Lines       13
  

Looking at Expressions::expressions

expression::expression(
  const tkns_citer & s, const tkns_citer & e) {

  tkns_citer op = std::find_if(s, e, is_muldiv);
  if (op == e)
    op = std::find_if(s, e, is_addsub);

  if (op == e) {
    assert(s->size() > 0);
    assert(s + 1 == e);

    if (isdigit((*s)[0])) {
      expr_t = number;
      val = bignum(s->c_str());
      }
    else {
      assert(isalpha((*s)[0]));
      expr_t = variable;
      }

    prep = *s;
    left = right = 0;
    }

  else {
    expr_t = operation;
    prep = *op;
    left = new expression(s, op);
    op++;
    right = new expression(op, e);
    }
  }

• A little big, a little tricky.

• Note the recursion.

• Also note the isalpha((*s)[0]).

Can We Simplify Now?

• Yes. But how?

• What does the problem say?

  • No more possible operations.

• When are operations possible?

  • When the operands are numbers or known variables.

• When are variables known?

  • When equated with a number: x = 100.

• So?

  • Constant fold an operation on numbers.

  • Substitute known variables for numbers.

• For example, given

  x = 100
  y = x + 3
  

  substitute for x

  x = 100
  y = 100 + 3
  

  and constant fold to get

  x = 100
  y = 103
  

Constant Folding Expressions

• The equation class needs to support constant folding.

  class expression {
    public:
      bool fold_constants(void);
    }
  
  bool expression::fold_constants(void) {
  
    if (expr_t != operation)
      return false;
  
    const bool b1 = left->fold_constants();
    const bool b2 = right->fold_constants();
  
    if ((left->expr_t != number) || (right->expr_t != number))
      return b1 || b2;
  
    expr_t = number;
  
    if (prep == "+")
      val = left->val + right->val;
    else if (prep == "-")
      val = left->val - right->val;
    else if (prep == "*")
      val = left->val*right->val;
    else if (prep == "/")
      val = left->val/right->val;
    else
      assert(!"unknown operation in expression::fold_constant()");
  
    delete left;
    delete right;
    left = right = 0;
  
    return true;
    }
  

Constant Folding Equations

• Why?

  • Only equations know about expressions.

  class equation {
    public:
      bool fold_constants(void);
    }
  
  bool equation::fold_constants(void) {
    const bool b1 = lhs->fold_constants();
    const bool b2 = rhs->fold_constants();
    return b1 || b2;
    }
  

Constant Folding Equation Sets

class equation_set {
  private:
    bool fold_constants(void);
  }

bool equation_set::fold_constants(void) {
  bool b = false;
  for (eset_iter i = equations.begin(); i != equations.end(); i++)
    b = i->fold_constants() || b;
  return b;
  }

void equation_set::simplify(void) {
  fold_constants();
  }

Substituting Known Variables

• This is complicated.

  • Expressions know how to substitute.

  • Equations know when they are simple.

  • Equation sets know which equations are involved.

• Significant function is spread out over several classes.

  • Danger - there is an overwhelming urge to combine classes.

  • Resist it - that way lies madness.

• Separate concerns and keep them separate.

  • Note that separate function is (relatively) simple.

  • The interactions among functions becomes complex.

  • Rigidly control the interactions to control complexity.

Variable Substitution

• In expressions.

  bool expression::simplify(
    const string & var, const bignum & bn) {
  
    if (expr_t == number) 
      return false;
  
    if (expr_t == operation) {
      const bool b1 = left->simplify();
      const bool b2 = right->simplify();
      return b1 || b2;
      }
  
    if (var != prep)
      return false;
  
    expr_t = number
    val = bn
  
    return true;
    }
  

• In equations.

  bool equation::is_known(void) const {
  
    if (lhs.is_type(equation_name) &&
        rhs.is_type(equation::number)) 
      return true;
  
    if ((lhs.type(equation::number) &&
        (rhs.type(equation::name)) {
      equation t = lhs;
      lhs = rhs;
      rhs = t;
      return true;
      }
  
    return false;
    }
  

But, What About Errors?

• Errors and the like cause real problems.

  • They cut across all aspects of the system.

  • They are usually ugly to handle - witness exceptions.

  • Concurrent synchronization is another example.

• Two approaches: hide errors or emphasize them.

  • Both approaches are still global.

  • Hiding is usually less disruptive than emphasis.

  • However, hiding is not always appropriate.

• In this problem,

  • fragment code discovers errors, but

  • equation-set code deals with them.

  • These are the extreme ends of our program design.

This page last modified on 15 November 2001.