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

import java.io.*;

/** A visitor interface for interpreting AST's */
interface EvalVisitor extends ASTVisitor<JamVal> {

 /** Factory method that constructs a new visitor of same class with specified environment env. */
 EvalVisitor newVisitor(PureList<Binding> env);

 /** Gets the environment field. */
 PureList<Binding> env();

  /** Factory method that constructs a Binding of var to ast in the current environment. */
 Binding newBinding(Variable var, AST ast);
}

/** Defines an interpreter object capable of performing callByValue, callbyName, or callByNeed on the embedded program. */
class Interpreter {

 Parser parser = null;

 Interpreter(String fileName) throws IOException {  parser = new Parser(fileName); }

 Interpreter(Parser p) { parser = p; }

 Interpreter(Reader reader) { parser = new Parser(reader); }

 // <unop>  ::= <sign> | ~
 // <binop> ::= <sign> | "*" | / | = |  < | | <= | & | "|"
 // <sign>  ::= "+" | -

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

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

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

 /** CBV Interprets prog with respect to symbols in lexer */
 public JamVal callByValue(AST prog) {
   return prog.accept(valueEvalVisitor);
 }

 /** CBN Interprets prog with respect to symbols in lexer */
 public JamVal callByName(AST prog) {
   return prog.accept(nameEvalVisitor);
 }

 /** CBN Interprets prog with respect to symbols in lexer */
 public JamVal callByNeed(AST prog) {
   return prog.accept(needEvalVisitor);
 }

 /** Defines an object representing a potential JamVal. */
 static class Suspension {

   private AST exp;
   private EvalVisitor ev;

   Suspension(AST a, EvalVisitor e) { exp = a; ev = e; }

   public AST exp() { return exp; }
   public EvalVisitor ev() { return ev; }
   public void putEv(EvalVisitor e) { ev = e; }

   JamVal eval() {
     // System.err.println("eval() called on the susp with AST = " + exp);
     return exp.accept(ev);  }

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

 /** Defines an object representing a callByValue binding in an environment. */
 static class ValueBinding implements Binding {
   private Variable var;
   private JamVal value;
   ValueBinding(Variable v, JamVal jv) { var = v; value = jv; }
   public Variable var() { return var; }
   public JamVal value() { return value; }
   public String toString() { return "[" + var + ", " + value + "]"; }
 }

 /** Defines an object representing a callByName binding in an environment. */
 static class NameBinding implements Binding {
   private Variable var;
   private Suspension susp;
   NameBinding(Variable v, Suspension s) { var = v; susp = s; }
   public Variable var() { return var; }
   public JamVal value() { return susp.eval(); }
   public String toString() { return "[" + var + ", " + susp + "]"; }
 }

 /** Defines an object representing a callByNeed binding in an environment. */
 static class NeedBinding implements Binding {
   Variable var;
   JamVal value;
   private Suspension susp;
   NeedBinding(Variable v, Suspension s) { var = v; value = null; susp = s; }
   public JamVal value() {
     if (value == null) {  // a legitimate JamVal CANNOT be null
       value = susp.eval();
       susp = null;  // release susp object for GC!
     }
     return value;
   }
   public Variable var() { return var; }
   public String toString() { return "[" + var + ", " + value + ", " + susp + "]"; }
 }

 /** Defines an operation that looks up the values of symbols in the environment (the host).  It works for all forms
  *  of Bindings: callByValue, callByName, callByNeed.
  */
 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; }

   public JamVal forEmpty(Empty<Binding> e) { throw new EvalException("variable " + var + " is unbound"); }

