Stack machine

In computer science, computer engineering and programming language implementations, a stack machine is a type of computer. In some cases, the term refers to a software scheme that simulates a stack machine. In computer science, computer engineering and programming language implementations, a stack machine is a type of computer. In some cases, the term refers to a software scheme that simulates a stack machine. The main difference from other computers is that most of its instructions operate on a pushdown stack of numbers rather than numbers held in processor registers. Because the operands used in the instructions are always in a known location, the top of the stack, the instructions themselves do not require memory addresses or register numbers to supply their operands. This leads to an instruction set architecture (ISA) style known as a zero address format. Stacks are not unique to stack machines; most programming languages make extensive use of stacks to support subroutines and method calls. For this reason, stack machines more closely mimic the inner workings of the programs that run on them, assuming the programs are written in high level languages. This has led to a number of central processor unit designs that implement stack machines in order to provide higher performance. In practice, however, these designs have been outperformed by the traditional register machine systems, and have remained a niche player in the market. A 'stack machine' is a computer that uses a last-in, first-out stack to hold short-lived temporary values. Most of its instructions assume that operands will be from the stack, and results placed in the stack. For a typical instruction such as Add the computer takes both operands from the topmost (most recent) values of the stack. The computer replaces those two values with the sum, which the computer calculates when it performs the Add instruction. The instruction's operands are 'popped' off the stack, and its result(s) are then 'pushed' back onto the stack, ready for the next instruction. Most stack instructions have only an opcode commanding an operation, with no additional fields to identify a constant, register or memory cell. The stack easily holds more than two inputs or more than one result, so a richer set of operations can be computed. Integer constant operands are often pushed by separate Load Immediate instructions. Memory is often accessed by separate Load or Store instructions containing a memory address or calculating the address from values in the stack. For speed, a stack machine often implements some part of its stack with registers. To execute quickly, operands of the arithmetic logic unit (ALU) may be the top two registers of the stack and the result from the ALU is stored in the top register of the stack. Some stack machines have a stack of limited size, implemented as a register file. The ALU will access this with an index. Some machines have a stack of unlimited size, implemented as an array in RAM accessed by a 'top of stack' address register. This is slower, but the number of flip-flops is less, making a less-expensive, more compact CPU. Its topmost N values may be cached for speed. A few machines have both an expression stack in memory and a separate register stack. In this case, software, or an interrupt may move data between them. The instruction set carries out most ALU actions with postfix (reverse Polish notation) operations that work only on the expression stack, not on data registers or main memory cells. This can be very convenient for executing high-level languages, because most arithmetic expressions can be easily translated into postfix notation. In contrast, register machines hold temporary values in a small, fast array of registers. Accumulator machines have only one general-purpose register. Belt machines use a FIFO queue to hold temporary values. Memory-to-memory machines do not have any temporary registers usable by a programmer. Stack machines may have their expression stack and their call-return stack separated or as one integrated structure. If they are separated, the instructions of the stack machine can be pipelined with fewer interactions and less design complexity. Usually it can run faster.