1.12.1 Interpreting Arithmetic Expressions

An ArithExpr is either:

• Const(c)
• Sum(left right),
• Neg( left)

where c is an int and left and right are ArithExprs.

As before, to represent this data type in Java, we employ the composite pattern. We define an abstract class to represent the union of these types, and three concrete subclasses, one for each of the different variants.

/** ArithExpr ::= Const(int) + Sum(ArithExpr, ArithExpr) +  Neg(ArithExpr) */
abstract class ArithExpr {
}

class Const extends ArithExpr {

  private int value;
  Const(int v) { value = v; }

  int getValue() { return value; }
  public String toString() { return Integer.toString(value); }
}

class Sum extends ArithExpr {

  ArithExpr left, right;
  Sum(ArithExpr l, ArithExpr r) { left = l; right = r; }

  ArithExpr getLeft() { return left; }
  ArithExpr getRight() { return right; }
  public String toString() {
    return "(" + left + "+" + right + ")";
  }
}

class Neg extends ArithExpr {

  ArithExpr arg;
  Neg(ArithExpr a) { arg = a; }

  ArithExpr getArg() { return arg; }
  public String toString() {
    return "-" + arg; 
  }
}

Next we need a way to evaluate our expressions. First, let's try defining an eval method that returns a constant for any ArithExpr.

We add the abstract method

abstract int eval();

to the ArithExpr class.

In the Const class, we add a concrete version of the abstract eval method:

  int eval() { return getValue();  }

For the Sum class, we write the corresponding method:

  int eval() {
    return left.eval() + right.eval();
  }

For the Neg class, we write the corresponding method:

  int eval() {
    return -(arg.eval());
  }

Finger Exercise: Enter the composite class hierarchy representing the type ArithExpr including eval in the DrJava Definitions window. Add a product expression class Prod. Define some appropriate examples as static members, and define check and test methods to test your implementation. Save your program in the file ArithExpr.java.

Let us amplify the ArithExpr type by adding variables as a new syntactic category. Writing down our revised data type in a shorthand form, we have

ArithExpr ::= Const(int) + Sum(ArithExpr, ArithExpr) +  
              Neg(ArithExpr) + Var(String)

where the variant Var represents variables. The String field in a Var is the variable's name.

In order to evaluate expressions including variables, we introduce environments, which store collections of bindings. A binding is simply a pair containing a variable name and a value. We will also have to modify eval so that its signature becomes

     int eval(Environment env)

We can implement Environments using functional lists of string-value pairs. The details of the implementation are left as an exercise.

The definition of eval will have to change accordingly for each of the existing concrete subclasses, but only the Var subclass will actually make use of the environment parameter. For example, Sum.eval will become

  int eval(Environment env) {
    return left.eval(env) + right.eval(env)
  }

The parameter env is not used directly in the eval code for Sums, but it is passed to the recursive calls to eval in case there is a Var further down in the expression. It is only in class Var that we need to use the environment parameter to look up the value of a variable:

class Var extends ArithExpr {

  private String name;

  Var(String n) { name = n; }

  public String getName() { return name; }
  public String toString() { return name; }
  int eval(Environment env) { return env.lookup(name); }
}

Here env.lookup(name) fetches the int value associated with name in the environment env (if there is no entry for name, lookup should raise some kind of exception).

Finger Exercise: Load your saved program ArithExpr.java into the DrJava Definitions window. Add the concrete class Var to your composite class hierarchy, and define an Environment class with a method int lookup(String name) as described above. Modify your definitions of eval, check, and test as appropriate to accommodate the new form of data.

Having to pass the environment as a parameter to all of the eval methods, when it is directly used in only one of them, is clumsy. As we shall see, there is a different way to implement expression evaluation that avoids this problem.