6502.org • View topic - Not your run of the mill control flow

View unanswered posts | View active topics

Board index » 6502.org Users Forum » Forth

All times are UTC

Not your run of the mill control flow

Page 2 of 5

[ 63 posts ]

Go to page Previous 1, 2, 3, 4, 5 Next

Previous topic | Next topic

Author

Message

JimBoyd

Post subject: Re: Not your run of the mill control flow

Posted: Tue Sep 27, 2022 12:59 am

Joined: Fri May 05, 2017 9:27 pm
Posts: 895

barrym95838 wrote:

Jim, I knew you'd be the guy here to figure out how eForth's AFT works. Now all I have to do is figure out how you figured it out, then figure out a proper use for it ... :lol:

I definitely needed the examples for that. It looks like all duplicate spaces were deleted from the original control flow diagrams.

Here are two words using WHILE to branch from between AFT and AFT's matching THEN to between that THEN and NEXT .

Code:

               v-------------------------------------------<<   
FOR A0 ... AFT A1 ... WHILE A2 ... THEN A3... THEN A4... NEXT A5...
                         >>------------------------^
            >>--------------------------^

Here is the first word.

Code:

: N4  ( -- )
   9
   FOR
      ." X"
   AFT
      ." Y"
      5 R@ <
   WHILE
   THEN
      R@ .
   THEN
   NEXT ;

And the test run.

Code:

N4 X9 Y8 Y7 Y6 YYYYYY OK

Here is the other.

Code:

: N6  ( -- )  9
   FOR
      CR ." A0"
   AFT
      CR ." A1"
      5 R@ <
   WHILE
      ."  A2"
   THEN
      ."  A3"
   ELSE
      ."  A4"
   THEN
      ."  A5 "  R@ .
   NEXT ;

And the test run.

Code:

N6 
A0 A3 A5 9 
A1 A2 A3 A5 8 
A1 A2 A3 A5 7 
A1 A2 A3 A5 6 
A1 A4 A5 5 
A1 A4 A5 4 
A1 A4 A5 3 
A1 A4 A5 2 
A1 A4 A5 1 
A1 A4 A5 0  OK

The word N7 has a FOR NEXT loop within another FOR NEXT loop.

Code:

: N7  ( -- )  9
   FOR
      CR ." A0"
   AFT
      CR ." A1"
      5 R@ <
   WHILE
      ."  A2 " 3 FOR ." X" AFT ." Y" THEN R@ . NEXT
   THEN
      ."  A3"
   ELSE
      ."  A4"
   THEN
      ."  A5 "  R@ .
   NEXT ;

And it works well.

Code:

N7 
A0 A3 A5 9 
A1 A2 X3 Y2 Y1 Y0  A3 A5 8 
A1 A2 X3 Y2 Y1 Y0  A3 A5 7 
A1 A2 X3 Y2 Y1 Y0  A3 A5 6 
A1 A4 A5 5 
A1 A4 A5 4 
A1 A4 A5 3 
A1 A4 A5 2 
A1 A4 A5 1 
A1 A4 A5 0  OK

Multiple occurrences of AFT in a FOR NEXT loop will not work. The first AFT drops the backward branch data from FOR and replaces it with its own and a forward branch. A second AFT would drop the forward branch data from the first AFT , leaving its backward branch data. The matching THEN will not resolve the backward branch and abort.
This will not compile on my system.

Code:

: N9  ( -- )
   CR 3
   FOR    ." A0 "
   AFT    ." A1 "
   AFT    ." A2 "
   THEN   ." A3 "
   THEN   ." A4 "
      R@ .
   NEXT ;

So let's get tricky. The first AFT still has backward branch data on the control flow stack, so that is what must be resolved.

Code:

: N10
   CR 3
   FOR    ." A0 "
   AFT    ." A1 "
   AFT    ." A2 "
   THEN   ." A3 "
   TRUE
   UNTIL  ." A4 "
      R@ .
   NEXT ;

This is what gets compiled.

Code:

