/**************************************************************************/
/***                                                                    ***/
/***                           Scheme.java                              ***/
/***                                                                    ***/
/***      A simple EOPL-style scheme interpreter written in Java        ***/
/***             C311 -- Programming Languages -- Spring 98             ***/
/***                                                                    ***/
/**************************************************************************/

import java.io.*;
import java.lang.*;
import java.util.*;

/**************************************************************************/
/***                            Environments                            ***/
/**************************************************************************/

// As always, an environment maintains a mapping from variable names
// to values. Notice that the extend method clones a new hash
// table to preserve the call by value semantics.

class Env {
  private Hashtable table;
  public Env() { table = new Hashtable(); }
  public Env(Vector vars,Vector vals,Hashtable h) {
    table = (Hashtable)h.clone();
    Enumeration evars = vars.elements();
    Enumeration evals = vals.elements();
    while (evars.hasMoreElements()) {
      Vector box = new Vector();
      box.addElement(evals.nextElement());
      table.put(evars.nextElement(),box);
    }
  }

  private void extendPrim(String opname,int op) {
    PrimValue p = new PrimValue(opname,op);
    Vector box = new Vector();
    box.addElement(p);
    table.put(opname,box);
  }

  static public Env initEnv() {
    Env env = new Env();
    env.extendPrim("+",PrimValue.PLUS);
    env.extendPrim("-",PrimValue.MINUS);
    env.extendPrim("*",PrimValue.TIMES);
    env.extendPrim("/",PrimValue.DIVIDE);
    env.extendPrim("<",PrimValue.LESS);
    env.extendPrim(">",PrimValue.GREATER);
    env.extendPrim("=",PrimValue.EQUAL);
    env.extendPrim("add1",PrimValue.ADD1);
    env.extendPrim("sub1",PrimValue.SUB1);
    env.extendPrim("zero?",PrimValue.ZERO);
    env.extendPrim("cons",PrimValue.CONS);
    env.extendPrim("list",PrimValue.LIST);
    env.extendPrim("car",PrimValue.CAR);
    env.extendPrim("cdr",PrimValue.CDR);
    env.extendPrim("null?",PrimValue.NULL);
    return env;
  }
  public Env extend(Vector vars,Vector vals) {
    return new Env(vars,vals,table);
  }
  public Vector apply(String var) {
    return (Vector)table.get(var);
  }
}

/**************************************************************************/
/***                               Values                               ***/
/**************************************************************************/

// Values are the results returned by the evaluator.  There is one
// abstract class Value, with a subclass for each of the different
// kind of values. ProcValue is another abstract class that
// represents values that can be in operator positions. It
// declares the apply method (apply-proc in our Scheme
// interpreters.) 

abstract class Value {
  public void println() { print(); System.out.println(""); }
  abstract public void print();
};

abstract class ProcValue extends Value {
  abstract public Value apply(Vector args);
};

class ClosureValue extends ProcValue {
  private Vector formals;
  private Exp body;
  private Env env;
  public ClosureValue(Vector _formals,Exp _body,Env _env) {
    formals=_formals;
    body=_body;
    env=_env;
  }
  public void print() { System.out.print("<procedure>"); }
  public Value apply(Vector args) {
    Env newenv = env.extend(formals,args);
    return body.eval(newenv);
  }
}

class PrimValue extends ProcValue {
  static final public int PLUS=0;
  static final public int MINUS=1;
  static final public int TIMES=2;
  static final public int DIVIDE=3;
  static final public int LESS=4;
  static final public int GREATER=5;
  static final public int EQUAL=6;
  static final public int ADD1=7;
  static final public int SUB1=8;
  static final public int ZERO=9;

  static final public int CONS=10;
  static final public int LIST=11;
  static final public int CAR=12;
  static final public int CDR=13;
  static final public int NULL=14;

  private String opname;
  private int op;
  public PrimValue(String _opname,int _op) { opname=_opname;op=_op; }
  public void print() {
    System.out.print("<system procedure "+opname+">");
  }

