Stack machine

From Wikipedia, the free encyclopedia

In computer science, a stack machine is a model of computation in which the computer's memory takes the form of one or more stacks. The term also refers to an actual computer implementing or simulating the idealized stack machine.

In addition, a stack machine can also refer to a real or simulated machine with a "0-operand" instruction set. In such a machine, most instructions implicitly operate on values at the top of the stack and replace those values with the result. Typically such machines also have a "load" and a "store" instruction that reads and writes to arbitrary RAM locations. (Like all other instructions, the "load" and "store" instructions in a typical stack machine need no operands -- they always take the RAM address from the top of the stack).

The advantage of stack machines ("0-operand instruction set") over accumulator machines ("1-operand instruction set") and register machines ("2-operand instruction set" or a "3-operand instruction set") is that programs written for a "0-operand" instruction set generally have higher code density than equivalent programs written for other instruction sets.

[edit] Stack model of computation

A stack machine has a number of stacks. The input is the initial content of stack 1; all the other stacks start empty. Each state of a stack machine is either a read state or a write state; and each state specifies a stack number to read (pop) from, or write (push) onto. In addition, a write state specifies the symbol to write, and the next state to transition to. A read state specifies, for each symbol in the alphabet, what state it would transition to if that symbol were read; in addition, it also specifies what state to transition to if the stack were empty. A stack machine halts when it transitions into a special halting state.

A stack machine with 1 stack is a very weak model of computation. For example, it can be shown that no 1-stack stack machine can recognize the simple language 0ⁿ1ⁿ (a number of 0s followed by the same number of 1s), via pumping arguments. The computational power of 1-state stack machines is strictly greater than that of finite automata, but strictly less than that of deterministic pushdown automata.

A stack machine with multiple stacks, on the other hand, is equivalent to a Turing machine. For example, a 2-stack machine can emulate a TM by using one stack for the tape portion to the left of the TM's current head position and the other stack for the portion to the right.

[edit] Stack machine instruction sets

Machines with a stack-based instruction set can have one or more stacks. The vast majority of stack machines are two-stack machines.^{[dubious — see talk page]} The two stacks are usually the data stack and the return stack, the former being used for operations on data and the latter to hold the return addresses for procedure calls.

A machine using processor registers for operands can easily simulate a stack machine. Such a simulation is sometimes called a virtual stack machine. The advantage of a stack-based instruction set architecture over an architecture using registers is that the instruction size is smaller since there is no need to specify operand addresses. This nearly always leads to dramatically smaller compiled programs. Stack machines, however, tend to execute instructions more slowly than register based machines when the CPU can execute instructions faster than they can be delivered from memory. This is because the results of partially computed values are always stored and retrieved from the stack - which is located in external memory - during any calculation.

Commercial implementations of stack machines generally include a small set of special purpose fixed-function registers for addressing the enclosing contexts. Perhaps this is not a "pure" stack machine in some sense, but this does allow a stack machine CPU to be entirely suitable for general purpose computing.

Examples of commercial use of a stack machine include

instruction set architectures directly executed in hardware
- the Burroughs large systems architecture (since 1961)
- Unisys Clearpath/MCP systems (latest implementation of Burroughs large systems architecture as of 2006)
- Tandem Computers T/16.
- HP 3000 (Classic, not PA-RISC)
- the Atmel MARC4 microcontroller [1]
- Several "Forth chips"[2] such as the RTX2000, the Sh-Boom, the F21[3] and the PSC1000[4]
- The 4stack processor by Bernd Paysan has four stacks.
- The "Ignite" stack machine architected by Charles H. Moore holds a leading functional density benchmark.

virtual machines interpreted in software
- the UCSD Pascal p-machine (which closely resembled Burroughs)
- the Java virtual machine instruction set
- the VES (Virtual Execution System) for the CIL (Common Intermediate Language) instruction set of the ECMA 335 (.NET environment)
- the Forth programming language, in particular the Forth virtual machine
- Adobe's PostScript
- Parakeet programming language
- Sun Microsystem's SwapDrop programming language for Sun Ray smartcard identification

Note that the Burroughs architecture combines a stack machine with tagged memory (a few bits in every memory word to describe the data type of the operands). Tagged memory requires fewer opcodes, e.g., a single "add" instruction works for any combination of integer and floating point operands. Requiring fewer opcodes means that the entire instruction set can fit into smaller opcodes, reducing the total instruction width.