FACTOID # 8: Bookworms: Vermont has the highest number of high school teachers per capita and third highest number of librarians per capita.
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 


FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:



(* = Graphable)



Encyclopedia > 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. Wikibooks Wikiversity has more about this subject: School of Computer Science Open Directory Project: Computer Science Collection of Computer Science Bibliographies Belief that title science in computer science is inappropriate Categories: Computer science | Academic disciplines ... A stack is a data structure that works on the principle of Last In First Out (LIFO). ...

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). Computability theory is that part of the theory of computation dealing with which problems are solvable by algorithms (equivalently, by Turing machines), with various restrictions and extensions. ... In automata theory, pushdown automata (PDA) are abstract devices that recognize context-free languages. ... In linguistics and computer science, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a non-terminal symbol and w is a string consisting of terminals and/or non-terminals. ... The Turing machine is an abstract machine introduced in 1936 by Alan Turing to give a mathematically precise definition of algorithm or mechanical procedure. As such it is still widely used in theoretical computer science, especially in complexity theory and the theory of computation. ... A computer program (often simply called a program) is an example of computer software that prescribes the actions (computations) that are to be carried out by a computer. ... Reverse Polish notation (RPN) , also known as postfix notation, is an arithmetic formula notation, derived from the Polish notation introduced in 1920 by the Polish mathematician Jan Łukasiewicz. ...

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. In computer science, a subroutine (function, procedure, or subprogram) is a sequence of code which performs a specific task, as part of a larger program, and is grouped as one or more statement blocks; such code is sometimes collected into software libraries. ...

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. A von Neumann machine is a model created by John von Neumann for a computing machine that uses a single storage structure to hold both the set of instructions on how to perform the computation and the data required or generated by the computation. ... An instruction set, or instruction set architecture (ISA), describes the aspects of a computer architecture visible to a programmer, including the native datatypes, instructions, registers, addressing modes, memory architecture, interrupt and exception handling, and external I/O (if any). ...

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. William Seward Burroughs (1857-1898), US inventor William S. Burroughs (1914-1997), author and grandson of William Seward Burroughs Edgar Rice Burroughs (1875-1950), American author of Tarzan fame The Burroughs Corporation began in 1886 as the American Arithmometer Company in St. ... UCSD Pascal was a specific implementation of the programming language Pascal which used the p-Code machine architecture. ... A Java virtual machine or JVM is a virtual machine that runs Java byte code. ... Forth is a programming language and programming environment. ... PostScript (PS) is a page description language used primarily in the electronic and desktop publishing areas. ...

External links

  • Stack Computers: the new wave book by Philip J. Koopman, Jr. 1989

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 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/



Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m