/** Call-by-value, Call-by-name, and Call-by-need Jam interpreter */

import java.io.IOException;
import java.io.Reader;

/** Interpreter Classes */

/** A class that implements call-by-value, call-by-name, and call-by-need interpretation of Jam programs. */
class Interpreter {

  /** program for this interpeter, initialized in constructors. */
  AST prog;

  /** Constructor for a program given in a file. Not used in Assignment 2*/
  public Interpreter(String fileName) throws IOException {
    Parser p = new Parser(fileName);
    prog = p.parse();
  }

  /** Constructor for a program already embedded in a Parser object. */
  public Interpreter(Parser p) {
    prog = p.parse();
  }

  /** Constructor for a program embedded in a Reader. Not used in Assignment 2. */
  public Interpreter(Reader reader) {
    Parser p = new Parser(reader);
    prog = p.parse();
  }

  /** Parses and CBV interprets the input embeded in parser */
  public JamVal callByValue() { return prog.accept(valueEvalVisitor); }

  /** Parses and CBNm interprets the input embeded in parser */
  public JamVal callByName() { return prog.accept(nameEvalVisitor); }

  /** Parses and CBNd interprets the input embeded in parser */
  public JamVal callByNeed() { return prog.accept(needEvalVisitor); }

  /** A class representing an unevaluated expresssion (together with the corresponding evaluator). */
  private 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 of Suspension interface. */
    public JamVal eval() {
      return exp.accept(ev);  }

