sealed abstract class Value
  case class Immediate(const : Int) extends Value
 
  sealed abstract class Address extends Value
    case class Register(r : Int) extends Address
    case class Memory(a : Int) extends Address
    case class Indirect(r : Int) extends Address
    case class IndirectOffset(r : Int, offset : Int) extends Address
 
sealed abstract class ArithOp
  case object Mul extends ArithOp
  case object Add extends ArithOp
  case object Sub extends ArithOp
 
sealed abstract class Instruction
  case class Quad(destination : Address,
  		  op : ArithOp,
	 	  source1 : Value,
		  source2 : Value) extends Instruction
  /* Possible restrictions to above, on various architectures:
       - source1,source2 must be registers (use Move if needed)
       - destination = source1
       - indirect addressing only for some registers
       - register 0 always stores constant 0
   */
  case class Move(destination : Address,
		  source : Value) extends Instruction
  case class BranchIfZero(r : Int, pcOffset : Int) extends Instruction
  case class BranchIndirect(r : Int) extends Instruction
  case class JumpSubroutine(pcOffset : Int) extends Instruction
 
class Computer(var code : Array[Instruction],
               var pc   : Int,        // program counter (current instruction)
               var reg  : Array[Int], // registers
	       var mem  : Array[Int]  // memory
	      )
{
  def compute(op : ArithOp, x : Int, y : Int) : Int = op match {
    case Mul => x * y
    case Add => x + y
    case Sub => x - y
  }
  def load(v : Value) : Int = v match {
    case Immediate(const) => const
    case Register(r) => reg(r)
    case Memory(a) => mem(a)
    case Indirect(r) => mem(reg(r))
    case IndirectOffset(r,offset) => mem(reg(r) + offset)
  }
  def store(a : Address, x : Int) = a match {
    case Register(r) => { reg(r) = x }
    case Memory(a) => { mem(a) = x }
    case Indirect(r) => { mem(reg(r)) = x }
    case IndirectOffset(r,offset) => { mem(reg(r) + offset) = x }
  }
  def step = code(pc) match {
    case Quad(destination,op,source1,source2) => {
      store(destination, compute(op, load(source1), load(source2)))
      pc = pc + 1
    }
    case Move(destination, source) => { 
      store(destination, load(source))
      pc = pc + 1
    }
    case BranchIfZero(r, pcOffset) => {
      if (reg(r)==0) 
	pc = pc + pcOffset
      else 
	pc = pc + 1
    }
    case BranchIndirect(r) => { pc = reg(r) }
    case JumpSubroutine(pcOffset) => {
      reg(15) = pc + 1
      pc = pc + pcOffset
    }
  }
  def run = {
    while (pc < code.length)
      step
  }
}
 
object Test {
    /* Memory layout:
         0  : 
         ...
         100 : x (initially 7)
         104 : y (initially 2)
	 108 : z (initially 6)
       Execute statement: 
         x = x*y + y*z + x*z
       Result should be 68.
    */
  val xAddr = 100
  val yAddr = 104
  val zAddr = 108
 
  def initMem() : Array[Int] = {
    val memory = new Array[Int](2048)
    memory(xAddr) = 7
    memory(yAddr) = 2
    memory(zAddr) = 6
    memory
  }
 
  def main(args : Array[String]) = {
    val registers = new Array[Int](32)
 
    // heavy use of memory addressing
    val codeMemory : Array[Instruction] = List(
      Quad(Register(1), Mul, Memory(xAddr), Memory(yAddr)),
      Quad(Register(2), Mul, Memory(yAddr), Memory(zAddr)),
      Quad(Register(1), Add, Register(1), Register(2)),
      Quad(Register(2), Mul, Memory(xAddr), Memory(zAddr)),
      Quad(Memory(xAddr), Add, Register(1), Register(2))
    ).toArray
 
    var computer = new Computer(codeMemory,0,registers, initMem)
    computer.run
    println(computer.mem(xAddr))
 
    // all arithmetic operations use registers,
    // always fresh register unless value stored previously
    val codeManyReg : Array[Instruction] = List(
      Move(Register(1), Memory(xAddr)), 
      Move(Register(2), Memory(yAddr)),
      Move(Register(3), Memory(zAddr)),
      Quad(Register(4), Mul, Register(1), Register(2)),
      Quad(Register(5), Mul, Register(2), Register(3)),
      Quad(Register(6), Mul, Register(1), Register(3)),
      Quad(Register(7), Add, Register(4), Register(5)),
      Quad(Register(8), Add, Register(7), Register(6)),
      Move(Memory(xAddr), Register(8))
    ).toArray
 
    computer = new Computer(codeManyReg,0,registers, initMem)
    computer.run
    println(computer.mem(xAddr))
 
    // all arithmetic operations use registers,
    // minimizing memory traffic and registers
    val codeSmart : Array[Instruction] = List(
      Move(Register(1), Memory(xAddr)), 
      Move(Register(2), Memory(yAddr)),
      Move(Register(3), Memory(zAddr)),
      Quad(Register(4), Mul, Register(1), Register(2)),
      Quad(Register(5), Mul, Register(2), Register(3)),
      Quad(Register(4), Add, Register(4), Register(5)),
      Quad(Register(5), Mul, Register(1), Register(3)),
      Quad(Register(4), Add, Register(4), Register(5)),
      Move(Memory(xAddr), Register(4))
    ).toArray
 
    computer = new Computer(codeSmart,0,registers, initMem)
    computer.run
    println(computer.mem(xAddr))
 
    // Question: can we do it with only one memory load for each x,y,z
    // but with even fewer registers used?
    val codeFourReg : Array[Instruction] = List(
      Move(Register(1), Memory(xAddr)), 
      Move(Register(2), Memory(yAddr)),
      Move(Register(3), Memory(zAddr)),
      Quad(Register(4), Mul, Register(1), Register(2)),
      Quad(Register(2), Mul, Register(2), Register(3)),
      Quad(Register(4), Add, Register(4), Register(2)),
      Quad(Register(1), Mul, Register(1), Register(3)),
      Quad(Register(4), Add, Register(4), Register(1)),
      Move(Memory(xAddr), Register(4))
    ).toArray
 
    computer = new Computer(codeFourReg,0,registers, initMem)
    computer.run
    println(computer.mem(xAddr))
  }
}