FIG-FORTH internals

by Jim Brooks www.jimbrooks.org

[1995/03 began] [2021/09 edited]
My notes from studying and modifying 8086 assembly code of FIG-FORTH. Describes how FIG-FORTH interpreter executes internally, how interpreting and compiling are virtually the same operation, ingenious solutions used to assemble FORTH interpreter. Also describes modifying FIG-FORTH to have direct-threaded code (DTC).

index

FIG-FORTH assembly source code

FIG-FORTH is written in assembly language. Core FIG-FORTH colon words are actually written in assembly code. This is one of the clever ways FORTH interpreter was created, a brilliant solution to paradox of creation, programming in FORTH is done even before FORTH interpreter has been assembled! This assembly code translates to FORTH as : ? @ . ;. This means to some extent FIG-FORTH assembly code is actually portable!

; ?             emit contents at addr                   \addr\--

                $COLON  81H,,?,QUES
                FW      AT,     DOT,    SEMIS

starting FORTH

When FORTH starts, it begins executing machine-code of physical CPU. FORTH registers IP SP RP of FORTH virtual processor are initialized. System words COLD WARM ABORT are executed which completes initialization. ABORT executes QUIT which is top-level of FORTH.

top-level of FORTH

QUIT, ironically, is executed once FORTH virtual processor is ready. QUIT is the top-level word and main loop of FORTH interpreter. QUIT is responsible for clearing return stack. QUIT accepts input from input stream (keyboard/block), calls INTERPRET to parse input stream, emits OK (if no error), then loops back.

interpreters

FORTH has an "inner interpreter" and "outer interpreter". Inner interpreter is the core of FORTH, it executes all kinds of defined FORTH words. Outer interpreter is both interpreter and compiler, it parses input stream, executes defined words (if interpreting), or adds new words to dictionary (if compiling). Significant words of outer interpreter are: QUIT INTERPRET -FIND WORD ENCLOSE NUMBER.

outer interpreter

During execution of COLD which starts a FIG-FORTH system, QUIT creates command prompt. QUIT contains words QUERY INTERPRET. QUERY accepts commands, INTERPRET interprets or compiles them. QUIT emits OK message after INTERPRET returns.

FORTH outer interpreter itself is a colon definition: INTERPRET. INTERPRET parses next word from input stream. If interpreter is compiling (between : ;), next parsed word is compiled into word currently being defined. Otherwise, interpreter is interpreting, so it tries to execute parsed word. But if parsed word does not exist in dictionary, interpreter will try to convert it into a number and push it onto data stack. If parsed word is not a number, then interpreter shows error message. Finally, interpreter checks that data stack is within bounds with ?STACK then interpreter loops back.

Whether interpreter is compiling or interpreting is controlled by STATE variable. COLON : actually does little work as virtually all compiling is done by interpreter in compiling state. COLON merely calls CREATE which removes from input stream name of word to be defined (which interpreter would incorrectly process). Next it switches interpreter into compiling state, IOW, instead of executing CFA of a fetched word, interpreter appends CFA into dictionary. Then when ; (semicolon) is encountered, interpreter returns to interpreting state.

outer interpreter steps

QUIT executes:

    Input source is set to keyboard.
    Enter interpret-mode.
    Emit "OK".
    Clear R-stack
    Accept keyboard input until Enter is pressed or buffer is filled.
    Interpret keyboard input by executing INTERPRET.
        If in interpret-mode then branch to step Emit OK.
        If in compile-mode then branch to step Clear R-stack.

INTERPRET executes:

    Error if S-stack (data stack) is out-of-bounds.
    Parse next word in input stream.
    Search for word in dictionary.
        If found:
            If compiling:
                 Execute word if it is marked IMMEDIATE,
                 else add word to dictionary.
            If interpreting:
                  Execute word if not NULL
                  If word was NULL, then INTERPRET returns to QUIT.
            If not found:
                  Try to convert word into a double-cell number.
                      Convert to single-cell number if word is numeric but does not contain ".".
                  If word is not numeric then error.

inner interpreter

FORTH instruction pointer (IP)

FORTH IP is actually a pointer-to-pointer. FORTH IP points to a pointer, stored in memory, to a FORTH word. Reason is a colon definition contains an array of pointers to FORTH words. FORTH IP points to an element in this array. During execution, FORTH IP will incrementally point to each pointer.

