Design a Bytecode Instruction Set

Topic Overview

Designing a Bytecode ISA

A virtual machine's instruction set architecture defines what operations exist and how they encode. The first fork every VM author faces is stack-based versus register-based design. Stack VMs keep operands implicit on an evaluation stack; register VMs name explicit slots in each frame.

Stack-Based vs Register-Based

Stack-based designs dominate portable bytecode:

• JVM, CPython, WebAssembly: compact opcodes, simple compiler targets
• Expression trees map directly: PUSH 5; PUSH 3; ADD leaves 8 on the stack

Register-based designs trade larger instructions for fewer memory touches:

• Lua 5.0+, Dalvik: ADD R1, R2, R3 names sources and destination explicitly
• Fewer dispatches per expression, but the compiler must allocate registers

Opcode layout matters early. A single-byte opcode (0-255) plus optional operand bytes is the pattern CPython and your VM will follow. Getting stack effects documented now (ADD pops 2, pushes 1) is what lets the compiler, GC, and JIT plug into a stable contract.

For example, compiling print(5 + 3) might emit PUSH 5; PUSH 3; ADD; PRINT.

For This Exercise

This exercise asks you to document a 16-opcode stack ISA before you implement the interpreter. You will implement opcode tables, stack-effect descriptions, and example sequences that every later task builds on.

Your Task

Design the instruction set for a small stack VM, then build its assembler (text to bytes, resolving labels in two passes) and disassembler (bytes back to text). Every later task in this subtrack uses this ISA.

ISA

Input

cCopy
Loading…

Rules

• Mnemonics are case-insensitive. PUSH takes a decimal or 0x integer in the int32 range. JMP/JZ take a label or a numeric address 0..65535.
• Pass 1 assigns each label the byte offset of the next instruction and reports duplicate labels. Pass 2 encodes the instructions. Errors are reported with the line number inside the asm block, pass-1 errors first:
  • line N: duplicate label X
  • line N: unknown mnemonic X
  • line N: M needs an operand
  • line N: too many operands for M
  • line N: undefined label X
  • line N: bad 32-bit immediate X
  • If there are any errors, only these lines and assembly failed: K error(s) are printed.
• Listing: each instruction's 4-digit hex offset and bytes, padded to column 22, then the instruction as written (PUSH shows its value). Then N bytes: and every byte.
• disasm decodes from offset 0:
  • PUSH operands are sign-extended; jump targets print as 0x%04x.
  • A byte above 0x0f prints ??? unknown opcode and decoding continues at the next byte.
  • An operand cut off by the end of the input prints (truncated operand), and decoding stops.

Output

cCopy
Loading…

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Use two passes, so forward jumps (jz done before done:) resolve.
2. Encode multi-byte operands little-endian, byte by byte, so the encoding does not depend on the host.

Hidden tests cover backward and forward labels, numeric jump targets, hex immediates, negative numbers, a label on its own line, every error message, and disassembly of every opcode.