6502.org

Camel Forth, which xForth is based upon, has, in addition to its data stack and return stack, a leave stack used during compilation.

As a small Forth implementation, it is tempting to find a use for space that is only ever used during compilation.

It become even more tempting when it turns out that after allocating my Buffer & Block information structure and the two string buffers required to support a Forth94/Forth2012 style S" in interpret mode ... the leave stack has room for over 32 addresses.

A third stack can be used as a substitute for the local values available in larger Forth94/Forth2012 systems, and it can be used to factor operations which might use the Rack, but which cannot be factored out if they do use the Rack.

Also, given the amount of space available for an auxiliary stack in this case (because User pages in xForth are always a single binary page on a page boundary), if the auxiliary stack grows down, and the Camel Forth leave stack grows up, the two uses of the space can share so long as they don't overdo it.

I call this the "T" stack for "Third Stack". I want this to be able to have stack frames (if used in place of local variable), so a byte is used to hold the T-Stack Pointer (TSP), and to hold the stack frame marker, TMARK. The semantics I have put in place (as yet untested, but the source assembles, so I will be starting to see if xForth02 runs sometime this week) are:

T-INIT ( -- ) Initialize the TSP to point to the top cell in stack (because the T-stack index points to the first free cell below the Top Of Stack), and TMARK to 0 (since there is no previous stack frame). TSP and TMARK are assembler labels -- neither TSP nor TMARK are directly available as Forth words.
NB: xForth ABORT executes T-INIT, so QUIT does not.

>T ( x -- T: x ) pop the data stack and push onto the T stack.

>>T ( x -- x T: x ) copy the data TOS and push onto the T stack

T> ( T: x -- x ) pop the T stack and push onto the data stack

T@ ( T: x -- x T: x ) copy the top of the T stack and push onto the data stack

T-MARK ( -- ) Push the current mark state on the top of the T stack and save the T stack index to the mark state

T-FREE ( -- ) If the mark state is 0, perform a T-INIT, otherwise restore to T stack index to the current mark state, and restore to the previous mark state.

T-PICK ( u T: x*n ... x*1 x*0 -- x*u T: x*n ... x*1 x*0 ) Fetch the u'th word to the data stack, where the 0th word is the one most recently pushed.

@T ( u T: <mark> x*0 x*1 ... x*n -- x*u T: <mark> x*0 x*1 ... x*n ) Fetch the u'th word to the data stack, where the 0th word is the one pushed after the most recent T-MARK.

T-PICK is so that words like T-DUP or T-OVER can be defined in Forth compiled code, without the same need for system specific knowledge as is needed to define "R" words in Forth compiled code -- without these extended T-stack operations residing in the core dictionary if they are not used.

@T is more focused on the use of T-stack frames for pseudo-local variable, so that helper words can be written like:

: LEN1 ( T: <mk> u1 ca1 -- u1 T: <mk> u1 ca1 ) 0 @T ;
: CA1 ( T: <mk> u1 ca1 -- ca1 T: <mk> u1 ca1 ) 1 @T ;
: LEN2 ( T: <mk> u1 ca1 u2 ca2 -- u2 T: <mk> u1 ca1 u2 ca2 ) 2 @T ;
: CA2 ( T: <mk> u1 ca1 u2 ca2 -- ca2 T: <mk> u1 ca1 u2 ca2 ) 3 @T ;

And LEN1 / CA1 remain the first STR (stack text reference) even if one or two more are pushed on top.

Is the "Rack" the return stack? I don't believe I've ever heard it called that before, but I like it.

I'd love to hear about your locals (or pseudo locals, or using this third stack in place of locals). Tali doesn't currently have any support for locals and they seem like they would be nice to have.

I've used locals in gforth, but I've never implemented them, and doubt I want to tackle it. You "declare" a local, which stores the top of stack there, and then use the locals like a VALUE ... including TO <<name>> if you want to change the value it holds. The system "knows" that there are locals on the return stack and a more extended ";" compiles the cleanup execution code before it compiles ``EXIT''.

And then that complicates ``TO'', which is much easier to design when it is just stuffing a cell value into the first parameter field of a CONSTANT, so that ``VALUE'' is just a synonym for ``CONSTANT''. Big Forths may have error checking on only using TO on appropriate words, but I prefer the approach "don't use this wrong, otherwise it will break, therefore test early, test thoroughly, and test often".

But locals are storing information on the Return Stack (yes, the "Rack" in the shorthand from the 80s), so they have to do a lot of stuff automagically that you can just do in ordinary Forth if you have a third stack that isn't affecting by calling a word or exiting from it.

So while it's just experimental, I figure that I can get much of the benefits of locals with the T stack. Plus it can be used for other things, like pushing the memory bank register contents at the start of a word that needs to move the memory bank, and then restoring the memory bank register at the end of the word, all done inside helper words, so the code wouldn't work if ">T" and "T>" were replaced by ">R" and "R>".

