Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site watnot.UUCP
Path: utzoo!watmath!watnot!ccplumb
From: ccplumb@watnot.UUCP (Colin Plumb)
Newsgroups: net.lang.forth
Subject: Re: FORTH control structures - A proposal
Message-ID: <12098@watnot.UUCP>
Date: Mon, 20-Oct-86 17:46:55 EDT
Article-I.D.: watnot.12098
Posted: Mon Oct 20 17:46:55 1986
Date-Received: Tue, 21-Oct-86 22:42:47 EDT
References: <12093@watnot.UUCP>
Reply-To: ccplumb@watnot.UUCP (Colin Plumb)
Distribution: net
Organization: U of Waterloo, Ontario
Lines: 159
Keywords: init-lists ?do  ?if
Summary: Additional stuff

: LINE-EATER  80 EXPECT DROP ;

  Here are a few things to add to my previous posting:

--It would be a good idea to *execute* INIT-LISTS before starting to use any of
the new control structures.  >RESOLVELIST will mess things up *badly* if you
give it phoney pointers.  You might also want to add INIT-LISTS to ABORT.

--Depending on how much you trust yourself, and if memory address 0 is vital to
the system, you might want to have >LISTRESOLVE check for a null list pointer,
or perhaps change the value of null from 0 to something else (maybe even an
explicit VARIABLE NULL).

--If there's demand from people who have chronically non-standard systems, I
can post definitions for things like BRANCH, ?BRANCH, (DO), etc., In FORTH.

--You can't use a  ... DO ... IF ... LOOP ... ELSE ... THEN ... syntax if you
follow some of the reccomendations I've seen around for defining ?DO. 
(If you haven't seen this, ?DO skips the entire loop if the initial index is    equal to the limit. It works like 2DUP - IF DO ... LOOP THEN)
A common definition is this:

: ?DO     COMPILE  2DUP   COMPILE  -    [COMPILE] IF  [COMPILE] DO ; IMMEDIATE
: DO      COMPILE  1      COMPILE  IF   [COMPILE] DO  ; IMMEDIATE
: LOOP   [COMPILE] LOOP  [COMPILE] THEN ; IMMEDIATE
: +LOOP  [COMPILE] +LOOP [COMPILE] THEN ; IMMEDIATE

 which is patently absurd, since it makes just plain DO-LOOP worse in both size
and speed _at_run_time_.  It would be far better to make these changes:

VARIABLE NULL     ( Junk variable for THEN to patch)
: ?DO    COMPILE  2DUP  COMPILE -   [COMPILE] IF   [COMPILE] DO ; IMMEDIATE
: DO    [COMPILE] DO    NULL  ; IMMEDIATE
          (NULL leaves phoney address for LOOP to patch)

 which wouldn't change the run-time behaviour of a DO-LOOP _at_all_.  (THEN has
no run-time behaviour. It just finds the last IF, and tells it the address to
branch to if the condition fails. It does this by putting the address to branch
to in an address left for it (on the stack). If NULL is left there, it just puts
garbage in NULL, and has no other effect.)

  Unfortunately, since both of these approaches use IF, and IFs have to be
properly nested, this doesn't solve the original problem.  It's hard to come up
with a _really_ elegant solution to this problem,  since LOOP and +LOOP have to
know whether the loop was started by DO or ?DO.  Since branching past a loop is
a forward branch, it's easy to use a linked list to store the branch addresses,
but the only way I could think of for LOOP to know whether DO or ?DO started the
loop (and thus whether it needs to patch a forward branch address or not) is to 
check the address it's supposed to loop back to, and compare it with the last
location that needs patching. If it finds they differ by 2, LOOP should patch
the address. Here's an example of when LOOP shold patch:

     null <--+ +--- ?DO-PTR
             | v
   ... (?DO) ___ ......
                 ^ 
     STACK ------+

 and an example of when it shouldn't:

     null <--+ +-- ?DO-PTR
             | v
   ... (?DO) ___ ...... (DO) ___ ......
                 ^               ^
                 |    STACK -----+
                 +-- STACK-1 

  There are other ways around this problem.  Another idea is to check the cell
