
             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 a performance gain
at the lowest VM level.

The issues of variable-size stack items on the H3sm pyte stack are more
treacherous than I had 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. This was a "note to self", but is posted publicly
because now that I think I can express this, it makes more sense to me,
and hopefully will to others as well.

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. In other words, the interpreter has this to deal with
on every token. 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. (H3m doesn't have BASE yet.) 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. That 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, it seems, 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, a named pointer actually, and not a virtual register. Here's an
asciimatic of the situation...


            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, and bytes sometimes.* 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; interpreter-to-user and user-to-intepreter. They
are performed in H3m with, "bump" or "undrop", drop, cells, and USize.

Consider the user-to-intepreter 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 unix-style
restrictions on token characters, are 

	s->p USize  p!  2pdrop cells_bd 

That's Size_to_pointer_stack, the USize pointer "variable",
pointer_store, two_pointer_drops, and bump_cells->Size_drop.  That's the
second half of the context wrapper for H3m's interpreter wrapper for it's
EXECUTE equivalent.

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


                bump USize->Size drop


Which occurs 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.

Ridiculous? Well, you don't change sizes THAT often, and the more complex
cases won't be something everyone needs. More importantly, this enables
"+", upshift, XOR and so on to work at 255 different pyte sizes at the VM
level. There's no "Double Wordset" in H3sm. There's "double", "halve" and
a few others, and "double" for example is "Size is now twice what it was".


July 2000
Rick Hohensee
rick@clienux.com


* (Earlier H3m interpreters were written with a "char" that could be any
size, but the UTF-8 system as implemented in Bell Labs' Plan9 OS is
appealing. UTF-8 handles wide characters as sequences of bytes and some
logic, and is thus backward-compatible to ASCII. "Runes", which are
indices into a glyph set, are two bytes, but the actual text data is
handled as clumps of one to three bytes with conditional content. These
"big-bytes" are somewhat expensive to convert to Runes, but they are 
bytes.)