I'll post the primitives when I get home this evening, plus some gforth examples of using locals plus what the T-stack equivalents might be (speculative until I have my T-stack in a live forth system).

For example, the "T>" primitive is:
This is a direct threaded forth (so no code field for a primitive) with the hardware stack used as the Rack and the data stack a pair of ,X indexed byte stacks -- DL in zero page, DH in the stack page.

In this implementation, Y and A are "free" registers, so the T stack operations use a,Y address modes. (See attached file).
By the way, sorry for the shouting, but in the CBM universe, starting with the PET, there is a choice between upper case & graphic tiles or lower & upper case ... and the lower case and upper case are in reversed places compared to ASCII. So ALL CAPS turns into "all lower case" in upper and lower case mode, and sticking with all-caps ASCII means it's readable in either character set.

The simple example of Local programming that gforth uses is one of those pointless examples, because you certainly already have a more efficient version in the system you are programming the example in, but consider "MYMAX":
gforth uses "{ a b -- result }" syntax, but they have additional features that are not compatible with keeping locals on the Rack, so I'll use the more common Forth94 syntax:
If you want to use variable a and b for the first two inputs in various words, then rather than extending the compiler, the T-stack approach would define helper words:
If you want to add C and D sometimes, but not start a new frame:
The predecessor of local variables were "promiscuous" variables made re-entrant using the RACK. So for the MYMAX example, consider simple promiscuous variables:
Except if these promiscuous variables are also used in a higher level word that calls this word, this "inner" use of the promiscuous variables will over-write the "outer" use. So a re-use safe version of using promiscuous variables is:
... and wherever you have a few or a lot of Forth programmers writing that kind of verbose code, some of them are going to work out ways to automate the verbose parts, and so by the late 80s and 90s, Locals were becoming a thing in more of the larger Forth systems.

Thanks for the explanation. I've looked into locals a bit, but it looks more complicated than I currently have time for. Most of my programs are small, so I can just get away with using actual variables or values in many cases. The part I got hung up on was where exactly to store the names of the locals, where to store their values during runtime, and having to modify the name lookup (that's pretty much the entire thing - lol). It's nice to see simpler alternatives like this.

With your TMARK word, you are just saving the previous mark value on the T stack and then putting the index to that previous value into TMARK, creating a linked list so you can drop entire stack frames with TFREE, regardless of how many items were added, right? It looks like TMARK is just a single-byte memory location, as it only needs to hold a value (offset) for the Y register to use.

I always think of stack frames as things to separate return addresses from local variables on the return stack, but I can see they are very useful for data stacks too.

Yes ... for things like saving the contents of an I/O setting register so that it can be restored at the end of the word, the stack frame is not needed, and if that is the only use being made of the T stack, then T-FREE, T-MARK and @T can be left out.

Those words are included for creating helper words that act "as if" they are local variables, where @T fetches based on the stack position counting from the position below the mark position heading down (so the first T> done after T-MARK is accessed with "0 T@", the second one is "1 T@" and so on). The trade-off is that you have to be aware when you are creating a stack frame so you remember to clean it up when you are done, which is why I would define the helper |<<stuff>>| or +|<<stuff>>| to bear in mind whether that is a frame stuffer word that starts a new frame or extends an existing one.

