A virtual machine implements a computer in software.

Task[edit]
Write a virtual machine interpreter. This interpreter should be able to run virtual
assembly language programs created via the task. This is a
byte-coded, 32-bit word stack based virtual machine.

The program should read input from a file and/or stdin, and write output to a file and/or
stdout.

Input format:

Given the following program:

count = 1;
while (count < 10) {
    print("count is: ", count, "\n");
    count = count + 1;
}

The output from the Code generator is a virtual assembly code program:



 Output from gen, input to VM



Datasize: 1 Strings: 2
"count is: "
"\n"
    0 push  1
    5 store [0]
   10 fetch [0]
   15 push  10
   20 lt
   21 jz     (43) 65
   26 push  0
   31 prts
   32 fetch [0]
   37 prti
   38 push  1
   43 prts
   44 fetch [0]
   49 push  1
   54 add
   55 store [0]
   60 jmp    (-51) 10
   65 halt

The first line of the input specifies the datasize required and the number of constant
strings, in the order that they are reference via the code.

The data can be stored in a separate array, or the data can be stored at the beginning of
the stack. Data is addressed starting at 0. If there are 3 variables, the 3rd one if
referenced at address 2.

If there are one or more constant strings, they come next. The code refers to these
strings by their index. The index starts at 0. So if there are 3 strings, and the code
wants to reference the 3rd string, 2 will be used.

Next comes the actual virtual assembly code. The first number is the code address of that
instruction. After that is the instruction mnemonic, followed by optional operands,
depending on the instruction.

Registers:

sp:

   the stack pointer - points to the next top of stack.  The stack is a 32-bit integer
   array.

pc:

   the program counter - points to the current instruction to be performed.  The code is an
   array of bytes.

Data:

   data
   string pool

Instructions:

Each instruction is one byte. The following instructions also have a 32-bit integer
operand:

fetch [index]

where index is an index into the data array.

store [index]

where index is an index into the data array.

push n

where value is a 32-bit integer that will be pushed onto the stack.

jmp (n) addr

where (n) is a 32-bit integer specifying the distance between the current location and the
desired location. addr is an unsigned value of the actual code address.

jz (n) addr

where (n) is a 32-bit integer specifying the distance between the current location and the
desired location. addr is an unsigned value of the actual code address.

The following instructions do not have an operand. They perform their operation directly
against the stack:

For the following instructions, the operation is performed against the top two entries in
the stack:

add
sub
mul
div
mod
lt
gt
le
ge
eq
ne
and
or

For the following instructions, the operation is performed against the top entry in the
stack:

neg
not

Print the word at stack top as a character.

prtc

Print the word at stack top as an integer.

prti

Stack top points to an index into the string pool. Print that entry.

prts

Unconditional stop.

halt

 A simple example virtual machine

def run_vm(data_size)
    int stack[data_size + 1000]
    set stack[0..data_size - 1] to 0
    int pc = 0
    while True:
        op = code[pc]
        pc += 1
 
        if op == FETCH:
            stack.append(stack[bytes_to_int(code[pc:pc+word_size])[0]]);
            pc += word_size
        elif op == STORE:
            stack[bytes_to_int(code[pc:pc+word_size])[0]] = stack.pop();
            pc += word_size
        elif op == PUSH:
            stack.append(bytes_to_int(code[pc:pc+word_size])[0]);
            pc += word_size
        elif op == ADD:   stack[-2] += stack[-1]; stack.pop()
        elif op == SUB:   stack[-2] -= stack[-1]; stack.pop()
        elif op == MUL:   stack[-2] *= stack[-1]; stack.pop()
        elif op == DIV:   stack[-2] /= stack[-1]; stack.pop()
        elif op == MOD:   stack[-2] %= stack[-1]; stack.pop()
        elif op == LT:    stack[-2] = stack[-2] <  stack[-1]; stack.pop()
        elif op == GT:    stack[-2] = stack[-2] >  stack[-1]; stack.pop()
        elif op == LE:    stack[-2] = stack[-2] <= stack[-1]; stack.pop()
        elif op == GE:    stack[-2] = stack[-2] >= stack[-1]; stack.pop()
        elif op == EQ:    stack[-2] = stack[-2] == stack[-1]; stack.pop()
        elif op == NE:    stack[-2] = stack[-2] != stack[-1]; stack.pop()
        elif op == AND:   stack[-2] = stack[-2] and stack[-1]; stack.pop()
        elif op == OR:    stack[-2] = stack[-2] or  stack[-1]; stack.pop()
        elif op == NEG:   stack[-1] = -stack[-1]
        elif op == NOT:   stack[-1] = not stack[-1]
        elif op == JMP:   pc += bytes_to_int(code[pc:pc+word_size])[0]
        elif op == JZ:    if stack.pop() then pc += word_size else pc += bytes_to_int(code[pc:pc+word_size])[0]
        elif op == PRTC:  print stack[-1] as a character; stack.pop()
        elif op == PRTS:  print the constant string referred to by stack[-1]; stack.pop()
        elif op == PRTI:  print stack[-1] as an integer; stack.pop()
        elif op == HALT:  break
 Additional examples
