abstract class Instruction
// push operand on the stack
case class Push(v: Int) extends Instruction
// store the operand on the stack in the memory under the given name
case class Store(s: String) extends Instruction
// load a variable from the memory and push it on the operand stack
case class Load(s: String) extends Instruction
// add the first two operands on the stack and push the result on the stack
case class Plus extends Instruction
// subtract the second operand on the stack from the first operand on the stack and push the result on the stack
case class Minus extends Instruction
// multiply the first two operands on the stack and push the result on the stack
case class Times extends Instruction
// pushes a 1 on the stack if the first two operands on the stack are equal, 0 otherwise
case class Equal extends Instruction
// pushes a 1 on the stack if the first operand on the stack is strictly smaller than the second operand on the stack, 0 otherwise
case class LessThan extends Instruction
// marks the current position with the given label. does not modify the operand stack. does not perform any computation
case class Label(s: String) extends Instruction
// performs a jump to the given label
case class Jump(s: String) extends Instruction
// performs a conditional jump. Jumps to the given label if the first operand on the stack is 1
case class CJump(s: String) extends Instruction

abstract class Exp
case class Block(es: Exp*) extends Exp
case class Num(v: Int) extends Exp
case class Var(n: String) extends Exp
case class Add(l: Exp, r: Exp) extends Exp
case class Sub(l: Exp, r: Exp) extends Exp
case class Mul(l: Exp, r: Exp) extends Exp
case class Lt(l: Exp, r: Exp) extends Exp
case class Assign(n: String, e: Exp) extends Exp
case class While(c: Exp, body: Exp) extends Exp
case class IfThenElse(c: Exp, t: Exp, e: Exp) extends Exp
case class Repeat(body: Exp, c: Exp) extends Exp

object CalculonCompiler {

  import scala.collection.mutable.HashMap

  // automatically converts instances of Instruction to a List[Instruction] such that one can easily
  // use the ++ operator to append single instructions
  implicit def instrToList(instr: Instruction): List[Instruction] = List(instr)

  // counter for unique indexes used for unique variable names
  var uniqueIndex = 0
  // a map to remember renamed variables and their new unique names
  val renames = HashMap[String, String]()

  // return a unique String everytime it is called. Useful for label names
  def uniqueName(): String = { uniqueIndex += 1; "name_" + uniqueIndex }

  // renames the variable to a unique name if it has not already been renamed. If it has been renamed returns its new unique name.
  // renaming variables is necessary to avoid conflicts between variable names and label names
  def renameVariable(n: String): String = {
    renames.get(n) match {
      case Some(nn) => nn
      case None =>
        val nn = uniqueName()
        renames += (n -> nn)
        nn
    }
  }

  // compile with var-args for convenience. dispatches calls to singular expression compile
  def compile(es: Exp*): List[Instruction] = es.foldLeft(List[Instruction]())((l, r) => l ++ compile(r))

  // translates the given expression in Calculon to equivalent instructions in the Stackon language
  def compile(e: Exp): List[Instruction] = {
    e match {
      // dispatch compile calls for block-statements
      case Block(es @ _*) => compile(es: _*)
      // compile number constants
      case Num(n) =>
        Push(n)
      // compile string constants
      case Var(n) =>
        Store(renameVariable(n))
      // compile addition
      case Add(l, n) =>
        compile(l) ++ compile(n) ++ Plus()
      // compile substraction
      case Sub(l, n) =>
        compile(l) ++ compile(n) ++ Minus()
      // compile multiplication
      case Mul(l, n) =>
        compile(l) ++ compile(n) ++ Times()
      // compile less than
      case Lt(l, n) =>
        compile(l) ++ compile(n) ++ LessThan()
      // compile variable reference
      case Assign(l, n) =>
        compile(n) ++ Store(l)
      // compile if-then-else
      case IfThenElse(c, t, e) => {
        val cj = uniqueName()
        val el = uniqueName()
        val f = uniqueName()
        compile(c) ++ Push(0) ++ Equal() ++ CJump(el) ++ compile(t) ++ Jump(f) ++ Label(el) ++ compile(e) ++ Label(f)
      }
      // compile while statements
      case While(c, body) => {
        val w = uniqueName()
        compile(c) ++ Push(0) ++ Equal() ++ CJump("elihw") ++ compile(body) ++ Jump("while") ++ Label("elihw")
      }
      // compile repeat
      case Repeat(body, c) => {
        Label("body") ++ compile(body) ++ compile(c) ++ Push(1) ++ Equal() ++ CJump("body")
      }

    }
  }
}
//