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

import os, parseutils, strutils, strscans, strformat
 
type
 
  Value = int32
  BytesValue = array[4, byte]
  Address = int32
 
  OpCode = enum
           opFetch = "fetch"
           opStore = "store"
           opPush = "push"
           opJmp = "jmp"
           opJz = "jz"
           opAdd = "add"
           opSub = "sub"
           opMul = "mul"
           opDiv = "div"
           opMod = "mod"
           opLt = "lt"
           opgt = "gt"
           opLe = "le"
           opGe = "ge"
           opEq = "eq"
           opNe = "ne"
           opAnd = "and"
           opOr = "or"
           opNeg = "neg"
           opNot = "not"
           opPrtc = "prtc"
           opPrti = "prti"
           opPrts = "prts"
           opHalt = "halt"
           opInvalid = "invalid"
 
  # Virtual machine description.
  VM = object
    stack: seq[Value]     # Evaluation stack.
    memory: seq[byte]     # Memory to store program.
    data: seq[Value]      # Data storage.
    strings: seq[string]  # String storage.
    pc: Address           # Program counter.
 
  # Exceptions.
  LoadingError = object of CatchableError
  RuntimeError = object of CatchableError
 
 
####################################################################################################
# Running program.
 
proc checkStackLength(vm: VM; minLength: int) {.inline.} =
  ## Check that evaluation stack contains at least "minLength" elements.
  if vm.stack.len < minLength:
    raise newException(RuntimeError, &"not enough operands on the stack (pc = {vm.pc}).")
 
#---------------------------------------------------------------------------------------------------
 
proc getOperand(vm: var VM): Value =
  ## Get a 32 bits operand.
 
  type Union {.union.} = object
    value: Value
    bytes: BytesValue
 
  if vm.pc + 4 >= vm.memory.len:
    raise newException(RuntimeError, &"out of memory (pc = {vm.pc}).")
 
  var aux: Union
  let address = vm.pc + 1
  for idx in 0..3:
    aux.bytes[idx] = vm.memory[address + idx]
  result = aux.value
 
#---------------------------------------------------------------------------------------------------
 
proc run(vm: var VM) =
  ## Run a program loaded in VM memory.
 
  vm.pc = 0
 
  while true:
 
    if vm.pc notin 0..vm.memory.high:
      raise newException(RuntimeError, &"out of memory (pc = {vm.pc}).")
 
    let opcode = OpCode(vm.memory[vm.pc])
    case opcode
 
    of opFetch, opStore:
      let index = vm.getOperand()
      if index notin 0..vm.data.high:
        raise newException(RuntimeError, &"wrong memory index (pc = {vm.pc}).")
      if opcode == opFetch:
        vm.stack.add(vm.data[index])
      else:
        vm.checkStackLength(1)
        vm.data[index] = vm.stack.pop()
      inc vm.pc, 4
 
    of opPush:
      let value = vm.getOperand()
      vm.stack.add(value)
      inc vm.pc, 4
 
    of opJmp:
      let offset = vm.getOperand()
      inc vm.pc, offset
 
    of opJz:
      let offset = vm.getOperand()
      vm.checkStackLength(1)
      let value = vm.stack.pop()
      inc vm.pc, if value == 0: offset else: 4
 
    of opAdd..opOr:
      # Two operands instructions.
      vm.checkStackLength(2)
      let op2 = vm.stack.pop()
      let op1 = vm.stack.pop()
      case range[opAdd..opOr](opcode)
      of opAdd:
        vm.stack.add(op1 + op2)
      of opSub:
        vm.stack.add(op1 - op2)
      of opMul:
        vm.stack.add(op1 * op2)
      of opDiv:
        vm.stack.add(op1 div op2)
      of opMod:
        vm.stack.add(op1 mod op2)
      of opLt:
        vm.stack.add(Value(op1 < op2))
      of opgt:
        vm.stack.add(Value(op1 > op2))
      of opLe:
        vm.stack.add(Value(op1 <= op2))
      of opGe:
        vm.stack.add(Value(op1 >= op2))
      of opEq:
        vm.stack.add(Value(op1 == op2))
      of opNe:
        vm.stack.add(Value(op1 != op2))
      of opAnd:
        vm.stack.add(op1 and op2)
      of opOr:
        vm.stack.add(op1 or op2)
 
    of opNeg..opPrts:
      # One operand instructions.
      vm.checkStackLength(1)
      let op = vm.stack.pop()
      case range[opNeg..opPrts](opcode)
      of opNeg:
        vm.stack.add(-op)
      of opNot:
        vm.stack.add(not op)
      of opPrtc:
        stdout.write(chr(op))
      of opPrti:
        stdout.write(op)
      of opPrts:
        if op notin 0..vm.strings.high:
          raise newException(RuntimeError, &"wrong string index (pc = {vm.pc}).")
        stdout.write(vm.strings[op])
 
    of opHalt:
      break
 
    of opInvalid:
      discard   # Not possible.
 
    inc vm.pc
 
 
