Interpreting Arithmetic Expressions

An ArithExpr is either:

• Const(c)
• Sum(left right),
• Prod(left,right), or
• 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 four concrete subclasses, one for each of the different variants.

abstract class ArithExpr {
}

class Const extends ArithExpr {
  /* fields */
  private int value;

  /* constructor */
  Const(int v) { value = v; }

  /* getters */
  int getValue() { return value; }

  /* toString */
  public String toString() { return Integer.toString(value); }
  }
}

class Sum extends ArithExpr {
  /* fields */
  ArithExpr left, right;

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

  /* getters */
  ArithExpr getLeft() { return left; }
  ArithExpr getRight() { return right; }

  /* toString */
  public String toString() {
    // here we have recursive calls to toString,
    // as we would expect in an inductively-defined type
    return "(" + left + "+" + right + ")";
  }
}

The two remaining classes, Prod and Neg, are defined similarly.

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 Const eval();

to the ArithExpr class. We could easily define eval to return an int, but we've chosen to return a Const instead because it buys us a little flexibility later.

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

  Const eval() { return this;  }

But now we encounter a minor problem: to evaluate products and sums, we need to be able to multiply or add two instances of Const. Multiplication and addition are not defined for instances of Const, but they are defined for the int values embedded inside instances of Const. Thus, we can use the accessor getvalue() to retrieve the value of a Const. To the class Prod, we add the method

  Const eval() {
    return new Const((left.eval().getValue()) * (right.eval().getValue()));
  }

The eval methods for Sum and Neg are defined similarly.

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

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

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

This notation is merely shorthand for the follow ing prose. An ArithExpr is either:

• Const(c ),
• Sum(left,right ),
• Prod(left,right) ),
• Neg(left), or
• Var(s)

where c is an int, left and right are ArithExprs, and s is a String.

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

     Const eval(Environment env)

We can implement Environments using functional lists of string-value pairs. The details of the implementation are left as an exercise. (Hint: look back at the departmental directory example.)

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

  Const eval(Environment env) {
    return new Const(left.eval(env).getValue() + right.eval(env).getValue());
  }

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 {
  /* fields */
  private String name;

  /* constructor */
  Var(String n) { name = n; }

  /* accessors */
  public String getName() { return name; }

  /* toString */
  public String toString() { return name; }

  Const eval(Environment env) { return env.lookup(name); }
}

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

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.

Finger Exercise 1.13.1.1 Finish writing the program to evaluate arithmetic expression given in this section.