A Third Stack for xForth

[enso1]

As an aside, after briefly experimenting with a multi-stack forth 20 or so years ago, I also tried a curious take on ColorForth with multiple TOS registers, mapping 7 colors to ARM7 registers for local computation and using a single datastack for manually spilling/filling registers.

_ _ 100 ::: c@++ () c!++ --<<<

The above copies 100 bytes -- with apologies to my color-blind friends.

Here BLUE register was used as a counter, RED as source, GREEN as destination, and --<<< means decrement/loop to previous ::: of that color using that color register as a counter. Black () simply designates BLACK register as dest of the fetch as well as source of subsequent store (by its LHS or RHS position).

The registers were explicitly pushed and popped onto/from the datastack using properly-colored , and _ operators. It was no longer forth but felt surprisingly forth-like and incredibly efficient and expressive, if somewhat arcane.

Sorry for the OT comment, but I thought it might be interesting as it was the opposite of having multiple datastacks, as well as largely eliminating the need of local symbols (using colors instead, a mixed blessing perhaps).

[BruceRMcF]

enso1 wrote:

... as well as largely eliminating the need of local symbols (using colors instead, a mixed blessing perhaps).

Yeah, I'd view that as color becoming a part of the symbolism.

But that is indeed moving away from the Forth ideal of zero-register operations to maximum available register operations. It seems almost certainly like nothing that Chuck Moore would do, but it does fit into his philosophy of not worrying about compatibility with past practice and just develop the tool that meets your needs.

[enso1]

Funny you should say that... Chuck was indeed annoyed when I tried to discuss manual control of the datastack (which is kind of necessary for any multi-register practice), and I gave up trying to get him excited about that. And in those early days of ColorForth he did not want to think about alternate uses for colors ...

I still think my use of color makes more sense than his -- I'd rather have obvious, at-a-glance control of multiple registers on machines that have them, than waste color on controlling compile-time chores.

In practice, only primitives made heavy use of registers (and colors). Normal code was very forth-like, because normal function calls just pass data on the datastack using a single (black) TOS. The colored register code was more like a weird assembly language.

[GARTHWILSON]

Quote:

As a small Forth implementation, it is tempting to find a use for space that is only ever used during compilation. [...] A third stack can be used as a substitute for the local values available in larger Forth94/Forth2012 systems,

I waited to bring up the following since it's slightly changing the subject; but I'll bring it up because it may meet the real goal, just using a possibly unexpected path.

I've thought about a third stack for higher-precision cells like floats, or double-, triple-, or quad-precision integers, since stack operations get hairy when you have mixed lengths of cells; but this is different.  Rather than a stack, my idea is to use buffers at the end of memory, allowing a lot more than Forth94/Forth2012 afford.  I started it in the topic "dynamic memory allocator, methods, uses, limitations, etc." and went on to develop it and document it in my article "ALLOC, FREE, and RESIZE in Forth."

Attractions include (but may not be limited to) the following:

• You can access local variables the normal way, with !, @, +!, PERFORM, etc. rather than requiring you to use a limited set of special words like TO.
• You can have local arrays, which the Forth standard's way does not allow (unless there's something new in the standards which I have not kept up with).
• You can have large quantities of local data, including multiple arrays that are not limited to 256 bytes.
• I envision (but have not implemented yet) actual executable words that are used only during compilation to compile other code, this code being in a buffer, and when the compiling code has served its purpose, you can delete it without disturbing the normal dictionary or leaving any holes in memory, and just fix up a link field in the normal dictionary to bypass code that had been in a buffer.

I got the code going in Forth, and although the stack gymnastics were the worst I've ever had, it was easy to get it working.  The stack gymnastics would be minimized by using local variables, which this whole thing was mostly for, meaning it's a chicken-and-egg situation.  I've written assembly-language code for it for the '816, but not the '02, but backburnered it before I got around to testing the assembly-language code. 

Admittedly there's some overhead to setting up and deleting a buffer, and especially to adjusting buffer length or deleting a buffer that's not at the end of the chain, these last two things being a rarer need; but in some cases, it may turn out to be a better alternative to accomplish the goal.

[BruceRMcF]

GARTHWILSON wrote:

Quote:

As a small Forth implementation, it is tempting to find a use for space that is only ever used during compilation. [...] A third stack can be used as a substitute for the local values available in larger Forth94/Forth2012 systems,

I waited to bring up the following since it's slightly changing the subject; but I'll bring it up because it may meet the real goal, just using a possibly unexpected path.

I've thought about a third stack for higher-precision cells like floats, or double-, triple-, or quad-precision integers, since stack operations get hairy when you have mixed lengths of cells; but this is different.  Rather than a stack, my idea is to use buffers at the end of memory, allowing a lot more than Forth94/Forth2012 afford.  I started it in the topic "dynamic memory allocator, methods, uses, limitations, etc." and went on to develop it and document it in my article "ALLOC, FREE, and RESIZE in Forth."

Attractions include (but may not be limited to) the following:

• You can access local variables the normal way, with !, @, +!, PERFORM, etc. rather than requiring you to use a limited set of special words like TO.
• You can have local arrays, which the Forth standard's way does not allow (unless there's something new in the standards which I have not kept up with).
• You can have large quantities of local data, including multiple arrays that are not limited to 256 bytes.
• I envision (but have not implemented yet) actual executable words that are used only during compilation to compile other code, this code being in a buffer, and when the compiling code has served its purpose, you can delete it without disturbing the normal dictionary or leaving any holes in memory, and just fix up a link field in the normal dictionary to bypass code that had been in a buffer.

