CS 509 - An Instructional Story

Lecture Notes for Advanced Programming II

16 April 2002 - An Instructional Story

Expression Trees

Expressions can be represented as binary trees.
- A convenient, powerful representation.
Three types of nodes.
1. binary operators
2. variables
3. numbers
Clue #1: Three different kinds of the same thing.

Implementing Expression Trees

A straightforward class.

class node {
  public:

    enum node_type {
      var_node,
      num_node,
      op_node
      }


    node(const node &);
   ~node(void);
    node & operator = (const node &);

    bool constant_fold(void);
    void print(ostream &) const;

  private:

    node_type nt;

    node * left, node * right;  // for operators
    big_num val;                // for numbers
    string name                 // for variables and ops
  };

Clue #2 - Type fields in the class.

Expression Node Member

The print member function.

void node::print(ostream & os) const {
  switch (ntype) { 
    case op_node:
      left->print(os);
      os << " " << name << " ";
      right->print(os;
      break;
    case num_node:
      val->print(os);
      break;
    case num_node:
      os << name;
      break;
    default:
      cerr << "Unknown node type in node::print().\n";
      exit(EXIT_FAILURE);
    }
  }

Clue #3 - Type-based switch or if statements.

But What's Wrong With That?

Adding more node types leads to an increasingly more complicated class.
- Mixed together instance variables.
- Every member function has to change for the new type.
Mixing everything together makes the class hard to understand.
- Does each function handle all types?
- Is each type handled by all functions?
- Are you sure?
Hard for client code to deal with individual node types.
- Disables type protection - everything's just a node.
- Explicit type testing is required.
- Node class changes could lead to client code changes.

Subtype Polymorphism - The Parent

class node {
  public:
    virtual ~node() { }
    virtual void print(ostream * os) const { }
    virtual bool constant_fold(void) { return false; }
  };

Note the definitions - virtual functions must be defined.
Note the virtual destructor.

Abstract virtual functions would work too.

class node {
  public:
    virtual ~node() = 0;
    virtual void print(ostream * os) const = 0;
    virtual bool constant_fold(void) = 0;
  };

Abstract virtual functions are usually the better choice.
- No member functions definitions required.
- Combats creeping code sharing (uses-a inheritance).
- Helps keep code consistent.

Subtype Polymorphism - The Children

Recast each node type as a child of the node class.

class num_node : node {
  public: 
    num_node(big_num & bn) : val(bn) { }
    void print(ostream & os) const { val->print(os); }
    bool constant_fold(void) { return true; }
  private:
    big_num val;
  };

class var_node : node {
  public: 
    var_node(string & n) : name(n) { }
    void print(ostream & os) const { os << name; }
    bool constant_fold(void) { return false; }
  private:
    string name;
  };


class op_node : node {
  public: 
    op_node(const string & o, node * l, node * r) 
      : op(o), left(l), right(r) { }

    op_node(const op_node &) { }
   ~op_node(void) { /* Whatever */ }
    op_node & operator = (const op_node & on) { /* whatever */ }

    void print(ostream & os) const { 
      left->print(os);
      os << " " << op << " "
      right->print(os);
      }
    bool constant_fold(void) { /* Whatever */ }
  private:
    const string op;
    node * left, * right;
  };

Subtype Polymorphism and Dynamic Casts

Dynamic casts move down the inheritance hierarchy.
- From parent to child.
Example - commuting operands.
- Commuting only makes sense for op nodes.
- Putting it in node probably isn't a good idea.
- Putting it in the op node makes it different from the other nodes.
- Given a node, explicit testing is needed to comute.
```
void try_commute(node * np) {
  op_node * onp = dymamic_cast<op_node *>(np);
  if (onp)
    onp->commute();
  }
```
- This is a tricky design problem.
Don't get carried away - don't re-implement subtype polymorphism.

Points to Remember

The coolest programmers use subtype polymorphism.
Watch out for code with
- Several related classes mashed into one class.
- Type fields in classes.
- Code with type-based switch or if statements.
It could indicate a missed opportunity for subtype polymorphism.
Dynamic casts let you move down the inheritance hierarchy.
- But don't re-implement subtype polymorphism.
There is still much to learn about subtype polymorphism.
- The visitor pattern.

This page last modified on 22 April 2002.