/* -------------------------------------------------------------------*/

public class jbclasses
{

public static stmtlist cons(stmt h, stmtlist t) 	// Syntactic Sugar
	{ return (new stmtlist(h,t)); }


public static abstract class expr    	// expressions class
{ 
  abstract expr eval(env e);  // every expr subclass has an eval method
                              // relative to an environment
  abstract String typecheck(SymbolTable ST);  // STATIC type checking
}


/* atomic expression classes: */
public static class boolexp extends expr
{  public boolean b;          // public for convenience sake!
   public boolexp(boolean x) { b = x; }
   expr eval(env e) { return this; }    // expression already atomic
   public String toString() 
	{ return ("" + b); }  // only ATOMIC expr's can print

   String typecheck(SymbolTable ST) { return "boolean"; }
}

public static class strexp extends expr
{  public String s;          // public for convenience sake!
   public strexp(String x) { s = x; }
   expr eval(env e) { return this; }    // expression already atomic
   public String toString() { return s; }
   String typecheck(SymbolTable ST) { return "string"; }
}

public static class intexp extends expr
{  public int n;          // public for convenience sake!
   public intexp(int x) { n = x; }
   expr eval(env e) { return this; }    // expression already atomic
   public String toString() { return ("" + n); }
   String typecheck(SymbolTable ST) { return "integer"; }
}

/* non-atomic expression classes: */
public static class sumexp extends expr
{  expr s1, s2;
   public sumexp(expr x, expr y) { s1 = x; s2 = y; }
   expr eval(env e) 
    { if ((s1 instanceof intexp) && (s2 instanceof intexp))
		return new intexp(((intexp) s1).n + ((intexp) s2).n);
	else
	  	return (new sumexp(s1.eval(e), s2.eval(e))).eval(e);
    }
   String typecheck(SymbolTable ST) 
    { if ( (s1.typecheck(ST).equals("integer")) &&
	   (s2.typecheck(ST).equals("integer")) )
	return "integer";
      else return "notype";
    }
     
}

public static class multexp extends expr
{  expr s1, s2;
   public multexp(expr x, expr y) { s1 = x; s2 = y; }
   expr eval(env e) 
    { if ((s1 instanceof intexp) && (s2 instanceof intexp))
		return new intexp(((intexp) s1).n * ((intexp) s2).n);
	else
	  	return (new multexp(s1.eval(e), s2.eval(e))).eval(e);
    }
   String typecheck(SymbolTable ST) 
    { if ( (s1.typecheck(ST).equals("integer")) &&
	   (s2.typecheck(ST).equals("integer")) )
	return "integer";
      else return "notype";
    }
}

public static class eqexp extends expr     // equality expressions (for ints!)
{ expr s1, s2;
  public eqexp(expr x, expr y) { s1 = x; s2 = y; }
  expr eval(env e)
   { if ((s1 instanceof intexp) && (s2 instanceof intexp))
	return (new boolexp(((intexp) s1).n == ((intexp) s2).n ));
      else
	return (new eqexp(s1.eval(e), s2.eval(e))).eval(e);
   }
  String typecheck(SymbolTable ST) 
    { if (s1.typecheck(ST).equals(s2.typecheck(ST)))
	return "boolean";
      else return "notype";
    }
}

public static class andexp extends expr     // logical AND expressions
{ expr s1, s2;
  public andexp(expr x, expr y) { s1 = x; s2 = y; }
  expr eval(env e)
   { if ((s1 instanceof boolexp) && (s2 instanceof boolexp))
	return (new boolexp(((boolexp) s1).b && ((boolexp) s2).b ));
      else
	return (new andexp(s1.eval(e), s2.eval(e))).eval(e);
   }
  String typecheck(SymbolTable ST) 
    { if ( (s1.typecheck(ST).equals("boolean")) &&
	   (s2.typecheck(ST).equals("boolean")) )
	return "boolean";
      else return "notype";
    }
} 

public static class negexp extends expr	// logical NOT expressions
{ expr s;
  public negexp(expr x) { s = x; }
  expr eval(env e)
   { if (s instanceof boolexp) 
      return (new boolexp(!(((boolexp) s).b)));
        else return (new negexp(s.eval(e))).eval(e);
   }
  String typecheck(SymbolTable ST) 
    { if (s.typecheck(ST).equals("boolean"))
	return "boolean";
      else return "notype";
    }
}

/*
public static class arrayexp extends expr // subscripts A[i]
{ String name;  
  expr index;
  expr[] A;
  public arrayexp(int size) { A = new expr[size]; }  // not always called!
  public arrayexp(String B, expr i) { name = B;  index = i; }
  expr eval(env e)
    { return (A[(int) (index.eval(e)).n]).eval(e); }
} // arrayexp

public static class arraydec extends expr  // array declaration
{ int size;   // no nested expressions here!
  public arraydec(String s, int i) { aid = s;  size = i; }
  expr eval(env e) 
    { return (new arrayexp(size)); }
}


*/  //array expressions left out for now 


// And now for the all-important Variable Expression:
public static class varexp extends expr
{ String v;
  public varexp(String x) { v = x; }
  expr eval(env e) { return e.lookup(v); }

