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

/* Relies on the imported Token interface. */

/** Jam general AST type */
interface AST {
  public <T> T accept(ASTVisitor<T> v);
}

/** Visitor class for general AST type */
interface ASTVisitor<T> {
  T forBoolConstant(BoolConstant b);
  T forIntConstant(IntConstant i);
  T forNullConstant(NullConstant n);
  T forVariable(Variable v);
  T forPrimFun(PrimFun f);
  T forUnOpApp(UnOpApp u);
  T forBinOpApp(BinOpApp b);
  T forApp(App a);
  T forMap(Map m);
  T forIf(If i);
  T forLet(Let l);
}

/** Jam token type.  Contains the definitions of the actual token types which are subtypes */
interface Token {
  public <T> T accept(TokenVisitor<T> v);
  public String toString();
}

interface TokenVisitor<T> {
  T forBoolConstant(BoolConstant t);
  T forIntConstant(IntConstant t);
  T forNullConstant(NullConstant t);
  T forPrimFun(PrimFun t);
  T forVariable(Variable t);
  T forOp(Op t);
  T forKeyWord(KeyWord t);
  T forLeftParen(LeftParen t);
  T forRightParen(RightParen t);
  T forLeftBrack(LeftBrack t);
  T forRightBrack(RightBrack t);
  T forLeftBrace(LeftBrace t);
  T forRightBrace(RightBrace t);
  T forComma(Comma t);
  T forSemiColon(SemiColon t);
}

/** A simple prototype for TokenVisitors. */
abstract class AbstractTokenVisitor<T> implements TokenVisitor<T> {
  
  public abstract T forDefault(Token t);
  
  public T forBoolConstant(BoolConstant t) { return forDefault(t); }
  public T forIntConstant(IntConstant t)   { return forDefault(t); }
  public T forNullConstant(NullConstant t) { return forDefault(t); }
  public T forPrimFun(PrimFun t)           { return forDefault(t); }
  public T forVariable(Variable t)         { return forDefault(t); }
  public T forOp(Op t)                     { return forDefault(t); }
  public T forKeyWord(KeyWord t)           { return forDefault(t); }
  public T forLeftParen(LeftParen t)       { return forDefault(t); }
  public T forRightParen(RightParen t)     { return forDefault(t); }
  public T forLeftBrack(LeftBrack t)       { return forDefault(t); }
  public T forRightBrack(RightBrack t)     { return forDefault(t); }
  public T forLeftBrace(LeftBrace t)       { return forDefault(t); }
  public T forRightBrace(RightBrace t)     { return forDefault(t); }
  public T forComma(Comma t)               { return forDefault(t); }
  public T forSemiColon(SemiColon t)       { return forDefault(t); } 
}

/** A trivial concrete TokenVisitor. */
class DefaultTokenVisitor<T> extends AbstractTokenVisitor<T> {
  public T forDefault(Token t) {
    throw new ParseException("Bad token: " + t.toString());
  }
}


/** Jam term AST type */
interface Term extends AST {
  public <T> T accept(ASTVisitor<T> v);
}

/** Jam constant type */
interface Constant extends Term { public <T> T accept(ASTVisitor<T> v); }

/** Jam Boolean constant class */
class BoolConstant implements Token, Constant {
  private boolean value;
  private BoolConstant(boolean b) { value = b; }
  public static BoolConstant make(Boolean b) { return b ? TRUE : FALSE; }
  
  // ** singleton pattern **
  public static final BoolConstant FALSE = new BoolConstant(false);
  public static final BoolConstant TRUE = new BoolConstant(true);
  
  public boolean getValue() { return value; }
  
  public <T> T accept(ASTVisitor<T> v) { return v.forBoolConstant(this); }
  public <T> T accept(TokenVisitor<T> v) { return v.forBoolConstant(this); }
  public String toString() { return String.valueOf(value); }
}

/** Jam integer constant class */
class IntConstant implements Token, Constant {
  private int value;
  
  public IntConstant(int i) { value = i; }
  // duplicates can occur!
  
  public int getValue() { return value; }
  
  public <T> T accept(ASTVisitor<T> v) { return v.forIntConstant(this); }
  public <T> T accept(TokenVisitor<T> v) { return v.forIntConstant(this); }
  public String toString() { return String.valueOf(value); }
}

