Push-down Stacks

"So the last will be first and the first will be last." Matthew 20:16

And there are other references in the Bible to a last-in first-out (LIFO) stack. Authoritative approval indeed.

Concept

A LIFO stack is also called a push-down stack. The word 'stack' comes from a stack of plates, where the last one placed on the stack is the first one removed. Leo Brodie uses a can of tennis balls as an example. The notion is used for queuing theory and inventory accounting as well as computers.

Computers often use a stack to handle nested subroutines calls. When a subroutine is called, the return address is pushed onto the stack. When that subroutine calls another, its return address is pushed. When a return is encountered, it pops an address off the stack. Thus nesting acts naturally in a LIFO manner.

The book Starting Forth has charming cartoons illustrating stack behavior.

Two stacks

Forth has 2 push-down stacks; arrays that can store numbers: data or addresses. One for nesting subroutines (return) and another for parameters used by those subroutines (data). The data stack is most visible and is explicitly controlled by the programmer.

Forth 'words' are like subroutines: When referenced, a return address is pushed onto the return stack. This stack is also used for loop counters. They can be nested just like words, and interspersed with return addresses, without conflict.

Some words push numbers onto the data stack. Literals, words that look like numbers, do that. For example

Initial stack: . . .
After 12345: . . . 12345

Other words change the stack

Initial stack: 123
After @: 16 (where the address 123 contains 16)

Or change the size of the stack

Initial stack: 123 100
After +: 223

One of the challenges to a new Forth programmer is learning to manage this data stack. It vastly reduces the need for named variables and changes the trade-offs when analysing a problem.

The 2 Forth stacks are connected: the top of the data stack can be pushed onto the return stack by the operator 'push'. Likewise the top of the return stack can be pushed onto the data stack by the operator 'pop'. They can be viewed as a single stack accessed from the center. This allows the return stack to be used for temporary storage (of course within a subroutine or loop).

The language C has a single stack that combines the return and data stacks. That is clumsy and complicated compared to separate stacks.

Hardware

It's certainly possible to emulate a push-down stack in software. Simply incrementing and decrementing a pointer properly. Ofttimes a hardware register is available for this.

GreenArrays' computers have a unique mechanism for implementing stacks with hardware: a stack is a set of registers with a pointer to the one currently on top. The pointer is moved up or down as required. The data is not moved, merely a pointer to the register in which the data is stored. This saves energy.

Moreover, the stack is circular. There is no beginning or end; no concept of empty or overflow. Just the pointer to the current top. If too many numbers are pushed onto the stack, the oldest are overwritten. If too many numbers are popped from the stack, they begin to repeat.

Again: the programmer is responsible for managing the stack. This is not difficult, merely requires attention. And often things can be abandoned on the stack, rather than take the trouble to remove them.

Consequences

Given a data stack, subroutine calling sequences vanish. Parameters are expected on the stack and results placed there. There can be more or fewer results than parameters. The cost of a subroutine is merely the call and return. This allows many small subroutines and more intense factoring of a problem.

In hardware, instructions become 0-operand. That is, an instruction such as + need not be told where its operands are. They are on the stack. Thus + can simply be a 5-bit op-code, and instructions can be packed, several per word of memory. This reduces the number of instruction fetches from memory, increasing speed of execution and density of instructions.

GreenArrays' F18 computer can pack 4 5-bit instructions into an 18-bit word. It's 64-word RAM can hold up to 256 instructions; and another 256 in ROM. Thanks to the push-down stack.