  String typecheck(SymbolTable ST) 
    { return ST.lookup(v); }
}


// The environment class:
public static class bindings		  // a list of variable-value bindings
{ String varname;
  expr   varval;    // it is implicit here that varval is atomic
  bindings cdr;
  public bindings(String s, expr v, bindings rest)
	{ varname = s; varval = v; cdr = rest; }
}

public static class env
{ bindings start; 
  private static expr reclookup(String v, bindings b)
    { if (b == null) return (new intexp(0));  // default value = 0 in jBASIC
        else if (v.equals(b.varname)) return b.varval;
          else return reclookup(v,b.cdr);
    }
  public expr lookup(String v) { return reclookup(v,start); }

  private static bindings change(String v, expr ep, bindings bds)
    { if (bds == null) return (new bindings(v,ep,null));
        else
          if (v.equals(bds.varname))
		{ bds.varval = ep; 
	 	  return bds; }     // binding changed
	   else { bds.cdr = change(v,ep,bds.cdr);
		  return bds; }
    }
  public void bind(String v, expr e) { start = change(v,e,start); }
} // end of class env


/* true term trees not possible because of looping pointers!!!!! */



/* statments */
public static abstract class stmt  	// statements class
{
  abstract void execute(prog p, env e);  // every subclass can be executed
 					 // prog param needed for goto's
  abstract boolean typecheck(SymbolTable ST);
}


public static class labelst extends stmt   // labels are statements by themselves
{ String label;
  public labelst(String l) { label = l; }
  void execute(prog p, env e) {/* do nothing! */}
  boolean typecheck(SymbolTable ST)  { return true; }
}

public static class printst extends stmt   // print statements
{ expr pexp;   // stuff to be printed
  public printst(expr e)  { pexp = e; }
  void execute(prog p, env e) { System.out.print(pexp.eval(e)); }
  boolean typecheck(SymbolTable ST)  { return true; }
    // alternatively, see if pexp is a printable expression
}

public static class assignst extends stmt  // assignment statements
{ String var;
  expr val;
  public assignst(String v, expr e) { var = v; val = e; }
  void execute(prog p, env e) { e.bind(var,val.eval(e)); }
  boolean typecheck(SymbolTable ST)  
    { String t1 = ST.lookup(var);
      String t2 = val.typecheck(ST);
      boolean answer = t1.equals(t2);
      if (!answer) System.out.println("You can't assign " + t2 +
	"s to " + t1 + "s you moron! This isn't C!");
      return answer;
    }
	  
}

public static class gotost extends stmt    // goto statement
{ String target;    // target label
  public gotost(String s) { target = s; }
  void execute(prog p, env e) { p.JUMP(target); }
  boolean typecheck(SymbolTable ST)  { return true; }
}

public static class ifst extends stmt	    // if-the statement
{ expr condition;
  stmt st;
  public ifst(expr c, stmt s) { condition = c; st = s; }
  void execute(prog p, env e)
    { boolexp tvalue = (boolexp) condition.eval(e);
      if (tvalue.b) st.execute(p,e);
    }
  boolean typecheck(SymbolTable ST)  
    { return ( (condition.typecheck(ST).equals("boolean")) && 
	       st.typecheck(ST) );
    }
}

public static class whilest extends stmt    // while loop statement
{ expr condition;
  stmt st;
  public whilest(expr c, stmt s) { condition = c; st = s; }
  void execute(prog p, env e)
    {  /* JAVA while used to implement JBASIC while  */
       while (((boolexp) condition.eval(e)).b)
              st.execute(p,e);
    }
  boolean typecheck(SymbolTable ST)  
    { return ( (condition.typecheck(ST).equals("boolean")) && 
	       st.typecheck(ST) );
    }
}  // end of whilest

public static class declst extends stmt    // declaration statement
{ String id;
  String type;
  public declst(String i, String t) { id=i; type=t; }
  void execute(prog p, env e) {}  // nothing for now

