Implement a Wasm Stack Machine Interpreter for a Subset of Instructions

Topic Overview

Wasm Stack Machine Interpreter

Wasm execution is specification-defined stack semantics. Your interpreter maintains an operand stack, locals array, and structured control frames for blocks and branches.

Instruction Subset

Core patterns:

• \`local.get\` / \`local.set\`: locals indexed 0..n
• \`i32.const\`, \`i32.add\`, \`i32.sub\`: integer stack ops
• \`br\`, \`br_if\`: branch with label depth
• \`call\`, \`return\`: functions and exits

Validation (next task) proves stack depth correct before you run. Execution pops operands, pushes results, and updates \`pc\` through the current function body.

For example, \`(param i32 i32) (result i32)\` with body \`local.get 0; local.get 1; i32.add\` leaves one \`i32\` on the stack.

\`\`\` stack: [] -> [a] -> [a,b] -> [a+b] \`\`\`

Design Notes

Structured control (`block`, `loop`, `if`) requires a control stack in addition to the operand stack. Branch depths index into that stack; getting depth wrong traps at runtime even after validation passes.

For This Exercise

This exercise asks you to implement a Wasm interpreter for a curated opcode subset. You will execute validated function bodies with an explicit operand stack matching the spec's stack effects.

You will use the same mental model here when reading production interpreter source later in the track. Sketch one concrete input on paper, predict the outcome, then confirm with code. That discipline catches logic errors early and makes debugging far faster when you extend the implementation in follow-on tasks.

Your Task

Implement a WebAssembly interpreter for i32 code with structured control flow. Wasm has no gotos: block, loop and if open labels, and br N jumps to the N-th enclosing label. A block's label is at its end, and a loop's label is at its start. Add locals, calls, select, and the spec's traps.

Input

;; starts a comment.

cCopy
Loading…

Instructions:

• Control: unreachable nop block loop if else end br N br_if N return call NAME drop select.
• Locals and constants: local.get/set/tee I, i32.const V.
• Comparisons: i32.eqz eq ne lt_s gt_s le_s ge_s.
• Arithmetic: i32.add sub mul div_s rem_s and or xor shl shr_s.

All blocks are void (no block parameters or results).

Semantics

• Labels: br N targets label N counting outward from 0. The function body itself is the outermost label, so branching to it returns. Taking a branch discards the values the targeted block pushed.
  • Branching to a block or if continues after its end.
  • Branching to a loop restarts it.
• Conditionals: if pops a condition. When false, it continues after its else (or its end). A then-branch that reaches else skips to the end. br_if pops a condition and branches if it is non-zero. select pops c, b, a and pushes c ? a : b.
• Calls: call pops the callee's params (the first param deepest), runs it, and pushes its result if it has one. return ends the function.
• Results: at the end, the function's result is the value on top of its stack.
• Arithmetic: wraps at 32 bits. Shift counts use the low 5 bits.
• Traps:
  • unreachable
  • integer divide by zero (div_s/rem_s by 0)
  • integer overflow (div_s of INT_MIN by -1; rem_s gives 0 there)
  • call stack exhausted (more than 1000 nested calls)
  • stack underflow in F at PC (PC is the instruction index in F, counting from 0)
  • call to unknown function X

Output

One line per invoke: NAME(ARGS) = V, NAME(ARGS) returned (no result), or NAME(ARGS) trapped: MESSAGE, followed by [max call depth D].

cCopy
Loading…

Errors:

• line N: unknown instruction X
• line N: OP needs a number, line N: OP takes no immediate, line N: call needs a function name
• line N: local I out of range
• line N: branch depth N out of range (deeper than the open blocks)
• line N: else without if
• line N: bad func, line N: bad func header word X
• line N: outside a func, line N: function too long
• After any error, every invoke prints module has errors.
• invoke: no function X, invoke F: expected N argument(s)

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Match every block/loop/if with its else/end once, at load time, so branches jump directly.
2. At run time, keep a label stack of {kind, start, end, stack height}. A branch pops labels and restores the height.

Hidden tests cover if/else, a two-level br_if escape, select, INT_MIN edge cases, rem_s sign, unreachable, unbounded recursion, a stack underflow, a function without a result, and load errors.