X-Git-Url: http://git.annexia.org/?a=blobdiff_plain;f=jonesforth.S;h=c41cbed029bb72676d7fd5b6a26fb29701138cd0;hb=9b874d69d45a0946840b5bb984e1e41d5307be1a;hp=dfa173ca71e3af883bc0fddc2867c1b908f843b2;hpb=964d44d11ff6cca78e7cf90fe597efbfd51ea8f9;p=jonesforth.git diff --git a/jonesforth.S b/jonesforth.S index dfa173c..c41cbed 100644 --- a/jonesforth.S +++ b/jonesforth.S @@ -1,8 +1,12 @@ /* A sometimes minimal FORTH compiler and tutorial for Linux / i386 systems. -*- asm -*- By Richard W.M. Jones http://annexia.org/forth + This is PUBLIC DOMAIN (see public domain release statement below). + $Id: jonesforth.S,v 1.24 2007-09-23 20:06:00 rich Exp $ gcc -m32 -nostdlib -static -Wl,-Ttext,0 -o jonesforth jonesforth.S - +*/ + .set JONES_VERSION,24 +/* INTRODUCTION ---------------------------------------------------------------------- FORTH is one of those alien languages which most working programmers regard in the same @@ -59,8 +63,27 @@ http://wiki.laptop.org/go/Forth_Lessons + http://www.albany.net/~hello/simple.htm + Here is another "Why FORTH?" essay: http://www.jwdt.com/~paysan/why-forth.html + Discussion and criticism of this FORTH here: http://lambda-the-ultimate.org/node/2452 + + 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. + + PUBLIC DOMAIN ---------------------------------------------------------------------- + + I, the copyright holder of this work, hereby release it into the public domain. This applies worldwide. + + In case this is not legally possible, I grant any entity the right to use this work for any purpose, + without any conditions, unless such conditions are required by law. + SETTING UP ---------------------------------------------------------------------- Let's get a few housekeeping things out of the way. Firstly because I need to draw lots of @@ -69,6 +92,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 @@ -90,6 +122,14 @@ strings (or rather it used to, but the developers removed it!) so I've abused the syntax slightly to make things readable. Ignore these warnings. + If you want to run your own FORTH programs you can do: + + ./jonesforth < myprog.f + + If you want to load your own FORTH code and then continue reading user commands, you can do: + + cat myfunctions.f - | ./jonesforth + ASSEMBLER ---------------------------------------------------------------------- (You can just skip to the next section -- you don't need to be able to read assembler to @@ -120,24 +160,312 @@ Now the tutorial starts in earnest. - INDIRECT THREADED CODE ---------------------------------------------------------------------- + THE DICTIONARY ---------------------------------------------------------------------- + + In FORTH as you will know, functions are called "words", and 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 should 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 + i386 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 + + On a 16-bit machine like the ones which originally ran FORTH the savings are even greater - 33%. + + [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 i386 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. + 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 @@ -150,6 +478,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 calls 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 @@ -165,47 +571,77 @@ _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 + .set 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 +/* The user definitions area: space for user-defined words and general memory allocations. */ + .set USER_DEFS_SIZE,16384 .align 4096 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. - */ -#define F_IMMED 0x80 -#define F_HIDDEN 0x20 +/* Flags - these are discussed later. */ + .set F_IMMED,0x80 + .set F_HIDDEN,0x20 + .set F_LENMASK,0x1f // length mask // 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 @@ -217,14 +653,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 ends 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 @@ -236,24 +690,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 @@ -261,6 +709,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 @@ -300,21 +752,21 @@ var_\name : NEXT defcode "4+",2,,INCR4 - addl $4,(%esp) // increment top of stack + addl $4,(%esp) // add 4 to top of stack NEXT defcode "4-",2,,DECR4 - subl $4,(%esp) // decrement top of stack + subl $4,(%esp) // subtract 4 from top of stack 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 it from next word on stack NEXT defcode "*",1,,MUL @@ -360,6 +812,46 @@ var_\name : 1: pushl $0 NEXT + defcode "<",1,,LT + pop %eax + pop %ebx + cmp %eax,%ebx + jl 1f + pushl $0 + NEXT +1: pushl $1 + NEXT + + defcode ">",1,,GT + pop %eax + pop %ebx + cmp %eax,%ebx + jg 1f + pushl $0 + NEXT +1: pushl $1 + NEXT + + defcode "<=",2,,LE + pop %eax + pop %ebx + cmp %eax,%ebx + jle 1f + pushl $0 + NEXT +1: pushl $1 + NEXT + + defcode ">=",2,,GE + pop %eax + pop %ebx + cmp %eax,%ebx + jge 1f + pushl $0 + NEXT +1: pushl $1 + NEXT + defcode "0=",2,,ZEQU // top of stack equals 0? pop %eax test %eax,%eax @@ -369,6 +861,51 @@ var_\name : 1: pushl $1 NEXT + defcode "0<>",3,,ZNEQU // top of stack not 0? + pop %eax + test %eax,%eax + jnz 1f + pushl $0 + NEXT +1: pushl $1 + NEXT + + defcode "0<",2,,ZLT + pop %eax + test %eax,%eax + jl 1f + pushl $0 + NEXT +1: pushl $1 + NEXT + + defcode "0>",2,,ZGT + pop %eax + test %eax,%eax + jg 1f + pushl $0 + NEXT +1: pushl $1 + NEXT + + defcode "0<=",3,,ZLE + pop %eax + test %eax,%eax + jle 1f + pushl $0 + NEXT +1: pushl $1 + NEXT + + defcode "0>=",3,,ZGE + pop %eax + test %eax,%eax + jge 1f + pushl $0 + NEXT +1: pushl $1 + NEXT + defcode "AND",3,,AND pop %eax andl %eax,(%esp) @@ -379,20 +916,88 @@ var_\name : orl %eax,(%esp) NEXT - defcode "INVERT",6,,INVERT + defcode "XOR",3,,XOR + pop %eax + xorl %eax,(%esp) + NEXT + + 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. @@ -401,25 +1006,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 @@ -463,34 +1056,86 @@ 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 - // _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 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. + +*/ + 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 +/* + BUILT-IN CONSTANTS ---------------------------------------------------------------------- - defcode "DSP@",4,,DSPFETCH - mov %esp,%eax - push %eax - NEXT + It's also useful to expose a few constants to FORTH. When the word is executed it pushes a + constant value on the stack. - defcode "DSP!",4,,DSPSTORE - pop %esp + The built-in constants are: + + VERSION Is the current version of this FORTH. + R0 The address of the top of the return stack. + DOCOL Pointer to DOCOL. + F_IMMED The IMMEDIATE flag's actual value. + F_HIDDEN The HIDDEN flag's actual value. + F_LENMASK The length mask. +*/ + + .macro defconst name, namelen, flags=0, label, value + defcode \name,\namelen,\flags,\label + push $\value NEXT + .endm + + defconst "VERSION",7,,VERSION,JONES_VERSION + defconst "R0",2,,RZ,return_stack + defconst "DOCOL",5,,__DOCOL,DOCOL + defconst "F_IMMED",7,,__F_IMMED,F_IMMED + defconst "F_HIDDEN",8,,__F_HIDDEN,F_HIDDEN + defconst "F_LENMASK",9,,__F_LENMASK,F_LENMASK + +/* + 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 ">R",2,,TOR pop %eax // pop parameter stack into %eax @@ -514,13 +1159,55 @@ var_\name : lea 4(%ebp),%ebp // pop return stack and throw away NEXT -#include +/* + PARAMETER (DATA) STACK ---------------------------------------------------------------------- - defcode "KEY",3,,KEY - call _KEY - push %eax // push return value on 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 -_KEY: + + 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 of 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 + call _KEY + push %eax // push return value on stack + NEXT +_KEY: mov (currkey),%ebx cmp (bufftop),%ebx jge 1f @@ -548,6 +1235,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 @@ -568,6 +1261,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 @@ -609,15 +1329,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 @@ -642,9 +1361,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 @@ -664,6 +1390,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 and >DFA. + + 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 @@ -685,7 +1435,7 @@ _FIND: // this won't pick the word (the length will appear to be wrong). xor %eax,%eax movb 4(%edx),%al // %al = flags+length field - andb $(F_HIDDEN|0x1f),%al // %al = name length + andb $(F_HIDDEN|F_LENMASK),%al // %al = name length cmpb %cl,%al // Length is the same? jne 2f @@ -712,7 +1462,36 @@ _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). The standard FORTH + word >CFA turns a dictionary pointer into a codeword pointer. + + The example below shows the result of: + + 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. + + What does CFA stand for? My best guess is "Code Field Address". +*/ + + defcode ">CFA",4,,TCFA pop %edi call _TCFA push %edi @@ -722,31 +1501,200 @@ _TCFA: add $4,%edi // Skip link pointer. movb (%edi),%al // Load flags+len into %al. inc %edi // Skip flags+len byte. - andb $0x1f,%al // Just the length, not the flags. + andb $F_LENMASK,%al // Just the length, not the flags. add %eax,%edi // Skip the name. addl $3,%edi // The codeword is 4-byte aligned. 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 +/* + Related to >CFA is >DFA which takes a dictionary entry address as returned by FIND and + returns a pointer to the first data field. + + FIND returns a pointer to this + | >CFA converts it to a pointer to this + | | + | | >DFA converts it to a pointer to this + | | | + V V V + +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+ + | LINK | 6 | D | O | U | B | L | E | 0 | DOCOL | DUP | + | EXIT | + +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+ + + (Note to those following the source of FIG-FORTH / ciforth: My >DFA definition is + different from theirs, because they have an extra indirection). + + You can see that >DFA is easily defined in FORTH just by adding 4 to the result of >CFA. +*/ + + defword ">DFA",4,,TDFA + .int TCFA // >CFA (get code field address) + .int INCR4 // 4+ (add 4 to it to get to next word) + .int EXIT // EXIT (return from FORTH word) + +/* + 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 the words : (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 on 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 + pointers (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 runs each word as it looks them up. This is known as + immediate mode. - defcode ":",1,,COLON + The interesting stuff happens when STATE is non-zero -- compiling mode. In this mode the + interpreter appends the codeword pointer to user memory (the HERE variable points to the next + free byte of user memory). - // Get the word and create a dictionary entry header for it. + 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 -- just the header part -- 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, ... + + (4) .. and most importantly leave HERE pointing just after the new codeword. This is where + the interpreter will append codewords. + + (5) Set STATE to 1. This goes into compile mode so the interpreter starts appending codewords to + our partially-formed header. + + After : has run, our input is here: + + : DOUBLE DUP + ; + ^ + | + Next byte returned by KEY will be the 'D' character of DUP + + so the interpreter (now it's in compile mode, so I guess it's really the compiler) reads "DUP", + looks it up in the dictionary, 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 + + The issue is what happens next. Obviously what we _don't_ want to happen is that we + read ";" and compile it and go on compiling everything afterwards. + + At this point, FORTH uses a trick. Remember the length byte in the dictionary definition + isn't just a plain length byte, but can also contain flags. One flag is called the + IMMEDIATE flag (F_IMMED in this code). If a word in the dictionary is flagged as + IMMEDIATE then the interpreter runs it immediately _even if it's in compile mode_. + + This is how the word ; (SEMICOLON) works -- as a word flagged in the dictionary as IMMEDIATE. + And all it does is append the codeword for EXIT on to the current definition and switch + back to immediate mode (set STATE back to 0). Shortly we'll see the actual definition + of ; and we'll see that it's really a very simple definition, declared IMMEDIATE. + + After the interpreter reads ; and executes it 'immediately', we get this: + + +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+ + | LINK | 6 | D | O | U | B | L | E | 0 | DOCOL | DUP | + | EXIT | + +---------+---+---+---+---+---+---+---+---+------------+------------+------------+------------+ + len pad codeword ^ + | + HERE + + STATE is set to 0. + + And that's it, job done, our new definition is compiled, and we're back in immediate mode + just reading and executing words, perhaps including a call to test our new word DOUBLE. + + The only last wrinkle in this is that while our word was being compiled, it was in a + half-finished state. We certainly wouldn't want DOUBLE to be called somehow during + this time. There are several ways to stop this from happening, but in FORTH what we + do is flag the word with the HIDDEN flag (F_HIDDEN in this code) just while it is + being compiled. This prevents FIND from finding it, and thus in theory stops any + chance of it being called. + + The above explains how compiling, : (COLON) and ; (SEMICOLON) works and in a moment I'm + going to define them. The : (COLON) function can be made a little bit more general by writing + it in two parts. The first part, called CREATE, makes just the header: + + +-- Afterwards, HERE points here. + | + V + +---------+---+---+---+---+---+---+---+---+ + | LINK | 6 | D | O | U | B | L | E | 0 | + +---------+---+---+---+---+---+---+---+---+ + len pad + + and the second part, the actual definition of : (COLON), calls CREATE and appends the + DOCOL codeword, so leaving: + + +-- Afterwards, HERE points here. + | + V + +---------+---+---+---+---+---+---+---+---+------------+ + | LINK | 6 | D | O | U | B | L | E | 0 | DOCOL | + +---------+---+---+---+---+---+---+---+---+------------+ + len pad codeword + + CREATE is a standard FORTH word and the advantage of this split is that we can reuse it to + create other types of words (not just ones which contain code, but words which contain variables, + constants and other data). +*/ + + defcode "CREATE",6,,CREATE + + // Get the word. call _WORD // Returns %ecx = length, %edi = pointer to word. mov %edi,%ebx // %ebx = address of the word + // Link pointer. movl var_HERE,%edi // %edi is the address of the header movl var_LATEST,%eax // Get link pointer stosl // and store it in the header. + // Length byte and the word itself. mov %cl,%al // Get the length. - orb $F_HIDDEN,%al // Set the HIDDEN flag on this entry. stosb // Store the length/flags byte. push %esi mov %ebx,%esi // %esi = word @@ -755,19 +1703,35 @@ _TCFA: addl $3,%edi // Align to next 4 byte boundary. andl $~3,%edi - movl $DOCOL,%eax // The codeword for user-created words is always DOCOL (the interpreter) - stosl - - // Header built, so now update LATEST and HERE. - // We'll be compiling words and putting them HERE. + // Update LATEST and HERE. movl var_HERE,%eax movl %eax,var_LATEST movl %edi,var_HERE - - // And go into compile mode by setting STATE to 1. - movl $1,var_STATE NEXT +/* + Because I want to define : (COLON) in FORTH, not assembler, we need a few more FORTH words + to use. + + The first is , (COMMA) which is a standard FORTH word which appends a 32 bit integer to the user + data area pointed to by HERE, and adds 4 to HERE. So the action of , (COMMA) is: + + previous value of HERE + | + V + +---------+---+---+---+---+---+---+---+---+-- - - - - --+------------+ + | LINK | 6 | D | O | U | B | L | E | 0 | | | + +---------+---+---+---+---+---+---+---+---+-- - - - - --+------------+ + len pad ^ + | + new value of HERE + + and is whatever 32 bit integer was at the top of the stack. + + , (COMMA) is quite a fundamental operation when compiling. It is used to append codewords + to the current word that is being compiled. +*/ + defcode ",",1,,COMMA pop %eax // Code pointer to store. call _COMMA @@ -778,38 +1742,225 @@ _COMMA: movl %edi,var_HERE // Update HERE (incremented) ret - defcode "HIDDEN",6,,HIDDEN - call _HIDDEN +/* + Our definitions of : (COLON) and ; (SEMICOLON) will need to switch to and from compile mode. + + Immediate mode vs. compile mode is stored in the global variable STATE, and by updating this + variable we can switch between the two modes. + + For various reasons which may become apparent later, FORTH defines two standard words called + [ and ] (LBRAC and RBRAC) which switch between modes: + + Word Assembler Action Effect + [ LBRAC STATE := 0 Switch to immediate mode. + ] RBRAC STATE := 1 Switch to compile mode. + + [ (LBRAC) is an IMMEDIATE word. The reason is as follows: If we are in compile mode and the + interpreter saw [ then it would compile it rather than running it. We would never be able to + switch back to immediate mode! So we flag the word as IMMEDIATE so that even in compile mode + the word runs immediately, switching us back to immediate mode. +*/ + + defcode "[",1,F_IMMED,LBRAC + xor %eax,%eax + movl %eax,var_STATE // Set STATE to 0. 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 + defcode "]",1,,RBRAC + movl $1,var_STATE // Set STATE to 1. NEXT -_IMMEDIATE: + +/* + Now we can define : (COLON) using CREATE. It just calls CREATE, appends DOCOL (the codeword), sets + the word HIDDEN and goes into compile mode. +*/ + + defword ":",1,,COLON + .int CREATE // CREATE the dictionary entry / header + .int LIT, DOCOL, COMMA // Append DOCOL (the codeword). + .int HIDDEN // Make the word hidden (see below for definition). + .int RBRAC // Go into compile mode. + .int EXIT // Return from the function. + +/* + ; (SEMICOLON) is also elegantly simple. Notice the F_IMMED flag. +*/ + + defword ";",1,F_IMMED,SEMICOLON + .int LIT, EXIT, COMMA // Append EXIT (so the word will return). + .int HIDDEN // Toggle hidden flag -- unhide the word (see below for definition). + .int LBRAC // Go back to IMMEDIATE mode. + .int EXIT // Return from the function. + +/* + EXTENDING THE COMPILER ---------------------------------------------------------------------- + + Words flagged with IMMEDIATE (F_IMMED) aren't just for the FORTH compiler to use. You can define + your own IMMEDIATE words too, and this is a crucial aspect when extending basic FORTH, because + it allows you in effect to extend the compiler itself. Does gcc let you do that? + + Standard FORTH words like IF, WHILE, ." and so on are all written as extensions to the basic + compiler, and are all IMMEDIATE words. + + The IMMEDIATE word toggles the F_IMMED (IMMEDIATE flag) on the most recently defined word, + or on the current word if you call it in the middle of a definition. + + Typical usage is: + + : MYIMMEDWORD IMMEDIATE + ...definition... + ; + + but some FORTH programmers write this instead: + + : MYIMMEDWORD + ...definition... + ; IMMEDIATE + + The two usages are equivalent, to a first approximation. +*/ + + defcode "IMMEDIATE",9,F_IMMED,IMMEDIATE movl var_LATEST,%edi // LATEST word. addl $4,%edi // Point to name/flags byte. xorb $F_IMMED,(%edi) // Toggle the IMMED bit. - ret + NEXT + +/* + HIDDEN toggles the other flag, F_HIDDEN, of the latest word. Note that words flagged + as hidden are defined but cannot be called, so this is only used when you are trying to + hide the word as it is being defined. +*/ - 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 + movl var_LATEST,%edi // LATEST word. + addl $4,%edi // Point to name/flags byte. + xorb $F_HIDDEN,(%edi) // Toggle the HIDDEN bit. NEXT -/* This definiton of ' (TICK) is strictly cheating - it also only works in compiled code. */ +/* + ' (TICK) is a standard FORTH word which returns the codeword pointer of the next word. + + The common usage is: + + ' FOO , + + which appends the codeword of FOO to the current word we are defining (this only works in compiled code). + + You tend to use ' in IMMEDIATE words. For example an alternate (and rather useless) way to define + a literal 2 might be: + + : LIT2 IMMEDIATE + ' LIT , \ Appends LIT to the currently-being-defined word + 2 , \ Appends the number 2 to the currently-being-defined word + ; + + So you could do: + + : DOUBLE LIT2 * ; + + (If you don't understand how LIT2 works, then you should review the material about compiling words + and immediate mode). + + This definition of ' uses a cheat which I copied from buzzard92. As a result it only works in + compiled code. It is possible to write a version of ' based on WORD, FIND, >CFA which works in + immediate mode too. +*/ defcode "'",1,,TICK lodsl // Get the address of the next word and skip it. pushl %eax // Push it on the stack. NEXT +/* + BRANCHING ---------------------------------------------------------------------- + + It turns out that all you need in order to define looping constructs, IF-statements, etc. + are two primitives. + + BRANCH is an unconditional branch. 0BRANCH is a conditional branch (it only branches if the + top of stack is zero). + + The diagram below shows how BRANCH works in some imaginary compiled word. When BRANCH executes, + %esi starts by pointing to the offset field (compare to LIT above): + + +---------------------+-------+---- - - ---+------------+------------+---- - - - ----+------------+ + | (Dictionary header) | DOCOL | | BRANCH | offset | (skipped) | word | + +---------------------+-------+---- - - ---+------------+-----|------+---- - - - ----+------------+ + ^ | ^ + | | | + | +-----------------------+ + %esi added to offset + + The offset is added to %esi to make the new %esi, and the result is that when NEXT runs, execution + continues at the branch target. Negative offsets work as expected. + + 0BRANCH is the same except the branch happens conditionally. + + Now standard FORTH words such as IF, THEN, ELSE, WHILE, REPEAT, etc. can be implemented entirely + in FORTH. They are IMMEDIATE words which append various combinations of BRANCH or 0BRANCH + into the word currently being compiled. + + As an example, code written like this: + + condition-code IF true-part THEN rest-code + + compiles to: + + condition-code 0BRANCH OFFSET true-part rest-code + | ^ + | | + +-------------+ +*/ + + 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 + +/* + PRINTING STRINGS ---------------------------------------------------------------------- + + LITSTRING and EMITSTRING are primitives used to implement the ." operator (which is + written in FORTH). See the definition of that operator below. +*/ + + 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 START AND INTERPRETER ---------------------------------------------------------------------- + + COLD is the first FORTH function called, almost immediately after the FORTH system "boots". + + INTERPRETER is the FORTH interpreter ("toploop", "toplevel" or "REPL" might be a more accurate + description -- see: http://en.wikipedia.org/wiki/REPL). +*/ + + // 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! */ @@ -876,25 +2027,69 @@ _IMMEDIATE: interpret_is_lit: .int 0 // Flag used to record if reading a literal +/* + ODDS AND ENDS ---------------------------------------------------------------------- + + CHAR puts the ASCII code of the first character of the following word on the stack. For example + CHAR A puts 65 on the stack. + + SYSEXIT exits the process using Linux exit syscall. + + In this FORTH, SYSEXIT must be the last word in the built-in (assembler) dictionary because we + initialise the LATEST variable to point to it. This means that if you want to extend the assembler + part, you must put new words before SYSEXIT, or else change how LATEST is initialised. +*/ + + 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 + // NB: SYSEXIT must be the last entry in the built-in dictionary. defcode SYSEXIT,7,,SYSEXIT pop %ebx mov $__NR_exit,%eax int $0x80 -/*---------------------------------------------------------------------- - * Input buffer & initial input. - */ +/* + START OF FORTH CODE ---------------------------------------------------------------------- + + We've now reached the stage where the FORTH system is running and self-hosting. All further + words can be written as FORTH itself, including words like IF, THEN, .", etc which in most + languages would be considered rather fundamental. + + As a kind of trick, I prefill the input buffer with the initial FORTH code. Once this code + has run (when we get to the "OK" prompt), this input buffer is reused for reading any further + user input. + + Some notes about the code: + + \ (backslash) is the FORTH way to start a comment which goes up to the next newline. However + because this is a C-style string, I have to escape the backslash, which is why they appear as + \\ comment. + + Similarly, any backslashes in the code are doubled, and " becomes \" (eg. the definition of ." + is written as : .\" ... ;) + + I use indenting to show structure. The amount of whitespace has no meaning to FORTH however + except that you must use at least one whitespace character between words, and words themselves + cannot contain whitespace. + + FORTH is case-sensitive. Use capslock! + + Enjoy! +*/ + .data .align 4096 buffer: - // XXX gives 'Warning: unterminated string; newline inserted' messages which you can ignore + // Multi-line constant gives 'Warning: unterminated string; newline inserted' messages which you can ignore. .ascii "\ \\ Define some character constants : '\\n' 10 ; : 'SPACE' 32 ; -: '\"' 34 ; -: ':' 58 ; \\ CR prints a carriage return : CR '\\n' EMIT ; @@ -902,10 +2097,6 @@ buffer: \\ SPACE prints a space : SPACE 'SPACE' EMIT ; -\\ Primitive . (DOT) function doesn't follow with a blank, so redefine it to behave like FORTH. -\\ Notice how we can trivially redefine existing functions. -: . . SPACE ; - \\ DUP, DROP are defined in assembly for speed, but this is how you might define them \\ in FORTH. Notice use of the scratch variables _X and _Y. \\ : DUP _X ! _X @ _X @ ; @@ -920,14 +2111,12 @@ buffer: : 2* 2 * ; : 2/ 2 / ; -\\ [ and ] allow you to break into immediate mode while compiling a word. -: [ IMMEDIATE \\ define [ as an immediate word - 0 STATE ! \\ go into immediate mode - ; - -: ] - 1 STATE ! \\ go back to compile mode - ; +\\ The primitive . (DOT) function doesn't follow with a blank, so redefine it to behave like FORTH. +\\ Notice how we can trivially redefine existing words. Word definitions are not recursive by +\\ default, but see below for the RECURSE word. +: . + . SPACE \\ call built-in DOT, then print a space. +; \\ LITERAL takes whatever is on the stack and compiles LIT : LITERAL IMMEDIATE @@ -935,14 +2124,35 @@ buffer: , \\ compile the literal itself (from the stack) ; +\\ Now we can use [ and ] to insert literals which are calculated at compile time. +\\ Within definitions, use [ ... ] LITERAL anywhere that '...' is a constant expression which you +\\ would rather only compute once (at compile time, rather than calculating it each time your word runs). +: ':' + [ \\ go into immediate mode temporarily + CHAR : \\ push the number 58 (ASCII code of colon) on the stack + ] \\ go back to compile mode + LITERAL \\ compile LIT 58 as the definition of ':' word +; + +\\ A few more character constants defined the same way as above. +: '(' [ CHAR ( ] LITERAL ; +: ')' [ CHAR ) ] LITERAL ; +: '\"' [ CHAR \" ] LITERAL ; + +\\ So far we have defined only very simple definitions. Before we can go further, we really need to +\\ make some control structures, like IF ... THEN and loops. Luckily we can define arbitrary control +\\ structures directly in FORTH. +\\ +\\ Please note that the control structures as I have defined them here will only work inside compiled +\\ words. If you try to type in expressions using IF, etc. in immediate mode, then they won't work. +\\ Making these work in immediate mode is left as an exercise for the reader. + \\ condition IF true-part THEN rest -\\ compiles to: -\\ condition 0BRANCH OFFSET true-part rest -\\ where OFFSET is the offset of 'rest' +\\ -- compiles to: --> condition 0BRANCH OFFSET true-part rest +\\ where OFFSET is the offset of 'rest' \\ condition IF true-part ELSE false-part THEN -\\ compiles to: -\\ condition 0BRANCH OFFSET true-part BRANCH OFFSET2 false-part rest -\\ where OFFSET if the offset of false-part and OFFSET2 is the offset of rest +\\ -- compiles to: --> condition 0BRANCH OFFSET true-part BRANCH OFFSET2 false-part rest +\\ where OFFSET if the offset of false-part and OFFSET2 is the offset of rest \\ IF is an IMMEDIATE word which compiles 0BRANCH followed by a dummy offset, and places \\ the address of the 0BRANCH on the stack. Later when we see THEN, we pop that address @@ -970,9 +2180,8 @@ buffer: ; \\ BEGIN loop-part condition UNTIL -\\ compiles to: -\\ loop-part condition 0BRANCH OFFSET -\\ where OFFSET points back to the loop-part +\\ -- compiles to: --> loop-part condition 0BRANCH OFFSET +\\ where OFFSET points back to the loop-part \\ This is like do { loop-part } while (condition) in the C language : BEGIN IMMEDIATE HERE @ \\ save location on the stack @@ -985,9 +2194,8 @@ buffer: ; \\ BEGIN loop-part AGAIN -\\ compiles to: -\\ loop-part BRANCH OFFSET -\\ where OFFSET points back to the loop-part +\\ -- compiles to: --> loop-part BRANCH OFFSET +\\ where OFFSET points back to the loop-part \\ In other words, an infinite loop which can only be returned from with EXIT : AGAIN IMMEDIATE ' BRANCH , \\ compile BRANCH @@ -996,9 +2204,8 @@ buffer: ; \\ BEGIN condition WHILE loop-part REPEAT -\\ compiles to: -\\ condition 0BRANCH OFFSET2 loop-part BRANCH OFFSET -\\ where OFFSET points back to condition (the beginning) and OFFSET2 points to after the whole piece of code +\\ -- compiles to: --> condition 0BRANCH OFFSET2 loop-part BRANCH OFFSET +\\ where OFFSET points back to condition (the beginning) and OFFSET2 points to after the whole piece of code \\ So this is like a while (condition) { loop-part } loop in the C language : WHILE IMMEDIATE ' 0BRANCH , \\ compile 0BRANCH @@ -1015,97 +2222,385 @@ buffer: SWAP ! \\ and back-fill it in the original location ; -\\ With the looping constructs, we can now write SPACES, which writes n spaces to stdout. -: SPACES +\\ FORTH allows ( ... ) as comments within function definitions. This works by having an IMMEDIATE +\\ word called ( which just drops input characters until it hits the corresponding ). +: ( IMMEDIATE + 1 \\ allowed nested parens by keeping track of depth BEGIN - SPACE \\ print a space - 1- \\ until we count down to 0 - DUP 0= - UNTIL + KEY \\ read next character + DUP '(' = IF \\ open paren? + DROP \\ drop the open paren + 1+ \\ depth increases + ELSE + ')' = IF \\ close paren? + 1- \\ depth decreases + THEN + THEN + DUP 0= UNTIL \\ continue until we reach matching close paren, depth 0 + DROP \\ drop the depth counter ; -\\ .S prints the contents of the stack. Very useful for debugging. -: .S - DSP@ \\ get current stack pointer +( + From now on we can use ( ... ) for comments. + + In FORTH style we can also use ( ... -- ... ) to show the effects that a word has on the + parameter stack. For example: + + ( n -- ) means that the word consumes an integer (n) from the parameter stack. + ( b a -- c ) means that the word uses two integers (a and b, where a is at the top of stack) + and returns a single integer (c). + ( -- ) means the word has no effect on the stack +) + +( With the looping constructs, we can now write SPACES, which writes n spaces to stdout. ) +: SPACES ( n -- ) BEGIN - DUP @ . \\ print the stack element - 4+ \\ move up - DUP S0 @ 4- = \\ stop when we get to the top - UNTIL + DUP 0> ( while n > 0 ) + WHILE + SPACE ( print a space ) + 1- ( until we count down to 0 ) + REPEAT DROP ; -\\ DEPTH returns the depth of the stack. -: DEPTH S0 @ DSP@ - ; - -\\ .\" is the print string operator in FORTH. Example: .\" Something to print\" -\\ The space after the operator is the ordinary space required between words. -\\ This is tricky to define because it has to do different things depending on whether -\\ we are compiling or in immediate mode. (Thus the word is marked IMMEDIATE so it can -\\ detect this and do different things). -\\ In immediate mode we just keep reading characters and printing them until we get to -\\ the next double quote. -\\ In compile mode we have the problem of where we're going to store the string (remember -\\ that the input buffer where the string comes from may be overwritten by the time we -\\ come round to running the function). We store the string in the compiled function -\\ like this: -\\ LITSTRING, string length, string rounded up to 4 bytes, EMITSTRING, ... -: .\" IMMEDIATE - STATE @ \\ compiling? - IF - ' LITSTRING , \\ compile LITSTRING - HERE @ \\ save the address of the length word on the stack - 0 , \\ dummy length - we don't know what it is yet +( .S prints the contents of the stack. Very useful for debugging. ) +: .S ( -- ) + DSP@ ( get current stack pointer ) + BEGIN + DUP S0 @ < + WHILE + DUP @ . ( print the stack element ) + 4+ ( move up ) + REPEAT + DROP +; + +( DEPTH returns the depth of the stack. ) +: DEPTH ( -- n ) + S0 @ DSP@ - + 4- ( adjust because S0 was on the stack when we pushed DSP ) +; + +( + [NB. The following may be a bit confusing because of the need to use backslash before + each double quote character. The backslashes are there to keep the assembler happy. + They are NOT part of the final output. So here we are defining a function called + 'dot double-quote' (not 'dot backslash double-quote').] + + .\" is the print string operator in FORTH. Example: .\" Something to print\" + The space after the operator is the ordinary space required between words. + + This is tricky to define because it has to do different things depending on whether + we are compiling or in immediate mode. (Thus the word is marked IMMEDIATE so it can + detect this and do different things). + + In immediate mode we just keep reading characters and printing them until we get to + the next double quote. + + In compile mode we have the problem of where we're going to store the string (remember + that the input buffer where the string comes from may be overwritten by the time we + come round to running the function). We store the string in the compiled function + like this: + ..., LITSTRING, string length, string rounded up to 4 bytes, EMITSTRING, ... +) +: .\" IMMEDIATE ( -- ) + STATE @ IF ( compiling? ) + ' LITSTRING , ( compile LITSTRING ) + HERE @ ( save the address of the length word on the stack ) + 0 , ( dummy length - we don't know what it is yet ) BEGIN - KEY \\ get next character of the string + KEY ( get next character of the string ) DUP '\"' <> WHILE - HERE @ !b \\ store the character in the compiled image - 1 HERE +! \\ increment HERE pointer by 1 byte + HERE @ !b ( store the character in the compiled image ) + 1 HERE +! ( increment HERE pointer by 1 byte ) REPEAT - DROP \\ drop the double quote character at the end - DUP \\ get the saved address of the length word - HERE @ SWAP - \\ calculate the length - 4- \\ subtract 4 (because we measured from the start of the length word) - SWAP ! \\ and back-fill the length location - HERE @ \\ round up to next multiple of 4 bytes for the remaining code + DROP ( drop the double quote character at the end ) + DUP ( get the saved address of the length word ) + HERE @ SWAP - ( calculate the length ) + 4- ( subtract 4 (because we measured from the start of the length word) ) + SWAP ! ( and back-fill the length location ) + HERE @ ( round up to next multiple of 4 bytes for the remaining code ) 3 + 3 INVERT AND HERE ! - ' EMITSTRING , \\ compile the final EMITSTRING + ' EMITSTRING , ( compile the final EMITSTRING ) ELSE - \\ In immediate mode, just read characters and print them until we get - \\ to the ending double quote. Much simpler than the above code! + ( In immediate mode, just read characters and print them until we get + to the ending double quote. Much simpler than the above code! ) BEGIN KEY - DUP '\"' = IF EXIT THEN + DUP '\"' = IF + DROP ( drop the double quote character ) + EXIT ( return from this function ) + THEN EMIT AGAIN THEN ; -\\ While compiling, [COMPILE] WORD compiles WORD if it would otherwise be IMMEDIATE. -: [COMPILE] IMMEDIATE - WORD \\ get the next word - FIND \\ find it in the dictionary - >CFA \\ get its codeword - , \\ and compile that +( + In FORTH, global constants and variables are defined like this: + + 10 CONSTANT TEN when TEN is executed, it leaves the integer 10 on the stack + VARIABLE VAR when VAR is executed, it leaves the address of VAR on the stack + + Constants can be read by not written, eg: + + TEN . CR prints 10 + + You can read a variable (in this example called VAR) by doing: + + VAR @ leaves the value of VAR on the stack + VAR @ . CR prints the value of VAR + + and update the variable by doing: + + 20 VAR ! sets VAR to 20 + + Note that variables are uninitialised (but see VALUE later on which provides initialised + variables with a slightly simpler syntax). + + How can we define the words CONSTANT and VARIABLE? + + The trick is to define a new word for the variable itself (eg. if the variable was called + 'VAR' then we would define a new word called VAR). This is easy to do because we exposed + dictionary entry creation through the CREATE word (part of the definition of : above). + A call to CREATE TEN leaves the dictionary entry: + + +--- HERE + | + V + +---------+---+---+---+---+ + | LINK | 3 | T | E | N | + +---------+---+---+---+---+ + len + + For CONSTANT we can continue by appending DOCOL (the codeword), then LIT followed by + the constant itself and then EXIT, forming a little word definition that returns the + constant: + + +---------+---+---+---+---+------------+------------+------------+------------+ + | LINK | 3 | T | E | N | DOCOL | LIT | 10 | EXIT | + +---------+---+---+---+---+------------+------------+------------+------------+ + len codeword + + Notice that this word definition is exactly the same as you would have got if you had + written : TEN 10 ; +) +: CONSTANT + CREATE ( make the dictionary entry (the name follows CONSTANT) ) + DOCOL , ( append DOCOL (the codeword field of this word) ) + ' LIT , ( append the codeword LIT ) + , ( append the value on the top of the stack ) + ' EXIT , ( append the codeword EXIT ) ; -\\ RECURSE makes a recursive call to the current word that is being compiled. -\\ Normally while a word is being compiled, it is marked HIDDEN so that references to the -\\ same word within are calls to the previous definition of the word. -: RECURSE IMMEDIATE - LATEST @ >CFA \\ LATEST points to the word being compiled at the moment - , \\ compile it +( + VARIABLE is a little bit harder because we need somewhere to put the variable. There is + nothing particularly special about the 'user definitions area' (the area of memory pointed + to by HERE where we have previously just stored new word definitions). We can slice off + bits of this memory area to store anything we want, so one possible definition of + VARIABLE might create this: + + +--------------------------------------------------------------+ + | | + V | + +---------+---------+---+---+---+---+------------+------------+---|--------+------------+ + | | LINK | 3 | V | A | R | DOCOL | LIT | | EXIT | + +---------+---------+---+---+---+---+------------+------------+------------+------------+ + len codeword + + where is the place to store the variable, and points back to it. + + To make this more general let's define a couple of words which we can use to allocate + arbitrary memory from the user definitions area. + + First ALLOT, where n ALLOT allocates n bytes of memory. (Note when calling this that + it's a very good idea to make sure that n is a multiple of 4, or at least that next time + a word is compiled that n has been left as a multiple of 4). +) +: ALLOT ( n -- addr ) + HERE @ SWAP ( here n -- ) + HERE +! ( adds n to HERE, after this the old value of HERE is still on the stack ) +; + +( + Second, CELLS. In FORTH the phrase 'n CELLS ALLOT' means allocate n integers of whatever size + is the natural size for integers on this machine architecture. On this 32 bit machine therefore + CELLS just multiplies the top of stack by 4. +) +: CELLS 4 * ; + +( + So now we can define VARIABLE easily in much the same way as CONSTANT above. Refer to the + diagram above to see what the word that this creates will look like. +) +: VARIABLE + 1 CELLS ALLOT ( allocate 1 cell of memory, push the pointer to this memory ) + CREATE ( make the dictionary entry (the name follows VARIABLE) ) + DOCOL , ( append DOCOL (the codeword field of this word) ) + ' LIT , ( append the codeword LIT ) + , ( append the pointer to the new memory ) + ' EXIT , ( append the codeword EXIT ) +; + +( + VALUEs are like VARIABLEs but with a simpler syntax. You would generally use them when you + want a variable which is read often, and written infrequently. + + 20 VALUE VAL creates VAL with initial value 20 + VAL pushes the value directly on the stack + 30 TO VAL updates VAL, setting it to 30 + + Notice that 'VAL' on its own doesn't return the address of the value, but the value itself, + making values simpler and more obvious to use than variables (no indirection through '@'). + The price is a more complicated implementation, although despite the complexity there is no + particular performance penalty at runtime. + + A naive implementation of 'TO' would be quite slow, involving a dictionary search each time. + But because this is FORTH we have complete control of the compiler so we can compile TO more + efficiently, turning: + TO VAL + into: + LIT ! + and calculating (the address of the value) at compile time. + + Now this is the clever bit. We'll compile our value like this: + + +---------+---+---+---+---+------------+------------+------------+------------+ + | LINK | 3 | V | A | L | DOCOL | LIT | | EXIT | + +---------+---+---+---+---+------------+------------+------------+------------+ + len codeword + + where is the actual value itself. Note that when VAL executes, it will push the + value on the stack, which is what we want. + + But what will TO use for the address ? Why of course a pointer to that : + + code compiled - - - - --+------------+------------+------------+-- - - - - + by TO VAL | LIT | | ! | + - - - - --+------------+-----|------+------------+-- - - - - + | + V + +---------+---+---+---+---+------------+------------+------------+------------+ + | LINK | 3 | V | A | L | DOCOL | LIT | | EXIT | + +---------+---+---+---+---+------------+------------+------------+------------+ + len codeword + + In other words, this is a kind of self-modifying code. + + (Note to the people who want to modify this FORTH to add inlining: values defined this + way cannot be inlined). +) +: VALUE ( n -- ) + CREATE ( make the dictionary entry (the name follows VALUE) ) + DOCOL , ( append DOCOL ) + ' LIT , ( append the codeword LIT ) + , ( append the initial value ) + ' EXIT , ( append the codeword EXIT ) +; + +: TO IMMEDIATE ( n -- ) + WORD ( get the name of the value ) + FIND ( look it up in the dictionary ) + >DFA ( get a pointer to the first data field (the 'LIT') ) + 4+ ( increment to point at the value ) + STATE @ IF ( compiling? ) + ' LIT , ( compile LIT ) + , ( compile the address of the value ) + ' ! , ( compile ! ) + ELSE ( immediate mode ) + ! ( update it straightaway ) + THEN +; + +( + ID. takes an address of a dictionary entry and prints the word's name. + + For example: LATEST @ ID. would print the name of the last word that was defined. +) +: ID. + 4+ ( skip over the link pointer ) + DUP @b ( get the flags/length byte ) + F_LENMASK AND ( mask out the flags - just want the length ) + + BEGIN + DUP 0> ( length > 0? ) + WHILE + SWAP 1+ ( addr len -- len addr+1 ) + DUP @b ( len addr -- len addr char | get the next character) + EMIT ( len addr char -- len addr | and print it) + SWAP 1- ( len addr -- addr len-1 | subtract one from length ) + REPEAT + DROP DROP ( len addr -- ) +; + +( + WORDS prints all the words defined in the dictionary, starting with the word defined most recently. + + The implementation simply iterates backwards from LATEST using the link pointers. +) +: WORDS + LATEST @ ( start at LATEST dictionary entry ) + BEGIN + DUP 0<> ( while link pointer is not null ) + WHILE + DUP ID. ( print the word ) + SPACE + @ ( dereference the link pointer - go to previous word ) + REPEAT + DROP + CR +; + +( + So far we have only allocated words and memory. FORTH provides a rather primitive method + to deallocate. + + 'FORGET word' deletes the definition of 'word' from the dictionary and everything defined + after it, including any variables and other memory allocated after. + + The implementation is very simple - we look up the word (which returns the dictionary entry + address). Then we set HERE to point to that address, so in effect all future allocations + and definitions will overwrite memory starting at the word. We also need to set LATEST to + point to the previous word. + + Note that you cannot FORGET built-in words (well, you can try but it will probably cause + a segfault). + + XXX: Because we wrote VARIABLE to store the variable in memory allocated before the word, + in the current implementation VARIABLE FOO FORGET FOO will leak 1 cell of memory. +) +: FORGET + WORD FIND ( find the word, gets the dictionary entry address ) + DUP @ LATEST ! ( set LATEST to point to the previous word ) + HERE ! ( and store HERE with the dictionary address ) ; -\\ ALLOT is used to allocate (static) memory when compiling. It increases HERE by -\\ the amount given on the stack. -: ALLOT HERE +! ; +( While compiling, '[COMPILE] word' compiles 'word' if it would otherwise be IMMEDIATE. ) +: [COMPILE] IMMEDIATE + WORD ( get the next word ) + FIND ( find it in the dictionary ) + >CFA ( get its codeword ) + , ( and compile that ) +; +( + RECURSE makes a recursive call to the current word that is being compiled. -\\ Finally print the welcome prompt. + Normally while a word is being compiled, it is marked HIDDEN so that references to the + same word within are calls to the previous definition of the word. However we still have + access to the word which we are currently compiling through the LATEST pointer so we + can use that to compile a recursive call. +) +: RECURSE IMMEDIATE + LATEST @ >CFA ( LATEST points to the word being compiled at the moment ) + , ( compile it ) +; + +( Finally print the welcome prompt. ) +.\" JONESFORTH VERSION \" VERSION . CR .\" OK \" " @@ -1117,3 +2612,5 @@ currkey: .int buffer bufftop: .int _initbufftop + +/* END OF jonesforth.S */