Local Variables in the FORTH language

An article I wrote in 1989 argued for support of local variables in the FORTH programming language.  I called my approach “Forth Prefix Frame Operators“.

This method was developed on a 68000-based, 32-bit, call-threading Forth system. Except for internal structure, memory addressing, and system dependencies, this system adheres to the Forth-83 Standard. It has a few differences that are straightforward: @ is a 32bit fetch, W@ is a 16-bit fetch, and C@ is an eight-bit fetch. The comma and store words are similar.

Implementation

Example use, bubble sort.

: SORT ( cfa.array cfa.compare cfa.exchange start end )
    L( ARRAY COMPARE EXCHANGE START END \ SWITCH N1 N2 )
    
    BEGIN  FALSE IS SWITCH L END L START
      DO  I GO ARRAY @ IS N1 I 1+ GO ARRAY IS N2
        L N1 L N2 GO COMPARE
        IF TRUE IS SWITCH
            I I 1+ L N1 L N2 L ARRAY GO EXCHANGE
        THEN
      LOOP L SWITCH FALSE =
    UNTIL S(  ) 
;

( Use:  ' DATA ' > ' EXCHANGE 1 6 SORT will do an ascending sort )

UPDATES:
*** I just learned (2/18/2010 at 05:58 gmt-5) that people have been using local variables in Forth for the last fifteen years. Wow. So I was right. I tried to look up some of the practices but could not find much using Google. Just:

*** From GreenArrays site, polyFORTH Reference Manual is online.

*** 9/12/2015: The evolving Forth 2012 standard (available here) includes Local variable support. Section 13 The optional Locals word set. Of course, it is not similar to the Forth Prefix Frame Operators approach discussed here.

By the way, the creator of the Forth language, C. H. Moore, was not a fan of local variables:

There is a lot of discussion about local variables. That is another aspect of your application where you can save 100% of the code. I remain adamant that local variables are not only useless, they are harmful. — 1xForth

Further Reading


A stack frame is space allocated in a stack for storage of local variables and parameters. Using a stack frame allows reentrant subroutines or procedures. Frames are so useful that some general purpose microprocessors have built-in structures to create them. For example, the 68000 has the LINK and UNLK instructions.

Surprisingly, the Forth Virtual Machine does not have a standard method of creating frames. Therefore, primitives must be written that do so. The method used here requires only one variable, which should be a host register for speed, the Return stack for re-entrancy, and the existing Parameter stack. Using the Forth stack saves time, whereas, in some local variable proposals, an initial relocation of items to another array or local stack does not. To identify labels, a few simple string operators are used. This makes it more portable to different Forth systems and saves dictionary space.

Listing 1 below is the source code for an example implementation. Also shown in the listing is 68000 assembler code for faster inline operation of the approach.
METHOD

A frame for use within a single definition is created with L(. It parses the input stream until the closing ) and creates a string array above HERE. This array is then pointed to by LPTR. The count of blank-delimited strings is the number of local variables needed. For example, the phrase: L( length width height )

will create a frame with three items labelled “length” “width” and “height”.
Two more capabilities were added to increase usefulness: lazy variables and stack extention.

Lazy Variables

Lazy variables are created when the character # is followd by a number in the string array. Lazy variables are one-character strings comprised of the letters M, N, P, and so on (to avoid confusion with the number 0, the letter O is not used). They are useful when one needs to quickly write a procedure and descriptive labels are not important, or when one IS lazy and prefers to use one-character labels.

In figure three, lazy variables are used in the word SUMMING. Four numbers on the stack are assigned to four local variables named M, N, P, and Q via the phrase ‘#4’. These are then used to compute a simple sum.

: SUMMING
    1 2 3 4 L( # 4 \ RESULT )
    L M L N L P L Q + + + IS RESULT     AT RESULT ?  S(  ) 
;         

Stack Extension

The other added capability can be used to extend the size of the frame. When local variables are allocated, they are based on the count of items in the string at LPTR @. This count cannot exceed the number of parameters which will be on the stack athe definition’s run-time, since a frame is made within the stack, not by extending the stack. But, if we need three local variables, for example, and there are only two items on the stack, there will be no room for the frame. One creates the neccessary room by preceding the names with a ‘\’ (backslash). This will cause the compiler ‘L(‘ to excute EXTSTK, which compiles in-line, stack-extension code.

In figure three, again, SUMMING uses the backslash option. The four Lazy variables are used to compute the sum, but another variable is needed to store it. This is done with the phrase: \ RESULT )

Frame Unlinking

The primitive ‘S(‘ is much simpler. It parses the input stream as above, but it compiles (SOME) or (NONE) depending on the number of parameters returned at run-time. These parameters can be named explicitly or with the character # followed by the count. The “# count” alternative is used when the stack contents are obvious. For example, if the last words in a phrase are L FLAG (leave contents of flag on the stack), one can write S( # 1) to avoid repeating the word ‘flag’ in the parameter string. Of course, in this example a more descriptive name could be used instead, such as: S( key_found? )

prefix operators

The prefix operators L, IS, and AT access frame items by parsing the in-line string in a definition and searching for a match in the string array at LPTR, then compiling the associated run-time prefix and offset. These prefixes are the minimum necessary to provide full use of prefix frame operators. However, to accommodate application needs as well as programming style, user-defined prefix operators can be created. To provide vectored execution, for example, a prefix called GO was defined. It is used in Figure One to help define a generic sort. The word expects code field addresses on the stack that specify what kind of data structure is being sorted: strings, numbers, complex, etc.

In addition to GO, a few more prefixes are shown, such as the “implicit” SUM. SUM replaces the phrase L one L two + with the phrase SUM one two.

These implicit prefixes make the source code more compact and readable, as illustrated in Figure Two.

: SOLVE   \ ( a b c -- [b-(b^2 - c)/2a [b+(b^2 - c]/2a true | false )
    ROT DUP 0 <>  \ denominator not zero?
    
    IF 2* l( b c 2a \ p ) L b DUP * L c - IS p
        SUB b p L 2a / SUM b p L 2a / TRUE
        S( difference sum true )
    ELSE  3 NDROP FALSE THEN 
    
;  \ ( 1 2 3  gives 1 1 -1 )

FRAME is the run-time frame creator; it saves the present contents of FPTR on the return stack and then uses the in-line number to add to the stack pointer, which will now point to the bottom of the frame. (SOME) and (NONE) are the run-time unframing words which unstack the FPTR and save or lose the items in the frame by resetting the stack pointer.

EXAMPLES

The structure compiled by prefix frame operators is seen by this simple definition:

 : SOLVE \ ( a b c -- [b-(b^2 - c)/2a [b+(b^2 - c]/2a true 
| false ) ROT DUP 0 <> \ denominator not zero?  
    
    IF 2* l( b c 2a \ p ) L b DUP * L c - IS p
        SUB b p L 2a / SUM b p L 2a / TRUE
        S( difference sum true )
    ELSE  3 NDROP FALSE THEN 
    
;  \ ( 1 2 3  gives 1 1 -1 )

This compiles as: EXTSTK 1 JSR (FRAME) 3 JSR (SUM) 0 1 JSR (IS) 3 JSR (L) 3 JSR (SOME) 1 RETURN

(Note: for simplicity, the actual compiled offsets and code are not shown.)

An unexpected benefit of prefix frame operators is the ability to use the frame as an array, as illustrated in Figure Five, where the word ?DISK.BYTES.FREE is defined. This word is used to determine the amount of free disk space.

the required data is provided by DISK.FREE which expects an address on the stack of a sixteen-byte buffer where it will store disk parameters in this order: FAU, TAU, SECTOR.SIZE, and SECTOR/ALU. ?DISK.BYTES.FREE creates this buffer as a frame and a name for each of these parameters. Note that the names in this list are in reverse order. This is because, in this Forth system, the parameter stack grows toward lower memory. As a consequence, so does the frame. Buffer names are, therefore, listd backward. Fetching the address of the variable FAU returns the beginning address of the buffer. This address is passed to DISK.FREE which stores the data; the rest of the definition uses that data to calculate the number of free bytes on the disk.

        
CODE DISK.FREE    ( 16byte.buffer.address ) \ call GEMDOS #36
    R -) 0 # MVOE .W R -) S )+ MOVE .L
    R -) $367 #MOVE .W 1 TRAP R AR 8 ADDQ .L NEXT
    
: ?DISK.BYTES.FREE   ( --- bytes )
    L( \ SECTOR/ALU SECTOR.SIZE TAU FAU ) AT FAU DISK.FREE
    L FAU L SECTOR/ALU * L SECTOR.SIZE * S( BYTES ) 
;

COMMENT: DISK.FREE expects the address of a buffer where it will put disk 
information in the order : fau tau sector.size sector/alu.  
?DISK.BYTES.FREE gives it the address of a frame created for that purpose, 
and then uses the data to compute bytes free.  COMMENT; 
        
: $=   ( $1 $2 --- flag )  L ( S1 S2 \ FLAG LEN )
    L S1 C@ 1+  IS LEN   
    TRUE IS FLAG  
    SUM LEN S1 L S1
    DO L S2 C@ I C@ <>  
       IF  FALSE IS FLAG LEAVE THEN ++ S2 
    LOOP
    L FLAG  S( # 1 )   \ true == equal
;        

Implementation

 
 Simple string words 

: $=  ( $1 $2 --- flag )   compare strings, same= true flag
    -1 ROT DUP C@ 1+  OVER + SWAP 
    DO  COUNT I C@ &lt;&gt;  IF SWAP DROP 0 SWAP LEAVE THEN
    LOOP DROP ;
    
: GETNAMES  name1 .... nameN )  ( adr --- count ) count is #items
     get instream labels and form string array at adr
     form:  [ 1len | $... |1len .......|1len| $...| 0 | ]
    0 SWAP BEGIN 32 WORD DUP 1+  C@ ASCII ) &lt;&gt;
            WHILE ROT 1+ -ROT 2DUP C@ 1+ &gt;R R@ CMOVE R&gt; +
           REPEAT  DROP   0 SWAP C!  ;
           

: $SRCH    ( $adr $array --- offset flag )   true = found
    0 0 2SWAP  ( count flag $adr bufadr )
    BEGIN  DUP C@ 0= 3 PICK OR NOT  not end or not true flag
        WHILE  2DUP $= IF  ROT DROP -1 -ROT  change flag to true
               ELSE &gt;R ROT 1+ -ROT R&gt; COUNT  + THEN
    REPEAT  2DROP   ;               


VARIABLE LPTR    name buffer pointer for temporary string array

: SRCH.CHAR  ( adr char --- adr )  search for char starting at adr
    BEGIN SWAP COUNT  SWAP -ROT OVER = UNTIL DROP 1- ;

: REMOVE  remove &quot;&quot; from name list at $array
     LPTR @ DUP ASCII  SRCH.CHAR  SWAP 0 SRCH.CHAR ( a a0 )
     SWAP DUP &gt;R 1+ SWAP R@ - R&gt; 1- SWAP CMOVE ;
     
 Lazy Variables

: &gt;SHOVE  ( $buffer n )   make room for lazy names in $array
    SWAP &gt;R 2* R@ + R&gt;   4+ SWAP OVER   ( 4+a 2n+a 4+a )
    LPTR @ 0 SRCH.CHAR SWAP - 1+ CMOVE&gt;
;    
    

: SKIP.O   ( c --- c' )  if c is 0 convert to P using hybrid logic
    DUP ASCII 0 = 1 AND +
;    

: RESERVE  ( $buffer n )   create lazy variables M, N, P, ... etc.
    2DUP &gt;SHOVE 2*  2DUP 1 FILL
    ASCII M -ROT  SWAP  1+ SWAP
    OVER + SWAP
    DO SKIP.O  DUP I C!   1+  2 +LOOP  DROP 
;    


: ?LAZY   ( #parsed --- new.number )  make lazy vars if neccessary
    LPTR @ W@  291 =    first name is '#'?
    IF 0 LPTR @ 2+ CONVERT 2DROP  ( n # )
        LPTR @ OVER RESERVE   + 2-
    THEN
;    


 Stack extension for uninitialized local variables

CREATE SLASH  1 C, ASCII  C,    the letter &quot;&quot; as a string

: EXTSTK  ( n )  compile inline stack extension code
    [ ASSEMBLER ] S SWAP  # SUBA  W [ 0 138 U+ ! ]
;    

: ?TEMPS   ( #parsed -- new# )   stack extension if needed
    SLASH LPTR@  $SRCH IF OVER SWAP - 4* EXTSTK REMOVE
                       ELSE  DROP  THEN 
;                       

 Framing
VARIABLE FPTR     frame pointer.  Should be register for speed.

: (FRAME)    run-time formation of frame WITHIN the stack!
     old fptr is put under return address on return stack
    'S R&gt; DUP W@ SWAP 2+    's n return )
    FTPR @ &gt;R  &gt;R  + FPTR !    ( ) (R  oldfptr return )
;                              fptr=sp+4n

: L(    name..)|name...  temp..)|# n)|# n  temp..)
    ?COMP HERE 1024 + DUP LPTR ! GETNAMES DUP
    0=  ABORT&quot; Empty parameter list!&quot;  ?LAZY  ?TEMP
    1-  0 MAX  4*  COMPILE (FRAME)  W, 
;  IMMEDIATE
    
 Unframing

CODE SP!   ( adr )   S AR S )+ MOVE .L NEXT     load stack pointer

: (NONE)     run-time stack reset leaving no parameters
    R&gt; R&gt; FPTR @ SWAP FPTR ! SWAP &gt;R 4+ SP! 
;    

: (SOME)     run-time stack reset leaving parameters
    'S R&gt; DUP W@  SWAP 2+  R&gt; SWAP &gt;R  FPTR @ SWAP FPTR !
    SWAP DUP &gt;R - 4+ SWAP OVER R&gt; CMOVE&gt; SP!
;    

: S(     name...)|# n names...)|# n )   compile frame release
    ?COMP   LPTR @ GETNAMES DUP
    IF  LPTR @ W@ 291 =  291 is string '#'
        IF  DROP 0 LPTR @ 2+   CONVERT 2DROP
        THEN   COMPILE (SOME)   4* W,
    ELSE   DROP  COMPILE (NONE)   THEN 
;  IMMEDIATE    

 Prefixing
: ?LOCAL     name  (   )  compile name's frame offset
    32 WORD   LPTR @ $SRCH 0=  IF HERE COUNT  TYPE
    ABORT&quot;  is local?&quot;  THEN  4* W, 
;    

: 'N     ( --adr )  get adr of stack cell using inline number
    FTPR @  R&gt; R&gt; DUP W@ SWAP 2+ &gt;R SWAP &gt;R - 
;    


 Prefixes

 Run-time code                             ( terminology)
: (L)    ( -- parameter )  'N @ ;  fetch   ( rvalue )

: (IS)   ( n --- )         'N ! ;  store   ( = )

: (AT)   ( --- adr )       'N   ;  address ( lvalue )

 Compile-time code
: L      name  ( -- n ) call to lvar fetch
    ?COMP  COMPILE (L)  ?LOCAL ; IMMEDIATE

: IS     name  ( n --  ) call to lvar store
    ?COMP  COMPILE (IS)  ?LOCAL ; IMMEDIATE

: AT     name  ( -- adr ) get pointer
    ?COMP  COMPILE (AT)  ?LOCAL ; IMMEDIATE


COMMENT:    The prefix defining words should be made into a 
    compact CREATE.... DOES&gt;  structure.   Was not done here since
    the Forth sys used does automatic inline code exapansion and I 
    could not tame it.
COMMENT;


 Extensions.  Byte and increment operators.

: (GO)  'N @ EXECUTE ;    vectored execution.

: (LC@)  'N @ C@ ;
: (LC!)  'N @ C! ;
: (++)   'N 1+!  ;
: (--)   'N 1-!  ;

: GO       vectored execution of CFA in local variable.
           Compile:  name ( --- )
    ?COMP   COMPILE  (GO)  ?LOCAL ; IMMEDIATE          


: LC@  ?COMP COMPILE (LC@)   ?LOCAL ; IMMEDIATE
: LC!  ?COMP COMPILE (LC!)   ?LOCAL ; IMMEDIATE
: ++   ?COMP COMPILE (++)    ?LOCAL ; IMMEDIATE
: --   ?COMP COMPILE (--)    ?LOCAL ; IMMEDIATE

 Implicit extensions.  Dual operators.
: 'NN   ( --- A1 A2 )  adr of next two parameters using inline numbers.
    FPTR @ R&gt; R&gt; DUP 4% &gt;R       ( f lret 2ndret ) (R ret )
    SWAP &gt;R DUP W@ SWAP 2+ W@    ( f n1 n2 ) (R ret lret
    &gt;R OVER R&gt; - &gt;R - R&gt;  ;      (a1 a2 ) (R ret lret )
    
: (SUM)    'NN @ SWAP @ + ;            implicit addition.
: (SUB)    'NN @ SWAP @ SWAP - ;       implicit subtraction.
: (MOVEC)  'NN SWAP @ C@ SWAP @ C! ;   implicit byte copy.  


: SUM       ( -- sum )  Compile: name1 name2
    ?COMP COMPILE (SUM)  ?LOCAL ?LOCAL  ; IMMEDIATE
    
: SUB       ( -- dif )  Compile: name1 name2
    ?COMP COMPILE (SUB)  ?LOCAL ?LOCAL  ; IMMEDIATE
    
: MOVEC     (  )        Compile: name1 name2
    ?COMP COMPILE (MOVEC)  ?LOCAL ?LOCAL  ; IMMEDIATE
    
 run-time words coded in 68000 machine language using Forth assembler.

: M.L   [ ASSEMBLER ] MOVE .L ;    abbreviation

CODE (FRAME)
    0 AR S AR M.L      1 AR R )+ M.L    R -) FPTR @#L M.L
    0 DR 1 )+ MOVE .W  R -) 1 AR M.L    0 0 DR ADDA .W
    FPTR @#L 0 AR M.L  
NEXT
    

CODE (NONE)
    0 DR FPTR @#L M.L   FPTR @#L 4 R i) M.L
    R ) R )+ M.L        0 DR 4 ADDQ .L
    S AR 0 DR M.L  
