What a stack machine is
A stack machine is a computer, real or imagined, whose instructions work on a stack instead of named registers or variables. Most instructions do one of two things: push a constant, or take values off the top, compute something and push the result. Because the operands are always at the top, the instructions need no operand addresses. That is why stack machine code can be so compact, and why real systems such as virtual machines for programming languages often use the design.
Esoteric languages make the idea easy to see, because their instruction sets are tiny and every effect is visible.
Postfix notation
An ordinary expression like (2 + 3) * 4 uses brackets and operator precedence to say what happens first. A stack machine does not need either. It uses postfix order, where the operator comes after its operands: 2 3 + 4 *. Evaluating it takes one pass from left to right:
| Step | Item | Stack afterward (top on the right) |
|---|---|---|
| 1 | 2 | 2 |
| 2 | 3 | 2 3 |
| 3 | + | 5 |
| 4 | 4 | 5 4 |
| 5 | * | 20 |
Each number is pushed. Each operator pops two values, combines them and pushes the answer. The final result sits alone on the stack. Nothing needed brackets because the order of the tokens already encodes the order of work.
Operand order for subtraction
For operators where order matters, the second item from the top is the left operand. The tokens 9 4 - give 5, and 4 9 - give -5. This is a common source of mistakes, and tracing by hand with a table like the one above is the usual way to catch it.
The same thing in Befunge
In the Befunge language, digits push themselves, + and * act on the top two values, . prints the top as a number, and @ ends the program. The expression above becomes:
23+4*.@The pointer moves right through the cells. After 2 and 3 the stack holds 2 and 3; + replaces them with 5; 4 pushes 4; * leaves 20; . prints 20; @ stops. The sequence is the same as the table, with the grid as the carrier for the instructions. The instructions that rearrange the stack, such as duplicate and swap, carry the same behavior in the Funge family.
Duplicate, swap and drop
Many tasks need more than push and operate. Three small instructions fill the gap:
- Duplicate copies the top item, so you can use a value twice.
- Swap exchanges the top two items, which fixes the operand order.
- Drop (or pop) discards the top item.
With these, squaring a number becomes duplicate then multiply. In a hypothetical stack notation, 7 dup * gives 49: push 7, duplicate to get 7 and 7, multiply. It is the same trick used by concatenative languages, which are built on this model.
Strings and reversal
Stacks are a natural fit for reversing. If a language lets you push each character of a word and then pop them all out, the output comes out backwards. A string reversal program is therefore one of the first things people write in a stack language. It shows the last-in, first-out rule more clearly than any definition.
When the stack misbehaves
Two problems are specific to this model:
- Underflow: an instruction needs two values but only one is present. Implementations differ: some stop with an error, some treat missing values as zero. Befunge-style languages typically use the zero convention, which can hide bugs, as discussed under stack underflow.
- Leftover items: if a program leaves values behind, they may confuse a later part. Careful code leaves the stack the way it found it.
Related are arithmetic edge cases such as division by zero, which every implementation must decide how to handle.
Why stack machines are easy to build
An interpreter for a stack machine is short. It holds a list for the stack, a program counter, and a loop that fetches an instruction and carries it out. That loop is the same one found at the heart of the execution loop in any larger interpreter, and a basic version is often the first project for people learning about building interpreters. You can write a working one in a few dozen lines, then extend it with jumps and conditional instructions to turn the calculator into a general-purpose language.
Beyond calculators
Add comparison, a way to jump, and a way to store values, and a stack machine can run loops and conditionals. The Funge family does the jumping with a direction-changing pointer on a grid. Other languages do it with labels or with code stored as values. The evaluation core stays the same: push, pop, compute, push.
Small languages are the best teachers for this. With a handful of instructions you can trace every step, see every value, and notice exactly where a mistake slipped in, which is a skill that carries over to far larger systems.