Call, Return, and a Depth Limit
A machine has an accumulator, a program of n instructions numbered from 0, and
a return stack that holds at most d addresses. The counter starts at 0, the
accumulator at 0, and the stack empty.
ADD v add v to the accumulator, then move the counter on by 1
CALL a push the address counter+1 onto the return stack, then set the
counter to a
RET pop an address off the return stack and set the counter to it
HLT stop
The machine performs at most s steps, and one step is: if the counter is
outside 0 to n - 1, stop and report FAULT; otherwise execute the
instruction there. Two instructions can fail instead of executing:
a CALL when the stack already holds d addresses -> OVERFLOW
a RET when the stack is empty -> UNDERFLOW
A failed instruction does not execute, so it changes neither the accumulator nor the stack, and the run stops there.
Print one line with three things separated by single spaces: the outcome word,
one of HALT, FAULT, OVERFLOW, UNDERFLOW or RUNNING; the accumulator;
and the deepest the stack ever got.
``` n = 5, d = 4, s = 100: CALL 2 / HLT / ADD 5 / CALL 4 / RET
counter 0: CALL 2 pushes 1 and sets the counter to 2. stack [1] counter 2: ADD 5, accumulator 5, counter 3. counter 3: CALL 4 pushes 4 and sets the counter to 4. stack [1, 4] counter 4: RET pops 4, so the counter becomes 4 again, which is this same RET. stack [1] counter 4: RET pops 1, so the counter becomes 1. stack [] counter 1: HLT.
the deepest the stack ever got was 2. -> HALT 5 2 ```
``` n = 1, d = 0, s = 100: CALL 0
the stack can hold nothing at all, so the first CALL fails immediately and the deepest depth is 0. -> OVERFLOW 0 0 ```
## What most people try first
Pushing the target address instead of the return address. CALL a must push
counter + 1, the instruction after the call, because that is where control
resumes. Pushing a makes every RET jump back to the function it just
entered, which looks like an infinite loop rather than a wrong answer, so it
is easy to misdiagnose.
The second common slip is the order inside a CALL. The push uses the OLD
counter plus one, and the counter is then overwritten. Writing the counter
first and pushing afterwards pushes a + 1.
## Why the depth has to be tracked as it grows
The answer wants the deepest the stack ever got, not the depth at the end. The stack is empty again at every clean return, so reading its size after the run usually gives 0. Take the maximum each time you push, which is the only moment the depth can increase.
## Why a failed instruction must leave no trace
OVERFLOW and UNDERFLOW stop the run, and the statement says the failing
instruction does not execute. That matters for the reported depth: on the
second worked example a CALL that is refused must not be counted as having
reached depth 1. It also means the accumulator is exactly what the previous
instruction left.
The budget is checked before the fault, as in #2165: noticing that the counter
has left the program costs a step, so a counter left outside by the last
affordable step is RUNNING.
## Overflow
The accumulator is a sum of at most s operands of up to 10^9, with s as
large as 10^5, so it can reach 10^14. A signed 32 bit integer stops at
2147483647, so the accumulator must be 64 bit. The depth is at most d, and
the counter stays within the program or stops the run.
## Cost
O(n + s) time, and O(n + d) memory for the program and the stack.