Having a background in programming, I am familiar with common
data structures including Stacks. My experience with using them has not
been extensive. My development using Lua relied on the Lua Virtual Stack,
while hooking into the VM from C to Lua. I also have written a small scripting
language that has stack based operations...
I suppose it should be stated that my 6502 assembler is NESASM because I
am learning NES programming...
I'm having a hard time understanding how the Stack is used. Can it be compared
to the way Lua provides an omni-present bridge from one environment to another?
Is it just a way of loading a procedure that is called outside of normal memory?
Is it used with interrupts?
Thanks, I know this is as clear as mud, but I'm on my lunch and didn't have a whole
lot of time to gather my thoughts.

_________________
http://www.thestarrlab.com

_________________
x86?  We ain't got no x86.  We don't NEED no stinking x86!

Although BDD did a good job above, I started this earlier and got called away just before I could finish. I might as well finish and post it.

I have no idea what Lua is, but here are some stack basics.

A stack is generally a last-on-first-off storage area, meaning that the last number put on is the first one to come off. This is the oposite of FIFO (first-in-first-out). A processor's instructions that use the hardware stack will have the incrementing and decrementing of the pointer integrated and automatic so your program doesn't have to use more instructions to take care of that part.

The most basic use is probably storing return addresses for subroutines, because you need to be able to nest them, ie, have one subroutine call another, which calls another, etc., and neither the one doing the calling nor the one being called should have to worry about how many subroutine calls were made before it that have not been returned to yet. On the 6502, the normal subroutine call instruction is JSR (Jump to SubRoutine, or, more accurately, Jump, Saving Return address). It puts the address on the stack so the program pointer can get back to where it left off in the calling routine before it did the subroutine. The subroutine's RTS (ReTurn from Subroutine) uses this address left on the stack to know where to jump back to.

You can also pass parameters to your subroutine on the hardware stack, using PHA for example. If a subroutine doesn't need more than three bytes passed to it, you can get away with using A, X, and Y unless you really need to leave one of those undisturbed for something else. For more, you can use variables in RAM, or, if it proves to be rather poor use of memory to set up tons of variables that only get used in one place, pass them via the stack instead, so they only exist when they're in use. Right away you might see a problem there. If the subroutine starts pulling bytes off the stack, the first two bytes will be the address it will need to return to when it's done. If it pulls them off, where is it going to keep them? It defeats the purpose of the stack. Wat you can do is TSX then something like ADC 103,X. This way you can reach different depths into the stack (by using 104, 105, 106, etc., not using extra instructions to increment and decrement X) without taking everything off the top to get to those elements. Going in order then is not required, and you're not limited to just PLA, PLX, and PLY, (as I showed with the ADC example). To make things easier, the 65816 added stack-relative addressing modes (as BDD mentioned).

JSR and RTS have other uses too, but we'll keep this simple here.

The interrupts do use the stack to store the address where to resume execution of the background routine when the interrupt service is finished, and to keep the processor status to restore when you go back to the background routine. If the interrupt-service routine (ISR) uses A, X, or Y, it needs to store those as well to restore later. I frequently find though that A is the only one I need in the ISR, and there's the rare case where the interrupt can be serviced without even using A (like to increment bytes in memory). This is to say you don't automatically have to push A, X, and Y in every ISR and pull them back off the stack at the conclusion of the ISR.

The Forth programming language and environment (since BDD mentioned it) has two stacks standard: a return stack and a data stack. It's almost like the 6502 was designed partly with Forth in mind, because the 6502's hardware stack works out perfectly for Forth's return stack, and zero page with its added addressing modes (like indirect indexed) works out perfectly for Forth's data stack. Sometimes Forth will have an additional stack for floating-point or other uses, but two is standard.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Hi Johnny.
Let me add some general thoughts. The 6502 stack is very like the C stack, in that it can hold data and return addresses. Indeed, during an interrupt it holds additional data and a return address - an interrupt being somewhat like a subroutine taken without warning.

However, the 6502 stack is small, and there is only weak support for addressing data within it, so it is often used only for return addresses (and for interrupts) - parameters for subroutines may instead be passed in the (limited) registers, or by shared memory (whether at agreed locations or by passing an address.)

As BDD says, the 65816 extends the 6502 in several ways, including better support for use of the stack.

I'm not sure what you might mean by 'outside of normal memory' - the 6502 has a simple and small memory model, within which the stack occupies a fixed 256-byte area. As to how memory is allocated between routines, the 6502 has nothing to say about it: it's a question of the prevailing conventions and the installed software.

There's another use of the concept of a stack, which is for operands, as seen in the Java VM but not the Lua VM, and as seen in Forth but not in C. I don't think this relates to your question.

I hope this helps a little!

Cheers
Ed

Johnny Starr, did the above responses answer your questions? Did they produce more questions? I was looking for something else and came across this again and figured I should find out if we're missing the question or if we addressed it adequately, since I'm little by little writing a primer on stacks [Edit: It's up, at http://wilsonminesco.com/stacks/ ] and I want to address the real questions people have that they might even be afraid to ask, in addition to giving some stack tricks that are simple but have not occurred to many. Any other questions or problems or misunderstandings you care to mention may end up helping quite a few others.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

As a complete aside, I was confronted with a Towers of Hanoi problem a while ago (in Mass Effect, of all places), which I remembered was one of the more interesting uses of stacks. Not something that has to go in a text, but might be a reference to "thinking with stacks" if you are planing to include something like that.