Stack machines and the 6502 IS

[LBSC]

I want the full 6502 instruction set and to learn things about stack machines. Stack machines are a real pain and I couldn't find much help.

[DerTrueForce]

I can't help you with stack machines, but the 6502 instruction set is in the datasheets, and in the Eyes & Lichty programming manual, which unfortunately appears to no longer be available for free.

[GARTHWILSON]

I find stack machines to be very intriguing. Stack machines and the 6502 are two rather unrelated things; but you can of course run Forth on the '02—it just won't perform like a stack machine would. From my links page:

• Forth processors (stack computers)
• Stack Computers: The New Wave The entire book is available to read online or to download.
• Many links for stack computers and Forth material

The E&L programming manual DerTrueForce mentioned really is the best AFAIK. No 65xx enthusiast should be without it. Even though it's not free anymore, it's definitely worth the price.

[LBSC]

GARTHWILSON wrote:

I find stack machines to be very intriguing. Stack machines and the 6502 are two rather unrelated things; but you can of course run Forth on the '02—it just won't perform like a stack machine would. From my links page:

• Forth processors (stack computers)
• Stack Computers: The New Wave The entire book is available to read online or to download.
• Many links for stack computers and Forth material

The E&L programming manual DerTrueForce mentioned really is the best AFAIK. No 65xx enthusiast should be without it. Even though it's not free anymore, it's definitely worth the price.

If the 6502 is not a stack machine, why is there a "stack pointer" and instructions like POP?

[DerTrueForce]

As I understand it, a stack machine uses only stacks. No arbitrarily-addressable memory is presented to the programmer. Of course, I could be wrong.