  private Value getVal(Vector args,int i) {
    return (Value)args.elementAt(i);
  }

  private int getInt(Vector args,int i) {
    return ((IntValue)getVal(args,i)).get();
  }

  private PairValue getPair(Vector args,int i) {
    return (PairValue)getVal(args,i);
  }

  public Value apply(Vector args) {
    switch (op) {
    case PLUS: {
      int i1 = getInt(args,0);
      int i2 = getInt(args,1);
      return new IntValue(i1+i2);
    } case MINUS: {
      int i1 = getInt(args,0);
      int i2 = getInt(args,1);
      return new IntValue(i1-i2);
    } case TIMES: {
      int i1 = getInt(args,0);
      int i2 = getInt(args,1);
      return new IntValue(i1*i2);
    } case DIVIDE: {
      int i1 = getInt(args,0);
      int i2 = getInt(args,1);
      return new IntValue(i1/i2);
    } case LESS: { 
      /* blank */
      int i1 = getInt(args, 0);
      int i2 = getInt(args, 1);
      return new BoolValue(i1 < i2);
    } case GREATER: { 
      /* blank */ 
      int i1 = getInt(args, 0);
      int i2 = getInt(args, 1);
      return new BoolValue(i1 > i2);
    } case EQUAL: {
      /* blank */
      int i1 = getInt(args, 0);
      int i2 = getInt(args, 1);
      return new BoolValue(i1 == i2);
    } case ADD1: {
      int i1 = getInt(args,0);
      return new IntValue(i1+1);
    } case SUB1: {
      int i1 = getInt(args,0);
      return new IntValue(i1-1);
    } case ZERO: { 
      /* blank */
      int i1 = getInt(args,0);
      return new BoolValue(i1 == 0);
    } case CONS: {
      Value v1 = getVal(args,0);
      Value v2 = getVal(args,1);
      return new PairValue(v1,v2);
    } case LIST: {
      if (args.isEmpty()) return new NullValue();
      else {
	Value v = getVal(args,0);
	args.removeElementAt(0);
	return new PairValue(v,apply(args));
      }
    } case CAR: {
      PairValue v = getPair(args,0);
      return v.car();
    } case CDR: {
      PairValue v = getPair(args,0);
      return v.cdr();
    } case NULL: { 
      /* blank */
      Value v = getVal(args,0);
      return new BoolValue(v.getClass() == new NullValue().getClass());
    } default: throw new EvalException("unknown primitive "+opname);
    }
  }
}

class IntValue extends Value {
  private int val;
  public IntValue(int _val) { val = _val; }
  public int get() { return val; }
  public void print() { System.out.print(val); }
}

// Added
class BoolValue extends Value {
  private boolean val;
  public BoolValue(boolean _val) { val = _val; }
  public boolean get() { return val; }
  public void print() { System.out.print(val); }
}

class VoidValue extends Value {
  public void print() { System.out.print("<void>"); }
  public void println() { System.out.print(""); }
}

class NullValue extends Value {
  public void print() {
    System.out.print("()");
  }
}

class PairValue extends Value {
  private Value v1;
  private Value v2;
  public PairValue(Value _v1,Value _v2) { v1=_v1;v2=_v2; }
  public void print() {
    System.out.print("(");
    v1.print();
    System.out.print(" . ");
    v2.print();
    System.out.print(")");
  }
  public Value car() { return v1; }
  public Value cdr() { return v2; }
}

/**************************************************************************/
/***                            Expressions                             ***/
/**************************************************************************/

// Expressions are the input to the interpreter.  There is one
// abstract class Exp with a subclass for each expression constructor
// in the Scheme-subset that we are interpreting (lambda, application,
// begin, if, etc.).  Each subclass of Exp must provide an
// implementation of the eval method.

abstract class Exp {
  abstract public Value eval(Env env);