; FW assembles pointer to FORTH word.
                FW      AT          ; @
                FW      DOT         ; .
                FW      SEMIS       ; ;S

In FIG-FORTH, FORTH IP (indirectly) points to next/following FORTH instruction, not the one currently executing (read NEXT routine). 8086 FIG-FORTH stores FORTH IP in 8086 SI register.

direct-threaded code (DTC)

Direct-Threaded Code (DTC) is a technique to boost speed of FORTH. Early FORTH systems and FIG-FORTH had Indirect-Threaded Code (ITC) in which Code Field Addresses (CFA) contained a pointer to machine-code. DTC eliminates this indirection by directly placing machine-code at CFAs. Modifying 8086 FIG-FORTH to have DTC reduced NEXT to two 8086 LODS / JMP @AX instructions.

DTC greatly improved performance, but DTC lost some flexibility of ITC. ITC allows any defined word to be revectored to a new definition. A new definition can override an old one, or can become an extension that calls older definition. Revectoring an old definition affects all words which include it in their definitions. In DTC, limited revectoring can be done by defining words using DEFER or by executing CFA stored in a variable.

NEXT

Machine-code routine named NEXT is the core of inner interpreter that executes next FORTH word.

NEXT routine:

1. Fetch CFA stored in cell pointed to by FORTH IP.
2. Increment FORTH IP to next/following FORTH instruction (cell).
3. Jump to fetched CFA.

For FORTH threaded-code to be fast, NEXT must be extremely optimized. In 8086 DTC version, NEXT is two 8086 instructions total, fetch/increment steps were combined in one 8086 LODS instruction.

; 80x86
@NEXT MACRO
          @LODS                   ;@AX = @SI, @SI += CellSize
          JMP     @AX             ;@AX = current instruction, @SI/@IP = next instruction
ENDM

6502 FIG-FORTH seems to also advance FORTH IP to next/following FORTH instruction before jumping.

; 6502
NEXT      LDY #1
          LDA (IP),Y     ; Fetch code field address pointed
          STA W+1        ; to by IP.
          DEY
          LDA (IP),Y
          STA W
          JSR TRACE      ; Remove this when all is well
          CLC            ; Increment IP by two.
          LDA IP
          ADC #2
          STA IP
          BCC L54
          INC IP+1
L54       JMP W-1        ; Jump to an indirect jump (W) which vectors to code

execution of machine-code words

Machine-code words are directly executed by physical CPU. Inner interpreter's NEXT routine, words EXECUTE BRANCH EXIT switch execution to machine-code words. Machine-code words execute directly within the lowest-level, their execution does not nest using return-stack as colon definitions do. Machine-code words exit at NEXT routine.

execution of threaded-code words

Threaded-code words contain virtual instructions for virtual FORTH processor. Threaded-code words include colon words and a few special words in assembly code which are assembled partly of machine-code and partly of FORTH words (examples are COLD BYE assembled with $ASM $FORTH macros). A threaded-code word is started from machine-code by calling a machine-code procedure or with $FORTH assembly macro. Often, procedure is specific to type of FORTH word, such as DOCOL DOVAR DOCON. In DTC, CFA of threaded-code words contain a machine-code CALL instruction that calls these procedures. Return address points to PFA (for colon words, PFA points to start of array of pointers to FORTH words). Machine-code procedure never returns after CALL instruction. Instead, return address from CALL is used as input parameter to obtain PFA. Procedure executes machine-code for word then exits by NEXT.

execution of colon words

Execution of colon words causes nesting. A colon word often calls other colon words, those can call more, nesting to more inner levels, until a machine-code word is reached. Machine-code words, which don't nest, do actual execution.

Execution of colon words enters at DOCOL and leaves at SEMIS (;S). Nesting is done when DOCOL pushes FORTH IP onto R-stack. Each word in colon definition will be executed until SEMIS is reached. SEMIS will pop IP from R-stack, causing unnesting, execution will resume at word in outer-level nest.

Although nesting/unnesting may seem a bottle-neck, by using DTC, routines were reduced to very few 8086 instructions.