####################################################################################################
# Loading assembly file.
 
proc parseHeader(line: string): tuple[dataSize, stringCount: int] =
  ## Parse the header.
 
  if not line.scanf("Datasize: $s$i $sStrings: $i", result.dataSize, result.stringCount):
    raise newException(LoadingError, "Wrong header in code.")
 
#---------------------------------------------------------------------------------------------------
 
import re
 
proc parseString(line: string; linenum: int): string =
  ## Parse a string.
 
  if not line.startsWith('"'):
    raise newException(LoadingError, "Line $1: incorrect string.".format(linenum))
  # Can't use "unescape" as it is confused by "\\n" and "\n".
  result = line.replacef(re"([^\\])(\\n)", "$1\n").replace(r"\\", r"\").replace("\"", "")
 
#---------------------------------------------------------------------------------------------------
 
proc parseValue(line: string; linenum: int; pos: var int; msg: string): int32 =
  ## Parse an int32 value.
 
  var value: int
 
  pos += line.skipWhitespace(pos)
  let parsed = line.parseInt(value, pos)
  if parsed == 0:
    raise newException(LoadingError, "Line $1: ".format(linenum) & msg)
  pos += parsed
  result = int32(value)
 
#---------------------------------------------------------------------------------------------------
 
proc parseOpcode(line: string; linenum: int; pos: var int): OpCode =
  ## Parse an opcode.
 
  var opstring: string
 
  pos += line.skipWhitespace(pos)
  let parsed = line.parseIdent(opstring, pos)
  if parsed == 0:
    raise newException(LoadingError, "Line $1: opcode expected".format(linenum))
  pos += parsed
 
  result = parseEnum[OpCode](opstring, opInvalid)
  if result == opInvalid:
    raise newException(LoadingError, "Line $1: invalid opcode encountered".format(linenum))
 
#---------------------------------------------------------------------------------------------------
 
proc parseMemoryIndex(line: string; linenum: int; pos: var int): int32 =
  ## Parse a memory index (int32 value between brackets).
 
  var memIndex: int
 
  pos += line.skipWhitespace(pos)
  let str = line.captureBetween('[', ']', pos)
  if str.parseInt(memIndex) == 0 or memIndex < 0:
    raise newException(LoadingError, "Line $1: invalid memory index".format(lineNum))
  pos += str.len + 2
  result = int32(memIndex)
 
#---------------------------------------------------------------------------------------------------
 
proc parseOffset(line: string; linenum: int; pos: var int): int32 =
  ## Parse an offset (int32 value between parentheses).
 
  var offset: int
 
  pos += line.skipWhitespace(pos)
  let str = line.captureBetween('(', ')', pos)
  if str.parseInt(offset) == 0:
    raise newException(LoadingError, "Line $1: invalid offset".format(linenum))
  pos += str.len + 2
  result = int32(offset)
 
#---------------------------------------------------------------------------------------------------
 
proc load(vm: var VM; code: string) =
  ## Load an assembly code into VM memory.
 
  # Analyze header.
  let lines = code.splitlines()
  let (dataSize, stringCount) = parseHeader(lines[0])
  vm.data.setLen(dataSize)
  vm.strings.setLen(stringCount)
 
  # Load strings.
  for idx in 1..stringCount:
    vm.strings[idx - 1] = lines[idx].parseString(idx + 1)
 
  # Load code.
  var pc: Address = 0
  for idx in (stringCount + 1)..lines.high:
    var pos = 0
    let line = lines[idx]
    if line.len == 0: continue
 
    # Process address.
    let address = line.parseValue(idx + 1, pos, "address expected")
    if address != pc:
      raise newException(LoadingError, "Line $1: wrong address".format(idx + 1))
 
    # Process opcode.
    let opcode = line.parseOpcode(idx + 1, pos)
    vm.memory.add(byte(opcode))
 
    # Process operand.
    case opcode
 
    of opFetch, opStore:
      # Find memory index.
      let memIndex = line.parseMemoryIndex(idx + 1, pos)
      vm.memory.add(cast[BytesValue](Value(memIndex)))
      inc pc, 5
 
    of opJmp, opJz:
      # Find offset.
      let offset = line.parseOffset(idx + 1, pos)
      vm.memory.add(cast[BytesValue](Value(offset)))
      # Find and check branch address.
      let branchAddress = line.parseValue(idx + 1, pos, "branch address expected")
      if branchAddress != pc + offset + 1:
        raise newException(LoadingError, "Line $1: wrong branch address".format(idx + 1))
      inc pc, 5
 
    of opPush:
      # Find value.
      let value = line.parseValue(idx + 1, pos, "value expected")
      vm.memory.add(cast[BytesValue](Value(value)))
      inc pc, 5
 
    else:
      inc pc
 
#———————————————————————————————————————————————————————————————————————————————————————————————————
 
let code = if paramCount() == 0: stdin.readAll() else: paramStr(1).readFile()
var vm: VM
 
vm.load(code)
vm.run()