Yes, that does get into the areas that gforth uses their locals for, and then extends it further.

This "third stack" is more like, "suppose you got comfortable with using a Forth where the "R" stack was not, in fact, the return stack, so you could use it more flexibly than the Return stack can be used ... and then had to port your use of ">R" and "2R@" to a Forth where the R stack is, in fact, the return stack."

Grow down from the end of memory transitory buffers in that context would be the Fourth Stack ("A Fourth Stack for Forth"). That's intriguing, but like my Modules, something I am comfortably deferring until I get the core of my xForth up and running. Just this morning, I fixed a cute little bug ... in ENTER when I was adding 1 to the subroutine return address to turn it into a vector, I did not clear carry, explaining why I was sometimes seeing the "JMP (...)" instruction in zero page contain an address one bigger than it should have been.

The "executable that goes away" is one of the things I am aiming for with my Module system, either 4KB living in C64 Golden RAM, or 8KB living in a High RAM segment in the CX16.

Quote:

I got the code going in Forth, and although the stack gymnastics were the worst I've ever had, it was easy to get it working.  The stack gymnastics would be minimized by using local variables, which this whole thing was mostly for, meaning it's a chicken-and-egg situation.  I've written assembly-language code for it for the '816, but not the '02, but backburnered it before I got around to testing the assembly-language code. 

Admittedly there's some overhead to setting up and deleting a buffer, and especially to adjusting buffer length or deleting a buffer that's not at the end of the chain, these last two things being a rarer need; but in some cases, it may turn out to be a better alternative to accomplish the goal.

Yes, for things like converting tab-delimited columns into CSV columns, those kind of flexible temporary buffers could be really handy. I could even see working with the information in the columns AWK-style as a column count with possibly variable size column contents, so not strictly speaking an array.

[GARTHWILSON]

Another possible usage that comes to mind, which I forgot to mention earlier, is a symbol table for use in assembling assembly-language code.  This would allow descriptive labels for branching and jumping in assembly-language code you assemble in your otherwise-Forth application, and once the assembly of that portion is complete, the symbol table ceases to exist.

[BruceRMcF]

GARTHWILSON wrote:

Another possible usage that comes to mind, which I forgot to mention earlier, is a symbol table for use in assembling assembly-language code.  This would allow descriptive labels for branching and jumping in assembly-language code you assemble in your otherwise-Forth application, and once the assembly of that portion is complete, the symbol table ceases to exist.

Excellent case ... I am going to be eventually aiming for a less obscure assembler for xForth, and while many primitives don't need very many labels, having them available can be great for readability.

Indeed, coming full circle, putting the operation code on the top of the T-stack with the address mode being the word that assembles the instruction means that there is a lot of freedom in generating the value address ... but the base case is more familiar to someone with 6502 assembly language experience. Kind of along the lines of:

Code: Select all

MASK1: :AND W ),Y;

where "W" might be a global constant or might be a local constant, and MASK1 is the label you are talking about.

[enso1]

Also, top memory is a good place for a temporary symbol table for local symbols, which are very similar to what the assembler needs and you can probably reuse most of the code. That is precisely what I was talking about a few posts back (and how I've implemented it a couple of times in the past). Surely if it's a good idea for an assembler, it is an even better idea for local symbol resolution (to an Rstack frame, of course, if you want locals)!

The obvious place for dynamic runtime local storage is a frame on the return stack -- you have but no choice to close the scope prior to returning, regardless of the threading model used. Otherwise, you have manual control of another stack, complete with remembering and documenting what's on it and associated bugs when you forget to close it out across calls. For safety you may decide that you don't need that kind of hassle and keep dynamic scope frames, keeping the frame pointer on the return stack of course, and data on this extra stack, which of course makes no sense at all (because you may as well just keep everything on the return stack).

To take this strange experiment further, there is a number of questionable four-stack projects, or at least vocalizations on the interweb, if you search. Why -- I don't know.

I can totally see the utility of a floating-point datastack as a separate entity, or take it further and have more stacks for other datatypes.

[BruceRMcF]

enso1 wrote:

... The obvious place for dynamic runtime local storage is a frame on the return stack -- you have but no choice to close the scope prior to returning, regardless of the threading model used. Otherwise, you have manual control of another stack, complete with remembering and documenting what's on it and associated bugs when you forget to close it out across calls. ...

While using the return stack forces you to set things up so that scope is closed, and using a third stack does not, in the second case, that is just a trade-off between ease of implementation and ease of use ... if you want, you can surely put the same automatic scope closure into a third stack frame ... and using transitory memory at the end of the dictionary space is a natural for that, with a linked list of opened items together with the xt's of their closer's being used by a version of ";" brought into the search order in front of the simpler ";", walking a linked list, executing the xt on the opening item pointer or id, releasing that bubble of RAM and proceeding until the null end of linked list market is hit.

[enso1]

That pretty much covers the implementation issues!

[BruceRMcF]

enso1 wrote:

That pretty much covers the implementation issues!

Except for the implementation of them.

After all, I cannot figure how to get break points set in the Commander X16 emulator debugger -- or the monitor in the emulated system -- and I cannot figure out how to get the SuperCPU64 emulator in VICE to get a ROM that lets it execute the Kernel "print to the screen" functions, so after making what felt like substantial progress in the first week of debugging, my debugging of my xForth core has bogged down.

I don't want to add anything more that would require testing and debugging until I have a working Forth system with a working command line interpreter to escape from the mud of assembling language debugging into the steady flow of Forth debugging.