home   |   stacks treatise index   |   1. Intro: stack basics   |   2. subroutine return addresses & nesting   |   3. interrupts   |   4. virtual stacks   |   5. stack addressing   |   6. passing parameters   |   7. inlined data   |   8. RPN operations   |   9. RPN efficiency   |   10. 65c02 added instructions   |   11. synth instructions w/ RTS/RTI/JSR   |   12. where-am-I routines   |   13. synthesizing 65816 stack instructions   |   14. local variables, environments   |   15. recursion   |   16. enough stack space?   |   17. forming program structures   |   18. stack potpourri   |   19. further reading   |   A: StackOps.ASM   |   B: 816StackOps.ASM   |   Appendix C


Definition and very basics

The kind of stack discussed here is a portion of RAM used for temporary storage of smallish pieces of data, whether variables or addresses, in a last-on, first-off access style, or last-in, first-out (LIFO).  The common comparison is made to a spring-loaded stack of plates in a buffet restaurant.  The amount of compression or stretch of the springs is proportional to the weight of the plates above it, so as long as the stack area does not fill completely, an employee can add any number of recently washed plates and the top one will always be in the same position at the top, ready for the next customer to take.  Usually, neither the employee nor the customer has any need to know how many plates are below the top one, being kept warm.

Or consider a spindle with a bunch of spindled papers on it.  You can see the ones below the top, and you could even read or write on them to some extent without removing ones above them, but the actual removal or addition of papers always take place at the top.

The opposite of a stack (or LIFO memory) would be a first-in, first-out (FIFO) memory, or queue, which can be compared to the conveyor belt on an X-ray machine in an airport or courthouse.  On this machine, things go in one end, and come out the other end in the same order they went in.

Unlike the stack of plates however, a stack of numbers in computer memory does not move up and down when something is added or removed from the stack.  Moving all that data up and down like the plates is very inefficient, so we just leave it where it is and just use an adjustable pointer to tell where the top is, or actually, in the case of the 6502 hardware stack which we will be discussing first, what RAM address is the next one available for putting something on the stack.  This pointer is the 6502's S register.

So, if the plate-dispenser analogy breaks down, why bring it up?  The point is that you usually only deal with what's on top, with no concern for how deep it is, like a ship at sea that does fine whether the water depth is 100 feet or 10,000 feet.  As long as an action or a routine has the stack items it needs, it does not matter how many more are further down in the stack, waiting to be used by other routines or parts of a routine.

In the illustration of a stack of firewood, if you always put the newly split logs on top, and also take off the top for the fireplace or wood-burning stove, the wood at the bottom is the oldest.

Putting something on the stack is called "pushing" it, and removing it from the stack is called "pulling" it off, or, in the parlance of many other processors, "popping" it off the stack.

Appropriately, the first stack discussed here is the 6502's hardware stack.  This is the processor's native stack, and it allows the nesting of subroutines, and of interrupts (whose nesting is rare compared to that of subroutines) and of local variables and environments.  The 6502's page one, ie, addresses $0100-$01FF, is given special significance in that that's where the hardware stack resides.  Tests show that contrary to urban legend, that's several times as much as you'll probably ever need.

The hardware stack pointer is register S which is only 8 bits wide; but the 6502 automatically makes the page number to be $01 for all stack accesses.  Its hardware stack in page 1 (ie, addresses $0100 to $01FF) grows down, not up.  Your reset routine should initialize the stack pointer at the top of available stack space.  This is usually $01FF, unless you have an unusual situation with I/O in the top of page 1, or other RAM usage there.  The reset routine will usually include:

        LDX  #$FF

If you plan to leave the entire page 1 for the hardware stack, and you know it wraps, you might be tempted to not initialize it.  There are times that it will matter though, which will be discussed later.

Since the stack grows downward, the stack pointer gets decremented after each byte is pushed onto the stack, and incremented before each byte is pulled off of the stack.

Next--> 2. subroutine return addresses & nesting

last updated Sep 2, 2015