1.13.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.