Katkat
Back

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

Jane StreetSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Practice writing an interpreter for a small language with load, store and integer arithmetic instructions, using an assumed stack-based specification. It tests parsing source text into instructions, executing them with correct operand order, and reporting errors such as stack underflow, undefined variables and division by zero.

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.

LOAD 6
LOAD 4
SUB
STORE x
LOAD x
LOAD 3
MUL
STORE y

run(program) -> {"x": 2, "y": 6}

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?

Hints

Hint 1

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 2

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.

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`?