Stack Machine: A computational model

Stack Machine is a computational model like Turing Machine, Belt Machine and many others. The central and most important component of a Stack Machine is a stack which is used in place of registers to hold temporary variables.

Stack is a data structure with two basic operations:

• push (to add an element)
• pop (to remove an element)

Stack data structure maintains the order in which elements are inserted. Push operation adds an element to the top of the list while pop operation removes an element from the top of the list. It is, also, known as a Last In First Out (LIFO) data structure.

You must think of Stack as a storage device and is used in place of registers in case of Stack Machines. Stacks are used to store temporary variables during computations in a Stack Machine.

Model

A Stack Machine is a computational model 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 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.

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.

Example Calculation in Stack Machine

Consider that we want to evaluate the following expression:

B + C - D 

We need to convert the expression to postfix notation:

B C + D -

Using Stack Machine, the expression is evaluated as:

push val B
push val C
add
push val D
sub

Operations add and sub are performed on the top two elements of Stack that is it is done using two pop operations and followed by a push operation.

Similarly, complex operations such as function calling, parameter passing and others are performed.

Advantages

Advantages of Stack Machines are:

• Stack does not need 'addressing' as it is implicit in the operators which use stack

• Stack Machine results in compact object code

• Compilers for Stack Machines are simple to build

• Interpreters for Stack Machines are simple

• Fast operand access

As there are no operand fields to decode, stack machines fetch each instruction and its operands at same time. Stack machines can omit the operand fetching stage of a register machine.

• Avoids data passing through memory, faster interpreters

• Minimal processor state

A machine with an expression stack can get by with just two registers that are visible to a programmer: The top-of-stack address and the next-instruction address.

Disadvantages

Disadvantages of Stack Machines are:

• More instructions result in slower interpreters

• Rigid code order

• Difficulty in using common sub-expressions multiple time with one execution