@NEXT MACRO
          @LODS                   ;@AX = @SI, @SI += CellSize
          JMP     @AX             ;@AX = current instruction, @SI/@IP = next instruction
ENDM

DOCOL:    SUB     @RP, @N         ;push @IP onto R-stack
          MOV     [@RP], @IP
          POP     @IP             ;@IP = return addr from CALL DOCOL
          @NEXT

SEMIS:    MOV     @IP, [@RP]      ;pop @IP from R-stack
          ADD     @RP, @N                 
          @NEXT

execution of variables and constants

Executing a variable or constant sounds strange, but FORTH interpreter executes everything.

Variables are executed in such a simple way that they seem NOPs. Machine-code procedure DOVAR just jumps to NEXT yet PFA has been pushed to stack.

Similar to variables, constants use return address from CALL DOCON to fetch value of constant stored in memory.

execution of creations of <BUILDS DOES>

Words which follow DOES> expect an address pushed onto stack. Machine-code procedure DODOE pushes this address. During compilation of a creation of <BUILDS DOES>, <BUILDS first executes 0 CONSTANT. Later, DOES> overwrites zero with address to first word compiled after DOES>. This means PFA of creation holds address which will be stored in FORTH IP which will execute words after DOES>.

DODOE first pushes FORTH IP to R-stack, as done with colon definitions. DODOE then loads IP with CFA contained in PFA, and pushes address after PFA, IOW, the cell after PFA. This address points to start of data compiled by any compiling words specified after <BUILDS. DODOE then executes NEXT to execute CFA contained in PFA.

FORTH word format

                        +---+---+---+---+---+---+---+---+
                        | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
                        +---+---+---+---+---+---+---+---+
            +-----------+---+---+---+-------------------+
            |    NFA    | D | I | S |     Name Width    |
            +-----------+---+---+---+-------------------+
                        |       characters of name      |
            +-----------+-------------------------------+
            |    LFA    |  ptr to NFA of previous word  |
            +-----------+-------------------------------+
            |    CFA    |    machine-code or CALL DO*   |
            +-----------+-------------------------------+
            |    PFA    |                               |
            +-----------+-------------------------------+

                D*= Delimiter bit       (1=signifies start of NFA)
                S = SMUDGE bit          (1=FINDable)
                I = IMMEDIATE bit       (1=IMMEDIATE)

NFA : Name Field Address
      Contains name of FORTH word.

LFA : Link Field Address
      Links FORTH words, contains pointer to NFA of previous FORTH word.

CFA : Code Field Address
      If primitive FORTH word, contains machine-code instructions.
      If higher-level FORTH word (colon, VARIABLE, CONSTANT, DOES>, DEFER),
      contains CALL machine-code instruction to DOCOL/DOVAR/DOCON/DODOE/DODEF machine-code procedure.

PFA : Parameter Field Address
      If VARIABLE or CONSTANT word, this is where variable/constant is stored.
      If colon word, contains array of pointers to FORTH words.

IMMEDIATE words

IMMEDIATE words are always executed, regardless if compiling or interpreting. INTERPRET issues -FIND, which returns NFA length/word-type byte of found word. STATE is then subtracted from this character. STATE will be 0 when executing, else C0 (hex) when interpreting. Smallest value for NFA length/word-type will be C1 (hex) for IMMEDIATE one-letter words. Only if STATE is smaller, will word get compiled, thus if marked IMMEDIATE it will always EXECUTE.

numeric conversion

pictured numeric output

pictured numeric output

(NUMBER)

(NUMBER) processes pure numerical text. (NUMBER) will convert an ASCII numerical character (0,1,..9,[A,B,..]) in current number BASE into a double-cell number. Double-cell number is added to a double-cell accumulator. Every iteration accumulator is multiplied by BASE. Conversion process starts with most significant digit to least.

(NUMBER) will begin incrementing DPL (Decimal Point Locator) whenever DPL is non-zero. This is part of interaction between (NUMBER) and NUMBER. NUMBER will reset DPL to 0 after (NUMBER) finds a period. Result is DPL will be set to count of characters after last period.

(NUMBER) stops whenever a non-numerical character is encountered (DIGIT will return 0). Typically, either space, null, or a period will be encountered. (NUMBER) sets DPL when a period is encountered.