  // We provide evalRands as a static method of class Exp, since it is
  // needed by several subclasses
  static protected Vector evalRands(Vector rands,Env env) {
    Vector rs = (Vector)rands.clone();
    Vector args = new Vector();
    while (!rs.isEmpty()) {
      args.addElement(((Exp)rs.firstElement()).eval(env));
      rs.removeElementAt(0);
    }
    return args;
  }
};

class Varref extends Exp {
  private String var;
  public Varref(String _var) { var = _var; }
  public Value eval(Env env) {
    Vector v = env.apply(var);
    if (v == null) throw new EvalException("variable "+var+" undefined");
    return (Value)v.firstElement();
  }
}

class Lambda extends Exp {
  private Vector formals;
  private Exp body;
  public Lambda(Vector _formals,Exp _body) { formals=_formals;body=_body; }
  public Value eval(Env env) { return new ClosureValue(formals,body,env); }
}

class App extends Exp {
  private Exp rator;
  private Vector rands;
  public App(Exp _rator,Vector _rands) { rator=_rator;rands=_rands; }
  public Value eval(Env env) {
    ProcValue rat = (ProcValue)rator.eval(env);
    return rat.apply(evalRands(rands,env));
  }
}

class Num extends Exp {
  private int val;
  public Num(int _val) { val = _val; }
  public Value eval(Env env) { return new IntValue(val); }
}

// Added
class Bool extends Exp {
  private boolean val;
  public Bool(boolean _val) { val = _val; }
  public Value eval(Env env) { return new BoolValue(val); }
}

class Null extends Exp {
  public Value eval(Env env) { return new NullValue(); }
}

class Begin extends Exp {
  private Vector exps;
  public Begin(Vector _exps) { exps=_exps; }
  public Value eval(Env env) {
    return (Value)evalRands(exps,env).lastElement();
  }
}

// Need to add
/*
class IF extends Exp {
}
*/

class Let extends Exp {
  private Vector vars;
  private Vector exps;
  private Exp body;
  public Let(Vector _vars,Vector _exps,Exp _body) {
    vars=_vars;
    exps=_exps;
    body=_body;
  }
  public Value eval(Env env) {
    Env newenv = env.extend(vars,evalRands(exps,env));
    return body.eval(newenv);
  }
}

class Letrec extends Exp {
  private Vector vars;
  private Vector formalss;
  private Vector exps;
  private Exp body;
  public Letrec(Vector _vars,Vector _formalss,Vector _exps,Exp _body) {
    vars=_vars;
    formalss=_formalss;
    exps=_exps;
    body=_body;
  }
  public Value eval(Env env) {
    Enumeration e1 = vars.elements();
    Enumeration e2 = formalss.elements();
    Enumeration e3 = exps.elements();
    Vector zeros = new Vector();
    Vector bodyexps = new Vector();
    while (e1.hasMoreElements()) {
      zeros.addElement(new Num(0));
      String var = (String)e1.nextElement();
      Vector formals = (Vector)e2.nextElement();
      Exp exp = (Exp)e3.nextElement();
      bodyexps.addElement(new Set(var,new Lambda(formals,exp)));
    }
    bodyexps.addElement(body);
    Exp newexp = new Let(vars,zeros,new Begin(bodyexps));
    return newexp.eval(env);
  }
}

class Set extends Exp {
  private String var;
  private Exp exp;
  public Set(String _var,Exp _exp) { var=_var;exp=_exp; }
  public Value eval(Env env) {
    Vector v = env.apply(var);
    if (v==null) throw new EvalException("variable "+var+" undefined");
    v.setElementAt(exp.eval(env),0);
    return new VoidValue();
  }
}


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

/**************************************************************************/
/***                       Read-eval-print loop                         ***/
/**************************************************************************/

// The class Scheme is the top-level of the program.  It is
// responsible for parsing the command line to tell whether it should
// read from a file or the keyboard, and then starting a
// read-eval-print loop, repeatedly reading expressions, parsing them,
// evaluating them, and printing their results.

public class Scheme {