The 6502 implements a stack in part of the main memory (Page 1 as it's called). The processor mainly uses it as a convenient place to store return adresses, but the programmer can make use of the stack with instructions such as PLA and PHA(PulL(pop) A and PusH A).

The 6502 presents the programmer with plenty of arbitrarily-addressable memory, and a number of ways in which to address that memory. If my understanding of what a stack machine is is correct, then this means that the 6502 is not a stack machine

[BigEd]

Indeed, the 6502 is an accumulator machine. A stack machine's instructions need zero addresses for an operation. An accumulator machine's instructions need one address for an instruction. A machine with a register file can have two-address instructions, if the result of a computation must land in one of the operand registers, or three-address instructions, if the result can go into any register. (Or a machine could have no accumulator and no register file, but always read from memory, operate, and write back to memory.)

A four-address machine could have a next-instruction address in every instruction, so it doesn't need an incrementing PC and programs need not be sequential in memory.

Read up on 'The Story of Mel' if you like!

[BigEd]

More helpfully: the 6502 is a machine, like many others, with some support for a stack. Garth has written a lot about stacks here:
http://wilsonminesco.com/stacks/basics.html

[GARTHWILSON]

DerTrueForce wrote:

As I understand it, a stack machine uses only stacks. No arbitrarily-addressable memory is presented to the programmer. Of course, I could be wrong.

The stack machine always allows arbitrary addressing and indexing of memory; but addresses and indexes go through the data stack (which is separate from the return stack, simplifying various things). So for example let's say you have 32 cells available for a data stack, but you have 50 variables. No problem. Suppose one variable is called FOOBAR1. Invoking FOOBAR1 puts the address of that variable's data space on the data stack. From there, you can store data to it, fetch data from it, increment the variable, etc.. so if you say

Code: Select all

    FOOBAR1 @

(the "@" is "fetch"), the address of FOOBAR1 gets replaced with the data fetched from that address. First you added the address of FOOBAR1 to the top of the data stack (increasing the stack depth by one), then after the fetch, that cell now holds the data instead of the address.

Now suppose FOOBAR2 is an array. It can be any length, as long as it fits in the available memory. Invoking FOOBAR2 puts the base address of the array's data space on the data stack. From there, you can add an index to it to get the address of the desired element in the array.

Now suppose the array is a table of addresses of other data or routines, meaning that the address you come up with will point to the address of the desired routine. IOW, it's a double indirect.

There's really no end to the flexibility. This is essentially what the Forth programming language is about. Forth and stack machines go together. Stack machines' native language basically is Forth, even if you use it to write a compiler or interpreter for another language.

When the 6502 is used as a virtual stack machine, the return stack is the usual page-1 hardware stack, and the data stack goes in zero page, not just because of the greater efficiency, but also because of the additional addressing modes afforded in zero page. Since there's no native stack pointer for zero page on the 6502, you use X. X won't be needed for much of anything else when you operate this way, and the few times you do need it, you can save it temporarily and then restore it. In the first example above, X would get decremented twice (with DEX) to add a cell to the data stack, and the address of FOOBAR1 would get put in that new cell in zero page. Fetching then consists of LDA (0,X). (Assuming 16-bit cells, the '02 requires incrementing the address and do it again to get the second byte. The 65816 is able to do all 16 bits at once, with one-fifth as many instructions.)

My treatise on 6502 stacks (plural, not just the page-1 hardware stack) has a few sections on doing things this way on the 6502 without particularly using Forth.

[whartung]

LBSC wrote:

If the 6502 is not a stack machine, why is there a "stack pointer" and instructions like POP?

Almost every CPU has either a dedicated stack pointer and POP/PUSH instructions, or generic instructions against de facto registers (for example, the PDP-11 uses R6 for its stack operations, notably JSR and what not, but uses generic MOV instructions for POP and PUSH).

In contrast to machine like the early Burroughs machines, which was a dedicated stack machine, a rather complicated one at that in contrast to the simpler Forth based ones.

The B5000 is very much like the UCSD P-machine (which is a virtual stack machine, like the Java VM) - a high level stack machine designed to with the idea of being the target of high level language compilers.

[LBSC]

Thank you a lot you wonderful people but, I am reading a book called "Programming The 6502" by Rodnay Zaks. There it explained that the memory is divided into pages (256 bytes each) and that the stack is the page 1 of memory (256-511). What if my memory has only one page? What if my memory has no page at all? It also explained that POP just pulls a value from the top of the stack and PUSH pushes a value to the top since stack memory can only be accessed one address at a time.

[BigEd]

> What if my memory has only one page? What if my memory has no page at all?

This might be a good test of your understanding of memory decoding!

The 6502 has 16 address lines, and will always use 16 bit addresses. In that address space, the stack operations will always be in page one - which means addresses in the range $0100 to $01FF.

Which RAM chips serve those addresses - if any - is down to the system design, and specifically the glue logic which activates the RAM chips for each access. Almost all 6502 designs will have RAM which responds to all addresses in the range, say, $0000 to $3FFF, and therefore the RAM will respond to zero page accesses, stack accesses, and absolute accesses.

If it happens that the size of the RAM is very small - say for example just 64 bytes - then the same RAM locations will serve for page zero, page one, and many other pages. The 6502 doesn't care. The software which is running will need to be organised in such a way that the 64 bytes is enough, and the zero page usage doesn't interfere with the stack usage.

> POP just pulls a value from the top of the stack and PUSH pushes a value to the top since stack memory can only be accessed one address at a time.

Yes, kind of. But note that some operations cause multiple stack accesses and therefore, in rapid succession, access multiple bytes within the stack. For example, RTS takes two bytes off the stack, and RTI takes three. It's true that PLA and PHA only take or put a single byte.

Hope this helps.

[BigEd]

(Possibly you're thinking of the term 'page' as if it was something like the term 'bank' whereby there are several areas of physical memory which can go in and out of the memory map. That's not the same thing. 'Page' is just a set of memory locations within an aligned 256-byte range, which is to say locations which share the same high address byte: Page nn is all locations like $nnxx, for any xx.)

[LBSC]

BigEd wrote:

> What if my memory has only one page? What if my memory has no page at all?

This might be a good test of your understanding of memory decoding!

The 6502 has 16 address lines, and will always use 16 bit addresses. In that address space, the stack operations will always be in page one - which means addresses in the range $0100 to $01FF.

Which RAM chips serve those addresses - if any - is down to the system design, and specifically the glue logic which activates the RAM chips for each access. Almost all 6502 designs will have RAM which responds to all addresses in the range, say, $0000 to $3FFF, and therefore the RAM will respond to zero page accesses, stack accesses, and absolute accesses.

If it happens that the size of the RAM is very small - say for example just 64 bytes - then the same RAM locations will serve for page zero, page one, and many other pages. The 6502 doesn't care. The software which is running will need to be organised in such a way that the 64 bytes is enough, and the zero page usage doesn't interfere with the stack usage.

> POP just pulls a value from the top of the stack and PUSH pushes a value to the top since stack memory can only be accessed one address at a time.

Yes, kind of. But note that some operations cause multiple stack accesses and therefore, in rapid succession, access multiple bytes within the stack. For example, RTS takes two bytes off the stack, and RTI takes three. It's true that PLA and PHA only take or put a single byte.

Hope this helps.

Thanks!

[GARTHWILSON]

Here's an example where having a RAM size even less than a whole 256-byte page still lets you have zero-page (ZP, or page-0) access for the extra addressing modes available there, and page-1 access for hardware-stack use. Hopefully it's not too hard to follow.

The 6532 RIOT (RAM, I/O, and timer) IC was intended to minimize the chip count back before microcontrollers were ubiquitous. It had 128 bytes of RAM, addressed with 7 address lines (A0 through A6) and a RAM-select-not input pin. Suppose you make your address decoding in a simple system such that RAM is selected anytime A15 and A14 are low. (The RIOT has its own phase-2 input, so you don't have to derive OE\ and WE\ signals.) Now those 128 bytes of RAM, all 128 bytes, will show up at
addresses $0000-007F,
and again at $0080-00FF,
and again at $0100-017F,
and again at $0180-01FF,
and again at $0200-027F,
and again at $0280-02FF,
and again at [...] up through $3FFF.

So is there ZP access? Sure. Is there page-1 access for the hardware stack? Again, yes. Is there access above that? Yes, but there's no reason to use it with so little RAM, since ZP access is more efficient, and there's nothing you can do with RAM in other pages that you can't do in page 0 or 1 except accommodate more memory (which we don't have in this case). So you could initialize the stack pointer at $1FF by doing LDX #$FF, TXS, and use ZP starting at address $0000 and going up. The stack will also show up at $007F and going down, so just make sure that as your use of ZP goes up, they don't use up all the available $7F bytes of RAM and overlap and corrupt something. Corruption could happen because for example if the stack reached as far as writing down to $1EE, that's also $006E in this example, so hopefully you don't need to get up that high with your ZP variables.

BTW, 6502 parlance uses "pull" instead of "pop" for the opposite of push; so when you see "pull" in the books and data sheets, don't be confused. It's the same thing as "pop" in other processors. (It makes more sense to me anyway, since "pop" implies some kind of small explosive rupture, along with the accompanying noise. )

[BigDumbDinosaur]

GARTHWILSON wrote:

BTW, 6502 parlance uses "pull" instead of "pop" for the opposite of push; so when you see "pull" in the books and data sheets, don't be confused. It's the same thing as "pop" in other processors. (It makes more sense to me anyway, since "pop" implies some kind of small explosive rupture, along with the accompanying noise. )

For some reason, every time I read of someone "popping" the stack I think of a teenager squeezing pimples. "Push" and "pull" are, in my opinion, better for describing the corresponding stack operations because the two words are antonyms.