/* The file defining the AST classes including the visitor interface, except for AST classes that are Token classes 
 * as well. */

/** AST ::= BoolConstant | IntConstant | EmptyConstant | Variable | PrimFun | UnOpApp | BinOpApp | App | Map | If | Let */

/** AST class definitions */

/** The AST type which support a visitor interface */
interface AST {
  public <ResType> ResType accept(ASTVisitor<ResType> v);
}

interface ASTVisitor<ResType> {
  ResType forBoolConstant(BoolConstant b);
  ResType forIntConstant(IntConstant i);
  ResType forEmptyConstant(EmptyConstant n);
  ResType forVariable(Variable v);
  ResType forPrimFun(PrimFun f);
  ResType forUnOpApp(UnOpApp u);
  ResType forBinOpApp(BinOpApp b);
  ResType forApp(App a);
  ResType forMap(Map m);
  ResType forIf(If i);
  ResType forLet(Let l);
  ResType forBlock(Block b);
}

/* The Term interface correspond to AST's that when output as concrete syntax by toString() can be used as terms 
 * in an iterative binary expression without enclosing parentheses. We enclose all binary expressions in parentheses
 * so we do not presume either left or right associativity for infix binary operators. */
/** Term ::= Constant | PrimFun | Variable | UnOpApp |  App */
interface Term extends AST {}

/* NOTE: all Constant objects belong to the types Token and AST; Constant tokens evaluate to themselves.
 * The variant classes (IntConstant, BoolConstant, EmptyConstant) are defined in the file ValuesTokens.java */

/** Constant ::= IntConstant | BoolConstant | EmptyConstant */
interface Constant extends Term {}

/** UnOp ::= UnOpPlus | UnOpMinus | OpTilde */
/** Class representing the unary operator within a UnOppApp. */
abstract class UnOp {
  String name;
  public UnOp(String s) { name = s; }
  public String toString() { return name; }
  public abstract <ResType> ResType accept(UnOpVisitor<ResType> v);
}

/** Visitor for the UnOp union type. */
interface UnOpVisitor<ResType> {
  ResType forUnOpPlus();
  ResType forUnOpMinus();
  ResType forOpTilde();
  ResType forOpBang();
  ResType forOpRef();
}

/** BinOp ::= BinOpPlus | BinOpMinus | OpTimes | OpDivide | OpEquals | OpNotEquals | OpLessThan | OpGreaterThan |
  *           OpLessThanOrEquals OpGreaterThanOrEquals | OpAnd | OpOr */

/** Class representing the binary operator within a BinOppApp. */
abstract class BinOp {
  String name;
  public BinOp(String s) { name = s; }
  public String toString() { return name; }
  public abstract <ResType> ResType accept(BinOpVisitor<ResType> v);
}

/** Visitor for the BinOp union type. */
interface BinOpVisitor<ResType> {
  ResType forBinOpPlus();
  ResType forBinOpMinus();
  ResType forOpTimes();
  ResType forOpDivide();
  ResType forOpEquals();
  ResType forOpNotEquals();
  ResType forOpLessThan();
  ResType forOpGreaterThan();
  ResType forOpLessThanEquals();
  ResType forOpGreaterThanEquals();
  ResType forOpAnd();
  ResType forOpOr();
  ResType forOpGets();
}

class UnOpPlus extends UnOp {
  public static final UnOpPlus ONLY = new UnOpPlus();
  private UnOpPlus() { super("+"); }
  public <ResType> ResType accept(UnOpVisitor<ResType> v) {
    return v.forUnOpPlus(); 
  }
}

class UnOpMinus extends UnOp {
  public static final UnOpMinus ONLY = new UnOpMinus();
  private UnOpMinus() { super("-"); }
  public <ResType> ResType accept(UnOpVisitor<ResType> v) {
    return v.forUnOpMinus(); 
  }
}

class OpTilde extends UnOp {
  public static final OpTilde ONLY = new OpTilde();
  private OpTilde() { super("~"); }
  public <ResType> ResType accept(UnOpVisitor<ResType> v) {
    return v.forOpTilde(); 
  }
}

/** UnOp for dereference operator '!' */
class OpBang extends UnOp {
  public static final OpBang ONLY = new OpBang();
  private OpBang() { super("!"); }
  public <ResType> ResType accept(UnOpVisitor<ResType> v) {
    return v.forOpBang();
  }
}

/** UnOp for ref creation operator 'ref' */
class OpRef extends UnOp {
  public static final OpRef ONLY = new OpRef();
  private OpRef() { super("ref"); }
  public <ResType> ResType accept(UnOpVisitor<ResType> v) {
    return v.forOpRef();
  }
}

class BinOpPlus extends BinOp {
  public static final BinOpPlus ONLY = new BinOpPlus();
  private BinOpPlus() { super("+"); }
  public <ResType> ResType accept(BinOpVisitor<ResType> v) {
    return v.forBinOpPlus(); 
  }
}

class BinOpMinus extends BinOp {
  public static final BinOpMinus ONLY = new BinOpMinus();
  private BinOpMinus() { super("-"); }
  public <ResType> ResType accept(BinOpVisitor<ResType> v) {
    return v.forBinOpMinus(); 
  }
}

class OpTimes extends BinOp {
  public static final OpTimes ONLY = new OpTimes();
  private OpTimes() { super("*"); }
  public <ResType> ResType accept(BinOpVisitor<ResType> v) {
    return v.forOpTimes(); 
  }
}

class OpDivide extends BinOp {
  public static final OpDivide ONLY = new OpDivide();
  private OpDivide() { super("/"); }
  public <ResType> ResType accept(BinOpVisitor<ResType> v) {
    return v.forOpDivide(); 
  }
}

class OpEquals extends BinOp {
  public static final OpEquals ONLY = new OpEquals();
  private OpEquals() { super("="); }
  public <ResType> ResType accept(BinOpVisitor<ResType> v) {
    return v.forOpEquals(); 
  }
}

class OpNotEquals extends BinOp {
  public static final OpNotEquals ONLY = new OpNotEquals();
  private OpNotEquals() { super("!="); }
  public <ResType> ResType accept(BinOpVisitor<ResType> v) {
    return v.forOpNotEquals(); 
  }
}

class OpLessThan extends BinOp {
  public static final OpLessThan ONLY = new OpLessThan();
  private OpLessThan() { super("<"); }
  public <ResType> ResType accept(BinOpVisitor<ResType> v) {
    return v.forOpLessThan(); 
  }
}

class OpGreaterThan extends BinOp {
  public static final OpGreaterThan ONLY = new OpGreaterThan();
  private OpGreaterThan() { super(">"); }
  public <ResType> ResType accept(BinOpVisitor<ResType> v) {
    return v.forOpGreaterThan(); 
  }
}

