Forth-eV Wiki

From willett!dwp@vax.cs.pitt.edu Wed Jan 26 02:43:08 1994
Return-Path: <willett!dwp@vax.cs.pitt.edu>
Received: from vax.cs.pitt.edu by ks.mpi-dortmund.mpg.de (4.1/SMI-4.1MHS-mpi-1.4.93)
	id AA13404; Wed, 26 Jan 94 02:42:51 +0100
Received: from willett.UUCP by vax.cs.pitt.edu (5.65/1.14)
	id AA16578; Tue, 25 Jan 94 20:30:25 -0500
Date: Tue, 25 Jan 94 06:53:28 EDT
From: dwp@willett.pgh.pa.us (Doug Philips)
Subject: Part 1 of 1 of SVAR.TXT
Message-Id: <9401250653.0.UUL1.3#5129@willett.pgh.pa.us>
To: plewe@mpi-dortmund.mpg.de
Content-Length: 8666
X-Lines: 219
Status: RO

Here is code that implements stack variables, in Standard
Forth.  The point of stack variables is that they act exactly
like variables unless you use special commands, but when you
use those commands then a stack variable simulates an extra
stack using a linked list.  This allows easy recursion with
variables -- you set up new values when you recurse, and call
the old values back when you return.  It allows as many extra
stacks as you like, but they don't work as fast as real stacks
and they use twice as much memory.  On the other hand they all
share the same space, so none of these simulates stacks will
overflow until they all do.  There's no concern about how deep
to make each one.

If you need a linked list instead of a simulated stack, you've
got it.  The code could be easily generalized for other sizes
of data, but different data-sizes can't be mixed.

The useful commands:

SVARIABLE makes a new stack variable.
V-NEW ( aa -- ) saves the current data and pointer to backup,
        sets the pointer to the new backup.
V-OLD ( aa -- ) restores the data and pointer to the
        previous values.
V-PUSH ( x aa -- ) does V-NEW and puts the top stack item into the
        data-address.
V-POP ( aa -- x ) copies the current data onto the
        stack and does V-OLD .
V-PICK ( n aa -- x ) returns the nth saved data item.
.SV ( aa -- ) prints out the list of saved data.
VOID ( svar -- ) discards the backup data-items, leaving the
        original data (not the current data).
VOID-ALL voids all the stack variables.

A pair of hard-to-use subtle commands:

SACTION is a stack variable designed to hold execution tokens.
        Each of them should expect some sort of data with the
        data-address of a stack variable or backup-item on top,
        and it should return some sort of data with a flag on
        top. The flag will be used to indicate whether SSEARCH
        should continue.
        ( j* svariable-link -- j*' f )

SSEARCH ( i* svar -- j* f ) takes data with a stack variable
        or backup-item data-address on top, and returns some
        other data with a flag.  If the flag is false, then
        the execution token in SACTION was used on every
        backup item for the stack variable, and never returned
        true.  If the flag is true, then the action once
        returned true and no further items were checked.

Various internals:

>THREAD ( aa1 -- aa2 ) goes from the data address returned by a
        stack variable to the pointer to the old
        values.
THREAD> ( aa2 -- aa1 ) goes from the pointer to the data
        address.
PREVIOUS-SV> ( aa1 -- aa3 ) goes from the data address to the
        pointer to another stack variable.
LAST-SVARIABLE points to a linked list of all the stack
        variables.
POOL is a constant that says how many backup items are
        available for stack variables
FREELIST points to the first unused backup item.
CELLSLINK initializes the backup items' pointers into a linked
        list.
ONLY-V? ( aa -- f ) says whether there is any previous data.

{

VARIABLE LAST-SVARIABLE
LAST-SVARIABLE OFF
: SVARIABLE   CREATE   0 , 0 , HERE LAST-SVARIABLE DUP @ , ! ;
256 CONSTANT POOL
CREATE FREELIST POOL 2* 1+ CELLS ALLOT
: CELLSLINK
     FREELIST POOL 0 DO
        0 OVER CELL+ !
        DUP 2 CELLS + DUP ROT ! LOOP
     OFF ; CELLSLINK
: >THREAD CELL+ ;
: THREAD> 1 CELLS - ;
: PREVIOUS-SV> 2 CELLS - ;



: V-NEW  ( aa -- ) FREELIST @
( aa 1st-free )    DUP 0= ABORT" Out of stack-variable space"
( aa 1st-free )    DUP @ FREELIST !
( aa free )        2DUP THREAD> 2 CELLS MOVE
( aa free )        SWAP >THREAD ! ;

: V-OLD ( aa -- )         DUP >THREAD @ DUP IF
( sv old-link )           DUP THREAD> ROT
( old-link old-value sv ) 2 CELLS MOVE
( )                       FREELIST @ OVER ! FREELIST ! ELSE
( sv old-link )           2DROP THEN ;

: V-PUSH ( x aa -- ) DUP V-NEW ! ;
: V-POP ( aa -- x ) DUP @ SWAP V-OLD ;


: V-PICK ( n aa -- x ) >THREAD SWAP ?DUP IF 0 DO @ LOOP
    THEN THREAD> @ ;
: ONLY-V? ( aa -- f ) >THREAD @ 0= 0= ;
: .SV ( svar -- ) CR >THREAD BEGIN DUP THREAD>
    @ U. @ ?DUP 0= UNTIL ;


SVARIABLE SACTION  ( SACTION will provide a flag )
( j* svariable-link -- j*' f )
: SSEARCH ( i* svar -- j* f )
             >R BEGIN
( j* )       R@ @ SACTION @ EXECUTE
( j* f )     R> OVER 0= WHILE
( j* f wida) >THREAD @ DUP WHILE THREAD> >R DROP REPEAT THEN
( j* f wida) DROP ;

: VOID ( svar -- ) BEGIN DUP >THREAD @ WHILE DUP V-OLD REPEAT
     DROP ;
: VOID-ALL   LAST-SVARIABLE @
    BEGIN DUP WHILE DUP PREVIOUS-SV> VOID  @ REPEAT  DROP ;
}

So far as I can tell, this code is 100% Standard with no
environmental dependencies.  Any system which has enough free
memory to load it, should give identical results over the minimum
required range of numbers with one exception:  The U. command in .SV
is not guaranteed to work with negative numbers (but will on all
reasonable systems).

Example:

SVARIABLE TEST
5 TEST !
12 TEST V-PUSH
TEST @ .  ( returns 12 ok )
TEST V-OLD
TEST @ .  ( returns 5 ok )

Something about how it works:

Each stack variable has 3 cell-size fields.
The first one holds the current data for this variable.
The second holds a pointer to a linked list, one that holds all
        the stacked data for this variable.
The third one holds a pointer for a linked list whose first
        element is in LAST-SVARIABLE.  You can use this linked
        list to keep track of all the stack variables.

For my convenience I put all the storage space in a single
area, after FREELIST .  CELLSLINK initializes the linkage.
FREELIST itself holds the pointer to the first free element.
Then each pair of cells has a cell for data followed by a
pointer to the next in line.  None of the other commands
depends in any way on this arrangement.  You could link in
pairs of cells anywhere in read-write space that won't be used
for anything else, and they'll work.  But if you try to do
something fancy that fails, that unlinks data from a stack
variable and doesn't link it into the unused list, it will stay
lost until you get it back.  The way I did it, you get it all
back with CELLSLINK.  But you also need to zero out all the
stack-variable pointers.  Of course, a fancy mistake could
corrupt any data in memory, since there's no telling where the
pointers might have pointed.  It might be better to start over
from scratch.  But if you restrict yourself to the easy
commands, you can't do too much damage.

If you try to do V-OLD on a stack variable that has no saved
values, nothing will happen.  This is harmless, although there
may be some unrelated problem if your program thinks it needs
to pop a simulated stack an extra time, when it doesn't.  You
can do ONLY-V? to find out whether there are saved values.

If you try to do V-NEW when there are no free elements, it
aborts with a message.  This makes it hard to completely
replace V-NEW with fast assembly code.  If you need speed and
you're sure your stacks won't overflow, you can remove that
behavior.  At any time you can estimate the high-water mark by
seeing where the highest non-zero data element is among the
currently-unused ones with FREELIST 1 CELLS - .SV .  It's
possible but not likely that your program might store and
restore zeroes in the same order, to fool you.


If you want to write your own fancy commands to manipulate
these linked lists, it helps to use >THREAD and THREAD> and
perhaps PREVIOUS-SV> .  Then if you later rearrange the
structure of the fields you won't have to rewrite your new
commands as much.

SSEARCH allows very fancy manipulation.  You put the execution
token for some action into SACTION, and give SSEARCH a stack
variable.  SSEARCH will do the action on each succesive
data-item, back through the list.  The action returns a flag.
If it returns a true flag then SSEARCH quits.  So, for example,
.SV could be written as:

: U.0 U. 0 ;
: .SV ['] U.0 SACTION V-PUSH ." top " SSEARCH
     DROP SACTION V-OLD ;

Each time, the action is to print out the number and leave the
flag that says to keep going.  At the end we get rid of the 0
flag.  We use V-PUSH so that .SV could be called inside of some
other SSEARCH command.

I find that sometimes SSEARCH saves me time and detail work,
but it isn't as easy to use as I'd like.  Something about the
syntax doesn't make it obvious exactly what's needed.  It's
possible to make it do really complicated Rube-Goldberg things
with it, that look simple but that take discipline to debug.
And while the code is short, it may be less efficient and
harder to read than just grinding out the result.  I'm cautious
about it.  Maybe someone will find a syntax that makes it all
more obvious.