  static void doFile(String fname) {
    try {
      File file = new File(fname);
      FileInputStream inFile = new FileInputStream(file);
      InputStreamReader inStream = new InputStreamReader(inFile);
      char[] cbuf = new char[(int)file.length()];
      inStream.read( cbuf, 0, (int)file.length() );
      String contents = new String(cbuf);
      Parser p = new Parser(contents);
      Exp e = p.parseExp();
      Env env = Env.initEnv();
      while (e != null) {
	e.eval(env).println();
	e = p.parseExp();
      }
    } catch (FileNotFoundException e) {
      System.out.println(e.getMessage());
    } catch (EvalException e) {
      System.out.println(e.getMessage());
    } catch (IOException e) {
      System.out.println(e.getMessage());
    } catch (ParseException e) {
      System.out.println(e.getMessage());
    }
  }

  public static void main(String argv[]) {
    if (argv.length==1) {
      doFile(argv[0]);
      return;
    }
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    Env env = Env.initEnv();
    while (true) {
      System.out.print("> ");
      try {
	Parser p = new Parser(in.readLine());
	p.parseExp().eval(env).println();
      } catch (EvalException e) {
	System.out.println(e.getMessage());
      } catch (IOException e) {
	System.out.println(e.getMessage());
      } catch (ParseException e) {
	System.out.println(e.getMessage());
      }
    }
  }
}

/**************************************************************************/
/***                             Parsing                                ***/
/**************************************************************************/

// The parser takes strings and converts them to expressions.  You can
// ignore this part of the interpreter.

class Parser {

  final static int ID = 0;
  final static int IF = 1;
  final static int EOF = 2;
  final static int LET = 3;
  final static int OPENP = 4;
  final static int CLOSEP = 5;
  final static int LAMBDA = 6;
  final static int LETREC = 8;
  final static int SET = 9;
  final static int NUM = 10;
  final static int BEGIN = 11;
  final static int TRUE = 12;
  final static int FALSE = 13;
  final static int QUOTE = 14;

  static class Token {
    int label;
    Object value;
  }

  static Token t = new Token();
  static Token lookahead = null;
  StringTokenizer list;
  
  
  public Parser(String contents) {
    list = new StringTokenizer(contents, " '()\t\n", true);
  }

  private Vector parseVars() throws ParseException {
    if (Next().label != OPENP) throw new ParseException("Invalid exp223");
    Vector vars = new Vector();
    t = Next();
    while (t.label != CLOSEP) {
      if (t.label != ID) throw new ParseException("Invalid exp232");
      vars.addElement(t.value);
      t = Next();
    }
    return vars;
  }

  public Vector parseRands() throws ParseException {
    Vector rands = new Vector();
    t = Peek();
    while (t.label != CLOSEP) {
      if (t.label == EOF) {
        Next();
	throw new ParseException("Invalid exp23");
      }
      rands.addElement(parseExp());
      t = Peek();
    }
    return rands;
  }