NEXT

CODE (SOME)
    0 DR S AR M.L        0 AR R )+ M.L       1 DR FTPR @#L M.L
    FPTR @#L R )+ M.L    2 DR 0 )+ MOVE .W   2 EXTL
    1 DR 2 DR SUB .L     1 DR 4 ADDQ .L      R -) 0 AR M.L
    S -) 0 DR M.L        S -) 1 DR M.L       S -) 2 DR M.L
    ' CMOVE&gt;  @#L JSR    S AR 1 DR M.L      
NEXT

CODE 'N
    0 DR FPTR @#L M.L   1 AR 4 R I)  M.L
    1 DR 1 )+ MOVE .W   1 EXTL    4 R I) 1 AR M.L
    0 DR 1 DR SUB .L    S -) 0 DR M.L 
NEXT

CODE 'NN
    0 DR FPTR @#L M.L    1 DR 0 DR M.L        0 AR 4 R I) M.L
    1 AR 0 )+ MOVE .W    2 AR 0 )+_ MOVE .W   4 R I) 0 AR M.L
    0 DR 1 AR SUB .L     1 DR 2 AR SUB .L     S -) 0 DR M.L
    S -) 1 DR M.L   
NEXT

One thought on “Local Variables in the FORTH language”

Leave a Reply

Your email address will not be published. Required fields are marked *