/* A sometimes minimal FORTH compiler and tutorial for Linux / i386 systems. -*- asm -*-
By Richard W.M. Jones <rich@annexia.org> http://annexia.org/forth
This is PUBLIC DOMAIN (see public domain release statement below).
+ $Id: jonesforth.S,v 1.20 2007-09-15 11:21:09 rich Exp $
gcc -m32 -nostdlib -static -Wl,-Ttext,0 -o jonesforth jonesforth.S
-
+*/
+ .set JONES_VERSION,20
+/*
INTRODUCTION ----------------------------------------------------------------------
FORTH is one of those alien languages which most working programmers regard in the same
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)
THE DICTIONARY ----------------------------------------------------------------------
- In FORTH as you will know, functions are called "words", as just as in other languages they
+ 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 +"
|
LATEST
- You shoud be able to see from this how you might implement functions to find a word in
+ 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),
+ 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.
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.
+ i386 machine code.
f:
CALL a E8 08 00 00 00
%esi -> 1C 00 00 00
2C 00 00 00
- The all-important x86 instruction is called LODSL (or in Intel manuals, LODSW). It does
+ 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:
| addr of DOUBLE ---------------> +------------------+
+------------------+ %eax -> | addr of DOCOL |
%esi -> | addr of DOUBLE | +------------------+
- +------------------+ | addr of DUP -------------->
+ +------------------+ | addr of DUP |
| addr of EXIT | +------------------+
+------------------+ | etc. |
- First, the call to DOUBLE causes DOCOL (the codeword of DOUBLE). DOCOL does this: It
+ 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:
| addr of DOUBLE ---------------> +------------------+
top of return +------------------+ %eax -> | addr of DOCOL |
stack points -> | addr of DOUBLE | + 4 = +------------------+
- +------------------+ %esi -> | addr of DUP -------------->
+ +------------------+ %esi -> | addr of DUP |
| addr of EXIT | +------------------+
+------------------+ | etc. |
+--|------+---+---+---+---+------------+
| LINK | 3 | D | U | P | code_DUP ---------------------> points to the assembly
+---------+---+---+---+---+------------+ code used to write DUP,
- ^ len codeword which is ended with NEXT.
+ ^ len codeword which ends with NEXT.
|
LINK in next word
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
defcode "-",1,,SUB
pop %eax // get top of stack
- subl %eax,(%esp) // and subtract if from next word on stack
+ subl %eax,(%esp) // and subtract it from next word on stack
NEXT
defcode "*",1,,MUL
_Z
S0 Stores the address of the top of the parameter stack.
R0 Stores the address of the top of the return stack.
+ VERSION Is the current version of this FORTH.
*/
defvar "STATE",5,,STATE
defvar "_Z",2,,TZ
defvar "S0",2,,SZ
defvar "R0",2,,RZ,return_stack
+ defvar "VERSION",7,,VERSION,JONES_VERSION
/*
RETURN STACK ----------------------------------------------------------------------
and compiling code, we might be reading words to execute, we might be asking for the user
to type their name -- ultimately it all comes in through KEY.
- The implementation of KEY uses an input buffer so a certain size (defined at the end of the
+ 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
So if DOUBLE is defined in the dictionary, then WORD DOUBLE FIND returns the following pointer:
- pointer to this
+ pointer to this
|
|
V
/*
FIND returns the dictionary pointer, but when compiling we need the codeword pointer (recall
- that FORTH definitions are compiled into lists of codeword pointers).
+ 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:
- In the example below, WORD DOUBLE FIND >CFA
+ WORD DOUBLE FIND >CFA
FIND returns a pointer to this
| >CFA converts it to a pointer to this
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
Now we'll talk about how FORTH compiles words. Recall that a word definition looks like this:
- : DOUBLE DUP + ;
+ : DOUBLE DUP + ;
and we have to turn this into:
LATEST points here points to codeword of DUP
There are several problems to solve. Where to put the new word? How do we read words? How
- do we define : (COLON) and ; (SEMICOLON)?
+ 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 in your own code.
+ 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
- points (using >CFA) and deciding what to do with them. What it does depends on the mode
- of the interpreter (in variable STATE). When STATE is zero, the interpreter just runs
- each word as it looks them up. (Known as immediate mode).
+ 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.
The interesting stuff happens when STATE is non-zero -- compiling mode. In this mode the
- interpreter just appends the codeword pointers to user memory (the HERE variable points to
- the next free byte of user memory).
+ interpreter appends the codeword pointer to user memory (the HERE variable points to the next
+ free byte of user memory).
So you may be able to see how we could define : (COLON). The general plan is:
(1) Use WORD to read the name of the function being defined.
- (2) Construct the dictionary entry header in user memory:
+ (2) Construct the dictionary entry -- just the header part -- in user memory:
- pointer to previous word (from LATEST) +-- Afterwards, HERE points here, where
+ pointer to previous word (from LATEST) +-- Afterwards, HERE points here, where
^ | the interpreter will start appending
| V codewords.
+--|------+---+---+---+---+---+---+---+---+------------+
+---------+---+---+---+---+---+---+---+---+------------+
len pad codeword
- (3) Set LATEST to point to the newly defined word and most importantly leave HERE pointing
- just after the new codeword. This is where the interpreter will append codewords.
+ (3) Set LATEST to point to the newly defined word, ...
- (4) Set STATE to 1. Go into compile mode so the interpreter starts appending codewords.
+ (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:
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.
+ 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_.
- I hope I don't need to explain that ; (SEMICOLON) is an IMMEDIATE flagged word. 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). After executing ; we get this:
+ I hope I don't need to explain that ; (SEMICOLON) is just such a word, flagged 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 |
|
HERE
- And that's it, job done, our new definition is compiled.
+ 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
NEXT
/*
- IMMEDIATE mode words aren't just for the FORTH compiler to use. You can define your
- own IMMEDIATE words too. 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.
+ 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:
...definition...
; IMMEDIATE
- The two are basically equivalent.
+ The two usages are equivalent, to a first approximation.
*/
defcode "IMMEDIATE",9,F_IMMED,IMMEDIATE
and immediate mode).
This definition of ' uses a cheat which I copied from buzzard92. As a result it only works in
- compiled code.
+ 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.
BRANCH is an unconditional branch. 0BRANCH is a conditional branch (it only branches if the
top of stack is zero).
- This is how BRANCH works. When BRANCH executes, %esi starts by pointing to the offset:
+ 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 |
0BRANCH is the same except the branch happens conditionally.
- Now standard FORTH words such as IF, THEN, ELSE, WHILE, REPEAT, etc. are implemented entirely
+ 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.
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
+ addl $3,%esi // but round up to next 4 byte boundary
andl $~3,%esi
NEXT
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).
+ INTERPRETER is the FORTH interpreter ("toploop", "toplevel" or "REPL" might be a more accurate
+ description -- see: http://en.wikipedia.org/wiki/REPL).
*/
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 pops the status off the stack and exits the process (using Linux exit syscall).
+ SYSEXIT exits the process using Linux exit syscall.
*/
defcode "CHAR",4,,CHAR
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 user input.
+ 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:
.data
.align 4096
buffer:
- // Multi-line constant 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 ;
\\ 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, ...
+\\ ..., LITSTRING, string length, string rounded up to 4 bytes, EMITSTRING, ...
: .\" IMMEDIATE
STATE @ \\ compiling?
IF
\\ ALLOT is used to allocate (static) memory when compiling. It increases HERE by
\\ the amount given on the stack.
-: ALLOT HERE +! ;
+\\: ALLOT HERE +! ;
\\ Finally print the welcome prompt.
+.\" JONESFORTH VERSION \" VERSION @ . CR
.\" OK \"
"
git.annexia.org / jonesforth.git / blobdiff