package languages.macho ;

import languages.sexp._ ;


object MachoSyntax {
  import SExpSyntax._

  /* Concrete syntax matchers. */
  object SProgram {
    def unapply (sx : SExp) : Option[List[SExp]] = sx match {
      case L(S("program") :: sxs) => Some(sxs)
      case _ => None
    }
  }

  object SLabel {
    def unapply (sx : SExp) : Option[SExp] = sx match {
      case L(S("label") :: List(sxlab)) => Some(sxlab)
      case _ => None
    }
  }

  object SAssignment {
    def unapply (sx : SExp) : Option[(SExp,SExp)] = sx match {
      case L(S(":=") :: List(sxlhs,sxrhs)) => Some((sxlhs,sxrhs))
      case _ => None
    }
  }

  object SPrintLn {
    def unapply (sx : SExp) : Option[SExp] = sx match {
      case L(S("println") :: List(sxrhs)) => Some(sxrhs)
      case _ => None
    }
  }

  object SSkip {
    def unapply (sx : SExp) : Option[Unit] = sx match {
      case L(List(S("skip"))) => Some(())
      case _ => None
    }
  }

  object SIfGoto {
    def unapply (sx : SExp) : Option[(SExp,SExp)] = sx match {
      case L(List(S("if"),cond,S("goto"),target)) => Some((cond,target))
      case _ => None
    }
  }

  object SReturn {
    def unapply (sx : SExp) : Option[SExp] = sx match {
      case L(List(S("return"), rv)) => Some(rv)
      case _ => None
    }
  }

  object SGoto {
    def unapply (sx : SExp) : Option[SExp] = sx match {
      case L(List(S("goto"), lab)) => Some(lab)
      case _ => None
    }    
  }



  /* Abstract syntax nodes. */
  object SyntaxNode {
    private var maxId = 0 
    def allocId() : Int = {
      maxId += 1
      maxId
    }
  }

  trait SyntaxNode {
    val synId = SyntaxNode.allocId()
    override def hashCode : Int = synId
    override def equals (a : Any) = 
      if (a.isInstanceOf[SyntaxNode])
        { a.asInstanceOf[SyntaxNode].synId == this.synId }
      else
        { false }
  }

  case class Program (val stmts : List[Stmt]) {
    override def toString : String = 
      stmts mkString "\n"

    def toSExp : SExp = L(S("program") :: (stmts map (_.toSExp)))

    // Set the program.
    for (s <- stmts) {
      s.prog = this
    }

    // Build a label map.
    private val labStmts = for (s <- stmts if s.isInstanceOf[Lab]) yield {
      (s.asInstanceOf[Lab].lab, s)
    }

    val labMap = scala.collection.immutable.TreeMap[String,Stmt]() ++ labStmts

    // Set succ/pred fields.
    private def setFlows(stmts : List[Stmt]) : Unit = stmts match {
      case List() => {}
      case s1 :: s2 :: rest => {
        s1.succ = s2
        s2.pred = s1
        setFlows(s2 :: rest)
      }
      case s :: rest => {
      }
    }

    setFlows(stmts)

    // Set preds fields.
    for (s <- stmts) {
      for (succ <- s.succs) {
        succ.preds = s :: succ.preds
      }
    }
  }



  abstract class Stmt extends SyntaxNode with Ordered[Stmt] {
    var prog : Program = null
    var succ : Stmt = null
    var pred : Stmt = null

    var preds : List[Stmt] = List()
    def succs : List[Stmt] = {
      // WARNING: This won't work for branching instructions.

      // By default: 
      if (succ != null)
        List(succ)
      else
        List()
    }

    def compare (stmt2 : Stmt) = this.synId compare stmt2.synId
    def toSExp : SExp ;
  }

  implicit def stmtToProgram (stmt : Stmt) : Program = Program(List(stmt))

  case class Lab (val lab : String) extends Stmt { 
    override def toString = lab + ": "
    def toSExp : SExp = L(List(S("label"), S(lab)))
  }
  case class Assn (lhs : LHS, rhs : RHS) extends Stmt {
    override def toString = lhs + " := " + rhs
    def toSExp : SExp = L(List(S(":="), lhs.toSExp, rhs.toSExp))
  }
  case class PrintLn (rhs : RHS) extends Stmt {
    override def toString = "println ("+rhs+")"
    def toSExp : SExp = L(List(S("println"), rhs.toSExp))
  }
  case class Skip extends Stmt {
    override def toString = "skip"
    def toSExp : SExp = L(List(S("skip")))
  }  
  case class IfGoto (cond : RHS, lab : String) extends Stmt {
    override def succs = List(succ, prog.labMap(lab))
    lazy val trueTarget = prog.labMap(lab)
    lazy val falseTarget = succ
    override def toString = "if (" +cond +") " +" goto "+lab
    def toSExp : SExp = L(List(S("if"), cond.toSExp, S("goto"), S(lab)))
  }
  case class Goto (lab : String) extends Stmt {
    override def succs = List(prog.labMap(lab))
    override def toString = "goto " + lab
    def toSExp : SExp = L(List(S("goto"), S(lab)))
  }
  case class Return (rv : RHS) extends Stmt {
    override def succs = List()
    override def toString = "return " + rv
    def toSExp : SExp = L(List(S("return"), rv.toSExp))
  }
  abstract class LHS {
    def := (rhs : RHS) : Stmt = Assn(this, rhs)
    def toSExp : SExp ;
  }
  case class Var(id : String) extends LHS {
    override def toString = id
    def toSExp : SExp = S(id)
  }
  implicit def stringToLHS (string : String) : LHS = Var(string)

