Not your run of the mill control flow

[JimBoyd]

I mentioned elsewhere that [BEGIN] and [UNTIL] may not be needed on a system with EVALUATE .

[JimBoyd]

These are reasonably generic versions of the new LOAD and THRU .

Code: Select all

VARIABLE HISTORY
: LOAD  ( BLK# -- )
   DUP 0= ABORT" CAN'T LOAD 0"
   BLK @ >IN @ 2>R
   >IN OFF BLK !
   INTERPRET
   BLK @ HISTORY !
   2R> >IN ! BLK ! ;
: THRU  ( U1 U2 -- )
   >R
   BEGIN
      5 ?CR
      DUP U.  LOAD
      R@ HISTORY @ 1+ TUCK U<
      DONE? OR
   UNTIL
   R> 2DROP ;

Only words from the Forth-83 Standard are used in the versions presented below. INTERPRET is from the controlled reference words and 2DROP is from the double number extension word set. All other words are from the required wordset.

Code: Select all

VARIABLE HISTORY
: LOAD  ( BLK# -- )
   DUP 0= ABORT" CAN'T LOAD 0"
   BLK @ >IN @ >R >R
   0 >IN ! BLK !
   INTERPRET
   BLK @ HISTORY !
   R> R> >IN ! BLK ! ;
: THRU  ( U1 U2 -- )
   >R
   BEGIN
      DUP U.  LOAD
      HISTORY @ 1+ R@ OVER U<
   UNTIL
   R> 2DROP ;

In the definition of LOAD it may be tempting to store the value of BLK in HISTORY before INTERPRET when it is stored in BLK . Don't do it! With the version of LOAD which saves BLK in HISTORY it must be done AFTER INTERPRET because INTERPRET could change the block number if a screen has --> or the fancier version of [UNTIL] .
I mentioned in a previous post that a version of THRU which is compatible with --> makes it possible to chain together all the screens for a word spanning multiple screens without causing problems if those same screens are also in a range loaded with THRU. It is my hope that this will encourage Forth programmers keeping source in screens to use a structured layout rather than that unreadable horizontal format for source. I'm definitely in support of tools which encourage readable source.
This:

Code: Select all

SCR# 125 
// NUMBER?
: NUMBER?  ( ADR -- D FLAG )
   RB
   1+ DUP C@ ASCII # - DUP 3 U<
   IF
      BASE.TABLE + C@ BASE !
      COUNT
   THEN
   DROP
   DPL ON
   COUNT ASCII - <> DUP>R +
   COUNT DIGIT DUP>R  AND 0
   ROT
   -->

SCR# 126 
// NUMBER?
   BEGIN
      1- CONVERT COUNT VALID?
   WHILE
      DPL OFF
      DUP C@ VALID?
   UNTIL
   THEN
   1- C@ BL =  R> AND
   R>  ?EXIT
   >R DNEGATE R> ;

vs this:

Code: Select all

SCR# 125
// NUMBER?
: NUMBER?  ( ADR -- D FLAG )  RB 1+ DUP C@ ASCII # - DUP 3 U<
   IF   BASE.TABLE + C@ BASE ! COUNT   THEN   DROP DPL ON COUNT
   ASCII - <> DUP>R + COUNT DIGIT DUP>R  AND 0 ROT   BEGIN   1-
   CONVERT COUNT VALID?   WHILE   DPL OFF DUP C@ VALID?   UNTIL
   THEN   1- C@ BL =  R> AND R>  ?EXIT >R DNEGATE R> ;

[JimBoyd]

JimBoyd wrote:

This post concerns a technique used on Forth systems with indirect threaded code (ITC). It may work with other threading models.
Although the example from M. L. Gassanenko's paper "Dynamically Structured Codes" wasn't really self modifying code, it certainly is not your run of the mill control flow.
Just as EXECUTE takes the address of a word's Code Field and launches that word, ENTER takes the address of a fragment of threaded code and 'launches' that fragment. The address must align on what Gassanenko calls an active 'threaded code element', or a TCE. An active TCE is an address which holds the CFA of a Forth word. The 'threaded code fragment' must also exit (or branch somewhere which exits or aborts).

I've noticed that some Forth programmers are uneasy about leaving a value on the return stack without removing it, and with good reason. I must admit that the definition of ENTER seems a little odd.

Code: Select all

: ENTER  ( T-ADR -- )  >R ;

An address is placed on the return stack followed by EXIT or its equivalent, which is compiled by semicolon.
Here is a functionally equivalent definition of ENTER .

Code: Select all

: ENTER  ( T-ADR -- )
   [ ASSEMBLER ] IP [ FORTH ] ! -;

Since -; does not compile EXIT , this version of ENTER is the same size.
Although do-colon changes the value of IP , what I wish to point out is that it first pushes the current value in IP onto the return stack. The address on the data stack is stored in IP . This version only works because ! (store) is a primitive. It stores the address in IP , drops the two values from the data stack and goes to NEXT . NEXT resumes address interpretation starting at the address T-ADR . When an EXIT is encountered, execution resumes in the word which called ENTER .

High level Forth words can branch using ?BRANCH and BRANCH . ENTER is similar to a subroutine call for high level Forth, with one major difference. The destination of the "subroutine call" is specified at run time which is like a computed GOSUB from BASIC .
I have the following in a few places in my Forth's system loader.

Code: Select all

XXXX ENTER

where XXXX is a literal number known, or computed, at compile time. This is like a high level subroutine call, or a non computed GOSUB.

The following uses of ENTER are like a computed GOSUB .

Code: Select all

   R@ ENTER
   <SOME.VARIABLE> @ ENTER
   <SOME.VALUE> ENTER

or even just ENTER by itself if the word using it requires an address to be on the data stack.

Code: Select all

: TEXECUTE  ( T-ADR -- )  \ Execute trailing part of a high level word.
   ENTER ;

An STC version of ENTER would not just compile a subroutine call to an address known at compile time. It would not be this:

Code: Select all

: ENTER  ( T-ADR -- )
   $20 C,  , ; IMMEDIATE

An STC version of ENTER for the 6502 would look like this:

Code: Select all

: ENTER  ( T-ADR -- )
   1- >R ;

In an STC Forth for the 6502, any time an address is copied from the return stack for use with ENTER it would need adjusted.
For example, FORK would change from this:

Code: Select all

: FORK  ( -- FLAG )
   TRUE  R@ ENTER  FALSE ;

to this:

Code: Select all

: FORK  ( -- FLAG )
   TRUE  R@ 1+ ENTER  FALSE ;

Which is why I initially stated that it is a technique for an ITC Forth.

[GARTHWILSON]

Thanks.  This kind of thing has crossed my mind before, but I never did it.  I don't remember what I might have wanted it for (and ended up taking a different approach).  Do you have real-life example usages?

[JimBoyd]

GARTHWILSON wrote:

Thanks. This kind of thing has crossed my mind before, but I never did it. I don't remember what I might have wanted it for (and ended up taking a different approach). Do you have real-life example usages?

I do have some real-life examples. They may not be what M.L.Gassanenko envisioned in his paper Dynamically Structured Codes , but it's still early.

I've mentioned before that my Forth has EVALUATE . Since WORD parses from a BLOCK or the text input buffer, my Forth's EVALUATE saves the current values of TIB and #TIB as well as BLK and >IN .

Code: Select all

: EVALUATE  ( ADR N -- )
   TIB #TIB @ 2>R
   #TIB ! (IS) TIB
   BLK 2@ 2>R
   BLK OFF >IN OFF
   INTERPRET
   2R> BLK 2!
   2R> #TIB ! (IS) TIB ;

(IS) gets compiled by IS and TO . Although IS will only write to the PFA of a DEFERred word and TO will only write to the body of a VALUE , (IS) will write to the body of anything.
This version of EVALUATE has a section which is similar to LOAD or LINELOAD . I can't have EVALUATE call LOAD or LINELOAD directly because both abort if trying to "load" block zero. I can use ENTER to enter the body of LINELOAD , which is used by LOAD , and return. The following is used twice in EVALUATE

Code: Select all

#TIB ! (IS) TIB

I can reuse this section without factoring out a word useless for anything else.

Code: Select all

: EVALUATE  ( ADR CNT -- )
   TIB #TIB @ 2>R
   LIT [ >MARK ] ENTER
   0 0 LIT
   [ ' LINELOAD >BODY DUP TRUE
     " LOAD 0" COUNT MATCH ?HUH
     + , ]
   ENTER
   2R>
   [ >RESOLVE ]
   #TIB ! (IS) TIB ;

The following line:

Code: Select all

     " LOAD 0" COUNT MATCH ?HUH

searches for the string in LINELOAD and returns the offset to the end.

Code: Select all

: LINELOAD  ( LINE# BLK# -- )
   DUP 0=
   ABORT" CAN'T LOAD 0"
   BLK 2@ 2>R
   BLK !  C/L * >IN !
   INTERPRET  2R>
   BRANCH [ BLK.2! , ] -;

Here is the decompilation of EVALUATE

Code: Select all

SEE EVALUATE 
EVALUATE
 16390  2761 TIB
 16392  2623 #TIB
 16394  3593 @
 16396  4768 2>R
 16398  3286 LIT 16416 
 16402 13953 ENTER
 16404  3325 0
 16406  3325 0
 16408  3286 LIT 11109 
 16412 13953 ENTER
 16414  4791 2R>
 16416  2623 #TIB
 16418  2230 !
 16420  7834 (IS)
 16422  2761 TIB
 16424  2480 EXIT
36 
 OK

This version of EVALUATE is 14 bytes smaller. ENTER has a body size of 4 bytes, a 2 byte code field, 6 byte name field and a 2 byte link field for a total of 14 bytes.
I also saved a couple of bytes with two other words: VOCS and ORDER . VOCS shows the VOCABULARY tree structure and is recursive, but not in the sense that the entire word is recursively called.

Code: Select all

: VOCS  ( -- )
   [ ' FORTH >BODY ] LITERAL 0  CR
   [ <MARK ]
   ?STACK  DUP>R SPACES
   DUP BODY> >NAME ID. CR
   VOC-LINK @
   BEGIN
      2DUP 2- @ =
      IF
         DUP 2- 2- R@ 2+ LIT
         CS-ROT  [ <RESOLVE ] ENTER
      THEN
      @ ?DUP 0=
   UNTIL
   R> 2DROP ;

The first line does not take part in the recursion; however, everything that follows does take part. The original version of VOCS factored out the recursive part as a :NONAME word. Although this version is only two bytes smaller, it's much easier to use with TRACE . Tracing by hand is fine when initially working out the logic for a word. Once a word is defined, the TRACE word is much more convenient. With the original version, I would have to either manually enter the addresses for <IP and IP> , the start and end limits for the trace range, or give the headerless word a name.
It's also possible to have a word with a recursive part within a larger recursive part.

ORDER is not recursive. It reuses a section of code.

Code: Select all

: ORDER  ( -- )
   CONTEXT
   LIT [ >MARK ] ENTER
   CURRENT
   [ >RESOLVE ]
   CR DUP BODY> >NAME ID. ." : "
   @
   BEGIN
      DUP BODY> >NAME ID. CR
      2+ @ ?DUP  0EXIT
      9 SPACES
   AGAIN  -;

ENTER can also be used with other tools for diagnostics.
Tracing my Forth's new FORGET can be problematic. The new FORGET has NEXT> . NEXT> restores NEXT which switches off tracing. The word which was in the process of being traced resumes normal execution without tracing. Since The trace word I use, a modification of Blazin' Forth's trace word, single steps and waits for a key-press to continue, ENTER can help.

Code: Select all

TRACE FORGET  OK
.S EMPTY  OK
FORGET BAD.WORD 
NAME      EMPTY 
CURRENT   29282 
@         29282  2604 
DUP       29282  9637 
CONTEXT   29282  9637  9637 
!         29282  9637  9637  2590 
          29282  9637 
?HUH      29278 65535 
>LINK     29278 
NEXT>     29267 TRACING OFF

Trace prints the name of the word which is about to be called and displays the data stack contents. The last line is where I pressed the RUN/STOP key to stop tracing before NEXT> was called. This not only stops the trace, it calls quit.
The following shows where I resume tracing FORGET . Instead of calling FORGET directly, I use ENTER to "GOSUB" into the body of FORGET . Including the headerless word for FORGET's new (FIND) , there are ten words to skip.

Code: Select all

TRACE FORGET  OK
' FORGET >BODY 20 + ENTER 
UNLINK    29267 
SINGLE    29267 
DUP>R     29267 
FENCE     29267 
@         29267  2531 
LIT       29267 29218 
UMAX      29267 29218 12054 
U<        29267 29218 
(ABORT")      0 
VOC-LINK  EMPTY 
R@         2675 
TRIM       2675 29267 
VOC-LINK  EMPTY 
@          2675 
DUP       26741 
2-        26741 26741 
2-        26741 26739 
R@        26741 26737 
TRIM      26741 26737 29267 
@         26741 
?DUP      24043 
0=        24043 24043 
?BRANCH   24043     0 
DUP       24043 
2-        24043 24043 
2-        24043 24041 
R@        24043 24039 
TRIM      24043 24039 29267 
@         24043 
?DUP      24027 
0=        24027 24027 
?BRANCH   24027     0 
DUP       24027 
2-        24027 24027 
2-        24027 24025 
R@        24027 24023 
TRIM      24027 24023 29267 
@         24027 
?DUP      24010 
0=        24010 24010 
?BRANCH   24010     0 
DUP       24010 
2-        24010 24010 
2-        24010 24008 
R@        24010 24006 
TRIM      24010 24006 29267 
@         24010 
?DUP      14303 
0=        14303 14303 
?BRANCH   14303     0 
DUP       14303 
2-        14303 14303 
2-        14303 14301 
R@        14303 14299 
TRIM      14303 14299 29267 
@         14303 
?DUP      12165 
0=        12165 12165 
?BRANCH   12165     0 
DUP       12165 
2-        12165 12165 
2-        12165 12163 
R@        12165 12161 
TRIM      12165 12161 29267 
@         12165 
?DUP       9641 
0=         9641  9641 
?BRANCH    9641     0 
DUP        9641 
2-         9641  9641 
2-         9641  9639 
R@         9641  9637 
TRIM       9641  9637 29267 
@          9641 
?DUP          0 
0=            0 
?BRANCH   65535 
R>        EMPTY 
DUP       29267 
DP        29267 29267 
!         29267 29267   872 
LIT       29267 
@         29267  2077 
UMIN      29267 29218 
LIT       29218 
!         29218  2077 
HERE      EMPTY 
LIT       29267 
BRANCH    29267  3053  OK

ENTER can be used to enter into the body of a high level word, with or without tracing, for diagnostic purposes. It can not be used to enter into the middle of a DO LOOP without causing problems, nor can it be used to enter into the middle of code which temporarily places items on the return stack; however, a word could be written which places the appropriate parameters on the return stack and calls ENTER .

In summary, not only can ENTER save a few bytes, it is also a handy diagnostic tool.
Regarding what M.L.Gassanenko mentions in his papers, I'll need to study that further.
[Edit: Corrected spelling: I just noticed that I misspelled M.L.Gassanenko's last name.]

[JimBoyd]

GARTHWILSON wrote:

JimBoyd wrote:

GARTHWILSON wrote:

Dr Jefyll wrote:

One of the words I added to my version of FIG Forth is NIF (short for "not if").

Wow, looking at my own code, there are enough occurrences of 0= IF that I think that would pay for itself in memory, so there's no penalty for the faster execution. I think I would call it something else though unless "NIF" is already in common use, because it looks like a short form of "nifty" and definitely did not make me think "NOT IF." NOT in Forth XOR's the value with -1, rather than doing 0=.

I think I saw it called -IF but it has been a while and I can't remember where.

IF0 or IF_0 would be pretty intuitive.

What about these?
IFF -- IF FALSE
WHILEF -- WHILE FALSE
UNTILF -- UNTIL FALSE

[SamCoVT]

JimBoyd wrote:

Code: Select all

: FORK  ( -- FLAG )
   TRUE  R@ 1+ ENTER  FALSE ;

Ooooooo... this one is fun. I wanted to print out some binary numbers so I tried:

Code: Select all

: enter 1- >r ;  ok
: fork true R@ 1+ enter false ;  ok
fork . 0  ok
: test fork . ;  ok
test -1 0  ok
: print01 if 1 else 0 then 1 u.r ;  ok
5 print01 1 ok
0 print01 0 ok
: testmany fork print01 fork print01 fork print01 cr ;  ok
testmany 111
0
01
0
011
0
01
0
 ok

print01 prints a single 0 or 1 (using u.r so as to not print a space - I forget who showed me that, but it was someone here so thanks!). testmany is supposed to print all combinations of 3-digit binary values. What I actually got was not what I was expecting, but after thinking about it I realized it was exactly what I asked for. The issue is that it has to do all of the right hand forks before it will re-evaluate the left hand fork. I have the correct number of CRs, but not all of the digits for each line. Here is my "fix":

Code: Select all

variable dig1  ok
variable dig2  ok
variable dig3  ok
: printdigs dig1 @ print01 dig2 @ print01 dig3 @ print01 cr ;  ok
printdigs 000
 ok
: testmany fork dig1 ! fork dig2 ! fork dig3 ! printdigs ; redefined testmany  ok
testmany 111
110
101
100
011
010
001
000
 ok

I never would have thought to write a FORK word for a non-multitasking system, but I can see where it might be useful.

[JimBoyd]

You could define print01 as:

Code: Select all

: PRINT01   1 AND  0 .R ;

[JimBoyd]

JimBoyd wrote:

You could define print01 as:

Code: Select all

: PRINT01   1 AND  0 .R ;

This works on my system. A negative argument to SPACES (used by .R) prints nothing. Other systems might need print01 defined as this:

Code: Select all

: PRINT01   1 AND  1 .R ;

Although it seems reasonable to me that a negative argument to SPACES should result in zero spaces without an error because SPACES takes a signed value.

[JimBoyd]

SamCoVT wrote:

JimBoyd wrote:

Code: Select all

: FORK  ( -- FLAG )
   TRUE  R@ 1+ ENTER  FALSE ;

Ooooooo... this one is fun. I wanted to print out some binary numbers so I tried:

Code: Select all

: enter 1- >r ;  ok
: fork true R@ 1+ enter false ;  ok
fork . 0  ok
: test fork . ;  ok
test -1 0  ok
: print01 if 1 else 0 then 1 u.r ;  ok
5 print01 1 ok
0 print01 0 ok
: testmany fork print01 fork print01 fork print01 cr ;  ok
testmany 111
0
01
0
011
0
01
0
 ok

print01 prints a single 0 or 1 (using u.r so as to not print a space - I forget who showed me that, but it was someone here so thanks!). testmany is supposed to print all combinations of 3-digit binary values. What I actually got was not what I was expecting, but after thinking about it I realized it was exactly what I asked for. The issue is that it has to do all of the right hand forks before it will re-evaluate the left hand fork. I have the correct number of CRs, but not all of the digits for each line. Here is my "fix":

Code: Select all

variable dig1  ok
variable dig2  ok
variable dig3  ok
: printdigs dig1 @ print01 dig2 @ print01 dig3 @ print01 cr ;  ok
printdigs 000
 ok
: testmany fork dig1 ! fork dig2 ! fork dig3 ! printdigs ; redefined testmany  ok
testmany 111
110
101
100
011
010
001
000
 ok

I never would have thought to write a FORK word for a non-multitasking system, but I can see where it might be useful.

Code: Select all

: TESTMANY
   FORK  1 AND $30 +  PAD C!
   FORK  1 AND $30 +  PAD 1+ C!
   FORK  1 AND $30 +  PAD 2+ C!
   PAD 3 TYPE CR ;

Using ASCII for clarity:

Code: Select all

: TESTMANY
   FORK  1 AND ASCII 0 +  PAD C!
   FORK  1 AND ASCII 0 +  PAD 1+ C!
   FORK  1 AND ASCII 0 +  PAD 2+ C!
   PAD 3 TYPE CR ;

ANSI Forth:

Code: Select all

: TESTMANY
   FORK  1 AND [CHAR] 0 +  PAD C!
   FORK  1 AND [CHAR] 0 +  PAD 1+ C!
   FORK  1 AND [CHAR] 0 +  PAD 2+ C!
   PAD 3 TYPE CR ;

[SamCoVT]

JimBoyd wrote:

... it seems reasonable to me that a negative argument to SPACES should result in zero spaces without an error because SPACES takes a signed value.

And so it does. The 2012 standard specifically denotes this behavior:

ANS 2012 wrote:

SPACES ( n -- ) If n is greater than zero, display n spaces.

I see that Tali2 assumes it is unsigned, so negative numbers give you LOTS of spaces, but passing it 0 does give you 0 spaces. I'll have to fix (add) the negative number handling.

JimBoyd wrote:

ANSI Forth:

Code: Select all

: TESTMANY
   FORK  1 AND [CHAR] 0 +  PAD C!
   FORK  1 AND [CHAR] 0 +  PAD 1+ C!
   FORK  1 AND [CHAR] 0 +  PAD 2+ C!
   PAD 3 TYPE CR ;

2+ isn't in the 2012 ANS standard. Once I wrote it, this compiled and worked great. I totally forgot about PAD and that this is exactly what it was intended to be used for.

[JimBoyd]

SamCoVT wrote:

2+ isn't in the 2012 ANS standard. Once I wrote it, this compiled and worked great. I totally forgot about PAD and that this is exactly what it was intended to be used for.

Code: Select all

: TESTMANY
   FORK  1 AND [CHAR] 0 +  PAD C!
   FORK  1 AND [CHAR] 0 +  PAD 1+ C!
   FORK  1 AND [CHAR] 0 +  PAD 2 + C!
   PAD 3 TYPE CR ;

The nice thing about words like 2+ and DUP>R , it's easy to see where to split the name in the source to make it compatible.

[JimBoyd]

GARTHWILSON wrote:

I believe FOR...NEXT is in the newest standards, probably as a concession to reduce newcomers' resistance to Forth, but I do like DO...LOOP and friends. I have 32-bit equivalents too, at http://wilsonminesco.com/Forth/32DOLOOP.FTH .

FOR and NEXT are not on the Forth 2012 Standard site.
I think the FOR NEXT loop may have been a low memory alternative to DO LOOPs for memory constrained systems.
Gforth has FOR and NEXT but not AFT , and it's not the only Forth system to have the FOR NEXT loop without AFT , not that anyone would claim Gforth is a minimal system.

[JimBoyd]

I found some interesting control flow words in the Forth literature. The word GEN , for generator, uses these control flow words. Here is the source for GENTEST , a word to test GEN .

Code: Select all

: GENTEST  ( -- )
   2 GEN CR .
   4 GEN CR 2 .R
   3 GEN CR 3 .R ;

Here is the test run:

Code: Select all

GENTEST 
0 
 0
  0
  1
  2
 1
  0
  1
  2
 2
  0
  1
  2
 3
  0
  1
  2
1 
 0
  0
  1
  2
 1
  0
  1
  2
 2
  0
  1
  2
 3
  0
  1
  2 OK

I will show what these words are and what they do in an upcoming post.
Now for the brain teaser. Can anyone figure out what GEN is doing and how?

[BruceRMcF]

JimBoyd wrote:

GARTHWILSON wrote:

I believe FOR...NEXT is in the newest standards, probably as a concession to reduce newcomers' resistance to Forth, but I do like DO...LOOP and friends. I have 32-bit equivalents too, at http://wilsonminesco.com/Forth/32DOLOOP.FTH .

FOR and NEXT are not on the Forth 2012 Standard site.
I think the FOR NEXT loop may have been a low memory alternative to DO LOOPs for memory constrained systems.
Gforth has FOR and NEXT but not AFT , and it's not the only Forth system to have the FOR NEXT loop without AFT , not that anyone would claim Gforth is a minimal system.

IIRC, Chuck Moore is an advocate of FOR NEXT.