Add Function Calls with a Call Stack

Topic Overview

The Call Stack

Functions need a call stack separate from the operand stack. Each invocation pushes a frame storing the return address, locals, and a link to the caller's frame. CPython's `PyFrameObject` and the JVM's per-method frame are production versions of what you build here.

CALL and RETURN

• `CALL addr`: push a frame, save `pc` as return address, jump to `addr`
• `RETURN`: pop the frame, restore `pc`, leave the return value on the operand stack
• Arguments typically sit on the operand stack before `CALL`

Recursion works because each call gets fresh locals. Python's default recursion limit of 1000 frames exists because this stack is finite.

For example, `factorial(5)` nests five frames, each with its own `n` local, before unwinding via `RETURN`.

Frame layout:

• Return address (where to resume)
• Local variable array (parameters and temporaries)
• Pointer to enclosing frame

Design Notes

Size each frame's local array to the function's needs and zero it on entry. Stale locals from a previous invocation are a subtle bug that only shows up when callers reuse overlapping stack slots without clearing state.

For This Exercise

This exercise asks you to add `CALL` and `RETURN` with a `CallFrame` struct. You will implement recursive factorial in bytecode to prove frames push and pop correctly under nested calls.

Your Task

Give the VM functions. CALL label nargs pushes a call frame: it moves the top nargs operands into the new frame's locals 0..nargs−1, records the return address and the current stack height, and jumps. RET pops the return value, drops anything else the callee left on the stack, pushes the value back for the caller, and resumes after the call. LOAD i/STORE i access the current frame's 8 locals. Recursion must work, and runaway recursion must hit a depth limit.

Input

cCopy
Loading…

Instructions: HALT PUSH n POP ADD SUB MUL DIV NEG DUP SWAP PRINT EQ LT GT JMP L JZ L CALL L nargs RET LOAD i STORE i.

Rules

• Existing instructions behave as before (int32 wrap-around, JZ pops, labels resolved at end).
• Frames. main is frame 0. A new frame's locals start at 0. Each frame has its own stack base: an instruction that needs more operands than exist above the base is a stack underflow, and a CALL needs nargs operands.
• CALL that would make the depth reach the limit prints error at PC (CALL L): call stack overflow (depth limit N). RET in main prints error at PC (RET): return from main.
• HALT prints halted after K instructions, C calls, max call depth D (main is depth 0).
• trace prints call NAME(arg, ...) and NAME returns V, indented 2 spaces per depth − 1.
• Load errors:
  • line N: bad operand for OP (PUSH needs an int32; LOAD/STORE need 0..7)
  • line N: CALL needs a label and 0..8 arguments
  • line N: JMP needs a label / JZ needs a label
  • line N: unsupported instruction X
  • line N: duplicate label X
  • line N: undefined label X
• Runtime errors are error at PC (OP): stack underflow | division by zero | result does not fit in 32 bits, plus error: step limit 100000 reached at PC and error: ran off the end of the program without HALT.

Output

cCopy
Loading…

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Store the return address and stack base in the frame. RET must restore the stack height, so a sloppy callee cannot corrupt the caller.
2. Pop arguments in reverse so that argument 0 is the one pushed first.

Hidden tests cover recursive Fibonacci, a two-argument function, a callee that leaves junk on the stack, the depth limit, RET from main, a callee reading below its base, and bad operands.