Stack machines are arguably the simplest kind of computer architecture. Their LIFO structure is quite suitable for block-oriented languages. The code size for a stack machine can be very compact because most instructions have no operand field.

Forth (from around 1970) is perhaps the most succesful stack-based programming language, based on a machine model consisting of a data stack and a return stack. Stack-oriented languages are a large subset of concatenative programming language (with the Om language being a rare example of a non-stack-oriented concatenative programming language).

Many virtual machines used as compilation targets of higher-level programming languages (?Java, Lua, etc.) are stack-based.

History

Reverse Polish notation was separately invented since the 1950s by several matematicians and computer scientists. GEORGE (1957) was the first practical programming language based on RPN.

Stack-based instruction sets were used by many mainframe computers of the early 1960s (notably, the Burroughs B5000 and the English Electric KDF9), but the idea was later marginalized by register-based architectures such as the IBM S/360. Still, some later stack-based computers (such as Niklaus Wirth's Lilith) proved to be quite competitive in terms of speed, particularly thanks to the high code density that reduced their need for memory bandwidth.

Example

Primitives:

• POP Remove an item at index, closing the hole left in the stack.
• ROLL Remove an item at index, push it on top of the stack.
• PICK Copy an item at index, push it on top of the stack.

From these primitives, the basic stack operations can be created:

• DROP(a b) Discard top item.
• NIP(a c) Discard second item.
• SWAP(a c b) Bring second item to top.
• ROT(b c a) Bring third item to top.
• DUP(a b c c) Copy top item.
• OVER(a b c b) Copy second item to top.