NUMBER

NUMBER expects input address to point to numerical text delimited by either a space or a null. DPL is set equal to count of chars after last decimal point (read (NUMBER) above). If there was no decimal point, NUMBER will set DPL to -1 which signifies single-cell number.

Examples:

123.45          DPL = 2
1.2345          DPL = 4
123.45.67       DPL = 2
12.456.7890     DPL = 4
12345.          DPL = 0 (there are no chars after decimal point)
(Quirk: NUMBER will convert blank to double-cell 0 !)

ENCLOSE

ENCLOSE encloses a word in a stream of text. ENCLOSE is text-processing engine of FORTH's interpreter/compiler. ENCLOSE is primitive of WORD. An address and delimiter is input to ENCLOSE, typically IN and 32 (ASCII space).

ENCLOSE begins by scanning thru text starting at input address for first non-delimiter character. This marks start of word to be enclosed. Next, ENCLOSE scans to trailing delimiter, which conversely marks end of word.

ENCLOSE is designed as an iteration primitive, since it automatically returns next address after enclosed word. Contents of IN holds address, either into TIB (Terminal Input Buffer) or memory of LOAD file (LOAD isn't in standard FIG-FORTH).

ENCLOSE does have an inherent quirk. This quirk causes " " to fail (dquote, space, dquote). Quirk is that when word " (dqoute) is interpreted and then executed, ENCLOSE will cause IN to be moved to second " (dquote). But, ENCLOSE will incorrectly first scan to first non-delimiter, which causes ENCLOSE to go beyond second ". This quirk could exist in other FORTH versions.

vocabularies

CURRENT, CONTEXT

Optionally, FORTH words can be combined into separate vocabularies, to segregate words when searching or when defining. Vocabularies are defined using FORTH word VOCABULARY which is a construction of <BUILDS DOES>. Vocabulary words are linked only with other vocabulary words. LFA of lastest vocabulary holds NFA of previous vocabulary, and so on, until FORTH vocabulary, which has a null in its LFA to mark end of vocabulary linked-list. Non-vocabulary words are not linked with vocabulary words -- vocabularies have their own search order. This how vocabularies are able to segregate words.

Default order of searching/defining is of FORTH vocabulary. Note word FORTH is a vocabulary word. When a new vocabulary is defined using VOCABULARY, order of searching/defining is not immediately changed. But when new vocabulary word is executed, it causes further searches of dictionary to begin in its vocabulary. If target of search was not found in new vocabulary, then another search is begun from FORTH vocabulary. Lastly, if search target was not found in FORTH vocabulary, then list of vocabulary words is searched, in case search target is a vocabulary word.

To define definitions into a vocabulary, word DEFINITIONS is used. DEFINITIONS makes defining vocabulary equal to search vocabulary. Typically, a vocabulary word is used in conjunction with DEFINITIONS such as FORTH DEFINITIONS.

These variables relate to vocabularies:

CONTEXT:

CONTEXT addresses a cell which holds NFA from where dictionary search begins. CONTEXT vocabulary is first vocabulary to be searched. Specifically, CONTEXT points into a vocabulary header, vocabulary header holds NFA of vocabulary's LATEST definition.

CURRENT:

CURRENT addresses a cell which is updated to hold NFA a new word, addressed in a manner similar to CONTEXT. CURRENT vocabulary is vocabulary in which new words are added. CREATE is responsible for updating CURRENT.

VOC-LINK:

VOC-LINK holds NFA of latest vocabulary. It is used to set LFA of a new vocabulary word, updated whenever a new vocabulary is defined.

CONTEXT and CURRENT can address same vocabulary header, and usually, and by default, indeed do. CONTEXT supports having up to two search orders, with vocabulary referenced by CONTEXT given precedence over default FORTH vocabulary. If CONTEXT references FORTH vocabulary, in effect there is only default search order. CURRENT supports selectively adding to any vocabulary, even retroactively. If CURRENT vocabulary happens to be NEW-VOCAB, FORTH vocabulary can specified as defining vocabulary via: FORTH DEFINITIONS. New words will be added to FORTH vocabulary, in so doing they do not become a part of NEW-VOCAB.

Vocabularies should be named uniquely, if not older vocabulary words in effect will be lost.