12 November 2005

Expressions are difficult to represent because they form a matrix of operations and data types. Languages make it either easy to add new operations but difficult to add data types or easy to add new data types but hard to add new operations. This problem isn't limited to expressions, of course, but it is a very clear and familiar example so I will use it to characterize the more general problem. I will present four ways to approach the problem, each with their particular strengths and weaknesses. For my examples I representing a simple expression language comprising of the following expression forms,

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

Some operations I want to perform on these expressions include evaluating expressions and printing expressions. The operations and the expressions form a matrix of functionality, expression kind by operation,

  Evaluate Print
Literal evaluate literal print literal
Add evaluate add print add
Subtract evaluate subtract print subtract
Multiply evaluate multiply print multiply
Divide evaluate divide print divide

Languages either make it easier to add new columns, that is operations, or add new rows, that is new expression kinds. Procedural and functional languages typically make it easy to add new operations. Object-oriented languages typically make it easier to add new expression kinds represented as new data types.

The first approach I will demonstrate is procedural. I define a data type, Expr, that will hold the operator and the operands.

enum Oper { Add, Subtract, Multiply, Divide, Literal }

class Expr {
  public Oper Oper;
  public Expr Left;
  public Expr Right;
  public double Value;

  public Expr(Oper oper, Expr left, Expr right) { ... }
  public Expr(double value) { ... }

The expression evaluation operation for this data structure looks like,

static double Evaluate(Expr e) {
  switch (e.Oper) {
    case Oper.Add: return Evaluate(e.Left) + Evaluate(e.Right);
    case Oper.Subtract: return Evaluate(e.Left) - Evaluate(e.Right);
    case Oper.Multiply: return Evaluate(e.Left) * Evaluate(e.Right);
    case Oper.Divide: return Evaluate(e.Left) / Evaluate(e.Right);
    case Oper.Literal: return e.Value;
    default: Debug.Fail("Unknown operator"); return 0;

The advantages to a procedural approach are,

  1. It is very simple to add additional operations (such as Evaluate()).
  2. All the logic for an operation is centralized in one place, and often in a single routine.
  3. New operations can be added without having the modify existing operations.
  4. New operations can be also be added dynamically without affecting or needing to recompile existing operations.

To demonstrate some of the advantages of using a procedural approach we will add a print operation. It looks like,

static void Print(Expr e) {
  switch (e.Oper) {
    case Oper.Add: Print(e.Left); Console.Write(" + "); Print(e.Right); break;
    case Oper.Subtract: Print(e.Left); Console.Write(" - "); Print(e.Right); break;
    case Oper.Multiply: Print(e.Left); Console.Write(" * "); Print(e.Right); break;
    case Oper.Divide: Print(e.Left); Console.Write(" / "); Print(e.Right); break;
    case Oper.Literal: Console.Write(e.Value); break;
    default: Debug.Fail("Unknown operator"); break;

Adding the Print operation on the Expr type doesn't require any modifications to Expr or Evaluate().

Some disadvantages to a procedural approach are,

  1. It is difficult to add additional data types (in our example, each data type represents a different operator) because adding a new type affects all operations.
  2. Each operation must account for every data type.
  3. The internal representation of the data type must be accessible to every operation. This makes even minor changes to the data layout have far reaching effects and often leads to difficult to maintain implementations.
  4. It is very difficult, and requires careful planning, to dynamically add data types.
  5. Efficient storage of the data types requires variant record support in the language, as discussed in note 1 below, (which can be simulated though inheritance in object-oriented languages but I don't provide and example of that).

To demonstrate the difficulty of adding a data type, let's add power support.

expr ^ expr Power

This represents the expression xn. To implement this we first we need to modify the enumeration to add Power,

enum Oper { Add, Subtract, Multiply, Divide, Literal, Power }

Next we need to add an additional case statement to Evaluate()'s switch statement,

case Oper.Power: return Math.Pow(left, right);

An finally we need to also add another case statement to Print's switch statement that looks like,

case Oper.Power: Print.(e.Left); Console.Write(" ^ "); Print(e.Right); break;

Note we had to modify both operations and the Oper enumeration. If we had several operations, we would have had to modify most, if not all, of them. Also, note that the compiler didn't help us find any of the places we need to modify since the code was legal after each of the above modifications. If we had made the changes to just Evaluate() for example, the compiler wouldn't have complained, but we would receive a runtime error if we called Print() with an expression tree that contains a Power node.

To learn more about the expression problem and its history, see Kim Bruce's excellent paper, Some Challenging Typing Issues in Object-Oriented Languages. Be warned, it will be a bit of a spoiler for some of what I will cover.

1 - A casual observer will notice that Expr is a bit wasteful in that it allocates room for a value for every node instead of only for literals. It also takes up space for Left and Right for literals. In C#, removing this waste is a bit awkward to express and makes the Evaluate() method more complicated, so I ignored the waste in favor of simplicity.

In C++, this is a bit less awkward, and might look like,

struct Expr {
  Oper            oper;
  union {
    struct {
      Expr   *left;
      Expr   *right;
    double      value;
  Expr(Oper oper, Expr *left, Expr *right) { ... }
  Expr(double value) { ... }

with a very similar evaluation function, but for now we will stick with C#. << back <<

2 - For simplicity, I ignored operator precedence. Later I will present a version of this routine that handles precedence correctly. << back <<

blog comments powered by Disqus