/** Jam null constant class, which is a singleton */
class NullConstant implements Token, Constant {
  public static final NullConstant ONLY = new NullConstant();
  private NullConstant() {}
  public <T> T accept(ASTVisitor<T> v) { return v.forNullConstant(this); }
  public <T> T accept(TokenVisitor<T> v) { return v.forNullConstant(this); }
  public String toString() { return "null"; }
}

/** Jam primitive function Class */
class PrimFun implements Token, Term {
  private String name;
  
  public PrimFun(String n) { name = n; }
  
  public String getName() { return name; }
  public <T> T accept(ASTVisitor<T> v) { return v.forPrimFun(this); }
  public <T> T accept(TokenVisitor<T> v) { return v.forPrimFun(this); }
  public String toString() { return name; }
}

/** Jam variable class.  Part of Term and Token composite hierarchies. */
class Variable implements Token, Term {
  private String name;
  public Variable(String n) { name = n; }
  
  public String getName() { return name; }
  public <T> T accept(ASTVisitor<T> v) { return v.forVariable(this); }
  public <T> T accept(TokenVisitor<T> v) { return v.forVariable(this); }
  public String toString() { return name; }
}

/** Jam operator class.  Only a Token class. */
class Op implements Token {
  private String symbol;
  private boolean isUnOp;
  private boolean isBinOp;
  public Op(String s, boolean iu, boolean ib) {
    symbol = s; isUnOp = iu; isBinOp = ib;
  }
  public Op(String s) {
    // isBinOp only!
    this(s,false,true);
  }
  public String getSymbol() { return symbol; }
  public boolean isUnOp() { return isUnOp; }
  public boolean isBinOp() { return isBinOp; }
  public String toString() { return symbol; }
  public <T> T accept(TokenVisitor<T> v) { return v.forOp(this); }
}

class KeyWord implements Token {
  private String name;
  
  public KeyWord(String n) { name = n; }
  public String getName() { return name; }
  public String toString() { return name; }
  public <T> T accept(TokenVisitor<T> v) { return v.forKeyWord(this); }  
}

/** Jam left paren token */
class LeftParen implements Token {
  public String toString() { return "("; }
  private LeftParen() {}
  public static final LeftParen ONLY = new LeftParen();
  public <T> T accept(TokenVisitor<T> v) { return v.forLeftParen(this); }
}

/** Jam right paren token */
class RightParen implements Token {
  public String toString() { return ")"; }
  private RightParen() {}
  public static final RightParen ONLY = new RightParen();
  public <T> T accept(TokenVisitor<T> v) { return v.forRightParen(this); }
}

/** Jam left bracket token */
class LeftBrack implements Token {
  public String toString() { return "["; }
  private LeftBrack() {}
  public static final LeftBrack ONLY = new LeftBrack();
  public <T> T accept(TokenVisitor<T> v) { return v.forLeftBrack(this); }
}

/** Jam right bracket token */
class RightBrack implements Token {
  public String toString() { return "]"; }
  private RightBrack() {}
  public static final RightBrack ONLY = new RightBrack();
  public <T> T accept(TokenVisitor<T> v) { return v.forRightBrack(this); }
}

/** Jam left brace token */
class LeftBrace implements Token {
  public String toString() { return "{"; }
  private LeftBrace() {}
  public static final LeftBrace ONLY = new LeftBrace();
  public <T> T accept(TokenVisitor<T> v) { return v.forLeftBrace(this); }
}

/** Jam right brace token */
class RightBrace implements Token {
  public String toString() { return "}"; }
  private RightBrace() {}
  public static final RightBrace ONLY = new RightBrace();
  public <T> T accept(TokenVisitor<T> v) { return v.forRightBrace(this); }
}

/** Jam comma token */
class Comma implements Token {
  public String toString() { return ","; }
  private Comma() {}
  public static final Comma ONLY = new Comma();
  public <T> T accept(TokenVisitor<T> v) { return v.forComma(this); }
}

/** Jam semi-colon token */
class SemiColon implements Token {
  public String toString() { return ";"; }
  private SemiColon() {}
  public static final SemiColon ONLY = new SemiColon();
  public <T> T accept(TokenVisitor<T> v) { return v.forSemiColon(this); }
}