  abstract class RHS  {
    def toSExp : SExp ;
  }
  type Cond = RHS
  type RV = RHS
  implicit def stringToRHS (string : String) : RHS = Ref(string)
  implicit def intToRHS (z : Int) : RHS = IntLit(z)

  case class Ref(id : String) extends RHS {
    override def toString = id
    def toSExp : SExp = S(id)
  }
  case class IntLit(z : BigInt) extends RHS {
    override def toString = z.toString
    def toSExp : SExp = Z(z)
  }
  case class App(prim : String, args : List[RHS]) extends RHS {
    override def toString = prim + "(" + (args mkString ",") + ")"
    def toSExp : SExp = L(S(prim) :: (args map (_.toSExp)))
  }


  /* Syntax helpers. */
  object Program {
    def parse (sx : SExp) : Program = sx match {
      case SProgram(sxstmts) => Program(sxstmts map Stmt.parse)
    }
  }

  object LHS {
    def parse (sx : SExp) : LHS = sx match {
      case S(name) => Var(name)
    }
  }

  object RHS {
    def parse (sx : SExp) : RHS = sx match {
      case S(name) => Ref(name)
      case L(S(opname) :: sxargs) => App(opname, sxargs map RHS.parse)
      case Z(z) => IntLit(z)
      case _ => throw new Exception("Unknown RHS: " + sx)
    }
  }

  object Label {
    def parse (sx : SExp) : String = sx match {
      case S(name) => name
    }
  }
  
  object Stmt {
    def parse (sx : SExp) : Stmt = sx match {
      case SSkip(()) => Skip()
      case SLabel(lab) => Lab(Label parse lab)
      case SAssignment(sxlhs,sxrhs) => LHS.parse(sxlhs) := RHS.parse(sxrhs)
      case SIfGoto(sxcond,sxlab) => IfGoto(RHS parse sxcond, Label parse sxlab)
      case SGoto(sxlab) => Goto(Label parse sxlab)
      case SPrintLn(sxrhs) => PrintLn(RHS parse sxrhs)
      case SReturn(sxrv) => Return(RHS parse sxrv)
    }
  }
  
}


class MachoInterpreter {
  
  import MachoSyntax._

  type Addr = String
  type Value = BigInt

  type Conf = scala.collection.immutable.SortedMap[Addr,BigInt]

  val q0 = scala.collection.immutable.TreeMap[Addr,BigInt]()

  def addr (q : Conf) (lhs : LHS) : Addr = lhs match {
    case Var(id) => id
  }

  def eval (q : Conf) (rhs : RHS) : Value = rhs match {
    case Ref(id) => q(id)
    case IntLit(z) => z
    case App("*",args) => (args map (eval (q) _)).foldLeft (BigInt(1)) (_ * _)
    case App("+",args) => (args map (eval (q) _)).foldLeft (BigInt(1)) (_ + _)
    case App("-",List(a,b)) => (eval (q) (a)) - (eval (q) (b))
    case App("/",List(a,b)) => (eval (q) (a)) / (eval (q) (b))
    case App("<=",List(a,b)) => BigInt(if ((eval (q) (a)) <= (eval (q) (b))) { 1 } else { 0 })
    case App("==",List(a,b)) => BigInt(if ((eval (q) (a)) == (eval (q) (b))) { 1 } else { 0 })
  }

  case class FinalStateException(state : State) extends Exception

  case class State (s : Stmt, q : Conf) {
    def next() = s match {
      case Skip() => State(s.succ, q)
      case Lab(lab) => State(s.succ, q)
      case Assn(lhs,rhs) => State(s.succ, q + ((addr (q) (lhs),eval (q) (rhs))))
      case PrintLn(rhs) => { println(eval (q) (rhs)) ; State(s.succ, q) ; }
      case ifs @ IfGoto(cond,lab) if (eval (q) (cond)) != 0 => State(ifs.trueTarget, q)
      case ifs @ IfGoto(_,lab) => State(ifs.falseTarget, q)
      case Goto(lab) => State(s.prog.labMap(lab), q)
      case Return(rv) => throw new FinalStateException(this)
    }

    def isFinal = s.isInstanceOf[Return]
  }

  def exec(prog : Program) : Value = {
    try {
      val entry = prog.stmts.head
      var s = State(entry, q0)
      while (true) {
        s = s.next()
      }
      throw new Exception("impossible!")
    } catch {
      case FinalStateException(State(Return(rv),qf)) =>
        eval (qf) (rv)
    }
  }

}


trait PartiallyOrdered[A] {
  def wt (rhs : A) : Boolean ;
}


trait Latticed[A] extends PartiallyOrdered[A] {
  def join (rhs : A) : A ;
  def meet (rhs : A) : A ;
}







object Macho {
  import MachoSyntax._

  def main (args : Array[String]) {
    val stdin : String = (scala.io.Source.fromInputStream(System.in)) mkString ""
    val sxs = SParser.parse(stdin)
    val sexp = sxs.head
    val prog = MachoSyntax.Program.parse(sexp)

    val interp = new MachoInterpreter()

    interp.exec(prog)

  }
}