1.6.1 Interpreting Arithmetic Expressions

An ArithExpr is one of

• Const c where c is an int,
• Sum(e1,e2),
• Prod(e1,e2), or
• Neg(e1)

where e1 and e2 are themselves 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 {
  // nothing needed in here
}

class Const extends ArithExpr {
  int value;
  Const(int value) {
    this.value = value;
  }
  public String toString() {
    return Integer.toString(value);
  }
}

class Sum extends ArithExpr {
  ArithExpr e1, e2;
  Sum(ArithExpr e1, ArithExpr e2) {
    this.e1 = e1;
    this.e2 = e2;
  }
  public String toString() {
    // here we have recursive calls to toString,
    // as we would expect in an inductively-defined type
    return "(" + e1 + "+" + e2 + ")";
  }
}

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 field selection .value to retrieve the value of a Const. To the class Prod, we add the method

  Const eval() {
    return new Const((e1.eval().value) * (e2.eval().value));
  }

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 datatype in a shorthand form, we have

ArithExpr ::== Const(int)
             | Sum(ArithExpr,ArithExpr)
             | Prod(ArithExpr,ArithExpr)
             | Neg(ArithExpr)
             | Var(String)
end{verbatim}
where the variant {\tt Var} is for variables and the
{\tt String} in a {\tt Var} is the variable's name.

In order to evaluate expressions with variables, we introduce
{\em environments}, which store collections of {\em bindings},
or name-value pairs. We will also have to modify {\tt eval} so
that its signature becomes

\begin{verbatim}
     Const eval(Environment env)

We can implement Environments using 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(e1.eval(env).value + e2.eval(env).value);
  }

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 {
  String name;
  Var(String n) {
    name = n;
  }
  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.