Threaded Code
Note:
There is extensive use of “Tooltips” text to support learning which do not seem to render on a Smartphone
Therefore this site is best viewed via a computer’s HD monitor
Threaded Code
“Threaded code is a programming technique where the code has a form that essentially consists entirely of calls to subroutines. It is often used in compilers, which may generate code in that form or be implemented in that form themselves. The code may be processed by an interpreter or it may simply be a sequence of machine code call instructions” Source: Wikipedia
“Threaded code, in its original meaning (Bell 1973), is one of the techniques for implementing virtual machine interpreters” Source: (Ertl n.d.)
A classic paper on “threaded code” was (Bell 1973) followed by Dewar’s paper on “indirect threading” (Dewar 1975). Charles Moore’s practical work implementing Forth as indirectly threaded code in 1970 predated both Bell’s and Dewar’s publications (Rather et al. 1996)
Moore’s genius lay in his invention of the indirect “code field address” (“CFA”) and the way it is used in Forth
Indirectly Threaded Code
“Indirect threading uses pointers to locations that in turn point to machine code. The indirect pointer may be followed by operands which are stored in the indirect “block” rather than storing them repeatedly in the thread. Thus, indirect code is often more compact than direct-threaded code […] Older FORTH systems typically produce indirect-threaded code” Source: Wikipedia (my emphasis)
figForth is implemented as indirectly threaded code, but there are a number of other code threading techniques employed in a number of more modern Forth implementations
Brad Rodriguez discusses this fully in a series of articles (Rodriguez 1993)
By modern Forth standards, figForth is rather old fashioned, so what has it got going for it?
The advantages in using old-fashioned figForth Image#1: (Husband 2011) based on (Ting 2013, p. i)
In the example below, I will use the Colon Compiler to define a new word (a “colon definition”) called SQUARE and analyse its internal form by using my SPELL decompiler tool
Using the Colon Compiler to create a simple definition & analysing the indirectly threaded code produced Image#2: (Husband 2011), using keyboard activity, his “SPELL” Forth Decompiler Tool & his eZ80 code based on the Intel 8080 figForth model (FIG 1979) (FIG 1979)
(1) - Define a "Test" word called SQUARE
“In mathematics, a square is the result of multiplying a number by itself” Source: Wikipedia
So how is this achieved in Forth?
The Parameter Stack is used to “send” and “receive” (pass) values between words and this is implicit
So we define a new word called “SQUARE” which expects value n1 on the stack, squares it (multiplies it by itself) and returns that new value back onto the stack as value n2 (“n x n”)
And we represent the behaviour of the new word SQUARE in “glossary format” like this:
n1 --- n2 SQUARE
Take the value n1 from the stack, multiply it with itself and return the result as n2
Formulating the definition of the new word SQUARE
Image#3 (below): Using Forth interactively from the keyboard (Husband 2021)
(The results are in the green box..)
Forth is an “interactive compiler” and in the image on the left, we see how it can be used from the keyboard to work out and test possible word definitions 1
As part of the default Outer Interpreter QUIT, I have added a word I called .S which always displays the stack contents… 2
(1)(1) - Put 10 onto the stack…
And looking at the results (highlighted in the image in the green box), .S is showing the value on the stack
(1)(2) - DUPlicate the top stack item…
And as expected 3 we can now see two identical items on the stack
(1)(3) - Multiply the top two stack items…
We use the word “*“ and we see the result of multiplying 10 by 10… Q.E.D.
(2) - Analyse the Compiled Code
Decompilation of the new test word SQUARE exposes its indirectly threaded code internal form…
(2)(1) - The NFA is the Name Field Address
The label NFA marks the start of the Name Field Address of SQUARE’s header
(2)(2) - The Name Field contents:
The NFA control byte & the ascii text in the header
(2)(3) - The LFA is the Link Field Address
The label LFA marks the Link Field Address used for threading the dictionary’s linked list
(2)(4) - The CFA is the Code Field Address
The label CFA marks the Code Field Address which always points towards executable code
In this case the assembler label DOCOL at (2)(6)
(2)(5) - The PFA is the Parameter Field Address
The label PFA marks the Parameter Field Address which is the start of a field of data which is interpreted by the code pointed to by the CFA…
The Parameter Field is one of the most fundamental and important Forth fields and comprises of a list of Code Field Addresses
(2)(6) - The Compiler that Defined this Word
This is a code field address and it points towards the executable machine code at assembler label DOCOL which is the run-time code compiled by the Colon Compiler
In the default figForth system there are different classes of compiler:
• The Colon Compiler & The Semi-Colon Compiler
• The Constant Compiler
• The Variable Compiler
• The User Variable Compiler
• The Text Compiler
• The “Roll Your Own” Compiler
(2)(7) - A list of compiled CFA addresses
In the case of a high-level colon definition, that data is a list of the Code Field Addresses of the other words in the high-level definition…
In the case of a primitive definition (code definition) the CFA points towards its own PFA (thereby complying with “rule” (2)(4)&(2)(5) above; that the PFA contains executable machine code
In the case of other kinds of definitions, such as constants, or variables, etc, the PFA will contain data that will be interpreted appropriately by the run-time code inserted by the compiler that created the definition….
This is discussed in later sections
(3) - The Three CFA's Compiled by the Colon Compiler
These compiled CFA’s can be seen at B,C & D respectively
(A) - : The Colon Compiler
The Colon Compiler compiles (“inserts”) its Colon Interpreter’s run-time code called “DOCOL” here as the CFA of SQUARE’s colon definition
The machine code at assembler label DOCOL is executed and uses the Return Stack to work its way through the Parameter Field Addresses of the definition until it encounters the Colon Interpreter’s terminator SEMIS (8)
(B) - DUP
(C) - * “Star”
(D) - ;S “Semis”
(4) - COLON's Compile-time Behaviour
(5) - COLON's Run-time Behaviour
(6) - Analyse DUP's Compiled Code
(7) - Analyse *'s Compiled Code
(8) - Analyse ;S's Compiled Code
Remember this !!
References:
Bell, J. R., 1973. Threaded Code. Available from: Http://figforth.org.uk/library/Threaded.Code.p370-bell.pdf.
Dewar, R. B. K., 1975. Indirect Threaded Code. Available from: Http://figforth.org.uk/library/Indirect.Threaded.Code.p330-dewar.pdf.
Ertl, A., n.d. Threaded Code. Available from: http://www.complang.tuwien.ac.at/forth/threaded-code.html.
FIG, 1979. Forth Model: fig-forth_8080_ver_11. Forth Interest Group [online]. Available from: Http://figforth.org.uk/library/fig-forth_8080_ver_11.pdf.
FIG, 1979. Forth Model: figForth Installation Manual. Forth Interest Group [online]. Available from: Http://figforth.org.uk/library/fig-FORTH_Manuals_May79.pdf.
Husband, D., 2011. M.Sc in IT (Software Engineering). Master’s thesis. University of Liverpool.
Husband, D., 2021. eZ80 figForth Development Software System.
Rather, E. D., Colburn, D. R. and Moore, C. H., 1996. The Evolution of Forth. ACM [online]. Available from: Http://figforth.org.uk/library/p625-rather_The.Evolution.of.Forth.pdf.
Rodriguez, B., 1993. Moving Forth. Available from: http://www.bradrodriguez.com/papers/moving1.htm.
Ting, C. H., 2013. Systems Guide to fig-Forth [online]. 3rd ed. San Mateo, CA 94402, USA: Offete Enterprises, Inc. Available from: http://figforth.org.uk/library/Systems.Guide.to.figForth.pdf.