Looking at gforth locals, they make heavy use of freedom to re-load the locals, so the first time { s1 s2 } is encountered, it puts s1 and s2 in a temporary name space and stores the tos values in spots reserved for them in their auxiliary locals stack (because they don't use the Rack to store their locals) ... but if it is encountered again, it store the current values on the top of stack into those locals. To define helper words to emulate that, I need !T as well as @T, to store values relative to the stack position counting from the stack frame marker. I'll add those if I run into a situation where I feel the need for that ... typically the way I would use locals is to keep changing values on the data stack and keep persistent values as locals.

And the gforth stack is set up so it can hold characters, cells, doubles or floats, and I wouldn't be willing to set aside all of the dictionary space required to implement that system in a Forth with less than 40KB available for the entire dictionary. Locals can be really handy for some Forth floating points algorithms, but if I were to add floats, I would do it with a float stack that grows down, so I could put an auxiliary "F" stack at the base of that area growing up.

Also, while the frame marker only occupies the low byte of it's T-stack position, I assume the base index mode when calling a routine in xForth16 (for the 65816) will be 16-bit index mode, which means in the 65816 version of the words, TSP and TMARK will label memory with 16-bit values and T-MARK will put a 16-bit value on the stack. So while I can imagine using the high byte for adding type information to a stack frame, I think I would refrain from that approach for better compatibility between xForth02 and xForth16/xForthGS.

Experimenting with using the T-stack in one of my Block words, 2>T and 2T@ eliminated my use of @T.

I may comment out @T and !T (which plays the role of "TO" for T-stack psuedo locals) and proceed with 2T> and 2T@ at the moment.

Why not use the return stack for locals? Since you have to close the scope prior to returning, it is absolutely natural to use it. Managing an extra stack does not seem worth it.

I've added locals to a few Forth-like languages by keeping a local 'symbol table' that tracks offsets into rstack, and adjusting the rstack on entry and exit -- really simple.

P.S. Although lately I tend to agree with Chuck that locals are not necessary, increase the overhead, and lead to sloppy code...

Yes, the Forth94 LOCALS are specified to be compatible with putting on the Return stack.

But there are tradeoffs, such as those I discussed above -- and some of those trade-offs is why gforth adopted the strategy of implementing their Locals with a third stack. After all, in the context of the Forth model, managing an extra stack is dead easy.
In addition to the other things already discussed, it allows doing it without keeping a local symbol table.

And also, when bringing up a port of a Forth implementation, refraining from more tinkering with the compiler words than necessary decreases the expected amount of debugging required.

There's a blurry line between necessity and convenience, and that line can be quite different from one application to another and one programmer to another. Allowing a feature without requiring it provides more flexibility but comes with an overhead that some would consider significant.

I'm feeling the same way with my latest project of adding floats to VTL02. The ability to run legacy unsigned integer code is causing some overhead that I am not in love with, and I will probably just create a VSL02 rather than a VTL02F.

By 'local symbol table' I mean that during the compilation of a word, I keep a device for resolving names to stack offsets, and clear/disable it at the end of a compilation.

Having a different stack does not change the fact that you need to resolve local names to offsets into _that_ stack. If you want to use actual offsets numbers instead of names, you can do that on any stack as well.

Indeed, having locals is very convenient, especially when you need to get something done instead of golfing to line up everything on the datastack. In my case, I've been a 'pleasure coder' for a while now, and I find the idea of finding solutions that match problems particularly enjoyable (and these solutions rarely follow the methodologies of 'computer science' as offered by ChatGPT, or University of Mumbai CS homework assignments that come up on Stack Overflow and such).

Yes ... having the T-stack means the possibility of more easily implementing gforth style locals at some future date, since, unlike the more restricted Forth94 locals semantics, the gforth locals semantics can't be implemented on the Return Stack. But that's not something I want to tackle at present, since the first priority with namespace management is supporting modules, which can be loaded from disk in the C64 and stored in High RAM in the CX16. And I am not going to be implementing modules until the current source is up and running ... I'm presently somewhere in COLD before it crashes, so I'm still hunting assembly bugs (typos so far).

The overhead for the T-stack proper is 280 bytes of dictionary space and 74 bytes of buffer less whatever would be allocated to the LEAVE stack if that space was not shared with the T-stack -- if 8 levels of LEAVE are allowed for, that implies an extra 54 bytes of buffer and two bytes for stack pointer and marker maintenance.

But I've got the Block buffers in the common top of the memory space holding the dictionary for the CX16/C64 -- $9700-$9EFF -- and I've got string buffers and block buffer management data in the $96xx page, and user pages are allocated on a page aligned address, so the default single user page is at $95xx. So after allocating the buffer management locations and the two string buffers, there'd be space in the LEAVE stack for 38 LEAVE levels, which is overkill. I am basically just giving the T-stack space that is left over due to page aligning Block buffers and user pages for efficiency.

And if signed integers are easier to work with alongside floats in a VTL-ish system, by all means go for it. The C64 with it's only-floats Basic was my first main home computer system, and if I had had proper integer operations as well, rather than just integers as a storage unit converted to floats for operations, I wouldn't have quibbled over whether they were signed or unsigned.

At present, during compilation of the word there is just the dictionary -- including the word being defined, though it is smudged until compilation or assembly is complete.

"Keeping a device for resolving names to stack offsets" means it would have to be kept somewhere, and define the primitives for managing it, and that's not something I want to add to the present process of bringing xForth up. And once I've brought it up, I can test the T-stack on the command line inside Forth, which is a lot more pleasant than grinding through the inner workings of the system on a monitor.

It's been a while, but it was minimal and contained (pretty much a temporary 48-byte array of 16 hashes/offsets and a 2 extra primitives to create and search). The code to accomplish this was kind of trivial, but my compiler was unorthodox in the first place.

Most importantly, syntactically, the only difference was the declaration of locals names at the top, and the rest of the syntax was intact! That, in my book, is a win.

I'm all for experimentation with Forth-like systems. It seems that you are happy with the extra stack, and I am looking forward to seeing where it takes you.

I know that there are some 6502 assembly wizards around here, but the 6502 assembly to create "a temporary 48 byte array of 16 hashes/offsets and 2 extra primitive to create and search" would not be trivial for me.
Yes, while it's been more "off" than "on", given that I've been programming in Forth off and on for over four decades now, I am more concerned with ease of factoring than with syntax. I only have the T-stack used in two parts of the BLOCKS section of the current xForth source, but in one of them, it lets me factor the words saving and restoring of the previous value of a High RAM bank register as parallel to the C64 words switching the Basic ROM out of the memory map and then restoring it.