// AST class definitions

/** Jam unary operator application class */
class UnOpApp implements AST {
  private Op rator;
  private AST arg;
  
  public UnOpApp(Op r, AST a) { rator = r; arg = a; }
  
  public Op getRator() { return rator; }
  public AST getArg() { return arg; }
  public <T> T accept(ASTVisitor<T> v) { return v.forUnOpApp(this); }
  public String toString() { return rator + " " + arg; }
}

/** Jam binary operator application class */
class BinOpApp implements AST {
  private Op rator;
  private AST arg1, arg2;
  
  public BinOpApp(Op r, AST a1, AST a2) { rator = r; arg1 = a1; arg2 = a2; }
  
  public Op getRator() { return rator; }
  public AST getArg1() { return arg1; }
  public AST getArg2() { return arg2; }
  public <T> T accept(ASTVisitor<T> v) { return v.forBinOpApp(this); }
  public String toString() { 
    return "(" + arg1 + " " + rator + " " + arg2 + ")"; 
  }
}

/** Jam map (closure) class */
class Map implements AST {
  private Variable[] vars;
  private AST body;
  
  public Map(Variable[] v, AST b) { vars = v; body = b; }
  public Map(ArrayList<Variable> v, AST b) { this(v.toArray(new Variable[v.size()]), b); }
  public Variable[] getVars() { return vars; }
  public AST getBody() { return body; }
  public <T> T accept(ASTVisitor<T> v) { return v.forMap(this); }
  public String toString() { 
    return "map " + ToString.toString(vars,",") + " to " + body ;
  }
}  

/** Jam function application class (rator must evaluate to PrimFun or Map)  */
class App implements AST {
  private AST rator;
  private AST[] args;
  
  public App(AST r, AST[] a) { rator = r; args = a; }
  public App(AST r, ArrayList<AST> a) { this(r, a.toArray(new AST[a.size()])); }
  
  public AST getRator() { return rator; }
  public AST[] getArgs() { return args; }
  
  public <T> T accept(ASTVisitor<T> v) { return v.forApp(this); }
  public String toString() { 
    if ((rator instanceof Variable) || (rator instanceof PrimFun))
      return rator + "(" + ToString.toString(args,", ") + ")"; 
    else
      return "(" +  rator + ")(" + ToString.toString(args,", ") + ")"; 
  }
}  

/** Jam if expression class */
class If implements AST {
  private AST test, conseq, alt;
  public If(AST t, AST c, AST a) { test = t; conseq = c; alt = a; }
  
  public AST getTest() { return test; }
  public AST getConseq() { return conseq; }
  public AST getAlt() { return alt; }
  public <T> T accept(ASTVisitor<T> v) { return v.forIf(this); }
  public String toString() { 
    return "if " + test + " then " + conseq + " else " + alt ; 
  }
}  

/** Jam let expression class */
class Let implements AST {
  private Def[] defs;
  private AST body;
  public Let(Def[] d, AST b) { defs = d; body = b; }
  public Let(ArrayList<Def> d, AST b) { this(d.toArray(new Def[d.size()]), b); }
  
  public <T> T accept(ASTVisitor<T> v) { return v.forLet(this); }
  public Def[] getDefs() { return defs; }
  public AST getBody() { return body; }
  public String toString() { 
    return "let " + ToString.toString(defs," ") + " in " + body; 
  }
}  

/** Jam definition class */
class Def {
  private Variable lhs;
  private AST rhs;  
  
  public Def(Variable l, AST r) { lhs = l; rhs = r; }
  public Variable getLhs() { return lhs; }
  public AST getRhs() { return rhs; }
  
  public String toString() { return lhs + " := " + rhs + ";"; }
}

/** String utility class */
class ToString {
  
  /** Prints array a with separator s between elements.   This method does NOT accept a == null, since null
    *  is NOT an array */
  public static String toString(Object[] a, String s) {
    StringBuffer result = new StringBuffer();
    for (int i = 0; i < a.length; i++) {
      if (i > 0) result.append(s);
      Object elt = a[i];
      String eltString = (elt instanceof Object[]) ?
        toString((Object[]) elt, s) : elt.toString();
      result.append(eltString);
    }
    return result.toString();
  }
}