Re: Avoid treating the stack as an array [Re: "Back & Forth" is back!]

Paul Rubin <no.email@nospam.invalid> writes:

The 100+ occurrences of DUP, DROP, and SWAP are either an abstraction
inversion (with a smart compiler, the data ends up in registers that
could be named by locals)

I don't see an inversion here.  The programmer-visible stack abstracts
(ideally) the registers in one way, the programmer-visible locals
abstracts them in a different way.

And if we look at the VICHECK example from Nick Nelson's Better Values
<http://www.euroforth.org/ef22/papers/nelson-values-slides.pdf> the
version with locals, followed by the version that eliminates the
locals:

: VICHECK {: pindex paddr -- pindex' paddr :} \ Checks for valid index
\ paddr is the address of the data, the first cell of which contains
\ the array size
    pindex 0 paddr @ WITHIN IF \ Index is valid
        pindex paddr
    ELSE \ Index is invalid
        Z" Invalid index " pindex ZFORMAT Z+
        Z" for " Z+ paddr >NAME 1+ Z+ \ >NAME does not work for separated data
        Z" length " Z+ paddr @ ZFORMAT Z+
        ERROR
        0 paddr \ Use zeroth index
    THEN ;

: VICHECK ( pindex paddr -- pindex' paddr ) \ Checks for valid index
\ paddr is the address of the data, the first cell of which contains
\ the array size
    over 0 2 pick @ WITHIN 0= IF \ Index is invalid
        Z" Invalid index " 2 PICK ZFORMAT Z+
        Z" for " Z+ OVER CELL- @ Z+ \ Add NFA from extra cell
        Z" length " Z+ OVER @ ZFORMAT Z+
        ERROR
        NIP 0 SWAP \ Use zeroth index
    THEN ;

So by keeping the values on the stack you not just eliminate their
repeated mention, but also eliminate one branch of the IF.  With a
more capable Forth system a synthesis of the two approaches is
possible:

: VICHECK ( pindex paddr -- pindex' paddr ) \ Checks for valid index
\ paddr is the address of the data, the first cell of which contains
\ the array size
    over 0 2 pick @ WITHIN 0= IF \ Index is invalid
        {: pindex paddr :}
        Z" Invalid index " pindex ZFORMAT Z+
        Z" for " Z+ paddr >NAME 1+ Z+ \ >NAME does not work for separated data
        Z" length " Z+ paddr @ ZFORMAT Z+
        ERROR
        0 paddr \ Use zeroth index
    THEN ;

Or one could factor out the code between IF and THEN and stay within
the confines of VFX:

: VIERROR {: pindex paddr -- 0 paddr :}
    Z" Invalid index " pindex ZFORMAT Z+
    Z" for " Z+ paddr >NAME 1+ Z+ \ >NAME does not work for separated data
    Z" length " Z+ paddr @ ZFORMAT Z+
    ERROR
    0 paddr \ Use zeroth index
;

: VICHECK ( pindex paddr -- pindex' paddr ) \ Checks for valid index
\ paddr is the address of the data, the first cell of which contains
\ the array size
    over 0 2 pick @ WITHIN 0= IF \ Index is invalid
        VIERROR
    THEN ;

The check can be simplified, which also simplifies the stack handling:

: VICHECK ( pindex paddr -- pindex' paddr ) \ Checks for valid index
\ paddr is the address of the data, the first cell of which contains
\ the array size
    2dup @ u>= IF \ Index is invalid
        VIERROR
    THEN ;

or they are stack traffic whose cost has to be
compared with the cost of indexed references to locals in the return
stack.

That check often results in the code without locals winning, but that
is, for a large part, due to suboptimal implementations of locals.
Ideally a perfect compiler will produce the same code for code using
locals and for equivalent code using stack manipulation words, because
the data flow is the same.  This actually works out in the case of lxf
processing various implementations of 3DUP, including a locals-based
one; see <2024Apr10.090038@mips.complang.tuwien.ac.at>.  However, in
general Forth systems do not produce perfect results.

I have now looked at what happens for the first two variants of
VICHECK; I have defined the non-standard words as follows to make it
possible to compile the code:

defer dummy
: z" [char] " parse 2drop postpone dummy ; immediate
defer zformat
defer z+
defer >name
defer error

I looked at 3 systems: Gforth (because I work on it); lxf (because it
produces the best results in the 3DUP case); VFX (because it's the
system Nick Nelson uses).  The numbers below are the number of bytes
of native code:

locals    stack
401       336   gforth-fast (AMD64)
179       132   lxf 1.6-982-823 (IA-32)
182       119   VFX FX Forth for Linux IA32 Version: 4.72 (IA-32)
241       159   VFX Forth 64 5.43 (AMD64)

I'd agree that they aren't necessary "juggling" which evokes
permuting stuff in the stack outside the usual FIFO order.  That does
happpen a little bit though, with OVER, ROT, etc.

In particular, in Starting Forth ROT is illustrated with a juggler
(you see the juggling balls right beside her), and the swap dragon
comments: "I hate jugglers".

https://www.forth.com/wp-content/uploads/2015/03/ch2-rot.gif

- anton
--
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: https://forth-standard.org/
   EuroForth 2024: https://euro.theforth.net