A Virtual Machine · Software Design by Example

The Problem

Still a lot of magic in the interpreter of Chapter 7
Build something that mimics hardware more closely
See [Nisan2021] for a fuller description
Or play Human Resource Machine

Architecture

Our virtual machine (VM)

Architecture

Instruction pointer (IP) holds the address of the next instruction
- Automatically initialized to 0, so every program must start there
Instructions can access registers R0 to R3 directly
- No memory-to-memory operations
256 words of memory
- Addresses fit in a single byte

What It Can Do

Instruction set defines what the processor can do
Each instruction is 3 bytes
op code fits in one byte
May have zero, one, or two single-byte operands
- Could use variable-length instructions, but that would complicate the VM
Each operand is a register identifier, a constant, or an address

Writing Instructions

Instructions are numbers,
Write them in assembly code for readability

Name	Code	Format	Action	Example
`hlt`	1	`--`	Halt program	`hlt`
`ldc`	2	`rv`	Load constant	`ldc R0 123`
`ldr`	3	`rr`	Load register	`ldr R0 R1`
`add`	6	`rr`	Add	`add R0 R1`
`bne`	9	`rv`	Branch if not equal	`bne R0 123`
`prr`	10	`r-`	Print register	`prr R0`

Details

NUM_REG = 4  # number of registers
RAM_LEN = 256  # number of words in RAM

OPS = {
    "hlt": {"code": 0x1, "fmt": "--"},  # Halt program
    "ldc": {"code": 0x2, "fmt": "rv"},  # Load value
    "ldr": {"code": 0x3, "fmt": "rr"},  # Load register
    "cpy": {"code": 0x4, "fmt": "rr"},  # Copy register
    "str": {"code": 0x5, "fmt": "rr"},  # Store register
    "add": {"code": 0x6, "fmt": "rr"},  # Add
    "sub": {"code": 0x7, "fmt": "rr"},  # Subtract
    "beq": {"code": 0x8, "fmt": "rv"},  # Branch if equal
    "bne": {"code": 0x9, "fmt": "rv"},  # Branch if not equal
    "prr": {"code": 0xA, "fmt": "r-"},  # Print register
    "prm": {"code": 0xB, "fmt": "r-"},  # Print memory
}

OP_MASK = 0xFF  # select a single byte
OP_SHIFT = 8  # shift up by one byte
OP_WIDTH = 6  # op width in characters when printing

VM Class

class VirtualMachine:
    def __init__(self):
        self.initialize([])
        self.prompt = ">>"

    def initialize(self, program):
        assert len(program) <= RAM_LEN, "Program too long"
        self.ram = [
            program[i] if (i < len(program)) else 0
            for i in range(RAM_LEN)
        ]
        self.ip = 0
        self.reg = [0] * NUM_REG

Fetching and Unpacking

    def fetch(self):
        instruction = self.ram[self.ip]
        self.ip += 1
        op = instruction & OP_MASK
        instruction >>= OP_SHIFT
        arg0 = instruction & OP_MASK
        instruction >>= OP_SHIFT
        arg1 = instruction & OP_MASK
        return [op, arg0, arg1]

Use bitwise operations to get bytes out of integer

Unpacking instructions — Figure 2: Using bitwise operations to unpack instructions.

Running a Program

    def run(self):
        running = True
        while running:
            op, arg0, arg1 = self.fetch()
            if op == OPS["hlt"]["code"]:
                running = False
            elif op == OPS["ldc"]["code"]:
                self.reg[arg0] = arg1
            elif op == OPS["ldr"]["code"]:
                self.reg[arg0] = self.ram[self.reg[arg1]]
            elif op == OPS["cpy"]["code"]:
                self.reg[arg0] = self.reg[arg1]
# ...22 lines not shown...
            else:
                assert False, f"Unknown op {op:06x}"

Sample Instructions

Store a value

            elif op == OPS["str"]["code"]:
                self.ram[self.reg[arg1]] = self.reg[arg0]

Addition

            elif op == OPS["add"]["code"]:
                self.reg[arg0] += self.reg[arg1]

Conditional jump

            elif op == OPS["beq"]["code"]:
                if self.reg[arg0] == 0:
                    self.ip = arg1

Writing Programs

Hexadecimal

00010a
000001

Assembly code

# Print initial contents of R1.
prr R1
hlt

Write an assembler to the latter into the former

Labels

Instruction set doesn't have names for addresses
But we want labels for readability

# Count up to 3.
# - R0: loop index.
# - R1: loop limit.
ldc R0 0
ldc R1 3
loop:
prr R0
ldc R2 1
add R0 R2
cpy R2 R1
sub R2 R0
bne R2 @loop
hlt

Counting Up

>> 0
>> 1
>> 2
R000000 = 000003
R000001 = 000003
R000002 = 000000
R000003 = 000000
000000:   000002  030102  00000a  010202
000004:   020006  010204  000207  020209
000008:   000001  000000  000000  000000

Counting Up

Counting from 0 to 2 — Figure 3: Flowchart of assembly language program to count up from 0 to 2.

Counting Up

Trace counting program — Figure 4: Tracing registers and memory values for a simple counting program.

Assembler Class

class Assembler:
    def assemble(self, lines):
        lines = self._get_lines(lines)
        labels = self._find_labels(lines)
        instructions = [
            ln for ln in lines if not self._is_label(ln)
        ]
        compiled = [
            self._compile(instr, labels) for instr in instructions
        ]
        program = self._to_text(compiled)
        return program

Resolving Labels

    def _find_labels(self, lines):
        result = {}
        loc = 0
        for ln in lines:
            if self._is_label(ln):
                label = ln[:-1].strip()
                assert label not in result, f"Duplicated {label}"
                result[label] = loc
            else:
                loc += 1
        return result

    def _is_label(self, line):
        return line.endswith(":")

Either save label or increment current address

Compiling an Instruction

    def _compile(self, instruction, labels):
        tokens = instruction.split()
        op, args = tokens[0], tokens[1:]
        fmt, code = OPS[op]["fmt"], OPS[op]["code"]

        if fmt == "--":
            return self._combine(code)

        elif fmt == "r-":
            return self._combine(self._reg(args[0]), code)

        elif fmt == "rr":
            return self._combine(
                self._reg(args[1]), self._reg(args[0]), code
            )

        elif fmt == "rv":
            return self._combine(
                self._val(args[1], labels),
                self._reg(args[0]), code
            )

Converting a Value

Look up label's address if value starts with @
Convert value to number if it doesn't

    def _val(self, token, labels):
        if token[0] != "@":
            return int(token)
        lbl = token[1:]
        assert lbl in labels, f"Unknown label '{token}'"
        return labels[lbl]

Summary

Concept map for virtual machine and assembler — Figure 5: Concept map.