class OpLessThanEquals extends BinOp {
  public static final OpLessThanEquals ONLY = new OpLessThanEquals();
  private OpLessThanEquals() { super("<="); }
  public <ResType> ResType accept(BinOpVisitor<ResType> v) {
    return v.forOpLessThanEquals(); 
  }
}

class OpGreaterThanEquals extends BinOp {
  public static final OpGreaterThanEquals ONLY = new OpGreaterThanEquals();
  private OpGreaterThanEquals() { super(">="); }
  public <ResType> ResType accept(BinOpVisitor<ResType> v) {
    return v.forOpGreaterThanEquals(); 
  }
}

class OpAnd extends BinOp {
  public static final OpAnd ONLY = new OpAnd();
  private OpAnd() { super("&"); }
  public <ResType> ResType accept(BinOpVisitor<ResType> v) {
    return v.forOpAnd(); 
  }
}

class OpOr extends BinOp {
  public static final OpOr ONLY = new OpOr();
  private OpOr() { super("|"); }
  public <ResType> ResType accept(BinOpVisitor<ResType> v) {
    return v.forOpOr(); 
  }
}

/** BinOp for assignment operator '<-' */
class OpGets extends BinOp {
  public static final OpGets ONLY = new OpGets();
  private OpGets() { super("<-"); }
  public <ResType> ResType accept(BinOpVisitor<ResType> v) {
    return v.forOpGets();
  }
}

/* UnOpApp is a Term because it does not need enclosing parentheses when appearing in a binary expression */
class UnOpApp implements Term {
  private UnOp rator;
  private AST arg;
  
  UnOpApp(UnOp r, AST a) { rator = r; arg = a; }
  
  public UnOp rator() { return rator; }
  public AST arg() { return arg; }
  public <ResType> ResType accept(ASTVisitor<ResType> v) { return v.forUnOpApp(this); }
  public String toString() { return rator + " " + arg; }
}

class BinOpApp implements Term {
  private BinOp rator;
  private AST arg1, arg2;
  
  BinOpApp(BinOp r, AST a1, AST a2) { rator = r; arg1 = a1; arg2 = a2; }
  
