Implement a Stack-Based VM Interpreter

Topic Overview

Fetch-Decode-Execute

Every interpreter follows the same loop: fetch the next instruction, decode its opcode, execute the handler. CPython's `ceval.c` and Lua's `lvm.c` are this pattern at production scale. Your `switch` statement is the same structure CPython 3.11 later replaced with computed gotos for speed.

The Operand Stack and PC

The program counter points at the next bytecode byte. Each cycle:

1. Read `bytecode[pc]` as the opcode
2. Dispatch to the handler
3. Advance `pc` (unless a jump changes it)

The operand stack is a fixed-size LIFO buffer:

• `PUSH val` grows the stack by one
• `ADD` pops two values, pushes their sum
• `PRINT` pops and displays the top

For example, `(10 + 20) * 3 - 5` compiles to a sequence of pushes and arithmetic ops ending with a single value on the stack.

```c while (running) { uint8_t op = bytecode[pc++]; switch (op) { case OP_PUSH: ... case OP_ADD: ... } } ```

Design Notes

Start with a debug print of pc and stack contents each cycle while developing. Interpreter bugs show up as impossible stack states long before you get wrong final answers. Once handlers are correct, gate the trace behind a flag so benchmarks stay meaningful.

For This Exercise

This exercise asks you to wire up a complete interpreter loop with overflow checks. You will implement `push`, `pop`, and handlers for arithmetic so later tasks add control flow without rewriting the core loop.

Your Task

Implement the core of every stack VM: the fetch, decode, execute loop. Run programs written in the straight-line subset of this subtrack's ISA with 32-bit integer semantics (wrap-around on overflow, division truncating toward zero), and report runtime errors precisely: underflow, overflow, division by zero, and missing HALT.

Input

cCopy
Loading…

Instructions (case-insensitive): HALT PUSH n POP ADD SUB MUL DIV NEG DUP SWAP PRINT.

Rules

• Binary operations pop b (the top), then a, and push a OP b. SWAP exchanges the top two values. PRINT pops the top and prints it.
• Arithmetic is int32 with wrap-around (two's complement). DIV truncates toward zero. INT32_MIN / -1 is an error.
• Errors stop the program (pc = the instruction index, starting at 0):
  • error at PC (OP): stack underflow
  • error at PC (OP): stack overflow (limit N) (PUSH/DUP on a full stack)
  • error at PC (DIV): division by zero
  • error at PC (DIV): result does not fit in 32 bits
  • error: ran off the end of the program without HALT
• HALT prints halted after K instructions, stack [..], where K counts every executed instruction including HALT.
• Trace prints PC OP[ n] -> [stack] after each instruction except HALT. A PRINT's output line comes before its trace line.
• Load-time errors: unsupported instruction X and PUSH needs a 32-bit integer (the line is skipped). stack: 1..256 is printed for a bad limit.

Output

cCopy
Loading…

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Check a stack's depth before popping, and report the failing instruction's index and name.
2. Do the arithmetic in 64 bits and wrap back to int32, so overflow is defined behaviour, not undefined behaviour.

Hidden tests cover underflow on an empty stack, overflow with a small stack limit, division by zero, INT32_MIN / -1, negative division, SWAP and POP, a missing HALT, and unsupported instructions.