Keywords: current

Next: 1.10.2 Openness in Data Up: 1.10 The Visitor Pattern Previous: 1.10 The Visitor Pattern

## 1.10.1 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 `ArithExpr`s.

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 `ArithExpr`s, 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 `Environment`s 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 `Sum`s, 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.

Next: 1.10.2 Openness in Data Up: 1.10 The Visitor Pattern Previous: 1.10 The Visitor Pattern