X-Git-Url: https://git.rrq.au/?a=blobdiff_plain;f=jonesforth.S;h=40be7d7e8869ff6a4e476261b0d712a71f35f9dd;hb=d82cc200f49729ea1708975c8f061529a69f997e;hp=4277547e95f76aed79244fd108fb2008a0d56991;hpb=a7db9b5e5c3a2f025463bf84d6701b7892e2e319;p=rrq%2Fjonesforth.git diff --git a/jonesforth.S b/jonesforth.S index 4277547..40be7d7 100644 --- a/jonesforth.S +++ b/jonesforth.S @@ -1,20 +1,274 @@ -/* A sometimes minimal FORTH interpreter for Linux / i386 systems. -*- asm -*- - * By Richard W.M. Jones - * - * gcc -m32 -nostdlib -static -Wl,-Ttext,0 -o jonesforth jonesforth.S - */ +/* A sometimes minimal FORTH compiler and tutorial for Linux / i386 systems. -*- asm -*- + By Richard W.M. Jones http://annexia.org/forth -#include + gcc -m32 -nostdlib -static -Wl,-Ttext,0 -o jonesforth jonesforth.S + + INTRODUCTION ---------------------------------------------------------------------- + + FORTH is one of those alien languages which most working programmers regard in the same + way as Haskell, LISP, and so on. Something so strange that they'd rather any thoughts + of it just go away so they can get on with writing this paying code. But that's wrong + and if you care at all about programming then you should at least understand all these + languages, even if you will never use them. + + LISP is the ultimate high-level language, and features from LISP are being added every + decade to the more common languages. But FORTH is in some ways the ultimate in low level + programming. Out of the box it lacks features like dynamic memory management and even + strings. In fact, at its primitive level it lacks even basic concepts like IF-statements + and loops. + + Why then would you want to learn FORTH? There are several very good reasons. First + and foremost, FORTH is minimal. You really can write a complete FORTH in, say, 2000 + lines of code. I don't just mean a FORTH program, I mean a complete FORTH operating + system, environment and language. You could boot such a FORTH on a bare PC and it would + come up with a prompt where you could start doing useful work. The FORTH you have here + isn't minimal and uses a Linux process as its 'base PC' (both for the purposes of making + it a good tutorial). It's possible to completely understand the system. Who can say they + completely understand how Linux works, or gcc? + + Secondly FORTH has a peculiar bootstrapping property. By that I mean that after writing + a little bit of assembly to talk to the hardware and implement a few primitives, all the + rest of the language and compiler is written in FORTH itself. Remember I said before + that FORTH lacked IF-statements and loops? Well of course it doesn't really because + such a lanuage would be useless, but my point was rather that IF-statements and loops are + written in FORTH itself. + + Now of course this is common in other languages as well, and in those languages we call + them 'libraries'. For example in C, 'printf' is a library function written in C. But + in FORTH this goes way beyond mere libraries. Can you imagine writing C's 'if' in C? + And that brings me to my third reason: If you can write 'if' in FORTH, then why restrict + yourself to the usual if/while/for/switch constructs? You want a construct that iterates + over every other element in a list of numbers? You can add it to the language. What + about an operator which pulls in variables directly from a configuration file and makes + them available as FORTH variables? Or how about adding Makefile-like dependencies to + the language? No problem in FORTH. This concept isn't common in programming languages, + but it has a name (in fact two names): "macros" (by which I mean LISP-style macros, not + the lame C preprocessor) and "domain specific languages" (DSLs). + + This tutorial isn't about learning FORTH as the language. I'll point you to some references + you should read if you're not familiar with using FORTH. This tutorial is about how to + write FORTH. In fact, until you understand how FORTH is written, you'll have only a very + superficial understanding of how to use it. + + So if you're not familiar with FORTH or want to refresh your memory here are some online + references to read: + + http://en.wikipedia.org/wiki/Forth_%28programming_language%29 + + http://galileo.phys.virginia.edu/classes/551.jvn.fall01/primer.htm + + http://wiki.laptop.org/go/Forth_Lessons + + Here is another "Why FORTH?" essay: http://www.jwdt.com/~paysan/why-forth.html + + ACKNOWLEDGEMENTS ---------------------------------------------------------------------- + + This code draws heavily on the design of LINA FORTH (http://home.hccnet.nl/a.w.m.van.der.horst/lina.html) + by Albert van der Horst. Any similarities in the code are probably not accidental. + + SETTING UP ---------------------------------------------------------------------- + + Let's get a few housekeeping things out of the way. Firstly because I need to draw lots of + ASCII-art diagrams to explain concepts, the best way to look at this is using a window which + uses a fixed width font and is at least this wide: + + <------------------------------------------------------------------------------------------------------------------------> + + 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 + i386. Linux because instead of programming directly to the hardware on a bare PC which I + could have done, I went for a simpler tutorial by assuming that the 'hardware' is a Linux + process with a few basic system calls (read, write and exit and that's about all). i386 + is needed because I had to write the assembly for a processor, and i386 is by far the most + common. (Of course when I say 'i386', any 32- or 64-bit x86 processor will do. I'm compiling + this on a 64 bit AMD Opteron). + + Again, to assemble this you will need gcc and gas (the GNU assembler). The commands to + assemble and run the code (save this file as 'jonesforth.S') are: + + gcc -m32 -nostdlib -static -Wl,-Ttext,0 -o jonesforth jonesforth.S + ./jonesforth + + You will see lots of 'Warning: unterminated string; newline inserted' messages from the + assembler. That's just because the GNU assembler doesn't have a good syntax for multi-line + 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. + + ASSEMBLER ---------------------------------------------------------------------- + + (You can just skip to the next section -- you don't need to be able to read assembler to + follow this tutorial). + + However if you do want to read the assembly code here are a few notes about gas (the GNU assembler): + + (1) Register names are prefixed with '%', so %eax is the 32 bit i386 accumulator. The registers + available on i386 are: %eax, %ebx, %ecx, %edx, %esi, %edi, %ebp and %esp, and most of them + have special purposes. + + (2) Add, mov, etc. take arguments in the form SRC,DEST. So mov %eax,%ecx moves %eax -> %ecx + + (3) Constants are prefixed with '$', and you mustn't forget it! If you forget it then it + causes a read from memory instead, so: + mov $2,%eax moves number 2 into %eax + mov 2,%eax reads the 32 bit word from address 2 into %eax (ie. most likely a mistake) + + (4) gas has a funky syntax for local labels, where '1f' (etc.) means label '1:' "forwards" + and '1b' (etc.) means label '1:' "backwards". + + (5) 'ja' is "jump if above", 'jb' for "jump if below", 'je' "jump if equal" etc. + + (6) gas has a reasonably nice .macro syntax, and I use them a lot to make the code shorter and + less repetitive. + + For more help reading the assembler, do "info gas" at the Linux prompt. + + Now the tutorial starts in earnest. + + THE DICTIONARY ---------------------------------------------------------------------- -/* NOTES------------------------------------------------------------------------------------------------------------------- + In FORTH as you will know, functions are called "words", as just as in other languages they + have a name and a definition. Here are two FORTH words: -Need to say something about $ before constants. + : DOUBLE DUP + ; \ name is "DOUBLE", definition is "DUP +" + : QUADRUPLE DOUBLE DOUBLE ; \ name is "QUADRUPLE", definition is "DOUBLE DOUBLE" -And about je/jne/ja/jb/jbe/etc + Words, both built-in ones and ones which the programmer defines later, are stored in a dictionary + which is just a linked list of dictionary entries. + <--- DICTIONARY ENTRY (HEADER) -----------------------> + +------------------------+--------+---------- - - - - +----------- - - - - + | LINK POINTER | LENGTH/| NAME | DEFINITION + | | FLAGS | | + +--- (4 bytes) ----------+- byte -+- n bytes - - - - +----------- - - - - + I'll come to the definition of the word later. For now just look at the header. The first + 4 bytes are the link pointer. This points back to the previous word in the dictionary, or, for + the first word in the dictionary it is just a NULL pointer. Then comes a length/flags byte. + The length of the word can be up to 31 characters (5 bits used) and the top three bits are used + for various flags which I'll come to later. This is followed by the name itself, and in this + implementation the name is rounded up to a multiple of 4 bytes by padding it with zero bytes. + That's just to ensure that the definition starts on a 32 bit boundary. + A FORTH variable called LATEST contains a pointer to the most recently defined word, in + other words, the head of this linked list. + DOUBLE and QUADRUPLE might look like this: + + pointer to previous word + ^ + | + +--|------+---+---+---+---+---+---+---+---+------------- - - - - + | LINK | 6 | D | O | U | B | L | E | 0 | (definition ...) + +---------+---+---+---+---+---+---+---+---+------------- - - - - + ^ len padding + | + +--|------+---+---+---+---+---+---+---+---+---+---+---+---+------------- - - - - + | LINK | 9 | Q | U | A | D | R | U | P | L | E | 0 | 0 | (definition ...) + +---------+---+---+---+---+---+---+---+---+---+---+---+---+------------- - - - - + ^ len padding + | + | + LATEST + + You shoud be able to see from this how you might implement functions to find a word in + the dictionary (just walk along the dictionary entries starting at LATEST and matching + the names until you either find a match or hit the NULL pointer at the end of the dictionary), + and add a word to the dictionary (create a new definition, set its LINK to LATEST, and set + LATEST to point to the new word). We'll see precisely these functions implemented in + assembly code later on. + + One interesting consequence of using a linked list is that you can redefine words, and + a newer definition of a word overrides an older one. This is an important concept in + FORTH because it means that any word (even "built-in" or "standard" words) can be + overridden with a new definition, either to enhance it, to make it faster or even to + disable it. However because of the way that FORTH words get compiled, which you'll + understand below, words defined using the old definition of a word continue to use + the old definition. Only words defined after the new definition use the new definition. + + DIRECT THREADED CODE ---------------------------------------------------------------------- + + Now we'll get to the really crucial bit in understanding FORTH, so go and get a cup of tea + or coffee and settle down. It's fair to say that if you don't understand this section, then you + won't "get" how FORTH works, and that would be a failure on my part for not explaining it well. + So if after reading this section a few times you don't understand it, please email me + (rich@annexia.org). + + Let's talk first about what "threaded code" means. Imagine a peculiar version of C where + you are only allowed to call functions without arguments. (Don't worry for now that such a + language would be completely useless!) So in our peculiar C, code would look like this: + + f () + { + a (); + b (); + c (); + } + + and so on. How would a function, say 'f' above, be compiled by a standard C compiler? + Probably into assembly code like this. On the right hand side I've written the actual + 16 bit machine code. + + f: + CALL a E8 08 00 00 00 + CALL b E8 1C 00 00 00 + CALL c E8 2C 00 00 00 + ; ignore the return from the function for now + + "E8" is the x86 machine code to "CALL" a function. In the first 20 years of computing + memory was hideously expensive and we might have worried about the wasted space being used + by the repeated "E8" bytes. We can save 20% in code size (and therefore, in expensive memory) + by compressing this into just: + + 08 00 00 00 Just the function addresses, without + 1C 00 00 00 the CALL prefix. + 2C 00 00 00 + + [Historical note: If the execution model that FORTH uses looks strange from the following + paragraphs, then it was motivated entirely by the need to save memory on early computers. + This code compression isn't so important now when our machines have more memory in their L1 + caches than those early computers had in total, but the execution model still has some + useful properties]. + + Of course this code won't run directly any more. Instead we need to write an interpreter + which takes each pair of bytes and calls it. + + On an i386 machine it turns out that we can write this interpreter rather easily, in just + two assembly instructions which turn into just 3 bytes of machine code. Let's store the + pointer to the next word to execute in the %esi register: + + 08 00 00 00 <- We're executing this one now. %esi is the _next_ one to execute. + %esi -> 1C 00 00 00 + 2C 00 00 00 + + The all-important x86 instruction is called LODSL (or in Intel manuals, LODSW). It does + two things. Firstly it reads the memory at %esi into the accumulator (%eax). Secondly it + increments %esi by 4 bytes. So after LODSL, the situation now looks like this: + + 08 00 00 00 <- We're still executing this one + 1C 00 00 00 <- %eax now contains this address (0x0000001C) + %esi -> 2C 00 00 00 + + Now we just need to jump to the address in %eax. This is again just a single x86 instruction + written JMP *(%eax). And after doing the jump, the situation looks like: + + 08 00 00 00 + 1C 00 00 00 <- Now we're executing this subroutine. + %esi -> 2C 00 00 00 + + To make this work, each subroutine is followed by the two instructions 'LODSL; JMP *(%eax)' + which literally make the jump to the next subroutine. + + And that brings us to our first piece of actual code! Well, it's a macro. */ /* NEXT macro. */ @@ -23,6 +277,165 @@ And about je/jne/ja/jb/jbe/etc jmp *(%eax) .endm +/* The macro is called NEXT. That's a FORTH-ism. It expands to those two instructions. + + Every FORTH primitive that we write has to be ended by NEXT. Think of it kind of like + a return. + + The above describes what is known as direct threaded code. + + To sum up: We compress our function calls down to a list of addresses and use a somewhat + magical macro to act as a "jump to next function in the list". We also use one register (%esi) + to act as a kind of instruction pointer, pointing to the next function in the list. + + I'll just give you a hint of what is to come by saying that a FORTH definition such as: + + : QUADRUPLE DOUBLE DOUBLE ; + + actually compiles (almost, not precisely but we'll see why in a moment) to a list of + function addresses for DOUBLE, DOUBLE and a special function called EXIT to finish off. + + At this point, REALLY EAGLE-EYED ASSEMBLY EXPERTS are saying "JONES, YOU'VE MADE A MISTAKE!". + + I lied about JMP *(%eax). + + INDIRECT THREADED CODE ---------------------------------------------------------------------- + + It turns out that direct threaded code is interesting but only if you want to just execute + a list of functions written in assembly language. So QUADRUPLE would work only if DOUBLE + was an assembly language function. In the direct threaded code, QUADRUPLE would look like: + + +------------------+ + | addr of DOUBLE --------------------> (assembly code to do the double) + +------------------+ NEXT + %esi -> | addr of DOUBLE | + +------------------+ + + We can add an extra indirection to allow us to run both words written in assembly language + (primitives written for speed) and words written in FORTH themselves as lists of addresses. + + The extra indirection is the reason for the brackets in JMP *(%eax). + + Let's have a look at how QUADRUPLE and DOUBLE really look in FORTH: + + : QUADRUPLE DOUBLE DOUBLE ; + + +------------------+ + | codeword | : DOUBLE DUP + ; + +------------------+ + | addr of DOUBLE ---------------> +------------------+ + +------------------+ | codeword | + | addr of DOUBLE | +------------------+ + +------------------+ | addr of DUP --------------> +------------------+ + | addr of EXIT | +------------------+ | codeword -------+ + +------------------+ %esi -> | addr of + --------+ +------------------+ | + +------------------+ | | assembly to <-----+ + | addr of EXIT | | | implement DUP | + +------------------+ | | .. | + | | .. | + | | NEXT | + | +------------------+ + | + +-----> +------------------+ + | codeword -------+ + +------------------+ | + | assembly to <------+ + | implement + | + | .. | + | .. | + | NEXT | + +------------------+ + + This is the part where you may need an extra cup of tea/coffee/favourite caffeinated + beverage. What has changed is that I've added an extra pointer to the beginning of + the definitions. In FORTH this is sometimes called the "codeword". The codeword is + a pointer to the interpreter to run the function. For primitives written in + assembly language, the "interpreter" just points to the actual assembly code itself. + + In words written in FORTH (like QUADRUPLE and DOUBLE), the codeword points to an interpreter + function. + + I'll show you the interpreter function shortly, but let's recall our indirect + JMP *(%eax) with the "extra" brackets. Take the case where we're executing DOUBLE + as shown, and DUP has been called. Note that %esi is pointing to the address of +. + + The assembly code for DUP eventually does a NEXT. That: + + (1) reads the address of + into %eax %eax points to the codeword of + + (2) increments %esi by 4 + (3) jumps to the indirect %eax jumps to the address in the codeword of +, + ie. the assembly code to implement + + + +------------------+ + | codeword | + +------------------+ + | addr of DOUBLE ---------------> +------------------+ + +------------------+ | codeword | + | addr of DOUBLE | +------------------+ + +------------------+ | addr of DUP --------------> +------------------+ + | addr of EXIT | +------------------+ | codeword -------+ + +------------------+ | addr of + --------+ +------------------+ | + +------------------+ | | assembly to <-----+ + %esi -> | addr of EXIT | | | implement DUP | + +------------------+ | | .. | + | | .. | + | | NEXT | + | +------------------+ + | + +-----> +------------------+ + | codeword -------+ + +------------------+ | + now we're | assembly to <------+ + executing | implement + | + this | .. | + function | .. | + | NEXT | + +------------------+ + + So I hope that I've convinced you that NEXT does roughly what you'd expect. This is + indirect threaded code. + + I've glossed over four things. I wonder if you can guess without reading on what they are? + + . + . + . + + My list of four things are: (1) What does "EXIT" do? (2) which is related to (1) is how do + you call into a function, ie. how does %esi start off pointing at part of QUADRUPLE, but + then point at part of DOUBLE. (3) What goes in the codeword for the words which are written + in FORTH? (4) How do you compile a function which does anything except call other functions + ie. a function which contains a number like : DOUBLE 2 * ; ? + + THE INTERPRETER AND RETURN STACK ------------------------------------------------------------ + + Going at these in no particular order, let's talk about issues (3) and (2), the interpreter + and the return stack. + + Words which are defined in FORTH need a codeword which points to a little bit of code to + give them a "helping hand" in life. They don't need much, but they do need what is known + as an "interpreter", although it doesn't really "interpret" in the same way that, say, + Java bytecode used to be interpreted (ie. slowly). This interpreter just sets up a few + machine registers so that the word can then execute at full speed using the indirect + threaded model above. + + One of the things that needs to happen when QUADRUPLE calls DOUBLE is that we save the old + %esi ("instruction pointer") and create a new one pointing to the first word in DOUBLE. + Because we will need to restore the old %esi at the end of DOUBLE (this is, after all, like + a function call), we will need a stack to store these "return addresses" (old values of %esi). + + As you will have read, when reading the background documentation, FORTH has two stacks, + an ordinary stack for parameters, and a return stack which is a bit more mysterious. But + our return stack is just the stack I talked about in the previous paragraph, used to save + %esi when calling from a FORTH word into another FORTH word. + + In this FORTH, we are using the normal stack pointer (%esp) for the parameter stack. + We will use the i386's "other" stack pointer (%ebp, usually called the "frame pointer") + for our return stack. + + I've got two macros which just wrap up the details of using %ebp for the return stack: +*/ + /* Macros to deal with the return stack. */ .macro PUSHRSP reg lea -4(%ebp),%ebp // push reg on to return stack @@ -34,6 +447,74 @@ And about je/jne/ja/jb/jbe/etc lea 4(%ebp),%ebp .endm +/* + And with that we can now talk about the interpreter. + + In FORTH the interpreter function is often called DOCOL (I think it means "DO COLON" because + all FORTH definitions start with a colon, as in : DOUBLE DUP + ; + + The "interpreter" (it's not really "interpreting") just needs to push the old %esi on the + stack and set %esi to the first word in the definition. Remember that we jumped to the + function using JMP *(%eax)? Well a consequence of that is that conveniently %eax contains + the address of this codeword, so just by adding 4 to it we get the address of the first + data word. Finally after setting up %esi, it just does NEXT which causes that first word + to run. +*/ + +/* DOCOL - the interpreter! */ + .text + .align 4 +DOCOL: + PUSHRSP %esi // push %esi on to the return stack + addl $4,%eax // %eax points to codeword, so make + movl %eax,%esi // %esi point to first data word + NEXT + +/* + Just to make this absolutely clear, let's see how DOCOL works when jumping from QUADRUPLE + into DOUBLE: + + QUADRUPLE: + +------------------+ + | codeword | + +------------------+ DOUBLE: + | addr of DOUBLE ---------------> +------------------+ + +------------------+ %eax -> | addr of DOCOL | + %esi -> | addr of DOUBLE | +------------------+ + +------------------+ | addr of DUP --------------> + | addr of EXIT | +------------------+ + +------------------+ | etc. | + + First, the call to DOUBLE causes DOCOL (the codeword of DOUBLE). DOCOL does this: It + pushes the old %esi on the return stack. %eax points to the codeword of DOUBLE, so we + just add 4 on to it to get our new %esi: + + QUADRUPLE: + +------------------+ + | codeword | + +------------------+ DOUBLE: + | addr of DOUBLE ---------------> +------------------+ + +------------------+ | addr of DOCOL | + | addr of DOUBLE | +------------------+ + +------------------+ %esi -> | addr of DUP --------------> + | addr of EXIT | +------------------+ + +------------------+ | etc. | + + Then we do NEXT, and because of the magic of threaded code that increments %esi again + and calls DUP. + + Well, it seems to work. + + One minor point here. Because DOCOL is the first bit of assembly actually to be defined + in this file (the others were just macros), and because I usually compile this code with the + text segment starting at address 0, DOCOL has address 0. So if you are disassembling the + code and see a word with a codeword of 0, you will immediately know that the word is + written in FORTH (it's not an assembler primitive) and so uses DOCOL as the interpreter. +*/ + + + + /* ELF entry point. */ .text .globl _start @@ -49,15 +530,6 @@ _start: cold_start: // High-level code without a codeword. .int COLD -/* DOCOL - the interpreter! */ - .text - .align 4 -DOCOL: - PUSHRSP %esi // push %esi on to the return stack - addl $4,%eax // %eax points to codeword, so make - movl %eax,%esi // %esi point to first data word - NEXT - /*---------------------------------------------------------------------- * Fixed sized buffers for everything. */ @@ -317,13 +789,13 @@ var_\name : push %eax // push value onto stack NEXT - defcode "+!",2,ADDSTORE + defcode "+!",2,,ADDSTORE pop %ebx // address pop %eax // the amount to add addl %eax,(%ebx) // add it NEXT - defcode "-!",2,SUBSTORE + defcode "-!",2,,SUBSTORE pop %ebx // address pop %eax // the amount to subtract subl %eax,(%ebx) // add it @@ -398,6 +870,8 @@ var_\name : lea 4(%ebp),%ebp // pop return stack and throw away NEXT +#include + defcode "KEY",3,,KEY call _KEY push %eax // push return value on stack @@ -943,7 +1417,7 @@ buffer: DUP '\"' <> WHILE HERE @ !b \\ store the character in the compiled image - HERE 1 +! \\ increment HERE pointer by 1 byte + 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