  public Exp parseExp() throws ParseException {
    t = Next();
    Exp e;

    switch (t.label) {
    case EOF: return null;
    case NUM: return new Num(((Integer)t.value).intValue());
    case TRUE: return new Bool(true);
    case FALSE: return new Bool(false);
    case QUOTE: {
      if (Next().label != OPENP) throw new ParseException("Invalid exp211");
      if (Next().label != CLOSEP) throw new ParseException("Invalid exp212");
      return new Null();
    }
    case ID: return new Varref((String)t.value);
    case OPENP: {
      t = Peek();
      switch (t.label) {
       case IF: {
 	t = Next();
 	Exp e1 = parseExp();
 	Exp e2 = parseExp();
 	Exp e3 = parseExp();
 	e = null; // new IF(e1,e2,e3);
 	break;
       } 
      case LET: {
	t = Next();
	if (Next().label != OPENP) throw new ParseException("Invalid exp222");
	Vector vars = new Vector();
	Vector exps = new Vector();
	t = Peek();
	while (t.label != CLOSEP) {
	  t = Next();
	  if (t.label != OPENP) throw new ParseException("Invalid exp224");
	  t = Next();
	  if (t.label != ID) throw new ParseException("Invalid exp225");
	  vars.addElement(t.value);
	  exps.addElement(parseExp());
	  t = Next();
	  if (t.label != CLOSEP) throw new ParseException("Invalid exp226");
	  t = Peek();
	}
	Next();
	e = new Let(vars,exps,parseExp());
	break;
      } case LAMBDA: {
	t = Next();
	e = new Lambda(parseVars(),parseExp());
	break;
      } case LETREC: {
	t = Next();
	if (Next().label != OPENP) throw new ParseException("Invalid exp221");
	Vector vars = new Vector();
	Vector formalss = new Vector();
	Vector exps = new Vector();
	t = Peek();
	while (t.label != CLOSEP) {
	  t = Next();
	  if (t.label != OPENP) throw new ParseException("Invalid exp234");
	  t = Next();
	  if (t.label != ID) throw new ParseException("Invalid exp235");
	  vars.addElement(t.value);
	  formalss.addElement(parseVars());
	  exps.addElement(parseExp());
	  t = Next();
	  if (t.label != CLOSEP) throw new ParseException("Invalid exp236");
	  t = Peek();
	}
	Next();
	e = new Letrec(vars,formalss,exps,parseExp());
	break;
      } case SET: {
	t = Next();
	t = Next();
	if (t.label != ID) throw new ParseException("Invalid exp245");
	e = new Set((String)t.value,parseExp());
	break;
      } case BEGIN: {
	t = Next();
	e = new Begin(parseRands());
	break;
      } default: {
	e = new App(parseExp(),parseRands());
      }
      }
      if (Next().label != CLOSEP) throw new ParseException("Invalid exp3");
      return e;
    } default: throw new ParseException("Invalid exp4");

    }
  }

  private boolean alpha(char c) {
    return c=='=' || c=='?' || c=='+' || c=='-' || c=='*' || c=='/' ||
      c=='<' || c=='>' || Character.isLetter(c);
  }

  private Token Peek() throws ParseException {
    lookahead = Next();
    return lookahead;
  }

  private Token Next() throws ParseException {

    String next;

    if (lookahead != null) {
      t = lookahead;
      lookahead = null;
      return t;
    }

    try {
      next = list.nextToken();
    } catch (NoSuchElementException e) {
      t.label = EOF;
      return t;
    }
    
    while (next.equals(" ") || next.equals("\n") || next.equals("\t")) {
      try {
	next = list.nextToken();
      } catch (NoSuchElementException e) {
	t.label = EOF;
	return t;
      }
    }

    if ( next.equals("if") ) t.label = IF;
    else if ( next.equals("let") ) t.label = LET;
    else if ( next.equals("letrecproc") ) t.label = LETREC;
    else if ( next.equals("set!") ) t.label = SET;
    else if ( next.equals("lambda") )  t.label = LAMBDA;
    else if ( next.equals("begin") )  t.label = BEGIN;
    else if ( next.equals("(") )  t.label = OPENP;
    else if ( next.equals(")") )  t.label = CLOSEP;
    else if ( next.equals("#f") )  { t.label=FALSE; }
    else if ( next.equals("#t") )  { t.label=TRUE; }
    else if ( next.equals("'") )  { t.label=QUOTE; }
    
    else if (Character.isDigit(next.charAt(0)) ) {
      int len = next.length();
      for (int i = 1; i<len;) 
	if (! Character.isDigit(next.charAt(i++)) ) 
	  throw new ParseException("Invalid token1"); 
      t.label = NUM;
      t.value = Integer.valueOf(next);
    }

    else if (alpha(next.charAt(0))) {
      int len = next.length();
      for (int i = 1; i<len; i++)
	if (!alpha(next.charAt(i)) && !Character.isDigit(next.charAt(i))) 
	  throw new ParseException(" Invalid token2");
      t.label = ID;
      t.value = next;
    }
    return t;
  }

}

class ParseException extends Exception {
  public ParseException(String msg) {
    super(msg);
  }
}