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).
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
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.
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.
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
.
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.
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.
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) 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.
Machine-code routine named NEXT
is the core of inner interpreter that executes next FORTH word.
NEXT
routine:
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
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.
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 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
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.
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.
+---+---+---+---+---+---+---+---+ | 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 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
.
(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
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
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.
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
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
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
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.