Your solution should pass all the test cases above and the additional tests found Here.

Reference
The C and Python versions can be considered reference implementations.

Related Tasks
 Lexical Analyzer task
 Syntax Analyzer task
 Code Generator task
 AST Interpreter task

 
package xyz.hyperreal.rosettacodeCompiler
 
import java.io.{BufferedReader, FileReader, Reader, StringReader}
 
import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer
 
object VirtualMachine {
 
  private object Opcodes {
    val FETCH: Byte = 0
    val STORE: Byte = 1
    val PUSH: Byte  = 2
    val JMP: Byte   = 3
    val JZ: Byte    = 4
    val ADD: Byte   = 5
    val SUB: Byte   = 6
    val MUL: Byte   = 7
    val DIV: Byte   = 8
    val MOD: Byte   = 9
    val LT: Byte    = 10
    val GT: Byte    = 11
    val LE: Byte    = 12
    val GE: Byte    = 13
    val EQ: Byte    = 14
    val NE: Byte    = 15
    val AND: Byte   = 16
    val OR: Byte    = 17
    val NEG: Byte   = 18
    val NOT: Byte   = 19
    val PRTC: Byte  = 20
    val PRTI: Byte  = 21
    val PRTS: Byte  = 22
    val HALT: Byte  = 23
  }
 
  import Opcodes._
 
  private val HEADER_REGEX = "Datasize: ([0-9]+) Strings: ([0-9]+)" r
  private val STRING_REGEX = "\"([^\"]*)\"" r
  private val PUSH_REGEX   = " *[0-9]+ push +([0-9]+|'(?:[^'\\n]|\\\\n|\\\\\\\\)')" r
  private val PRTS_REGEX   = " *[0-9]+ prts" r
  private val PRTI_REGEX   = " *[0-9]+ prti" r
  private val PRTC_REGEX   = " *[0-9]+ prtc" r
  private val HALT_REGEX   = " *[0-9]+ halt" r
  private val STORE_REGEX  = " *[0-9]+ store +\\[([0-9]+)\\]" r
  private val FETCH_REGEX  = " *[0-9]+ fetch +\\[([0-9]+)\\]" r
  private val LT_REGEX     = " *[0-9]+ lt" r
  private val GT_REGEX     = " *[0-9]+ gt" r
  private val LE_REGEX     = " *[0-9]+ le" r
  private val GE_REGEX     = " *[0-9]+ ge" r
  private val NE_REGEX     = " *[0-9]+ ne" r
  private val EQ_REGEX     = " *[0-9]+ eq" r
  private val JZ_REGEX     = " *[0-9]+ jz +\\((-?[0-9]+)\\) [0-9]+" r
  private val ADD_REGEX    = " *[0-9]+ add" r
  private val SUB_REGEX    = " *[0-9]+ sub" r
  private val MUL_REGEX    = " *[0-9]+ mul" r
  private val DIV_REGEX    = " *[0-9]+ div" r
  private val MOD_REGEX    = " *[0-9]+ mod" r
  private val AND_REGEX    = " *[0-9]+ and" r
  private val OR_REGEX     = " *[0-9]+ or" r
  private val NOT_REGEX    = " *[0-9]+ not" r
  private val NEG_REGEX    = " *[0-9]+ neg" r
  private val JMP_REGEX    = " *[0-9]+ jmp +\\((-?[0-9]+)\\) [0-9]+" r
 
  def fromStdin = fromReader(Console.in)
 
  def fromFile(file: String) = fromReader(new FileReader(file))
 
  def fromString(src: String) = fromReader(new StringReader(src))
 