SEE N10 
N10
 31299  6707 CR
 31301  2266 3
 31303  4656 >R
 31305  7809 (.") A0 
 31311  3042 BRANCH 0 
16 
 OK

The forward branch from the first AFT does not get resolved resulting in a branch to address zero.
I typed

Code:

EAD :DIS

to see the rest of N10 .

Code:

EAD :DIS 
 31315  7809 (.") A1 
 31321  3042 BRANCH 31331 
 31325  7809 (.") A2 
 31331  7809 (.") A3 
 31337  3388 TRUE
 31339  2781 ?BRANCH 31325 
 31343  7809 (.") A4 
 31349  4740 R@
 31351  7568 .
 31353 31202 (NEXT)
 31355 31315 
 31357  2970 EXIT
44 
 OK

It is possible to tighten the compiler security so this doesn't happen. The control flow data consists of an address and a number.
One for >MARK and >RESOLVE .
Two for <MARK and <RESOLVE .

Code:

// FOR NEXT LOOP -- EXTRA SECURITY
: FOR  ( -- )
       ( N -- )
   COMPILE >R
   <MARK  2+ 2+ ; IMMEDIATE
: NEXT  ( -- )
   COMPILE  (NEXT)
   2- 2- <RESOLVE ; IMMEDIATE
: AFT  ( -- )
   6 ?PAIRS  DROP
   COMPILE BRANCH  >MARK
   <MARK  2+ 2+
   [COMPILE] CS-SWAP ; IMMEDIATE

Sixteen extra bytes to make sure:
FOR is only resolved with AFT or NEXT .
AFT is only resolved with THEN and NEXT in that order.

By the way, the version of Gforth on my desktop has FOR and NEXT but not AFT . I suspect it is because this version of Gforth does not have CS-DROP , just CS-PICK and CS-ROLL in accordance with the ANSI standard.
Since this version of Gforth uses the data stack for the control flow stack, I was able to add AFT to it.

Code:

\ AFT for gforth
: AFT  ( -- )
   2DROP DROP
   POSTPONE BRANCH >MARK
   POSTPONE BEGIN  DROP DO-DEST
   POSTPONE BUT ; IMMEDIATE

Code:

: BUT
   1 CS-ROLL ; IMMEDIATE

Anyone who notices that DO-DEST and thinks this version of Gforth's FOR NEXT loops are compatible with its DO LOOP's would be correct. Gforth's DO LOOP's only have two parameters pushed to the return stack, the limit and index. Gforth's FOR pushes a zero as a limit and the number on the stack as the index. Here is an example of a mixed FOR and DO loop in Gforth. Gforth's I is an alias for R@ .

Code:

\ this is weird
: test  50 for  cr i .  -10 +loop ;  ok
test 
50 
40 
30 
20 
10 
0  ok

Top

GARTHWILSON

Post subject: Re: Not your run of the mill control flow

Posted: Tue Sep 27, 2022 1:31 am

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8543
Location: Southern California

It would help me if I had some idea of what "AFT" stands for. "a forward transfer" is all I can think of, but that doesn't totally make sense. Some of this stuff is just too cryptic. I'm also going with IF_0, UNITL_0, etc..

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Top

JimBoyd

Post subject: Re: Not your run of the mill control flow

Posted: Tue Sep 27, 2022 1:55 am

Joined: Fri May 05, 2017 9:27 pm
Posts: 895

I think of the most basic FOR A0 AFT A1 THEN A3 NEXT loop like this.
The first time through the loop, and only the first time, A0 gets executed.
If the loop executes more than once, all the other times A1 gets executed, but not the first time through.
A3 always gets executed.

I also suspect the name AFT was a play on words, but I could be wrong. Fore and aft referring to the front and back of a ship.

Top

JimBoyd

Post subject: Re: Not your run of the mill control flow

Posted: Tue Sep 27, 2022 2:12 am

Joined: Fri May 05, 2017 9:27 pm
Posts: 895

And I think AFT might be short for After. After the first pass, do this bit between this location and THEN .

Top

JimBoyd

Post subject: Re: Not your run of the mill control flow

Posted: Fri Sep 30, 2022 11:39 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 895

When scotws started the topic Looping in a world without a BREAK statement, a few ideas were presented on how to proceed. Looking back, I think the best solution presented was to factor the loop out as a separate word. BREAK is just EXIT and CONTINUE is easy to implement. This version of CONTINUE goes back to the beginning of the word where it is used, not the beginning of a loop. As with EXIT , the level of control flow nesting in the word to be continued does not matter.
CONTINUE can even be used to restart a word from within a DO LOOP or in a DO LOOP nested within another, but it must be preceded with an UNLOOP for each level of DO LOOP nesting.
For example:

Code:

: DO.THIS
   5 0
   DO
      4 0
      ?DO
         <DO SOMETHING>
         <TEST>
         IF  UNLOOP UNLOOP CONTINUE  THEN  \ go back to start of DO.THIS
      LOOP
   LOOP ;

I'm not saying continuing a word with a DO LOOP is practical, I'm just saying it's possible.

Now to define CONTINUE .
This is my Forth's definition for RECURSE

Code:

: RECURSE  ( -- )
   ?COMP  LAST , ; IMMEDIATE

My Forth uses LAST so recursion is also supported in :NONAME words; however, some Forths define RECURSE like this:

Code:

: RECURSE  ( -- )
   ?COMP  LATEST NAME> , ; IMMEDIATE

Where the word LAST is replaced by the phrase
LATEST NAME> .
?COMP may or may not be present. It aborts if state is not compiling.
CONTINUE can be defined like this

Code:

: CONTINUE  ( -- )
   COMPILE BRANCH
   LAST >BODY , ; IMMEDIATE

Here are some other CONTINUE words for completeness.

Code:

: ?0CONTINUE  ( -- )  // COMPILING
              ( F -- )  // EXECUTING
   COMPILE ?BRANCH
   LAST >BODY , ; IMMEDIATE
: ?CONTINUE  ( -- )  // COMPILING
             ( F -- )  // EXECUTING
   COMPILE 0=
   [COMPILE] ?0CONTINUE ; IMMEDIATE

?0CONTINUE continues if the top of stack is false. ?CONTINUE continues if the top of stack is true.
Since CONTINUE branches to the beginning of a word, whether a loop is present or not, it can be used to eliminate tail recursion.

Code:

: GCD  ( N1 N2 -- N3 )
   TUCK MOD ?DUP 0EXIT RECURSE ;

Code:

: GCD  ( N1 N2 -- N3 )
   TUCK MOD ?DUP 0EXIT CONTINUE ;

Code:

: GCD  ( N1 N2 -- N3 )
   TUCK MOD ?DUP ?CONTINUE ;

Top

JimBoyd

Post subject: Re: Not your run of the mill control flow

Posted: Sat Oct 01, 2022 2:25 am

Joined: Fri May 05, 2017 9:27 pm
Posts: 895

Another nonstandard control flow word is CO , the coroutine word.
The high level definition is

Code:

: CO 2R> SWAP 2>R ;

Here is a low level definition for my Forth, which is a Forth-83 Standard ITC Forth.

Code:

CODE CO  (  R: ADR1 -- ADR2 )
         ( IP: ADR2 -- ADR1 )
   PLA  TAY  PLA  N STA
   IP 1+ LDA  PHA
   IP    LDA  PHA
   IP STY  N LDA
   ' EXIT @ 4 + JMP
   END-CODE

The code at ' EXIT @ 4 +

Code:

   IP 1+ STA
  <falls through to NEXT, the address interpreter>

With only one trip through the address interpreter, NEXT , this CO is about five times faster for only ten more bytes.
My Forth has a word WITH-WORDS which is used like this:

Code:

: <SOMEWORD>
   <do this once> WITH-WORDS <do this once for each word in the CONTEXT vocabulary> ;

For each word in the CONTEXT vocabulary, WITH-WORDS places that word's name field address on the stack. Here is a simple word to count all the words in the CONTEXT vocabulary.

Code:

: #WORDS  ( -- N )
   0  WITH-WORDS  DROP 1+ ;

When WITH-WORDS is defined with the primitive version of CO , #WORDS takes about 81% the time to run as it did before.
A longer word using WITH-WORDS is IN-NAME . This word takes about 96% the time to run.

Top

pjeaton

Post subject: Re: Not your run of the mill control flow

Posted: Sat Oct 01, 2022 6:29 pm

Joined: Wed Feb 23, 2005 9:20 am
Posts: 23
Location: Zurich, Switzerland

!if is probably what I'd go with, regardless of the clash with regular !

We used ! to mean NOT at university 30+ years ago, I use it in code, variables, comments...

_________________
P*h*i*l*l*i*p EEaattoon in real life

Top

JimBoyd

Post subject: Re: Not your run of the mill control flow

Posted: Sun Oct 02, 2022 7:52 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 895

It's certainly not what I would go with. Although I'm considering renaming 0EXIT to ?0EXIT (I'm still not sure about that), I will not rename it to something like ?!EXIT .
As for !IF , it kind of reminds me of C.
Speaking of C, chitselb has a word in pettil which is like the ternary operator from Ruby Java and C so he named it ?: . It consumes a flag from the data stack and executes one of the following two words before program flow resumes.

Code:

: TEST  ( FLAG -- )
   ?: EXECUTE.IF.TRUE  EXECUTE.IF.FALSE  EXECUTE.ALWAYS ... ;

chitselb had this source for ?:

Code:

: ?:   ( "name1" "name2" -- )
    ?comp compile (?:) ' , ' , ; immediate

There is the possibility of compiling an immediate word by accident.
Here is the source for an ITC Forth which avoids that problem.

Code:

CODE (?:)
   0 ,X LDA  1 ,X ORA
   0= IF  2 # LDY  THEN
   IP )Y LDA  W STA  INY
   IP )Y LDA  W 1+ STA
   CLC
   IP LDA  4 # ADC  IP STA
   CS IF  IP 1+ INC  THEN
   INX  INX
   0 # LDY  W 1- JMP
   END-CODE

: ?:  ( -- )
   ?COMP  COMPILE (?:)
   BL WORD FIND 2/ ?HUH ,
   BL WORD FIND 2/ ?HUH , ;
   IMMEDIATE

The source for ?HUH

Code:

: ?HUH  ( -F -- )
   0= ABORT" WHAT?" ;

?HUH aborts if the parsed name can't be found.
the phrase

Code:

BL WORD FIND 2/ ?HUH

is to insure that an immediate name is not compiled.

I'm not sure the high level protection is needed. The programmer just needs to remember that two words (other than the final exit) need to be compiled after ?: .
Although ?: is normally used like this:

Code:

... ?: TRUE.WORD FALSE.WORD ...

this will also work.

Code:

... (?:) TRUE.WORD FALSE.WORD ...

(?:) can be used like the following because BEGIN doesn't compile anything:

Code:

   ...
   (?:) TRUE.WORD
   BEGIN
      FALSE.WORD
      <OTHER LOOP STUFF>
   UNTIL
   ...

A flag is consumed on the first pass through the loop and either TRUE.WORD or FALSE.WORD will be executed. FALSE.WORD will be executed on each successive loop.
Here is another example. TESTTWO could take some time, so rather than AND the results from both tests, the quicker test is run first.

Code:

   ...
   TESTONE
   IF
      TESTTWO
      (?:) TRUE.WORD
   THEN
   FALSE.WORD
   <ALWAYS DO THIS PART>
   ...

This works because THEN does not compile anything, it just resolves the forward branch from IF .
FALSE.WORD is executed if either test returns a false flag. TRUE.WORD is only executed if both tests return a true flag.
So, should both ?: and (?:) exist, or should (?:) be renamed ?: ?

Top

GARTHWILSON

Post subject: Re: Not your run of the mill control flow

Posted: Mon Oct 03, 2022 7:25 am

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8543
Location: Southern California

JimBoyd wrote:

So, should both ?: and (?:) exist, or should (?:) be renamed ?: ?

I guess I can't really think of any reason to have the immediate compile-only word that compiles the other. I have a few words that others have built the protection into which I didn't think was really necessary, like 2LEAVE, 2?LEAVE, 2BOUNDS, 2I, and 2UNLOOP in my 32-bit DO...LOOP word set.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Top

BruceRMcF

Post subject: Re: Not your run of the mill control flow

Posted: Mon Oct 03, 2022 5:04 pm

Joined: Wed Aug 21, 2019 6:10 pm
Posts: 217

pjeaton wrote:

!if is probably what I'd go with, regardless of the clash with regular !

We used ! to mean NOT at university 30+ years ago, I use it in code, variables, comments...

I would still read it "Store If" in a Forth context, just like I might use /Select to mean an active low SPI select in a hardware context but understand /CELL to mean "divide by the Cell size" in a Forth context.

Top

GARTHWILSON

Post subject: Re: Not your run of the mill control flow

Posted: Mon Oct 03, 2022 8:29 pm

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8543
Location: Southern California

BruceRMcF wrote:

pjeaton wrote:

!if is probably what I'd go with, regardless of the clash with regular !

We used ! to mean NOT at university 30+ years ago, I use it in code, variables, comments...

I suppose you could use a trailing backslash instead which I think OrCAD did (although I haven't used OrCAD in many years). We also have /MOD and other such words in Forth, where the / means "divide." ! in at least some BASICs means the rest of the line is comments.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Top

BruceRMcF

Post subject: Re: Not your run of the mill control flow

Posted: Tue Oct 04, 2022 7:20 pm

Joined: Wed Aug 21, 2019 6:10 pm
Posts: 217

JimBoyd wrote:

I do think that the "Fore and Aft" was deliberate, but the verbose reading of AFT might be "once-then-afterward"

N @ FOR init AFT iterator THEN act NEXT

is "N fetch FOR init once-then-afterwards iterator THEN act NEXT"

Top

JimBoyd

Post subject: Re: Not your run of the mill control flow

Posted: Wed Oct 05, 2022 11:18 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 895

GARTHWILSON wrote:

JimBoyd wrote:

So, should both ?: and (?:) exist, or should (?:) be renamed ?: ?

I guess I can't really think of any reason to have the immediate compile-only word that compiles the other.

Neither can I. Naming the primitive ?: sounds good to me.

GARTHWILSON wrote:

I have a few words that others have built the protection into which I didn't think was really necessary, like 2LEAVE, 2?LEAVE, 2BOUNDS, 2I, and 2UNLOOP in my 32-bit DO...LOOP word set.

My opinion is that protection should be just enough to prevent things which obviously will not work, but not enough to get in the programmer's way.
Since a >MARK can not be resolved by a <RESOLVE and a <MARK can not be resolved by a >RESOLVE , compiler security to make sure >MARK is resolved by >RESOLVE and <MARK is resolved by <RESOLVE makes sense; however, in a Forth where LEAVE and ?LEAVE do not have an inline branch address, but use a third loop parameter, immediate compiler words are unnecessary.

Top

JimBoyd

Post subject: Re: Not your run of the mill control flow

Posted: Wed Oct 05, 2022 11:44 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 895

JimBoyd wrote:

This version of CONTINUE goes back to the beginning of the word where it is used, not the beginning of a loop. As with EXIT , the level of control flow nesting in the word to be continued does not matter.

Other programming languages use the name CONTINUE to continue a loop at the beginning, not to restart a function. The word EXIT can exit a word at any point, but it is not called BREAK . The word I presented does not even need to be in a loop. It restarts the word it is in. Perhaps it should have a more suitable name. Maybe something like RESTART or RERUN ?

Top

JimBoyd

Post subject: Re: Not your run of the mill control flow

Posted: Mon Oct 10, 2022 11:07 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 895

In my last post I indicated my dissatisfaction with the name CONTINUE as it implies continuing with the next iteration of a loop. It seems CONTINUE is a better name for a word which compiles a branch back to the beginning of a BEGIN loop without discarding the control flow information. Something like the following:

Code:

: CONTINUE  ( -- )
   CS-DUP  [COMPILE] AGAIN ; IMMEDIATE

Which would be used like this:

Code:

   BEGIN
      <SOMETHING0>
   CONTINUE
      <SOMETHING1>
   UNTIL 

This would be awkward to use in an IF THEN statement.

Code:

   BEGIN
      <SOMETHING0>
      IF   CS-SWAP CONTINUE  CS-SWAP  THEN
      <SOMETHING1>
   UNTIL

Therefore I find CONTINUE , as it is used in BEGIN loops, to be not very useful. This fragment compiles the same thing:

Code:

   BEGIN
      <SOMETHING0>
      CS-DUP  WHILE  AGAIN  THEN
      <SOMETHING1>
   UNTIL

but this is better.

Code:

   BEGIN
      <SOMETHING0>
      0=
      CS-DUP UNTIL
      <SOMETHING1>
   UNTIL

The versions which branch back to the beginning of a word can be nested deeply in other control flow structures because the branch address they compile is not from control flow data. I'd also like to initially have just two names. Consider the Forth-83 Standard's two branching primitives, BRANCH and ?BRANCH . BRANCH always branches and ?BRANCH only branches if the top stack value is false. BEGIN loops have the word AGAIN to compile a branch always back to BEGIN and the word UNTIL to compile a branch back to BEGIN if the top of stack is false. The Standard does not specify an immediate word to compile the word 0= followed by ?BRANCH .
I'd like to follow that example and specify two new words rather than CONTINUE ?CONTINUE and ?0CONTINUE .
For the first word, I'd like the name to mean something like AGAIN , but to begin the word at the start. For the second, I'd like something like UNTIL , but to branch back to the start of the word.

Code:

BACK  ( -- )  \ Branch back to beginning of definition.
?PASS  ( flag -- )  \ Branch back if the flag is false.

BACK always branches back to the beginning of the word.
?PASS only branches back if the flag is false. The implied meaning is if the flag is true then pass onto the rest of the word. If the flag is false "You shall not pass!"

Code:

: BACK  ( -- )
   COMPILE BRANCH
   LAST >BODY , ; IMMEDIATE
: ?PASS  ( -- )  // COMPILING
         ( F -- )  // EXECUTING
   COMPILE ?BRANCH
   LAST >BODY , ; IMMEDIATE

Code:

: BACK  ( -- )
   COMPILE BRANCH
   LATEST NAME> >BODY , ; IMMEDIATE
: ?PASS  ( -- )  // COMPILING
         ( F -- )  // EXECUTING
   COMPILE ?BRANCH
   LATEST NAME> >BODY , ; IMMEDIATE

Does anyone have a suggestion for better names?

Top

Page 2 of 5

[ 63 posts ]

Go to page Previous 1, 2, 3, 4, 5 Next

Board index » 6502.org Users Forum » Forth

All times are UTC

Who is online

Users browsing this forum: No registered users and 22 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum