Forth's Stacks

"The" stack and the return stack

Standard Forth has two built-in stacks, the data stack, and the return stack. The data stack is so important that it is simply called "the" stack, unless you have to distinguish it from some other stack. I will assume that you are familiar with it, and will not discuss it further.

When a word is invoked, the inner interpreter puts the next address on the return stack. When the word is completed the top item on the return stack is popped into a register called ip (instruction pointer), and execution continues from there. Most Forths that run on Intel machines use the BP register for ip.

Since the return stack is actually used only on invocation and completion, , it is available as a kind of catch-all in between. One common use for the return stack is to store do ... loop parameters. Anything added to the return stack during the execution of a word must be removed before the word ends, and the same is true for a loop.

Words that affect the return stack

do ( n1 n2 -- )

Pushes the loop index and loop limit onto the return stack.

?do ( n1 n2 -- )

Similar to do. The difference is seen when n1 equals n2. With do, there will be 64k iterations on a 16-bit machine, whereas with ?do there will be none. The advantage of DO is that it is much speedier on many machines.

loop ( -- )

Increments the loop index by 1 and tests against the upper limit. If the loop index is equal to the limit, discard the loop parameters and continue execution immediately following the loop. Otherwise continue execution at the beginning of the loop.

+loop ( n -- )

Same, but increments the loop index by n. Exit, as above, if the index has crossed the boundary between the loop limit minus 1 and the loop; otherwise continue.

i ( -- n)

Returns the current value of the loop index, provided the return stack is "clean," that is, nothing has been added to it by the program.

j ( -- n)

When do loops are nested, returns the current value of the outer loop index, provided that the return stack is clean.

leave ( -- )

Exits from the loop at once, discarding the loop count and loop limit from the return stack. If the return stack is not clean, watch out! If you are lucky, your program will hang up. In early Forths, LEAVE najes the counter equal to the limit, forcing exit the next time LOOP or +LOOP is executed. Forth-83 and ANSI demand immediate exit from the loop.

>r ( n --)

Store top of parameter stack on return stack. Pronounced "to R."

r> ( -- n)

Reverse of >R. Pronounced "from R."

r@ ( -- n) or r ( -- n)

Copy top of return stack onto parameter stack. Prounounced "R fetch." r@ is Forth 83 and ANSI standard. Some older Forths use r.

A stack is not an array

In some Forths, for example, F83, the data stack and return stacks are located entirely in RAM and can be handled as arrays. In others, this is not so; for instance, many Forths gain speed by keeping the top element of the stack in a register.

For this reason, an ANSI standard program cannot make any assumptions about where the stacks are located or how they are implemented. pick ( .... n -- .... x) is available to copy the nth stack item onto the top of the stack.

Software Stacks

Software stacks are sometimes called "pseudostacks." Actually, they are genuine stacks, and I prefer the term "software stack" or "LIFO", which stands for "last in first out." That name is taken from the language of finance, where it is used to describe a method of accounting for inventory.

I have implemented LIFO's as a kind of specialized array with a pointer. Pushing a quantity onto a software stack removes it from the parameter stack, stores it in the array, and bumps the pointer; popping does the reverse. A program can have any number of LIFO's. If only one is needed the code can be simplified. In my implementation, there is protection against underflow but not against overflow.

Glossary

lifo ( n -- ) ( -- adr)

During compilation, create a LIFO (software stack) with n cells. On execution, return the address of the stack.

push ( n lifo -- )

Push number onto LIFO.

pop ( lifo -- n )

Pop number from LIFO.

pclear ( lifo -- )

Clear LIFO.

pbounds ( lifo -- addr1 addr2 )

Create parameters for a ?DO loop that will scan every item currently in LIFO. The intended use is:

( lifo )   pbounds ?do -- cell +loop

Code meets requrements for an ANS Forth standard program.

Home

Updated: June 18, 1996

\ Software stacks (see text for documentation)                                       
: lifo ( n -- ) ( -- adr)
     create here cell+ , cells allot does> ;

: push ( n lifo -- )
     swap over @ ! cell swap +! ;

: pop ( lifo -- x )
     cell negate over +! dup @ swap over >=
     abort" [pseudostack underflow] " @ ;

: pclear ( lifo -- ) dup cell+ swap ! ;

: pbounds ( lifo -- addr1 addr2 )   dup @ swap cell+ ;