Stack machine
A processor using a push-down stack for temporary values.
A stack machine is a type of processor or virtual machine that primarily handles short-lived temporary values by pushing them onto and popping them off a push-down stack. For hardware implementations, a physical hardware stack is used. This design greatly cuts down on the number of processor registers needed. Because stack machines are essentially push-down automata enhanced with load/store operations or multiple stacks, they are Turing-complete.
In most stack machine designs, instructions assume that operands come from the stack and results go back onto it. The stack can easily hold more than two inputs or multiple results, allowing for a wide range of operations. Stack machine code (sometimes called p-code) often uses a zero-address format, where instructions consist only of an opcode without fields for constants, registers, or memory cells. This simplifies instruction decoding. Branches, immediate loads, and load/store instructions do require an argument field, but stack machines typically pack these together with the opcode into a compact bit group. Operand selection from prior results happens implicitly through instruction order. Some stack machine instruction sets are meant for interpretive execution in a virtual machine rather than direct hardware control.
Integer constants are pushed using Push or Load Immediate instructions. Memory access usually requires separate Load or Store instructions that either contain a memory address or calculate one from stack values. Practical stack machines include variants of load-store opcodes for accessing local variables and parameters without explicit address calculations, often using offsets from the current top-of-stack address or a stable frame-base register.
The instruction set performs most ALU actions with postfix (reverse Polish notation) operations that work only on the expression stack, not on data registers or main memory. This suits high-level languages well, since arithmetic expressions translate easily into postfix notation. For example, the expression A*(B−C)+(D+E) in reverse Polish becomes A B C − * D E + +. On a simple stack machine, this would execute by pushing A, B, and C, then subtracting to get B−C, multiplying to get A*(B−C), pushing D and E, adding to get D+E, and finally adding to get the result.
- First described
- 1961 by Robert S. Barton
- Early hardware example
- Z4 (1945) with a 2-level stack
- Notable commercial implementation
- Burroughs Large Systems architecture (since 1961)
- Kdf9 stack depths
- 19-level arithmetic register stack, 17-level subroutine return stack
- Hybrid examples
- MU5 and ICL 2900 Series; HP 3000; Tandem Computers T/16
- Virtual machine examples
- Java virtual machine, WebAssembly bytecode, Common Intermediate Language (.NET)
Lore & Background
Most stack machine instructions assume operands come from the stack and results are placed there, allowing a rich set of operations with a zero-address format that simplifies instruction decoding. Branches, load immediates, and load/store instructions require an argument field, but these often fit with the opcode into a compact group of bits. Integer constants are pushed by Push or Load Immediate instructions, while memory is accessed via separate Load or Store instructions that may calculate addresses from stack values. All practical stack machines have variants of load–store opcodes for accessing local variables and formal parameters without explicit address calculations, using offsets from the current top-of-stack address or from a stable frame-base register.
The instruction set carries out most ALU actions with postfix (reverse Polish notation) operations that work only on the expression stack. For example, the expression A*(B−C)+(D+E) is written as A B C − * D E + +. The arithmetic operations act on the two topmost operands, popping them and pushing the result. Stack machines may have their expression stack and call-return stack separated or integrated; separation allows pipelining with fewer interactions and less design complexity, usually running faster. Optimisation of compiled stack code is possible, with back-end optimisation of compiler output significantly improving code and potentially performance, while global optimisation within the compiler achieves further gains.
Description of such a method requiring only two values at a time in registers, with a limited set of pre-defined operands extendable by definition of further operands, functions and subroutines, was first provided at a conference by Robert S. Barton in 1961. Commercial hardware stack machines include the Z4 (1945), Burroughs Large Systems, English Electric KDF9, Collins CAPS and Rockwell Collins AAMP, Xerox Dandelion and Daybreak, UCSD Pascal p-machine, MU5 and ICL 2900 Series, HP 3000, HP FOCUS-based HP 9000 systems, Tandem T/16, Atmel MARC4, several Forth chips (RTX2000, RTX2010, F21, PSC1000), Setun ternary computer, Patriot Scientific Ignite, Saab Ericsson Space Thor, Inmos transputers, and the ZPU. Virtual stack machines include the Whetstone ALGOL 60 interpretive code, UCSD Pascal p-machine, Niklaus Wirth p-code machine, Smalltalk, Java virtual machine, WebAssembly bytecode, .NET Common Intermediate Language, Forth, PostScript, Sun's SwapDrop, Adobe ActionScript Virtual Machine 2, Ethereum EVM, CPython bytecode interpreter, Ruby YARV, Rubinius, Unix bc and dc calculators, Lua up to version 5.0, TON Virtual Machine, and Apple's TrueType font system.
Reader's Guide
Stack machines are significant for their efficient use of a push-down stack, which reduces the number of processor registers needed and simplifies instruction decoding through zero-address format. This design is particularly convenient for executing high-level languages, as arithmetic expressions translate easily into postfix notation. The approach has been implemented both in hardware—from early computers like the Z4 and Burroughs Large Systems to modern microcontrollers and Forth chips—and in software as virtual machines for languages such as Java, .NET, WebAssembly, Python, Ruby, and Ethereum smart contracts. Hybrid machines combine stack and register features to address inefficiencies, such as when procedures access multiple fields from the same object, by adding register-machine features like a visible register file for addresses. Another hybrid approach adds memory address modes that emulate push/pop operations, as seen in DEC's PDP-11 and later VAX and Motorola 6800 series. The legacy of stack machines includes their role in enabling complete programming environments on early 8-bit microprocessors with limited RAM, as with the UCSD Pascal p-machine, and their continued use in virtual machines for modern platforms.
Did You Know?
- The Z4 computer (1945) by Konrad Zuse had a 2-level stack.
- The English Electric KDF9 had a 19-level deep pushdown stack of arithmetic registers and a 17-level deep stack for subroutine return addresses.
- The Setun ternary computer performed balanced ternary using a stack.
- The Java virtual machine instruction set is stack-based, though HotSpot implements the interpreter as handwritten assembly stubs.
More in Microprocessors 1-24
Spotted an error? Know more?
Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced