X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;ds=sidebyside;f=jonesforth.S;h=20f6e695d13feb175cfe01b76cfc03f53d8a6c0e;hb=deea51e0a6ac4c90629b5e7a6819d54b93a95abe;hp=49c8303166670bd2e1aa6a5f6a81da4e1b8ad93c;hpb=f7c5270917edc9078e85b10f6ef98017a95dc990;p=rrq%2Fjonesforth.git
diff --git a/jonesforth.S b/jonesforth.S
index 49c8303..20f6e69 100644
--- a/jonesforth.S
+++ b/jonesforth.S
@@ -61,6 +61,14 @@
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.
+
+ Also I used this document (http://ftp.funet.fi/pub/doc/IOCCC/1992/buzzard.2.design) which really
+ defies easy explanation.
+
SETTING UP ----------------------------------------------------------------------
Let's get a few housekeeping things out of the way. Firstly because I need to draw lots of
@@ -69,6 +77,15 @@
<------------------------------------------------------------------------------------------------------------------------>
+ 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
@@ -125,7 +142,7 @@
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 2 * ; \ name is "DOUBLE", definition is "2 *"
+ : 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
@@ -173,7 +190,15 @@
LATEST to point to the new word). We'll see precisely these functions implemented in
assembly code later on.
- INDIRECT THREADED CODE ----------------------------------------------------------------------
+ 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
@@ -181,15 +206,72 @@
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. */
@@ -198,6 +280,168 @@
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!".
+
+ 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.
+ They don't need interpreting, they just run.
+
+ 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.
+ You use them as for example "PUSHRSP %eax" (push %eax on the return stack) or "POPRSP %ebx"
+ (pop top of return stack into %ebx).
+*/
+
/* Macros to deal with the return stack. */
.macro PUSHRSP reg
lea -4(%ebp),%ebp // push reg on to return stack
@@ -209,6 +453,84 @@
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 ---------------> +------------------+
+top of return +------------------+ %eax -> | addr of DOCOL |
+stack points -> | addr of DOUBLE | + 4 = +------------------+
+ +------------------+ %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.
+
+ STARTING UP ----------------------------------------------------------------------
+
+ Now let's get down to nuts and bolts. When we start the program we need to set up
+ a few things like the return stack. But as soon as we can, we want to jump into FORTH
+ code (albeit much of the "early" FORTH code will still need to be written as
+ assembly language primitives).
+
+ This is what the set up code does. Does a tiny bit of house-keeping, sets up the
+ separate return stack (NB: Linux gives us the ordinary parameter stack already), then
+ immediately jumps to a FORTH word called COLD. COLD stands for cold-start. In ISO
+ FORTH (but not in this FORTH), COLD can be called at any time to completely reset
+ the state of FORTH, and there is another word called WARM which does a partial reset.
+*/
+
/* ELF entry point. */
.text
.globl _start
@@ -224,25 +546,18 @@ _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
+/*
+ We also allocate some space for the return stack and some space to store user
+ definitions. These are static memory allocations using fixed-size buffers, but it
+ wouldn't be a great deal of work to make them dynamic.
+*/
-/*----------------------------------------------------------------------
- * Fixed sized buffers for everything.
- */
.bss
-
/* FORTH return stack. */
#define RETURN_STACK_SIZE 8192
.align 4096
.space RETURN_STACK_SIZE
-return_stack:
+return_stack: // Initial top of return stack.
/* Space for user-defined words. */
#define USER_DEFS_SIZE 16384
@@ -250,21 +565,57 @@ return_stack:
user_defs_start:
.space USER_DEFS_SIZE
+/*
+ BUILT-IN WORDS ----------------------------------------------------------------------
+ Remember our dictionary entries (headers). Let's bring those together with the codeword
+ and data words to see how : DOUBLE DUP + ; really looks in memory.
+ pointer to previous word
+ ^
+ |
+ +--|------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
+ | LINK | 6 | D | O | U | B | L | E | 0 | DOCOL | DUP | + | EXIT |
+ +---------+---+---+---+---+---+---+---+---+------------+--|---------+------------+------------+
+ ^ len pad codeword |
+ | V
+ LINK in next word points to codeword of DUP
+
+ Initially we can't just write ": DOUBLE DUP + ;" (ie. that literal string) here because we
+ don't yet have anything to read the string, break it up at spaces, parse each word, etc. etc.
+ So instead we will have to define built-in words using the GNU assembler data constructors
+ (like .int, .byte, .string, .ascii and so on -- look them up in the gas info page if you are
+ unsure of them).
+
+ The long way would be:
+ .int
+ .byte 6 // len
+ .ascii "DOUBLE" // string
+ .byte 0 // padding
+DOUBLE: .int DOCOL // codeword
+ .int DUP // pointer to codeword of DUP
+ .int PLUS // pointer to codeword of +
+ .int EXIT // pointer to codeword of EXIT
+
+ That's going to get quite tedious rather quickly, so here I define an assembler macro
+ so that I can just write:
+
+ defword "DOUBLE",6,,DOUBLE
+ .int DUP,PLUS,EXIT
+
+ and I'll get exactly the same effect.
+
+ Don't worry too much about the exact implementation details of this macro - it's complicated!
+*/
-
-
-/*----------------------------------------------------------------------
- * Built-in words defined the long way.
- */
+/* Flags - these are discussed later. */
#define F_IMMED 0x80
#define F_HIDDEN 0x20
// Store the chain of links.
.set link,0
- .macro defcode name, namelen, flags=0, label
+ .macro defword name, namelen, flags=0, label
.section .rodata
.align 4
.globl name_\label
@@ -276,14 +627,32 @@ name_\label :
.align 4
.globl \label
\label :
- .int code_\label // codeword
- .text
- .align 4
- .globl code_\label
-code_\label : // assembler code follows
+ .int DOCOL // codeword - the interpreter
+ // list of word pointers follow
.endm
- .macro defword name, namelen, flags=0, label
+/*
+ Similarly I want a way to write words written in assembly language. There will quite a few
+ of these to start with because, well, everything has to start in assembly before there's
+ enough "infrastructure" to be able to start writing FORTH words, but also I want to define
+ some common FORTH words in assembly language for speed, even though I could write them in FORTH.
+
+ This is what DUP looks like in memory:
+
+ pointer to previous word
+ ^
+ |
+ +--|------+---+---+---+---+------------+
+ | LINK | 3 | D | U | P | code_DUP ---------------------> points to the assembly
+ +---------+---+---+---+---+------------+ code used to write DUP,
+ ^ len codeword which is ended with NEXT.
+ |
+ LINK in next word
+
+ Again, for brevity in writing the header I'm going to write an assembler macro called defcode.
+*/
+
+ .macro defcode name, namelen, flags=0, label
.section .rodata
.align 4
.globl name_\label
@@ -295,24 +664,18 @@ name_\label :
.align 4
.globl \label
\label :
- .int DOCOL // codeword - the interpreter
- // list of word pointers follow
- .endm
-
- .macro defvar name, namelen, flags=0, label, initial=0
- defcode \name,\namelen,\flags,\label
- push $var_\name
- NEXT
- .data
+ .int code_\label // codeword
+ .text
.align 4
-var_\name :
- .int \initial
+ .globl code_\label
+code_\label : // assembler code follows
.endm
- // Some easy ones, written in assembly for speed
- defcode "DROP",4,,DROP
- pop %eax // drop top of stack
- NEXT
+/*
+ Now some easy FORTH primitives. These are written in assembly for speed. If you understand
+ i386 assembly language then it is worth reading these. However if you don't understand assembly
+ you can skip the details.
+*/
defcode "DUP",3,,DUP
pop %eax // duplicate top of stack
@@ -320,6 +683,10 @@ var_\name :
push %eax
NEXT
+ defcode "DROP",4,,DROP
+ pop %eax // drop top of stack
+ NEXT
+
defcode "SWAP",4,,SWAP
pop %eax // swap top of stack
pop %ebx
@@ -367,13 +734,13 @@ var_\name :
NEXT
defcode "+",1,,ADD
- pop %eax
- addl %eax,(%esp)
+ pop %eax // get top of stack
+ addl %eax,(%esp) // and add it to next word on stack
NEXT
defcode "-",1,,SUB
- pop %eax
- subl %eax,(%esp)
+ pop %eax // get top of stack
+ subl %eax,(%esp) // and subtract if from next word on stack
NEXT
defcode "*",1,,MUL
@@ -438,20 +805,83 @@ var_\name :
orl %eax,(%esp)
NEXT
- defcode "INVERT",6,,INVERT
+ defcode "INVERT",6,,INVERT // this is the FORTH "NOT" function
notl (%esp)
NEXT
- // COLD must not return (ie. must not call EXIT).
- defword "COLD",4,,COLD
- // XXX reinitialisation of the interpreter
- .int INTERPRETER // call the interpreter loop (never returns)
- .int LIT,1,SYSEXIT // hmmm, but in case it does, exit(1).
+/*
+ RETURNING FROM FORTH WORDS ----------------------------------------------------------------------
+
+ Time to talk about what happens when we EXIT a function. In this diagram QUADRUPLE has called
+ DOUBLE, and DOUBLE is about to exit (look at where %esi is pointing):
+
+ QUADRUPLE
+ +------------------+
+ | codeword |
+ +------------------+ DOUBLE
+ | addr of DOUBLE ---------------> +------------------+
+ +------------------+ | codeword |
+ | addr of DOUBLE | +------------------+
+ +------------------+ | addr of DUP |
+ | addr of EXIT | +------------------+
+ +------------------+ | addr of + |
+ +------------------+
+ %esi -> | addr of EXIT |
+ +------------------+
+
+ What happens when the + function does NEXT? Well, the following code is executed.
+*/
defcode "EXIT",4,,EXIT
POPRSP %esi // pop return stack into %esi
NEXT
+/*
+ EXIT gets the old %esi which we saved from before on the return stack, and puts it in %esi.
+ So after this (but just before NEXT) we get:
+
+ QUADRUPLE
+ +------------------+
+ | codeword |
+ +------------------+ DOUBLE
+ | addr of DOUBLE ---------------> +------------------+
+ +------------------+ | codeword |
+ %esi -> | addr of DOUBLE | +------------------+
+ +------------------+ | addr of DUP |
+ | addr of EXIT | +------------------+
+ +------------------+ | addr of + |
+ +------------------+
+ | addr of EXIT |
+ +------------------+
+
+ And NEXT just completes the job by, well in this case just by calling DOUBLE again :-)
+
+ LITERALS ----------------------------------------------------------------------
+
+ The final point I "glossed over" before was how to deal with functions that do anything
+ apart from calling other functions. For example, suppose that DOUBLE was defined like this:
+
+ : DOUBLE 2 * ;
+
+ It does the same thing, but how do we compile it since it contains the literal 2? One way
+ would be to have a function called "2" (which you'd have to write in assembler), but you'd need
+ a function for every single literal that you wanted to use.
+
+ FORTH solves this by compiling the function using a special word called LIT:
+
+ +---------------------------+-------+-------+-------+-------+-------+
+ | (usual header of DOUBLE) | DOCOL | LIT | 2 | * | EXIT |
+ +---------------------------+-------+-------+-------+-------+-------+
+
+ LIT is executed in the normal way, but what it does next is definitely not normal. It
+ looks at %esi (which now points to the literal 2), grabs it, pushes it on the stack, then
+ manipulates %esi in order to skip the literal as if it had never been there.
+
+ What's neat is that the whole grab/manipulate can be done using a single byte single
+ i386 instruction, our old friend LODSL. Rather than me drawing more ASCII-art diagrams,
+ see if you can find out how LIT works:
+*/
+
defcode "LIT",3,,LIT
// %esi points to the next command, but in this case it points to the next
// literal 32 bit integer. Get that literal into %eax and increment %esi.
@@ -460,25 +890,13 @@ var_\name :
push %eax // push the literal number on to stack
NEXT
- defcode "LITSTRING",9,,LITSTRING
- lodsl // get the length of the string
- push %eax // push it on the stack
- push %esi // push the address of the start of the string
- addl %eax,%esi // skip past the string
- addl $3,%esi // but round up to next 4 byte boundary
- andl $~3,%esi
- NEXT
-
- defcode "BRANCH",6,,BRANCH
- add (%esi),%esi // add the offset to the instruction pointer
- NEXT
+/*
+ MEMORY ----------------------------------------------------------------------
- defcode "0BRANCH",7,,ZBRANCH
- pop %eax
- test %eax,%eax // top of stack is zero?
- jz code_BRANCH // if so, jump back to the branch function above
- lodsl // otherwise we need to skip the offset
- NEXT
+ As important point about FORTH is that it gives you direct access to the lowest levels
+ of the machine. Manipulating memory directly is done frequently in FORTH, and these are
+ the primitive words for doing it.
+*/
defcode "!",1,,STORE
pop %ebx // address to store at
@@ -522,34 +940,59 @@ var_\name :
push %eax // push value onto stack
NEXT
- // The STATE variable is 0 for execute mode, != 0 for compile mode
- defvar "STATE",5,,STATE
+/*
+ BUILT-IN VARIABLES ----------------------------------------------------------------------
- // This points to where compiled words go.
- defvar "HERE",4,,HERE,user_defs_start
+ These are some built-in variables and related standard FORTH words. Of these, the only one that we
+ have discussed so far was LATEST, which points to the last (most recently defined) word in the
+ FORTH dictionary. LATEST is also a FORTH word which pushes the address of LATEST (the variable)
+ on to the stack, so you can read or write it using @ and ! operators. For example, to print
+ the current value of LATEST (and this can apply to any FORTH variable) you would do:
- // This is the last definition in the dictionary.
- defvar "LATEST",6,,LATEST,name_SYSEXIT // SYSEXIT must be last in built-in dictionary
+ LATEST @ . CR
+
+ To make defining variables shorter, I'm using a macro called defvar, similar to defword and
+ defcode above. (In fact the defvar macro uses defcode to do the dictionary header).
+*/
+
+ .macro defvar name, namelen, flags=0, label, initial=0
+ defcode \name,\namelen,\flags,\label
+ push $var_\name
+ NEXT
+ .data
+ .align 4
+var_\name :
+ .int \initial
+ .endm
+
+/*
+ The built-in variables are:
- // _X, _Y and _Z are scratch variables used by standard words.
+ STATE Is the interpreter executing code (0) or compiling a word (non-zero)?
+ LATEST Points to the latest (most recently defined) word in the dictionary.
+ HERE Points to the next free byte of memory. When compiling, compiled words go here.
+ _X These are three scratch variables, used by some standard dictionary words.
+ _Y
+ _Z
+ S0 Stores the address of the top of the parameter stack.
+ R0 Stores the address of the top of the return stack.
+
+*/
+ defvar "STATE",5,,STATE
+ defvar "HERE",4,,HERE,user_defs_start
+ defvar "LATEST",6,,LATEST,name_SYSEXIT // SYSEXIT must be last in built-in dictionary
defvar "_X",2,,TX
defvar "_Y",2,,TY
defvar "_Z",2,,TZ
-
- // This stores the top of the data stack.
defvar "S0",2,,SZ
-
- // This stores the top of the return stack.
defvar "R0",2,,RZ,return_stack
- defcode "DSP@",4,,DSPFETCH
- mov %esp,%eax
- push %eax
- NEXT
+/*
+ RETURN STACK ----------------------------------------------------------------------
- defcode "DSP!",4,,DSPSTORE
- pop %esp
- NEXT
+ These words allow you to access the return stack. Recall that the register %ebp always points to
+ the top of the return stack.
+*/
defcode ">R",2,,TOR
pop %eax // pop parameter stack into %eax
@@ -573,6 +1016,48 @@ var_\name :
lea 4(%ebp),%ebp // pop return stack and throw away
NEXT
+/*
+ PARAMETER (DATA) STACK ----------------------------------------------------------------------
+
+ These functions allow you to manipulate the parameter stack. Recall that Linux sets up the parameter
+ stack for us, and it is accessed through %esp.
+*/
+
+ defcode "DSP@",4,,DSPFETCH
+ mov %esp,%eax
+ push %eax
+ NEXT
+
+ defcode "DSP!",4,,DSPSTORE
+ pop %esp
+ NEXT
+
+/*
+ INPUT AND OUTPUT ----------------------------------------------------------------------
+
+ These are our first really meaty/complicated FORTH primitives. I have chosen to write them in
+ assembler, but surprisingly in "real" FORTH implementations these are often written in terms
+ of more fundamental FORTH primitives. I chose to avoid that because I think that just obscures
+ the implementation. After all, you may not understand assembler but you can just think of it
+ as an opaque block of code that does what it says.
+
+ Let's discuss input first.
+
+ The FORTH word KEY reads the next byte from stdin (and pushes it on the parameter stack).
+ So if KEY is called and someone hits the space key, then the number 32 (ASCII code of space)
+ is pushed on the stack.
+
+ In FORTH there is no distinction between reading code and reading input. We might be reading
+ and compiling code, we might be reading words to execute, we might be asking for the user
+ to type their name -- ultimately it all comes in through KEY.
+
+ The implementation of KEY uses an input buffer so a certain size (defined at the end of the
+ program). It calls the Linux read(2) system call to fill this buffer and tracks its position
+ in the buffer using a couple of variables, and if it runs out of input buffer then it refills
+ it automatically. The other thing that KEY does is if it detects that stdin has closed, it
+ exits the program, which is why when you hit ^D the FORTH system cleanly exits.
+*/
+
#include
defcode "KEY",3,,KEY
@@ -607,6 +1092,12 @@ _KEY:
mov $__NR_exit,%eax // syscall: exit
int $0x80
+/*
+ By contrast, output is much simpler. The FORTH word EMIT writes out a single byte to stdout.
+ This implementation just uses the write system call. No attempt is made to buffer output, but
+ it would be a good exercise to add it.
+*/
+
defcode "EMIT",4,,EMIT
pop %eax
call _EMIT
@@ -627,6 +1118,33 @@ _EMIT:
.bss
2: .space 1 // scratch used by EMIT
+/*
+ Back to input, WORD is a FORTH word which reads the next full word of input.
+
+ What it does in detail is that it first skips any blanks (spaces, tabs, newlines and so on).
+ Then it calls KEY to read characters into an internal buffer until it hits a blank. Then it
+ calculates the length of the word it read and returns the address and the length as
+ two words on the stack (with address at the top).
+
+ Notice that WORD has a single internal buffer which it overwrites each time (rather like
+ a static C string). Also notice that WORD's internal buffer is just 32 bytes long and
+ there is NO checking for overflow. 31 bytes happens to be the maximum length of a
+ FORTH word that we support, and that is what WORD is used for: to read FORTH words when
+ we are compiling and executing code. The returned strings are not NUL-terminated, so
+ in some crazy-world you could define FORTH words containing ASCII NULs, although why
+ you'd want to is a bit beyond me.
+
+ WORD is not suitable for just reading strings (eg. user input) because of all the above
+ peculiarities and limitations.
+
+ Note that when executing, you'll see:
+ WORD FOO
+ which puts "FOO" and length 3 on the stack, but when compiling:
+ : BAR WORD FOO ;
+ is an error (or at least it doesn't do what you might expect). Later we'll talk about compiling
+ and immediate mode, and you'll understand why.
+*/
+
defcode "WORD",4,,WORD
call _WORD
push %ecx // push length
@@ -668,15 +1186,14 @@ _WORD:
// overwrite this buffer. Maximum word length is 32 chars.
5: .space 32
- defcode "EMITSTRING",10,,EMITSTRING
- mov $1,%ebx // 1st param: stdout
- pop %ecx // 2nd param: address of string
- pop %edx // 3rd param: length of string
-
- mov $__NR_write,%eax // write syscall
- int $0x80
+/*
+ . (also called DOT) prints the top of the stack as an integer. In real FORTH implementations
+ it should print it in the current base, but this assembler version is simpler and can only
+ print in base 10.
- NEXT
+ Remember that you can override even built-in FORTH words easily, so if you want to write a
+ more advanced DOT then you can do so easily at a later point, and probably in FORTH.
+*/
defcode ".",1,,DOT
pop %eax // Get the number to print into %eax
@@ -701,9 +1218,16 @@ _DOT:
call _EMIT
ret
- // Parse a number from a string on the stack -- almost the opposite of . (DOT)
- // Note that there is absolutely no error checking. In particular the length of the
- // string must be >= 1 bytes.
+/*
+ Almost the opposite of DOT (but not quite), SNUMBER parses a numeric string such as one returned
+ by WORD and pushes the number on the parameter stack.
+
+ This function does absolutely no error checking, and in particular the length of the string
+ must be >= 1 bytes, and should contain only digits 0-9. If it doesn't you'll get random results.
+
+ This function is only used when reading literal numbers in code, and shouldn't really be used
+ in user code at all.
+*/
defcode "SNUMBER",7,,SNUMBER
pop %edi
pop %ecx
@@ -723,6 +1247,30 @@ _SNUMBER:
jnz 1b
ret
+/*
+ DICTIONARY LOOK UPS ----------------------------------------------------------------------
+
+ We're building up to our prelude on how FORTH code is compiled, but first we need yet more infrastructure.
+
+ The FORTH word FIND takes a string (a word as parsed by WORD -- see above) and looks it up in the
+ dictionary. What it actually returns is the address of the dictionary header, if it finds it,
+ or 0 if it didn't.
+
+ So if DOUBLE is defined in the dictionary, then WORD DOUBLE FIND returns the following pointer:
+
+ pointer to this
+ |
+ |
+ V
+ +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
+ | LINK | 6 | D | O | U | B | L | E | 0 | DOCOL | DUP | + | EXIT |
+ +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
+
+ See also >CFA which takes a dictionary entry pointer and returns a pointer to the codeword.
+
+ FIND doesn't find dictionary entries which are flagged as HIDDEN. See below for why.
+*/
+
defcode "FIND",4,,FIND
pop %edi // %edi = address
pop %ecx // %ecx = length
@@ -771,7 +1319,31 @@ _FIND:
xor %eax,%eax // Return zero to indicate not found.
ret
- defcode ">CFA",4,,TCFA // DEA -> Codeword address
+/*
+ FIND returns the dictionary pointer, but when compiling we need the codeword pointer (recall
+ that FORTH definitions are compiled into lists of codeword pointers).
+
+ In the example below, WORD DOUBLE FIND >CFA
+
+ FIND returns a pointer to this
+ | >CFA converts it to a pointer to this
+ | |
+ V V
+ +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
+ | LINK | 6 | D | O | U | B | L | E | 0 | DOCOL | DUP | + | EXIT |
+ +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
+
+ Notes:
+
+ Because names vary in length, this isn't just a simple increment.
+
+ In this FORTH you cannot easily turn a codeword pointer back into a dictionary entry pointer, but
+ that is not true in most FORTH implementations where they store a back pointer in the definition
+ (with an obvious memory/complexity cost). The reason they do this is that it is useful to be
+ able to go backwards (codeword -> dictionary entry) in order to decompile FORTH definitions.
+*/
+
+ defcode ">CFA",4,,TCFA
pop %edi
call _TCFA
push %edi
@@ -787,12 +1359,91 @@ _TCFA:
andl $~3,%edi
ret
- defcode "CHAR",4,,CHAR
- call _WORD // Returns %ecx = length, %edi = pointer to word.
- xor %eax,%eax
- movb (%edi),%al // Get the first character of the word.
- push %eax // Push it onto the stack.
- NEXT
+/*
+ COMPILING ----------------------------------------------------------------------
+
+ Now we'll talk about how FORTH compiles words. Recall that a word definition looks like this:
+
+ : DOUBLE DUP + ;
+
+ and we have to turn this into:
+
+ pointer to previous word
+ ^
+ |
+ +--|------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+
+ | LINK | 6 | D | O | U | B | L | E | 0 | DOCOL | DUP | + | EXIT |
+ +---------+---+---+---+---+---+---+---+---+------------+--|---------+------------+------------+
+ ^ len pad codeword |
+ | V
+ LATEST points here points to codeword of DUP
+
+ There are several problems to solve. Where to put the new word? How do we read words? How
+ do we define : (COLON) and ; (SEMICOLON)?
+
+ FORTH solves this rather elegantly and as you might expect in a very low-level way which
+ allows you to change how the compiler works in your own code.
+
+ FORTH has an interpreter function (a true interpreter this time, not DOCOL) which runs in a
+ loop, reading words (using WORD), looking them up (using FIND), turning them into codeword
+ points (using >CFA) and deciding what to do with them. What it does depends on the mode
+ of the interpreter (in variable STATE). When STATE is zero, the interpreter just calls
+ each word as it looks them up. (Known as immediate mode).
+
+ The interesting stuff happens when STATE is non-zero -- compiling mode. In this mode the
+ interpreter just appends the codeword pointers to user memory (the HERE variable points to
+ the next free byte of user memory).
+
+ So you may be able to see how we could define : (COLON). The general plan is:
+
+ (1) Use WORD to read the name of the function being defined.
+
+ (2) Construct the dictionary entry header in user memory:
+
+ pointer to previous word (from LATEST) +-- Afterwards, HERE points here, where
+ ^ | the interpreter will start appending
+ | V codewords.
+ +--|------+---+---+---+---+---+---+---+---+------------+
+ | LINK | 6 | D | O | U | B | L | E | 0 | DOCOL |
+ +---------+---+---+---+---+---+---+---+---+------------+
+ len pad codeword
+
+ (3) Set LATEST to point to the newly defined word and most importantly leave HERE pointing
+ just after the new codeword. This is where the interpreter will append codewords.
+
+ (4) Set STATE to 1. Go into compile mode so the interpreter starts appending codewords.
+
+ After : has run, our input is here:
+
+ : DOUBLE DUP + ;
+ ^
+ |
+ Next byte returned by KEY
+
+ so the interpreter (now it's in compile mode, so I guess it's really the compiler) reads DUP,
+ gets its codeword pointer, and appends it:
+
+ +-- HERE updated to point here.
+ |
+ V
+ +---------+---+---+---+---+---+---+---+---+------------+------------+
+ | LINK | 6 | D | O | U | B | L | E | 0 | DOCOL | DUP |
+ +---------+---+---+---+---+---+---+---+---+------------+------------+
+ len pad codeword
+
+ Next we read +, get the codeword pointer, and append it:
+
+ +-- HERE updated to point here.
+ |
+ V
+ +---------+---+---+---+---+---+---+---+---+------------+------------+------------+
+ | LINK | 6 | D | O | U | B | L | E | 0 | DOCOL | DUP | + |
+ +---------+---+---+---+---+---+---+---+---+------------+------------+------------+
+ len pad codeword
+
+
+
+*/
defcode ":",1,,COLON
@@ -837,14 +1488,13 @@ _COMMA:
movl %edi,var_HERE // Update HERE (incremented)
ret
- defcode "HIDDEN",6,,HIDDEN
- call _HIDDEN
+ defcode ";",1,F_IMMED,SEMICOLON
+ movl $EXIT,%eax // EXIT is the final codeword in compiled words.
+ call _COMMA // Store it.
+ call _HIDDEN // Toggle the HIDDEN flag (unhides the new word).
+ xor %eax,%eax // Set STATE to 0 (back to execute mode).
+ movl %eax,var_STATE
NEXT
-_HIDDEN:
- movl var_LATEST,%edi // LATEST word.
- addl $4,%edi // Point to name/flags byte.
- xorb $F_HIDDEN,(%edi) // Toggle the HIDDEN bit.
- ret
defcode "IMMEDIATE",9,F_IMMED,IMMEDIATE
call _IMMEDIATE
@@ -855,12 +1505,20 @@ _IMMEDIATE:
xorb $F_IMMED,(%edi) // Toggle the IMMED bit.
ret
- defcode ";",1,F_IMMED,SEMICOLON
- movl $EXIT,%eax // EXIT is the final codeword in compiled words.
- call _COMMA // Store it.
- call _HIDDEN // Toggle the HIDDEN flag (unhides the new word).
- xor %eax,%eax // Set STATE to 0 (back to execute mode).
- movl %eax,var_STATE
+ defcode "HIDDEN",6,,HIDDEN
+ call _HIDDEN
+ NEXT
+_HIDDEN:
+ movl var_LATEST,%edi // LATEST word.
+ addl $4,%edi // Point to name/flags byte.
+ xorb $F_HIDDEN,(%edi) // Toggle the HIDDEN bit.
+ ret
+
+ defcode "CHAR",4,,CHAR
+ call _WORD // Returns %ecx = length, %edi = pointer to word.
+ xor %eax,%eax
+ movb (%edi),%al // Get the first character of the word.
+ push %eax // Push it onto the stack.
NEXT
/* This definiton of ' (TICK) is strictly cheating - it also only works in compiled code. */
@@ -869,6 +1527,41 @@ _IMMEDIATE:
pushl %eax // Push it on the stack.
NEXT
+ defcode "BRANCH",6,,BRANCH
+ add (%esi),%esi // add the offset to the instruction pointer
+ NEXT
+
+ defcode "0BRANCH",7,,ZBRANCH
+ pop %eax
+ test %eax,%eax // top of stack is zero?
+ jz code_BRANCH // if so, jump back to the branch function above
+ lodsl // otherwise we need to skip the offset
+ NEXT
+
+ defcode "LITSTRING",9,,LITSTRING
+ lodsl // get the length of the string
+ push %eax // push it on the stack
+ push %esi // push the address of the start of the string
+ addl %eax,%esi // skip past the string
+ addl $3,%esi // but round up to next 4 byte boundary
+ andl $~3,%esi
+ NEXT
+
+ defcode "EMITSTRING",10,,EMITSTRING
+ mov $1,%ebx // 1st param: stdout
+ pop %ecx // 2nd param: address of string
+ pop %edx // 3rd param: length of string
+
+ mov $__NR_write,%eax // write syscall
+ int $0x80
+
+ NEXT
+
+ // COLD must not return (ie. must not call EXIT).
+ defword "COLD",4,,COLD
+ .int INTERPRETER // call the interpreter loop (never returns)
+ .int LIT,1,SYSEXIT // hmmm, but in case it does, exit(1).
+
/* This interpreter is pretty simple, but remember that in FORTH you can always override
* it later with a more powerful one!
*/