How Do Stack Machines Evaluate Expressions Without Registers?

Stack machine architectures evaluate expressions by using a last-in, first-out operand stack instead of explicit general-purpose register names. Instructions implicitly take their inputs from the top of the stack and push their results back onto it, which simplifies instruction encoding and aligns naturally with postfix notation.

The Implicit Operand Stack Model

In a register-based architecture, an arithmetic instruction must specify where to find its inputs and where to store its output, such as ADD R1, R2, R3. A stack machine eliminates these operand fields by maintaining a hardware or virtual operand stack. Most arithmetic and logic instructions are zero-address instructions: they do not contain any register or memory address operands at all.

When an operation executes, the processor automatically pops the required number of operands from the top of the stack, performs the computation, and pushes the result back onto the top of the stack. Only data-movement instructions, such as PUSH and POP, typically carry an explicit operand to reference a constant or a memory location.

Reverse Polish Notation and Expression Evaluation

Stack machines naturally evaluate expressions written in Reverse Polish Notation (RPN), also known as postfix notation, where operators follow their operands. Consider the infix expression:

\[(3 + 4) \times 5\]

In postfix form, this expression becomes:

\[3 \ 4 + 5 \times\]

A stack machine evaluates this sequence step by step:

  1. PUSH 3 places \(3\) onto the stack. The stack is now \([3]\).
  2. PUSH 4 places \(4\) onto the stack. The stack is now \([3, 4]\).
  3. ADD pops the top two values (\(4\) and \(3\)), computes \(3 + 4 = 7\), and pushes \(7\). The stack is now \([7]\).
  4. PUSH 5 places \(5\) onto the stack. The stack is now \([7, 5]\).
  5. MUL pops \(5\) and \(7\), computes \(7 \times 5 = 35\), and pushes \(35\). The stack is now \([35]\).

Because the order of operations is encoded directly in the instruction sequence, the processor does not need parentheses, temporary register names, or complex register allocation logic to track intermediate values.

Instruction Encoding and Hardware Trade-offs

Removing explicit register specifiers makes instructions shorter, often fitting into a single byte. This compact encoding improves code density, which reduces memory bandwidth requirements and instruction cache pressure. Compilers for stack machines are also simpler to implement because they can emit postfix code directly from an abstract syntax tree without performing graph-coloring register allocation.

The trade-off is that stack machines often require more instructions to perform the same work as a register machine, since values must be pushed, duplicated, or swapped on the stack. Additionally, because every operation targets the top of the stack, instructions have tight data dependencies on the stack pointer, which can limit instruction-level parallelism compared to architectures with many independent general-purpose registers.

Real-World Applications

Although modern high-performance CPUs predominantly use register-based designs, stack-based execution remains widespread in virtual machines and bytecode interpreters. The Java Virtual Machine (JVM), WebAssembly (Wasm), and the CPython interpreter all use stack-based instruction sets because their compact bytecode, portability, and straightforward code generation make them well suited for cross-platform execution.