Write an Interpreter for a Small Language with Load, Store and Arithmetic

Implement an interpreter for a small programming language designed for the interview. The language already defines simple load and store instructions and arithmetic operations; your job is to write the program that reads source text in this language and executes it. The exact syntax given in the interview was not reported. Practice with the minimal specification below, which is an assumption, and keep your design easy to adapt if the specification you receive differs, for example a register-based language instead of a stack-based one. - A program is a string with one instruction per line. Tokens on a line are separated by whitespace, and blank lines are ignored. - The machine has an operand stack of integers and a memory of named variables. A variable name starts with a letter or an underscore, followed by letters, digits or underscores. - `LOAD x` pushes a value onto the stack. Its operand is either an integer literal such as `7` or `-3`, or the name of a variable that has already been stored. - `STORE x` pops the top of the stack and writes it to the variable `x`. - `ADD`, `SUB`, `MUL` and `DIV` pop the right operand, then the left operand, and push `left + right`, `left - right`, `left * right` or `left / right`. Implement `run(source: str) -> dict[str, int]`, which executes a program and returns the final contents of memory. ```text LOAD 6 LOAD 4 SUB STORE x LOAD x LOAD 3 MUL STORE y run(program) -> {"x": 2, "y": 6} ``` ```hint Two jobs, two stages Reading text and executing instructions fail in different ways. Decide which errors you can catch before running a single instruction, and what form the program should take between the two steps. ``` ```hint Consume tokens in order Each opcode tells you how many operand tokens follow it. Taking tokens from the front of a queue keeps that bookkeeping simple and makes missing or leftover tokens easy to detect. ``` ### Constraints and Clarifications - The specification above stands in for the one supplied in the interview. The source reports load, store and arithmetic only, so no control flow (labels, jumps, loops) is assumed. - No follow-up questions were reported for this round; the follow-ups below are practice extensions of the same task. ### Clarifying Questions - Are integers unbounded, or fixed width (32-bit or 64-bit), and if fixed, what happens on overflow? - How does `DIV` round a negative quotient, toward zero or toward negative infinity, and what happens on division by zero? - What should happen on an unknown instruction, a missing or extra operand, a pop from an empty stack, or a `LOAD` of a variable that was never stored? - Is it an error if values remain on the stack when the program ends? - Should the interpreter return the final memory, print values, or both? Are opcodes case-sensitive? ### What a Strong Answer Covers - Settles numeric semantics and the error policy before writing code - A clean split between parsing the source into an instruction list and executing that list - Correct stack mechanics, including the operand order of `SUB` and `DIV` - Error messages that name the line and the cause, for both syntax errors and runtime errors - A structure in which adding an instruction is a local change, plus tests for every instruction and every error ### Follow-up Questions - Add labels and a conditional jump, such as "pop a value and jump to a label if it is zero". How do parsing and execution change, and how do you stop a program that never halts? - Users want to write `y = (x - 4) * 3` instead of instructions. How would you compile such an expression into this instruction set? - The same program runs a million times with different starting memory. What would you precompute so that each run is as fast as possible? - How would your design change if the specification were register-based, for example `LOAD r1 x` and `ADD r3 r1 r2`?