Here is another "Why FORTH?" essay: http://www.jwdt.com/~paysan/why-forth.html
+ ACKNOWLEDGEMENTS ----------------------------------------------------------------------
+
+ This code draws heavily on the design of LINA FORTH (http://home.hccnet.nl/a.w.m.van.der.horst/lina.html)
+ by Albert van der Horst. Any similarities in the code are probably not accidental.
+
SETTING UP ----------------------------------------------------------------------
Let's get a few housekeeping things out of the way. Firstly because I need to draw lots of
<------------------------------------------------------------------------------------------------------------------------>
+ Secondly make sure TABS are set to 8 characters. The following should be a vertical
+ line. If not, sort out your tabs.
+
+ |
+ |
+ |
+
+ Thirdly I assume that your screen is at least 50 characters high.
+
ASSEMBLING ----------------------------------------------------------------------
If you want to actually run this FORTH, rather than just read it, you will need Linux on an
Now the tutorial starts in earnest.
- INDIRECT THREADED CODE ----------------------------------------------------------------------
+ THE DICTIONARY ----------------------------------------------------------------------
+
+ In FORTH as you will know, functions are called "words", as just as in other languages they
+ have a name and a definition. Here are two FORTH words:
+
+ : DOUBLE DUP + ; \ name is "DOUBLE", definition is "DUP +"
+ : QUADRUPLE DOUBLE DOUBLE ; \ name is "QUADRUPLE", definition is "DOUBLE DOUBLE"
+
+ Words, both built-in ones and ones which the programmer defines later, are stored in a dictionary
+ which is just a linked list of dictionary entries.
+
+ <--- DICTIONARY ENTRY (HEADER) ----------------------->
+ +------------------------+--------+---------- - - - - +----------- - - - -
+ | LINK POINTER | LENGTH/| NAME | DEFINITION
+ | | FLAGS | |
+ +--- (4 bytes) ----------+- byte -+- n bytes - - - - +----------- - - - -
+
+ I'll come to the definition of the word later. For now just look at the header. The first
+ 4 bytes are the link pointer. This points back to the previous word in the dictionary, or, for
+ the first word in the dictionary it is just a NULL pointer. Then comes a length/flags byte.
+ The length of the word can be up to 31 characters (5 bits used) and the top three bits are used
+ for various flags which I'll come to later. This is followed by the name itself, and in this
+ implementation the name is rounded up to a multiple of 4 bytes by padding it with zero bytes.
+ That's just to ensure that the definition starts on a 32 bit boundary.
+
+ A FORTH variable called LATEST contains a pointer to the most recently defined word, in
+ other words, the head of this linked list.
+
+ DOUBLE and QUADRUPLE might look like this:
+
+ pointer to previous word
+ ^
+ |
+ +--|------+---+---+---+---+---+---+---+---+------------- - - - -
+ | LINK | 6 | D | O | U | B | L | E | 0 | (definition ...)
+ +---------+---+---+---+---+---+---+---+---+------------- - - - -
+ ^ len padding
+ |
+ +--|------+---+---+---+---+---+---+---+---+---+---+---+---+------------- - - - -
+ | LINK | 9 | Q | U | A | D | R | U | P | L | E | 0 | 0 | (definition ...)
+ +---------+---+---+---+---+---+---+---+---+---+---+---+---+------------- - - - -
+ ^ len padding
+ |
+ |
+ LATEST
+
+ You shoud be able to see from this how you might implement functions to find a word in
+ the dictionary (just walk along the dictionary entries starting at LATEST and matching
+ the names until you either find a match or hit the NULL pointer at the end of the dictionary),
+ and add a word to the dictionary (create a new definition, set its LINK to LATEST, and set
+ LATEST to point to the new word). We'll see precisely these functions implemented in
+ assembly code later on.
+
+ One interesting consequence of using a linked list is that you can redefine words, and
+ a newer definition of a word overrides an older one. This is an important concept in
+ FORTH because it means that any word (even "built-in" or "standard" words) can be
+ overridden with a new definition, either to enhance it, to make it faster or even to
+ disable it. However because of the way that FORTH words get compiled, which you'll
+ understand below, words defined using the old definition of a word continue to use
+ the old definition. Only words defined after the new definition use the new definition.
+
+ DIRECT THREADED CODE ----------------------------------------------------------------------
+
+ Now we'll get to the really crucial bit in understanding FORTH, so go and get a cup of tea
+ or coffee and settle down. It's fair to say that if you don't understand this section, then you
+ won't "get" how FORTH works, and that would be a failure on my part for not explaining it well.
+ So if after reading this section a few times you don't understand it, please email me
+ (rich@annexia.org).
+
+ Let's talk first about what "threaded code" means. Imagine a peculiar version of C where
+ you are only allowed to call functions without arguments. (Don't worry for now that such a
+ language would be completely useless!) So in our peculiar C, code would look like this:
+
+ f ()
+ {
+ a ();
+ b ();
+ c ();
+ }
+
+ and so on. How would a function, say 'f' above, be compiled by a standard C compiler?
+ Probably into assembly code like this. On the right hand side I've written the actual
+ 16 bit machine code.
+
+ f:
+ CALL a E8 08 00 00 00
+ CALL b E8 1C 00 00 00
+ CALL c E8 2C 00 00 00
+ ; ignore the return from the function for now
+
+ "E8" is the x86 machine code to "CALL" a function. In the first 20 years of computing
+ memory was hideously expensive and we might have worried about the wasted space being used
+ by the repeated "E8" bytes. We can save 20% in code size (and therefore, in expensive memory)
+ by compressing this into just:
+
+ 08 00 00 00 Just the function addresses, without
+ 1C 00 00 00 the CALL prefix.
+ 2C 00 00 00
+
+ [Historical note: If the execution model that FORTH uses looks strange from the following
+ paragraphs, then it was motivated entirely by the need to save memory on early computers.
+ This code compression isn't so important now when our machines have more memory in their L1
+ caches than those early computers had in total, but the execution model still has some
+ useful properties].
+
+ Of course this code won't run directly any more. Instead we need to write an interpreter
+ which takes each pair of bytes and calls it.
+
+ On an i386 machine it turns out that we can write this interpreter rather easily, in just
+ two assembly instructions which turn into just 3 bytes of machine code. Let's store the
+ pointer to the next word to execute in the %esi register:
+
+ 08 00 00 00 <- We're executing this one now. %esi is the _next_ one to execute.
+ %esi -> 1C 00 00 00
+ 2C 00 00 00
+
+ The all-important x86 instruction is called LODSL (or in Intel manuals, LODSW). It does
+ two things. Firstly it reads the memory at %esi into the accumulator (%eax). Secondly it
+ increments %esi by 4 bytes. So after LODSL, the situation now looks like this:
+
+ 08 00 00 00 <- We're still executing this one
+ 1C 00 00 00 <- %eax now contains this address (0x0000001C)
+ %esi -> 2C 00 00 00
+
+ Now we just need to jump to the address in %eax. This is again just a single x86 instruction
+ written JMP *(%eax). And after doing the jump, the situation looks like:
+
+ 08 00 00 00
+ 1C 00 00 00 <- Now we're executing this subroutine.
+ %esi -> 2C 00 00 00
+
+ To make this work, each subroutine is followed by the two instructions 'LODSL; JMP *(%eax)'
+ which literally make the jump to the next subroutine.
+
+ And that brings us to our first piece of actual code! Well, it's a macro.
+*/
-
+/* NEXT macro. */
+ .macro NEXT
+ lodsl
+ jmp *(%eax)
+ .endm
+/* The macro is called NEXT. That's a FORTH-ism. It expands to those two instructions.
+ Every FORTH primitive that we write has to be ended by NEXT. Think of it kind of like
+ a return.
+ The above describes what is known as direct threaded code.
+ To sum up: We compress our function calls down to a list of addresses and use a somewhat
+ magical macro to act as a "jump to next function in the list". We also use one register (%esi)
+ to act as a kind of instruction pointer, pointing to the next function in the list.
+ I'll just give you a hint of what is to come by saying that a FORTH definition such as:
+ : QUADRUPLE DOUBLE DOUBLE ;
+ actually compiles (almost, not precisely but we'll see why in a moment) to a list of
+ function addresses for DOUBLE, DOUBLE and a special function called EXIT to finish off.
-*/
+ At this point, REALLY EAGLE-EYED ASSEMBLY EXPERTS are saying "JONES, YOU'VE MADE A MISTAKE!".
-/* NEXT macro. */
- .macro NEXT
- lodsl
- jmp *(%eax)
- .endm
+ I lied about JMP *(%eax).
+
+ INDIRECT THREADED CODE ----------------------------------------------------------------------
+
+ It turns out that direct threaded code is interesting but only if you want to just execute
+ a list of functions written in assembly language. So QUADRUPLE would work only if DOUBLE
+ was an assembly language function. In the direct threaded code, QUADRUPLE would look like:
+
+ +------------------+
+ | addr of DOUBLE --------------------> (assembly code to do the double)
+ +------------------+ NEXT
+ %esi -> | addr of DOUBLE |
+ +------------------+
+
+ We can add an extra indirection to allow us to run both words written in assembly language
+ (primitives written for speed) and words written in FORTH themselves as lists of addresses.
+
+ The extra indirection is the reason for the brackets in JMP *(%eax).
+
+ Let's have a look at how QUADRUPLE and DOUBLE really look in FORTH:
+
+ : QUADRUPLE DOUBLE DOUBLE ;
+
+ +------------------+
+ | codeword | : DOUBLE DUP + ;
+ +------------------+
+ | addr of DOUBLE ---------------> +------------------+
+ +------------------+ | codeword |
+ | addr of DOUBLE | +------------------+
+ +------------------+ | addr of DUP --------------> +------------------+
+ | addr of EXIT | +------------------+ | codeword -------+
+ +------------------+ %esi -> | addr of + --------+ +------------------+ |
+ +------------------+ | | assembly to <-----+
+ | addr of EXIT | | | implement DUP |
+ +------------------+ | | .. |
+ | | .. |
+ | | NEXT |
+ | +------------------+
+ |
+ +-----> +------------------+
+ | codeword -------+
+ +------------------+ |
+ | assembly to <------+
+ | implement + |
+ | .. |
+ | .. |
+ | NEXT |
+ +------------------+
+
+ This is the part where you may need an extra cup of tea/coffee/favourite caffeinated
+ beverage. What has changed is that I've added an extra pointer to the beginning of
+ the definitions. In FORTH this is sometimes called the "codeword". The codeword is
+ a pointer to the interpreter to run the function. For primitives written in
+ assembly language, the "interpreter" just points to the actual assembly code itself.
+
+ In words written in FORTH (like QUADRUPLE and DOUBLE), the codeword points to an interpreter
+ function.
+
+ I'll show you the interpreter function shortly, but let's recall our indirect
+ JMP *(%eax) with the "extra" brackets. Take the case where we're executing DOUBLE
+ as shown, and DUP has been called. Note that %esi is pointing to the address of +.
+
+ The assembly code for DUP eventually does a NEXT. That:
+
+ (1) reads the address of + into %eax %eax points to the codeword of +
+ (2) increments %esi by 4
+ (3) jumps to the indirect %eax jumps to the address in the codeword of +,
+ ie. the assembly code to implement +
+
+ +------------------+
+ | codeword |
+ +------------------+
+ | addr of DOUBLE ---------------> +------------------+
+ +------------------+ | codeword |
+ | addr of DOUBLE | +------------------+
+ +------------------+ | addr of DUP --------------> +------------------+
+ | addr of EXIT | +------------------+ | codeword -------+
+ +------------------+ | addr of + --------+ +------------------+ |
+ +------------------+ | | assembly to <-----+
+ %esi -> | addr of EXIT | | | implement DUP |
+ +------------------+ | | .. |
+ | | .. |
+ | | NEXT |
+ | +------------------+
+ |
+ +-----> +------------------+
+ | codeword -------+
+ +------------------+ |
+ now we're | assembly to <------+
+ executing | implement + |
+ this | .. |
+ function | .. |
+ | NEXT |
+ +------------------+
+
+ So I hope that I've convinced you that NEXT does roughly what you'd expect. This is
+ indirect threaded code.
+
+ I've glossed over four things. I wonder if you can guess without reading on what they are?
+
+ .
+ .
+ .
+
+ My list of four things are: (1) What does "EXIT" do? (2) which is related to (1) is how do
+ you call into a function, ie. how does %esi start off pointing at part of QUADRUPLE, but
+ then point at part of DOUBLE. (3) What goes in the codeword for the words which are written
+ in FORTH? (4) How do you compile a function which does anything except call other functions
+ ie. a function which contains a number like : DOUBLE 2 * ; ?
+
+ THE INTERPRETER AND RETURN STACK ------------------------------------------------------------
+
+ Going at these in no particular order, let's talk about issues (3) and (2), the interpreter
+ and the return stack.
+
+ Words which are defined in FORTH need a codeword which points to a little bit of code to
+ give them a "helping hand" in life. They don't need much, but they do need what is known
+ as an "interpreter", although it doesn't really "interpret" in the same way that, say,
+ Java bytecode used to be interpreted (ie. slowly). This interpreter just sets up a few
+ machine registers so that the word can then execute at full speed using the indirect
+ threaded model above.
+
+ One of the things that needs to happen when QUADRUPLE calls DOUBLE is that we save the old
+ %esi ("instruction pointer") and create a new one pointing to the first word in DOUBLE.
+ Because we will need to restore the old %esi at the end of DOUBLE (this is, after all, like
+ a function call), we will need a stack to store these "return addresses" (old values of %esi).
+
+ As you will have read, when reading the background documentation, FORTH has two stacks,
+ an ordinary stack for parameters, and a return stack which is a bit more mysterious. But
+ our return stack is just the stack I talked about in the previous paragraph, used to save
+ %esi when calling from a FORTH word into another FORTH word.
+
+ In this FORTH, we are using the normal stack pointer (%esp) for the parameter stack.
+ We will use the i386's "other" stack pointer (%ebp, usually called the "frame pointer")
+ for our return stack.
+
+ I've got two macros which just wrap up the details of using %ebp for the return stack:
+*/
/* Macros to deal with the return stack. */
.macro PUSHRSP reg
lea 4(%ebp),%ebp
.endm
+/*
+ And with that we can now talk about the interpreter.
+
+ In FORTH the interpreter function is often called DOCOL (I think it means "DO COLON" because
+ all FORTH definitions start with a colon, as in : DOUBLE DUP + ;
+
+ The "interpreter" (it's not really "interpreting") just needs to push the old %esi on the
+ stack and set %esi to the first word in the definition. Remember that we jumped to the
+ function using JMP *(%eax)? Well a consequence of that is that conveniently %eax contains
+ the address of this codeword, so just by adding 4 to it we get the address of the first
+ data word. Finally after setting up %esi, it just does NEXT which causes that first word
+ to run.
+*/
+
+/* DOCOL - the interpreter! */
+ .text
+ .align 4
+DOCOL:
+ PUSHRSP %esi // push %esi on to the return stack
+ addl $4,%eax // %eax points to codeword, so make
+ movl %eax,%esi // %esi point to first data word
+ NEXT
+
+/*
+ Just to make this absolutely clear, let's see how DOCOL works when jumping from QUADRUPLE
+ into DOUBLE:
+
+ QUADRUPLE:
+ +------------------+
+ | codeword |
+ +------------------+ DOUBLE:
+ | addr of DOUBLE ---------------> +------------------+
+ +------------------+ %eax -> | addr of DOCOL |
+ %esi -> | addr of DOUBLE | +------------------+
+ +------------------+ | addr of DUP -------------->
+ | addr of EXIT | +------------------+
+ +------------------+ | etc. |
+
+ First, the call to DOUBLE causes DOCOL (the codeword of DOUBLE). DOCOL does this: It
+ pushes the old %esi on the return stack. %eax points to the codeword of DOUBLE, so we
+ just add 4 on to it to get our new %esi:
+
+ QUADRUPLE:
+ +------------------+
+ | codeword |
+ +------------------+ DOUBLE:
+ | addr of DOUBLE ---------------> +------------------+
+ +------------------+ | addr of DOCOL |
+ | addr of DOUBLE | +------------------+
+ +------------------+ %esi -> | addr of DUP -------------->
+ | addr of EXIT | +------------------+
+ +------------------+ | etc. |
+
+ Then we do NEXT, and because of the magic of threaded code that increments %esi again
+ and calls DUP.
+
+ Well, it seems to work.
+
+ One minor point here. Because DOCOL is the first bit of assembly actually to be defined
+ in this file (the others were just macros), and because I usually compile this code with the
+ text segment starting at address 0, DOCOL has address 0. So if you are disassembling the
+ code and see a word with a codeword of 0, you will immediately know that the word is
+ written in FORTH (it's not an assembler primitive) and so uses DOCOL as the interpreter.
+*/
+
+
+
+
/* ELF entry point. */
.text
.globl _start
cold_start: // High-level code without a codeword.
.int COLD
-/* DOCOL - the interpreter! */
- .text
- .align 4
-DOCOL:
- PUSHRSP %esi // push %esi on to the return stack
- addl $4,%eax // %eax points to codeword, so make
- movl %eax,%esi // %esi point to first data word
- NEXT
-
/*----------------------------------------------------------------------
* Fixed sized buffers for everything.
*/
projects / rrq / jonesforth.git / blobdiff