Add Control Flow: JUMP and Conditional Branches

Topic Overview

Control Flow in Bytecode

Without jumps, a VM is a calculator. `JUMP`, `JUMP_IF_FALSE`, and comparison opcodes turn straight-line bytecode into real programs with loops and conditionals.

Comparisons and Branching

Comparison instructions pop two values and push a boolean (0 or 1):

• `EQ`, `LT`, `GT` produce the condition for an `if` or `while`
• `JUMP_IF_FALSE addr` pops the top; if zero, sets `pc = addr`
• `JUMP addr` always transfers control (skipping `else` blocks, looping back)

An `if/else` in bytecode looks like:

``` <condition> JUMP_IF_FALSE else_label <then block> JUMP end_label else_label: <else block> end_label: ```

For example, summing 1 through 10 uses a loop that jumps back to `loop_start` until the counter exceeds 10.

Forward jumps need backpatching: the compiler emits a placeholder address and patches it once the target label's offset is known. CPython's `compile.c` does exactly this for every `if` and `while`.

Design Notes

Patch jump targets only after you know the final bytecode offset. If you patch too early, inserting another instruction later shifts every following address and silently breaks branches. Compiler writers keep a list of pending patches for this reason.

For This Exercise

This exercise asks you to add branching to your VM and demonstrate a loop plus conditional. You will implement comparison opcodes and absolute jumps, including the backpatch pattern your compiler will rely on next.

Your Task

Add control flow to the stack VM: comparisons that push 1 or 0, an unconditional JMP, and JZ, which pops a value and jumps if it is zero. Resolve jump labels after the whole program has been read, count the jumps taken, and stop runaway loops with a step limit.

Input

cCopy
Loading…

Instructions: HALT PUSH n POP ADD SUB MUL DIV NEG DUP SWAP PRINT EQ LT GT JMP label JZ label.

Rules

• Existing instructions behave as in the stack-machine task: int32 wrap-around, DIV truncates, and the errors stack underflow, stack overflow (limit N), division by zero and result does not fit in 32 bits are reported as error at PC (OP): ....
• EQ/LT/GT pop b, then a, and push a == b, a < b or a > b as 1 or 0.
• JMP L jumps unconditionally. JZ L pops a value and jumps if it is 0, otherwise it continues.
• Labels. A label names the index of the next instruction and may share a line with it. Labels are resolved at end. Any line N: undefined label X prevents the run. Line numbers count the non-empty lines of the program.
• Step limit. Before executing each instruction, if the limit has been reached, print error: step limit N reached at PC (infinite loop?).
• HALT prints halted after K instructions, J jumps taken, stack [..].
• Trace prints jumps as PC JZ label -> [stack] plus (jump) when taken.
• Load errors: line N: unsupported instruction X, line N: PUSH needs a 32-bit integer, line N: JMP needs a label / JZ needs a label, line N: duplicate label X, and steps: must be positive.

Output

cCopy
Loading…

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Jumps set pc directly. Do not also increment it. That off-by-one is the classic VM bug.
2. Resolve labels only after reading the whole program, so forward jumps work.

Hidden tests cover a stepping loop that ends on GT, LT and GT results, JZ both taken and not taken, an infinite loop caught by a small step limit, duplicate labels, and missing jump operands.