Keywords: current

Next: 1.11.2 Using Java Exceptions Up: 1.11 Unusual Situations versus Previous: 1.11 Unusual Situations versus

## 1.11.1 A Motivating Example

Recall the visitor class for evaluating arithmetic expressions with variables:

    class evalVisitor implements Visitor {
      Env e;
      Object forConst(Const c) {return c; }
      Object forSum(Sum s) {
        Const l = (Const)(s.left.accept(this));
        Const r = (Const)(s.right.accept(this));
        return new Const(l.value + r.value);
      }
      Object forVar(Var v) { return env.lookup(v.name); }
    }

The casting operations `(Const) ...` in the body of the `forSum` method are required by the Java type checker. The Java type system is too imprecise to determine that the recursive invocations of the visitor in `forSum` will never return any value other than a `Const`. The Java type system simply uses the declared return type for a method as the type of invocation of that method.

You might wonder why the designers of Java adopted such a simple, imprecise type system. Precise type systems have two crippling disadvantages. First, they perform a complex inference process that is difficult to understand. If a programmer makes a type error, it is difficult to determine what program revisions are required to satisfy the type checker. Second, precise type inference is expensive. The time complexity of very precise type checking (depending on the specific algorithm) may grow with the square or cube of program size or worse.

Now let us augment Arithmetic Expressions with a variable binding operator `let`. For example, we might want to evaluate the expression:

    let x = 17 in x + y

in an environment where y is bound to `10` to produce the value `17`. This extension is reflected in the definition for data type `ArithExpr` by adding a `Let` form to the list of variants:

    ArithExpr ::= Const(int)
                | Sum(ArithExpr, ArithExpr)
                | ...
                | Let(Var, ArithExpr, ArithExpr)

Similarly, in the object-oriented implementation of `ArithExpr`, we must add the variant class

    class Let extends ArithExpr {
      Var bindVar;
      ArithExpr bindExpr;
      ArithExpr body;
      ...
      Object accept(Visitor v) { v.forLet(this); }
    }

To define operations for our generalized Arithmetic Expressions using visitors, we need to define a new visitor interface with `for` methods for all of the variants:

    interface Visitor {
      Object forConst(Const c);
      Object forSum(Sum c);
      Object forProd(Prod p);
      Object forVar(Var v);
      Object forLet(Let l);
    }

Since the evaluation of a `Let` form involves extending the environment, let us write the code for manipulating environments:

    class Env {
      abstract Const lookup(String name);
    }

    class Empty extends Env {
      Const lookup(String name) {
        return null;
      }
    }
    class Cons extends Env {
      String firstName;
      Const firstVal;
      Env rest;

      Cons(String name, Const val, Env env) {
        firstName = name;
        firstVal = val;
        rest = env;
      }

      Const lookup(String name) {
        if (name.equals(firstName)) return firstVal;
        else return rest.lookup(name);
      }
    }

To evaluate generalized Arithmetic Expressions, we must define an appropriate concrete class extending `Visitor`:

    class EvalVisitor implements Visitor {
      Env env;
      Object forConst(Const c) { return c; }
      ...
      Object forLet(Let l) {
        Const bv = (Const) l.bindExpr.accept(this);
        return l.body.accept(
          new evalVisitor(new Cons(l.bindingVar.name, bv, env));
      }
    }

Notice the cast to Const in the definition of `bv`. Java requires this cast operation because the declared return type of `accept` is `Object`. But the value we bind to a variable to in a let expression must be a `Const`. What happens if we try to evaluate a `Var` that is not bound in the environment? To explain how Java will behave in a such a situation, we need to discuss Java exceptions in more depth.

Next: 1.11.2 Using Java Exceptions Up: 1.11 Unusual Situations versus Previous: 1.11 Unusual Situations versus