Jump to content
IGNORED

TF, camel, FB Forth fun


GDMike
 Share

Recommended Posts

While studying on how I could "improve" Mark's SAMS code compiler, (still wondering if it's possible :))

I realized that using the TF BRANCH word was the key to making tail-call optimization in Indirect threaded Forth.

 

This version should be translatable to the other systems if one wanted to do it.

I am using the manual version name that Chuck Moore used in his Machine Forth.

 

The next trick would be to make it smart enough to know if the last word in a definition can be jumped to directly.

I did some preliminary testing for COLON and CODE words but it failed on DEFER.  (sounds familiar) 

 

Edit: GOTO changed. We do not need to auto-increment the *IP register because we are jumping somewhere else. This made it a bit faster

 

\ tail call optimizizing semicolon from machine forth    nov 27 2022
\ For ITC Forth
HEX
CODE GOTO   C259 ,  ( *IP IP MOV,)  NEXT, ENDCODE

: CELL-   2- ;
: PREVXT ( -- XT)  HERE CELL- @ ; \ fetch the XT of previous compiled word

: -;  ( -- ) \ programmer controlled
       PREVXT >BODY          \ get previous XT, compute data field
       -2 ALLOT              \ erase the previous XT
       POSTPONE GOTO  ,      \ compile the address for GOTO
       POSTPONE [            \ turn off compiler
       REVEAL
       ?CSP
; IMMEDIATE
\ -; does not end with EXIT because it is branching directly to another
\ list of tokens. That other list will end in EXIT or NEXT.

 

 

I tried it out on a 1,000,000 nest/unnest benchmark that I found here:  The ultimate Forth Benchmark (theultimatebenchmark.org)

(Section 13.7) 

 

Normal time is                : 2:30.7 

With tail-call optimization: 1:55.5 1:54.06

 

In another test I did 1 call per definition on 20 definitions.

Normal semi-colon was 1533 uS.

Optimized is 873  852uS.

 

The TAIL* definitions compile to continuous calls to NEXT and the return stack doesn't move! :)

 

 

Spoiler
\ TAIL CALL OPTIMIZATION TEST

NEEDS -;     FROM DSK1.TAILCALL

: ACTION   ;

: NEST1   ACTION ;
: NEST2   NEST1 ;
: NEST3   NEST2 ;
: NEST4   NEST3 ;
: NEST5   NEST4 ;
: NEST6   NEST5 ;
: NEST7   NEST6 ;
: NEST8   NEST7 ;
: NEST9   NEST8 ;
: NEST10  NEST9 ;
: NEST11  NEST10 ;
: NEST12  NEST11 ;
: NEST13  NEST12 ;
: NEST14  NEST13 ;
: NEST15  NEST14 ;
: NEST16  NEST15 ;
: NEST17  NEST16 ;
: NEST18  NEST17 ;
: NEST19  NEST18 ;


: TAIL1   ACTION -;
: TAIL2   TAIL1 -;
: TAIL3   TAIL2 -;
: TAIL4   TAIL3 -;
: TAIL5   TAIL4 -;
: TAIL6   TAIL5 -;
: TAIL7   TAIL6 -;
: TAIL8   TAIL7 -;
: TAIL9   TAIL8 -;
: TAIL10  TAIL9 -;
: TAIL11  TAIL10 -;
: TAIL12  TAIL11 -;
: TAIL13  TAIL12 -;
: TAIL14  TAIL13 -;
: TAIL15  TAIL14 -;
: TAIL16  TAIL15 -;
: TAIL17  TAIL16 -;
: TAIL18  TAIL17 -;
: TAIL19  TAIL18 -;

DECIMAL
: .uS     213 10 */ . ." uS" ;

: TEST1   TMR@  NEST19 TMR@ -  .uS ; \ 1533uS
: TEST2   TMR@  TAIL19 TMR@ -  .uS ; \ 852uS

 

 

 

  • Like 3
Link to comment
Share on other sites

This code is a more complete version that you can turn the optimizing on or off with a variable set to true/false, or just use the manual version as you see fit.

The smart semi-colon will only optimize CODE words or COLON definitions if they are the last word before the semi-colon.

 

I realize this is an academic thing. Not really needed. 

This was mostly my need to understand how you would do this in an ITC Forth system. :) 

 

It works for most code, but there are things that it breaks. 

That is why it needs TAILCALL ON / TAILCALL OFF, which is not very practical except for a new project. 

 

 

\ tail call optimizizing semicolon for Camel99 Forth  Nov 27 2022 Brian Fox

HEX
CODE GOTO   C259 ,  ( *IP IP MOV,)  NEXT, ENDCODE

