Final Project: tiny stack VM

Challenge

Execute a tiny stack-based bytecode program.

Task

Implement int vm_run(const int *code, size_t n, int *out) that runs a program of n opcodes against an operand stack. The opcodes are:

• PUSH x — push integer x (the next int in code is its argument).
• ADD — pop b, pop a, push a+b.
• MUL — pop b, pop a, push a*b.
• NEG — pop a, push -a.
• HALT — stop; the result is the current top of stack.

The program is a flat int array; PUSH occupies two slots (the opcode then its argument). Use these constants:

enum { OP_PUSH=1, OP_ADD=2, OP_MUL=3, OP_NEG=4, OP_HALT=5 };

Input

• code: array of n ints encoding the program.
• n: the number of ints in code.
• out: where to write the final result on success.

Output

int: 1 on success, writing the top-of-stack value at HALT through *out. Return 0 on any error: stack underflow, stack overflow, a PUSH with no argument, an unknown opcode, or reaching the end with no HALT.

Example

PUSH 3, PUSH 4, ADD, HALT          ->   1, *out == 7
PUSH 5, PUSH 6, MUL, NEG, HALT     ->   1, *out == -30
ADD, HALT                          ->   0   (underflow)
PUSH 1, PUSH 2                     ->   0   (no HALT)
99, HALT                           ->   0   (bad opcode)

Edge cases

• A program with no HALT is an error (return 0).
• A PUSH at the very end with no argument is an error.
• ADD/MUL need two stack items; NEG needs one; HALT needs one.

Rules

• Do not allocate; use a fixed stack of 256 ints. Mind operand order — ADD/MUL are commutative but NEG is not.

Why this matters

A stack VM is the simplest possible interpreter and the model behind the JVM, CPython, and WebAssembly. Building one teaches dispatch loops and the elegance of postfix evaluation.

Input format

code: array of n ints (PUSH takes a following argument int); n; out: result pointer. Stack capacity 256.

Output format

int: 1 on success with the final top-of-stack in *out; 0 on underflow/overflow/bad opcode/missing HALT.

Constraints

No malloc. Stack fixed at 256 ints.

Starter code

#include <stddef.h>
enum { OP_PUSH=1, OP_ADD=2, OP_MUL=3, OP_NEG=4, OP_HALT=5 };
int vm_run(const int *code, size_t n, int *out) { /* TODO */ return 0; }

Common mistakes

Popping in the wrong order (ADD/MUL are commutative; NEG is not); reading past n on a malformed program; forgetting the IP++ for PUSH's argument.

Edge cases to handle

Empty program — no HALT means error. PUSH at end with no argument — error. Stack underflow on bare ADD.

Complexity

O(n) per instruction stream.

Background lessons

• Stacks