Stack machine (computational model)

A stack machine is a computation model that uses one or more stacks to hold operands and intermediate results. It underlies many virtual machines, interpreters and expression evaluators.

In computer science a stack machine is a model of computation in which the primary storage for intermediate results and operands is one or more stacks. Instead of naming registers, instructions implicitly consume their inputs from the top of the stack and push results back. This makes the instruction set compact and well suited to expression evaluation and interpreters.

Characteristics

Stack machines typically use simple operations such as push, pop, arithmetic or logical operators that act on the top stack entries, and control-flow instructions. Typical features include implicit operand addressing (no explicit register fields), a last-in-first-out (LIFO) value discipline, and a limited or absent register file. Programs are often shorter in bytes because instructions omit operand specifiers.

History and development

The idea of using a stack to evaluate expressions predates modern computers and appears in mathematical postfix (RPN) notation. Hardware and software machines that emphasize stack operations emerged as designers sought compact instruction encodings and easy expression evaluation. Later, stack-oriented virtual machines and languages promoted the model for portability and simplicity of interpreters.

Uses and examples

Virtual machines: many interpreters and bytecode systems use stack-based instruction sets for compactness and simple implementation.
Programming languages: stack-oriented languages and some runtimes implement expression evaluation with push/pop semantics.
Calculators and small embedded systems: because stack code can be dense, it is attractive where memory is limited.

Concrete examples include well-known bytecode systems and several stack-oriented languages; implementations may use a memory-backed stack or a small fast cache of top-of-stack values for performance. A simple stack trace for 3 + 4 would be: push 3, push 4, add → top-of-stack becomes 7.

Trade-offs and notable facts

Stack machines favor compact code and easy compilation of expression trees but can require more instructions and extra memory traffic compared with register machines. Compiler backends often convert high-level code into stack code or translate stack code into register operations; analyses such as stack-depth calculation are important to avoid underflow or overflow. For further technical background see related resources.