
	     The Hairiest Part of a Pyte-Stack

H3sm, Hohensee's 3-stack machine, has a return stack, a pointer stack, and
a "pyte" stack, which holds integers at various sizes. All pyte operations
are at Size, which is a virtual register affiliated with the pyte data
stack. The Current Size is maintained by the programmer, and copies of it
are often stashed on the return stack. I'm beginning to be tempted to do a
Size stack, and I'm more tempted to do a flags stack. Adding a flags stack
to H3m looks like it would be a net simplification, and performance gain.

The issues of variable size stack items on the H3sm pyte stack are worse
than I'd hoped, but they can be codified and perhaps abstracted tolerably.
This stuff is utterly bewildering when it's not working, involving some
subtle but crucial interactions. However, with a clear view of what must
happen, a tricky body of code can be coaxed into coherence with reasonable
effort. "variable-size stack items" then becomes a workable concept.

The worst point is when switching between the interpreter and the base
stack state of the system, the user context. The stack state of the
interpreter must "float" above the base stack state of the system.  There
are two points in H3sm at which the interpreter and user contexts cross.
The point at which a number that has been parsed by the interpreter and is
to have it's value placed on the stack is one. The other is whenever a
word is interpreted. The two words that perform these user/interpreter
transitions are both given names that are the mirror-image of thier
"actual" or user-context-only names. "drowod" is doword, and "rebmunxeh"
is hexnumber. These names are obfuscation as documentation, a technique
JET Thomas has mentioned in comp.lang.forth. These names are supposed to
be off-putting. I had tried for a while to keep two "frames" on the data
stack, but that was even more bug-prone and un-Forth-like than the present
approach.

Consider a "floating" stack context, that must not disturb the stack state
beneath it. The interpreter's stack effects are like unpredictable
staining of the stack above what the user is concerned with. This can be
of some use on rare occaisions, such as when deriving a double-precision
result for an operation, for example. In simple cases, an "undrop" or two
may be desirable. For the most part however, stack effects above the
current TOS are gone, lost, and may not even exist on many stack-machine
implementations.

In any case, what the interpreter left on the stack mustn't stain the user
state. That means several things. Than means the interpreter can't
underflow, or overflow. It means there are two types of state-crossing,
to-user and from-user. It means that the interpreter can have no net stack
effect between occurances of drowod and/or rebmunxeh. Rather, it means
that interpreter net stack effects between drowod and rebmunxeh are user
state effects. It means basically the entire interpreter must be tight as
a drum and coordinated vis-a-vis stack effects.

Those considerations apply to stack machines and stacks themselves
normally, for any "stack context". In H3m we also have the issue of the
two pyte data stack states being on different and variable Size "plies".

My current (1.3) H3sm setup is based on a couple things. The H3sm data
stack pointer points at the lowest byte of the current TOS, an occupied
location. I also assume that TOS in the user context is a pyte of the Size
at which a crossing is to be made. This requirement can be accomodated in
all cases, I believe, because not all Size changes have immediate stack
effects. The interpreter stack data begins tightly abutted to the base
stack state. There is no intervening padding. A copy of Size in the user
context is kept in the USize "variable", which is a plain threaded
variable, and not a virtual register. Here's an asciimatic of the
situation...  (tabs are 8 spaces)


	    the stack state the user is 	interpreter
		concerned with                   "staining"

 ------------base state, various pytes---/----interpreter cells

-----------------------------------------------------------------
      |     | | | | |                |^  |^       |        |        |    
      |     | | | | |                | A |   1    |  2     |  3     |    
      |     | | | | |                |   |        |        |        |    
--------------------------------------------------------------------------
		               |^        |				
                               |  Inull  |
                               |         |
                              -------------


The H3sm user state is of unknown and variable pyte sizes. The interpreter
works with machine cells mostly. The "1" is where you'll be if you're in
the interpreter and you have one item on the stack, as far as the
interpreter is concerned. If you are in the interpreter and you have no
items on the stack, you are actually overlapping the base state. Inull is
a vacant cell in the interpreter, and there is no telling what it is in
the user context. That is, Inull is where the interpreter stack context
starts.  The 3 ^'s show the byte-wise pyte stack pointer offsets for TOS
in the base context, TOS in the interpreter with nothing on it's sense of
the stack, and TOS with one item on the stack that the interpreter may
use. "A" is an occupied base state pyte. It's TOS of the pyte stack to the
H3m user. The border between A and 1 is where the user context data and
interpreter context "staining" abut.

There are two types of transitions to be accomplished without
desyncronizing the stack; to-user and from-user. They are effected in H3m
with, "bump" or "undrop", drop, cells, and USize. Consider the from-user
case. You are sitting at A, TOS, at the Size of A probably, and need to be
where? You are going to be putting things on the stack at Size=cell. You
therefor need to be at Inull, with Size=cell. Then the first push to the
stack will abut, but not clobber, the user TOS, A. How do we get to Inull?
From any Size context? Thusly...

		bump cells drop

"bump" is an undrop, and happens at the same size as A, putting us at "1".
We then change to Size cells, the interpreter's default Size. Then we
drop, and we are ready to push "1" onto the stack without clobbering "A",
but leaving no un-used stack space between A and 1. That's only good for
one transition though. "cells" clobbers the Size virtual register. We have
to save a copy of the user context Size or we can't get back. The actual
procedure (in pseudo-Forth) then is


		getSize USize store bump cells drop


and in H3m's m4 proto-assembler in the C sourcecode, in "drowod"....


		OP(sTOp)    
		SUB
		 OP(USize) 
		OP(pstore)
		OP(twopdrop)
		OP(cells_bd)


SUB and OP are m4 macros. The H3sm words, without C's restrictions on
token characters, are s->p, USize, p!, 2pdrop and cells_bd. That's
Size_to_pointer_stack, the USize pointer "variable", pointer_store,
two_pointer_drops, and bump_cells->Size_drop. (cells_bd may go away. It's
not worth the name. "bump cells drop" is worth the verbosity.) That's the
second half of the context wrapper for H3m's interpreter warpper for it's
EXECUTE equivalent.

Going the other way, going TO the user context, we then have...


		bump USize->Size drop


Which is effectly thusly in drowod...


		SUB
		 OP(USize)
		OP(pfetch)
		OP(bump)
		OP(pTOs)
		OP(drop)
 

Passing values between the two contexts can be performed by leaving net
stack effects between performing these two transitions. This is what
rebmunxeh (hexnumber) does explicitly. It goes into user state, leaves a
value on the stack normally, and returns to the interpreter state. That
is, rebmunxeh does it's work by not having 0 net stack depth effect.
drowod may and will have depth effects also, but they are unknown to
drowod itself.

There are similar issues any time you change Size, but within a single
state context the issues of a Size change are simpler than the above.

Nuts, eh? Well, you don't change sizes THAT often, and this enables "+",
upshift, XOR and so on to work at 255 different pyte sizes at the VM
level.


July 2000
Rick Hohensee
rick@clienux.com

