Stack Machine Trace

Run a program on a tiny stack machine used by a label-printer controller and report exactly how it stopped.

The machine has a data stack of integers (empty at the start), a return stack of addresses, an output list, and a program counter pc starting at 0. program[pc] is executed, one instruction at a time:

• PUSH n pushes n. POP discards the top. DUP pushes a copy of the top. SWAP exchanges the top two values. PRINT pops the top and appends it to the output.
• ADD, SUB, MUL, LT pop a (the top) and then b, and push b + a, b - a, b * a, and 1 if b < a else 0 respectively.
• JMP t sets pc = t. JMPZ t pops the top and sets pc = t if it was 0, otherwise continues with the next instruction.
• CALL t pushes pc + 1 on the return stack and sets pc = t. RET pops the return stack into pc; if the return stack is empty, RET ends the program normally. HALT ends the program normally.

Unless an instruction jumps, pc moves to the next instruction. The program also ends normally when pc reaches len(program).

Errors. The machine stops with an error status, changing nothing for that instruction, in these cases (checked in this order, before the instruction runs):

1. "timeout": max_steps instructions have already run and the program has not ended. (A program that ends normally within max_steps instructions, with HALT, RET or running off the end, is not a timeout.)
2. "bad-target": a JMP, JMPZ or CALL whose target is not in 0..len(program) inclusive, whether or not the jump would be taken.
3. "underflow": the data stack has fewer values than the instruction needs (POP, DUP, PRINT, JMPZ need 1; SWAP, ADD, SUB, MUL, LT need 2).
4. "call-overflow": a CALL when the return stack already holds 16 addresses.

Input: program (each instruction is a string such as "PUSH -4" or "JMPZ 8"), max_steps.

Output: [status, output, stack] where status is "halted" for a normal end or one of the error names above, output is everything printed so far, and stack is the data stack from bottom to top when the machine stopped.