: CELL-   2- ;
: PREVXT ( -- XT)  HERE CELL- @ ; \ fetch the XT of previous compiled word

: -;  ( -- ) \ programmer controlled
       PREVXT >BODY          \ get previous XT, compute data field
       -2 ALLOT              \ erase the previous XT
       POSTPONE GOTO  ,      \ compile the address for GOTO
       POSTPONE [            \ turn off compiler
       REVEAL
       ?CSP
; IMMEDIATE

: CODE?   ( xt -- ?) DUP @ CELL- = ;
: COLON?  ( xt -- ?) @ ['] DOCOL @ = ;

VARIABLE TAILCALL  \ control tail call optimizizing with this variable
                   \ TAILCALL ON  turns optimizer on

: TAILCALL? ( xt --?) DUP CODE? SWAP COLON? OR  TAILCALL @ AND ;

: ;   ( -- )
      PREVXT TAILCALL?
      IF   POSTPONE -;
      ELSE POSTPONE ;
      THEN ; IMMEDIATE

\ -; does not end with EXIT because it is branching directly to another
\ list of tokens. That other list will end in EXIT or NEXT.

 

  • Like 1
  • Thanks 1
Link to comment
Share on other sites

For your reading pleasure. Found on comp.lang.forth 

 

"Forth's most important feature has little to do with the fact that it is a stack language,

it has instead to do with the way it interacts as a whole with the user. Forths extensibility,

structure, modularity and very simple syntax are key attributes that give the programmer

freedom to structure solutions for problems in ways that programmers of other languages

cannot understand or attempt."

 

An Interview with Tom Zimmer (wordpress.com)

  • Like 3
Link to comment
Share on other sites

If you have ever wondered why GPL is slower than Forth on TI-99, this short lecture by Dr. Brad Rodriguez might explain why.

 

Brad is the author of Camel Forth. In the lecture he explains his work on making a version that uses byte-codes ("token-threading) on the MSP430.

A byte-code Forth operates in a similar way to GPL in that Forth "instructions" are abstracted to single bytes. 

 

Spoiler alert: The conventional "address threading" method (like Forth in this neighbourhood) is about 2x faster than byte-codes on MSP430.

I would expect a similar result for TMS9900. 

 

  • Like 2
Link to comment
Share on other sites

  • 1 month later...

I have continued trying to debug my file to compile Forth to SAMS using more CODE words with limited success.

It's very appealing because I got the call overhead down to under 0.3%, the and dictionary headers are only 4 cells, with the rest of the definition going into SAMS.  

That is 5X faster than the Forth versions which have about 1.6% call overhead dictionary entries that are 8 CELLS total size 

 

At one point I went back to Mark's orginal code and implemented my ideas in Forth.

 

In the file below I have back-migrated what I did so that it runs on Turbo Forth.

I can't remember if I posted something like this before, but I think this version is cleaner and uses 672 bytes of dictionary. 

If you need a lot SAMS pages for Forth code this version saves valuable dictionary space because it doesn't need the array of dictionary pointers.

The dictionary pointers are maintained in each SAMS page in the last memory location.

 

The changes are:

  1. Replace the array of dictionary pointers with pointer at the end of the each SAMS page
  2. Write a magic number in each SAMS page to indicate page is ready to use (not used but it's there) 
  3. BANKS now performs the initialization of each SAMS memory page
Spoiler
\ COMPILE TO SAMS MEMORY for TurboForth:  
\ http://turboforth.net/resources/sams.html

\ BFox changes:
\ - Replace array _HERES with pointer at the end of the each SAMS page
\ - Write a magic number in each SAMS page to indicate page is ready to use 
\ - BANKS now performs the initialization of each page

create _bnkstk 20 cells allot  \ bank stack

$F9F9 _bnkstk ! \ force first entry on bank stack to $F9

\ SAMS CARD management
HEX        3000 CONSTANT CSEG    \ MASTER REFERENCE CODE SEG WINDOW 

 \ SAMS memory addresses for management variables 
    CSEG 0FFE + CONSTANT SAMSDP   \ variable at end of SAMS page
    SAMSDP 2-   CONSTANT SAMSID   \ ID field that this is a valid page
          ABBA  CONSTANT MAGIC# 


_bnkstk value _bsp             \ pointer into bank stack
-1 value _bank                 \ current bank
0 value _nhere                 \ "normal" here
0 value _maxBank

: CMAP  ( n -- ) CSEG >MAP ; \ "code map"

: >bank ( n --)  2 +to _bsp   dup _bsp ! CMAP ;
: bank> ( -- n) -2 +to _bsp   _bsp @     CMAP ;

 \ reserve space for here pointers for n banks
: BANKS ( n -- )  
  DUP TO _MAXBANK
  DUP 1+ 0 
  DO   
    I CMAP 
    CSEG SAMSDP ! 
    MAGIC# SAMSID ! 
  LOOP 
  CR 4 * U. ." K SAMS code" CR ;

: b: ( n -- )
  \ begin compiling a banked definition in bank n
  _bank -1 <> if
    :
  \ runtime stuff   
    compile lit _bank ,     
    compile >bank
    compile branch  SAMSDP @ dup ,
\ compile time stuff     
    here to _nhere          \ save "normal here"
    h !                     \ set h to _bank's "here"
    _bank CMAP              \ map in the bank
  else : then ;


: _bfree ( -- ) \ print free memory in the bank...
  $4000  SAMSDP @ -  .   ." bytes free." cr ;
  
  
: ;b ( -- ) \ end banked compilation 
  compile branch  _nhere ,
  here  SAMSDP ! \ update here for bank
  _bfree
  _nhere h !                    \ restore h to "normal" memory
  compile bank>   [compile] ; ;
   
: :  ( -- )  _bank -1 = if : else b: then ;

-1 TO _BANK 
: ;  ( -- )  _bank -1 = if [compile] ; else ;b then ; immediate 

: setBank ( bank -- )
  to _bank
  _BANK -1 _maxBank within 0= abort" Illegal bank number"
  _BANK -1 = if cr ." Compiling to 32K memory." cr EXIT then 
  cr ." Bank " _bank . ." active. "  _bfree ;


HERE SWAP -   DECIMAL .  .( bytes)

 

 

Test code 

Spoiler
DECIMAL 
32 BANKS

HERE 
16 SETBANK
: TEST   CR ." This has got to work!" ;

17 SETBANK
: HELLO   CR ." Hello from SAMS"  ;

18 SETBANK
: NESTED1  ." nesting 1" ;

19 SETBANK
: NESTED2  NESTED1  ."  2 "  ;

20 SETBANK
: NESTED3  CR NESTED2  ."  3 "  CR TEST   ;

16 SETBANK ( Use 240 again for a circular nest)
: GO   NESTED3 HELLO  ;

HERE SWAP - . .( bytes)

GO 

 

 

  • Like 4
Link to comment
Share on other sites

  • 2 weeks later...

@oddemann demonstrated a BASIC program he had generated by ChatGPT.

 

This post is for people who might want to try Forth but aren't sure what it's like.

 

I am always curious how Forth compares to BASIC for various programming tasks.

The Forth version of this program takes advantage of the word #INPUT which in a library for Camel99 Forth.

#INPUT gives Forth an easy to use INPUT statement for numbers, that behaves like TI BASIC INPUT but for numbers only. 

(It would not be hard to make a version of #INPUT for any Forth system. I would do it for anyone who wanted it)

 

TI BASIC Version

1 rem written by ChatGPT
2 rem minor changes for TI-BASIC
10 RANDOMIZE
20 N=INT(RND*10)+1
30 PRINT "I'm thinking of a number between 1 and 10."
40 INPUT "What is your guess? ": GUESS
50 IF GUESS=N THEN 90
60 PRINT "Sorry, that's not the number I was thinking of."
70 PRINT "Try again!"
80 GOTO 40
90 PRINT "Congratulations! You guessed the number!"
100 END


Things to Notice about Forth vs BASIC

Forth systems use files of source code (text) to add functionality to the language. See the INCLUDE statements.

Different Forth systems will stuff more or less into the base system depending on the implementer's taste.

Camel99 is a minimal system so typically needs more "INCLUDE" statements. 

 

Forth has no GOTO statement. It uses structured looping (BEGIN    WHILE   REPEAT and others)

That can be adjustment when you are used to BASIC.

 

Forth only understands what you have already told it so variables must be declared before you can use them.

Newlines only happen if you want them. CR means "carriage return" from the days of the teletype. 

I have heard that ChatGPT writes crappy Forth code. I guess I should ask it myself.

 

Here is my Forth equivalent program.

INCLUDE DSK1.RANDOM
INCLUDE DSK1.INPUT 

VARIABLE N
VARIABLE GUESS

: RUN
   RANDOMIZE
   10 RND 1+ N !
   CR ." I'm thinking of a number between"
   CR ." 1 and 10."
   BEGIN
     CR ." What is your guess? " GUESS #INPUT
     GUESS @ N @ <>
   WHILE
     CR ." Sorry, that's not the number I was thinking of."
     CR ." Try again!"
   REPEAT
   CR ." Congratulations! You guessed the number!"
   CR ." ** DONE ** "
;

image.png.8f9351094cca898d0d41d42054786dde.png

  • Like 2
  • Thanks 1
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...