19 November 2005

Last time we took a procedural approach to solve the expression problem. This time I will demonstrate an object-oriented approach. As a reminder, we want to model the following forms of expressions,

number Literal
expr + expr Add
expr - expr Subtract
expr * expr Multiply
expr / expr Divide

The most natural thing to do in an object-oriented language is to make each of the above expression forms its own class. First, I will introduce a base class to provide an expression abstraction.

abstract class Expr {
}

Now I will now create a sub-class for each expression.

class Literal: Expr {
  protected double Value;

  public Literal(double value) {
    Value = value;
  }
}

abstract class BinaryExpr: Expr {
  protected Expr Left;
  protected Expr Right;

  public BinaryExpr(Expr left, Expr right) {
    Left = left;
    Right = right;
  }
}

class Add: BinaryExpr {
  public Add(Expr left, Expr right) : base(left, right) { }
}

class Subtract: BinaryExpr {
  public Subtract(Expr left, Expr right) : base(left, right) { }
}

class Multiply: BinaryExpr {
  public Multiply(Expr left, Expr right) : base(left, right) { }
}

class Divide: BinaryExpr {
  public Divide(Expr left, Expr right) : base(left, right) { }
}

I created a base class for the binary expressions which I will take advantage of below.

To evaluate the expression I will add an abstract virtual method, Evaluate(), to Expr.

abstract class Expr {
    public abstract double Evaluate();
}

Then I will override the Evaluate() method for each of the above classes. Evaluating a literal is simply returning the value of the literal so I modified the Literal class to,

class Literal: Expr {
  protected double Value;

  public Literal(double value) {
    Value = value;
  }

  public override double Evaluate() {
    return Value;
  }
}

All binary expressions need to evaluate their left-hand expression and right-hand expression and then perform their operation on the results. To represent this, I overrode Evaluate() to evaluate both Left and Right and then call a newly introduced EvaluateOp() method. I sealed the Evaluate() method because I want descendants to override EvaluateOp() not Evaluate().

abstract class BinaryExpr: Expr {
  protected Expr Left;
  protected Expr Right;

  public BinaryExpr(Expr left, Expr right) {
    Left = left;
    Right = right;
  }

  public sealed override double Evaluate() {
    return EvaluateOp(Left.Evaluate(), Right.Evaluate());
  }

  protected abstract double EvaluateOp(double left, double right);
}

Now I can implemented the concrete descendents of BinaryExpr.

class Add: BinaryExpr {
  public Add(Expr left, Expr right) : base(left, right) { }

  protected override double EvaluateOp(double left, double right) {
    return left + right;
  }
}

class Subtract: BinaryExpr {
  public Subtract(Expr left, Expr right) : base(left, right) { }

  protected override double EvaluateOp(double left, double right) {
    return left - right;
  }
}

class Multiply: BinaryExpr {
  public Multiply(Expr left, Expr right) : base(left, right) { }

  protected override double EvaluateOp(double left, double right) {
    return left * right;
  }
}

class Divide: BinaryExpr {
  public Divide(Expr left, Expr right) : base(left, right) { }

  protected override double EvaluateOp(double left, double right) {
    return left / right;
  }
}

The advantages an object-oriented approach are,

  1. New data types can be added without affecting any of the other data types.
  2. Each data type is encapsulated, only the data type needs to have access the instance variables.
  3. All the operations affecting the instance variables are in one place, the methods of instance variable's class.
  4. New operations can be added as abstract methods. The compiler will then generate an error if an operation is not implemented for one of the leaf classes.
  5. Efficient storage is natural. Adding field to one of the expression types do not affect the others.

To demonstrate how easy it is to add a new data type I will again add support for Power.

expr ^ expr Power

To do this I will add a class to represent the Power expression form. This looks like,

class Power: BinaryExpr {
  public Power(Expr left, Expr right) : base(left, right) { }

  protected override double EvaluateOp(double left, double right) {
    return Math.Pow(left, right);
  }
  }

Note that the Power data type can be added without modifying the other classes.

The disadvantages to an object-oriented approach are,

  1. It is difficult to add new operations because adding an operation requires modifying all the classes.
  2. The logic for each operation is spread over multiple classes and often multiple files. This makes it cumbersome to get a complete picture what the operation does.
  3. It is very difficult to dynamically add operations and can't be done without careful planning.

To demonstrate some of the difficulties of adding a new operation, I will add the Print operation. First I will modify the base Expr class to add an abstract Print() method.

abstract class Expr {
  public abstract double Evaluate();
  public abstract void Print();
}

Now I will override this method in each class similar to the way I did for the Evaluate() method.

class Literal: Expr {
  protected double Value;

  public Literal(double value) {
    Value = value;
  }

  public override double Evaluate() {
    return Value;
  }

  public override void Print() {
    Console.Write(Value);
  }
}

abstract class BinaryExpr: Expr {
  protected Expr Left;
  protected Expr Right;

  public BinaryExpr(Expr left, Expr right) {
    Left = left;
    Right = right;
  }

  public sealed override double Evaluate() {
    return EvaluateOp(Left.Evaluate(), Right.Evaluate());
  }

  protected abstract double EvaluateOp(double left, double right);

  public sealed override void Print() {
    Left.Print();
    PrintOp();
    Right.Print();
  }

  protected abstract void PrintOp();
}

class Add: BinaryExpr {
  public Add(Expr left, Expr right) : base(left, right) { }

  protected override double EvaluateOp(double left, double right) {
    return left + right;
  }

  protected override void PrintOp() {
    Console.Write(" + ");
  }
}

class Subtract: BinaryExpr {
  public Subtract(Expr left, Expr right) : base(left, right) { }

  protected override double EvaluateOp(double left, double right) {
    return left - right;
  }

  protected override void PrintOp() {
    Console.Write(" - ");
  }
}

class Multiply: BinaryExpr {
  public Multiply(Expr left, Expr right) : base(left, right) { }

  protected override double EvaluateOp(double left, double right) {
    return left * right;
  }

  protected override void PrintOp() {
    Console.Write(" * ");
  }
}

class Divide: BinaryExpr {
  public Divide(Expr left, Expr right) : base(left, right) { }

  protected override double EvaluateOp(double left, double right) {
    return left / right;
  }

  protected override void PrintOp() {
    Console.Write(" / ");
  }
}

class Power: BinaryExpr {
  public Power(Expr left, Expr right) : base(left, right) { }

  protected override double EvaluateOp(double left, double right) {
    return Math.Pow(left, right);
  }

  protected override void PrintOp() {
    Console.Write(" ^ ");
  }
}

As you can see, each of the classes needed to be modified to implement Print(). You can also note that the compiler complained until each of the classes implemented the Print() operation. This is because we used an abstract method in the Expr class.

If you compare the procedural approach vs. the object-oriented approach you will notice that they are pretty much opposites. It is easy to add operations in the procedural approach but difficult using an object-oriented approach. Adding data types is difficult using in a procedural approach, but easy in an object-oriented approach. Data needs to be public in procedural, but can be private in object oriented. When deciding which approach to use you need to try an predict what will occur more often, adding new data types or adding new operations. What I will present next are some compromise solutions that balance the advantages and disadvantages.



blog comments powered by Disqus