    public String toString() { return "<" + exp + ", " + ev + ">"; }
  }

  /** Class representing a binding in CBV evaluation. */
  private static class ValueBinding extends Binding {
    ValueBinding(Variable v, JamVal jv) { super(v, jv); }
    public JamVal value() { return value; }
    public void setBinding(Suspension s) { value = s.eval(); }
    public String toString() { return "[" + var + ", " + value + "]"; }
  }

  /** Class representing a binding in CBName evaluation. The inherited value field is ignored. */
  private static class NameBinding extends Binding {
    protected Suspension susp;
    NameBinding(Variable v, Suspension s) {
      super(v, null);
      susp = s;
    }
    /** Evaluates the suspension each time value is requested. */
    public JamVal value() { return susp.eval(); }
    /** Sets the suspension for this binding. */
    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-driven evaluation. */
  private static class NeedBinding extends NameBinding {
    NeedBinding(Variable v, Suspension s) { super(v,s); }
    /** Evaluates the suspension on first access, caches the result for subsequent accesses. */
    public JamVal value() {
      if (value == null) {
        value = susp.eval();
      }
      return value;
    }
    public String toString() { return "[" + var + ", " + value + ", " + susp + "]"; }
  }

  /** Visitor class implementing a lookup method on environments.
    * @return value() for variable var for both lazy and eager environments. */
  private static class LookupVisitor implements PureListVisitor<Binding,JamVal> {

    Variable var;   // the lexer guarantees that there is only one Variable for a given name

    LookupVisitor(Variable v) { var = v; }

    /* Visitor methods. */
    /** Throws EvalException since the variable was not found in the environment. */
    public JamVal forEmpty(Empty<Binding> e) {
      throw new EvalException("Variable " + var + " is undefined");
    }
    /** Checks if the first binding matches var; if so returns value, otherwise recurses on rest. */
    public JamVal forCons(Cons<Binding> c) {
      Binding b = c.first();
      if (b.var() == var) return b.value();
      return c.rest().accept(this);
    }
  }

  /** The interface supporting various evaluation policies (CBV, CBNm, CBNd) for map applications and let constructions. */
  private interface EvalPolicy {
    /** Constructs the appropriate binding object for this, binding var to ast in the evaluator ev */
    Binding newBinding(Variable var, AST ast, EvalVisitor ev);
  }

  /** An ASTVisitor class for evaluating ASTs where the evaluation policy for function applications and other
    * binding operations such as let are determined by an embedded EvalPolicy. */
  private static class EvalVisitor implements ASTVisitor<JamVal> {

    /* The code in this class assumes that:
     * * OpTokens are unique;
     * * Variable objects are unique: v1.name.equals(v.name) => v1 == v2; and
     * * The only objects used as boolean values are BoolConstant.TRUE and BoolConstant.FALSE.
     * Hence,  == can be used to compare Variable objects, OpTokens, and BoolConstants. */

    private PureList<Binding> env;  // the embdedded environment
    private EvalPolicy evalPolicy;  // the embedded EvalPolicy

    /** Constructor for recursive calls. */
    private EvalVisitor(PureList<Binding> e, EvalPolicy ep) {
      env = e;
      evalPolicy = ep;
    }

    /** Top level constructor. */
    public EvalVisitor(EvalPolicy ep) { this(new Empty<Binding>(), ep); }

    /** Factory method that constructs a new visitor with environment e and same evalPolicy as this. */
    public EvalVisitor newVisitor(PureList<Binding> e) {
      return new EvalVisitor(e, evalPolicy);
    }

    /** Factory method that constructs a Binding of var to ast corresponding to this.evalPolicy */
    public Binding newBinding(Variable var, AST ast) {
      return evalPolicy.newBinding(var, ast, this);
    }

    /** Getter for env field */
    public PureList<Binding> env() { return env; }

    /* ASTVisitor methods */
    public JamVal forBoolConstant(BoolConstant b) { return b; }
    public JamVal forIntConstant(IntConstant i) { return i; }
    public JamVal forEmptyConstant(EmptyConstant n) { return JamEmpty.ONLY; }

    /** Looks up the variable in the current environment. */
    public JamVal forVariable(Variable v) {
      return env.accept(new LookupVisitor(v));
    }

    /** Primitive functions are values; returns the function directly. */
    public JamVal forPrimFun(PrimFun f) { return f; }

    /** Evaluates the argument, then applies the unary operator. */
    public JamVal forUnOpApp(UnOpApp u) {
      JamVal argVal = u.arg().accept(this);
      return u.rator().accept(new StandardUnOpVisitor(argVal));
    }

    /** Delegates to StandardBinOpVisitor which handles short-circuit evaluation for & and |. */
    public JamVal forBinOpApp(BinOpApp b) {
      return b.rator().accept(new StandardBinOpVisitor(b.arg1(), b.arg2(), this));
    }

    /** Evaluates the rator, checks it is a function, then applies it to the args. */
    public JamVal forApp(App a) {
      JamVal rator = a.rator().accept(this);
      if (!(rator instanceof JamFun)) {
        throw new EvalException("Attempted to apply " + rator + " which is not a function");
      }
      return ((JamFun) rator).accept(new StandardFunVisitor(a.args(), this));
    }

    /** Creates a closure capturing the current environment. */
    public JamVal forMap(Map m) {
      return new JamClosure(m, env);
    }

    /** Evaluates the test; if boolean, evaluates the appropriate branch. */
    public JamVal forIf(If i) {
      JamVal test = i.test().accept(this);
      if (!(test instanceof BoolConstant)) {
        throw new EvalException("if-then-else requires a boolean test, got " + test);
      }
      if (test == BoolConstant.TRUE) {
        return i.conseq().accept(this);
      } else {
        return i.alt().accept(this);
      }
    }

    /** Non-recursive let: binds all defs in the current environment, then evaluates body in extended env. */
    public JamVal forLet(Let l) {
      Def[] defs = l.defs();
      PureList<Binding> newEnv = env;
      for (int i = defs.length - 1; i >= 0; i--) {
        newEnv = newEnv.cons(newBinding(defs[i].lhs(), defs[i].rhs()));
      }
      return l.body().accept(newVisitor(newEnv));
    }
  }

  /** Top-level EvalVisitors implementing CBV, CBNm, and CBNd evaluation. */
  private static EvalVisitor valueEvalVisitor = new EvalVisitor(CallByValue.ONLY);
  private static EvalVisitor nameEvalVisitor = new EvalVisitor(CallByName.ONLY);
  private static EvalVisitor needEvalVisitor = new EvalVisitor(CallByNeed.ONLY);

  /** JamFunVisitor class that evaluates the application of a JamFun to argument expressions. */
  private static class StandardFunVisitor implements JamFunVisitor<JamVal> {

    /** Unevaluated arguments */
    AST[] args;

    /** Evaluation visitor */
    EvalVisitor evalVisitor;

    StandardFunVisitor(AST[] asts, EvalVisitor ev) {
      args = asts;
      evalVisitor = ev;
    }

    /** Eagerly evaluate all arguments using the current eval visitor. */
    private JamVal[] evalArgs() {
      JamVal[] vals = new JamVal[args.length];
      for (int i = 0; i < args.length; i++) {
        vals[i] = args[i].accept(evalVisitor);
      }
      return vals;
    }

    /** Applies a closure: checks arity, extends closure env with bindings, evaluates body. */
    public JamVal forJamClosure(JamClosure closure) {
      Map map = closure.code();
      Variable[] params = map.vars();
      if (params.length != args.length) {
        throw new EvalException("Closure expected " + params.length + " arguments but got " + args.length);
      }
      PureList<Binding> closureEnv = closure.env();
      for (int i = params.length - 1; i >= 0; i--) {
        closureEnv = closureEnv.cons(evalVisitor.newBinding(params[i], args[i]));
      }
      return map.body().accept(evalVisitor.newVisitor(closureEnv));
    }

    /** Applies a primitive function: always evaluates args eagerly regardless of eval policy. */
    public JamVal forPrimFun(PrimFun primFun) {
      JamVal[] evaledArgs = evalArgs();
      return primFun.accept(new StandardPrimFunVisitor(evaledArgs));
    }
  }

  /** CBV: evaluates the argument and binds the variable to the resulting value. */
  private static class CallByValue implements EvalPolicy {

    public static final EvalPolicy ONLY = new CallByValue();
    private CallByValue() { }

    public Binding newBinding(Variable var, AST arg, EvalVisitor ev) {
      return new ValueBinding(var, arg.accept(ev));
    }
  }

  /** CBName: binds the variable to a suspension that re-evaluates the expression each time. */
  private static class CallByName implements EvalPolicy {
    public static final EvalPolicy ONLY = new CallByName();
    private CallByName() {}

    public Binding newBinding(Variable var, AST arg, EvalVisitor ev) {
      return new NameBinding(var, new ConcreteSuspension(arg, ev));
    }
  }

  /** CBNeed: binds the variable to a suspension that evaluates once and caches the result. */
  private static class CallByNeed implements EvalPolicy {
    public static final EvalPolicy ONLY = new CallByNeed();
    private CallByNeed() {}

    public Binding newBinding(Variable var, AST arg, EvalVisitor ev) {
      return new NeedBinding(var, new ConcreteSuspension(arg, ev));
    }
  }

  /* Only works for eager unary operators */
  private static class StandardUnOpVisitor implements UnOpVisitor<JamVal> {
    private final JamVal val;
    StandardUnOpVisitor(JamVal jv) { val = jv; }

    /** Returns val provided it is an IntConstant; throws EvalException otherwise. */
    private IntConstant checkInteger(String op) {
      if (!(val instanceof IntConstant)) {
        throw new EvalException("Unary operator " + op + " requires an integer, got " + val);
      }
      return (IntConstant) val;
    }

    /** Returns val provided it is a BoolConstant; throws EvalException otherwise. */
    private BoolConstant checkBoolean(String op) {
      if (!(val instanceof BoolConstant)) {
        throw new EvalException("Unary operator " + op + " requires a boolean, got " + val);
      }
      return (BoolConstant) val;
    }

    public JamVal forUnOpPlus() { return checkInteger("+"); }
    public JamVal forUnOpMinus() {
      IntConstant i = checkInteger("-");
      return new IntConstant(-i.value());
    }
    public JamVal forOpTilde() {
      BoolConstant b = checkBoolean("~");
      return b.not();
    }
  }

  /** Structural equality comparison for Jam values. Numbers and booleans use value equality,
    * lists use recursive structural equality, functions use identity (==). */
  private static boolean jamEquals(JamVal v1, JamVal v2) {
    if (v1 instanceof IntConstant && v2 instanceof IntConstant) {
      return ((IntConstant) v1).value() == ((IntConstant) v2).value();
    }
    if (v1 instanceof BoolConstant && v2 instanceof BoolConstant) {
      return v1 == v2;
    }
    if (v1 instanceof JamEmpty && v2 instanceof JamEmpty) {
      return true;
    }
    if (v1 instanceof JamCons && v2 instanceof JamCons) {
      JamCons c1 = (JamCons) v1;
      JamCons c2 = (JamCons) v2;
      return jamEquals(c1.first(), c2.first()) && jamEquals(c1.rest(), c2.rest());
    }
    if (v1 instanceof JamFun && v2 instanceof JamFun) {
      return v1 == v2;
    }
    return false;
  }

  private static class StandardBinOpVisitor implements BinOpVisitor<JamVal> {
    private AST arg1, arg2;
    private EvalVisitor evalVisitor;

    StandardBinOpVisitor(AST a1, AST a2, EvalVisitor ev) { arg1 = a1; arg2 = a2; evalVisitor = ev; }

    /** Evaluate the specified argument AST and confirm that it is an IntConstant. */
    private IntConstant evalIntegerArg(AST arg, String op) {
      JamVal val = arg.accept(evalVisitor);
      if (!(val instanceof IntConstant)) {
        throw new EvalException("Binary operator " + op + " requires integer arguments, got " + val);
      }
      return (IntConstant) val;
    }

    /** Evaluate the specified argument AST and confirm that it is a BoolConstant. */
    private BoolConstant evalBooleanArg(AST arg, String op) {
      JamVal val = arg.accept(evalVisitor);
      if (!(val instanceof BoolConstant)) {
        throw new EvalException("Binary operator " + op + " requires boolean arguments, got " + val);
      }
      return (BoolConstant) val;
    }

    public JamVal forBinOpPlus() {
      IntConstant left = evalIntegerArg(arg1, "+");
      IntConstant right = evalIntegerArg(arg2, "+");
      return new IntConstant(left.value() + right.value());
    }
    public JamVal forBinOpMinus() {
      IntConstant left = evalIntegerArg(arg1, "-");
      IntConstant right = evalIntegerArg(arg2, "-");
      return new IntConstant(left.value() - right.value());
    }
    public JamVal forOpTimes() {
      IntConstant left = evalIntegerArg(arg1, "*");
      IntConstant right = evalIntegerArg(arg2, "*");
      return new IntConstant(left.value() * right.value());
    }
    public JamVal forOpDivide() {
      IntConstant left = evalIntegerArg(arg1, "/");
      IntConstant right = evalIntegerArg(arg2, "/");
      if (right.value() == 0) {
        throw new EvalException("Division by zero");
      }
      return new IntConstant(left.value() / right.value());
    }

    public JamVal forOpEquals() {
      JamVal left = arg1.accept(evalVisitor);
      JamVal right = arg2.accept(evalVisitor);
      return BoolConstant.toBoolConstant(jamEquals(left, right));
    }
    public JamVal forOpNotEquals() {
      JamVal left = arg1.accept(evalVisitor);
      JamVal right = arg2.accept(evalVisitor);
      return BoolConstant.toBoolConstant(!jamEquals(left, right));
    }
    public JamVal forOpLessThan() {
      IntConstant left = evalIntegerArg(arg1, "<");
      IntConstant right = evalIntegerArg(arg2, "<");
      return BoolConstant.toBoolConstant(left.value() < right.value());
    }
    public JamVal forOpGreaterThan() {
      IntConstant left = evalIntegerArg(arg1, ">");
      IntConstant right = evalIntegerArg(arg2, ">");
      return BoolConstant.toBoolConstant(left.value() > right.value());
    }
    public JamVal forOpLessThanEquals() {
      IntConstant left = evalIntegerArg(arg1, "<=");
      IntConstant right = evalIntegerArg(arg2, "<=");
      return BoolConstant.toBoolConstant(left.value() <= right.value());
    }
    public JamVal forOpGreaterThanEquals() {
      IntConstant left = evalIntegerArg(arg1, ">=");
      IntConstant right = evalIntegerArg(arg2, ">=");
      return BoolConstant.toBoolConstant(left.value() >= right.value());
    }

    /** Short-circuit AND: returns false immediately if left is false. */
    public JamVal forOpAnd() {
      BoolConstant left = evalBooleanArg(arg1, "&");
      if (left == BoolConstant.FALSE) return BoolConstant.FALSE;
      return evalBooleanArg(arg2, "&");
    }
    /** Short-circuit OR: returns true immediately if left is true. */
    public JamVal forOpOr() {
      BoolConstant left = evalBooleanArg(arg1, "|");
      if (left == BoolConstant.TRUE) return BoolConstant.TRUE;
      return evalBooleanArg(arg2, "|");
    }
  }

  /** Visitor that implements each primitive function.  Only supports strict functions. */
  private static class StandardPrimFunVisitor implements PrimFunVisitor<JamVal> {

    JamVal[] vals;  // evaluated arguments for PrimFun App

    StandardPrimFunVisitor(JamVal[] vls) { vals = vls; }

    private JamVal primFunError(String fn) {
      throw new EvalException("Primitive function `" + fn + "' applied to " + vals.length + " arguments");
    }

    /** Confirms that vals[0] is a JamCons. Assumes that the function is unary (arity already checked). */
    private JamCons confirmJamCons(String funName) {
      if (vals.length != 1) return (JamCons) primFunError(funName);
      if (!(vals[0] instanceof JamCons)) {
        throw new EvalException("Primitive function `" + funName + "' requires a non-empty list, got " + vals[0]);
      }
      return (JamCons) vals[0];
    }

    public JamVal forFunctionPPrim() {
      if (vals.length != 1) return primFunError("function?");
      return BoolConstant.toBoolConstant(vals[0] instanceof JamFun);
    }
    public JamVal forNumberPPrim() {
      if (vals.length != 1) return primFunError("number?");
      return BoolConstant.toBoolConstant(vals[0] instanceof IntConstant);
    }
    public JamVal forListPPrim() {
      if (vals.length != 1) return primFunError("list?");
      return BoolConstant.toBoolConstant(vals[0] instanceof JamList);
    }
    public JamVal forConsPPrim() {
      if (vals.length != 1) return primFunError("cons?");
      return BoolConstant.toBoolConstant(vals[0] instanceof JamCons);
    }
    public JamVal forEmptyPPrim() {
      if (vals.length != 1) return primFunError("empty?");
      return BoolConstant.toBoolConstant(vals[0] instanceof JamEmpty);
    }
    public JamVal forConsPrim() {
      if (vals.length != 2) return primFunError("cons");
      if (!(vals[1] instanceof JamList)) {
        throw new EvalException("cons requires a list as second argument, got " + vals[1]);
      }
      return new JamCons(vals[0], (JamList) vals[1]);
    }
    public JamVal forArityPrim() {
      if (vals.length != 1) return primFunError("arity");
      JamVal val = vals[0];
      if (val instanceof JamClosure) {
        return new IntConstant(((JamClosure) val).code().vars().length);
      }
      if (val instanceof PrimFun) {
        return ((PrimFun) val).accept(new PrimFunVisitor<JamVal>() {
          public JamVal forFunctionPPrim() { return new IntConstant(1); }
          public JamVal forNumberPPrim() { return new IntConstant(1); }
          public JamVal forListPPrim() { return new IntConstant(1); }
          public JamVal forConsPPrim() { return new IntConstant(1); }
          public JamVal forEmptyPPrim() { return new IntConstant(1); }
          public JamVal forArityPrim() { return new IntConstant(1); }
          public JamVal forConsPrim() { return new IntConstant(2); }
          public JamVal forFirstPrim() { return new IntConstant(1); }
          public JamVal forRestPrim() { return new IntConstant(1); }
        });
      }
      throw new EvalException("arity requires a function argument, got " + val);
    }
    public JamVal forFirstPrim() {
      if (vals.length != 1) return primFunError("first");
      JamCons c = confirmJamCons("first");
      return c.first();
    }
    public JamVal forRestPrim() {
      if (vals.length != 1) return primFunError("rest");
      JamCons c = confirmJamCons("rest");
      return c.rest();
    }

  }
}

class EvalException extends RuntimeException {
  EvalException(String msg) { super(msg); }
}