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
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 +.
+ 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:
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:
+ 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. */
| codeword |
+------------------+ DOUBLE:
| addr of DOUBLE ---------------> +------------------+
- +------------------+ | addr of DOCOL |
- | addr of DOUBLE | +------------------+
+top of return +------------------+ %eax -> | addr of DOCOL |
+stack points -> | addr of DOUBLE | + 4 = +------------------+
+------------------+ %esi -> | addr of DUP -------------->
| addr of EXIT | +------------------+
+------------------+ | etc. |
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
cold_start: // High-level code without a codeword.
.int COLD
-/*----------------------------------------------------------------------
- * Fixed sized buffers for everything.
- */
- .bss
+/*
+ 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.
+*/
+ .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
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 <link to previous word>
+ .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
.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
.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
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
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
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.
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
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
- // _X, _Y and _Z are scratch variables used by standard words.
+/*
+ The built-in variables are:
+
+ 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 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
+/*
+ RETURN STACK ----------------------------------------------------------------------
+
+ These words allow you to access the return stack. Recall that the register %ebp always points to
+ the top of the return stack.
+*/
+
defcode "DSP@",4,,DSPFETCH
mov %esp,%eax
push %eax
lea 4(%ebp),%ebp // pop return stack and throw away
NEXT
+/*
+ INPUT AND OUTPUT ----------------------------------------------------------------------
+
+
+
+
+*/
+
#include <asm-i386/unistd.h>
defcode "KEY",3,,KEY
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
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
/* This definiton of ' (TICK) is strictly cheating - it also only works in compiled code. */
defcode "'",1,,TICK
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
+
+ // 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!
*/
projects / rrq / jonesforth.git / blobdiff