   public JamVal forCons(Cons<Binding> c) {
     // System.err.println("forCons in LookUpVisitor invoked; c = " + c);
     Binding b = c.first();
     if (var == b.var()) return b.value();
     return c.rest().accept(this);
   }
 }

 /** The interface supported by various evaluation policies (call-by-value, call-by-name, and call-by-need).
  *  Constructing a new Binding only requires an EvalVisitor (and not an environment) because the environment is
  *  embedded within the EvalVisitor.  Hence as an EvalPolicy is used to interpret an expression, the passed
  *  EvalVisitor will change (!) as the environment changes.  An EvalPolicy should NOT directly reference an
  *  EvalVisitor.
  */
 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);
 }

 /** Defines an operation that evaluates Jam ASTs using a specific EvalPolicy. */
 static class FlexEvalVisitor implements EvalVisitor {

   // Assumes that: (i)   OpTokens are unique.
   //               (ii)  Variable objects are unique: v1.name.equals(v.name) => v1 == v2.
   //               (iii) The only objects used as boolean values are BoolConstant.TRUE and BoolConstant.FALSE
   // Hence, "==" can be used to compare Variable objects, OpTokens, and BoolConstants

   PureList<Binding> env;
   EvalPolicy evalPolicy;

   private FlexEvalVisitor(PureList<Binding> e, EvalPolicy ep) { env = e; evalPolicy = ep; }

   public FlexEvalVisitor(EvalPolicy ep) { this(new Empty<Binding>(), ep); }

   public EvalVisitor newVisitor(PureList<Binding> e) { return new FlexEvalVisitor(e, evalPolicy); }

   public Binding newBinding(Variable var, AST ast) { return evalPolicy.newBinding(var, ast, this); }

   public PureList<Binding> env() { return env; }

   /* EvalVisitor methods */
   public JamVal forBoolConstant(BoolConstant b) { return b; }
   public JamVal forIntConstant(IntConstant i) { return i; }
   public JamVal forNullConstant(NullConstant n) { return JamEmpty.ONLY; }

   public JamVal forVariable(Variable v) {
     // System.err.println("forVariable invoked in EvalVisitorProxy; v = " + v);
     return env.accept(new LookupVisitor(v));
   }
   public JamVal forPrimFun(PrimFun f) { return f; }
   public JamVal forUnOpApp(UnOpApp u) {
     return u.rator().accept(new StandardUnOpVisitor(u.arg().accept(this)));
   }
   public JamVal forBinOpApp(BinOpApp b) {
     return b.rator().accept(new StandardBinOpVisitor(b.arg1(), b.arg2(), this));
   }
   public JamVal forApp(App a) {
     JamVal rator = a.rator().accept(this);
     if (rator instanceof JamFun)
       return ((JamFun) rator).accept(new FunVisitor(a.args(), this, StandardPrimFunFactory.ONLY));

     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);
   }
   public JamVal forLet(Let l) { /* let semantics */
     Def[] defs = l.defs();
     int n = defs.length;

     Variable[] vars = new Variable[n];
     for (int i = 0; i < n; i++) vars[i] = defs[i].lhs();

     AST[] exps =  new AST[n];
     for (int i = 0; i < n; i++) exps[i] = defs[i].rhs();

     // construct newEnv for Let body; vars are bound to corresponding values or potential values using evalVisitor
     PureList<Binding> newEnv = env;
     for (int i = n-1; i >= 0; i--) newEnv = newEnv.cons(newBinding(vars[i], exps[i]));

     return l.body().accept(newVisitor(newEnv));
   }
 }

 /* Visitors implementating callByValue, callByName, callByNeed */
 static ASTVisitor<JamVal> nameEvalVisitor = new FlexEvalVisitor(CallByName.ONLY);
 static ASTVisitor<JamVal> valueEvalVisitor = new FlexEvalVisitor(CallByValue.ONLY);
 static ASTVisitor<JamVal> needEvalVisitor = new FlexEvalVisitor(CallByNeed.ONLY);

 /** Defines an operation that evaluates a function application using the specified EvalVisitor. */
 static class FunVisitor implements JamFunVisitor<JamVal> {

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

   /** evaluation visitor */
   EvalVisitor evalVisitor;

   /** PrimFun visitor */
   PrimFunVisitorFactory primFunFactory;

   FunVisitor(AST[] asts, EvalVisitor ev, PrimFunVisitorFactory pff) {
     args = asts;
     evalVisitor = ev;
     primFunFactory = pff;
   }

   /* visitor methods */
   public JamVal forJamClosure(JamClosure closure) {
     Map map = closure.body();

     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 body using JamClosure env
     PureList<Binding> newEnv = closure.env();
     for (int i = n-1; i >= 0; i--) newEnv = newEnv.cons(evalVisitor.newBinding(vars[i], args[i]));

     return map.body().accept(evalVisitor.newVisitor(newEnv));
   }

   public JamVal forPrimFun(PrimFun primFun) {
     return primFun.accept(primFunFactory.newVisitor(evalVisitor, args));
   }
 }

 static class CallByValue implements EvalPolicy {

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

   /** Constructs binding of var to value of arg in ev */
   public Binding newBinding(Variable var, AST arg, EvalVisitor ev) { return new ValueBinding(var, arg.accept(ev)); }
 }

 static class CallByName implements EvalPolicy {
   public static final CallByName ONLY = new CallByName();
   private CallByName() {}

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

 static class CallByNeed implements EvalPolicy {
   public static final CallByNeed ONLY = new CallByNeed();
   private CallByNeed() {}

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

 static class StandardUnOpVisitor implements UnOpVisitor<JamVal> {
   private JamVal val;
   StandardUnOpVisitor(JamVal jv) { val = jv; }

   private IntConstant checkInteger(UnOp op) {
     if (val instanceof IntConstant) return (IntConstant) val;
     throw new EvalException("Unary operator `" + op + "' applied to non-integer " + val);
   }

   private BoolConstant checkBoolean(UnOp op) {
     if (val instanceof BoolConstant) return (BoolConstant) val;
     throw new EvalException("Unary operator `" + op + "' applied to non-boolean " + val);
   }

   public JamVal forUnOpPlus(UnOpPlus op) { return checkInteger(op); }
   public JamVal forUnOpMinus(UnOpMinus op) {
     return new IntConstant(- checkInteger(op).value());
   }
   public JamVal forOpTilde(OpTilde op) { return checkBoolean(op).not(); }
   // public JamVal forOpBang(OpBang op) { return ... ; }  // Supports addition of ref cells to Jam
   // public JamVal forOpRef(OpRef op) { return ... ; }    // Supports addition of ref cells to Jam
 }

 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; }

   private IntConstant evalIntegerArg(AST arg, BinOp b) {
     JamVal val = arg.accept(evalVisitor);
     if (val instanceof IntConstant) return (IntConstant) val;
     throw new EvalException("Binary operator `" + b + "' applied to non-integer " + val);
   }

   private BoolConstant evalBooleanArg(AST arg, BinOp b) {
     JamVal val = arg.accept(evalVisitor);
     if (val instanceof BoolConstant) return (BoolConstant) val;
     throw new EvalException("Binary operator `" + b + "' applied to non-boolean " + val);
   }

   public JamVal forBinOpPlus(BinOpPlus op) {
     return new IntConstant(evalIntegerArg(arg1,op).value() + evalIntegerArg(arg2,op).value());
   }
   public JamVal forBinOpMinus(BinOpMinus op) {
     return new IntConstant(evalIntegerArg(arg1,op).value() - evalIntegerArg(arg2,op).value());
   }

   public JamVal forOpTimes(OpTimes op) {
     return new IntConstant(evalIntegerArg(arg1,op).value() * evalIntegerArg(arg2,op).value());
   }

   public JamVal forOpDivide(OpDivide op) {
     return new IntConstant(evalIntegerArg(arg1,op).value() / evalIntegerArg(arg2,op).value());
   }

   public JamVal forOpEquals(OpEquals op) {
     JamVal val1 = arg1.accept(evalVisitor);
     JamVal val2 = arg2.accept(evalVisitor);
     return BoolConstant.toBoolConstant(val1.equals(val2));
   }

   public JamVal forOpNotEquals(OpNotEquals op) {
     return BoolConstant.toBoolConstant(! arg1.accept(evalVisitor).equals(arg2.accept(evalVisitor)));
   }

   public JamVal forOpLessThan(OpLessThan op) {
     return BoolConstant.toBoolConstant(evalIntegerArg(arg1,op).value() < evalIntegerArg(arg2,op).value());
   }

   public JamVal forOpGreaterThan(OpGreaterThan op) {
     return BoolConstant.toBoolConstant(evalIntegerArg(arg1,op).value() > evalIntegerArg(arg2,op).value());
   }

   public JamVal forOpLessThanEquals(OpLessThanEquals op) {
     return BoolConstant.toBoolConstant(evalIntegerArg(arg1,op).value() <= evalIntegerArg(arg2,op).value());
   }

   public JamVal forOpGreaterThanEquals(OpGreaterThanEquals op) {
     return BoolConstant.toBoolConstant(evalIntegerArg(arg1,op).value() >= evalIntegerArg(arg2,op).value());
   }

   public JamVal forOpAnd(OpAnd op) {
     BoolConstant b1 = evalBooleanArg(arg1,op);
     if (b1 == BoolConstant.FALSE) return BoolConstant.FALSE;
     return evalBooleanArg(arg2,op);
   }
   public JamVal forOpOr(OpOr op) {
     BoolConstant b1 = evalBooleanArg(arg1,op);
     if (b1 == BoolConstant.TRUE) return BoolConstant.TRUE;
     return evalBooleanArg(arg2,op);
   }
   // public JamVal forOpGets(OpGets op) { return ... ; }  // Supports addition of ref cells to Jam
 }

 interface PrimFunVisitorFactory {
   PrimFunVisitor<JamVal> newVisitor(EvalVisitor ev, AST[] args);
 }

 static class StandardPrimFunFactory implements PrimFunVisitorFactory {
   public static StandardPrimFunFactory ONLY = new StandardPrimFunFactory();
   private StandardPrimFunFactory() {}

   public PrimFunVisitor<JamVal> newVisitor(EvalVisitor ev, AST[] args) {
     return new StandardPrimFunVisitor(ev, args);
   }

   static private class StandardPrimFunVisitor implements PrimFunVisitor<JamVal> {
     EvalVisitor evalVisitor;
     AST[] args;

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

     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);
       return vals;
     }

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

     private JamCons evalJamConsArg(AST arg, String fun) {
       JamVal val = arg.accept(evalVisitor);
       if (val instanceof JamCons) return (JamCons) val;
       throw new EvalException("Primitive function `" + fun + "' applied to argument " + val +
                               " that is not a JamCons");
     }

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

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

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

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

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

     public JamVal forConsPrim() {
       JamVal[] vals = evalArgs();
       if (vals.length != 2) return primFunError("cons");
       if (vals[1] instanceof JamList) return new JamCons(vals[0], (JamList) vals[1]);
       throw new EvalException("Second argument " + vals[1] + " to `cons' is not a JamList");
     }

     public JamVal forArityPrim() {
       JamVal[] vals = evalArgs();
       if (vals.length != 1) return primFunError("arity");
       if (! (vals[0] instanceof JamFun) ) throw new EvalException("arity applied to argument " + vals[0]);
       return ((JamFun) vals[0]).accept(ArityVisitor.ONLY);
     }

     public JamVal forFirstPrim() { return evalJamConsArg(args[0], "first").first(); }
     public JamVal forRestPrim() { return evalJamConsArg(args[0], "rest").rest(); }

     static private class ArityVisitor implements JamFunVisitor<IntConstant> {
       static public ArityVisitor ONLY = new ArityVisitor();
       private ArityVisitor() {}
       public IntConstant forJamClosure(JamClosure jc) { return new IntConstant(jc.body().vars().length); }
       public IntConstant forPrimFun(PrimFun jpf) { return jpf.accept(PrimArityVisitor.ONLY); }
     }

     static private class PrimArityVisitor implements PrimFunVisitor<IntConstant> {
       static public PrimArityVisitor ONLY = new PrimArityVisitor();
       private PrimArityVisitor() {}

       public IntConstant forFunctionPPrim() { return new IntConstant(1); }
       public IntConstant forNumberPPrim() { return new IntConstant(1); }
       public IntConstant forListPPrim() { return new IntConstant(1); }
       public IntConstant forConsPPrim() { return new IntConstant(1); }
       public IntConstant forNullPPrim() { return new IntConstant(1); }
       public IntConstant forArityPrim() { return new IntConstant(1); }
       public IntConstant forConsPrim() { return new IntConstant(2); }
       public IntConstant forFirstPrim() { return new IntConstant(1); }
       public IntConstant forRestPrim() { return new IntConstant(1); }
     }
   }
 }

 public static void main(String[] args) throws IOException {
   Parser p;
   if (args.length == 0) {
     System.out.println("Usage: java Interpreter <filename> { value | name | need }");
     return;
   }
   p = new Parser(args[0]);
   AST prog = p.parse();
   System.out.println("Parse tree is: " + prog);
   Interpreter i = new Interpreter(p);
   if (args.length == 1) {
     System.out.println("Call-by-value Answer is: " + i.callByValue(prog));
     System.out.println("Call-by-name Answer is: " + i.callByName(prog));
     System.out.println("Call-by-need Answer is: " + i.callByNeed(prog));
   }
   else if (args[1].equals("value")) System.out.println("Call-by-value Answer is: " + i.callByValue(prog));
   else if (args[1].equals("need")) System.out.println("Call-by-need Answer is: " + i.callByNeed(prog));
   else System.out.println("Call-by-name Answer is: " + i.callByName(prog));
 }
}

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