  public BinOp rator() { return rator; }
  public AST arg1() { return arg1; }
  public AST arg2() { return arg2; }
  public <ResType> ResType accept(ASTVisitor<ResType> v) { return v.forBinOpApp(this); }
  public String toString() {
    return "(" + toString(arg1) + " " + rator + " " + toString(arg2) + ")"; 
  }
  private String toString(AST arg) {
    String argString = arg.toString();
    if (! (arg instanceof Term)) return "(" + argString + ")";

... (truncated 4685 chars)

/** Nine different interpreters for Jam that differ in binding policy and cons evaluation policy.
  * The binding policy is either: call-by-value, call-by-name, or call-by-need.
  * The cons evaluation policy is either: call-by-value (eager), call-by-name (redundant lazy), or
  * call-by-need (efficient lazy).
  */

import java.io.IOException;
import java.io.Reader;
import java.util.HashMap;


/** The exception class for Jam run-time errors during program evaluation. */
class EvalException extends RuntimeException {
  EvalException(String msg) { super(msg); }
}

/** The exception class for type checking errors in Typed Jam. */
class TypeException extends RuntimeException {
  TypeException(String msg) { super(msg); }
}

/** Interpreter class supporting nine forms of evaluation for Jam programs.  These forms of evaluation differ in
  * binding policy and cons evaluation policy.
  * The binding policy is either: call-by-value, call-by-name, or call-by-need.
  * The cons evaluation policy is either: call-by-value (eager), call-by-name (redundant lazy), or
  * call-by-need (efficient lazy). */
class Interpreter {
  /** Parser to use. */
  Parser parser;  // initialized in constructors
  
  /** Parsed AST. */
  AST prog;       // initialized in constructors
  
  Interpreter(String fileName) throws IOException {
    parser = new Parser(fileName);
    prog = parser.parseAndCheck();
  }
  
  Interpreter(Parser p) {
    parser = p;
    prog = parser.parseAndCheck();
  }
  
  Interpreter(Reader reader) {
    parser = new Parser(reader);
    prog = parser.parseAndCheck();
  }
  
  /* Interpreter API: the public methods of this Jam Interpreter */
  
  /** Parses and ValueValue interprets the input embeded in parser, returning the result. */
  public JamVal callByValue() { return prog.accept(valueValueVisitor); }
  
  /** Parses and NameValue interprets the input embeded in parser, returning the result. */
  public JamVal callByName() { return prog.accept(nameValueVisitor); }
  
  /** Parses and NeedValue interprets the input embeded in parser, returning the result. */
  public JamVal callByNeed() { return prog.accept(needValueVisitor); }
  
  /** Parses and ValueValue interprets the input embeded in parser, returning the result. */
  public JamVal valueValue() { return prog.accept(valueValueVisitor); }
  
  /** Parses and ValueName interprets the input embeded in parser, returning the result. */
  public JamVal valueName() { return prog.accept(valueNameVisitor); }
  
  /** Parses and ValueNeed interprets the input embeded in parser, returning the result. */
  public JamVal valueNeed() {return prog.accept(valueNeedVisitor); }
  
  /** Parses and NameValue interprets the input embeded in parser, returning the result.  */
  public JamVal nameValue() { return prog.accept(nameValueVisitor); }
  
  /** Parses and NameName interprets the input embeded in parser, returning the result. */
  public JamVal nameName() { return prog.accept(nameNameVisitor); }
  
  /** Parses and NameNeed interprets the input embeded in parser, returning the result. */
  public JamVal nameNeed() { return prog.accept(nameNeedVisitor); }
  
  /** Parses and NeedValue interprets the input embeded in parser, returning the result. */
  public JamVal needValue() { return prog.accept(needValueVisitor); }
  
  /** Parses and NeedName interprets the input embeded in parser, returning the result. */
  public JamVal needName() { return prog.accept(needNameVisitor); }
  
  /** Parses and NeedNeed interprets the input embeded in parser, returning the result. */
  public JamVal needNeed() { return prog.accept(needNeedVisitor); }

  /** Parses, type checks, and eagerly evaluates (call-by-value/eager) the input. */
  public JamVal eagerEval() {
    AST checked = checkTypes(prog);
    return checked.accept(valueValueVisitor);
  }

  /** Parses, type checks, and lazily evaluates (call-by-value/lazy) the input. */
  public JamVal lazyEval() {
    AST checked = checkTypes(prog);
    return checked.accept(valueNeedVisitor);
  }

  /** Type checks the given AST and returns it if it's well-typed.
    * Throws TypeException if type checking fails. */
  public AST checkTypes(AST ast) {
    new TypeCheckVisitor().checkExp(ast, new java.util.HashMap<String, Type>());
    return ast;
  }

  /* Interfaces that support different forms of variable binding and different forms of list construction */
  
  /** The interface supported by various binding evaluation policies: call-by-value, call-by-name, and call-by-need. */
  interface BindingPolicy {  // formerly called EvalPolicy
    
    /** Constructs the appropriate binding object for this, binding var to ast in the evaluator ev. */
    Binding newBinding(Variable var, AST ast, EvalVisitor ev);
    
    /** Constructs the appropriate dummy binding object for this. */
    Binding newDummyBinding(Variable var);
  }
  
  /** Interface containing a factory to build the cons object specified by this ConsPolicy. */
  interface ConsPolicy {
    /** Constructs the appropriate cons given the arguments and corresponding EvalVisitor. */
    JamVal evalCons(AST[] args, EvalVisitor ev);
  }
  
  /* Note: Binding is defined in the file ValuesTokens because the JamClosure class depends on it. */
  
  /** Class representing a binding in CBV evaluation. */ 
  static class ValueBinding extends Binding {
    ValueBinding(Variable v, JamVal jv) { super(v, jv); }
    public JamVal value() { 
      if (value == null) illegalForwardReference(var());
      return value; 
    }
    public void setBinding(Suspension s) { value = s.eval(); }  // immediate evaluation
    public String toString() { return "[" + var + ", " + value + "]"; }
  }
  
  /** Class representing a binding in CBName evaluation. The inherited value field is ignored. */
  static class NameBinding extends Binding {
    protected Suspension susp;
    NameBinding(Variable v, Suspension s) { 
      super(v,null);
      susp = s;
    }
    public JamVal value() { return (susp == null) ? illegalForwardReference(var()) : susp.eval(); }
    public void setBinding(Suspension s) { susp = s; }
    public String toString() { return "[" + var + ", " + susp + "]"; }
  }
  
  /** Class representing a binding in CBNeed evaluation.  The inherited value field is used to hold the value
    * first computed by need .. */
  static class NeedBinding extends NameBinding {
    NeedBinding(Variable v, Suspension s) { super(v,s); }
    public JamVal value() {
      if (value == null) {  // a legitimate JamVal CANNOT be null
        if (susp == null) illegalForwardReference(var());
        else {             // Force the suspension and cache its value
          value = susp.eval();
          susp = null;     // release susp object for GC!
        }
      }
      return value;
    }
    public void setBinding(AST exp, EvalVisitor ev) { susp = new ConcreteSuspension(exp, ev); value = null; }
    public String toString() { return "[" + var + ", " + value + ", " + susp + "]"; }
  }
  
  /** Helper method supporting Binding classes */
  static JamVal illegalForwardReference(Variable v) {
    throw new EvalException("Attempt to evaluate variable " + v + " bound to null, indicating an illegal forward reference");
  }
  
  /** Binding policy for call-by-value. */
  static final BindingPolicy CALL_BY_VALUE = new BindingPolicy() {
    public Binding newBinding(Variable var, AST arg, EvalVisitor ev) { return new ValueBinding(var, arg.accept(ev)); }
    public Binding newDummyBinding(Variable var) { return new ValueBinding(var, null); } // null indicates still unbound
  };
  
  /** Binding policy for call-by-name. */
  static final BindingPolicy CALL_BY_NAME = new BindingPolicy() {
    public Binding newBinding(Variable var, AST arg, EvalVisitor ev) {
      return new NameBinding(var, new ConcreteSuspension(arg, ev));
    }
    public Binding newDummyBinding(Variable var) { return new NameBinding(var, null); } // null indicates still unbound
  };
  
  /** Binding policy for call-by-need. */
  static final BindingPolicy CALL_BY_NEED = new BindingPolicy() {
    public Binding newBinding(Variable var, AST arg, EvalVisitor ev) {
      return new NeedBinding(var, new ConcreteSuspension(arg, ev));
    }
    public Binding newDummyBinding(Variable var) { return new NeedBinding(var, null); } // null indicates still unbound
  };
  
  
  /** A class representing an unevaluated expresssion (together with the corresponding evaluator). */
  static class ConcreteSuspension implements Suspension {
    private AST exp;
    private EvalVisitor ev;  
    
    ConcreteSuspension(AST a, EvalVisitor e) { exp = a; ev = e; }
    
    AST exp() { return exp; }
    EvalVisitor ev() { return ev; }
    void putEv(EvalVisitor e) { ev = e; }
    
    /** Evaluates this suspension. Only method in Suspension interface */
    public JamVal eval() { 
      // System.err.println("eval() called on the susp with AST = " + exp);
      return exp.accept(ev);
    } 
    
    public String toString() { return "<" + exp + ", " + ev + ">"; }
  }
  
  /** Class for a lazy cons structure. */
  static class JamLazyNameCons extends JamCons {
    /** Suspension for first */
    protected Suspension firstSusp;
    
    /** Suspension for rest */
    protected Suspension restSusp;
    
    public JamLazyNameCons(AST f, AST r, EvalVisitor ev) {
      super(null, null);
      firstSusp = new ConcreteSuspension(f, ev);
      restSusp = new ConcreteSuspension(r, ev);
    }
    
    public JamVal first() { return firstSusp.eval(); }
    public JamList rest() { return checkList(restSusp.eval()); }
  }
  
  /** Class for a lazy cons with optimization. */
  static class JamLazyNeedCons extends JamLazyNameCons {
    
    public JamLazyNeedCons(AST f, AST r, EvalVisitor ev) { super(f, r, ev); }
    
    public JamVal first() {
      if (first == null) {
        first = firstSusp.eval();
        firstSusp = null;
      }
      return first;
    }
    
    public JamList rest() {
      if (rest == null) {
        rest = checkList(restSusp.eval());
        restSusp = null;
      }
      return (JamList)rest;
    }
  }
  
  /** Eager cons evaluation policy. Presumes that args has exactly 2 elements. */
  public static final ConsPolicy EAGER = new ConsPolicy() {
    public JamVal evalCons(AST[] args, EvalVisitor ev) {
      JamVal val0 = args[0].accept(ev);
      JamVal val1 = args[1].accept(ev);
      if (val1 instanceof JamList) {
        return new JamCons(val0, (JamList)val1);
      }
      throw new EvalException("Second argument " + val1 + " to `cons' is not a JamList");
    }
  };
  
  /** Call-by-name lazy cons evaluation policy.  Presumes that args has exactly 2 elements. */
  public static final ConsPolicy LAZYNAME = new ConsPolicy() {
    public JamVal evalCons(AST[] args, EvalVisitor ev) { return new JamLazyNameCons(args[0], args[1], ev); }
  };
  
  /** Call-by-need lazy cons evaluation policy.  Presumes that args has exactly 2 elements. */
  public static final ConsPolicy LAZYNEED = new ConsPolicy() {
    public JamVal evalCons(AST[] args, EvalVisitor ev) { return new JamLazyNeedCons(args[0], args[1], ev); }
  };
  
  /** Value-value visitor. */
  static final ASTVisitor<JamVal> valueValueVisitor = new EvalVisitor(CALL_BY_VALUE, EAGER);
  
  /** Value-name visitor. */
  static final ASTVisitor<JamVal> valueNameVisitor = new EvalVisitor(CALL_BY_VALUE, LAZYNAME);
  
  /** Value-need visitor. */
  static final ASTVisitor<JamVal> valueNeedVisitor = new EvalVisitor(CALL_BY_VALUE, LAZYNEED);
  
  /** Name-value visitor. */
  static final ASTVisitor<JamVal> nameValueVisitor = new EvalVisitor(CALL_BY_NAME, EAGER);
  
  /** Name-name visitor. */
  static final ASTVisitor<JamVal> nameNameVisitor = new EvalVisitor(CALL_BY_NAME, LAZYNAME);
  
  /** Name-need visitor. */
  static final ASTVisitor<JamVal> nameNeedVisitor = new EvalVisitor(CALL_BY_NAME, LAZYNEED);
  
  /** Need-value visitor. */
  static final ASTVisitor<JamVal> needValueVisitor = new EvalVisitor(CALL_BY_NEED, EAGER);
  
  /** Need-name visitor. */
  static final ASTVisitor<JamVal> needNameVisitor = new EvalVisitor(CALL_BY_NEED, LAZYNAME);
  
  /** Need-need visitor. */
  static final ASTVisitor<JamVal> needNeedVisitor = new EvalVisitor(CALL_BY_NEED, LAZYNEED);
  
  
  /** Primary visitor class for performing interpretation. */
  static class EvalVisitor implements ASTVisitor<JamVal> {
    
    /* Assumes that:
     *   OpTokens are unique
     *   Variable objects are unique: v1.name.equals(v.name) => v1 == v2
     *   Only objects used as boolean values are BoolConstant.TRUE and BoolConstant.FALSE
     * Hence, == can be used to compare Variable objects, OpTokens, and BoolConstants
     */
    
    /** Environment. */
    PureList<Binding> env;
    
    /** Policy to create bindings. */
    BindingPolicy bindingPolicy;
    
    /** Policy to create cons. */
    ConsPolicy consPolicy;
    
    private EvalVisitor(PureList<Binding> e, BindingPolicy bp, ConsPolicy cp) {
      env = e;
      bindingPolicy = bp;
      consPolicy = cp;
    }
    
    public EvalVisitor(BindingPolicy bp, ConsPolicy cp) { this(new Empty<Binding>(), bp, cp); }
    
    /* EvalVisitor methods */
    
    /** Factory method that constructs a visitor similar to this with environment env. */
    public EvalVisitor newEvalVisitor(PureList<Binding> env) {
      return new EvalVisitor(env, bindingPolicy, consPolicy);
    }
    
    /** Getter for env field. */
    public PureList<Binding> env() { return env; }
    
    /* methods of ASTVisitor<JamVal> interface */
    
    public JamVal forBoolConstant(BoolConstant b) { return b; }
    public JamVal forIntConstant(IntConstant i) { return i; }
    public JamVal forEmptyConstant(EmptyConstant n) { return JamEmpty.ONLY; }
    
    public JamVal forVariable(Variable v) {
      Binding match = env.accept(new LookupVisitor<Binding>(v));
      if (match == null) {
        throw new EvalException("variable " + v + " is unbound");
      }
      return match.value();
    }
    
    public JamVal forPrimFun(PrimFun f) { return f; }
    public JamVal forUnOpApp(UnOpApp u) { return u.rator().accept(new UnOpEvaluator(u.arg().accept(this))); }
    public JamVal forBinOpApp(BinOpApp b) { return b.rator().accept(new BinOpEvaluator(b.arg1(), b.arg2())); }
    
    public JamVal forApp(App a) {
      JamVal rator = a.rator().accept(this);
      if (rator instanceof JamFun) 
        return ((JamFun)rator).accept(new FunEvaluator(a.args()));
      throw new EvalException(rator + " appears at head of application " + a + " but it is not a valid function");
    }
    
    public JamVal forMap(Map m) { return new JamClosure(m, env); }
    
    public JamVal forIf(If i) {
      JamVal test = i.test().accept(this);
      if (!(test instanceof BoolConstant))  throw new EvalException("non Boolean " + test + " used as test in if");
      if (test == BoolConstant.TRUE)  return i.conseq().accept(this);
      return i.alt().accept(this);
    }
    
    /** Evaluates a block expression by evaluating all expressions in sequence and returning the last value.
      * Blocks must contain at least one expression (enforced by parser). */
    public JamVal forBlock(Block b) {
      AST[] exps = b.exps();
      int n = exps.length;
      if (n == 0) throw new EvalException("Block must contain at least one expression");
      JamVal result = null;
      for (int i = 0; i < n; i++) {
        result = exps[i].accept(this);
      }
      return result;
    }

    /* Recursive let semantics */
    public JamVal forLet(Let l) {
      
      /* Extract binding vars and exps (rhs's) from l */
      Variable[] vars = l.vars();
      AST[] exps = l.exps();
      int n = vars.length;
      
      /* Construct newEnv with dummy bindings for each variable in vars. */
      PureList<Binding> newEnv = env();
      Binding[] bindings = new Binding[n];
      for(int i = 0; i < n; i++) {
        bindings[i] = bindingPolicy.newDummyBinding(vars[i]);  // create appropriate form of dummy binding for var[i]
        newEnv = newEnv.cons(bindings[i]);                     // add new Binding to newEnv; it is shared so it can be updated
      }
      /* create new EvalVisitor instance with new environment (with dummy bindings for vars). */
      EvalVisitor newEV = newEvalVisitor(newEnv); 
      
      /* Fix up the dummy bindings in newEnv using exps as specified by binding policy using newEV (containing newEnv) */
      for(int i = 0; i < n; i++) {
        bindings[i].setBinding(new ConcreteSuspension(exps[i], newEV));  // modifies newEnv and hence newEV
      }
      return l.body().accept(newEV);
    }
    
    /* Inner classes */
    
    /** Evaluates the application of a function to an array of argument ASTs. A true inner class that accesses the enclosing 
      * EvalVisitor instance. The applied function may be a JamClosure or a PrimFun. */
    class FunEvaluator implements JamFunVisitor<JamVal> {
      /** Unevaluated arguments */
      AST[] args;
      
      FunEvaluator(AST[] asts) { args = asts; }
      
      /** The anonymous inner class that evaluates PrimFun applications.  The evaluation of arguments must be deferred
        * in the evaluation of lazy cons. As a result, the evalArgs() method is called in all of the forXXXX methods
        * except forCons.  Note: this anonymous inner class replaces the named static inner class StandardPrimFunVisior
        * in the solution to Assignment 2.   This revision was motivated by the fact that an anonymous inner class can 
        * access variables in the enclosing instance while a static inner instance class cannot.  This restriction is
        * very annoying when the static inner class is itself nested inside a true inner class; it cannot see the same
        * context as the inner class in which it is nested!
        * The evaluation of cons is special because it defers evaluating its arguments in the context of lazy 
        * evaluation. */
      
      PrimFunVisitor<JamVal> primEvaluator = new PrimFunVisitor<JamVal>() {
        
        /** Deferred evaluation of the args using the enclosing EvalVisitor. */
        private JamVal[] evalArgs() {
          int n = args.length;
          JamVal[] vals = new JamVal[n];
          for(int i = 0; i < n; i++) {
            vals[i] = args[i].accept(EvalVisitor.this);
          }
          return vals;
        }
        
        /** Throws an error.*/
        private void primFunError(String fn) {
          throw new EvalException("Primitive function `" + fn + "' applied to " + args.length + " arguments");
        }
        
        /** Evaluates an argument that has to be a Jam cons. */
        private JamCons evalJamConsArg(AST arg, String fun) {
          JamVal val = arg.accept(EvalVisitor.this);
          if (val instanceof JamCons) {
            return (JamCons)val;
          }
          throw new
            EvalException("Primitive function `" + fun + "' applied to argument " + val + " that is not a JamCons");
        }
        
        /* Visitor methods. */
        public JamVal forFunctionPPrim() {
          JamVal[] vals = evalArgs();
          if (vals.length != 1) primFunError("function?");
          return BoolConstant.toBoolConstant(vals[0] instanceof JamFun);
        }
        
        public JamVal forNumberPPrim() {
          JamVal[] vals = evalArgs();
          if (vals.length != 1) primFunError("number?");
          return BoolConstant.toBoolConstant(vals[0] instanceof IntConstant);
        }
        
        public JamVal forListPPrim() {
          JamVal[] vals = evalArgs();
          if (vals.length != 1) primFunError("list?");
          return BoolConstant.toBoolConstant(vals[0] instanceof JamList);
        }
        
        public JamVal forConsPPrim() {
          JamVal[] vals = evalArgs();
          if (vals.length != 1) primFunError("cons?");
          return BoolConstant.toBoolConstant(vals[0] instanceof JamCons);
        }
        
        public JamVal forEmptyPPrim() {
          JamVal[] vals = evalArgs();
          if (vals.length != 1) primFunError("null?");
          return BoolConstant.toBoolConstant(vals[0] instanceof JamEmpty);
        }

        public JamVal forRefPPrim() {
          JamVal[] vals = evalArgs();
          if (vals.length != 1) primFunError("ref?");
          return BoolConstant.toBoolConstant(vals[0] instanceof JamRef);
        }

        public JamVal forConsPrim() {
          if (args.length != 2) primFunError("cons");
          return consPolicy.evalCons(args, EvalVisitor.this);   // Evaluation of args determined by consPolicy
        }
        
        public JamVal forArityPrim() {
          JamVal[] vals = evalArgs();
          if (vals.length != 1) primFunError("arity");
          if (!(vals[0] instanceof JamFun))  throw new EvalException("arity applied to argument " +  vals[0]);
          
          return ((JamFun)vals[0]).accept(new JamFunVisitor<IntConstant>() {
            public IntConstant forJamClosure(JamClosure jc) { return new IntConstant(jc.code().vars().length); }
            public IntConstant forPrimFun(PrimFun jpf) { return new IntConstant(jpf instanceof ConsPrim ? 2 : 1); }
          });
        }
        
        public JamVal forFirstPrim() { 
          if (args.length != 1) primFunError("first");
          return evalJamConsArg(args[0], "first").first(); 
        }
        public JamVal forRestPrim() { 
          if (args.length != 1) primFunError("rest");
          return evalJamConsArg(args[0], "rest").rest(); 
        }
      };  // end of anonymous inner class primFunEvaluator
      
      /* Support for JamFunVisitor<JamVal> interface */
      
      /* Evaluates the closure application. */
      public JamVal forJamClosure(JamClosure closure) {
        Map map = closure.code();
        int n = args.length;
        Variable[] vars = map.vars();
        if (vars.length != n) {
          throw new EvalException("closure " + closure + " applied to " + n + " arguments");
        }
        /* Construct newEnv for JamClosure code using JamClosure env. */
        PureList<Binding> newEnv = closure.env();
        for(int i = 0; i < n; i++) {
          newEnv = newEnv.cons(bindingPolicy.newBinding(vars[i], args[i], EvalVisitor.this));
        }
        return map.body().accept(newEvalVisitor(newEnv));
      }
      
      /* Evaluates the primFun application.  The arguments cannot be evaluated yet because cons may be lazy. */
      public JamVal forPrimFun(PrimFun primFun) { return primFun.accept(primEvaluator); }
    }
    
    /** Evaluator for unary operators. Operand is already value (JamVal). */
    static class UnOpEvaluator implements UnOpVisitor<JamVal> {
      /** Value of the operand. */
      private JamVal val;
      
      UnOpEvaluator(JamVal jv) { val = jv; }
      
      /** Returns the value of the operand if it is an IntConstant; otherwise throws an exception. */
      private IntConstant checkInteger(String op) {
        if (val instanceof IntConstant)  return (IntConstant)val;
        throw new EvalException("Unary operator `" + op + "' applied to non-integer " + val);
      }
      
      /** Returns the value of the operand if it is a BoolConstant; otherwise throws an exception. */
      private BoolConstant checkBoolean(String op) {
        if (val instanceof BoolConstant)  return (BoolConstant)val;
        throw new EvalException("Unary operator `" + op + "' applied to non-boolean " + val);
      }
      
      /** Returns the value of the operand if it is a JamRef; otherwise throws an exception. */
      private JamRef checkRef(String op) {
        if (val instanceof JamRef) return (JamRef) val;
        throw new EvalException("Unary operator `" + op + "' applied to non-ref " + val);
      }

      /* Visitor methods in UnOpVisitor<JamVal> interface */
      public JamVal forUnOpPlus() { return checkInteger("+"); }
      public JamVal forUnOpMinus() { return new IntConstant(-checkInteger("-").value()); }
      public JamVal forOpTilde() { return checkBoolean("~").not(); }
      public JamVal forOpBang() { return checkRef("!").value(); }
      public JamVal forOpRef() { return new JamRef(val); }
    }
    
    /** Evaluator for binary operators. A true inner class that references the enclosing EvalVisior. */
    class BinOpEvaluator implements BinOpVisitor<JamVal> {
      /** Unevaluated arguments. */
      private AST arg1, arg2;
      
      BinOpEvaluator(AST a1, AST a2) {
        arg1 = a1;
        arg2 = a2;
      }
      
      /** Returns the value of arg if it is an IntConstant; otherwise throw an exception, */
      private IntConstant evalIntegerArg(AST arg, String b) {
        JamVal val = arg.accept(EvalVisitor.this);
        if (val instanceof IntConstant)  return (IntConstant)val;
        throw new EvalException("Binary operator `" + b + "' applied to non-integer " + val);
      }
      
      /** Returns the value of the argument if it is a BoolConstant, otherwise throw an exception, */
      private BoolConstant evalBooleanArg(AST arg, String b) {
        JamVal val = arg.accept(EvalVisitor.this);
        if (val instanceof BoolConstant)  return (BoolConstant)val;
        throw new EvalException("Binary operator `" + b + "' applied to non-boolean " + val);
      }
      
      /* Visitor methods */
      public JamVal forBinOpPlus() {
        return new IntConstant(evalIntegerArg(arg1,"+").value() + evalIntegerArg(arg2, "+").value());
      }
      
      public JamVal forBinOpMinus() {
        return new IntConstant(evalIntegerArg(arg1,"-").value() - evalIntegerArg(arg2, "-").value());
      }
      
      public JamVal forOpTimes() {
        return new IntConstant(evalIntegerArg(arg1,"*").value() * evalIntegerArg(arg2, "*").value());
      }
      
      public JamVal forOpDivide() {
        int divisor = evalIntegerArg(arg2, "/").value();
        if (divisor == 0) {
          throw new EvalException("Attempt to divide by zero");
        }
        return new IntConstant(evalIntegerArg(arg1,"/").value() / divisor);
      }
      
      public JamVal forOpEquals() {
        return BoolConstant.toBoolConstant(arg1.accept(EvalVisitor.this).equals(arg2.accept(EvalVisitor.this)));
      }
      
      public JamVal forOpNotEquals() {
        return BoolConstant.toBoolConstant(!arg1.accept(EvalVisitor.this).equals(arg2.accept(EvalVisitor.this)));
      }
      
      public JamVal forOpLessThan() {
        return BoolConstant.toBoolConstant(evalIntegerArg(arg1, "<").value() < evalIntegerArg(arg2, "<").value());
      }
      
      public JamVal forOpGreaterThan() {
        return BoolConstant.toBoolConstant(evalIntegerArg(arg1, ">").value() > evalIntegerArg(arg2, ">").value());
      }
      
      public JamVal forOpLessThanEquals() {
        return BoolConstant.toBoolConstant(evalIntegerArg(arg1, "<=").value() <= evalIntegerArg(arg2, "<=").value());
      }
      
      public JamVal forOpGreaterThanEquals() {
        return BoolConstant.toBoolConstant(evalIntegerArg(arg1, ">=").value() >= evalIntegerArg(arg2, ">=").value());
      }
      
      public JamVal forOpAnd() {
        BoolConstant b1 = evalBooleanArg(arg1, "&");
        if (b1 == BoolConstant.FALSE)  return BoolConstant.FALSE;
        return evalBooleanArg(arg2, "&");
      }
      
      public JamVal forOpOr() {
        BoolConstant b1 = evalBooleanArg(arg1, "|");
        if (b1 == BoolConstant.TRUE) return BoolConstant.TRUE;
        return evalBooleanArg(arg2, "|");
      }

      public JamVal forOpGets() {
        JamVal val1 = arg1.accept(EvalVisitor.this);
        if (!(val1 instanceof JamRef))
          throw new EvalException("Binary operator `<-' applied to non-ref " + val1);
        JamVal val2 = arg2.accept(EvalVisitor.this);
        ((JamRef) val1).setValue(val2);
        return JamUnit.ONLY;
      }
    } // end of BinOpEvaluator class
  } // end of EvalVisitor class

  /* Type System for Typed Jam */

  /** Type interface for all Jam types. */
  interface Type {
    public String toString();
  }

  /** Type for int values. */
  static class IntType implements Type {
    public static final IntType ONLY = new IntType();
    private IntType() {}
    public String toString() { return "int"; }
  }

  /** Type for boolean values. */
  static class BoolType implements Type {
    public static final BoolType ONLY = new BoolType();
    private BoolType() {}
    public String toString() { return "bool"; }
  }

  /** Type for unit values. */
  static class UnitType implements Type {
    public static final UnitType ONLY = new UnitType();
    private UnitType() {}
    public String toString() { return "unit"; }
  }

  /** Type for list values with element type. */
  static class ListType implements Type {
    private Type elemType;
    ListType(Type et) { elemType = et; }
    public Type elemType() { return elemType; }
    public String toString() { return "list " + elemType; }
    public boolean equals(Object o) {
      if (!(o instanceof ListType)) return false;
      return elemType.equals(((ListType)o).elemType);
    }
  }

  /** Type for reference values with referenced type. */
  static class RefType implements Type {
    private Type elemType;
    RefType(Type et) { elemType = et; }
    public Type elemType() { return elemType; }
    public String toString() { return "ref " + elemType; }
    public boolean equals(Object o) {
      if (!(o instanceof RefType)) return false;
      return elemType.equals(((RefType)o).elemType);
    }
  }

  /** Type for function values. */
  static class FunType implements Type {
    private Type[] paramTypes;
    private Type resultType;
    FunType(Type[] pts, Type rt) { paramTypes = pts; resultType = rt; }
    public Type[] paramTypes() { return paramTypes; }
    public Type resultType() { return resultType; }
    public String toString() {
      StringBuilder sb = new StringBuilder("(");
      for (int i = 0; i < paramTypes.length; i++) {
        if (i > 0) sb.append(", ");
        sb.append(paramTypes[i]);
      }
      sb.append(" -> ").append(resultType).append(")");
      return sb.toString();
    }
    public boolean equals(Object o) {
      if (!(o instanceof FunType)) return false;
      FunType ft = (FunType)o;
      if (paramTypes.length != ft.paramTypes.length) return false;
      for (int i = 0; i < paramTypes.length; i++) {
        if (!paramTypes[i].equals(ft.paramTypes[i])) return false;
      }
      return resultType.equals(ft.resultType);
    }
  }

  /** Polymorphic type variable (like 'a in ML). */
  static class PolymorphicType implements Type {
    private String name;
    PolymorphicType(String n) { name = n; }
    public String name() { return name; }
    public String toString() { return "'" + name; }
    public boolean equals(Object o) {
      if (!(o instanceof PolymorphicType)) return false;
      return name.equals(((PolymorphicType)o).name);
    }
  }

  /** Type checking visitor. */
  static class TypeCheckVisitor {
    private java.util.Map<String, Type> typeEnv;

    /** Check an expression and return its type. */
    Type checkExp(AST exp, java.util.Map<String, Type> env) {
      this.typeEnv = env;
      return exp.accept(new ExpTypeChecker());
    }

    private class ExpTypeChecker implements ASTVisitor<Type> {
      public Type forBoolConstant(BoolConstant b) { return BoolType.ONLY; }
      public Type forIntConstant(IntConstant i) { return IntType.ONLY; }
      public Type forEmptyConstant(EmptyConstant n) {
        // Return a polymorphic list type that can be any list type.
        // The actual element type is determined by context.
        return new ListType(new PolymorphicType("a"));
      }

      public Type forVariable(Variable v) {
        Type t = typeEnv.get(v.toString());
        if (t == null) throw new TypeException("Unbound variable: " + v);
        return t;
      }

      public Type forPrimFun(PrimFun f) {
        // PrimFuns need context-dependent typing. They should only appear in applications.
        // For now, we'll return a placeholder and handle them in forApp.
        // This allows them to appear syntactically but requires special handling in applications.
        return IntType.ONLY;  // placeholder - will be overridden in application context
      }

      public Type forUnOpApp(UnOpApp u) {
        Type argType = checkExp(u.arg(), typeEnv);
        UnOp op = u.rator();

        if (op == UnOpPlus.ONLY) {
          if (!(argType instanceof PolymorphicType) && !typeEq(argType, IntType.ONLY))
            throw new TypeException("Unary + expects int, got " + argType);
          return IntType.ONLY;
        }
        if (op == UnOpMinus.ONLY) {
          if (!(argType instanceof PolymorphicType) && !typeEq(argType, IntType.ONLY))
            throw new TypeException("Unary - expects int, got " + argType);
          return IntType.ONLY;
        }
        if (op == OpTilde.ONLY) {
          if (!(argType instanceof PolymorphicType) && !typeEq(argType, BoolType.ONLY))
            throw new TypeException("~ expects bool, got " + argType);
          return BoolType.ONLY;
        }
        if (op == OpBang.ONLY) {
          if (!(argType instanceof RefType) && !(argType instanceof PolymorphicType))
            throw new TypeException("! expects ref type, got " + argType);
          if (argType instanceof RefType)
            return ((RefType)argType).elemType();
          return new PolymorphicType("a");  // placeholder for polymorphic case
        }
        if (op == OpRef.ONLY) {
          return new RefType(argType);
        }
        throw new TypeException("Unknown unary operator: " + op);
      }

      public Type forBinOpApp(BinOpApp b) {
        Type arg1Type = checkExp(b.arg1(), typeEnv);
        Type arg2Type = checkExp(b.arg2(), typeEnv);
        BinOp op = b.rator();

        if (op == BinOpPlus.ONLY || op == BinOpMinus.ONLY || op == OpTimes.ONLY || op == OpDivide.ONLY) {
          if (!typeEq(arg1Type, IntType.ONLY))
            throw new TypeException("Binary " + op + " expects int operands, got " + arg1Type);
          if (!typeEq(arg2Type, IntType.ONLY))
            throw new TypeException("Binary " + op + " expects int operands, got " + arg2Type);
          return IntType.ONLY;
        }
        if (op == OpEquals.ONLY || op == OpNotEquals.ONLY) {
          // For = and !=, both operands must have the same type
          // Polymorphic types unify with any type
          if (!hasPolymorphicType(arg1Type) && !hasPolymorphicType(arg2Type)) {
            if (!typeEq(arg1Type, arg2Type))
              throw new TypeException("Comparison " + op + " requires same types, got " + arg1Type + " and " + arg2Type);
          }
          return BoolType.ONLY;
        }
        if (op == OpLessThan.ONLY || op == OpGreaterThan.ONLY ||
            op == OpLessThanEquals.ONLY || op == OpGreaterThanEquals.ONLY) {
          if (!typeEq(arg1Type, IntType.ONLY))
            throw new TypeException("Binary " + op + " expects int operands, got " + arg1Type);
          if (!typeEq(arg2Type, IntType.ONLY))
            throw new TypeException("Binary " + op + " expects int operands, got " + arg2Type);
          return BoolType.ONLY;
        }
        if (op == OpAnd.ONLY || op == OpOr.ONLY) {
          if (!typeEq(arg1Type, BoolType.ONLY))
            throw new TypeException("Binary " + op + " expects bool operands, got " + arg1Type);
          if (!typeEq(arg2Type, BoolType.ONLY))
            throw new TypeException("Binary " + op + " expects bool operands, got " + arg2Type);
          return BoolType.ONLY;
        }
        if (op == OpGets.ONLY) {
          if (!(arg1Type instanceof RefType))
            throw new TypeException("<- expects a ref type, got " + arg1Type);
          Type refElemType = ((RefType)arg1Type).elemType();
          if (!typeEq(refElemType, arg2Type))
            throw new TypeException("<- type mismatch: ref element type is " + refElemType + " but value is " + arg2Type);
          return UnitType.ONLY;
        }
        throw new TypeException("Unknown binary operator: " + op);
      }

      public Type forApp(App a) {
        AST rator = a.rator();
        AST[] args = a.args();

        // Special handling for primitive functions with polymorphic types
        if (rator instanceof PrimFun) {
          return typePrimApp((PrimFun) rator, args);
        }

        Type ratorType = checkExp(rator, typeEnv);
        if (!(ratorType instanceof FunType))
          throw new TypeException("Function application: rator has type " + ratorType + ", not a function type");
        FunType ft = (FunType) ratorType;
        Type[] paramTypes = ft.paramTypes();
        if (args.length != paramTypes.length)
          throw new TypeException("Function application: expected " + paramTypes.length + " arguments, got " + args.length);
        for (int i = 0; i < args.length; i++) {
          Type argType = checkExp(args[i], typeEnv);
          if (!typeEq(argType, paramTypes[i]))
            throw new TypeException("Function application: argument " + i + " has type " + argType + ", expected " + paramTypes[i]);
        }
        return ft.resultType();
      }

      /** Type check application of a primitive function with polymorphic type. */
      private Type typePrimApp(PrimFun prim, AST[] args) {
        // Handle each primitive function
        if (prim instanceof ConsPrim) {
          if (args.length != 2)
            throw new TypeException("cons expects 2 arguments, got " + args.length);
          Type elem = checkExp(args[0], typeEnv);
          Type list = checkExp(args[1], typeEnv);
          if (!(list instanceof ListType))
            throw new TypeException("cons second argument must be a list, got " + list);
          ListType lt = (ListType) list;
          // Check that element type matches list element type
          Type listElem = lt.elemType();
          // If list element type is concrete, check elem matches it
          if (!(listElem instanceof PolymorphicType)) {
            // List has concrete element type - elem must match
            if (elem instanceof PolymorphicType || !typeEq(elem, listElem)) {
              throw new TypeException("cons: element type " + elem + " does not match list element type " + listElem);
            }
          } else if (!(elem instanceof PolymorphicType)) {
            // Element is concrete, list is polymorphic - return list with concrete element type
            return new ListType(elem);
          }
          // Both polymorphic or element is concrete and matches - OK
          return list;
        }

        if (prim instanceof FirstPrim) {
          if (args.length != 1)
            throw new TypeException("first expects 1 argument, got " + args.length);
          Type list = checkExp(args[0], typeEnv);
          if (!(list instanceof ListType))
            throw new TypeException("first argument must be a list, got " + list);
          return ((ListType) list).elemType();
        }

        if (prim instanceof RestPrim) {
          if (args.length != 1)
            throw new TypeException("rest expects 1 argument, got " + args.length);
          Type list = checkExp(args[0], typeEnv);
          if (!(list instanceof ListType))
            throw new TypeException("rest argument must be a list, got " + list);
          return list;
        }

        if (prim instanceof EmptyPPrim) {
          if (args.length != 1)
            throw new TypeException("empty? expects 1 argument, got " + args.length);
          Type arg = checkExp(args[0], typeEnv);
          if (!(arg instanceof ListType))
            throw new TypeException("empty? argument must be a list, got " + arg);
          return BoolType.ONLY;
        }

        if (prim instanceof ConsPPrim) {
          if (args.length != 1)
            throw new TypeException("cons? expects 1 argument, got " + args.length);
          Type arg = checkExp(args[0], typeEnv);
          if (!(arg instanceof ListType))
            throw new TypeException("cons? argument must be a list, got " + arg);
          return BoolType.ONLY;
        }

        // For other prims (number?, function?, list?, ref?, arity), reject them
        throw new TypeException("Primitive function " + prim + " is not supported in typed Jam");
      }

      public Type forMap(Map m) {
        // Type-check the map body with parameters added to environment
        java.util.Map<String, Type> newEnv = new HashMap<String, Type>(typeEnv);
        Variable[] vars = m.vars();
        // For now, we can't determine parameter types from the AST since they were parsed and discarded
        // In a proper implementation, we'd store type annotations in the AST
        // For now, assume parameters have some generic type
        Type[] paramTypes = new Type[vars.length];
        for (int i = 0; i < vars.length; i++) {
          // We can't determine the type without storing it in the AST
          // For now, just add to environment with a placeholder
          paramTypes[i] = IntType.ONLY; // placeholder
          newEnv.put(vars[i].toString(), paramTypes[i]);
        }
        Type bodyType = checkExp(m.body(), newEnv);
        return new FunType(paramTypes, bodyType);
      }

      public Type forIf(If i) {
        Type testType = checkExp(i.test(), typeEnv);
        if (!typeEq(testType, BoolType.ONLY))
          throw new TypeException("if condition must be bool, got " + testType);
        Type conseqType = checkExp(i.conseq(), typeEnv);
        Type altType = checkExp(i.alt(), typeEnv);
        if (!typeEq(conseqType, altType))
          throw new TypeException("if branches have different types: " + conseqType + " vs " + altType);
        return conseqType;
      }

      public Type forLet(Let l) {
        // Type-check the let definitions and add variables to environment
        java.util.Map<String, Type> newEnv = new HashMap<String, Type>(typeEnv);
        Def[] defs = l.defs();
        for (Def def : defs) {
          Type expType = checkExp(def.rhs(), newEnv);
          Variable var = def.lhs();
          // For now, we can't extract the declared type from the AST since we parsed and discarded it
          // In a proper implementation, we'd check that expType matches the declared type
          // For now, just use the inferred type
          newEnv.put(var.toString(), expType);
        }
        // Type-check the body with the new environment
        return checkExp(l.body(), newEnv);
      }

      public Type forBlock(Block b) {
        Type resultType = null;
        for (AST exp : b.exps()) {
          resultType = checkExp(exp, typeEnv);
        }
        return resultType != null ? resultType : UnitType.ONLY;
      }
    }

    /** Check if a type contains any polymorphic type variables. */
    private boolean hasPolymorphicType(Type t) {
      if (t instanceof PolymorphicType) return true;
      if (t instanceof ListType) return hasPolymorphicType(((ListType)t).elemType);
      if (t instanceof RefType) return hasPolymorphicType(((RefType)t).elemType);
      if (t instanceof FunType) {
        FunType ft = (FunType) t;
        for (Type pt : ft.paramTypes()) {
          if (hasPolymorphicType(pt)) return true;
        }
        return hasPolymorphicType(ft.resultType());
      }
      return false;
    }

    /** Check if two types are equal. Polymorphic types unify with any type. */
    private boolean typeEq(Type t1, Type t2) {
      // Polymorphic types unify with any type
      if (t1 instanceof PolymorphicType || t2 instanceof PolymorphicType) return true;

      if (t1 == IntType.ONLY && t2 == IntType.ONLY) return true;
      if (t1 == BoolType.ONLY && t2 == BoolType.ONLY) return true;
      if (t1 == UnitType.ONLY && t2 == UnitType.ONLY) return true;
      if (t1 instanceof ListType && t2 instanceof ListType) {
        return typeEq(((ListType)t1).elemType, ((ListType)t2).elemType);
      }
      if (t1 instanceof RefType && t2 instanceof RefType) {
        return typeEq(((RefType)t1).elemType, ((RefType)t2).elemType);
      }
      if (t1 instanceof FunType && t2 instanceof FunType) {
        return t1.equals(t2);
      }
      return false;
    }
  }

} // end of Interpreter class