  def fromReader(r: Reader) = {
    val in = new BufferedReader(r)
    val vm =
      in.readLine match {
        case HEADER_REGEX(datasize, stringsize) =>
          val strings =
            for (_ <- 1 to stringsize.toInt)
              yield
                in.readLine match {
                  case STRING_REGEX(s) => unescape(s)
                  case null            => sys.error("expected string constant but encountered end of input")
                  case s               => sys.error(s"expected string constant: $s")
                }
          var line: String = null
          val code         = new ArrayBuffer[Byte]
 
          def addShort(a: Int) = {
            code += (a >> 8).toByte
            code += a.toByte
          }
 
          def addInstIntOperand(opcode: Byte, operand: Int) = {
            code += opcode
            addShort(operand >> 16)
            addShort(operand)
          }
 
          def addInst(opcode: Byte, operand: String) = addInstIntOperand(opcode, operand.toInt)
 
          while ({ line = in.readLine; line ne null }) line match {
            case PUSH_REGEX(n) if n startsWith "'" =>
              addInstIntOperand(PUSH, unescape(n.substring(1, n.length - 1)).head)
            case PUSH_REGEX(n)    => addInst(PUSH, n)
            case PRTS_REGEX()     => code += PRTS
            case PRTI_REGEX()     => code += PRTI
            case PRTC_REGEX()     => code += PRTC
            case HALT_REGEX()     => code += HALT
            case STORE_REGEX(idx) => addInst(STORE, idx)
            case FETCH_REGEX(idx) => addInst(FETCH, idx)
            case LT_REGEX()       => code += LT
            case GT_REGEX()       => code += GT
            case LE_REGEX()       => code += LE
            case GE_REGEX()       => code += GE
            case NE_REGEX()       => code += NE
            case EQ_REGEX()       => code += EQ
            case JZ_REGEX(disp)   => addInst(JZ, disp)
            case ADD_REGEX()      => code += ADD
            case SUB_REGEX()      => code += SUB
            case MUL_REGEX()      => code += MUL
            case DIV_REGEX()      => code += DIV
            case MOD_REGEX()      => code += MOD
            case AND_REGEX()      => code += AND
            case OR_REGEX()       => code += OR
            case NOT_REGEX()      => code += NOT
            case NEG_REGEX()      => code += NEG
            case JMP_REGEX(disp)  => addInst(JMP, disp)
          }
 
          new VirtualMachine(code, datasize.toInt, strings)
        case _ => sys.error("expected header")
      }
 
    in.close
    vm
  }
 
}
 
class VirtualMachine(code: IndexedSeq[Byte], datasize: Int, strings: IndexedSeq[String]) {
 
  import VirtualMachine.Opcodes._
 
  var pc      = 0
  val stack   = new mutable.ArrayStack[Int]
  val data    = new Array[Int](datasize)
  var running = false
 
  def getByte = {
    val byte = code(pc) & 0xFF
 
    pc += 1
    byte
  }
 
  def getShort = getByte << 8 | getByte
 
  def getInt = getShort << 16 | getShort
 
  def pushBoolean(b: Boolean) = stack push (if (b) 1 else 0)
 
  def popBoolean = if (stack.pop != 0) true else false
 
  def operator(f: (Int, Int) => Int) = {
    val y = stack.pop
 
    stack.push(f(stack.pop, y))
  }
 
  def relation(r: (Int, Int) => Boolean) = {
    val y = stack.pop
 
    pushBoolean(r(stack.pop, y))
  }
 
  def connective(c: (Boolean, Boolean) => Boolean) = pushBoolean(c(popBoolean, popBoolean))
 
  def execute: Unit =
    getByte match {
      case FETCH => stack push data(getInt)
      case STORE => data(getInt) = stack.pop
      case PUSH  => stack push getInt
      case JMP   => pc = pc + getInt
      case JZ    => if (stack.pop == 0) pc = pc + getInt else pc += 4
      case ADD   => operator(_ + _)
      case SUB   => operator(_ - _)
      case MUL   => operator(_ * _)
      case DIV   => operator(_ / _)
      case MOD   => operator(_ % _)
      case LT    => relation(_ < _)
      case GT    => relation(_ > _)
      case LE    => relation(_ <= _)
      case GE    => relation(_ >= _)
      case EQ    => relation(_ == _)
      case NE    => relation(_ != _)
      case AND   => connective(_ && _)
      case OR    => connective(_ || _)
      case NEG   => stack push -stack.pop
      case NOT   => pushBoolean(!popBoolean)
      case PRTC  => print(stack.pop.toChar)
      case PRTI  => print(stack.pop)
      case PRTS  => print(strings(stack.pop))
      case HALT  => running = false
    }
 
  def run = {
    pc = 0
    stack.clear
    running = true
 
    for (i <- data.indices) data(i) = 0
 
    while (running) execute
  }
 
}
 