Stack machine
|
|
In computer science, a stack machine is a model of computation in which the computer's memory takes the form of a stack. The term also refers to an actual computer implementing or simulating the idealized stack machine.
In computability theory, the pushdown automaton (PDA) is the abstraction of a stack machine. It is important to note that a PDA, even the nondeterministic kind, can recognize only context-free grammars, and therefore is not equivalent to a Turing machine (TM). This means that a PDA cannot execute arbitrary programs. Thus, single-stack machines are restricted to simple computations (such as arithmetic calculations in postfix notation).
A two-stack machine on the other hand, can emulate a Turing machine (by using one stack for the tape portion to the left of the TM's current head position and the other stack for the right).
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 Von Neumann machine (a regular computer) 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 on a Von Neumann machine is that the instruction size decreases, since there is no need to specify operand addresses. This nearly always lead to dramatically smaller compiled programs. Smaller code meant faster execution when the limitation on performance was how fast current technology would allow instructions to be fetched from memory. Put differently - stack machines tend to be faster when the CPU can execute instructions faster than they can be delivered from memory.
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 the Burroughs "Large Systems" architecture, 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, and Adobe's PostScript. Note that the Burroughs machines combined a stack machine with tagged memory (a few bits in every memory word to describe the type of data contained). With tagged memory you need fewer opcodes - a single "add" instruction works for any combination integer and floating point numbers. Fewer opcodes means you can fit your entire instruction set into small 8-bit opcodes.
External links
- Stack Computers: the new wave book by Philip J. Koopman, Jr. 1989 (http://www.ece.cmu.edu/~koopman/stack_computers/)
More than two stacks
The vast majority of stack machines are two-stack machines. There has been very little research on using more than two stacks.
- The 4stack processor by Bernd Paysan (http://jwdt.com/~paysan/4stack.html) has 4 stacks.
- "Win32FX .... [includes] Five stacks and demos showing why modern Forths need at least 4, and preferably 5 stacks to be viable in today's computer world." http://sourceforge.net/projects/win32fx/ has unfortunately never released any files (as of 2004) but current releases with source are available at http://www.win32fx.com/