just before the address to be LOOPed back to. If it contains (DO), don't patch.
If it contains 0 (or some other special value), do patch.  The fact that this
makes LOOP's behaviour depend on something other than its input data (the values
on the stack it uses, and a linked list pointer assigned to it), makes it seem
less elegant to me.  If anybody out there has any better ideas, please tell me!!
I'd love to hear them.

  The code to add this to what's not already in my last posting is here:

VARIABLE ?DO-LIST

: INIT-LISTS   IF-LIST 0!  BEGIN-LIST 0!  DO-LIST  0!  ?DO-LIST 0! ;
INIT-LISTS     ( Forgot this last time!)

: (?DO)  ( limit index --)   ( ?DO run-time part)
       R>         ( limit index addr)
                   ( Save return address.  Only necessary in high-level FORTH)
       -ROT       ( addr limit index) ( : -ROT  ROT ROT ;)
       2DUP = IF  ( addr limit index) ( If we don't want to do the loop...)
        2DROP     ( addr) ( ... get rid of the unnecessary limit & index,)
        @         ( addr') ( and fetch the address of the end of the loop)
      ( NOTE: A pre-incrementing FORTH is assumed)
       ELSE
        SWAP >R >R ( addr) ( put limit & index on return stack in usual order)
        2+        ( addr') ( skip end-of-loop address)
       THEN
        >R ;      ( ) ( restore modified return address)

: ?DO   ( -- old-list-ptr back-branch-addr)
       COMPILE (?DO)       ( compile run-time part)
       ?DO-LIST >LISTMARK  ( do this end of a forward branch)
       DO-LIST DUP @       ( save old DO-LIST)
       SWAP 0!             ( and get ready for this level of LEAVEs)
       <MARK               ( leave back-branch-addr for LOOP)
       ; IMMEDIATE

: LOOP  ( old-list-ptr back-branch-addr --)
       COMPILE (LOOP)      ( compile run-time part)
       DUP                 ( keep one copy of resolution address for reference)
       <RESOLVE            ( and resolve the other)
       ?DO-LOOP @          ( get address of last ?DO)
       - 2 =               ( and check if they're close)
        IF                 ( If so, we want to patch)
         ?DO-LOOP >LISTRESOLVE  ( DUP could have been added above, but that
                       would have required an ELSE DROP. Either way works.)
        THEN ; IMMEDIATE

: +LOOP  ( old-list-ptr back-branch-addr --)
       COMPILE (+LOOP)
       DUP <RESOLVE
       ?DO-LOOP @
       - 2 = IF
         ?DO-LOOP >LISTRESOLVE
       THEN ; IMMEDIATE

EXIT ( Ignore further text)

  Like last time, this code hasn't been tested. Use with caution.
(If somebody knows of a FORTH that can run on a VAX under UNIX, I could test
it, but it looks as if I'm gonna have to learn VAX assembler first.)


--One thing I've found useful is a ?IF word, which behaves like ?DUP IF
(You could try : ?IF  COMPILE ?DUP  [COMPILE] IF ; IMMEDIATE), but
doesn't test the value on the stack twice.  Such a word _should_ be written
in assembler for speed (Which is the whole POINT of not just using ?DUP IF),
but a high-level definition is:

: (?IF)  ( 0 -- | f -- f)
       R>         ( f addr) ( save return address)
       OVER IF    ( f addr) ( check flag)
        2+        ( f addr') ( skip branch address)
       ELSE       ( 0 addr)
        @         ( 0 addr') ( take branch)
        SWAP DROP ( addr') ( or NIP if you have it in assembler)
       THEN       ( f addr' | addr' )
       >R ;       ( f | )

: ?IF  ( --)
      COMPILE (?IF)
      IF-LIST >LISTMARK
      ; IMMEDIATE

  This should be fairly easy to convert to ML. (You only need to convert (?IF).)
 
Note: All _this_ code is my own work. You're welcome to use it for any purpose
      you wish.

 I hope you find this useful!     -Colin Plumb  (ccplumb@watnot.UUCP)

Quote    : LIFE  BEGIN  WORK WORK WORK WORK WORK  SLEEP SLEEP  REPEAT ;
  ( "WORK" 5 times is 5 cells.  "5 0 DO WORK LOOP" is 8, and slower as well.)