Stack Machine - Practical Expression-Stack Machines

Practical Expression-Stack Machines

A stack machine implements registers with a stack. The operands of the arithmetic logic unit (ALU) are always the top two registers of the stack and the result from the ALU is stored in the top register of the stack. 'Stack machine' commonly refers to computers which use a Last-in, First-out stack to hold short-lived temporary values while executing individual program statements. 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.

For a typical instruction like Add, both operands implicitly come from the topmost (most recent) values of the stack, and those two values get replaced by the result of the Add. 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 are encoded as just an opcode, with no additional fields to specify a register number or memory address or literal constant. This encoding is easily extended to richer operations with more than two inputs or more than one result. Integer constant operands are pushed by separate Load Immediate instructions. All accessing of program variables in main memory RAM is segregated into separate Load or Store instructions containing one memory address or some way to calculate that address from stacked operands.

The stack machine style is in contrast to register file machines which hold temporary values in a small fast visible array of similar registers, or accumulator machines which have only one visible general-purpose temp register, or memory-to-memory machines which have no visible temp registers.

Some machines have a stack of very limited size, implemented as a register file and a dynamic register renumbering scheme. Some machines have a stack of unlimited size, implemented as an array in RAM accessed by a 'top of stack' address register. Its topmost N values may be cached by invisible data registers for speed. A few machines have both an expression stack in memory and a separate visible register stack.

Stack machines may have their expression stack and their call-return stack as separate things or as one integrated structure.

Some technical handheld calculators use reverse Polish notation in their keyboard interface, instead of having parenthesis keys. This is a form of stack machine. The Plus key relies on its two operands already being at the correct topmost positions of the user-visible stack.