  boolean typecheck(SymbolTable ST)
   {if (!(type.equals("string") || type.equals("integer") ||
	   type.equals("boolean")))
	{ System.err.println("Invalid type: " + type);
          return false; }
     else
       { ST.insert(id,type);   // add to symbol table!
         return true;
       }
   }// end of typecheck
}  // end of declst

public static class scopest extends stmt  // scoped statement
{ stmtlist body;
  scopest(stmtlist l) { body=l; }
  void execute(prog p, env e)  // NEW ACTIVATION RECORD NOT CREATED!
  {  stmtlist LPC;   //local program counter
       for(LPC = body; LPC != null; LPC = LPC.cdr)
         LPC.car.execute(p,e);
  }
  
  boolean typecheck(SymbolTable ST)
    { ST.pushframe();  // create new frame!
      boolean answer = true;
      stmtlist LPC;   //local program counter
      for(LPC = body; LPC != null; LPC = LPC.cdr)
         answer = answer && (LPC.car.typecheck(ST));
      ST.popframe();   // exit scope!
      return answer;
    }
} // end of scopest



/*  The program class */
public static class stmtlist
{ stmt car;
  stmtlist cdr;
  public stmtlist(stmt h, stmtlist t) { car = h; cdr = t; }
}

public static class prog			
{ stmtlist statements;		// Source Code. Always keep a copy for gotos.
  env RAM = new env();		// Random Access Memory
  stmtlist PC;			// Program Counter Register
  SymbolTable ST;		// Symbol table for type checking
  public prog(stmtlist sl) { statements = sl; }

  private stmtlist findlabel(String l)  // returns subprogram at a label
    { stmtlist current = statements;    // needed for goto statements
      stmtlist answer = null;
      while (current != null)
       {
	 if ((current.car instanceof labelst) &&
	    (((labelst) current.car).label.equals(l)))
	      { answer = current; 
		current = null; }
	   else current = current.cdr;
       }
      return answer;
    }
  public void JUMP(String l)    //  Changes PC
    { PC = findlabel(l); }

  public void run()		// Run the program!
    { env RAM = new env();	// Clear Memory
      PC = statements;		// Set PC to start of source code
      while (PC != null)
	{ PC.car.execute(this, RAM);
	  PC = PC.cdr;		// Increment PC
        }
    }  // end of run

  public boolean typecheck()
    { ST = new SymbolTable();
      ST.pushframe();  // creates empty frame
      boolean answer = true;
      for(stmtlist c=statements;c!=null;c=c.cdr) // typecheck statements
	answer = answer && ( c.car.typecheck(ST) );
      return answer;
    } // end typecheck()

        
}  // end of class prog


} // end of jbclasses wrapper class




/* symbol table classes */

class Frame
{ String id;     // will be ID for tiger
  String type;   // will be type "TYPE" for tiger
  Frame tail;
  Frame(String i, String t, Frame n)
   { id=i; type=t; tail=n; }
}


class StackFrame
{ Frame head;
  StackFrame tail;
  StackFrame(Frame h, StackFrame t) { head=h; tail=t; }
}


class SymbolTable
{ StackFrame FramesTOS;
  
  public void pushframe()
   { FramesTOS = new StackFrame(null,FramesTOS); }

  public void popframe()
   { if (FramesTOS != null) FramesTOS = FramesTOS.tail; }

  public void insert(String id, String type)
   { FramesTOS.head = 
       new Frame(id,type,FramesTOS.head);
   }

  public String lookup(String id)  // returns type of id
   { boolean found = false;
     String answer = "notype";   // "notype" is reserved!
     StackFrame currentFrame = FramesTOS;
     Frame current;
     while ( (currentFrame != null) && !(found) )  // look through all frames
      { 
	current = currentFrame.head;
        while ((current != null) && !(found))      // look through one frame
         {
          if (current.id.equals(id))  // compare id's
		{ answer = current.type;
	          found = true;
 		}
          current = current.tail;  // advance within frame
         } // end inner while

        currentFrame = currentFrame.tail;  // advance entire frame

      } // end outer while

     return answer;
    } // end lookup

} // end class SymbolTable